I’ve struggled a bit in the past to explain why letrec was necessary to allow recursion in a language with first class functions. All we’re trying to achieve is:
|
1 |
sub recurse() { recurse() } |
But without the use of a global subroutine name, or in fact any environment assignments. If you remember, letrec created a recursive function by creating a symbol naming the function first, with a dummy value, then evaluated the function in the environment where it’s name was already present, then assigned the resulting closure to the symbol so the function could “see itself”. But in a purely functional setting, assignment is bad, right?
There is a little bit of programming language magic called the “Y-Combinator” that does the job. It’s very succinctly expressed in the λ calculus as:
|
1 |
λ.x (x x) (λ.x (x x)) |
That is to say, a function taking a function as argument applying that function to itself, and given (a copy of) itself as argument.
In case this seems all a bit too esoteric, here it is in F♮:
|
1 |
fn (x) { x(x) }( fn (x) { x(x) } ) |
And if that’s still too esoteric here it is in Perl:
|
1 2 3 4 5 6 7 8 9 |
sub { my ($x) = @_; $x->($x) }->( sub { my ($x) = @_; $x->($x) } ); |
Notice that we haven’t named any subroutine, so on the face of it recursion is impossible, but nonetheless, if you give the above code to perl it will very slowly rattle your discs until an out of memory exception, without even a deep recursion error because there’s no function name for perl to attribute the recursion to.
Beore going any further I should point out that none of this is of any value to you whatsoever, other than to assuage your curiosity. Most all modern languages allow recursion, if not support or encourage it (supporting as opposed to just allowing recursion is a fine but important point: scheme supports recursion, Perl and its ilk merely allow it.) Anyway we can use the Y-combinator to calculate a factorial:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
print sub { my ($factorial) = @_; $factorial->($factorial, 5) }->( sub { my ($factorial, $n) = @_; if ($n <= 0) { 1; } else { $n * $factorial->($factorial, $n - 1); } } ); # prints 120 |
Once the inner sub has got hold of itself in $factorial it can call $factorial as a subref. The outer anonymous sub bootstraps the whole thing by:
- Capturing the inner sub in its $factorial
- Both calling $factorial and passing $factorial to it
- Passing an extra argument, 5, the number we require the factorial of.