6.001 Tutorial 5Structure and Interpretation of Computer Programs March 20, 2006Symbols, Quotation, and Tagged dataSymbolsSymbols are atomic id entifiers. The fact that they have a textual representation is just for theprogrammer. Symbols are interned, meaning that no matter how many times ’foo appears in yourco de, Scheme ensures it will always refer to the same symbol object.QuoteInternally, your S cheme code is represented just like lists that you create. The quote special formliterally hands over a reference to Scheme’s internal copy of your code. ’(1 2 3) is syntactic sugarfor (quote (1 2 3)).EqualityThere are a couple of different types of equality you might want to test for.Equality type Predicate “Works for” Order of growthNumeric equality = Numbers1O(n)Referential equality eq? Bo oleans, symbols, strings, pairs O(1)Do-what-I-mean equality eqv? Like = for numbers, eq? otherwise O(n)Print equality equal? Anything (Do they print the same?) NoneReferential equality tests if two references are to the s ame object in memory. In other words, dotheir pointers go to the same place? This works as you would expect on strings and pairs. Thisalso works on booleans and symbols, because these are interned.Tagged DataSch eme only provides us with some basic types from which to construct more complex data struc-tures. We need some way to differentiate between our own data typ es s ince they’re all made of thesame underlying stuff. To do this, we tag every structure we create.1Do not use eq? for numbers. It is unspecified whether numbers are objects or not, and therefore the behav ior ofreferential equality is unspecified on numbers. In most implementations, integers between −(230) and 230− 1 are notobjects, and all other numbers are. A common implementation trick is to use a machine word (32-bits) to representreferences. Three bits are “tag” bits, which specify the type of t he object and information for the garbage collector.Some things, like small numbers, can be packed directly into the remaining b its, which makes integer math fast;otherwise, the remaining bits are a memory pointer off to the real object. eq? typically performs a literal comparisonof two references.16.001 SICP Symbols, Quotation, and Tagged dataReader ExercisesWhat do the following expressions desugar to?’ ∗’ ( 1 2)’ ( ’ a b)’ ’ ’ cQuote ExercisesEvaluate the following expressions’ ∗’ ( 1 2)’ ’ ’ c( d e fi ne x ’ (+ 1 2 ) ) ( define y x ) y’ n i l’ ( )( ’ ∗ 3 4)( c ons ’1 ’ ( b ) )( i f ’ ( / 1 0) 10 20)( i f ’ #f 5 1 0)Equality Exercises(= ’2 2)( eq? ”x” ’ x ); Don ’ t r e l y on t h i s !( eq? ’ x ’ X); Don ’ t do t h i s !( eq? 9876543210 98765432 1 0); Or t h i s !( eq? 2 2)( 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? ( cd r x ) ( c d r x ) ) )( eq? ca r ca r )( eq? ( car ( l i s t ’ x 2 ) ) ( c ar ( l i s t ’ x 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 cdr +) ’ ( cdr +) )( eqv? 9876543210 987654 3 210)Brainteaser1A quine is a piece of code that, when evaluated, returns its own code as a result. A self-printingexpression is a simple example of a quine (ie, evaluating 2 results in 2). Using quote, write anon-atomic quine.26.001 SICP Symbols, Quotation, and Tagged data(The shortest Scheme qu ine I’m aware of will easily fit in the above sp ace, but you might want towork it out on a separate sheet of paper).In addition to being amusing, quines actually have a deep theoretical basis in the recursion theorem.It turns out that any Turing-complete language is capable of reproducing its own code. (Quineshappen to be particularly cool in Scheme because data and cod e are interchangeable; f or example,the best a C quine can do is print out a string of its own code). The recursion theorem is typi-cally quite useful in proofs of what cannot be computed, bu t self-reproduction also has interestingphilosophical implications. Intuitively, people tend to think that machines can only produce sim-pler machines, but the recursion theorem proves that they can at least produce machines of equalcomplexity (for instance, it’s possible to build a factory factory that creates copies of itself)Hint:Here’s an English quine.2Print out two copies of the following, the second one in quotes: “Print out two copies of the following, the second one in quotes:”Brainteaser2It turns out (I think) that Dr. Scheme’s equal? will always terminate, even with self-referential datastructures. How could you implement such an equal??2From Introduction to the Theory of Computation, Michael Sipser. Yay
View Full Document
Unlocking...