Paradoxical Combinator

Here's an excellent post describing this and other topics:

http://groups.google.com/groups?selm=ln1wds3v.fsf_-_%40lambda.unlambda.com&output=gplain

 From: james@fredbox.com (JamesCrippen?)
 Subject: Re: The Lambda Nature
 Date: 2000/04/29
 Message-ID: <ln1wds3v.fsf_-_@lambda.unlambda.com>
 Sender: root@lambda.unlambda.com
 References: <66t696q5.fsf@lambda.unlambda.com> <HmAFOfTAOnak6jtktaUBNrCWV0fD@4ax.com> <ya61799l.fsf_-_@lambda.unlambda.com> <qij3do88cbr.fsf_-_@ernie.ai.mit.edu> <Ys5O4.1295$F.37918@news4.giganews.com> <ln1yfskr.fsf@lambda.unlambda.com> <390A5F1B.4B7627CD@mastnet.net> <slrn8gkohv.8c5.cbbrowne@knuth.brownes.org> <390A6B11.2C543E14@mastnet.net> <8ee7ub$asc$1@news.huji.ac.il> <390AF3EA.3B98DCE1@mastnet.net>
 Organization: Lambda Unlimited
 Newsgroups: comp.lang.scheme
 X-Complaints-To: newsabuse@supernews.com

JohnClonts <jclonts@mastnet.net> writes:

> Ok, I guess I didn't know what a koan *was*.

A koan is a riddle used in ZenBuddhism (and other related forms) to pose a question or problem to the student whose answer transcends ordinary human logical thought. The student is expected to find some answer or reply to the koan in a certain manner that only his master can recognize. Hopefully after a few of these the student learns to think extrarationally, and potentially experiences satori (the blinding flash of enlightenment many people describe) and, with time, total enlightenment. The typical koan is a Japanese haiku or similar poetical verse; short, strong, and endlessly open to interpretation and examination.

AI koans, while somewhat tongue-in-cheek and self-mocking, are in the same vein. They typically describe events in the life of masters in AI and related fields, similarly to how Zen koans describe events in the life of revered Zen masters. They describe some sort of belief or idea held by the AI community, and are frequently extralogical in the fashion of traditional ZenKoan?s.

You may wish to see the related entry in the Jargon file

http://catb.org/~esr/jargon/html/koans.html

The other three entries listed should be helpful as well.

> So Thank you, at least now I know that my question is silly.

It isn't really silly. You just touched on a subject that defies typical rational analysis. Though perhaps this could have been explained a bit better, as newcomers are easily confused by such blatantly irrational things popping up in the context of solidly rational pursuits such as programming.

> So I must use some other approach to even approach the question.

Spending time immersed in the SchemeLanguage (and related LispLanguage-ish and FunctionalProgrammingLanguages) and in historical documents of the AI lab cultures will invariably assist you in understanding not only the superficial culture of the hackish crowd, its lore, and history, but also will aid you in understanding the underlying ideas and motives that produced such languages as Scheme. Probably one of the simpler windows into the culture is a dated but still relevant paper by RichardGabriel,

http://www.ai.mit.edu/docs/articles//good-news/good-news.html

This is a somewhat non-technical, short paper describing why the Lisp community as of ten years ago failed to succeed as well as it could have in the face of microcomputers, Unix, and poorly educated C hackers. It's well worth the read, and RPG not only defends his thesis well but brings up many sensitive topics rarely broached amongst the Lisp hacker community.

 > Does my lack of understanding of the Lambda Nature the reason that my
 > mind reels at this, that I saw on news:comp.object the other day:
 >
 > (define <
 >     (y
 >         (lambda (lesser)
 >             (lambda (x)
 >                 (lambda (y)
 >                     (((if-then-else (is-zero x))
 >                       (lambda ()
 >                           (((if-then-else (is-zero y))
 >                             (lambda () false))
 >                                 (lambda () true))))
 >                      (lambda ()
 >                          (((if-then-else (is-zero y))
 >                            (lambda () false))
 >                                (lambda () ((lesser (predecessor x))
 >                                            (predecessor y)))))))))))
 >
 > I cannot even figure out how to *read* it, i.e. what words or images to
 > formulate as I come across these nested lambda's.  I have been studying
 > through SICP, and I don't see this ["idiom?" | "style?" ] used.  Is this
 > a "lispy" style that has some different typical way of expressing in
 > scheme?

What it entails most predominantly is the use of the Y combinator, inherited (as is the entire language design) from AlonzoChurch's LambdaCalculus, a logical formalism first presented in the 1930s as a system for exploring the foundations of mathematics. At this task it failed due to some mathematical reasons that would be somewhat unreasonable to explain to someone not familiar with the calculus already. However it succeeded quite astonishingly in later years as developments in computing proceeded. AlanTuring proved that a function which was definable in the LambdaCalculus was equivalent to an algorithm computable by a TuringMachine, thus showing that the lambda calculus could be used as a foundation for the study of computability. Later the lambda calculi (there are actually numerous variations on the same theme) were used to develop a language for denotational semantics, the study of how to assign and prove the meaning (semantics) of programming languages. Today it is still used for all of these pursuits as well as for explorations in compilation, functional languages, and much more. The lambda calculi and related theories merit investigation entirely on their own as well, and learning to understand the lambda calculi is not only rewarding, but because of its relative simplicity (as compared to other mathematical subjects) is remarkably simple to the person with an affinity for logical thought. I myself have taught the rudiments to a few people with little background in mathematics or computer science, and all have found it entertaining and fascinating.

Enough propaganda. The Y combinator is a prime example of functions called `FixedPointCombinators'. A fixed point is the point in a function's domain which is equal to the corresponding point in its range. That is, suppose a function f which maps from a set A to a set B, that is `f: A -> B' . A fixed point of f is an x in A that equals f(x). So you get input which is exactly the same as the output. Y is particularly strange -- it is termed the `ParadoxicalCombinator' because *any* expression which you apply Y to will result in a fixed point for that expression.

This function is a description of the "lesser than" predicate using the Y combinator and ChurchNumerals.

It's much more sensible once you understand the lambda calculus. If you aren't interested in doing that then don't worry too much about it. To become a truly wizardly Scheme programmer you will likely need to study the lambda calculus intensively at some point. It will teach you much more about functional programming than any programming language can.

 > Ok, there are probably several levels of "over-my-head-edness" that
 > I'm in here, but maybe someone will throw this blind pig an
 > enlightening acorn anyway.

As I said, you hit not one but several complicated topics. I hope I've at least clarified some things for you, but it's more likely that you're even more confused than you were. All I can say is, don't despair. I feel the same way and I've been nosing around in these subjects for four or five years now.

To the group: Perhaps I've not explained things as best as I can, or possibly gotten a few things wrong. I apologize in advance. My learning is far from complete, and indeed I hope shall never reach completion.

-- james