SICP Exercise 1.1: Interpreter Evaluation

The first exercise is simply a case of evaluating some expressions in your chosen Scheme interpreter and recording the output.  Nothing overly complex here, apart from chosing your interpreter.  After hunting around for a while I settled on the DrRacket environment, which includes support for both the Racket dialect of Scheme and the R6RS scheme standard.  DrRacket provides a development environment incorporating an editor, interpreter, debugger and other bits and bobs.  The editor includes all the usual editory features you'd expect, but it's worth noting that it provides syntax highlighting, auto-indentation, and bracket matching.  The last of these is pretty crucial when writing any LISP-dialect code, and the others help a lot too.

For various reasons I've also tinkered with the Kawa interpreter.  However, I found it to have some "interesting idiosyncrasies", such as scoping issues and buggy interpreter interactions, so I try to stick to DrRacket now.

Anyway, without further ado, exercise 1.1.

Below is a sequence of expressions.  What is the result printed by the interpreter in response to each expression?  Assume that the sequence is to be evaluated in the order in which it is presented.

> 10
10

Expressions consisting of only digits are evaluated to the decimal value they represent.

> (+ 5 3 4)
12

Scheme uses prefix notation (also known as Polish notation) for its expressions.  Unlike the infix notation we know and love from our maths lessons at school, in prefix notation the operator comes first within the parenthesised expression with the operands following after, so this expression is equivalent to 5 + 3 + 4 in infix notation.  If you've never prefix notation before then it can take a little while to get used to.

> (- 9 1)
8

This is equivalent to 9 - 1 in infix notation. It's worth noting that you can apply more than two operands to the - operator. Scheme's interpretation of such expressions is equivalent to taking the first operand as the initial value and then subtracting each and every subsequent operand in turn from the value. I.e. (- 10 5 3 1) is equivalent to 10 - 5 - 3 - 1 in infix notation.

> (/ 6 2)
3

This is equivalent to 6 / 2 in infix notation. Note that division has an equivalent interpretation to subtraction when there are more than two operands. I.e. (/ 15 5 3) is equivalent to (15 / 5) / 3 in infix notation.

> (+ (* 2 4) (- 4 6))
6

This is equivalent to (2 * 4) + (4 - 6) in infix notation.

> (define a 3)

As noted in the text, the result printed by the interpreter in response to evaluating the define operator depends greatly on the interpreter in use. DrRacket doesn't print anything. However, we've now associated the value 3 with the variable a...

> (define b (+ a 1))

...and the value 4 with the variable b. Obviously the order of evaluation is critial here. As the definition of b relies upon the variable a, the expression which defines a must preceed the expression defining b!

> (+ a b (* a b))
19

This is equivalent to a + b + (a * b) in infix notation, and relies upon the preceeding definitions of a (= 3) and b (= 4).

> (= a b)
#f

Boolean values are represented in Scheme by #t and #f for true and false respectively. The book notes a couple of interesting things here:

• You can also use true and false (although evaluating these returns #t and #f respectively).
• When the interpreter evaluates a predicate it evaluates #f as a false value and any other value as true. Which means that #t and true aren't strictly necessary.
  

> (if (and (> b a) (< b (* a b)))
      b
      a)
4

Our first conditional expression. The interpreter first evaluates the predicate (the first operand). If it evaluates to true^* then it returns the value produced by evaluating the consequent (the second operand). If, on the other hand, the predicate evaluates to false then it returns the value produced by evaluating the alternative (the third operand). In this case the predicate evaluates to true (as, using substitution, (> b a) = (> 4 3) = #t), so it returns the value produced by evaluating the consequent.

^*Of course, when we say "true" we mean any value other than #f.

> (cond ((= a 4) 6)
        ((= b 4) (+ 6 7 a))
        (else 25))
16

The cond operand is a multi-branch conditional expression. Each operand in a correctly constructed cond expression consists of a pair of sub-expressions. The first being a predicate and the second being an arbitrary expression. The interpreter's evaluation of a cond expression is equivalent to starting at the first operand and then performing the following set of steps:

1. Evaluate the predicate.
2. If the predicate evaluates to true then return the value produced by evaluating the corresponding arbitrary expression. Do not evaluate any further operands in the cond expression.
3. If the predicate evaluates to false then move onto the next operand and repeat the procedure.

What happens if none of the predicates evaluate to true? In the case of DrRacket it returns an empty (void) value.

Anyway, in this exercise, the predicate for the first operand evaluates to false (a equals 3, not 4), so it falls through to the second operand where the predicate evaluates to true (b does equal 4) and so the the second operand's arbitrary expression, (+ 6 7 a), is evaluated and its result is returned as the value of the expression.

> (+ 2 (if (> b a) b a))
6

In this expression, the if conditional is embedded within an outer expression so in order to interpret the latter the interpreter must first interpret the former. As b is greater than a the predicate evaluates to true and so the consequent of the if operator is evaluated and returned as its value (= b = 4), which then allows the outer expression to be evaluated as (+ 2 4).

> (* (cond ((> a b) a)
           ((< a b) b)
           (else -1))
     (+ a 1))
16

The final expression to be evaluated again embeds a conditional expression (a cond this time). The predicate for the second operand is the first one that evaluates to true, so the whole cond expression evaluates to 4. However, before the interpreter can evaluate the * expression it must also evaluate its second operand as well. (+ a 1) = (+ 3 1) = 4, so the * expression can be evaluated as (* 4 4).

Phew! That took a while to write up. And I know that quite a few of the ones between here and where I've got to so far have a lot of text in them too. It may take me a while to catch-up...