[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: scheme@mc.lcs.mit.edu*Subject*: Re: Re^2: Scheme Digest #8, Efficiency of Y*From*: titan!dorai@rice.edu (Dorai Sitaram)*Date*: Fri ,18 Nov 88 15:43:31 EDT*Organization*: Rice University, Houston*References*: <8811172108.AA00499@duchamps.ads.com>*Sender*: scheme-request@mc.lcs.mit.edu

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

**References**:**Re^2: Scheme Digest #8, Efficiency of Y***From:*zodiac!DUCHAMPS.ADS.COM!rar@ames.arpa (Bob Riemenschneider)

- Prev by Date:
**Re: Scheme Digest #8, Efficiency of Y** - Next by Date:
**Re: Scheme Digest #8, Efficiency of Y** - Previous by thread:
**Re^2: Scheme Digest #8, Efficiency of Y** - Next by thread:
**Re: Re^2: Scheme Digest #8, Efficiency of Y** - Index(es):