;;; 6.945 Problem Set #2 ;;; 02/17/2009 ;;; Bryan Newbold 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.