[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Re^2: Scheme Digest #8, Efficiency of Y
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...)))
$ ===(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...))))
$ ===(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