💾 Archived View for gnebbia.net › notes › sicp › sections › 2_substitution_model.gmi captured on 2023-11-04 at 11:42:42. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2023-01-29)
-=-=-=-=-=-=-
In this section we analyze how procedures that we write affect processes
in a machine. We learn about linear iteration, linear recursion and
tree recursion processes. All these processes are all built using
recursive procedures since in Lisp this is very natural and used as a
common approach.
In order to understand how procedures affect processes we use the
until we introduce a more complex model to understand how procedures
are managed within a machine.
This model can be thought of as the classical mechanics or ideality in
physics, when we are ok with a simplistic approximation. Anyway for some
other scenarios we will find out it is not enough to use the substitution
model and will be forced to deal with a more complex model.
Procedures are made of expressions, which can be of these types:
- Numbers
- Symbols
- Combinations
- Lambda Expressions (special form)
- Definitions (special form)
- Conditionals (special form)
Note that "special form" means that for that kind of expression
we have other specific rules.
Once we have a procedure and a procedure call we can understand what
processes are generated by this procedure call by using the so called
"substitution model".
The steps to evaluate an application and observe the related generated
process can be described with the following steps:
- evaluate the operator to get the procedure;
- evaluate the operands to get the arguments;
- apply the procedure to the arguments:
- if the procedure is compound (not primitive) copy the body of the
procedure substituting the arguments supplied for the formal
parameters of the procedure;
- evaluate the resulting body;
Let's apply the substitution rule to the following
simple procedure.
(define (+ x y)
(if (= x 0)
y
(+ (dec x) (inc y))))
Now let's say the procedure gets called with:
(+ 3 4)
Now to apply the substitution model we can just do:
(+ 3 4) (if (= 3 0) 4 (+ (dec 3) (inc 4))) (+ (dec 3) (inc 4)) (+ (inc 3) 5) (+ 2 5) (if (= 2 0) 5 (+ (dec 2) (inc 5))) (+ (dec 2) (inc 5)) (+ (dec 2) 6) (+ 1 6) (if (= 1 0) 6 (+ (dec 1) (inc 6))) (+ (dec 1) (inc 6)) (+ (dec 1) 7) (+ 0 7) (if (= 0 0) 7 (+ (dec 0) (inc 7))) 7
Our method of evaluation by evaluating operator, evaluating the
operands and then applying the operator is just one possible rule of
evaluation. The ordering we have been using is called "Applicative
Order". An alternative method of evaluation would be to not evaluate
the operand until the value is needed. This method is called "Normal
Order". We can see the difference between these 2 from the following
example:
(square (+ 3 2))
Note that the input to square is (+ 3 2).
Applicative Order:
(square (+ 3 2)) (square 5) (* 5 5) 25
In Applicative Order, you would evaluate the parameter x, before you
go the body of square, which is `(* x x)`. When you evaluate (+ 3 2),
you get 5 and this is what you pass into square. So x is bound to 5.
Normal Order:
(square (+ 3 2)) (* (+ 3 2) (+ 3 2)) (* 5 5) 25
In Normal Order, you don't evaluate (+ 3 2) until you absolutely need
to. So in this case, the x in (square x) is bound to (+ 3 2).
Notice that, in Normal Order, since you don't evaluate the x, which is (+
3 2), until it's needed, you need to evaluate it twice. On the other hand,
in Applicative Order, since you evaluate the operand x before applying
the procedure, you only evaluate (+ 3 2) once.
In this subsection we analyze two procedures which are functionally
identic, but produce a quite different process.
This is imporant because allow us to understand the relation
between a procedure and process and how to evaluate
the result of an applied substitution model.
```scheme
(define (+ x y)
(if (= x 0)
y
(+ (dec x) (inc y))))
Its substitution model for the procedure call `(+ 3 4)` is:
(+ 3 4)
(+ 2 5)
(+ 1 6)
(+ 0 7)
7
# Peano Arithmetic Sum v2 (Recursive Process)
```scheme
(define (+ x y)
(if (= x 0)
y
(inc (+ (dec x) y))))
Its substitution model for the procedure call `(+ 3 4)` is:
(+ 3 4) (inc (+ 2 4)) (inc (inc (+ 1 4))) (inc (inc (inc (+ 0 4)))) (inc (inc (inc (4)))) (inc (inc 5)) (inc 6) 7
These processes have a very different shapes.
Note that the shape of the process is 2d and each dimension has a meaning.
The y axis is time, while the x axis is the space, so amount of things
I have to remember.
This v1 version has a time complexity of O(x) since the number of steps
on the y axis increases linearly with increasing x.
But has a constant complexity in space O(1).
A process which has a linear time complexity and a constant space complexity
is called **iteration process** (linear iteration).
These complexities put a bound, saying that every machine can perform
this procedure with this amount of resources at maximum.
Note that of course we are abstracting details such as how big is a number,
but it doesn't matter since we are at a different level of abstraction.
We could also consider that all the numbers take the same space.
This v2 version has a time complexity of O(x) since the number of steps
on the y axis increases linearly with increasing x.
And the same happens for space, if we increase x we have two more
lines, hence space complexity is also O(x).
A process which has both linear time complexity and space complexity
is called **recursion process** (or linear recursion).
This happens everytime we have a recursive process where two or more
calls to the same function are performed. As an example the fibonacci
sum can be computed very naturally in this way. Although an iterative
version would be more efficient, the tree recursive way is more natural
to design and is very easy to think in recursive terms. Other functions
using tree recursion are functions operating on complex data structures
such as binary trees, b trees, graphs and so on, which have a huge amount
of applications in computer science.
Both iteration and recursion process have been defined using a recursive
definition (with recursive functions), since we call the function itself
in the studied function.
There is nothing special about this, we just have a recursive function
leading to two different process shapes (which have different names).
So the takeaway here is, expressed by the following note.
NOTE: we must be careful not to confuse the notion of a **recursive process**
with the notion of a **recursive procedure**.
In addition to sum up, in this section we have seen the relationship
between procedures and processes, and how to apply the substitution
model to generate the resulting process starting from a procedure and
a procedure call. We have then observed and discussed common different
processes, namely:
- iterative processes;
- linear recursive processes;
- tree recursive processes;