PROFESSOR: Hi.

You've seen that the job of a programmer is to design

processes that accomplish particular goals, such as

finding the square roots of numbers or other sorts of

things you might want to do.

We haven't introduced anything else yet.

Of course, the way in which a programmer does this is by

constructing spells, which are constructed out of procedures

and expressions.

And that these spells are somehow direct a process to

accomplish the goal that was intended by the programmer.

In order for the programmer to do this effectively, he has to

understand the relationship between the particular things

that he writes, these particular spells, and the

behavior of the process that he's attempting to control.

So what we're doing this lecture is attempt to

establish that connection in as clear a way as possible.

What we will particularly do is understand how particular

patterns of procedures and expressions cause particular

patterns of execution, particular

behaviors from the processes.

Let's get down to that.

I'm going to start with a very simple program.

This is a program to compute the sum of the

squares of two numbers.

And we'll define the sum of the squares of x and y to be

the sum of the square of x--

I'm going to write it that way--

and the square of y where the square of x is the

product of x and x.

Now, supposing I were to say something to this, like, to

the system after having defined these things, of the

form, the sum of the squares of three and four, I am hoping

that I will get out a 25.

Because the square of three is nine, and the square of four

is 16, and 25 is the sum of those.

But how does that happen?

If we're going to understand processes and how we control

them, then we have to have a mapping from the mechanisms of

this procedure into the way in which these processes behave.

What we're going to have is a formal, or semi-formal,

mechanical model whereby you understand how a machine

could, in fact, in principle, do this.

Whether or not the actual machine really does what I'm

about to tell you is completely

irrelevant at this moment.

In fact, this is an engineering model in the same

way that, electrical resistor, we write down a model v equals

i r, it's approximately true.

It's not really true.

If I put up current through the resistor it goes boom.

So the voltage is not always proportional to the current,

but for some purposes the model is appropriate.

In particular, the model we're going to describe right now,

which I call the substitution model, is the simplest model

that we have for understanding how procedures work and how

processes work.

How procedures yield processes.

And that substitution model will be accurate for most of

the things we'll be dealing with in the next few days.

But eventually, it will become impossible to sustain the

illusion that that's the way the machine works, and we'll

go to other more specific and particular models that will

show more detail.

OK, well, the first thing, of course, is we say, what are

the things we have here?

We have some cryptic symbols.

And these cryptic symbols are made out of pieces.

There are kinds of expressions.

So let's write down here the kinds of

expressions there are.

And we have-- and so far I see things like numbers.

I see things like symbols like that.

We have seen things before like lambda expressions, but

they're not here.

I'm going to leave them out.

Lambda expressions, we'll worry about them later.

Things like definitions.

Things like conditionals.

And finally, things like combinations.

These kinds of expressions are--

I'll worry about later--

these are special forms.

There are particular rules for each of these.

I'm going to tell you, however, the rules for doing a

general case.

How does one evaluate a combination?

Because, in fact, over here, all I really have are

combinations and some symbols and numbers.

And the simple things like a number, well, it

will evaluate to itself.

In the model I will have for you, the

symbols will disappear.

They won't be there at the time when you need them, when

you need to get at them.

So the only thing I really have to explain to you is, how

do we evaluate combinations?

OK, let's see.

So first I want to get the first slide.

Here is the rule for evaluating an application.

What we have is a rule that says, to evaluate a

combination, there are two parts, three

parts to the rule.

The combination has several parts.

It has operators and it has operands.

The operator returns into a procedure.

If we evaluate the operator, we will get a procedure.

And you saw, for example, how I'll type at the machine and

out came compound procedure something or other.

And the operands produce arguments.

Once we've gotten the operator evaluated to get a procedure,

and the argument is evaluated to get argument--

the operand's value to get arguments--

we apply the procedure to these arguments by copying the

body of the procedure, which is the expression that the

procedure is defined in terms of.

What is it supposed to do?

Substituting the argument supplied for the formal

parameters of the procedure, the formal parameters being

the names defined by the declaration of the procedure.

Then we evaluate the resulting new body, the body resulting

