DOC PREVIEW
MIT 6 001 - Lecture Notes

This preview shows page 1-2-3-18-19-37-38-39 out of 39 pages.

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

Unformatted text preview:

Today’s topicsProcedural abstractionProcedural abstraction example: sqrtThe universe of procedures for sqrtSlide 5sqrt - Block StructureSummary of part 1Language ElementsCompound dataPairs (cons cells)Compound DataPair AbstractionPair abstractionUsing pair abstractions to build proceduresSlide 15Grouping together larger collectionsConventional interfaces -- listsConventional Interfaces - Lists… to be really carefulCommon patterns of data manipulationCommon Pattern #1: cons’ing up a listCommon Pattern #2: cdr’ing down a listCdr’ing and Cons’ing ExamplesCommon Pattern #3: Transforming a ListSlide 25Lessons learnedPairs, Lists, & TreesElements of a Data AbstractionRational numbers as an exampleRational Number AbstractionSlide 31Alternative Rational Number Abstractionprint-rat Layered OperationLayered Rational Number OperationsUsing our system“Rationalizing” ImplementationAlternative “Rationalizing” ImplementationAlternative +rat OperationsSlide 396.001 SICP1/39Today’s topics•Abstractions•Procedural •Data •Relationship between data abstraction and procedures that operate on it•Isolating use of data abstraction from details of implementation6.001 SICP2/39Procedural abstraction•Process of procedural abstraction•Define formal parameters, capture pattern of computation as a process in body of procedure•Give procedure a name•Hide implementation details from user, who just invokes name to apply procedureInput: typeOutput: typeDetails of contract for converting input to outputprocedure6.001 SICP3/39Procedural abstraction example: sqrtTo find an approximation of square root of x:• Make a guess G• Improve the guess by averaging G and x/G• Keep improving the guess until it is good enough(define try (lambda (guess x) (if (good-enuf? guess x) guess (try (improve guess x) x))))(define improve (lambda (guess x) (average guess (/ x guess))))(define average (lambda (a b) (/ (+ a b) 2)))(define good-enuf? (lambda (guess x) (< (abs (- (square guess) x)) 0.001)))(define sqrt (lambda (x) (try 1 x)))6.001 SICP4/39The universe of procedures for sqrttryimproveaverageGood-enuf?sqrt6.001 SICP5/39The universe of procedures for sqrtaveragetryimproveGood-enuf?sqrt6.001 SICP6/39sqrt - Block Structure(define sqrt (lambda (x) (define good-enuf? (lambda (guess) (< (abs (- (square guess) x)) 0.001))) (define improve (lambda (guess) (average guess (/ x guess)))) (define sqrt-iter (lambda (guess) (if (good-enuf? guess) guess (sqrt-iter (improve guess))))) (sqrt-iter 1.0)) )good-enuf?improvesqrt-itersqrtx: number : numberx6.001 SICP7/39Summary of part 1•Procedural abstractions•Isolate details of process from its use•Designer has choice of which ideas to isolate, in order to support general patterns of computation6.001 SICP8/39Language Elements•Primitives•prim. data: numbers, strings, booleans•primitive procedures•Means of Combination•procedure application•compound data (today)•Means of Abstraction•naming•compound procedures–block structure–higher order procedures (next time)•conventional interfaces – lists (today)•data abstraction6.001 SICP9/39Compound data•Need a way of gluing data elements together into a unit that can be treated as a simple data element•Need ways of getting the pieces back out•Ideally want the result of this “gluing” to have the property of closure:•“the result obtained by creating a compound data structure can itself be treated as a primitive object and thus be input to the creation of another compound object”•Need a contract between the “glue” and the “unglue”6.001 SICP10/39Pairs (cons cells)•(cons <x-exp> <y-exp>) ==> <P> •Where <x-exp> evaluates to a value <x-val>, and <y-exp> evaluates to a value <y-val>•Returns a pair <P> whose car-part is <x-val> and whose cdr-part is <y-val>•(car <P>) ==> <x-val> •Returns the car-part of the pair <P>•(cdr <P>) ==> <y-val>•Returns the cdr-part of the pair <P>6.001 SICP11/39Compound Data•Treat a PAIR as a single unit:•Can pass a pair as argument•Can return a pair as a value1 2 3 4 554321(2, 3)point(define (make-point x y) (cons x y))(define (point-x point) (car point))(define (point-y point) (cdr point))(define (make-seg pt1 pt2) (cons pt1 pt2))(define (start-point seg) (car seg))6.001 SICP12/39Pair Abstraction•Constructor; cons: A,B -> A X B; cons: A,B -> Pair<A,B>(cons <x> <y>) ==> <P>•Accessors; car: Pair<A,B> -> A(car <P>) ==> <x>; cdr: Pair<A,B> -> B(cdr <P>) ==> <y>•Predicate; pair? anytype -> boolean(pair? <z>) ==> #t if <z> evaluates to a pair, else #f6.001 SICP13/39Pair abstraction•Note how there exists a contract between the constructor and the selectors:•(car (cons <a> <b> ))  <a>•(cdr (cons <a> <b> ))  <b>•Note how pairs have the property of closure – we can use the result of a pair as an element of a new pair:•(cons (cons 1 2) 3)6.001 SICP14/39Using pair abstractions to build procedures•Here are some data abstractions(define p1 (make-point 1 2))(define p2 (make-point 4 3))(define s1 (make-seg p1 p2))1 2 3 4 554321(define stretch-point (lambda (pt scale) (make-point (* scale (point-x pt)) (* scale (point-y pt)))))(stretch-point p1 2)  (2 . 4)p1  (1 . 2)SelectorConstructor6.001 SICP15/39Using pair abstractions to build procedures•Generalize to other structures(define stretch-seg (lambda (seg sc) (make-seg (stretch-point (start-pt seg) sc) (stretch-point (end-pt seg) sc))))(define seg-length (lambda (seg) (sqrt (+ (square (- (point-x (start-point seg)) (point-x (end-point seg)))) (square (- (point-y (start-point seg)) (point-y (end-point seg))))))))1 2 3 4 554321Selector for segmentSelector for point6.001 SICP16/39Grouping together larger collections•Suppose we want to group together a set of points. Here is one way(cons (cons (cons (cons p1 p2) (cons p3 p4)) (cons (cons p5 p6) (cons p7 p8))) p9)•UGH!! How do we get out the parts to manipulate them?6.001 SICP17/39Conventional interfaces -- lists•A list is a data object that can hold an arbitrary number of ordered items.•More formally, a list is a sequence of pairs with the following properties:•Car-part of a pair in sequence – holds an item•Cdr-part of a pair in sequence


View Full Document

MIT 6 001 - Lecture Notes

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 Lecture Notes
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 Lecture Notes 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 Lecture Notes 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?