The Y-function for newLISP

[Lutz]

Here is a development of the Y function for newLISP:

http://www.newlisp.org/index.cgi?Y_Function

it follows closely the method shown by Richard P. Gabriel in "The Why of Y"

http://www.dreamsongs.com/NewFiles/WhyOfY.pdf

[xytroxon]

LOL!

Lutz, I guess we both had "Y" on the mind...

Mike Vanier recently wrote this article I was trying to absorb this weekend, which has a good explanation of this clever scheme (in Scheme of course):

The Y Combinator (Slight Return) or:
How to Succeed at Recursion Without Really Recursing
http://mvanier.livejournal.com/2897.html

From the intro:

Why Y?

Before I get into the details of what Y actually is, I'd like to address the question of why you, as a programmer, should bother to learn about it. To be honest, there aren't a lot of good nuts-and-bolts practical reasons for learning about Y. Even though it does have a few practical applications, for the most part it's mainly of interest to computer language theorists. Nevertheless, I do think it's worth your while to know something about Y for the following reasons:

1. It's one of the most beautiful ideas in all of programming. If you have any sense of programming aesthetics, you're sure to be delighted by Y.

2. It shows in a very stark way how amazingly powerful the simple ideas of functional programming are.

In 1959, the British scientist C. P. Snow gave a famous lecture called The Two Cultures where he bemoaned the fact that many intelligent and well-educated people of the time had almost no knowledge of science. He used knowledge of the Second Law of Thermodynamics as a kind of dividing line between those who were scientifically literate and those who weren't. I think we can similarly use knowledge of the Y combinator as a dividing line between programmers who are "functionally literate" (i.e. have a reasonably deep knowledge of functional programming) and those who aren't. There are other topics that could serve just as well as Y (notably monads), but Y will do nicely. So if you aspire to have the True Lambda-Nature, read on.

By the way, Paul Graham (the Lisp hacker, Lisp book author, essayist, and now venture capitalist) apparently thinks so highly of Y that he named his startup incubator company Y Combinator. Paul got rich from his knowledge of ideas like these; maybe someone else will too. Maybe even you.

-- xytroxon

[Lutz]

The version of Y from Mike Vanier's blog is added to the document at the bottom. Functionally it is identical to Richard P. Gabriel's version, but looks much better with the self-referential (g g) expression written out in lambdas.

Also linked from: http://www.newlisp.org/index.cgi?Tips_and_Tricks

[Cyril]

Just for comparison: python code, from my blog near the end of 2007.

Code: Select all

Y = lambda f: (lambda g: f (lambda h: g(g)(h))) \
              (lambda g: f (lambda h: g(g)(h)))

fact = lambda f: lambda n: 1 if n == 0 else n * f(n-1)

print Y(fact)(100)

[xytroxon]

Just for fun, Cyril, have you compared Python and newLISP speeds on a large factorial? Or with one of the Schemes?

[Cyril]

Just for fun, Cyril, have you compared Python and newLISP speeds on a large factorial? Or with one of the Schemes?

Alas newLISP has no built-in bignums, ony 32-bit integers, so large factorials are not so trivial in it. And among languages that has bignums, CLISP rumored to be one of the most efficient (but I have not tested this myself).

[Lutz]

Integers in all newLISP versions are 64-bit. For higher precision use the "GNU MP Bignum Library interface", see here:

http://www.newlisp.org/code/modules/gmp.lsp.html

Code: Select all

> (load (append (env "NEWLISPDIR") "/modules/gmp.lsp"))

> (GMP:fac "300")
"306057512216440636035370461297268629388588804173576999416776741259476533176716867465515291422477573349939147888701726368864263907759003154226842927906974559841225476930271954604008012215776252176854255965356903506788725264321896264299365204576448830388909753943489625436053225980776521270822437639449120128678675368305712293681943649956460498166450227716500185176546469340112226034729724066333258583506870150169794168850353752137554910289126407157154830282284937952636580145235233156936482233436799254594095276820608062232812387383880817049600000000000000000000000000000000000000000000000000000000000000000000000000"
> 
> (time (GMP:fac "300") 1000)
62
> 

[xytroxon]

615 digits!

Here's a factorial calculator (Allowed range: 0 to 71,352)
http://nitrogen.no-ip.org/factorialcalc.php

Lutz's number looks correct, of course :)

As always, with newLISP's ease of experimentation, I have "discovered" something interesting and unexpected...

By inspection of the digit strings for factorial numbers >= 2! the first non-zero right hand digit is always even. 2, 4, 6, or 8.

n n!
0 1
1 1
--------------
2 2 -> 2
3 6 -> 6
4 24 -> 4
5 120 -> 2
6 720 -> 2
7 5,040 -> 4
8 40,320 -> 2
9 362,880 -> 8
10 3,628,800 -> 8
11 39,916,800 -> 8
12 479,001,600 -> 6
13 6,227,020,800 -> 8
14 87,178,291,200 -> 2
15 1,307,674,368,000 -> 8

300 -> 6

Again for fun (and those with big iron cpus), is this always true? And does it approach an even digit distribution of 2, 4, 6 and 8? Or is one digit more or less likely?

Early returns show digits 2-(5) and 8-(5) more than twice as likely as digits 4-(2) and 6-(2)...

--------

Here's the Wikipedia Factorial page:
http://en.wikipedia.org/wiki/Factorial

-- xytroxon