The Meaning of Scheme

A legal DrScheme program consists of two items: a sequence of function definitions (in the Definitions window) and a sequence of interactions (in the Interactions window). Each interaction is a demand for the evaluation of one Scheme expression, which typically refers to the functions defined in the upper part of DrScheme.

When DrScheme evaluates an expression, it uses nothing but the laws of arithmetic and algebra to convert an expression into a value. In ordinary mathematics courses, values are just numbers. We also include symbols, booleans, and indeed all constants:

The collection of values is thus just a subset of the collection of expressions.

Now that we have defined the set of values, it is easy to introduce and to explain the evaluation rules. The rules come in two categories: those that appeal to arithmetic knowledge and those that rely on a small amount of algebra. First, we need an infinite number of rules like those of arithmetic to evaluate applications of primitives:

(+ 1 1) = 2
(- 2 1) = 1 

(not true) = false
(symbol=? 'a 'b) = false 
(symbol=? 'a 'a) = true 

Second, we need one rule from algebra to understand how the application of a user-defined function advances computation. Suppose the Definitions window contains the definition

(define (f x-1 ... x-n) 
  exp) 

where v-1 ... v-n is a sequence of values that is as long as x-1 ... x-n.

This rule is as general as possible, so it is best to look at a concrete example. Say the definition is

(define (poly x y) 
  (+ (expt 2 x) y)) 

  (poly 3 5)
= (+ (expt 2 3) 5)) 
  ;; This line is (+ (expt 2 x) y) where x was replaced by 3 and y by 5 . 
= (+ 8 5) 
= 13 

Third and finally, we need some rules that help us determine the value of cond-expressions. These rules are algebraic rules but are not a part of the standard algebra curriculum:

cond_false:

when the first condition is false:

  (cond 
    [false ...] 
    [exp1 exp2] 
    ...) 

  = (cond
      ; The first line disappeared. 
      [exp1 exp2] 
      ...) 

then the first cond-line disappears;

cond_true:

when the first condition is true:

  (cond 
    [true exp] 
    ...) 

  = exp

the entire cond-expressions is replaced by the first answer;

cond_else:

when the only line left is the else-line:

  (cond 
    [else exp]) 

  = exp

the cond-expressions is replaced by the answer in the else-clause.

Consider the following evaluation:

(cond
  [false 1] 
  [true (+ 1 1)] 
  [else 3])

= (cond 
    [true (+ 1 1)] 
    [else 3])

= (+ 1 1)

= 2 

The rules are equations of the form that we use in arithmetic and algebra on a daily basis. Indeed, the same laws apply to this system of equations as to those in mathematics. For example, if a = b and b = c, then we also know that a = c. A consequence is that as we get better at hand-evaluations, we can skip obvious steps and combine several equational inferences into one. Here is one shorter version of the previous evaluation:

  (cond
    [false 1] 
    [true (+ 1 1)] 
    [else 3])

= (+ 1 1)

= 2 

Even more importantly, we can replace any expression by its equal in every context--just as in algebra. Here is a another cond-expression and its evaluation:

  (cond
    [   0] 
    [else (+ 1 1)]) 
  ;; The underlined expression is evaluated first.  
= (cond 
    [false 0] 
    [else (+ 1 1)]) 
  ;; Here cond_false applies.  
= (cond 
    [else (+ 1 1)]) 
  ;; Using cond_else, we now get an arithmetic expression.  
= (+ 1 1) 
= 2 

Exercise 8.3.1

Evaluate the following expressions step by step:

1. (+ (* (/ 12 8) 2/3) 
          (- 20 (sqrt 4)))

2. (cond 
         [(= 0 0) false] 
         [(> 0 1) (symbol=? 'a 'a)] 
         [else (= (/  1 0) 9)])

3. (cond 
         [(= 2 0) false] 
         [(> 2 1) (symbol=? 'a 'a)] 
         [else (= (/  1 2) 9)]) ; Solution 

Exercise 8.3.2

Suppose the Definitions window contains

;; f : number number -> number
(define (f x y) 
  (+ (* 3 x) (* y y))) 

Show how DrScheme evaluates the following expressions, step by step:

1. (+ (f 1 2) (f 2 1))

2. (f 1 (* 2 3))

3. (f (f 1 (* 2 3)) 19) ; Solution