Recitation 2

Handouts: Don't Panic.

Admin

We spent 15 mins on admin stuff: checking who's in the recitation, assigning tutorial times, etc. I told you to email jill@ai if you need to change sections. I had you make name signs and asked you to bring them to the next few recitations (until I've learnt all your names).

Problem Set Hints

I gave you some hints for doing PS1:
-- read it carefully through first
-- try the debugger, but don't rush to use it
-- use a separate buffer and keep evaluating the entire buffer

Today's Idea: Evaluation

Since many of you missed my first recitation, I repeated some stuff from last time: the comparison of compiler and interpreter models and the notion of defines "installing" values against names.

We talked about the various kinds of expression:
-- primitive (12, false)
-- name (x, pi, +, *)
-- combination ("(+ 1 2)")
-- special form ("(define x 2)")

I pointed out that "expressions" in Scheme are not like expressions in Java or Pascal: a Scheme program is an expression! (or, more accurately, a bunch of expressions).

We discussed evaluation rules:
-- primitive: just do it
-- name: evals to what was last installed with that name
-- combination: eval the parts, then apply the operator value (on left) to the argument values
-- special forms: special rules

Examples of combinations
(+ 1 2)
(* (+ 1 2) 5)
(< 3 4)
(2)

Evaluating define
-- general form is (define NAME EXPR)
-- eval the expression
-- install its value under NAME

Examples:
(define x 3)
(+ (* x x) 4)

(define y (+ x 1))
(+ y y)

I pointed out that we check whether something's a name by trying it in the first position of a define. We did some daring experiments:

(define 1 2)
(define + 2)
(define define 2)

From this, we discovered that + is a name: a surprise for veteran programmers perhaps, but not for novices. The addition procedure is a value like any other; when the interpreter starts up, the name + is bound to it.

Evaluating if
-- general form is (if COND-EXPR THEN-EXPR ELSE-EXPR)
-- eval the COND-EXPR
-- if it evals to true, eval the THEN-EXPR and return that value
-- if it evals to false, eval the ELSE-EXPR and return that value

Note crucial difference between if-special-form and combinations: in a combination, all exprs get evaluated.

Examples
(if (< 3 4) (* 2 3) 5)

Exercise. What defines should precede ... so it evaluates to 4?
-- (f x 1)
-- (g 2)
-- (if (< a 2) y 5)
-- for the brave and foolish: (* + 3)

In my 11am recitation we discussed the question of how evaluation might fail. Never got to this in the 10am recitation, but we'll do it next time.

Does evaluation always succeed?

Several things can go wrong:
-- type error in primitive operation
-- never terminates with a value
-- (overflows system resources)

Examples
(/ 2 (- 1 1))
(+ 1 false)
(define (f x) (f x))
(f 1)

Sometimes we don't even get to evaluation
-- (define 1)
-- (define 2 2)

In summary:
-- Scheme is a small language with a few rules
-- We looked at the combination rule, and the rules for if and define
-- We understand a bit better the relationships between expressions, names, and values

Daniel Jackson
September 10, 1999