"Greg Morrisett" <jgm@cs.cornell.edu> writes:
What a pain... This is why ML got this right.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Matthias Blume <blume@mocha.cs.princeton.edu> wrote:
Since that was what started the thread: ML is such a
^^^^^^^^^^^^
language, and it gets this issue exactly right.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
I'm not so sure. Let me give you some examples:
1. We all agree that that EQUAL? should not be defined on procedures. Because
EQUAL? is defined extensionally and equality of procedures is undecidable.
But it is nonetheless *useful* to compare *intensions* of procedures (i.e.
representations of procedures, in other words code pointers) for equality.
Inter alia, this arrises in the following situation. Suppose I had a
representation of logic variables. And I could attach constraints to them.
For efficiency, I would want to make sure that the same constraint doesn't get
attached multiple times.
(define-structure logic-variable value constraints)
(define (assert! constraint logic-variable)
(unless (memq constraint (logic-variable-constraints logic-variable))
(set-logic-variable-constraints!
logic-variable
(cons constraint (logic-variable-constraints logic-variable))))
(for-each (lambda (constraint) (constraint logic-variable))
(logic-variable-constraints logic-variable)))
Now, I can't do (MEMBER CONSTRAINT (LOGIC-VARIABLE-CONSTRAINTS LOGIC-VARIABLE))
because this uses EQUAL? which is undefined on procedures. But procedures
(at least ones without closures) are immutable. So I can't do
(MEMQ CONSTRAINT (LOGIC-VARIABLE-CONSTRAINTS LOGIC-VARIABLE)) either because
this uses EQ?. But I *want* to be able to do this. Because it is *useful*.
It can reduce the complexity class of many algorithms. IMHO, this is an issue
that ML gets dead wrong and Scheme gets almost right.
2. Scheme doesn't get this quite right either. In fact, no language that I
know of gets this right. As the following example shows. We already said that
EQUAL? is undefined on procedures. And EQ? only really works on procedures
without closures. (Ignore for the moment that it is undecidable whether a
procedure requires a closure:
(lambda (x)
(lambda ()
(if (goldbachs-conjecture-is-true?)
x
#f))))
Suppose, using the above example, I wish to do:
(define (assert->! x n) (assert! (lambda (y) (> y n)) x))
(let ((x (create-logic-variable)))
(assert->! x 1)
(assert->! x 1))
In order to not redundantly assert the same constraint twice, I need to
compare closures for equivalence. I can't do that in Scheme (or ML, or any
language that I know of). Extending EQUAL? to compare closures is really not
the right thing to do because EQUAL? does a comparison of unbounded depth.
Often, I want to do something between EQ? and EQUAL?. Like:
(define (list-contents-eq? l1 l2)
(and (list? l1)
(list? l2)
(= (length l1) (length l2))
(every eq? l1 l2)))
So I need to be able to build my own equality predicates. To do that I need
component accessors. In Scheme, I can access pair and structure slots, and I
can access vector and string elements. But I can't access closure slots.
3. This leads to a third example. One that doesn't involve procedural
equality. But does involve shallow versus deep comparisons. Suppose I wish
to represent sets as lists without duplicates. And I have the usual complement
of procedures to do so. Such procedures ultimately must compare objects for
equality to build the notion of duplicate. Now suppose I wish to have sets of
circular objects. In most existing implementations, the only way to create
circular objects is by mutation. But one could imagine situations where I only
mutated objects to create circular representations and then never mutated them
again. And one could imagine a language that allowed me to declare such
objects as immutable after their creation. Or one could imagine an
implementation that infered that such objects were immutable after their
creation. I can't compare such objects for equality using EQUAL? because
EQUAL? won't terminate on circular objects. (Though I could make a version of
EQUAL? that did work.) So I might want to use EQ?. But I can only do so if EQ?
works on immutable objects. And even if I could use EQUAL? (either because I
made a circular version or because I wasn't using circular object), I might
have large objects and I might intern them precisely so I could later compare
them with EQ? instead of EQUAL?
Jeff (home page http://www.emba.uvm.edu/~qobi)
|