What languages ​​support * recursive * literal / anonymous function functions?

Question

It seems that currently several major languages ​​support function literals . 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 that gives a function that is not yet defined elsewhere, therefore, for example, in C, &printf not taken into account.

EDIT to add: if you have a true expression of the <exp> function, you must pass it to the f(<exp>) function or apply it immediately to the argument, i.e. <exp>(5) .

I am curious what languages ​​allow you to write function literals that are recursive. The Wikipedia " anonymous recursion " article does not provide any programming examples.

As an example, you can use a recursive factorial function.

Here are the ones I know:

• JavaScript / ECMAScript can do this with callee :

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

• easy in languages ​​with letrec , like Haskell (which calls let ):

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

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

Are there any others?

Answer 1

Most languages ​​support it with Y combinator . Here is an example in Python (from 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 

Answer 2

FROM#

Reading Wes Dyer's , you will see that @Jon Skeet's answer is not entirely correct. I am not a genius in languages, but there is a difference between a recursive anonymous function, and "the fib function really just calls the delegate that the local variable fib refers" to a 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(); } 

Answer 3

You can do this 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 is not strictly necessary; I included it to emphasize that the result is a true anonymous function.

Answer 4

Well, apart from the generic Lisp ( labels ) and Scheme ( letrec ) that you already mentioned, JavaScript also lets you name an anonymous function:

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

which may be more convenient than using callee . (This differs from function at the top level, and the latter will cause the name to appear in the global area too, while in the first case the name appears only in the area of ​​the function itself.)

Answer 5

In Perl 6:

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

Answer 6

F # has "let rec"

Answer 7

You have mixed up some terminology here, functional literals should not be anonymous.

In javascript, the difference depends on whether the function is written as an operator or expression. It discusses the difference in answers to this question .

Let's say you pass your example function:

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

This can also be written:

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

In both cases, it is a function literal. But keep in mind that in the second example, the name is not added to the surrounding area, which can be confusing. But this is not widely used, as some javascript implementations do not support this or have an erroneous implementation. I also read that it is slower.

Anonymous recursion is again something else, when a function recurses without reference to itself, Y Combinator has already been mentioned. In most languages, this is not necessary as best practices are available. Here is a link to javascript implementation .

Answer 8

In C #, you need to declare a variable to hold the delegate and set it to zero to make sure it is definitely assigned, then you can call it from the lambda expression that you assigned to it:

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

I think I heard rumors that the C # team was considering changing the rules on a specific task to make a separate declaration / initialization unnecessary, but I would not swear at it.

One of the important issues for each of these languages ​​/ runtimes is support for tail calls. In C #, as far as I know, the MS compiler does not use tail. operation code tail. IL, but JIT can optimize it anyway, in certain circumstances . Obviously, this can very easily make the difference between a work program and a stack overflow. (It would be nice to have more control over this and / or guarantee when this will happen. Otherwise, a program running on one machine might fail in another way.)

Edit: as FryHard pointed out that this is only pseudo recursion . Simple enough to get the job done, but Y-combinator is a cleaner approach. There is another caveat from the code that I wrote above: if you change the fac value, everything that tries to use the old value will fail because the lambda expression is captured by the fac variable itself. (Which he needs to work properly in general, of course ...)

Answer 9

You can do this in Matlab using an anonymous function that uses the dbstack () introspection to get the function literal itself and then evaluate it. (I admit that this is a hoax because dbstack should 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 from x and then returns 1. This is not very useful, because Matlab does not have an operator ?: and forbids if-blocks inside anonymous functions, so it is difficult to construct a base register / recursive step form.

You can demonstrate that it is recursive by calling f (-1); it will count indefinitely and, ultimately, will produce a maximum 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 call an anonymous function directly, without binding it to any variable, 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 this, you can create a separate function that implements the recursive logic of the step, using "if" to protect the recursive case from being evaluated.

 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 there is a 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 reference.

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

Answer 10

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

 (expression[#0]) & 

eg. factorial:

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

This corresponds to the designation #i for reference to the ith parameter, and the shell-script convention that the script is its own 0th parameter.

Answer 11

I think this may not be exactly what you are 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 

Answer 12

Delphi includes anonymous features 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; 

Using:

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

Answer 13

Since 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 bit 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 

Answer 14

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

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

Answer 15

'You have the idea of ​​anonymous functions incorrectly, this is not just the creation of a runtime environment, but also an area. Consider this schema macro:

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

In this way:

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

Computes a true anonymous recursive factorial function that can, for example, be used as:

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

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

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

Then the function is cleared from memory and has no scope, so after that:

 (f 4) 

They will either signal an error, or will be associated with what was previously associated with.

In Haskell, a special way to achieve the same result would be:

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

The difference, again, is that this function does not have scope, if I do not use it, since the Haskell Lazy effect is the same as an empty line of code, it really is a literal, because it has the same effect as the C code:

 3; 

Literal number. And even if I use it right after that, it will leave. This is what literal functions are, not creation at run time as such.

Answer 16

Clojure can do this because fn uses an optional name (the name does not go beyond the scope of the definition):

 > (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 this is 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))))))