shivers@bronto.soar.cs.cmu.EDU (Olin Shivers) (05/08/91)
In the revised report that I have (3.95) (eqv? (lambda (x) x) (lambda (x) x)) is explicitly undefined -- implementations can return either true or false. However, this is never spelled out for (eq? (lambda (x) x) (lambda (x) x)) Has this been settled? Transformations that beta-substitute lambda expressions need to know. -Olin
barmar@think.com (Barry Margolin) (05/08/91)
In article <9105080039.aa09228@mc.lcs.mit.edu> shivers@bronto.soar.cs.cmu.EDU (Olin Shivers) writes: >In the revised report that I have (3.95) > (eqv? (lambda (x) x) (lambda (x) x)) >is explicitly undefined -- implementations can return either true or false. > >However, this is never spelled out for > (eq? (lambda (x) x) (lambda (x) x)) >Has this been settled? (eq? x y) implies (eqv? x y), which implies (not (eqv? x y)) implies (not (eq? x y)). So, if those two procedures can be non-eqv, then they can be non-eq. -- Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
alan@lcs.mit.edu (Alan Bawden) (05/09/91)
In article <1991May8.063427.25012@Think.COM> barmar@think.com (Barry Margolin) writes: In article <9105080039.aa09228@mc.lcs.mit.edu> shivers@bronto.soar.cs.cmu.EDU (Olin Shivers) writes: >In the revised report that I have (3.95) > (eqv? (lambda (x) x) (lambda (x) x)) >is explicitly undefined -- implementations can return either true or false. > >However, this is never spelled out for > (eq? (lambda (x) x) (lambda (x) x)) >Has this been settled? (eq? x y) implies (eqv? x y), which implies (not (eqv? x y)) implies (not (eq? x y)). So, if those two procedures can be non-eqv, then they can be non-eq. This is true; if the EQV? case is undefined, it follows that the EQ? case -may- return #F. But perhaps Olin is wondering if (eq? (lambda (x) x) (lambda (x) x)) might be -required- to return #F (even though EQV? was allowed to be smarter and discover their equivalence). My memory is that the -intent- of the Revised Report authors was that EQ? was to be just as undefined as EQV? in this case.
carlton@husc10.harvard.edu (david carlton) (05/11/91)
In article <ALAN.91May9100139@august.lcs.mit.edu> alan@lcs.mit.edu (Alan Bawden) writes:
This is true; if the EQV? case is undefined, it follows that the EQ? case
-may- return #F. But perhaps Olin is wondering if
(eq? (lambda (x) x) (lambda (x) x))
might be -required- to return #F (even though EQV? was allowed to be
smarter and discover their equivalence).
It would certainly be out of character, since they allow
(eq? '(1 2) '(1 2))
, say, to be true.
My memory is that the -intent- of the Revised Report authors was that EQ?
was to be just as undefined as EQV? in this case.
Doubtless.
david carlton
carlton@husc9.harvard.edualan@lcs.mit.edu (Alan Bawden) (05/11/91)
In article <CARLTON.91May10135234@husc10.harvard.edu> carlton@husc10.harvard.edu (david carlton) writes: In article <ALAN.91May9100139@august.lcs.mit.edu> alan@lcs.mit.edu (Alan Bawden) writes: This is true; if the EQV? case is undefined, it follows that the EQ? case -may- return #F. But perhaps Olin is wondering if (eq? (lambda (x) x) (lambda (x) x)) might be -required- to return #F (even though EQV? was allowed to be smarter and discover their equivalence). It would certainly be out of character, since they allow (eq? '(1 2) '(1 2)) , say, to be true. Well, but certainly (eq? (cons 1 2) (cons 1 2)) is required to be false. I can imagine a programmer thinking it would be convenient if every evaluation of a LAMBDA-expression resulted in a unique (in the sense of EQ?) closure.
hanche@imf.unit.no (Harald Hanche-Olsen) (05/11/91)
In article <ALAN.91May10232758@august.lcs.mit.edu> alan@lcs.mit.edu (Alan Bawden) writes:
Well, but certainly
(eq? (cons 1 2) (cons 1 2))
is required to be false. I can imagine a programmer thinking it would be
convenient if every evaluation of a LAMBDA-expression resulted in a unique
(in the sense of EQ?) closure.
If I have understood it right, that form is required to be false
because of the existence of procedures like set-car! and set-cdr!
which could change equal-looking objects to look different. You
cannot change a closure in an analogous way. So what is so convenient
about (lambda (x) x) not being eq? to (lambda (x) x) ?
- Harald Hanche-Olsen <hanche@imf.unit.no>
Division of Mathematical Sciences
The Norwegian Institute of Technology
N-7034 Trondheim, NORWAYjinx@zurich.ai.mit.edu (Guillermo J. Rozas) (05/12/91)
In article <HANCHE.91May11164038@hufsa.imf.unit.no> hanche@imf.unit.no (Harald Hanche-Olsen) writes: Path: ai-lab!mintaka!think.com!sdd.hp.com!wuarchive!udel!rochester!kodak!uupsi!sunic!ugle.unit.no!hanche From: hanche@imf.unit.no (Harald Hanche-Olsen) Newsgroups: comp.lang.scheme Date: 11 May 91 14:40:38 GMT References: <9105080039.aa09228@mc.lcs.mit.edu> <1991May8.063427.25012@Think.COM> <ALAN.91May9100139@august.lcs.mit.edu> <CARLTON.91May10135234@husc10.harvard.edu> <ALAN.91May10232758@august.lcs.mit.edu> Sender: news@ugle.unit.no Organization: The Norwegian Institute of Technology, Trondheim, Norway. Lines: 20 In article <ALAN.91May10232758@august.lcs.mit.edu> alan@lcs.mit.edu (Alan Bawden) writes: Well, but certainly (eq? (cons 1 2) (cons 1 2)) is required to be false. I can imagine a programmer thinking it would be convenient if every evaluation of a LAMBDA-expression resulted in a unique (in the sense of EQ?) closure. If I have understood it right, that form is required to be false because of the existence of procedures like set-car! and set-cdr! which could change equal-looking objects to look different. You cannot change a closure in an analogous way. So what is so convenient about (lambda (x) x) not being eq? to (lambda (x) x) ? - Harald Hanche-Olsen <hanche@imf.unit.no> Division of Mathematical Sciences The Norwegian Institute of Technology N-7034 Trondheim, NORWAY You cannot? What about things like (let ((loc 'unknown)) (lambda (new) (let ((old loc)) (set! loc new) old))) Should two such closures be EQ?/EQV? when they have different environments? Should such a closure not be EQ?/EQV? to itself? Such closures behave very much like structures built out of mutable pairs, and should behave very much like them as far as EQ?/EQV? are concerned. In general, the intent was that LAMBDA is very much like CONS, and every time a LAMBDA expression is evaluated, you get a different object (in the sense of EQ?/EQV?). Note that the formal semantics represents procedure objects as pairs of locations and functions, and models this behavior exactly. This restriction was relaxed somewhat in order to allow compilers to merge procedure objects that it can prove will always operate indistinguishably. In other words, it is spurious to make procedures distinct when only EQ?/EQV? would be able to tell them apart. Since determining function equivalence is an undecidable problem, you cannot expect implementations to do it perfectly, and rather than imposing precise rules that might be improved later, we left the decision to the implementors. Thus (eqv? (lambda (x) x) (lambda (y) y)) may be either true or false. Similarly for (define (make-new-procedure) (lambda (y) y)) (eqv? (make-new-procedure) (make-new-procedure))
alan@lcs.mit.edu (Alan Bawden) (05/12/91)
In article <HANCHE.91May11164038@hufsa.imf.unit.no> hanche@imf.unit.no (Harald Hanche-Olsen) writes: In article <ALAN.91May10232758@august.lcs.mit.edu> alan@lcs.mit.edu (Alan Bawden) writes: I can imagine a programmer thinking it would be convenient if every evaluation of a LAMBDA-expression resulted in a unique (in the sense of EQ?) closure. If I have understood it right, that form is required to be false because of the existence of procedures like set-car! and set-cdr! which could change equal-looking objects to look different. You cannot change a closure in an analogous way. So what is so convenient about (lambda (x) x) not being eq? to (lambda (x) x) ? Well, I confess I'm not certain where this desire comes from really. Note please that nothing I have said so far indicates that I myself subscribe to this desire -- when pressed to the wall I will generally agree that the behavior should be unspecified -- but I know that I have wished otherwise upon occasion, and I have seen others want it as well. It usually seems to happen when using closures for a certain style of object oriented programming. If anyone wants a real example where Scheme programmers wanted more constraints on the EQ-ness of procedures than the standard guarantees, they should look in the 1988 L&FP proceedings for a paper by Rees and Adams. Fairly early on in the paper the authors remark that a sufficiently smart compiler can foil their intentions by recognizing that a certain closure need only be created once -- but they trust that any competent programmer can sufficiently confuse his compiler so as to prevent the problem. [I think this reference is right, I can't seem to lay my hands on a copy of the LFP88 proceedings right now.]