from copying the old body with the substitutions made.

It's a very simple rule, and we're going to do it very

formally for a little while.

Because for the next few lectures, what I want you to

do is to say, if I don't understand something, if I

don't understand something, be very mechanical and do this.

So let's see.

Let's consider a particular evaluation, the one we were

talking about before.

The sum of the squares of three and three.

What does that mean?

It says, take--

well, I could find out what's on the square-- it's some

procedure, and I'm not going to worry about the

representation, and I'm not going to write it on the

blackboard for you.

And I have that three represents some number, but if

I have to repeat that number, I can't tell you the number.

The number itself is some abstract thing.

There's a numeral which represents it, which I'll call

three, and I'll use that in my substitution.

And four is also a number.

I'm going to substitute three for x and four for y in the

body of this procedure that you see over here.

Here's the body of the procedure.

It corresponds to this

combination, which is an addition.

So what that reduces to, as a reduction step, we call it, is

the sum of the square of three and the square of four.

Now, what's the next step I have to do here?

I say, well, I have to evaluate this.

According to my rule, which you just saw on that overhead

or slide, what we had was that we have to

evaluate the operands--

and here are the operands, here's one and

here's the next operand--

and how we have to evaluate procedure.

The order doesn't matter.

And then we're going to apply the procedure, which is plus,

and magically somehow that's going to produce the answer.

I'm not to open up plus and look inside of it.

However, in order to evaluate the operand, let's pick some

arbitrary order and do them.

I'm going to go from right to left.

Well, in order to evaluate this operand, I have to

evaluate the parts of it by the same rule.

And the parts are I have to find out what square is-- it's

some procedure, which has a formal parameter x.

And also, I have an operand which is four, which I have to

substitute for x in the body of square.

So the next step is basically to say that this is the sum of

the square of three and the product of four and four.

Of course, I could open up asterisk if I liked--

the multiplication operation--

but I'm not going to do that.

I'm going to consider that primitive.

And, of course, at any level of detail, if you look inside

this machine, you're going to find that there's multiple

levels below that that you don't know about.

But one of the things we have to learn how to

do is ignore details.

The key to understanding complicated things is to know

what not to look at and what not compute

and what not to think.

So we're going to stop this one here and say, oh, yes,

this is the product of two things.

We're going to do it now.

So this is nothing more than the sum of the square

of three and 16.

And now I have another thing I have to evaluate, but that

square of three, well, it's the same thing.

That's the sum of the product of three and three and 16,

which is the sum of nine and 16, which is 25.

So now you see the basic method of doing substitutions.

And I warn you that this is not a perfect description of

what the computer does.

But it's a good enough description for the problems

that we're going to have in the next few lectures that you

should think about this religiously.

And this is how the machine works for now.

Later we'll get more detailed.

Now, of course, I made a specific choice of the order

of evaluation here.

There are other possibilities.

If we go back to the telestrator here and look at

the substitution rule, we see that I evaluated the operator

to get the procedures, and I evaluated the operands to get

the arguments first, before I do the application.

It's entirely possible, and there are alternate rules

called normal order evaluation whereby you can do the

substitution of the expressions which are the

operands for the formal parameters

inside the body first.

And you'll get also the same answer.

But right now, for concreteness, and because this

is the way our machine really does it, I'm going to give you

this rule, which has a particular order.

But that order is to some extent arbitrary, too.

In the long run, there are some reasons why you might

pick one order or another, and we'll get to that

later in the subject.

OK, well now the only other thing I have to tell you about

just to understand what's going on is let's look at the

rule for conditionals.

Conditionals are very simple, and I'd like to examine this.

A conditional is something that is if-- there's also

cond, of course--

but I'm going to give names to the parts of the expression.

There's a predicate, which is a thing that is

either true or false.

And there's a consequent, which is the thing you do if

the predicate is true.

And there's an alternative, which is the thing you do if

the predicate is false.

It's important, by the way, to get names for, to get names

for, the parts of things, or the parts of expressions.

One of the things that every sorcerer will tell you is if

you have the name of a spirit, you have power over it.

So you have to learn these names so that we can discuss