Better yet, I think that I can explain it.
This is all much simpler if we allow ourselves functions of 2 variables. It is fairly easy to build a recursive function of one variable starting with functions of 2 variables:
\nF = proc { |recurse, n|\n if n == 0 then\n 1\n else\n n * recurse.call(recurse, n-1)\n end\n}\n\nY = proc { |builder, n|\n builder.call(builder, n)\n}\n\np Y.call(F, 5) # prints 120\nThe idea being that Y calls F with F as an argument, and that sets up the recursion. You can even write that directly without the temporary variables Y and F just by expanding out Y and F in the expression Y.call(F,5):
\np proc {|builder, n|\n builder.call(builder, n)\n }.call(\n proc { |recurse, n|\n if n == 0 then\n 1\n else\n n * recurse.call(recurse, n-1)\n end\n },\n 5\n )\nBut a brilliant guy named Haskell Curry has a clever trick, you
don't need functions of 2 variables if you have functions that return functions. The translation is perfectly mechanical. The idea is that something like:
\nX = proc {|foo, bar|\n ...\n}\nX.call(this, that)\ncan always be written as
\nX = proc {|foo| proc{ |bar|\n ...\n}}\nX.call(this).call(that)\nwhere ... remains unchanged. So edit the declaration and the calls to functions of 2 variables, and we only need functions of one variable.
Let's apply this mechanical translation to F above. We had:
\nF = proc { |recurse, n|\n if n == 0 then\n 1\n else\n n * recurse.call(recurse, n-1)\n end\n}\nSince we now want both recurse and F to be functions of 1 variable, we get the following:
\nF = proc { |recurse| proc { |n|\n if n == 0 then\n 1\n else\n n * recurse.call(recurse).call(n-1)\n end\n}}\nAnd likewise Y becomes:
\nY = proc { |builder| proc { |n|\n builder.call(builder).call(n)\n}}\nand our call becomes:
\np Y.call(F).call(5)\n
Or the complex version with no intermediate variables becomes:
\np proc {|builder| proc { |n|\n builder.call(builder).call(n)\n }}.call(\n proc { |recurse| proc { |n|\n if n == 0 then\n 1\n else\n n * recurse.call(recurse).call(n-1)\n end\n }}).call(\n 5\n )\nWhich is, modulo formatting,
exactly what Jim wrote.
That runs, but following the execution should make your head spin... :-)
Cheers,
Ben
OT: Inner/outer classes.
- (pwhysall)
- (30)
- Feb. 14, 2005, 05:27:22 AM EST
