Какие языки поддерживают * рекурсивные * функции литералов/анонимные функции?

Question

Кажется, в наши дни довольно много основных языков поддержки function literals. Их также называют anonymous functions, но мне все равно, есть ли у них имя. Важно то, что литерал функции является выражением, которое дает функцию, которая еще не определена в другом месте, поэтому, например, в C, &printf не учитывается.

EDIT, чтобы добавить: если у вас есть истинное функциональное выражение <exp>, вы должны передать его функции f(<exp>) или сразу применить ее к аргументу, т.е. <exp>(5).

Мне любопытно, какие языки позволяют писать функциональные литералы, которые являются рекурсивными. Статья в Википедии «anonymous recursion» не содержит примеров программирования.

В качестве примера воспользуемся рекурсивной факторной функцией.

Вот те, которые я знаю:

• JavaScript/ECMAScript может сделать это с callee:

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

• легко в языках с letrec, например, Haskell (который называет его let) :

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

  и есть эквиваленты в Lisp и Scheme. Обратите внимание, что привязка fac является локальной для выражения, поэтому все выражение на самом деле является анонимной функцией.

Есть ли другие?

Answer 1

F# имеет "пусть Rec"

Answer 2

Ну, кроме Common Lisp (labels) и схемы (letrec), который вы уже упоминалось, JavaScript также позволяет назвать анонимную функцию:

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

который может быть более удобным, чем using callee. (Это отличаетс от function на верхнем уровне, а последнее может вызывать его также в глобальном масштабе, тогда как в первом случае имя отображается только в пределах самой функции.)

Answer 3

Поддержка большинства языков это путем использования Y combinator. Вот пример в Python (от 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

Вы можете сделать это в Perl:

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

print $factorial->(4); 

do блок не является строго необходимым; Я включил его, чтобы подчеркнуть, что результатом является истинная анонимная функция.

Answer 5

В C# вы должны объявить переменную для хранения делегата и присвоить нуль к нему, чтобы убедиться, что он определенно присвоенной, то вы можете вызвать его из внутри лямбда-выражения, которые вы назначаете ему:

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

I Я слышал слухи о том,

Одним из важных вопросов для каждого из этих языков/сред выполнения является поддержка хвостовых вызовов. В C#, насколько я знаю, MS-компилятор не использует код операции tail. IL, но JIT may optimise it anyway, in certain circumstances. Очевидно, что это очень легко может сделать разницу между рабочей программой и переполнением стека. (Было бы неплохо иметь больший контроль над этим и/или гарантировать, когда это произойдет. В противном случае программа, работающая на одной машине, может быть неудачной с другой с помощью жесткого подхода).

Редактировать: as FryHard указал, что это только псевдорекурсия. Достаточно просто, чтобы выполнить задание, но Y-combinator - более чистый подход. Есть еще одно предостережение от кода, который я написал выше: если вы измените значение fac, все, что пытается использовать старое значение, начнет сбой, потому что выражение лямбда захватило переменную fac. (Что нужно для правильной работы вообще, конечно ...)

Answer 6

Я думаю, что это может быть не совсем то, что вы ищете, но в методах Lisp можно использовать для динамического объявления функций которые можно назвать рекурсивно.

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

Чтение Wes Dyer's блог, вы увидите, что ответ @ Джон Скита не совсем правильно. Я не гений на языках, но есть разница между рекурсивной анонимной функцией, а функция «» действительно просто вызывает делегата, что локальная переменная fib ссылается на », чтобы процитировать из блога.

Фактическая C# ответ будет выглядеть примерно так:

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 включает в себя анонимные функции с версии 2009.

Пример из 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; 

Использование:

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

    Call(proc); 
    readln 
end. 

Answer 9

Вы перепутали какую-то терминологию здесь, функциональные литералы не обязательно должны быть анонимными.

В javascript разница зависит от того, написана ли функция как оператор или выражение. Обсуждаются различия в ответах на вопросы this question.

Допустим, вы передаете ваш пример функции:

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

Это также может быть написано:

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

В обоих случаях это функция буквальным. Но учтите, что во втором примере имя не добавляется в окружающую область, что может сбивать с толку. Но это не широко используется, так как некоторые реализации javascript не поддерживают это или имеют ошибочную реализацию. Я также читал, что это медленнее.

Анонимная рекурсия снова является чем-то другим, когда функция повторяется без ссылки на себя, Y Combinator уже упоминался. В большинстве языков это не обязательно, поскольку доступны лучшие методы. Вот ссылка на a javascript implementation.

Answer 10

В Perl 6:

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

Answer 11

Потому что мне было интересно, я на самом деле пытался придумать способ сделать это в MATLAB. Это может быть сделано, но это выглядит немного Руби-Голдберг-эск:

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

Вы можете сделать это в Matlab, используя анонимную функцию, которая использует dbstack() самоанализа, чтобы получить функцию буквальное себя, а затем оценить Это. (Я признаю, что это обман, потому что dbstack вероятно, следует считать экстралингвистические, но она доступна во всех Matlabs.)

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

Это анонимная функция, которая отсчитывает от х, а затем возвращает 1. Это не очень полезно, потому что Matlab не имеет оператора?: И запрещает if-блоки внутри анонимных функций, поэтому сложно построить базовый регистр/рекурсивную форму шага.

Вы можете продемонстрировать, что он является рекурсивным, вызывая f (-1); он будет отсчитывать до бесконечности и, в конечном счете, выдает ошибку максимальной рекурсии.

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

И вы можете вызвать анонимную функцию непосредственно, без привязки его к какой-либо переменной, переходя непосредственно к 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) 

Чтобы сделать что-то полезное из этого, вы можете создать отдельную функцию, которая реализует рекурсивный шаг логику, с помощью «если», чтобы защитить рекурсивное дело против оценки.

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 

Учитывая, что здесь факториал.

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

И вы можете назвать это без привязки.

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

Answer 13

Анонимные функции существуют в C++ 0x с лямбда, и они могут быть рекурсивными, хотя я не уверен, что анонимно.

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

Answer 14

«Tseems у вас есть идея анонимных функций неправильно, это не только о создании во время выполнения, это также о объеме.Рассмотрим эту схему макрос:

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

, что:

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

Оценивает к истинному анонимной рекурсивной функции факториала, которая может, например, использоваться как:

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

Однако, истинная причина что делает его анонимным, если я это сделаю:

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

Функции затем стираются из памяти и не имеют рамок, таким образом, после этого:

(f 4) 

либо сигнализировать об ошибке, или будет привязан к любым е было связан прежде.

В Haskell, специальный способ достижения же будет:

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

Разница снова в том, что эта функция не имеет рамки, если я не использую его, с Haskell лениться эффект так же, как пустая строка коды, это действительно буквальная, как это имеет тот же эффект, что и код C:

3; 

буквального номер. И даже если я буду использовать его сразу после этого, он уйдет. Это то, что есть буквальные функции, а не создание во время выполнения как таковое.

Answer 15

Это также кажется Mathematica позволяет определять рекурсивные функции, используя #0 для обозначения самой функции, как:

(expression[#0]) & 

например факториал:

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

Это в соответствии с обозначениями #i для обозначения параметра го, и оболочка-сценариев соглашение, что сценарий является его собственным параметром 0th.

Answer 16

Clojure может сделать это, так как fn занимает дополнительное имя специально для этой цели (имя не выходит рамки определения):

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

Если это происходит с хвостовой рекурсией, то recur является гораздо более эффективный метод:

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