💾 Archived View for gemini.lostleonardo.xyz › sicp › lecture-5A.gmi captured on 2022-07-16 at 13:29:42. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2021-11-30)
-=-=-=-=-=-=-
"Today we're going to do something horrible, we're going to add an assigmment statement"
Functional programs enocode mathematical truths > processes evolved by such programs can be understood by substitution > methods may be distinguished by the choice of truths expressed (recursive and iterative processes that compute the same answer are equivalent mathematical truths).
The way you choose and arrage those truths (operations) detemines the process that is evolved. This gives us the flexibility to talk about the function to be computed and the method by which it is computed, so it is not clear we would need more.
"However, today, I am going to do this awful thing, I am going to introduce this assigment operation"
(SET! <variable> <value>)
The implication of assigment is that there is a time at which something happens. The order of evaluation doesn't matter in programs without assigment statements. But assigment is special - it produces a moment in time, such that after a moment in time, the <variable> has the value <value>. SET! changes the value of the variable. Until this moment, we had nothing that changed.
The procedure that we write for the function factorial is pretty much identical to the function factorial. Independent of what context it is in and no matter how many times I run it I always get the same answer.
A function is a unique map from the argument to the answer/value.
Once you have assigment, you no longer have functions. The same expression can lead to two different answers, depending on time at which it runs. This kills the substitution model dead.
The substitution model is a static phenomenon, it describes things that are true, not things that change. As such, we are going to need a new model of computation.
Symbols like 'count or 'x are no longer going to refer to the values that they have but to some place where the value is stored.
"It's going to be a very bad thing and cause a lot of trouble. The very fact that we are inventing this bad thing means that there better be a good reason for it".
In an iterative recursive procedure, new values are assigned to the variables every time you recur.
The substitution model is a purely mathematical description, it does not describe how the computer actually works.
You can write an imperative version of the same process... before he says it, where I think he is going, the big benefit is the ability to package things together - you can package the variables (data) with the procedure, rather than passing the data as arguments every time you loop.
The difference between assignment (the environemnt model) and the substitution model:
"The substitution model says that you copy the body of the procedure with the arguments substituted for the formal parameters. Here, I am not worrying about copying, I am changing the values of the variables."
There are possibilities for error that did not exist in the substitution model becuase our model now has time in it. For instance, if the transpose the order of procedures, you can compute something different. In the substitution model procedures compute the same value regardless of when or how many times they are run.
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 occuring in E, for every occurance of V in E.
The meaning of the expression does not depend on the particular letters used to describe x and y. As in algebra, it's still the same expression, regardless of the symbol. This should be a familiar idea to those who have played a bit with mathematics.
Quantifier - a symbol that binds a variable.
In Scheme, LAMBDA is the (quantifier) essential thing that binds variables.
(LAMBDA (y) ((LAMBDA (x) (* x y)) 3))
equivalent
(LAMBDA (y) ((LAMBDA (z) (* z y)) 3))
Each LAMBDA binds the variables in the brackets that follow.
In the following expression y is not bound.
(LAMBDA (x) (* x y))
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 occuring in E, for every occurance of V in E.
If X is a bound variable in E then there is a lambda expression where it is bound. We call the list of formal paramaters 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.
The only thing that can make a name is a lambda expression.
The region over which a variable is defined.
Really the only things that makes names is a lambda. That is kind of its job. The other amazing thing is that you can compute with only lambda.
"Now we enough terminology to begin to understand how to make a new model for computation because the key thing going on here is that we have destroyed the substitution model and we now have to have a model that represents names as referring to places. If we going to change something then we have to have a place where it is stored"
An environment is a way of doing substutions virtually; it represents a place where something is stored which is the substitutons that you haven't done. It is the place where the names of the variables are associated with the variables that they have, so environment is a function or a table made out of things called frames. Frames are chained together by parent links. The frames correspond to the application's procedures.
A procedure is made out of two parts - the first part refers to a set of instructions and the second part is an environment, and we use this to capture the free variables that occur in this procedure.
Rule 1: A procedure object is applied to a set of arguments by constructing a new frame, binding the formal paramaters 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 the environment part of the procedure object being applied.
The environment pointer captures the place where the lambda expression was evaluated, where the definition was used to make the procedure.
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 the evaluation.
This is our new model for understanding the execution of programs.
The environment is a linked chain of frames.
"The way I like to think about it as the pointer to the first one, because once you've got that you've got all of them"
"I've done this terrible thing to you. I've introduced a very complicated thing - assignment - which destroys most of the interesting mathematical properties of our programs".
In order to investigate the behviour of a computation, you now have to make an environment model because programs cannot now be understood any other way.
There is a global environment the computer is born with... and it will have in it a bunch of initial things...
Global - +: *: -: /: cons: car: cdr:
Computation happens relative to the global environment, so first you need a pointer to the global environment, then you need a procedure object. Evaluating the procedure adds that procedure (or a pointer to that procedure) to the global environment.
Evaluating a procedure
What we have now are computational objects, each with their own independent local state.
"We like to think in terms of objects because it is economical to think that way".
Objects are not just things in the world, objects are entities that have behaviours/operations.
"How would we know if we have objects?"
"By introducing assignment and objects, we have opened ourselves up to all the horrible questions of philosophy that have been plaguing philosophers for some thousands of years".
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.
That's you're assignment statement - state change denotes a moment in time - before and after.
"We like to think about the world as being comprised of independent objects with independent local state".
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.
"Modularity can be enhanced by using an assignment statement judiciously".
"However, objects are very useful, for the sake of intellectual economy".
"We want there to be isomorphism between the objects in the world and the objects in our mental model... so we invent things like object-oriented programming to provide us with that power"
"The state of the random number generator has leaked out into the procedure that does the Monte Carlo experiment... and the Monte Carlo experiment is no longer general. I've lost the ability to decompose a problem into pieces because I was not willing to add a state variable that was confined to the object".