CS200: Computer Science, Spring 2004

Notes: Wednesday 21 January 2004
Schedule
 Friday, 23 January: Read SICP, Section 1.2.
 Monday, 26 January: Read GEB, Little Harmonic Labyrinth and GEB, Chapter 5
 Monday, 2 February: Problem Set 2
BackusNaur Form Scheme Grammar with Rules of Evaluation Expression ::= Primitive
Evaluation Rule 1: Primitives. If the expression is a primitive, it is selfevaluating.
Expression ::= NameEvaluation Rule 2: Names. If the expression is a name, it evaluates to the value associated with that name.
Expression ::= (Expression ExpressionList)
ExpressionList ::=
ExpressionList ::= Expression ExpressionListEvaluation 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 ParametersEval 4lambda. Lambda expressions selfevaluate. (Do not do anything until it is applied.)Expression ::= (define Name Expression)Eval 4define. If the expression is (define Name Expression) associate the Expression with Name (for Evaluation Rule 2).Expression ::= (if Expression_{0} Expression_{1} Expression_{2})Eval 4if. If the expression is (if Expression_{0} Expression_{1} Expression_{2}) evaluate Expression_{0}. If it evaluates to #f, the value of the if expression is the value of Expression_{2}. Otherwise, the value of the if expression is the value of Expression_{1}.Expression ::= (begin ExpressionList Expression)Eval 4begin. If the expression is (begin ExpressionList Expression) evaluate all the subexpressions 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)))) (define (compose f g) (lambda (x) (f (g 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 MIUsystem 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
 Why VerbInitial Languages are Not Frequent [PDF], Andre Gr¨ning, May 2002. Interesting paper that speculates on why most natural languages are SOV or SVO using results from computer simulations.
 Revised^{5} Report on the Algorithmic Language Scheme [PDF]  this is the official definition of the Scheme language
 C++ Standard Core Language Active Issues (440 issues or problems with C++ that the language experts can't agree on)
"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
cs200staff@cs.virginia.edu Using these Materials 