1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
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.
|
