Notes for Lab 1

Notes for Lab 1
[Main Page]

Table of Contents
A. Scheme Expressions
1. Normal Scheme Expressions
2. Special Forms
B. Evaluation Model
1. Normal Scheme Expressions
2. Special Forms
a) Define
- Desugaring
b) Lambda
C. Special Notes
1. Lambda as operator

A. Scheme Expressions

1. Normal Scheme Expressions

This is the syntax for all scheme expressions:
(func op1 op2 ...)
- where func is called the "operator" because of its position in the expression
- and op1, op2, ... are called "operands" because of their positions in the expression (the number of operands can vary)

2. Special Forms

Most "interesting" scheme expressions are "special forms". Here is the list of special forms so far (there will be more):

if
define
cond
lambda
or
and

B. Evaluation Model

1. Normal Scheme Expressions

Most scheme expressions are "normal" and follow this evaluation method:

Evaluate the operands
Evaluate the operator
Apply the operator to the operands

(more accurately, {operator}* is applied to {operands}*)

2. Special Forms

When a "special form" appears as an operator, then you must follow the special rules for evaluation corresponding to whatever "special form" operator you have. Moreover, special forms have stricter syntax than "normal scheme expressions". For example, define takes exactly 2 operands, and will cause an error immediately if given more or less operands. This is not true for "normal" expressions where ALL operands will be evaluated, then the operator will be evaluated, and if the operator cannot be applied because the number of operands is incorrect, THEN the evaluation will fail. Thus, the define fails immediately for incorrect # of operands whereas "normal" operators will not fail until the apply step if given an incorrect # of operands.

a) Define

Evaluation steps for define:
(define op1 op2)
*special form (check number of operands)
1. evaluate op2
2. create an association between the name given as op1 and {op2}*
Thus after (define x (+ 2 3)) subsequent evaluations of x will result in 5, not (+ 2 3), because an association was made between x and {(+ 2 3)}* = 5.

There is a slight exception to the evaluation steps for define. This exception occurs when one has the "sugared" form for defining lambdas.

- Desugaring

In a scheme expression where there is "synctatic sugar", the expression must be completely "desugared" before any evaluation can take place.
The sugared form of a define expression looks like this:
(define (func arg1 arg2 ...) (body ...))
and should be desugared into this:
(define func (lambda (arg1 arg2 ...) (body ...)))
After "desugaring", follow the normal evaluation steps for define.

b) Lambda

Evaluation steps for lambda:
(lambda (arg1 arg2 ...) (...body...))
1. evaluate (lambda (arg1 arg2 ...) (...body...)) -> (lambda (arg1 arg2 ...) (...body...))
(the lambda expression evaluates to itself)

To be more accurate, the lambda expression evaluates to an internal procedure that takes some arguments and substitutes them for (arg1 arg2 ...) in (...body...) after which (...body...) is evaluated like any other scheme expression.

Application steps for lambda:
((lambda (arg1 arg2 ...) (...body...)) op1 op2 ...)
[ evaluate operands ]
1. evaluate op1
2. evaluate op2
...

[ evaluate operator ]
1. evaluate (lambda (arg1 arg2 ...) (...body...)) -> (lambda (arg1 arg2 ...) (...body...))

[ apply operator to operands ]
1. apply (lambda (arg1 arg2 ...) (...body...)) to {op1}, {op2}, {...}*
2. substitute {op1} for arg1, {op2} for arg2, etc. in (...body...)
3. evaluate the substituted form of (...body...)

C. Special Notes

1. Lambda as operator

It is important to note that a lambda expression can be used as both an operator and as an operand. This is why we can use (define f (lambda (arg1 arg2 ...) (...body...))) if we want to use the lambda expression multiple times. After the association has been made between f and {(lambda (arg1 arg2 ...) (...body...))}*, you can use f as an operator because it will evaluate to {(lambda (arg1 arg2 ...) (...body...))}*.

As an example, suppose we take +. + works as an operator on numbers, but we can also use it as an operand. Try the following in scheme to demonstrate this principle:
(define a +) ;; using + as an operand to define
(a 2 3) ;; using a which evaluates to {+}*

Once you understand that using a lambda expression is just like working with any other "normal" operator, the method of evaluating and applying lambda expressions makes more sense.

* {expr} represents what expr evaluates to (assuming expr is a valid scheme expression) [Back]