Mental models of computation

Summary

We dive into our substitutive model of computation introduced last week in more detail, in particular, looking at how functions operate within the model.

So far, we have introduced a number of features of the Scheme programming language including top-level definitions, procedure declarations, and procedure applications. We have also focused nearly exclusively on how to author programs using these tools, appealing to your intuition about these constructs to explain how they work.

However, this intuition might fail to explain some corner cases that you are bound to run into while writing Scheme programs. For example, consider the following procedure definitions:

(define f (lambda (x) (+ x 1)))

(define g (lambda (y) (+ y 1)))

Are these two procedures equivalent? Textually, the procedures f and g are nearly identical, but the names of the parameters are different. Does this difference matter? Our intuition says no: parameter names don’t seem to matter in this regard. For example, if we try out these procedures in Scamper’s exploration pane:

> (f 5)
6
> (g 5)
6
> (f -1)
0
> (g -1)
0

There’s too many integers to test in this manner, but after a few checks of this sort, we feel pretty confident in our intuition.

However, what happens if we have the following situation:

(define x 100)

(define f (lambda (x) (+ x 1)))

What will (f 10) produce? Two sensible answers are:

• 101 if the defineed version of x is used in the computation of f.
• 11 if the value of 10 that is passed to the procedure is used.

But maybe the code produces an error because x is defined twice. Or even more bizarre, but not out of the realm of possibility: maybe the defineed x is now 10 or 11!

Which of these is the correct answer? We can, of course, run this code to find out:

> (f 10)
11
> x
100

But why is this the case? What rules govern the execution of Scheme programs and how can they explain this behavior?

In this reading, we’ll introduce such a set of rules: a mental model of computation. This mental model will allow us to interpret Scheme programs and accurately predict their results.

Expressions

The core of the Scheme programming language is the expression. Expressions are syntactic constructs that evaluate to values. We are intimately familiar with expressions already: they form the basis of computation in arithmetic! For example, here is an arithmetic expression:

\[ 3 × (8 + 4 ÷ 2) \]

This expression evaluates to a final value, \( 30 \). We say that \( 30 \) is a value: it is an expression that no longer takes any steps of evaluation.

The analogous Scheme code is also an expression:

> (* 3 (+ 8 (/ 4 2)))
30

This extends to Scheme code that doesn’t involve numbers at all!

