University of Virginia Computer Science
CS150: Computer Science, Fall 2005
|
(none)
29 August 2005
|
CS150 Notes 2
(29 August 2005)
Assignments Due
- 31 August: Pledge
- 31 August: Problem Set 1
- Friday, 2 September: Read SICP, Section 1.2
- Monday, 5 September: Read GEB, Little Harmonic Labyrinth and GEB, Chapter 5
Backus-Naur Form Scheme Grammar with Rules of
Evaluation
Expression ::= Primitive
Evaluation Rule 1: Primitives. If the expression is a primitive,
it is self-evaluating.
Expression ::= Name
Evaluation Rule 2: Names. If the expression is a name, it
evaluates to the value associated with that name.
Expression ::= (Expression ExpressionList)
ExpressionList ::=
ExpressionList ::= Expression ExpressionList
Evaluation Rule 3: Application. If the expression is an application:
(a) Evaluate all the subexpressions of the combination (in any order)
(b) Apply the value of the first
subexpression to the values of all the other subexpressions.
Application Rule 1: Primitives. If the procedure to apply is a
primitive, just do it.
Application Rule 2: Compound Procedures. If the procedure is a
compound procedure, evaluate the body of the procedure
with each formal parameter replaced by the corresponding actual argument
expression value.
Expression ::= (lambda (Parameters) Expression)
Parameters ::=
Parameters ::= Name Parameters
Eval 4-lambda. Lambda expressions self-evaluate. (Do not do anything
until it is applied.)
Expression ::= (define Name
Expression)
Eval 4-define. If the expression is (define Name Expression)
associate the Expression with Name (for Evaluation
Rule 2).
Expression ::= (if Expression0 Expression1 Expression2)
Eval 4-if. If the expression is
(if Expression0 Expression1 Expression2)
evaluate Expression0. If it evaluates to #f, the value of the if
expression is the value of Expression2. Otherwise, the value of the if
expression is the value of Expression1.
Expression ::= (begin ExpressionList Expression)
Eval 4-begin. If the expression is (begin
ExpressionList Expression) evaluate all the
sub-expressions in ExpressionList in order from left to
right. Then evaluate Expression. The
value of the begin expression is the value of Expression.
The common syntax for defining a procedure is actually syntactic sugar
(an easier way to write something that means exactly the same thing)
for a lambda expression. For example,
(define (square x) (* x x))
is just a short way of expressing:
(define square (lambda (x) (begin (* x x))))
Questions
How would the Scheme Rules of Evaluation evaluate (square 4)?
You will need more space for this, but its worth doing. Of course, you
know the final value, but the important thing is to understand how
following the Scheme evaluation rules steps will produce that value.
You should be confident that you can determine the value of any
Scheme expression just by following the evaluation rules systematically.
Evaluation Rule 3a does not say in what order the subexpressions should be
evaluated in. For example, we could evaluate them left to right, or
right to left, or in any other order. This is like the MIU-system Rule
3 that does not say which occurance of III should be replaced.
Does it ever matter in which order the subexpressions of an application
are evaluated? (Tough question, but try to think of a Scheme expression
where it would make a difference.)
Links
|
|
"Somehow it seems to fill my head with ideas - only I don't exactly know what they are!"
Alice, in Alice and Wonderland by Lewis Carroll after hearing The Jaberwocky.
The best book on programming for the layman is Alice in
Wonderland;
but that's because it's the best book on anything for the layman.
Alan Perlis, author
of SICP Forward and First Turing Award (biggest prize for Computer
Science) Winner
|
|
");
print ( $res[$first] ) ;
print (" |
");
?>