You're viewing a comment by bluestorm and its responses.

bluestorm Permalink
February 19, 2010, 18:11

tommy > there is a quirk in the Erlang syntax, wich makes that you can't have a local declaration of a recursive function (inside an expression) : actually, there is no syntax for named function declaration inside expressions, so you have to use anonymous functions. Hence, you can't declare a local recursive function without such a fixpoint operator. This is actually a bad idea, as you end up reimplementing a part of the runtime system in a probably slow and certainly cryptic way, but that was just for the example.

Peter > this combinator is just one among the different fixpoint combinators available. There is for example the Turing Fixpoint combinator, wich is also derivable. Do you know where in your derivation you made a decision that lead you to this combinator instead of another ? I have a gut feeling that the derivation is not "canonical" and that one could probably use a slightly different succession of software-engineering-and-common-sense steps that would naturally lead to another combinator.

Also, I'm not sure I agree with your presentation of the Y-combinator. You describe it as something about recursion and anonymous functions. I believe it is much more general than that : fixpoint combinators allow you to control recursion. It is all about parametrizing the function you call over at your recursion sites, instead of hardcoding recursion using the language syntax (or lack of). From a software engineering point of view, you could say that it decouples two aspects of your function : the implementation (with domain-specific knowledge and all) and the "looping" / "tying the knot" process, wich is deferred to the fixpoint combinator.

You can do quite interesting (but somewhat hacky) things once you've decoupled those two separate concerns. Matt mentioned memoization (automagic memoization of inner recursive calls, wich have been exposed by the decoupling process), there are quite a few folk examples, see for example the following article That About Wraps it Up.

It's a funny hack, for example, to write in your favorite language a function that take any derecursified/decoupled function and, assuming the original function was tail-recursive, produce a tail-recursive implementation of it, using an explicit call stack, wich doesn't depend on the implementation of tail recursion in the compiler/runtime.

Reply To This Comment

(why do I need your e-mail?)

(Your twitter handle, if you have one.)

Type the word "apple_197": (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.