6.001 Final Exam ReviewSpring 2005By Gerald DalleyStudy Resources• Lectures– 2005-05-12 lecture had some good summary portions (+ preview of future courses)• Previous exams– Skip any problems with ec-eval or (goto …)• Online tutor• Tutorial problemsTopics• Scheme• Procedures and recursion• Orders of growth• Data abstractions• Higher-order procedures• Program methodology• Symbols and quotation• Abstract data types• Mutation• Environment model• Object-oriented systems• Interpretation / evaluation• Lazy evaluation• Asynchronous computingFall 1998 Exam: True/False• If the Scheme evaluator supports the delay and force special forms, it is possible for the Scheme user to implement cond as a simple procedure without additional extensions to the evaluator.– False: delay requires that the user explicitly mark delayed expressions. The cond “procedure” needs to implicitly delay all of its arguments.• Deadlock can occur between two processes that are running in parallel if a mutual exclusion approach is used (such as the synchronization approach discussed in class) in which both processes try to gain access to a single shared resource.– False: we need two shared resources for deadlock (given the scheme presented in class)Box-and-Pointers(definedefinedefinedefine mob '(1 2 3 4))(setsetsetset----cdrcdrcdrcdr!!!! (cdddrcdddrcdddrcdddr mob) mob)(definedefinedefinedefine (l x y) (setsetsetset----car!car!car!car! x y) (setsetsetset----car!car!car!car! y x))(l mob (cddrcddrcddrcddr mob))(l (cdrcdrcdrcdr mob) (cdddrcdddrcdddrcdddr mob))mobBox-and-Pointers(definedefinedefinedefine mob '(1 2 3 4))(setsetsetset----cdrcdrcdrcdr!!!! (cdddrcdddrcdddrcdddr mob) mob)(definedefinedefinedefine (l x y) (setsetsetset----car!car!car!car! x y) (setsetsetset----car!car!car!car! y x))(l mob (cddrcddrcddrcddr mob))(l (cdrcdrcdrcdr mob) (cdddrcdddrcdddrcdddr mob))mob1324mobListless Fun• What is the final value of z? (definedefinedefinedefine x '(1 2 3))(definedefinedefinedefine y '(4 5 6))(definedefinedefinedefine z (listlistlistlist (listlistlistlist (listlistlistlist x y)) x 7))(setsetsetset----cdrcdrcdrcdr!!!! (cddrcddrcddrcddr x) (thirdthirdthirdthird z))• ((((1 2 3 . 7) (4 5 6))) (1 2 3 . 7) 7)Orders of Growth(definedefinedefinedefine (find-e n) (ifififif (==== n 0) 1. (++++ (//// (fact n)) (find-e (---- n 1))))) • Time: Θ(n2) • Space: Θ(n)(definedefinedefinedefine (fast-expt x n) (condcondcondcond ((==== n 0) 1) ((even? even? even? even? n) (fast-expt (**** x x) (//// n 2))) (else else else else (**** x (fast-expt x (---- n 1)))))) • Time: Θ(log n) • Space: Θ(log n)Environmental Trivia• To drop a frame…(let ((…) …) …)(proc …)• To create a double-bubble…(let ((…) …) …) if desugaring(lambda (…) …)(define (foo …) …)• Environments form what type of a graph (e.g. chain, tree, directed acyclic graph, general graph, …)?– Tree• (Re)memorize the environment model!a bcWrite the Scheme Code to Create the Following Environment DiagramGEWrite the Scheme Code to Create the Following Environment Diagrama bc(load "env-dia.scm")(define define define define c(letletletlet ((a (let let let let ((b nilnilnilnil))(lambda lambda lambda lambda (newb)(set! set! set! set! b newb)b))))(a (lambdalambdalambdalambda (x) (**** x x)))))(env-dia 'render "tricky")GEOOPs• In the following code, how many references are created to the “anakin” symbol?(definedefinedefinedefine (walker self name speed) (letletletlet ((named-part (named-object self name))) …))(definedefinedefinedefine (biker self name speed)(letletletlet ((named-part (named-object self name))) …))(definedefinedefinedefine (swimmer self name speed)(letletletlet ((named-part (named-object self name))) …))(definedefinedefinedefine (tri-athlete self name walk-speed bike-speed swim-speed)(letletletlet ((walker-part (walker self name walk-speed))(biker-part (biker self name bike-speed))(swimmer-part (swimmer self name swim-speed))) …))(definedefinedefinedefine (jedi self name)(letletletlet ((tri-athlete-part (tri-athelete self name 20 50 15))) …))(definedefinedefinedefine anakin (create-jedi 'anakin))• 8 (3 named-objects, walker, biker, swimmer, tri-athlete, jedi)– Moral: multiple personalities lead to Sithdom.Meandering Streams(define define define define ones (consconsconscons----streamstreamstreamstream 1 ones))(define define define define ints(consconsconscons----streamstreamstreamstream 1 (add-streams ones ints)))(define define define define (row rnum col-stream)(if if if if (null? null? null? null? col-stream) '()(consconsconscons----stream stream stream stream (list list list list rnum (streamstreamstreamstream----car car car car col-stream))(row rnum (streamstreamstreamstream----cdrcdrcdrcdr col-stream)))))(define define define define (block started-rows next-row col-stream)(define define define define (helper sr)(if if if if (null?null?null?null? sr)(block (appendappendappendappend(mapmapmapmap stream-cdr started-rows)(listlistlistlist (row (streamstreamstreamstream----carcarcarcar next-row) col-stream)))(streamstreamstreamstream----cdrcdrcdrcdr next-row)col-stream)(consconsconscons----stream stream stream stream (streamstreamstreamstream----carcarcarcar (carcarcarcar sr))(helper (cdrcdrcdrcdr sr)))))(helper (reversereversereversereverse started-rows)))(show-stream (block nil ints ints) 15)…………………(4 4)(4 3)(4 2)(4 1)4…(3 4)(3 3)(3 2)(3 1)3…(2 4)(2 3)(2 2)(2 1)2…(1 4)(1 3)(1 2)(1 1)1…4321What gets displayed by show-stream?(1 1) (2 1) (1 2) (3 1) (2 2) (1 3) (4 1) (3 2) (2 3) (1 4) (5 1) (4 2) (3 3) (2 4) (1 5)• What are the possible values for z at the completion of the parallel-execution below?(definedefinedefinedefine z 5)(definedefinedefinedefine (P1) (set!set!set!set! z (++++ z 10)))(definedefinedefinedefine (P2) (set!set!set!set! z (**** z 2)))(parallelparallelparallelparallel----executeexecuteexecuteexecute P1 P2)Fall 1998 Exam: InterleavingsFall 1998 Exam: Interleavings(+ z 10))(set! z(* z 2))(set! z 30(+ z 10))(* z 2))(set! z(set! z 10(+ z 10))(* z 2))(set! z(set! z 15(* z 2))(+ z 10))(set! z(set! z 10(* z 2))(+ z 10))(set! z(set! z 15(* z 2))(set! z(+ z 10))(set! z 20foreach special form(foreachforeachforeachforeach var expbody-expbody-exp)(foreachforeachforeachforeach x (listlistlistlist 1 2 3 4 5)(displaydisplaydisplaydisplay x) (displaydisplaydisplaydisplay "
View Full Document
Unlocking...