Beware of bugs in the above code; I have only proved it correct, not tried it.
I am doing a startup!
Cross-browser testing from your browser!
I have written my fourth book!
Be faster than Larry Wall at command line!
You're viewing a comment by bluestorm and its responses.
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.
Peteris > 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.
(why do I need your e-mail?)
It would be nice if you left your e-mail address. Sometimes I want to send a private message, or just thank for the great comment. Having your e-mail really helps.
I will never ever spam you.
(Your twitter name, if you have one. (I'm @pkrumins, btw.))
* use <pre>...</pre> to insert a plain code snippet.
* use <pre lang="lang">...</pre> to insert a syntax highlighted code snippet.
For example, <pre lang="python">...</pre> will insert Python highlighted code.
* use <code>...</code> to highlight a variable or a single shell command.
* use <a href="url">title</a> to insert links.
* use other HTML tags, such as, <b>, <i>, <blockquote>, <sup>, <sub> for text formatting.
Type the first letter of your name: (just to make sure you're a human)
Please preview the comment before submitting to make sure it's OK.
Peteris Krumins' blog about programming, hacking, software reuse, software ideas, computer security, google and technology.
Reach me at:
Or meet me on:
Subscribe through an RSS feed:
(what is rss?)
Subscribe through email:
Enter your email address:
Delivered by FeedBurner
I am being sponsored by Syntress since 2007! They bought me an amazing dedicated server to run catonmat on. If you're looking web services in Chicago area, I highly recommend the Syntress guys!
I love to read science books. They make my day and I get ideas for awesome blog posts, such as Busy Beaver, On Functors, Recursive Regular Expressions and many others.
Take a look at my Amazon wish list, if you're curious about what I have planned reading next, and want to surprise me. :)
See all top articles
See all downloads
See more detailed list of recent articles
See more detailed category information
See more detailed list of all articles
catonmat's source code.
If you are interested in advertising on catonmat.net, contact me.