The Y-function for newLISP

[Lutz]

Here is a development of the Y function for newLISP:



http://www.newlisp.org/index.cgi?Y_Function">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">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">//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">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 Expand

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">http://www.newlisp.org/code/modules/gmp.lsp.html

Code Select Expand

> (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">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">http://en.wikipedia.org/wiki/Factorial



-- xytroxon