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

Question

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

ИЗМЕНИТЬ, чтобы добавить: если у вас есть подлинное буквальное выражение функции <exp>, вы должны быть в состоянии передать его функции f(<exp>) или сразу применить его к аргументу, т.е. <exp>(5).

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

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

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

• 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

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

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

Answer 1

Большинство языков поддерживают это благодаря использованию Y комбинатора . Вот пример на Python (из поваренной книги ):

# 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

C #

Читая блог Уэса Дайера , вы увидите, что ответ @Jon Skeet не совсем правильный. Я не гений в языках, но есть разница между рекурсивной анонимной функцией и функцией " fib", которая на самом деле просто вызывает делегата, на который локальная переменная 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 3

Вы можете сделать это в 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 4

В Perl 6:

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

Answer 5

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

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

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

Answer 6

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

В javascript разница зависит от того, записана ли функция в виде оператора или выражения. В ответах на этот вопрос .

обсуждается различие.

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

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 уже упоминался В большинстве языков это не обязательно, так как доступны лучшие методы. Вот ссылка на реализацию javascript .

Answer 7

F # имеет "let rec"

Answer 8

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

(expression[#0]) &

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

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

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

Answer 9

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

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

Это анонимная функция, которая отсчитывает от x и возвращает 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)

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

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 10

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

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

Я думаю Я слышал слухи о том, что команда C # рассматривает возможность изменения правил для определенного назначения, чтобы сделать ненужным отдельное объявление / инициализацию, но я бы не стал клясться в этом.

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

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