Assignment, State & Side-effects

Table of Contents

1 Assignment

Today, we're going to do something horrible: we're going to add an assignment statement.

New features should provide new means of decomposition. So far, all of the programs have been functional; they have encoded mathamatical truths. Processes evolved by such programs can be understood by substitution.

(set! <var> <value>)

Note: Similar to how ? denotes predicate procedure, ! denotes assignment-like things.

By introducing assignment, time is now introduced. var has a different state before and after.

(define count 1)
(define (demo x)
  (set! count (1+ count))
  (+ x count))
(demo 3)
(demo 3)

To show the difference between functional and imperative, let's see how the factorial procedures differ.

Functional version:

(define (fact n)
  (define (iter m i)
    (cond ((> i n) m)
          (else (iter (* i m) (+ i 1)))))
  (iter 1 1))

Imperative version:

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

Note that defineletset!. Two define​s are illegal, and let sets up a scope.

The following two statements are equivalent.

(let ((var1 e1) (var2 e2))

((lambda (var1 var2)

2 Environment model

The substitution model is dead. Long live the environment model.

2.1 Bound variables

We say that a variable, v, is bound in an expression, e, if the meaning of e is unchanged by the uniform replacement of a variable, w not occurring in e for every occurrence of v in e.

2.2 Free variables

We say that a variable, v, is free in an expression, e, if the meaning of e is changed by the uniform replacement of a variable, w not occurring in e for every occurrence of v in e.

In the following expression, x is bound, y is free.

(lambda (x) (* x y))

In the following expression, * is a free variable.

(lambda (y) ((lambda (x) (* x y)) 3))

2.3 Bound variable list

If x is a bound variable in e then there is a lambda expression where it is bound. We call the list of formal parameters of the lambda expression the bound variable list and we say that the lambda expression binds the variables declared in its bound variable list. In addition, those parts of the expression, where a variable has a value defined by the lambda expression which binds it, is called the scope of the variable.

2.4 Environment rules

An environment is a sequence of frames linked together.

2.4.1 Rule 1

A procedure object is applied to a set of arguments by constructing a frame, binding the formal parameters of the procedure to the actual arguments of the call, and then evaluating the body of the procedure in the context of the new environment constructed. The new frame has as its enclosing environment part of the procedure object being applied.

2.4.2 Rule 2

A lambda expression is evaluated relative to a given environment as follows: a new procedure object is formed, combining the text (code) of the lambda-expression with a pointer to the environment of evaluation.

3 Objects

Assignment allows us to create separate objects.

(define make-counter
  (lambda (n)
    (lambda ()
      (set! n (1+ n))
(define c1 (make-counter 0))
(define c2(make-counter 10))

By introducing assignment and objects, we have opened ourselves up to all of the horrible questions of philosophy that have been plaguing philosophers for some thousands of years.

Don't use assignment when it can be avoided - it's the wrong way to think.

3.1 Actions and identity

We say that an action, a had an effect on an object, x, (or equivalently, that x was changed by a) if some property, p, which was true of x before a became false of x after a.

We say that two objects, x and y, are the same if any action which has an effect on x has the same effect on y.

4 Cesàro's method for estimating pi

Prob ( gcd ( n 1 , n 2 ) = 1 ) = 6 π 2 fragments Prob fragments ( gcd fragments ( n 1 , n 2 ) 1 ) 6 superscript 𝜋 2 \text{Prob}(\text{gcd}(n1,n2)=1)=\frac{6}{\pi^{2}}

The proof can be found here.

(define (estimate-pi n)
  (sqrt (/ 6 (monte-carlo n cesaro))))
(define (cesaro)
  (= (gcd (rand) (rand)) 1 ))
(define (monte-carlo trials experiment)
  (define (iter remaining passed)
    (cond ((= remaining 0)
           (/ passed trials))
           (iter (-1+ remaining)
                 (1+ passed)))
           (iter (-1+ remaining)
  (iter trials 0))
(define rand
  (let ((x random-init))
    (lambda ()
      (set! x (rand-update x))

rand-update is a screwy function, details of which can be found in Knuth's books.

If assignment isn't available, the procedure is a lot worse: it's monolithic.

(define (estimate-pi n)
  (sqrt (/ 6 (random-gcd-test n))))
(define (random-gcd-test trials)
  (define (iter remaining passed x)
    (let ((x1 (rand-update x)))
      (let ((x2 (rand-update x1)))
        (cond ((= remaining 0)
               (/ passed trials))
              ((= (gcd x1 x2) 1)
               (iter (-1+ remaining)
                     (1+ passed)
               (iter (-1+ remaining)
  (iter trials 0 random-seed))

The state of the random number generator is no longer confined to the inside of the random number generator - it has leaked out. Leaked out into cesaro, and then into monte-carlo, meaning none of the functions ca be written generally. The assignment version is evidently vastly superior.

Plus ça change, plus c'est la même chose.

Alphonse Kaar

Things are seldom what they seem
Skim milk masquerades as cream…

Gilbert and Sullivan, H.M.S. Pinafore