Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

[REBOL] Re: Functional programming in REBOL

From: larry:ecotope at: 12-Aug-2001 17:08

Hi Ladislav, OK, I will stop teasing. The mystery function ??? is actually a very famous function with the rather imposing name "the applicative-order Y-combinator". Its derivation was a culminating point in the development of the lambda calculus (the mathematical theory underlyling functional programming). It is also known as the Paradoxical Combinator and the *dreaded* Y-combinator. I must say that it is a truly mind-stretching function, even when you have done a derivation of it, it still seems like black magic. There have been recent discussions of the implementation of Y in Perl, Scheme, Ruby, Java, and the lambda calculus on the web: http://lambda.weblogs.com/discuss/msgReader$838 And now we also have a version in REBOL.:-) Although paradoxical, it is actually a useful function (especially in the lambda calculus, because it is what allows recursion). The applicative-order Y-combinator in REBOL: Y: func [g][ do func [h][h :h] cfunc [f][g func [x][do f :f x]] ] I found that it requires only one use of cfunc (the function that makes functions that remember their args). My simple cfunc is included below for those who wish to try this version. Ladislav's e-func will work just as well. Alternatively, we can replace the single use of cfunc with an equivalent USE block, thus making Y self-contained: Y: func [g][ do func [h][h :h] func [f][use [h][h: :f g func [x][do h :h x]]] ] We can define the "self-application" U-combinator as: U: func [f][f :f] Then the second version of Y can be written as: Y: func [g][ U func [f][use [h][h: :f g func [x][do h :h x]]] ] The Y-combinator is a very special function because it generates the fixed-point of its function argument. It satisifes the following equation: (g (Y g)) = (Y g) (g (g (Y g))) = (Y g) and so on. We will test this in a bit. The Why of Y We know that we can use a function without giving it a name, e.g.
>> do func [x][x + 12] 5
== 17 But consider a recursive function like the recursive version of factorial: fact: func [n][ either zero? n [1][n * fact n - 1] ] Here it seems, the name fact for the function is required in order to obtain the recursion. But one can avoid naming the function and still get the recursion. In a nutshell, this is what Y does. I will illustrate it's use on the fact function. Step 1) We want to use functional abstraction to remove the reference to fact in the global context from the body. We can do this with a function wrapper made like this: fact*: func [fact][ func [n][ either zero? n [1][n * fact n - 1] ] ] So the function to be applied in the body for the next recursion is passed in as an argument. Notice the code in the body of fact has not been changed. Making the wrapper just means creating a func with an arg of the same name as the name of the function used in the body for the recursion step. Notice that fact* is not recursive. This is the kind of function which Y needs for its argument. Y will instantly turn this kind of function into one that recurs as often as needed. The inner func must have a termination condition or the application of Y will create a function that loops forever. Step 2) Now we can define the recursive factorial we want as:
>>fact: Y :fact* >> fact 12
== 479001600
>> source fact
fact: func [n][ either zero? n [1] [n * fact n - 1] ] This is a bit misleading because the two occurences of fact are unrelated, we could have named the outer function anything we wanted. But we still seem to be using a variable name for one of our functions. This is easily avoided by substituting the definition of fact* as the arg for Y: fact: Y func [fact][ func [n][either zero? n [1][n * fact n - 1]] ] Look Ma! No Names. This is the final product, a recursive version of factorial which does not require any external name resolution for the recursion function in the inner body. It can be shown that Y is a universal recurser (i.e., it can be used to recursively reduce any wrapped recursive function). Now we can test the fixed-point property with respect to the fact* function.
>> do Y :fact* 5
== 120
>> do fact* Y :fact* 5
== 120
>> do fact* fact* Y :fact* 5
== 120
>>
So (Y fact*) is indeed a fixed-point of fact*. The Y-combinator has been an object of fascination in computer science since Church invented it in the 30's. It has also apparently struck fear in the hearts of many students. My own reaction is: Wow! Y is possibly the most clever and devious function I have seen. It's fun stretching your mind and Y is guaranteed to do that. There are some good references on the web with derivations of Y, mostly in the Scheme language: http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html http://www.mactech.com/articles/mactech/Vol.08/08.01/DazeY/ http://www.mactech.com/articles/mactech/Vol.07/07.05/LambdaCalculus/index.ht ml http://www.mit.edu/afs/athena/project/adedev/elk/tst/Y There is also a good derivation in Chapter 9 of "The Little Schemer" by Friedman and Felleisen. This is repeated with extensive annotation by Jim Weirich in the Scheme link of the URL at the top of this note. His final comment: ;; I've walked through the entire thing, and can say I believe I ;; understand each step, but the wonder of the entire process leaves ;; my mind boggled. Ladislav, could you please check all the functions I give above, and see if I went too far in eliminating the use of cfunc. Let me know if you see a better way to present the Y function. Try applying it to your favorite recursive function. Enjoy -Larry PS I am looking forward to your further comments on Y, especially with regard to your comments below. BTW There is another way to produce recursive anonymous functions using just the U combinator combined with a small change in the original recursive function body. ---------code for cfunc -------------------- cfunc: func [spec body /local args][ args: copy [] repeat el spec [if word? :el [append args to-get-word :el]] func spec compose/deep [ do append reduce [func [(spec)][(body)]][(args)] ] ]