¿Qué idiomas admiten * recursivos * funciones literales/funciones anónimas?

Question

Parece un buen número de lenguajes de soporte estándar function literals estos días. También se llaman anonymous functions, pero no me importa si tienen un nombre. Lo importante es que una función literal es una expresión que produce una función que no se ha definido en otro lugar, por lo que, por ejemplo, en C, &printf no cuenta.

EDITAR para agregar: si tiene una expresión literal de función genuina <exp>, debe poder pasarla a una función f(<exp>) o aplicarla inmediatamente a un argumento, es decir. <exp>(5).

Tengo curiosidad de qué idiomas le permiten escribir literales de función que son recursivo. El artículo "anonymous recursion" de Wikipedia no da ningún ejemplo de programación.

Vamos a usar la función factorial recursiva como el ejemplo.

Éstos son los que conozco:

• Javascript/ECMAScript puede hacerlo con callee:

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

• es fácil en idiomas con letrec, por ejemplo, Haskell (que lo llama let) :

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

  y no son equivalentes en Lisp y Scheme. Tenga en cuenta que el enlace de fac es local a la expresión, por lo que la expresión completa es, de hecho, una función anónima.

¿Hay algún otro?

Answer 1

F# ha "dejar que rec"

Answer 2

Bueno, aparte de Common Lisp (labels) y medioambientales (letrec), que ya se ha mencionado, JavaScript también permite asignar un nombre a una función anónima:

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

que puede ser más práctico que using callee. (Esto es diferente de function de alto nivel, este último haría que el nombre que aparezca en el ámbito global también, mientras que en el primer caso, el nombre aparece sólo en el ámbito de la propia función.) De apoyo

Answer 3

