SICP 05A - Assignment

• Date: [2021-03-11 gio 23:45]

• Link: Lecture 5A | MIT 6.001 Structure and Interpretation, 1986

• Table of contents:

So far we have used a language without any assignment statements. Today we are going to do something horrible: we are going to add an assignment statements.

Why we would ever add such a bad thing (assignments), if we could do much without it? In terms of adding new features to our language, we should always follow this rule: we're only going to add a new feature to our language because there are good reasons to do so.

In this case, the ability you get from assignments is that with assignment statements you are able to break a problem into particular pieces in a way that you woulnd't be able to do without them. In other words, assignments give you another means of decomposition.

So far we have written functional programs, which sort-of encode mathematical truths. For example consider the following factorial procedure

(define (fact n)
  (cond ((= n 1) 1)
        (else (+ n (fact (- n 1))))))

which encodes the following mathematical definition:

\[\forall n \in \mathbb{N}: \;\;\; n! := \begin{cases} 1 \,\,&,\,\, n = 1 \\ n \cdot (n-1)! \,\,&,\,\, n \geq 1 \\ \end{cases}\]

Whenever we work with statements of this sort, we can understand exactly how the process evolves by applying the substitution model to the procedure definition.

(fact 4)
(* 4 (fact 3))
(* 4 (* 3 (fact 2)))
(* 4 (* 3 (* 2 (fact 1))))
(* 4 (* 3 (* 2 1)))
(* 4 (* 3 2))
(* 4 6)
24

Notice that in each step of the substitution process, an underlying truth is preserved. That is, we go from true statament to true statement, until we get our answer.

There might be different ways of expressing true statements. These different ways may evolve into different processes. This is the case for the sum procedure, which can be express both by a recursive process

(define (+ n m)
  (cond ((= n 0) m)
        (else (1+ (+ (-1+ n) m)))))

which encodes this mathematical rule

\[n + m = \begin{cases} m \;\;&, \;\; n = 0 \\ ((n - 1) + m) + 1 \;\;&,\;\; n > 0 \\ \end{cases}\]

as well as by an iterative process

(define (+ n m)
  (cond ((= n 0) m)
        (else (+ (-1+n) (1+ m)))))

which encodes this other mathematical rule

\[n + m = \begin{cases} m \;\;&, \;\; n = 0 \\ (n-1) + (m+1) \;\;&,\;\; n > 0 \\ \end{cases}\]

With this sort of scaffolding we have the flexibility to talk about both the function being computed as well as the method by which we compute it.

The syntax used for the assignment operator is described as follows

(set! <var> <value>)   

Its worth notice that the syntax "set!" with the escalmation mark at the end is only useful to humans reading the code, and not the machine interpreting it. It means "this is an assignment operator, be careful!"

By introducing the assignment operation we inevitably introduce the notion of time. That is, now there is a time when something happens. That "something" is exactly that assignment operation. Said in another way, an assignment is the first thing we have that produces the difference between a before and an after

Thus we get

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

such that after the operation <var> has the value <value> .

Think about the factorial procedure, and think about how it is essentially the same as the function, because anywhere I write it, anytime I write it, I always get the same answer. Independent of what context its in, it uniquely maps the arguments to the answer.

When we introduce assignments, this is no longer the case. Consider the following procedure

(define count 1)

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

Let us execute it: the first time we execute it we get an answer of \(5\), because initially count is \(1\). But then, if I execute it again, I get an answer of \(6\). Thus, the same expression leads to two different answers depending upon time. This means that this procedure is not a function anymore.

(demo 3) ;; returns 5
(demo 3) ;; returns 6

This is also the first place where the substituion model doesn't work anymore, because the substitution model only allows to model static phenomenons, and with the introduction and usage of assignment we have a dynamic processes which evolves over time.

Consider the demo procedure, if we substitute the same value on both istances of the name count we get a wrong answer, because in reality they contain different values.

The substitution model describes static truths. Here instead we have truths that change. The new model we'll have to work with has to treat such variables differently. In particular, variables will no longer be referred to the values they have, but rather to some sort of place where the value is stored.

Let us write the functional version of factorial by an iterative process

(define (fact n)
  (define (fact-iter cur i)
    (if (eq? i n)
        cur
        (fact-iter (* cur i) (+ i 1))))
  (fact-iter 1 1))

Let us now write a similar sort of program but with assignments, which we will call the 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)))

The substitution model says to "copy" the body of the procedure in which the formal parameters are substituted by the arguments. In this imperative version instead I'm not worried about copying, because I'm changing the values of both i and m .

Notice however that in the imperative version I can make more mistakes than in the functional version. For example, if I interchange the assignments between m and i , then the procedure would not compute the same values as before. This is because m depends on the previous value of i .

Thus, in order to introduce this new statament we need:

1. A new model of computation that allows us to understand what is going on;

2. A damn good reason for introducing such a statement.

Observation 1: Notice that define is used to set the value of something the first time. With only defines you cannot change the state of the program, because define happens only once for everything.

Observation 2: The let expression is simply an applied lambda expression, that is

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

is equivalent to

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

We will now create a new model of computation. This new model is much more complicated than the substitution model and its called the environment model.

What is an object?

We like to think in terms of objects because it is economical. When I say "I'm an object", and "you are an object", we are separating the world into two pieces. The world thus becomes easy to reason about. Yes, its true that two objects are never really independent from eachothers in an absolute sense, but still, it is also true that most of the variables that define my state are decoupled from the variables that define your state, and therefore we can think of them as being independent of eachothers. With this approach instead of having the cartesian product of the two state variables sets, we can simply "sum" them.

The bugs that we see in quantum mechanims are mainly due to the fact that we are made to think that things are broken up in independent pieces, while there is actually more coupling than we see in the surfaces.

If I take two integers at random \(n_1\), \(n_2\), and consider their gcd, it can either by \(1\) or not \(1\). The probability that two random numbers have gcd equal to \(1\) is related to \(\pi\) in the following way

\[P\Big(\text{gcd}(n_1, n_2) = 1\Big) = \frac{6}{\pi^2}\]

we can thus approximate \(\pi\) by estimating such probability. And to estimate such probability we can do lots of experiments and compute the ratio between those that succeed and those that fail.