💾 Archived View for gemini.lostleonardo.xyz › sicp › lecture-1B.gmi captured on 2021-11-30 at 20:18:30. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
The job of a programmer is to design processes that accomplish particular goals. The programmer does this by constructing programs (out of procedures and expressions) that direct processes.
In order to do this effectively, the programmer has to understand the relationship between the procedures that he writes and the process that he is attempting to control. What we are going to establish in this lecture is that particular patterns of procedures and expressions cause particular patterns of execution.
If we are going to understand processes and how we control them, then we have to have a mapping from the mechanisms of the procecures to the processes that those procedures yield. In other words, we need a formal or semi-formal mechnical model that illustrates how a machine /could/ do this in principle. Whether or not the machine really works that way is irrelevant. This is an engineering model; it only needs to be approximately true.
The substitution model is the simplest way we have of understanding how procedures yield processes.
Kinds of expressions
In the substitution model, numbers evaluate to themselves and symbols disappear. The only piece of complexity derives from how we evaluate combinations.
To evaluate an application,
evaluate the operator to get a procedure,
evaulate the operands to get the arguments,
Then apply the procedure to the arguments by copying the body of the proc
substituting the arguments supplied for the formal parameters of the
Then evaluate the new body.
"At any level of detail, if you look inside this machine, you are going to find that there are multiple levels below that you don't know about, but one of the things we have to learn how to do is to ignore details. The key to understanding complicated things is to know what not to look at, and what not to compute, and what not to think".
The basic method of doing substitution is a good enough model for understanding how the machine works at some level of analysis.
To evaluate an IF expression,
evaluate the predicate expression
if it yields TRUE
evaluate the consequent expression
otherwise
evaluate the alternative expression
(IF <predicate>
<consequent>
<alternative>)
"It is important to get names for the parts of expressions. One of the things that every sorcerer will tell you is that if you have the name of a spirit, you have power over it".
There is presumably some large library of primitive operations that are simply available, but ultimately it does not matter that they are primitive, it matters that you know what they do.
A computational model is a reasonably mechanical way of describing how a program made out of procedures and expressions evolves a process.
Processes have different shapes
The number of steps is an approximation of how much time a problem takes.
The amount that you need to remember is an approximation of the how much memory the problem takes.
Iterative process (linear iteration) - constant space
complexity
Recursive process (linear recursion) - linear space complexity
An iteration is a process that has all of its state in explicit variables.
"Now you have a feeling for two different types of processes that can be evolved from almost the same program".
Does the 'iterative' nature of the process derive from the fact that alternative parameters are passed into each recursive procedure call? I presume that this is the equivalent of changing the state of a local variable in a more imperative language.
"How a program represents itself as the rules for the evolution of a process".
The recursive fibonnaci procedure breaks down into two parts - under some condition then the node breaks up into two parts or there is another reduction. At each step, the process that gets built is an instance of a particular rule.
"The reason people think of programming as being hard is because at every instance you are writing down a general rule, which is going to be used for lots of instances, that is going to control a particular instance for you... this is why it helps to break processes down into composable chunks".
Each procedure of a recursive algorithm performs a reduction step, which resolves to a simpler problem that then reduces and reduces until you arrive at some base case.
"The way in which you would construct a recursive process is by wishful thinking; you have to believe".
The naive way of making these moves will produce an exponential tree walk.