diff options
Diffstat (limited to 'ps02_generics/bnewbold_ps02.txt')
| -rw-r--r-- | ps02_generics/bnewbold_ps02.txt | 94 |
1 files changed, 94 insertions, 0 deletions
diff --git a/ps02_generics/bnewbold_ps02.txt b/ps02_generics/bnewbold_ps02.txt new file mode 100644 index 0000000..1e6fbb5 --- /dev/null +++ b/ps02_generics/bnewbold_ps02.txt @@ -0,0 +1,94 @@ +;;; 6.945 Problem Set #2 +;;; 02/17/2009 +;;; Bryan Newbold <bnewbold@mit.edu> + + +Problem 2.1 +------------------------ +(see attached code: gen-full-seq.scm) + +Problem 2.2 +------------------------ +(see attached code: amended-specs.txt, + gen-full-seq.scm) + +I changed sequence:append, sequence:map, sequence:for-each, and added +sequence:elements-equal? to the specifications, but I only implemented the +changes to sequence:append. + +Problem 2.3 +------------------------ +As we saw with sequence:append, the nice thing about folding with generic +operators is that the "unspecified arity" part of the arguments can be made +of any type of objects; this flexibility can be powerful. However, it could be +more difficult to remove this ambiguity: if you only wanted, for instance, +an arbitrary number of strings, you will have to check every single element +of the argument while folding, or create special non-generic operators which +check for themselves. + +One way to implement this flexibility would be to add a formal argument to +make-generic-operator which would flag that the last predicate should be +repeated for arbitrary many arguments, and save this flag in the table. Then +specify either a specific predicate or any? when using assign-operation, and +the operator defined within make-generic-operator would have to know to check +for this flag when it has extra arguments and reapply the last predicate to all +successive arguments. + +Problem 2.4 +------------------------ +A) The problem with Louis' implementation is that the car-s of the two lists +aren't checked properly leading to possible not-well-orderings such as: + +'(2 1) < '(1 2) => true +'(1 2) < '(2 1) => true + +And so either of the following ordered lists could be generated as sets: + +'(1 (2 1) (1 2) (a b c)) +'(1 (1 2) (2 1) (a b c)) + +which ruins the 1-1 correspondence between ordered lists and sets. + +B) It would be harder to extend Alyssa's implementation because it is not +modular: if later on Ben wanted to add a complex number type to the ordering +and Louis wanted to add a puppy type to the ordering, they would both have to +edit the single generic:less? procedure: loading one new version or the other +would clobber the other's changes. + +C) (see attached code: gen-full-seq.scm) + +D) Without Alyssa's recommendation, I wouldn't have been able to reuse the +existing scheme list manipulation tools and get correct results with reasonable +computational complexity; the ordering makes the existing algorithms run +quickly. Rewriting all of the set membership searches for a different data +structure would have taken a lot of code and could potentially have had high +computational overhead. Of course using hash tables or other techniques could +improve membership searches even more... + +Problem 2.5 +------------------------ +Playing off the themes of this course, using predicate dispatch allows us to +reuse existing data structures and types in ways they may not have originally +been intended for. For systems with types already tagged, the predicate call +overhead should be minimal, and for systems without tagging, it is very +possible that the predicate overhead is not greater than the resources required +to tag all of the individual objects. Using memoization would further reduce +overhead by essentially only tagging those objects whose type will be important +later. + +The predicate method also allows for additional flexibility when considering +complicated type hierarchies; primitives would either have to be multiply +tagged, have a more intelligent tag-checking predicate (eg, return multiple +tags: *complex*, *real*, and *rational* for a tagged *rational* number), or +have a HUGE procedure lookup table. + +I can't really think of a situation where the performance overhead of tags +versus predicate dispatch would matter at all: any performance critical +operation should be optimizing with static types anyways. Maybe a tagged data +dispatch system would be easier for compiler to analyze and optimize? + +In short, a predicate dispatch /system/ can accommodate tagged /data/ quite +easily with no loss of flexibility. Data with associated predicates could +easily be statically tagged in specific instances with a loss of flexibility +but the potential for run-time efficiency. + |