Practical use of so-called Y operator -
More precisely called "an applicative order combinator function"
Let me apologize ahead of time for wasting everyone's time with such a trivial subject, but I can't find any forum named "Lisp for Hobbyists" - - any suggestions along these lines would be appreciated.
I am an off-and-on Lisp hobbyist, with a spotty and incomplete knowledge of Lisp. It doesn't help that I am getting up in age, <71> so my memory is not what it was in my earlier years.
I was browsing through my Lisp notes and ran across a version of the Y operator written in Scheme, so I promptly converted it to Common Lisp.
To make a long story longer, here is my code, with a question at the end of this post.
(setf y
#'(lambda (m)
((lambda (u)
(funcall m #'(lambda (&rest arg)
(apply (funcall u u) arg) )))
#'(lambda (u)
(funcall m #'(lambda (&rest arg)
(apply (funcall u u) arg) ))) )))
; Here is Y applied to a lambda function that takes two arguments,
; two lists of equal length and 'shuffles' them together.
(funcall
(funcall y
#'(lambda (foo) ;lambda version of shuffle function
#'(lambda (list1 list2)
(cond
((null list1) nil)
(t (cons (car list1)
(cons (car list2)
(funcall foo (cdr list1)
(cdr list2))) ))) )))
'(a c e) '(b d f) ) ;arguments for shuffle function
;Returns list (A B C D E F)
;*********************************************************
; Same as above, except the lambda form of Y is used in order to
; get rid of the global variable Y.
(funcall
(funcall
#'(lambda (m) ;lambda version of Y
((lambda (u)
(funcall m #'(lambda (&rest arg)
(apply (funcall u u) arg) )))
#'(lambda (u)
(funcall m #'(lambda (&rest arg)
(apply (funcall u u) arg) ))) ))
#'(lambda (foo) ;shuffle function
#'(lambda (list1 list2)
(cond
((null list1) nil)
(t (cons (car list1)
(cons (car list2)
(funcall foo (cdr list1)
(cdr list2))) ))) )))
'(a c e) '(b d f) ) ;arguments for shuffle function
;Returns list (A B C D E F)
Now my question is:
Are there any uses for Y other than the ability to avoid the use of "defun" for creating recursive functions, when such use of defun is not desirable in a program.
Be gentle, remember my spotty knowledge of Lisp.
Gerald
Gerald Smith <··········@CompuServe.COM> writes:
> Now my question is:
>
> Are there any uses for Y other than the ability to avoid the use
> of "defun" for creating recursive functions, when such use of
> defun is not desirable in a program?
Not that I am aware of. I've only seen the Y combinator used in
mathematical analysis of programs.
Gerald Smith wrote:
> Practical use of so-called Y operator -
>
> I was browsing through my Lisp notes and ran across a version of the Y operator
> written in Scheme, so I promptly converted it to Common Lisp.
Great job! [I am a Schemer and stopped by accidentally. I am also primarily a PL guy.]
There are two things about the Y combinator that are of interest:
1. it illustrates the idea of self-application of functions
2. it can be used to define recursive functions directly
There are on occasion other things that have the flavor of self-application in the real
world. Use structures/objects to model a graph and you have some form of self
reference. Use engines in Scheme, and an engine returns an engine when it fails to
complete the computation with the given fuel.
I have seen several cute uses over the years of Y-based recursive function definitions.
For example, you can use a Y-based definition to add debugger/tracer code w/o changing
the definition of the function proper. You can use a Y-based definition to memoize and to
turn a purely recursive program into a dynamic-programming algorithm.
Of course, in Scheme or CL you can do the above with macros, too. The only difference is
that macros assume that you have access to source code, and a redefinition based on Y
doesn't. You don't need to recompile these things -- you just play games with first-class
functions.
So, yes, the Y combinator illustrates a few things that occur in reality and is useful as a
device on occasion. But, honestly, it's mostly a theoretical construction that permits foundational
guys to reduce a language to a very small kernel and to study the properties of this kernel w/o
giving up the claim that it relates to real programming languages.
-- Matthias
Matthias,
Thanks for clarifying the so-called "Y operator".
You got me interested in various side issues related to the fascinating Y-operator, so I opened
my Scheme reference book to learn more.
The book -
Title: Essentials of Programming Languages
Authors: Daniel P. Friedman, Mitchell Wand, Christopher T. Haynes
ISBN: 0-262-06145-7
Various incarnations of the Y operator are described. Even Y-op mutual-recursion techniques are
touched upon. <pg-117> - - A teaser statement on the same page, "All manner of data structures
can be represented as lambda expressions using appropriate tricks"
(inferred meaning of that quote, they can also be represented as versions of the Y-operator)
Gadd, hope I don't get too interested in the Y-op, else I might have to buy some books
on the "Lambda Calculus"<g>
I don't wanna be an egghead, just a trivial hobbyist with no desire to make money - - although Lisp
_does_ presently rank ahead of my other retirement hobbies, like motorcycling, archery, etc.
Forgot how good that "essentials" Scheme book is, for learning such things as applicative-order,
normal-order, thunks, call-by-need, call-by-name, continuation-passing-style, etc., etc., etc.
I generally learn my "hobby" Lisp from Scheme books, then transfer everything over to Common Lisp.
Of course, some things fight me mightily when I attempt the transfer, like Scheme continuations
for example. I use Graham's macros to implement Scheme continuations, but that is awkward
and non-intuitive, not to mention some features of Scheme continuations can't
be implemented in CL.
Heck, even CL has lotsa stuff it does better than Scheme, <macros for one> - so it gives me fits
when I try to transfer stuff the _other_ way, from CL to Scheme.
Ideally, instant transfer from Scheme to CL - - or CL to Scheme would be nice, that way the
strengths of both these fine languages might be brought to bear on a programming project
that needed features from both languages.
Heck, why stop there ;-) Arrange things so *any* useful language could be used,
depending on the challenge at hand.
I vaguely recall that "blackboard systems" were supposed to do this trick,
but I have not heard much about them lately.
Gerald
Gerald Smith wrote:
> Matthias,
>
> Thanks for clarifying the so-called "Y operator".
>
> You got me interested in various side issues related to the fascinating Y-operator, so I opened
> my Scheme reference book to learn more.
>
> The book -
>
> Title: Essentials of Programming Languages
> Authors: Daniel P. Friedman, Mitchell Wand, Christopher T. Haynes
> ISBN: 0-262-06145-7
>
> Various incarnations of the Y operator are described. Even Y-op mutual-recursion techniques are
> touched upon. <pg-117> - - A teaser statement on the same page, "All manner of data structures
> can be represented as lambda expressions using appropriate tricks"
>
You may wish to read The Little Schemer (nee The Little LISPer) by Friedman and myself, especially
the teaser chapter that we were allowed to place on our web page:
http://www.cs.rice.edu/~matthias/TLS/
It includes a discussion of the Y combinator. There is some other stuff on how to use lambda to do
everything ... in a playful manner, no egg-head lambda calculus book needed (CS people have abused
the lambda calculus anyway, and it is difficult to find a good book on CS and lambda.)
> Of course, some things fight me mightily when I attempt the transfer, like Scheme continuations
> for example. I use Graham's macros to implement Scheme continuations, but that is awkward
> and non-intuitive, not to mention some features of Scheme continuations can't
> be implemented in CL.
> Heck, even CL has lotsa stuff it does better than Scheme, <macros for one> - so it gives me fits
> when I try to transfer stuff the _other_ way, from CL to Scheme.
Perhaps I am missing something but I believe that the macro systems of Scheme are superior to CLs.
For one thing, they pay attention to the lexical scope of the language and ensure hygiene (though I
admit that there are serious flaws in the specified version that prevent it from scaling to
components).
(Graham who?)
Yes, we are working on a system where people express their thoughts in their favorite language and
exchange data at a fine-grained level -- no COM objects allowed here, no unsafe languages either.
-- Matthias
Matthias Felleisen <········@rice.edu> writes:
> You may wish to read The Little Schemer (nee The Little LISPer) by Friedman and myself, especially
> the teaser chapter that we were allowed to place on our web page:
>
> http://www.cs.rice.edu/~matthias/TLS/
>
> It includes a discussion of the Y combinator.
Isn't that in the *seasoned* schemer?
I struggled for a few evenings with Y, but can't claim to have
understood it :-(
Regards
Jon K�re
This doesn't have anything to do with the Y-Operator, but one subject
leads to another.<g>
Regarding macros in CL -
> Graham who?
Paul Graham, an independent consultant specializing in Lisp.
He received his PhD in CS from Harvard. His book is the definately
best treatment of CL macros that I have read.
Title: On Lisp
Subtitle: Advanced Techniques for Common Lisp
Publisher: Prentice Hall (1994)
ISBN: 0-13-030552-9
I will grant that CL macros are not what Schemers call "hygienic",
because there is no built-in provision to prevent name conficts,
variable capture, etc. Lets face it, one of the reasons people use
Lisp is because of the automatic features, so I agree that hygienic
macros should be part of the language spec' itself, as in Scheme.
Graham claims that CL macros could have *all* the functionality
of Scheme macros, <except the "hygienic" aspect> - - if the CL source code
were first converted to "Continuation-Passing-Style". He outlines how to do
that at the end of his chapter on Scheme continuations. I have not checked
out that statement of his, but plan to do so in the future.
One caution about Graham's book, I found some of his "example" code in the
book buggy, in the chapter concerned with simulating Scheme continuations
in Common Lisp.
I would use Scheme much more if I could find a recent well maintained
version. Most of the available versions of the Scheme language seem to
have been written around 1994. It seems to me that back then they were
discussing among themselves just how to go about implementing macros.
As I recall one camp favored a system called "extended syntax" or something
like that. Have they finalized macros in Scheme, and is that reflected in
the available Scheme language versions?
Is there a modern commercial version of Scheme available for purchase, one
that implements Scheme macros "properly" according to current Scheme thinking.?
I have read your book "The Little Lisper" and "The Little Schemer", also read
"The Seasoned Schemer". Very good books, all of them
Gerald
On 5 Jun 2000 14:11:29 GMT, Gerald Smith <··········@CompuServe.COM> wrote:
>
>I would use Scheme much more if I could find a recent well maintained
>version. Most of the available versions of the Scheme language seem to
>have been written around 1994. It seems to me that back then they were
>discussing among themselves just how to go about implementing macros.
>As I recall one camp favored a system called "extended syntax" or something
>like that. Have they finalized macros in Scheme, and is that reflected in
>the available Scheme language versions?
>
>Is there a modern commercial version of Scheme available for purchase, one
>that implements Scheme macros "properly" according to current Scheme thinking.?
Have a look at www.schemers.org and at
www.cs.rice.edu/CS/PLT/packages/drscheme/
Marc
--
------------------------------------------------------------------------------
email: marc dot hoffmann at users dot whh dot wau dot nl
------------------------------------------------------------------------------
Gerald Smith wrote:Title: On Lisp
> Subtitle: Advanced Techniques for Common Lisp
> Publisher: Prentice Hall (1994)
> ISBN: 0-13-030552-9
>
>
Thanks.
> Graham claims that CL macros could have *all* the functionality
> of Scheme macros, <except the "hygienic" aspect> - - if the CL source code
> were first converted to "Continuation-Passing-Style". He outlines how to do
> that at the end of his chapter on Scheme continuations. I have not checked
> out that statement of his, but plan to do so in the future.
Hmph. In that case, I'd say Turing machines can also express Scheme macros.
And C, too. Some ten years ago, I wrote a first article on the expressiveness of
PLs and how to compare them. Others have followed. I collaborated with others
on that. Converting the entire program first does NOT prove a thing. Sorry.
> I would use Scheme much more if I could find a recent well maintained
> version. Most of the available versions of the Scheme language seem to
> have been written around 1994. It seems to me that back then they were
> discussing among themselves just how to go about implementing macros.
> As I recall one camp favored a system called "extended syntax" or something
> like that. Have they finalized macros in Scheme, and is that reflected in
> the available Scheme language versions?
>
> Is there a modern commercial version of Scheme available for purchase, one
> that implements Scheme macros "properly" according to current Scheme thinking.?
You may wish to check out DrScheme and the PLT Scheme suite, available from my
site. No, it doesn't support all of the macro stuff but it's a PE that does alot
for people.
especially portable graphics, scripting etcetc.
You may also wish to check out Petite Chez from Indiana's Web site. (Kent Dybvig
sells Chez, but Petite Chez may do all you want).
-- Matthias
>>>>> "Gerald" == Gerald Smith <··········@CompuServe.COM> writes:
Gerald> I will grant that CL macros are not what Schemers call
Gerald> "hygienic", because there is no built-in provision to prevent
Gerald> name conficts, variable capture, etc.
But this is not just a bug, it can also be a feature. Some of the
examples in Grahams book exploits namecapture to do tricky things.
Gerald> ... I agree that hygienic macros should be part of the
Gerald> language spec' itself, as in Scheme.
Hygenic macros can be built on top of a non-hygenic macro
system. There are papers on this from back when the scheme community
found the way to implement it. I think one of the originators was
named something like Eugene Kohlbecker.
I even think that SLIB (a rather big scheme library, maintained by
Aubrey Jaffer) contain an implementation of hygenic macros on top of a
defmacro like construct.
Gerald> Graham claims that CL macros could have *all* the
Gerald> functionality of Scheme macros, <except the "hygienic" aspect>
Gerald> - - if the CL source code were first converted to
Gerald> "Continuation-Passing-Style".
I believe this talking of CPS was more in the context of implementing
call-with-current-continuation, which is much harder to do without
lowlevel support. Graham provides one solution, with several
restrictions, based on a handfull of macros, and then comments that a
general solution could be implemented using CPS conversion.
CPS conversion is not easy, but then again code conversions
(ie. meta-programming) are one of the things that LISP *is* good for.
Gerald> I would use Scheme much more if I could find a recent well
Gerald> maintained version. Most of the available versions of the
Gerald> Scheme language seem to have been written around 1994.
There are a number of systems still under maintenance, though a number
of these see a rather low level of activity, judging from the mailing
lists.
One system which is bustling with activity, is Guile Scheme, the
official choice of extension language of the GNU project. They have
just issued a code freeze in order to prepare a new release (1.4).
There should be links from www.gnu.org.
Gerald> It seems to me that back then they were discussing among
Gerald> themselves just how to go about implementing macros.
It is a good indication of the scheme community works, that R4RS (the
scheme standard (v4), sort of) came out without any serious mentioning
of macros, simply because no good solution to the namecapture problem
was known at the time. The committee would rather throw away macros
than put in something with known defiencies.
Given what macros means to LISP programming, this naturally lead to
each and every scheme implementation rolling their own macro systems,
differing in subtle ways.
Gerald> As I recall one camp favored a system called "extended syntax"
Gerald> or something like that. Have they finalized macros in Scheme,
Gerald> and is that reflected in the available Scheme language
Gerald> versions?
Yep. R5RS has macros, but not all schemes have yet made the full move
to R5RS compability. However, macros would probably typically be in
order (or one could check out the aforementioned SLIB).
---------------------------+--------------------------------------------------
Christian Lynbech | Ericsson Telebit, Fabrikvej 11, DK-8260 Viby J
Fax: +45 8675 6881 | email: ···@ericssontelebit.com
Phone: +45 8675 6828 | web: www.ericssontelebit.com
---------------------------+--------------------------------------------------
Hit the philistines three times over the head with the Elisp reference manual.
- ·······@hal.com (Michael A. Petonic)
My comments from a prior post:
>> Graham claims that CL macros could have *all* the
>> functionality of Scheme macros, <except the "hygienic" aspect>
>> if the CL source code were first converted to
>> "Continuation-Passing-Style".
>>>>>Christian Lynbech <·······@ericssontelebit.com> responded::
> I believe this talking of CPS was more in the context of implementing
> call-with-current-continuation, which is much harder to do without
> lowlevel support. Graham provides one solution, with several
> restrictions, based on a handfull of macros, and then comments that a
> general solution could be implemented using CPS conversion.
Whoops! - - you are correct, Graham was referring to implementing CC,
not Scheme macros. Sorry for that mistake.
Christian Lynbech writes:
> R5RS has macros, but not all schemes have yet made the full move
> to R5RS compability.
Are there some Scheme implementations that have macros implemented
in accordance with R5RS? I will be running the Scheme on a Mac.
Gerald -
Gerald Smith <··········@CompuServe.COM>