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

This preview shows page 1-2-17-18-19-36-37 out of 37 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 37 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 37 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 37 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 37 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 37 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 37 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 37 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 37 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

6.001: Structure and Interpretation of Computer ProgramsReview: data abstractionSlide 4Creating and Referencing SymbolsQuoteSymbol: a primitive typeSymbol: printed representationSymbols are ordinary valuesA useful property of the quote special formThe operation eq? tests for the same objectGeneralization: quoting other expressionsShorthand: the single quote markSlide 15The Davis Rule of Thumb for QuoteTraditional LISP structure: association listAlist operation: find-assocAn aside on testing equalityAlist operation: add-assocAlists are not an abstract data typeWhy do we care that Alists are not an ADT?Symbolic differentiationBuilding a system for differentiation1. How to get startedType of the data will guide implementation2. A direct implementationSimple expressionsCompound expressionsSum expressionsThe direct implementation works, but...3. A better implementationUse data abstractionsA better implementationIsolating changes to improve performanceModularity makes changes easierJust change data abstractionModularity helps in other waysSeparating out aspects of simplification6.001 SICP 1/406.001: Structure and Interpretation of Computer Programs•Symbols•Alists•Example of using symbols•Differentiation6.001 SICP 2/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 SICP 4/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 SICP 5/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 SICP 6/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: alpha6.001 SICP 7/40Symbol: a primitive type•constructors: None since really a primitive not an object with parts•selectors None•operations: symbol? ; type: anytype -> boolean (symbol? (quote alpha)) ==> #t eq? ; discuss in a minute6.001 SICP 8/40Symbol: printed representation(lambda (x) (* x x))evallambda-ruleA compound procthat squares itsargument#[compound-...]print(quote beta)evalquote-rulesymbolprintbetabeta6.001 SICP 9/40Symbols are ordinary values(list 1 2) ==> (1 2)symbolgammasymboldelta(list (quote delta) (quote gamma)) ==> (delta gamma)6.001 SICP 10/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 SICP 11/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 SICP 12/40 Expression: Reader converts to: Prints out as:1. (quote a) a a2. (quote (a b)) (a b) 3. (quote 1) 1 1Generalization: quoting other expressionsIn general, (quote DATUM) is converted to DATUMa b6.001 SICP 13/40Shorthand: the single quote mark'a is shorthand for (quote a)'(1 2) (quote (1 2))6.001 SICP 15/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 SICP 17/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!((quote fred) (quote quote) (+ 3 5)))'6.001 SICP 18/40Traditional LISP structure: association list•A list where each element is a list of the key and value.15x20yx: 15y: 20 • Represent the table as the alist: ((x 15) (y 20))6.001 SICP 19/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 SICP 20/40An aside on testing equality•= tests equality of numbers•Eq? Tests equality of symbols•Equal? Tests equality of symbols, numbers or lists of symbols and/or numbers that print the same6.001 SICP 21/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 SICP 22/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 SICP 23/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•Hide the 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 SICP 24/40Symbolic differentiation(deriv <expr> <with-respect-to-var>) ==> <new-expr>Algebraic expression RepresentationX + 3 (+ x 3)X X5y (* 5 y)X+ y + 3 (+ x (+ y 3))(deriv '(+ x 3) 'x) ==> 1(deriv '(+ (* x y) 4) 'x) ==>


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?