6.001 Recitation 9Structure and Interpretation of Computer Programs March 3, 2005Symbols and Quote1. SymbolsSymbols are atomic. Symbols are also interned. The fact that they have textual representationis just for the programmer.2. QuoteReturns, literally, Scheme’s internal copy of the co de inside the q uote. ’(1 2 3) is syntacticsugar for (quote (1 2 3)).3. Equality= Numerical equivalence only.eq? Referential equivalence. Always works for symbols.eqv? Almost referential equivalence. Also works for numbers.equal? Representational equivalence. Do they look the same?4. QuotingWhat do the following expressions desugar to?’ ∗’ (1 2 (3 4) )’4Evaluate the following expressions.’ ( 2 3 4)( quote (+ 1 2 ) )’ ’ a’ n i l’5’ ( 1 ’ a b )( ’+ 3 4)( cons ’ a ’ ( b ) )( i f ’(= 1 0) 5 1 0)( i f ’ #f 5 10)16.001 Structure and Interpretation of Computer Programs Symbols and Quote5. Equality(= ’2 2)( eq? ’ x ’X)( eq? ”x” ’ x )( eq? 9876543210 98765 43210 ) ; ( But don ’ t do t h i s ! )( eq? 2 2) ; ( or t h i s ! )( eq? ( l i s t 1 2) ( l i s t 1 2) )( l e t ( ( x ( l i s t 1 2 ) ) ) ( eq? x x ) )( l e t ( ( x ( l i s t 1 2 ) ) ) ( eq? ( cdr x ) ( cdr x ) ) )( eq? c a r c ar )( eq? ( c ar ( l i s t 1 2 ) ) ( c a r ( l i s t 1 2 ) ) )( e qu a l? ( l i s t 1 2) ( l i s t 1 2 ) )( e qu a l? ’ x ’ x )( e qu a l? ( l i s t c d r +) ’( cd r +) )( eqv? 9876543210 987654321 0)6. BrainteaserA quine is a piece of code that, when evaluated, returns its own code as a result. A self-printing expression is a simple example of a quine (ie, evaluating 2 results in 2). Using quote,write a non-atomic quine.(The shortest Scheme quin e I’m aware of will easily fit in the above space, but you mightwant to work it out on a separate sheet of paper).In addition to being amusing, quines actually have a deep theoretical basis in the recursiontheorem. It turns out that any Tu ring-complete language is capable of reproducing its ownco de. (Quines happen to be particularly cool in Scheme because data and code are inter-changeable; for example, the best a C quine can do is pr int out a string of its own cod e).The recursion theorem is typically quite useful in proofs of what cannot be computed, butself-reproduction also has interesting philosophical implications. Intuitively, people tend tothink that machines can only pro duce simpler machines, but the recursion theorem provesthat they can at least produce machines of equal complexity (for instance, it’s possib le tobuild a factory factory that creates copies of itself)Hint: Here’s an English quine.Print out two copies of the following, the second one in quotes: “Print out two copies of the following, the second one in
View Full Document