DOC PREVIEW
MIT 6 001 - Procedural abstraction

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/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 : numberx26.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 #f36.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 – holds a pointer to rest of list•Empty-list nil – signals no more pairs, or end of list• Note that lists are closed under operations of consand cdr.6.001 SICP18/39Conventional Interfaces - Lists(cons <el1> <el2>)<el1><el2>Predicate(null? <z>)==> #t if <z> evaluates to empty list(list <el1> <el2> ... <eln>)<el1> <el2> <eln>…46.001 SICP19/39… to be really careful• For today we are going to create different constructors and selectors for a list• (define first car)• (define rest cdr)• (define adjoin cons)• Note how these abstractions inherit closure from the underlying abstractions!6.001 SICP20/39Common patterns of data manipulation• Have seen common patterns of procedures• When applied to data structures, often see common patterns of procedures as well• Procedure pattern reflects recursive nature of data structure• Both procedure and data structure rely on – Closure of data structure– Induction to ensure correct kind of result returned6.001 SICP21/39Common Pattern #1: cons’ing up a list(define (enumerate-interval from to)(if (> from to)nil(adjoin from(enumerate-interval(+ 1 from)to))))(e-i 2 4)(if (> 2 4) nil (adjoin 2 (e-i (+ 1 2) 4)))(if #f nil (adjoin 2 (e-i 3 4)))(adjoin


View Full Document

MIT 6 001 - Procedural abstraction

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 Procedural abstraction
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 Procedural abstraction 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 Procedural abstraction 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?