16.001 SICP1/416.001: Structure and Interpretation of Computer Programs• Symbols• Quotation• Relevant details of the reader• Example of using symbols• Alists• Differentiation6.001 SICP2/41Data Types in Lisp/Scheme• Conventional• Numbers (integer, real, rational, complex)– Interesting property in “real” Scheme: exactness• Booleans: #t, #f• Characters and strings: #\a, “Hello World!”• Vectors: #(0 “hi” 3.7)• Lisp-specific• Procedures: value of +, result of evaluating (λ (x) x)• Pairs and Lists: (3 . 7), (1 2 3 5 7 11 13 17)• Symbols: pi, +, MyGreatGrandMotherSue6.001 SICP3/41Symbols• So far, we’ve seen them as the names of variables• But, in Lisp, all data types are first class• Therefore, we should be able to– Pass symbols as arguments to procedures– Return them as values of procedures– Associate them as values of variables– Store them in data structures– E.g., (apple orange banana)apple orangebanana6.001 SICP4/41How do we refer to Symbols?• Substitution Model’s rule of evaluation:• Value of a symbol is the value it is associated with in the environment• We associate symbols with values using the special form define–(define pi 3.1415926535)• … but that doesn’t help us get at the symbol itself6.001 SICP5/41Referring to Symbols• Say your favorite color• Say “your favorite color”• In the first case, we want the meaning associated with the expression, e.g., •red• In the second, we want the expression itself, e.g., • your favorite color• We use quotation to distinguish our intended meaning6.001 SICP6/41New Special Form: quote• Need a way of telling interpreter: “I want the following object as whatever it is, not as an expression to be evaluated”(quote alpha);Value: alpha(define pi 3.1415926535);Value: "pi --> 3.1415926535"pi;Value: 3.1415926535(quote pi);Value: pi(+ pi pi);Value: 6.283185307(+ pi (quote pi));The object pi, passed asthe first argument to integer->flonum, is not the correct type.(define fav (quote pi))fav;Value: pi26.001 SICP7/41• A data abstraction consists of:• constructors• selectors• operations• contractReview: data abstraction(define make-point(lambda (x y) (list x y)))(define x-coor(lambda (pt) (car pt)))(define on-y-axis?(lambda (pt) (= (x-coor pt) 0)))(x-coor (make-point <x> <y>)) = <x>6.001 SICP8/41Symbol: a primitive type• constructors: None since really a primitive, not an object with parts• Only way to “make one” is to type it– (or via string->symbol from character strings, but shhhh…)• selectorsNone– (except symbol->string)• operations:symbol? ; type: anytype -> boolean(symbol? (quote alpha)) ==> #teq? ; discuss in a minuteR5RS shows thefull riches of Scheme6.001 SICP9/41What’s the difference between symbols and strings?• Symbol• Evaluates to the value associated with it by define• Every time you type a particular symbol, you get the exact same one! Guaranteed.– Called interning• E.g., (list (quote pi)(quote pi))• String• Evaluates to itself• Every time you type a particular string, it’s up to the implementation whether you get the same one or different ones.• E.g., (list ”pi” ”pi”)orpi”pi””pi””pi”6.001 SICP10/41The operation eq? tests for the same object • a primitive procedure• returns #t if its two arguments are the same object•very fast (eq? (quote eps) (quote eps)) ==> #t(eq? (quote delta) (quote eps)) ==> #f• For those who are interested:; eq?: EQtype, EQtype ==> boolean; EQtype = any type except number or string• One should therefore use = for equality of numbers, not eq?6.001 SICP11/41Making list structure with symbols((red 700) (orange 600) (yellow 575) (green 550)(cyan 510) (blue 470) (violet 400))(list (list (quote red) 700) (list (quote orange) 600)… (list (quote violet) 400))red 700orange 600violet 4006.001 SICP12/41More Syntactic Sugar• To the reader,’piis exactly the same as if you had typed(quote pi)• Remember REPL'pi;Value: piUser types’pi(quote pi)readpievalpiprint36.001 SICP13/41More Syntactic Sugar• To the reader,’piis exactly the same as if you had typed(quote pi)• Remember REPL'pi;Value: pi'17;Value: 17'"hi there";Value: "hi there"User types’17(quote 17)read17eval17print6.001 SICP14/41More Syntactic Sugar• To the reader,’piis exactly the same as if you had typed(quote pi)• Remember REPL'pi;Value: pi'17;Value: 17'"hi there";Value: "hi there"'(+ 3 4);Value: (+ 3 4)User types’(+ 3 4)(quote(+ 3 4))read(+ 3 4)eval(+ 3 4)print6.001 SICP15/41More Syntactic Sugar• To the reader,’piis exactly the same as if you had typed(quote pi)• Remember REPL'pi;Value: pi'17;Value: 17'"hi there";Value: "hi there"'(+ 3 4);Value: (+ 3 4)''pi;Value: (quote pi)But in Dr. Scheme,'piUser types’’pi(quote (quote pi))read(quote pi)eval(quote pi)print6.001 SICP16/41But wait… Clues about “guts” of Scheme(pair? (quote (+ 2 3)));Value: #t(pair? '(+ 2 3));Value: #t(car '(+ 2 3));Value: +(cadr '(+ 2 3));Value: 2(null? (cdddr '(+ 2 3)));Value: #t+23Now we know that expressions are represented by lists!6.001 SICP17/41Your turn: what does evaluating these print out?(define x 20)(+ x 3) ==>'(+ x 3) ==>(list (quote +) x '3) ==>(list '+ x 3) ==>(list + x 3) ==>6.001 SICP19/41Grimson’s Rule of Thumb for Quote'(quote fred (quote quote) (+ 3 5))(quote (quote fred (quote quote) (+ 3 5)))???46.001 SICP21/41Revisit making list structure with symbols(list (list (quote red) 700) (list (quote orange) 600)… (list (quote violet) 400))(list (list ’red 700) (list ’orange 600) … (list ’violet 400))’((red 700) (orange 600) (yellow 575) (green 550)(cyan 510) (blue 470) (violet 400))• Because the reader knows how to turn parenthesized (for lists) and dotted (for pairs) expressions into list structure!red 700orange 600violet 4006.001 SICP22/41Aside: What all does the reader “know”?• Recognizes and creates• Various kinds of numbers– 312 ==> integer– 3.12e17 ==> real, etc.• Strings enclosed by “…”• Booleans #t and #f• Symbols• ’… ==> (quote …)• (…) ==> pairs (and lists, which are made of pairs)• and a few other obscure things6.001 SICP23/41Traditional LISP structure: association list• A list where each element is a list of the key and value.15x20yx: 15y: 20 • Represent the tableas the alist: ((x 15) (y 20))6.001 SICP24/41Alist operation: find-assoc(define
View Full Document
Unlocking...