5A Assignment, State, and Side-Effects⁠

# Part 1

# Introducing assignment

• We’ve learned enough about programming in Lisp to do fairly complex things.
• Today, we’re going to add an assignment statement to the language.
• If we can do so much without it, why should we add it?
• We need to have a good reason for adding a new feature to the language!
• We’re doing it because it gives us a new way of decomposing programs.

# Functional programming

• Functional programs are a kind of encoding of mathematical truths.
• Processes evolved by these programs can be understood by substitution.
• It’s like simplifying an equation. You write a sequence of equalities, preserving truth.

# Assignment and Time

• To do assignment, we use (set! variable value).
• The “!” suffix is a convention for procedures that do assignment-like things.
• Now that we have assignment, we have to consider time.
• Assignment produces a moment in time, which has a before and an after.
• After that moment, variable has the value value, independent of what it was before.
• So far, calling procedures with the same inputs always produced the same outputs.
• With assignment, this is no longer true because the output depends on time.
• The substitution model completely breaks down. It assumes that things don’t change.
• We need a new model of computation for this “bad thing.” We’d better have a good reason for introducing assignment.

# Identity

• Symbols for variables no longer refer directly to their values, but to some place.
• A variable now refers to an identity associated with a series of causally related values.
• The state of an identity is its current associated value.
• When we talk about time, we mean the before/after ordering of causal values.

# Factorial example

• Here’s how we implemented factorial functionally:

(define (fact n)
  (define (iter p i)
    (if (> i n) m (iter (* i p) (+ i 1))))
  (iter 1 1))

• We could instead write it with assignments:

(define (fact n)
  (let ((p 1) (i 1))
    (define (loop)
      (cond ((> i n) p)
            (else (set! p (* i p))
                  (set! i (+ i 1))
                  (loop))))
    (loop)))

• There are ways of making mistakes in the second program that simply didn’t exist when we couldn’t do assignment.
• For example, it produces the wrong answer if we change the order of the assignments.

# Part 2

# Environment model

• We need a new model of computation to understand programs that use assignment.
• The new model is called the environment model.
• Unfortunately, it is significantly more complicated than the substitution model.

# Free and bound variables

• A variable $v$ is bound in an expression $E$ if the meaning of $E$ is unchanged when we replace all occurrences of $v$ by some other variable $w$ not already occuring in $E\htmlClass{math-punctuation}{\text{.}}$
• We use bound variables all the time. In Lisp, variables are bound by lambda.
• If a variable isn’t bound, we say it is a free variable.
• The parts of an expression where a variable has a value defined by a lambda binding is the scope of that variable.

# Environments, frames, and bindings

• Environments are a way of doing substitutions virtually.
• It’s the place where the names of the variables are associated with values:
  • An environment is a pointer to a frame.
  • A frame is a table of bindings, with a pointer to a parent environment.
  • A binding associates a variable name with a value.
• To look up the value of a variable in an environment, we traverse its frames, finding the first one that has a binding for the variable, and read its associated value.
• If a variable is bound twice in an environment, the second shadows the first.

# Procedure creation and application

• A procedure is a pair consisting of some code and an environment.
• We look up free variables in the procedure’s environment.
• To evaluate a lambda expression, we create a new procedure object combining the lambda’s code with the current environment.
• To apply a procedure to arguments:
  1. Construct a new frame whose parent is the procedure’s environment.
  2. Bind the formal parameters of the procedure to the arguments provided.
  3. Evaluate the body of the procedure in the context of the new environment.

# Part 3

# Counter example

• We’ve introduced a very complicated thing, assignment, which destroys most of the interesting mathematical properties of our programs.
• We wouldn’t have done this without a good reason.
• Consider the following program:

(define make-counter
  (lambda (n)
    (lambda ()
      (set! n (inc n))
      n)))

(define c1 (make-counter 0))
(define c2 (make-counter 10))

(c1)
→ 1

(c1)
→ 2

(c2)
→ 11

(c2)
→ 12

• These two counters are independent: they each have their own state.
• The environments of c1 and c2 point to different frames with different bindings for n.
• The parent of both frames is the global environment, which contains built-in procdures like car, +, *, etc., and the top-level definitions make-counter, c1, and c2.

# Objects

• We like to think about the world as being made up of independent, stateful objects.
• The only way to see if two objects are “the same,” not just associated with values that are equal, is to change one and see if the other changes in the same way.
• The idea of objects, change, and sameness raises deep philosophical problems.

# Actions and identity

• An action $A$ has an effect on an object $x$ (or equivalently, $x$ was changed by $A\htmlClass{math-punctuation}{\text{)}}$ if some property which was true of $x$ before $A$ became false after.
• We consider two objects to be the same if any action that has an effect on one has the same effect on the other.

# Uses of objection orientation

• One of the nice things about objects is the way they let us model the world.
• The modularity of the world can give us modularity in our programming.
• For example, in the Monte Carlo program from § 3.1.2, using the assignment statement for random number generation greatly enhances modularity.
• But for most things, objects and assignment are not the right way to think. We should only use them if we need them.