6.001 Tutorial 4Structure and Interpretation of Computer Programs March 5, 2007Data Abstraction, HOPs, Good Coding, and Quiz 1 ReviewData AbstractionWhen constructing your own data type, you need to use some underlying representation for thedata. Lists are generally the best way to go. However, you want to abstract away the und erlyingrepresentation for a few reasons. It makes it easier to change later. It also makes it easier to writeyour co de because you don’t have to remember the representation. So, you keep your repr esentationwalled-off behind a fence. Obviously something has to know your representation, so there are acouple of gatekeepers: functions that are aware of the representation and provide an interface tothe data type for the rest of the program:Constructor Creates an instance of the data type (ie make−point)Accessors (or Selectors) Gets values out of an data type (ie get−x and get−y)Other than these functions, the r est of the program is ignorant of the representation. Everythingelse must go through this interface to access the data type. These gatekeepers must be very carefullywritten, so write as much as possible above the abstraction barrier.Higher-order ProceduresWe’ve already seen these, now we just have a name for them. Higher-order procedures are simplyprocedures which take or return other procedures.HOP’s are particularly useful for manipulating lists:(map <procedure> <list>) – Apply ‘procedure’ to every element of ‘list’, returning the list of results.( filter <procedure> <list>) – Apply ‘procedure’ to every element of ‘list’, returning the list of elementsfor which ‘procedure’ returned #t.Good ProgrammingGood programming is mostly an art that you develop from writing code an d reading code, butthere are some guidelines to get you started.• Document your code. No really. It’s called “code” for a reason. You won’t be able to readit later. This doesn’t just mean “write lots of comments”; things like variable and functionnames count as code documentation as well.• Plan your code. In these early projects, the structure of your code is basically given to you,but in bigger projects, you’ll need to thin k about how to take a big problem and break itdown into smaller problems that can be solved independently and tied together neatly.• Keep your code simple. A procedure should be short and should accomplish precisely the onething it’s supposed to accomplish. Put subproblems in other procedures. “A designer knowshe has achieved perfection not when there is nothing left to add, but when there is nothingleft to take away.” – Antoine de Saint-Exup’ery16.001 SICP Data Abstraction, HOPs, Good Coding, and Quiz 1 ReviewList HOP ExercisesWrite the following procedure without map and then with map:; ; M u l t i p l e e ver y element in ‘ l s t ’ by 2( d e f i n e ( d ou b le − li st l s t ))Evaluate the following expressions.(map o dd? (list 5 3 8 2 7))( filter odd? ( list 5 3 8 2 7))HOP Exercises; ; P a r t i a l l y a ppl y ‘ func ’ ( a f u nc t i o n o f two arguments : ‘ arg1 ’ and; ; ‘ arg2 ’ ) to ‘ arg1 ’ , r et u r n in g a f u nc ti o n t h a t t a k e s j u s t ‘ arg2 ’ .( d e f i n e ( p ar tia l −a p p l y fun c arg1 ))Rewrite double−list using map and partial−apply.( d e f i n e ( d ou b le − li st l s t ) )What is the type of double−list? What is the type of partial−apply?SetsImplement the following interface for sets of numbers.; ; Convert a l i s t i n t o a s e t( d e f i n e ( s e t : l is t − >s e t l s t )); ; Test wh ethe r or n o t a s e t c o n t ai n s an element( d e f i n e ( s e t : c on t ai n s? s e t e l t )); ; Compute t h e uni on o f two s e t s( d e f i n e ( s e t : union s1 s2 ))26.001 SICP Data Abstraction, HOPs, Good Coding, and Quiz 1 ReviewUsing Data AbstractionsUsing the set abstraction and filter , implement the following procedur e. Bonus points if you alsouse partial−apply.; ; Return t h e e lem en t s t h a t l i s t a and l i s t b have i n common , i n t he; ; o r der th e y appear i n a( d e f i n e ( l i s t − i n t e r s e c t i o n a b)( l e t ( ( b−set ( s e t : l i st − >s e t b ) ) ))Suppose set : list−>set takes O(n log n) time (where n is the length of the list) and set :contains? takesO(log n) time (where n is the size of the set). If a is n elements and b is m elements, how muchtime does list−difference take?Sets as FunctionsYet another representation of sets is as “predicate f unctions”. Instead of representing a set withdata, we represent it as a fu nction with type number → boolean. T his function returns #t if theargument is in the set and #f otherwise. Implement the above set interface using this representation.; ; Convert a l i s t i n t o a s e t( d e f i n e ( s e t : l is t − >s e t l s t ); ; Hint : member has t ype : a, list h ai → boolean1); ; Test wh e the r or not a s e t c o n t ai n s an elemen t( d e f i n e ( s e t : c on t ai n s? s e t e l t ) ); ; Compute t h e uni on o f two s e t s( d e f i n e ( s e t : union s1 s2 ))List HOP’s Brainteaser (foldr is nifty)Implement map, reverse, and append using foldr .HOP’s BrainteaserAnd you thought it was hard to make thin gs out of just lambdas. A combinator is a function whichcomposes functions taken as arguments and returns a function. Many combinator calculi are just aspowerf ul as the Lambda Calculus. The cool thing about combinator calculi is that they eliminate1This is a lie. member has type a, list hai → list hai | boolean . It returns the list starting at where the element isfound, or #f otherwise.36.001 SICP Data Abstraction, HOPs, Good Coding, and Quiz 1 Revieweven the need for variables because a program is just a composition of predefined combinators. Onepopular example is the SK-combinator Calculus, wh …
View Full Document
Unlocking...