DOC PREVIEW
MIT 6 001 - Structure and Interpretation of Computer Programs

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

16.001 SICP1/406.001: Structure and Interpretation of Computer Programs• Symbols•A-lists• Example of using symbols• Differentiation6.001 SICP2/40• 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 SICP3/40Symbols?• Say your favorite color• What is the difference?• Say “your favorite color”6.001 SICP4/40Symbols?• Say your favorite color• What is the difference?• In one case, we want the meaning associated with the expression• In the other case, we want the actual words (or symbols) of the expression• Say “your favorite color”6.001 SICP5/40Creating and Referencing Symbols• How do I create a symbol?(define alpha 27)• How do I reference a symbol’s value?alpha;Value: 27• How do I reference the symbol itself?e.g,: How can I build this list: (27 alpha)(list alpha _???_)(27 alpha )6.001 SICP6/40Quote• Need a way of telling interpreter: “I want the following object as a data structure, not as an expression to be evaluated”(quote alpha);Value: alpha26.001 SICP7/40Symbol: a primitive type• constructors: None since really a primitive not an object with parts• selectorsNone• operations:symbol? ; type: anytype -> boolean(symbol? (quote alpha)) ==> #teq? ; discuss in a minute6.001 SICP8/40Symbol: printed representation(lambda (x) (* x x))evallambda-ruleA compound procthat squares itsargument#[compound-...]print(quote beta)evalquote-rulesymbolprintbetabetaThe reader converts this expression into an internal representation of the symbol6.001 SICP9/40Symbols are ordinary values(list 1 2) ==> (1 2)symbolgammasymboldelta(list (quote delta) (quote gamma)) ==> (delta gamma)6.001 SICP10/40A useful property of the quote special form(list (quote delta) (quote delta))symboldeltaTwo quote expressions with the same name return the same object symboldelta6.001 SICP11/40The 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 SICP12/40Expression: Reader converts to: Prints out as:1. (quote a) a a2. (quote (a b)) (a b)3. (quote 1) 1 14. (quote “foobar”) “foobar” “foobar”Generalization: quoting other expressionsIn general, (quote DATUM) is converted to DATUMa b36.001 SICP13/40Shorthand: the single quote mark'a is shorthand for (quote a)'(1 2) (quote (1 2))6.001 SICP14/40Your turn: what does evaluating these print out?(define x 20)(+ x 3) ==>'(+ x 3) ==>(list (quote +) x '3) ==>(list '+ x 3) ==>(list + x 3) ==>23(+ x 3)(+ 20 3)(+ 20 3)([procedure #…] 20 3)6.001 SICP15/40Your turn: what does evaluating these print out?(define x 20)(+ x 3) ==>'(+ x 3) ==>(list (quote +) x '3) ==>(list '+ x 3) ==>(list + x 3) ==>23(+ x 3)(+ 20 3)(+ 20 3)([procedure #…] 20 3)6.001 SICP16/40Davis’ Rule of Thumb for Quote(list '(quote fred (quote quote) (+ 3 5)))(list (quote (quote fred (quote quote) (+ 3 5))))???6.001 SICP17/40The Davis Rule of Thumb for Quote'((quote fred) (quote quote) (+ 3 5)))(quote ((quote fred) (quote quote) (+ 3 5))))???What's the value of the quoted expression?WHATEVER IS UNDER YOUR THUMB (subject to reader’s actions)!(‘fred ‘quote (+ 3 5))'6.001 SICP18/40Traditional 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))46.001 SICP19/40Alist operation: find-assoc(define (find-assoc key alist)(cond((null? alist) #f)((equal? key (caar alist)) (cadar alist))(else (find-assoc key (cdr alist)))))(define a1 '((x 15) (y 20)))(find-assoc 'y a1) ==> 2015x20y6.001 SICP20/40An aside on testing equality• = tests equality of numbers• Eq? Tests equality of symbols(for now, we’ll see later applies to other structures)• Equal? Tests equality of symbols, numbers or lists of symbols and/or numbers that print the same6.001 SICP21/40Alist operation: add-assoc(define (add-assoc key val alist) (cons (list key val) alist))(define a2 (add-assoc 'y 10 a1))a2 ==> ((y 10) (x 15) (y 20))(find-assoc 'y a2) ==> 10We say that the new binding for y “shadows” the previous one6.001 SICP22/40Alists are not an abstract data type• Missing a constructor:• Used quote or list to construct(define a1 '((x 15) (y 20)))• There is no abstraction barrier: the implementation is exposed. • User may operate on alists using standard list operations.(filter (lambda (a) (< (cadr a) 16)) a1))==> ((x 15))6.001 SICP23/40Why do we care that Alists are not an ADT?• Modularity is essential for software engineering• Build a program by sticking modules together• Can change one module without affecting the rest• Alists have poor modularity• Programs may use list ops like filter and map on alists• These ops will fail if the implementation of alists change• Must change whole program if you want a different table• To achieve modularity, hide information•Hidethe fact that the table is implemented as a list• Do not allow rest of program to use list operations• ADT techniques exist in order to do this6.001 SICP24/40Symbolic differentiation(deriv <expr> <with-respect-to-var>) ==> <new-expr>(+ x (+ y 3))X+ y + 3(* 5 y)5yXX(+ x 3)X + 3RepresentationAlgebraic expression(deriv '(+ x 3) 'x) ==> 1(deriv '(+ (* x y) 4) 'x) ==> y(deriv '(* x x) 'x) ==> (+ x x)56.001 SICP25/40Building a system for differentiationExample of:• Lists of lists• How to use the symbol type• Symbolic manipulation 1. how to get started2. a direct implementation3. a better implementation6.001 SICP26/401. How to get started•Analyze the problem preciselyderiv constant dx = 0deriv variable dx = 1 if variable is the same as x= 0 otherwisederiv (e1+e2) dx = deriv e1 dx + deriv e2 dxderiv (e1*e2) dx = e1 * (deriv e2 dx) + e2 * (deriv e1 dx)•Observe:•e1 and e2 might be complex subexpressions•derivative of (e1+e2) formed from deriv


View Full Document

MIT 6 001 - Structure and Interpretation of Computer Programs

Documents in this Course
Quiz 1

Quiz 1

6 pages

Databases

Databases

12 pages

rec20

rec20

2 pages

Quiz II

Quiz II

15 pages

Streams

Streams

5 pages

Load more
Download Structure and Interpretation of Computer Programs
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Structure and Interpretation of Computer Programs and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Structure and Interpretation of Computer Programs 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?