Which languages support *recursive* function literals / anonymous functions?

Question

It seems quite a few mainstream languages support function literals these days. They are also called anonymous functions, but I don't care if they have a name. The important thing is that a function literal is an expression which yields a function which hasn't already been defined elsewhere, so for example in C, &printf doesn't count.

EDIT to add: if you have a genuine function literal expression <exp>, you should be able to pass it to a function f(<exp>) or immediately apply it to an argument, ie. <exp>(5).

I'm curious which languages let you write function literals which are recursive. Wikipedia's "anonymous recursion" article doesn't give any programming examples.

Let's use the recursive factorial function as the example.

Here are the ones I know:

• JavaScript / ECMAScript can do it with callee:

  function(n){if (n<2) {return 1;} else {return n * arguments.callee(n-1);}}
  

• it's easy in languages with letrec, eg Haskell (which calls it let):

  let fac x = if x<2 then 1 else fac (x-1) * x in fac

  and there are equivalents in Lisp and Scheme. Note that the binding of fac is local to the expression, so the whole expression is in fact an anonymous function.

Are there any others?

Neckcloth

Anonymous functions are different from dynamic functions, the difference is in scope, an anonymous function or 'function literal' is a true object just as an integer 3. For instance, PHP prior to 5.3 did have dynamic functions, but not anonymous. (See post below) – Meakem

Answer 1

Most languages support it through use of the Y combinator. Here's an example in Python (from the cookbook):

# Define Y combinator...come on Gudio, put it in functools!
Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg)))

# Define anonymous recursive factorial function
fac = Y(lambda f: lambda n: (1 if n<2 else n*f(n-1)))
assert fac(7) == 5040

Jaggery

"Most languages" No, any statically-typed language cannot write the real Y combinator. – Colpin

@newacct, contrary to your statement, here is an implementation of a Y combinator in Scala: scala-blogs.org/2008/09/y-combinator-in-scala.html – Inlay

@avernet: I would argue that that's not a "true" Y combinator, because the Y combinator is an expression in a very specific form, and that example requires an external type, and involves creating an object of that type inside the expression, which is not in the Y combinator. – Colpin

@newacct, this is an interesting argument, and I don't know enough about Y combinators to fully appreciate it. What you are saying seems to go same direction as the couple of sentences starting with "One well-known fixed point combinator…" on the second paragraph of en.wikipedia.org/wiki/Fixed_point_combinator. – Inlay

Answer 2

C#

Reading Wes Dyer's blog, you will see that @Jon Skeet's answer is not totally correct. I am no genius on languages but there is a difference between a recursive anonymous function and the "fib function really just invokes the delegate that the local variable fib references" to quote from the blog.

The actual C# answer would look something like this:

delegate Func<A, R> Recursive<A, R>(Recursive<A, R> r);

static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f)
{
    Recursive<A, R> rec = r => a => f(r(r))(a);
    return rec(rec);
}

static void Main(string[] args)
{
    Func<int,int> fib = Y<int,int>(f => n => n > 1 ? f(n - 1) + f(n - 2) : n);
    Func<int, int> fact = Y<int, int>(f => n => n > 1 ? n * f(n - 1) : 1);
    Console.WriteLine(fib(6));                          // displays 8
    Console.WriteLine(fact(6));
    Console.ReadLine();
} 

Kimura

Yes, the Y combinator will certainly do the trick, and is recursion in a somewhat purer sense - it's just harder to understand than my "pseudo-recursion" solution :) – Charbonnier

Harder may be an understatement :) – Kimura

Answer 3

You can do it in Perl:

my $factorial = do {
  my $fac;
  $fac = sub {
    my $n = shift;
    if ($n < 2) { 1 } else { $n * $fac->($n-1) }
  };
};

print $factorial->(4);

The do block isn't strictly necessary; I included it to emphasize that the result is a true anonymous function.

Clabber

