CS200: Computer Science, Spring 2004

Notes: Friday 23 January 2004
Schedule
 Monday, 26 January: Read GEB, Little Harmonic Labyrinth and GEB, Chapter 5
 Monday, 2 February: Problem Set 2
GEB Reading Guide As you read GEB Little Harmonic Labyrinth and Chapter 5, here are some things to think about:
 Is music you know recursive like the Little Harmonic Labyrinth?
 How do the Recursive Transition Networks he uses to describe languages compare to the Backus Naur Form we saw in class? Can any Recursive Transition Network be rewritten as in Backus Naur Form? Which notation is more compact? Which notation is easier to understand?
 Can you translate his definition of FIBO (p. 136) into a Scheme procedure that calculates Fibonacci numbers? (We will do this in Monday's class, but think about it yourself first)
 Are Feynman diagrams a formal system? Are they a language?
Richard Feynman won the Nobel Prize in Physics in 1965 and was important in the Manhattan Project and in the Space Shuttle Challenger investigation. He also made important contributions to Computer Science (a few of which we will see later in this class). In 1984, Richard Feynman and Gerry Sussman cotaught a course at Caltech using an early version of the Wizard Book. Here's a story about that from Feynman Online ( For more stories about Feynman, "Surely You're Joking, Mr. Feynman!": Adventures of a Curious Character is highly recommended summer reading.):
In the beginning part of 1984, Feynman was teaching a course on computing at Caltech. The course was also cojointly taught by Gerald Sussman from MIT. On one occasion Feynman was lecturing at the blackboard, but this time Sussman kept coming up and correcting him. Later that week Feynman was supposed to come over for dinner. On the night in question, Feynman's wife Gweneth called to say that Feynman was in the hospital and that they would not be able to come over. She told me not to tell anyone, as she didn't want the word to get around. Apparently Feynman in his excitement to purchase a new computer tripped on the sidewalk curb and hit his head. This caused some internal complications and bleeding. In a week or so, Feynman was back on his feet and returned to class. At lunch Feynman related what had happened. After bumping his head, he paid little or no attention to it. He was bleeding when he entered the computer store. What was interesting is that he gradually began to loose his sense of what was happening around him without internally realizing it. First, he couldn't locate his car. Then he had a very strange session with one of his artistic models. And on another day, he told his secretary Helen Tuck that he was going home, and proceeded to undress and lie down in his office. He forgot that he was to give a lecture at Hughes aircraft, and so on... Everything was just rationalized away. But you know, he said, NO ONE told me I was going crazy. Now why not? I said, Come on. You are always doing weird stuff. Besides there such a fine line between genius and madness that it sometimes difficult to tell! Listen, ape, the next time I go crazy around here, you be sure to tell me!Evaluation Rules (define square (lambda (x) (* x x)))Expression ::= (define Name Expression)(square 4)
Eval 4define. If the expression is (define Name Expression) associate the Expression with Name (for Evaluation Rule 2).So, the expression associated with square is (lambda (x) (* x x)).
Expression ::= (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.So, we need to evaluate the subexpressions according to rule 3a:
square is a nameSo, we are applying (lambda (x) (* x x)) to 4. Since (lambda (x) (* x x)) is a compound procedure, we use apply rule 2:Expression ::= Name4 is a primitiveEvaluation Rule 2: Names. If the expression is a name, it evaluates to the value associated with that name.The expression associated with square is (lambda (x) (* x x)).Evaluate (lambda (x) (* x x))
Expression ::= (lambda (Parameters) Expression)
Eval 4lambda. Lambda expressions selfevaluate. (Do not do anything until it is applied.)So, square evaluates to (lambda (x) (* x x)).
Expression ::= Primitive
Evaluation Rule 1: Primitives. If the expression is a primitive, it is selfevaluating.4 evaluates to the number 4. Apply the value of the first subexpression to the values of all the other subexpressions.
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.The body of the procedure is (* x x). The name of the first parameter is x which corresponds to the first argument expression value, 4. So, we need to evaluate (* x x) with each x replaced by 4: (* 4 4).Expression ::= (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.Rule 3a tells us to evaluate each subexpression: * is a primitive that selfevaluates to the primitive procedure *, 4 is the value 4.
Rule 3b tells us to apply the value of the first subexpression, the primitive procedure * to the values of all the other subexpressions. since * is a primitive procedure, we use application rule 1:
Application Rule 1: Primitives. If the procedure to apply is a primitive, just do it.Hence, (* 4 4) evaluates to 16 and the original expression (square 4) evaluates to 16 (as one would hope).Defining Recursive Procedures
 Be optimistic.
 Assume you can solve it.
 If you could, how would you solve a bigger problem.
 Think of the simplest version of the problem, something you can already solve.
 This is called the base case.
 Usually something like solve for 0 or the empty list
 Combine them to solve the problem.
(define (findclosest goal numbers) (if (= 1 (length numbers)) (first numbers) (if (< (abs ( goal (first numbers))) (abs ( goal (findclosest goal (rest numbers))))) (first numbers) (findclosest goal (rest numbers))))Links
 US Patent Law Frequently Asked Questions
 Photomosaic Patent
 Runaway Technologies (www.photomosaic.com)
cs200staff@cs.virginia.edu Using these Materials 