rar@DUCHAMPS.ADS.COM (Bob Riemenschneider) (11/18/88)
Max Hailpern writes:
=> There is another reason, in Scheme, not to use Y: it breaks the fact
=> that you can use procedures as objects. While the R^3R says that a
=> procedure created by a given lambda at a given time will be eqv to
=> itself (and implies eq as well, though on looking I see that isn't in
=> there -- is this a mistake?), the same does not necessarily hold for
=> the various incarnations of a procedure that Y will churn out (or
=> rather, that Y is entitled to churn out: presumably in Rozas's
=> implementation there is indeed only one procedure).
=>
=> Perhaps I'm wrong to mix together such disparate worlds as Y and
=> eqvness of procedures belong to, but I do consider this to be
=> something of an issue. Does anyone else?
Could you provide a specific example? I don't see how Y makes the situation
any worse than lambda. Just as you might decide to write
(let ((p (lambda (n) ...n...)))
===p===p===)
rather than
===(lambda(n) ...n...)===(lambda (n) ...n...)===
because Scheme doesn't guarantee that even syntactically identical lambda
terms will test equivalent---Does anyone know why 'operational equivalence'
for procedures was defined extensionally, making it uncomputable, rather
than intensionally (say, in terms of alpha-convertability)?--, you might
decide to write
(let ((p (Y (lambda (q) ...q...))))
===p===p===)
rather than
===(Y (lambda(q) ...q...))===(Y (lambda (q) ...q...))===
Arguments against Y that apply equally well to lambda don't count!
-- rarmxh@SUMEX-AIM.STANFORD.EDU (Max Hailperin) (11/18/88)
What I had in mind was something like this:
(letrec ((p (lambda () p)))
(eqv? p (p)))
This is will evaluate to #t, according to R^3R.
On the other hand, if we rewrite this as
(let ((p (Y (lambda (p) (lambda () p)))))
(eqv? p (p)))
then it is undefined whether the result will be #t or #f. For a
straightforward impelementation of Y, it will probably be #f, but for an
optimized one, it would be #t.
The problem is not, as you suggested, from two occurences of (Y (lambda
...)), but from the difference between the procedure as the outside world
knows it vs. as it knows itself.
Now that I've explained myself, let me try to answer your question about the
definition of eqvness of procedures. The problem with defining it as
alpha-convertability [plus same environment] is two fold:
1) It is not in keeping with the philosophy as to what a procedure is. In
particular, contrary to some other languages, scheme doesn't allow you to
"reopen" a closure: they are black boxes which can only be applied.
2) It can lead to inefficiencies of two sorts (one obvious, one less so):
a) if the implementation doesn't choose to fold together procedures
which are eqv in your sense, then testing eqvness is slow
b) if the implementation *does* choose to fold together procedures which
it can determine are operationally equivalent but *not* eqv in your
sense, then your eqv test becomes impossible -- so such a compiler
optimization has to be ruled out, at a possible loss in speed.
2b in particular essentially is a way of saying that you want to
define into the language spec a particular level of
compiler-optimization smarts. That's unwise. Moreover, the existing
definition turns out to work well in practice.dorai@titan.rice.edu (Dorai Sitaram) (11/19/88)
Bob Riemenschneider writes: $Max Hailpern writes: $ $=> There is another reason, in Scheme, not to use Y: it breaks the fact $=> that you can use procedures as objects. While the R^3R says that a $=> procedure created by a given lambda at a given time will be eqv to $=> itself (and implies eq as well, though on looking I see that isn't in $=> there -- is this a mistake?), the same does not necessarily hold for $=> the various incarnations of a procedure that Y will churn out (or $=> rather, that Y is entitled to churn out: presumably in Rozas's $=> implementation there is indeed only one procedure). $=> $=> Perhaps I'm wrong to mix together such disparate worlds as Y and $=> eqvness of procedures belong to, but I do consider this to be $=> something of an issue. Does anyone else? $ $Could you provide a specific example? I don't see how Y makes the situation $any worse than lambda. Just as you might decide to write $ $ (let ((p (lambda (n) ...n...))) $ ===p===p===) $ $rather than $ $ ===(lambda(n) ...n...)===(lambda (n) ...n...)=== $ $because Scheme doesn't guarantee that even syntactically identical lambda $terms will test equivalent---Does anyone know why 'operational equivalence' $for procedures was defined extensionally, making it uncomputable, rather $than intensionally (say, in terms of alpha-convertability)?--, you might $decide to write $ $ (let ((p (Y (lambda (q) ...q...)))) $ ===p===p===) $ $rather than $ $ ===(Y (lambda(q) ...q...))===(Y (lambda (q) ...q...))=== $ $Arguments against Y that apply equally well to lambda don't count! $ $ -- rar It is very useful that a procedure be eq to itself [and to nothing else (not even to something alpha-convertible)]. For instance, we can create abstract data objects using lambda and set!. Using the fact that procedures are self-eq, we can determine whether these data objects are self-eq. Lambda and set! give the conventional Scheme way of getting recursive functions with rec/letrec. Recursive procedures created thus a r e self-eq, like any other procedure. Eg, (let ([h (rec h (lambda (dummy) h))]) (eq? h (h 'any))) yields t r u e. However, if _h_ had been defined with _Y_, ie, (let ([h (Y (lambda (h) (lambda (dummy) h)))]) (eq? h (h 'any))) the result is f a l s e, owing of course to the different [read non-eq] procedures created for _h_ at each time it shows up. Self-eqness of ADOs is lost, and though it can retrieved with some amount of hacking [like adding a separate field in the ADO a n d redefining the eq function (see Matthias Felleisen's thesis where he describes a cons data object)] the result is anything but concise or easily extendable. --dorai