Answer 4

Well, apart from Common Lisp (labels) and Scheme (letrec) which you've already mentioned, JavaScript also allows you to name an anonymous function:

var foo = {"bar": function baz() {return baz() + 1;}};

which can be handier than using callee. (This is different from function in top-level; the latter would cause the name to appear in global scope too, whereas in the former case, the name appears only in the scope of the function itself.)

Billington

Answer 5

In Perl 6:

my $f = -> $n { if ($n <= 1) {1} else {$n * &?BLOCK($n - 1)} }
$f(42);  # ==> 1405006117752879898543142606244511569936384000000000

Alkalimeter

Answer 6

F# has "let rec"

Patterman

Answer 7

You've mixed up some terminology here, function literals don't have to be anonymous.

In javascript the difference depends on whether the function is written as a statement or an expression. There's some discussion about the distinction in the answers to this question.

Lets say you are passing your example to a function:

foo(function(n){if (n<2) {return 1;} else {return n * arguments.callee(n-1);}});

This could also be written:

foo(function fac(n){if (n<2) {return 1;} else {return n * fac(n-1);}});

In both cases it's a function literal. But note that in the second example the name is not added to the surrounding scope - which can be confusing. But this isn't widely used as some javascript implementations don't support this or have a buggy implementation. I've also read that it's slower.

Anonymous recursion is something different again, it's when a function recurses without having a reference to itself, the Y Combinator has already been mentioned. In most languages, it isn't necessary as better methods are available. Here's a link to a javascript implementation.

Whinstone

Answer 8

In C# you need to declare a variable to hold the delegate, and assign null to it to make sure it's definitely assigned, then you can call it from within a lambda expression which you assign to it:

Func<int, int> fac = null;
fac = n => n < 2 ? 1 : n * fac(n-1);
Console.WriteLine(fac(7));

I think I heard rumours that the C# team was considering changing the rules on definite assignment to make the separate declaration/initialization unnecessary, but I wouldn't swear to it.

One important question for each of these languages / runtime environments is whether they support tail calls. In C#, as far as I'm aware the MS compiler doesn't use the tail. IL opcode, but the JIT may optimise it anyway, in certain circumstances. Obviously this can very easily make the difference between a working program and stack overflow. (It would be nice to have more control over this and/or guarantees about when it will occur. Otherwise a program which works on one machine may fail on another in a hard-to-fathom manner.)

Edit: as FryHard pointed out, this is only pseudo-recursion. Simple enough to get the job done, but the Y-combinator is a purer approach. There's one other caveat with the code I posted above: if you change the value of fac, anything which tries to use the old value will start to fail, because the lambda expression has captured the fac variable itself. (Which it has to in order to work properly at all, of course...)

Charbonnier

It seems like you were on the path to the right answer, but did not totally get there. Creating a copy of fac (Func<int, int> facCopy = fac;) and then change the definition of fac will cause facCopy and fac to return different results. – Kimura

FryHard: We're thinking of the same thing. Where I wrote "the old value" that's where you've got facCopy :) – Charbonnier

Answer 9

You can do this in Matlab using an anonymous function which uses the dbstack() introspection to get the function literal of itself and then evaluating it. (I admit this is cheating because dbstack should probably be considered extralinguistic, but it is available in all Matlabs.)

f = @(x) ~x || feval(str2func(getfield(dbstack, 'name')), x-1)

This is an anonymous function that counts down from x and then returns 1. It's not very useful because Matlab lacks the ?: operator and disallows if-blocks inside anonymous functions, so it's hard to construct the base case/recursive step form.

You can demonstrate that it is recursive by calling f(-1); it will count down to infinity and eventually throw a max recursion error.

>> f(-1)
??? Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)
to change the limit.  Be aware that exceeding your available stack space can
crash MATLAB and/or your computer.

And you can invoke the anonymous function directly, without binding it to any variable, by passing it directly to feval.

