Кажется, что в настоящее время несколько основных языков поддерживают литералы функций. Их также называют анонимными функциями, но мне все равно, есть ли у них имя. Важно то, что литерал функции является выражением, которое дает функцию, которая еще не определена в другом месте, поэтому, например, в C, &printf не учитывается.
EDIT, чтобы добавить: если у вас есть истинное выражение функции <exp>, вы должны передать его функции f(<exp>) или сразу применить ее к аргументу, т.е. <exp>(5).
Мне любопытно, какие языки позволяют писать литералы функций, которые являются рекурсивными. Wikipedia " анонимная рекурсия" статья не дает никаких примеров программирования.
В качестве примера можно использовать рекурсивную факториальную функцию.
Вот те, которые я знаю:
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 и схеме. Обратите внимание, что привязка fac является локальной для выражения, поэтому все выражение на самом деле является анонимной функцией.
Есть ли другие?
Большинство языков поддерживают его с помощью 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
С#
Чтение Wes Dyer's, вы увидите, что ответ @Jon Skeet не совсем корректен. Я не гений на языках, но есть разница между рекурсивной анонимной функцией, и "функция fib действительно просто вызывает делегата, что локальная переменная fib ссылается" на цитату из блога.
Фактический ответ С# будет выглядеть примерно так:
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();
}
Вы можете сделать это в Perl:
my $factorial = do {
my $fac;
$fac = sub {
my $n = shift;
if ($n < 2) { 1 } else { $n * $fac->($n-1) }
};
};
print $factorial->(4);
Блок do не является строго необходимым; Я включил его, чтобы подчеркнуть, что результатом является истинная анонимная функция.
Ну, кроме общих Lisp (labels) и Scheme (letrec), которые вы уже упоминали, JavaScript также позволяет вам назвать анонимную функцию:
var foo = {"bar": function baz() {return baz() + 1;}};
который может быть более удобным, чем используя callee. (Это отличается от function на верхнем уровне, а последнее приведет к тому, что имя появится в глобальной области тоже, тогда как в первом случае имя появляется только в области самой функции.)
В Perl 6:
my $f = -> $n { if ($n <= 1) {1} else {$n * &?BLOCK($n - 1)} }
$f(42); # ==> 1405006117752879898543142606244511569936384000000000
F # имеет "let rec"
Вы перепутали какую-то терминологию здесь, функциональные литералы не должны быть анонимными.
В 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.
В С# вам нужно объявить переменную для хранения делегата и присвоить ей нуль, чтобы убедиться, что она определенно назначена, затем вы можете вызвать ее из выражения lambda, которое вы ему назначили:
Func<int, int> fac = null;
fac = n => n < 2 ? 1 : n * fac(n-1);
Console.WriteLine(fac(7));
Я думаю, что слышал слухи о том, что команда С# рассматривала возможность изменения правил на определенном задании, чтобы сделать отдельную декларацию/инициализацию ненужной, но я не стал бы к ней ругаться.
Одним из важных вопросов для каждого из этих языков/сред выполнения является поддержка хвостовых вызовов. В С#, насколько мне известно, компилятор MS не использует код операции tail. IL, но JIT может в любом случае оптимизировать его, в определенных обстоятельства. Очевидно, что это очень легко может сделать разницу между рабочей программой и переполнением стека. (Было бы неплохо иметь больше контроля над этим и/или гарантировать, когда это произойдет. В противном случае программа, работающая на одной машине, может сработать с ошибкой другим способом.)
Изменить: как FryHard указал, что это только псевдорекурсия. Достаточно просто, чтобы выполнить работу, но Y-combinator - более чистый подход. Там есть еще одно предостережение от кода, который я написал выше: если вы измените значение fac, все, что пытается использовать старое значение, начнет сбой, потому что выражение лямбда захватило сама переменная fac. (Который он должен, чтобы нормально работать вообще, конечно...)
Вы можете сделать это в 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 ==> [email protected](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
Также кажется, что Mathematica позволяет вам определять рекурсивные функции, используя #0 для обозначения самой функции, как:
(expression[#0]) &
например. факториал:
fac = Piecewise[{{1, #1 == 0}, {#1 * #0[#1 - 1], True}}] &;
Это соответствует обозначению #i для ссылки на i-й параметр, а соглашение оболочки-скрипта, что script является его собственным 0-м параметром.
Я думаю, что это может быть не совсем то, что вы ищете, но в 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
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.
Поскольку мне было любопытно, я на самом деле пытался придумать способ сделать это в MATLAB. Это можно сделать, но это выглядит немного 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
Анонимные функции существуют в С++ 0x с lambda, и они могут быть рекурсивными, хотя я не уверен в анонимности.
auto kek = [](){kek();}
'У вас есть идея анонимных функций неправильно, это не просто создание среды выполнения, но и область. Рассмотрим этот макрос схемы:
(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 Lazy эффект такой же, как и пустая строка кода, он действительно литерал, поскольку он имеет тот же эффект, что и C код:
3;
Литеральное число. И даже если я буду использовать его сразу после этого, он уйдет. Это то, что буквальные функции, а не создание во время выполнения как таковое.
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))))))