# SICP 5a

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.

<before> (set! <var> <value>) <after>

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)

5

(demo 3)

6

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) (else (set! m (* i m)) (set! i (+ i 1)) (loop)))) (loop)))

Note that `define`

≠ `let`

≠ `set!`

. Two `define`

s are illegal, and `let`

sets
up a scope.

The following two statements are equivalent.

(let ((var1 e1) (var2 e2)) e3) ((lambda (var1 var2) e3) e1 e2)

## 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)) n))) (define c1 (make-counter 0)) (define c2(make-counter 10)) (c1)

1

(c2)

11

(c1)

2

(c2)

12

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

$\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)) ((experiment) (iter (-1+ remaining) (1+ passed))) (else (iter (-1+ remaining) passed)))) (iter trials 0)) (define rand (let ((x random-init)) (lambda () (set! x (rand-update x)) 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) x2)) (else (iter (-1+ remaining) passed x2)))))) (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.

Things are seldom what they seem

Skim milk masquerades as cream…