(> (string-upcase (string-append "hello world" "!!!"))
"HELLO WORLD!!!"

Here the expression produces a string as output—the upper-case version of the string resulting from gluing "hello world" and "!!!" together.

A substitutive model of evaluation

The process of determining the value that an expression produces is called evaluation. The evaluation of expressions is the primary way that we perform computation in Scheme! But how do expressions evaluate? We determine how expressions evaluate by applying two basic sets rules:

1. Rules of precedence that tell the order in which to evaluate operators.
2. Associativity rules that tell us how the arguments to operators bind when chained together.

For arithmetic, we know that division and multiplication are evaluated before addition and subtraction. Furthermore, expressions in parentheses are evaluated first, irrespective of the operators involved. Finally, we typically expect that the arithmetic operators are left-associative resulting in a left-to-right evaluation order.

  3 × (8 + 4 ÷ 2)
= 3 × (8 +   2  )
= 3 ×     10
= 30

At every step of evaluation we:

1. We determine the sub-expression to evaluate next based off of our rules.
2. We evaluate that sub-expression to a value.
3. We substitute the resulting value for that sub-expression to create a new, slightly simplified expression.

We then repeat this process until we arrive at a final value.

While we may find Scheme’s syntax arcane at first, it has one major benefit: There is only one rule for determining order-of-operations for expressions! That rule is straightforward: evaluate the parameters to a procedure before appling the procedure! (Some of us say “evaluate the innermost parenthesized expression first”.) There is nothing else to know. Or almost nothing else to know. Let’s see how that works for the Scheme version of this arithmetic expression:

    (* 3 (+ 8 (/ 4 2)))
--> (* 3 (+ 8    2  ))
--> (* 3      10     )
--> 30

(Note that we use the symbol --> to denote that one expression in Scheme evaluates or steps to another expression.)

Perhaps it would’ve been better in grade school if you were introduced to Scheme-style infix notation for arithmetic operations first. There are less rules to memorize, after all… 😊.

Okay, perhaps it’s not quite that simple. What happens if a a procedure is called with multiple parameters, each of whic his an expression?

    (* (+ 1 2) (+ 4 1))

We need to evaluate the (+ 1 2) before we do the multiplication. We need to evaluate the (+ 4 1) before we do the multiplication. But which of those to should we do first? Generally, it doesn’t matter. Let’s check.

First, we’ll evaluate the first parameter first.

    (* (+ 1 2) (+ 4 1))
--> (* 3 (+ 4 1))
--> (* 3 5)
--> 15

Next, we’ll evaluate the second parameter first.

    (* (+ 1 2) (+ 4 1))
--> (* (+ 1 2) 5)
--> (* 3 5)
--> 15

You may not be surprised to discover that we got the same result in each case. But it turns out that we can’t guarantee that in all programming languages. (We can’t even guarantee it in Scheme, but we can guarantee it for most of the programs we write.) Nonetheless, for the time being, you can assume that the order in which we evaluate parameters does not matter, provided you evaluate parameters before you apply a procedure.

Definitions

We have a starting point. We know how to evaluate expressions. But expressions often involve variables. In Scheme, we create variables (named values that don’t really vary) using define statements. How should we mentally model define statements and the variables they define?

One easy way to think about them is in terms of a table that tells us what value to use for each variable. When we see a define statement, we first evaluate the expression and then we put the named and the value in the table. We tend to write that as name:value.

    ; Table: []
    (define x 5)
    ; Table: [x:5]
    (define y 17)
    ; Table: [x:5, y:17]
    (define z (* 2 3))
--> (define z 6)
    ; Table: [x:5, y:17, z:6]

What good is the table? The table informs how we evaluate expressions that consist only of variables (named values). When evaluating an expression, when the next expression to evaluate is a variable, we look in the table to find the value associated with the variables.

    ; Table: []
    (define x 10)
    ; Table: [x:10]
    (define y 2)
    ; Table: [x:10, y:2]
    (+ (* x 4) y))
    ; We need to evaluate the (* x 4) before we add
    ; We need to evaluate the x before we multiply.
    ; We look x up in the table
--> (+ (* 10 4) y)
    ; We need to evaluate the (* 10 x) before we add
--> (+ 40 y)
    ; We need to evaluate the y before we add
    ; We look y up in the table
--> (+ 40 2)
--> 42

Seems pretty straightforward. Right? What happens if we write an expression that involves a variable not in the table?

    ; Table: [x:10]
    (+ (* x 4) y))
--> (+ (* 10 4) y)
--> (+ 40 y)
    ; y is not in the table
    y: undefined

Note that these tables are mostly a notational convenience, designed to make it easier for us to figure out the value of expressions when we’re tracing. However, most programming languages, including Scheme, also have a hidden form of table which basically does the same thing (that is, that associates values with variables names).

Procedures and the substitutive model

When we evaluate procedures, we have implicitly “carried out the behavior of the procedures” in our head and replaced the procedure call with the value. For example

    (+ 1 1)
--> 2

We know how addition works, so we can treat the evaluation of + as a single step. Of course, if the arguments to + required evaluation first, we would need to carry that out according to our evaluation rules:

    (+ (+ 1 1) 8)
--> (+    2    8)
--> 10

The step-by-step evaluation of an expression to a final value is called the execution trace or just trace of a particular expression.

However, what happens when our procedures are those we have defined ourselves? For example, something simple like double:

(define double
  (lambda (n) 
    (* 2 n)))

How does an expression like (double (/ 6 3)) evaluate? As a first order of business, we should evaluate its argument to a value.

    (double (/ 10 2))
--> (double 5)

Good! Now how does (double 5) evaluate? We proceed as follows:

1. We substitute the body of the procedure for the procedure call in question. The body of double is (* 2 n) so we would replace (double 5) with (* 2 n).
2. Note that, on its own, the parameter n is not defined! To patch this up, we also substitute each argument for its associated parameter in the body of the procedure. We pass 5 for n so we ultimately replace (double 5) with (* 2 5).

All of this occurs in one step of evaluation and afterwards, we continue evaluation of the expression as normal. So the complete evaluation of our original expression is:

    (double (/ 10 2))
--> (double    5)
--> (* 2 5)
--> 10

While this rule is simple, it covers all occurrences of procedures we’ll see in Scheme! This is the beauty of a programming language at its core: a small set of rules governs a near, unimaginable set of behavior we can author in a computer program!

Definitions, tables, and procedures

We’ve separately considered models for the definitions that let us evaluate variables for procedures. Let’s also consider them together. We know that (define var exp) evaluates the expression and the pairs it with the variable in a table. So what happens when we write (define var (lambda (params) body))?

It turns out that Scheme does something a bit special with lambda expressions (expressions that begin with lambda). Instead of evaluating them further, Scheme stops evaluating until you need to apply the lambda expression. Then, and only then, does it do what we described above: We substitute it in for the name and then replace its named parameters (the “formals”, in CS parlance) with the values of the corresponding arguments (the “actuals”, in CS parlance).

It turns out that these model of operation means we can use lambdas without defining them. We’ll leave that issue for a bit later in your education.

Self-checks

Check 1: Code tracing (‡)

Assume the existence of the following Scheme definitions:

(define add-3
  (lambda (x y z)
    (+ (+ x y) z)))

(define triple
  (lambda (n)
    (add-3 n n n)))

With these definitions, give the step-by-step evaluation (i.e., evaluation traces) for each of the following expressions. Make sure to write down all steps of evaluation as required by our substitutive model of computation!

1. (+ 3 (* 5 (/ 2 (- 10 5))))
2. (add-3 (* 2 3) (+ 8 3) (/ 1 2))
3. (triple (+ 5 0.25))

Make sure to check your work by entering these expressions into Scheme!

Q&A

These questions are gathered from prior reading responses.

Does the table consist of multiple (define ...) definitions or of the ;comment with table [.. : ..]? Do we need to write the table for easier readiblity? Are define values not easy to read?

The table contains the results of the many define definitions. I include it to remember all of the definitions in one place so that I don’t have to go back and look. Write it how you’d prefer.

Do we have to write the table?

I find it easier to keep track of what’s going on if you write the table, but it’s not strictly necessary. I include the table, in part, because the Scheme interpreter has a table behind the scenes.

Could you explain how to define/use add-3?

add3 is a procedure that takes three inputs, which we’ll call x, y, and z. If we pretend that addition only takes two parameters, we’ll add x and y, and then add that result and z.

We say that it’s a procedure with (lambda (x y z) …).

We say “add x and y, and then add that result and z” with (+ (+ x y) z).

Putting it all together, we get

(define add-3
  (lambda (x y z) 
    (+ (+ x y) z)))

If we evaluate/trace, say (add-3 2 3 4), we substitute 2 for x, 3 for y, and 4 for z in the body. We then evaluate with the normal strategy.

    (add-3 2 3 4)
--> (+ (+ 2 3) 4)
--> (+ 5 4)
--> 9

In the fancier house example, I don’t understand how the overlay/align doesn’t apply to both the door and the roof of the house. Only the door is aligned at the bottom center of the house, while the roof is above it. But both of their commands come after (overlay/align "bottom" "center" ...).

overlay-align aligns images. It does not delve into the pieces or components of the individual images.

In this case, the outermost overlay-align aligns the door (itself built with an overlay/align) and the house with roof (built with the above).

I’m confused by what we call variables. In (define x 5), is the x the variable or the 5?

The variable is the name. In this case, x. It’s value is 5.

In Scheme, variables we created with define don’t tend to vary. In other programming languages, variables do vary.