Mental models of computation

Summary

We introduce a mental model of computation for Racket programs that allows us to read code and predict its behavior without having to run the program in DrRacket.

So far, we have introduced a number of features of the Racket programming language including top-level definitions, function declarations, and function application. 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 Racket programs. For example, consider the following function definition:

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

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

Are these two functions equivalent? Textually, the functions 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 functions in DrRacket’s interactive 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 function 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 Racket 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 Racket programs and accurately predict their results.

Expressions

The core of the Racket 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 Racket code is also an expression:

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

This extends to Racket 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 Racket! 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 Racket’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 innermost parenthesized expressions first! There is nothing else to know. Let’s see how that works for the Racket 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 Racket evaluates or steps to another expression.)

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

Functions and the substitutive model

When we evaluate functions, we have implicitly “carried out the behavior of the function” in our head and replaced the function 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 functions are user-defined? 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 function for the function call in question. The body of double is (* 2 n) so we would replace (double 2) 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 function. We pass 5 for n so we ultimately replace (double 2) 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 functions we’ll see in Racket! 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!

Self-checks

Check 1: Code tracing (‡)

Assume the existence of the following Racket 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 Racket!