mayoría de los lenguajes a través del uso del Y combinator. He aquí un ejemplo en Python (del 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 4

usted puede hacerlo en Perl:

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

print $factorial->(4); 

El bloque do no es estrictamente necesario; Lo incluí para enfatizar que el resultado es una verdadera función anónima.

Answer 5

En C# tiene que declarar una variable para contener el delegado, y asignar nula a él para asegurarse de que está definitivamente asignado, continuación se le puede llamar desde el interior de una expresión lambda que se asignan a la misma:

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

I think Escuché rumores de que el equipo de C# estaba considerando cambiar las reglas de asignación definitiva para hacer innecesaria la declaración/inicialización por separado, pero no lo juraría.

Una pregunta importante para cada uno de estos lenguajes/entornos de tiempo de ejecución es si admiten llamadas finales. En C#, hasta donde yo sé, el compilador de MS no utiliza el código de operación tail. IL, pero el JIT may optimise it anyway, in certain circumstances. Obviamente, esto puede marcar la diferencia entre un programa que funcione y un desbordamiento de pila. (Sería bueno tener más control sobre esto y/o garantías sobre cuándo ocurrirá. De lo contrario, un programa que funciona en una máquina puede fallar en otra de una manera difícil de entender).

Editar: como FryHard señalado, esto es solo pseudo-recursión. Lo suficientemente simple como para hacer el trabajo, pero el Y-combinator es un enfoque más puro. Hay otra advertencia con el código que publiqué arriba: si cambia el valor de fac, todo lo que intente usar el valor anterior comenzará a fallar, porque la expresión lambda ha capturado la variable fac. (Para que funcione correctamente, por supuesto ...)

Answer 6

Creo que esto puede no ser exactamente lo que está buscando, pero en Lisp 'etiquetas' se puede usar para declarar funciones dinámicamente que se puede llamar recursivamente.

(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 7

C#

lectura Wes Dyer's blog, se verá que la respuesta de @ Jon Skeet no es totalmente correcto. No soy un genio en idiomas, pero hay una diferencia entre una función anónima recursiva y la función "fib simplemente invoca al delegado que la variable local fib hace referencia a" para citar del blog.

El actual C# respuesta sería algo parecido a esto:

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 8

Delphi incluye las funciones anónimas con la versión 2009.

Ejemplo de 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; 

Uso:

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

    Call(proc); 
    readln 
end. 

Answer 9

Ha mezclado aquí algunos términos, los literales de funciones no tienen que ser anónimos.

En javascript, la diferencia depende de si la función está escrita como una declaración o una expresión. Hay alguna discusión sobre la distinción en las respuestas a this question.

digamos que usted está pasando su ejemplo a una función:

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

Esto también se podría escribir:

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

En ambos casos se trata de un literal de la función. Pero tenga en cuenta que en el segundo ejemplo, el nombre no se agrega al ámbito circundante, lo que puede ser confuso. Pero esto no se usa ampliamente, ya que algunas implementaciones de JavaScript no son compatibles con esto o tienen una implementación incorrecta. También he leído que es más lento.

Recursión anónima es algo diferente otra vez, es cuando una función se repite sin tener una referencia a sí misma, el Combinador Y ya se ha mencionado. En la mayoría de los idiomas, no es necesario ya que hay mejores métodos disponibles. Aquí hay un enlace al a javascript implementation.

Answer 10

En Perl 6:

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

Answer 11

porque tenía curiosidad, en realidad trató de llegar a una manera de hacer esto en MATLAB. Se puede hacer, pero se ve un poco de 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 12

Usted puede hacer esto en Matlab utilizando una función anónima que utiliza la introspección dbstack() para obtener la función literal del mismo y luego evaluar eso. (Admito que esto es hacer trampa porque dbstack probablemente se debe considerar extralingüística, pero está disponible en todas las Matlabs.)

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

Ésta es una función anónima que una cuenta atrás de x y luego devuelve 1. No es muy útil porque Matlab carece del operador?: Y no permite bloques dentro de funciones anónimas, por lo que es difícil construir el caso base/forma de paso recursivo.

Puede demostrar que es recursivo llamando a f (-1); contará hacia abajo hasta el infinito y eventualmente arrojará un error máximo de recursión.

>> 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. 

Y se puede invocar la función anónima directamente, sin enlazarlo a cualquier variable, ésta pasa directamente a 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) 

Para hacer algo útil de ella, puede crear una función separada que implementa la lógica paso recursivo, el uso de "si" para proteger el caso recursivo contra la evaluación.

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 

Dado que, aquí está factorial.

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

Y puede llamarlo sin encuadernar. Existen

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

Answer 13

funciones anónimas en C++ 0x con lambda, y pueden ser recursivas, aunque no estoy seguro de forma anónima.

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

Answer 14

'Tseems que tienes la idea de funciones anónimas mal, no es sólo acerca de la creación de tiempo de ejecución, se trata también de alcance.Considere este esquema macro:

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

tal que:

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

se evalúa como una verdadera función factorial recursiva anónima que pueden por ejemplo ser usado como:

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

Sin embargo, la verdadera razón eso lo hace anónimo es que si lo hago:

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

La función se borra después de la memoria y no tiene un ámbito de aplicación, por lo tanto después de esto:

(f 4) 

, o bien señalar un error, o será obligado a cualquier f estaba destinado a antes.

En Haskell, de manera ad hoc para lograr la misma sería:

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

La diferencia más es que esta función no tiene ningún alcance, si yo no lo uso, con Haskell ser perezoso es el efecto lo mismo que una línea vacía de código, es verdaderamente literal, ya que tiene el mismo efecto que el código C:

3; 

un número literal. E incluso si lo uso inmediatamente después, desaparecerá. De esto se tratan las funciones literales, no la creación en tiempo de ejecución per se.

Answer 15

También parece Mathematica le permite definir funciones recursivas utilizando #0 para denotar la función en sí, como:

(expression[#0]) & 

por ejemplo, un factorial:

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

Esto está de acuerdo con la notación #i para referirse al parámetro i-ésimo, y la convención shell-scripting que un guión es su propio parámetro 0 ª.

Answer 16

Clojure puede hacerlo, como fn toma un nombre opcional específicamente para este propósito (el nombre no se escapa del alcance definición):

> (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 

Si pasa a ser la recursión de cola, a continuación, es una recur método mucho más eficiente:

funciones

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