>> feval(@(x) ~x || feval(str2func(getfield(dbstack, 'name')), x-1), -1)
??? Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)
to change the limit.  Be aware that exceeding your available stack space can
crash MATLAB and/or your computer.

Error in ==> create@(x)~x||feval(str2func(getfield(dbstack,'name')),x-1)

To make something useful out of it, you can create a separate function which implements the recursive step logic, using "if" to protect the recursive case against evaluation.

function out = basecase_or_feval(cond, baseval, fcn, args, accumfcn)
%BASECASE_OR_FEVAL Return base case value, or evaluate next step
if cond
    out = baseval;
else
    out = feval(accumfcn, feval(fcn, args{:}));
end

Given that, here's factorial.

recursive_factorial = @(x) basecase_or_feval(x < 2,...
    1,...
    str2func(getfield(dbstack, 'name')),...
    {x-1},...
    @(z)x*z);

And you can call it without binding.

>> feval( @(x) basecase_or_feval(x < 2, 1, str2func(getfield(dbstack, 'name')), {x-1}, @(z)x*z), 5)
ans =
   120

Rambunctious

I don't have Matlab but you seem to have missed the obvious: ` @(x) ~x || x * feval(str2func(getfield(dbstack, 'name')), x-1) ` . +1 anyway :) – Neckcloth

@Hugh Allen: unfortunately, Matlab's || operator converts its operands to logical (0/1) values, so the simpler variant you suggest would always evaluate to 1 or 0. Hence the contortions to get a useful factorial implementation. Thanks. – Rambunctious

There is also a slightyl less verbose version shown here. – Bernhard

Answer 10

It also seems Mathematica lets you define recursive functions using #0 to denote the function itself, as:

(expression[#0]) &

e.g. a factorial:

fac = Piecewise[{{1, #1 == 0}, {#1 * #0[#1 - 1], True}}] &;

This is in keeping with the notation #i to refer to the ith parameter, and the shell-scripting convention that a script is its own 0th parameter.

Wiebmer

Answer 11

I think this may not be exactly what you're looking for, but in Lisp 'labels' can be used to dynamically declare functions that can be called recursively.

(labels ((factorial (x) ;define name and params
    ; body of function addrec
    (if (= x 1)
      (return 1)
      (+ (factorial (- x 1))))) ;should not close out labels
  ;call factorial inside labels function
  (factorial 5)) ;this would return 15 from labels

Prurient

Answer 12

Delphi includes the anonymous functions with version 2009.

Example from http://blogs.codegear.com/davidi/2008/07/23/38915/

type
  // method reference
  TProc = reference to procedure(x: Integer);               

procedure Call(const proc: TProc);
begin
  proc(42);
end;

Use:

var
  proc: TProc;
begin
  // anonymous method
  proc := procedure(a: Integer)
  begin
    Writeln(a);
  end;               

  Call(proc);
  readln
end.

Skive

Answer 13

Because I was curious, I actually tried to come up with a way to do this in MATLAB. It can be done, but it looks a little Rube-Goldberg-esque:

>> fact = @(val,branchFcns) val*branchFcns{(val <= 1)+1}(val-1,branchFcns);
>> returnOne = @(val,branchFcns) 1;
>> branchFcns = {fact returnOne};
>> fact(4,branchFcns)

ans =

    24

>> fact(5,branchFcns)

ans =

   120

Overbear

I don't know MATLAB but that doesn't look anonymous to me. Can you write a function expression without binding the names 'fact', 'returnOne', and 'branchFcns'? – Neckcloth

'fact' and 'returnOne' are simply the variables that store the handles to the two anonymous functions. External to the functions, 'branchFcns' is simply a variable passed in which can be called anything. Within the functions, the inputs 'val' and 'branchFcns' can be given any name. – Overbear

Answer 14

Anonymous functions exist in C++0x with lambda, and they may be recursive, although I'm not sure about anonymously.

auto kek = [](){kek();}

Goodhen

Answer 15

'Tseems you've got the idea of anonymous functions wrong, it's not just about runtime creation, it's also about scope. Consider this Scheme macro:

(define-syntax lambdarec
  (syntax-rules ()
    ((lambdarec (tag . params) . body)
     ((lambda ()
       (define (tag . params) . body)
        tag)))))

Such that:

(lambdarec (f n) (if (<= n 0) 1 (* n (f (- n 1)))))

Evaluates to a true anonymous recursive factorial function that can for instance be used like:

(let ;no letrec used
    ((factorial (lambdarec (f n) (if (<= n 0) 1 (* n (f (- n 1)))))))
  (factorial 4)) ; ===> 24

However, the true reason that makes it anonymous is that if I do:

((lambdarec (f n) (if (<= n 0) 1 (* n (f (- n 1))))) 4)

The function is afterwards cleared from memory and has no scope, thus after this:

(f 4)

Will either signal an error, or will be bound to whatever f was bound to before.

In Haskell, an ad hoc way to achieve same would be:

\n -> let fac x = if x<2 then 1 else fac (x-1) * x
    in fac n

The difference again being that this function has no scope, if I don't use it, with Haskell being Lazy the effect is the same as an empty line of code, it is truly literal as it has the same effect as the C code:

3;

A literal number. And even if I use it immediately afterwards it will go away. This is what literal functions are about, not creation at runtime per se.

Meakem

Nothing you have said convinces me that I've got anything wrong. "expression which yields a function" doesn't imply runtime creation, and what you are saying about scope is obvious. I made the distinction between anonymous functions and function literals because I don't care if in some weird language, a function literal introduces a new binding, ie. a new named (non-anonymous) function. – Neckcloth

Well, I'm sorry, you just have your terminology wrong, function-literal or anonymous function as the name suggests implies nothing more than a nameless function. Your JavaScript function is is anonymous, your Haskell function is named. And expression which yields a function does imply creation at runtime, the value of an expression is only known at runtime. An anonymous function is just a function-object returned from some function creating expression that's not given a name, just as an expression can return a number object that can be used directly and not stored in a variable first. – Meakem

"JavaScript function is is anonymous ... Haskell function is named". You are still missing my point about not caring whether it's anonymous. "expression which yields a function does imply creation at runtime". I suppose you haven't heard of a "constant-expression" or an "optimizing compiler". The value of 1+1 is usually known at compile time. A function expression is a little more complex, but evaluating the expression at compile time to produce a "function" (in the form of machine code etc) is what a compiler does. – Neckcloth

No, then it's not an expression, that's why in C, functions are in fact declared by statements, and not by expressions. The value of 1+1 theoretically is not known at compile time though some compilers run it for optimization sake. The question of named functions can have recursion is not interesting, all named versions can refer to themselves and thus have recursion. There isn't a language in the world which does not allow recursion in its named functions, compile time or runtime, but there are some languages which don't in anonymous (PHP < 5.3 for instance) – Meakem

@Lajla: "There isn't a language in the world which does not allow recursion in its named functions": That's a rash statement ;) I can name at least two. (early versions of BASIC and FORTRAN) – Neckcloth

Fair enough, I rephrase, there isn't a language used today which doesn't. – Meakem

Answer 16

Clojure can do it, as fn takes an optional name specifically for this purpose (the name doesn't escape the definition scope):

> (def fac (fn self [n] (if (< n 2) 1 (* n (self (dec n))))))
#'sandbox17083/fac
> (fac 5)
120
> self
java.lang.RuntimeException: Unable to resolve symbol: self in this context

If it happens to be tail recursion, then recur is a much more efficient method:

> (def fac (fn [n] (loop [count n result 1]
                     (if (zero? count)
                       result
                       (recur (dec count) (* result count))))))

Photomontage