Реализации алгоритмов/Замыкание
Замыкание (англ. closure) в программировании — функция, в теле которой присутствуют ссылки на переменные, объявленные вне тела этой функции в окружающем коде и не являющиеся её параметрами. Говоря другим языком, замыкание — функция, которая ссылается на свободные переменные в своём контексте.
Реализации замыканий и их аналогов на различных языках программирования[править]
Delphi[править]
Пример работы замыканий на Delphi (c 2009 версии):
type
TGenericFunction = reference to function: string;
function Factory(const ASomeText: string): TGenericFunction;
begin
Result := function: string
begin
Result := ASomeText;
end;
end;
var
f1, f2: TGenericFunction;
begin
f1 := Factory('First');
f2 := Factory('Second');
Writeln(f1);
Writeln(f2);
Readln;
end.
В версиях начиная с 2009, этот код выведет в консоль строки First и Second. Когда переменной типа reference to *** присваивается совместимая по спецификации анонимная подпрограмма или метод, неявно создаётся и инициализируется экземпляр анонимного класса, с полями для хранения значений, используемых подпрограммой из контекста её объявления, методом выполнения (присвоенной подпрограммой) и счётчиком ссылок.
Scheme[править]
Пример работы замыканий на Scheme:
(define (make-adder n) ; возвращает замкнутое лямбда-выражение
(lambda (x) ; в котором x - связанная переменная,
(+ x n))) ; а n - свободная (захваченная из внешнего контекста)
(define add1 (make-adder 1)) ; делаем процедуру для прибавления 1
(add1 10) ; возвращает 11
(define sub1 (make-adder -1)); делаем процедуру для вычитания 1
(sub1 10) ; возвращает 9
C#[править]
Анонимные методы в C# 2.0 могут замыкаться на локальный контекст:
int[] ary = { 1, 2, 3 };
int x = 2;
var ary1 = Array.ConvertAll<int, int>(ary, delegate(int elem) { return elem * x; }); // { 2, 4, 6 }
// or..
var ary2 = Array.ConvertAll<int, int>(ary, elem => elem * x); // { 2, 4, 6 }
Функция Array.ConvertAll преобразует один список/массив в другой, применяя для каждого элемента передаваемую ей в качестве параметра функцию.
В C# 3.0 введены лямбда-выражения, которые делают синтаксис анонимных методов более кратким и выразительным. Соответственно, они также поддерживают замыкания. То есть, замыкания в C# 3.0 практически аналогичны анонимным функциям из C# 2.0, но синтаксически более кратки. Вот тот же пример с применением лямбда-выражений в C# 3.0:
int[] ary = { 1, 2, 3 };
var x = 2;
var ary1 = ary.Select(elem => elem * x); // { 2, 4, 6 }
Метод Select аналогичен методу Array.ConvertAll за тем исключением, что он принимает и возвращает IEnumerable<T>.
C++[править]
В языке C++ замыкание долгое время не поддерживалось. Однако стандарт языка C++11 вводит лямбда-функции и выражения, ограниченно поддерживающие замыкание:
function<function<int()>()> f = [] {
int x = 0;
return [=] () mutable {return ++x; };
};
auto fun = f();
for (int i = 0; i < 5; ++i) {
cout << fun() << endl;
}
VB.NET[править]
В VB.NET 9.0 лямбда-функции могут быть только однострочными. Начиная с версии 10.0, можно использовать синтаксис для описания многострочных лямбда-функций.
Dim ary As Integer() = {1, 2, 3}
Dim x As Integer = 2
' VB.NET 9.0 - { 2, 4, 6 }
Dim ary1() As Integer = Array.ConvertAll(Of Integer, Integer)(ary, Function(elem) elem * x)
' VB.NET 10.0 - { 2, 4, 6 }
Dim ary2() As Integer = Array.ConvertAll(Of Integer, Integer)(ary, Function(elem)
Return elem * x
End Function)
Ruby[править]
Некоторые языки, такие как Ruby, позволяют выбирать различные способы замыканий по отношению к оператору возврата return:
# ruby
def foo
f = Proc.new { return "return from foo from inside proc" }
f.call # после вызова функции замыкания f осуществляется выход из foo
# результатом работы функции foo является результат работы f замыкания
return "return from foo"
end
def bar
f = lambda { return "return from lambda" }
f.call # после вызова функции замыкания f продолжается выполнение bar
return "return from bar"
end
puts foo # печатает "return from foo from inside proc"
puts bar # печатает "return from bar"
И Proc.new, так же как и lambda, в этом примере — это способы создания замыкания, но семантика замыканий различна по отношению к оператору return.
PHP[править]
PHP имеет встроенную поддержку замыканий начиная с версии 5.3. Пример замыкания. Локальная переменная $id будет увеличиваться при вызове возвращаемой функцией getAdder вложенной функции:
function getAdder()
{
$id = 1;
return function() use (&$id){ // use (&$id) для того чтобы передать в возвращаемую функцию внешнюю переменную $id
return $id++;
};
}
$test= getAdder();
echo $test(); //1 $id увеличивается только после того, как возвращается, так как написано $id++
echo $test(); //2
echo $test(); //3
echo $test(); //4
Для более ранних версий возможно использовать одноименный шаблон проектирования, который реализуется в библиотеке Николаса Нассара. P.S. Однако, до сих пор существует проблема с замыканиями в классах, в частности — для статических методов класса.
Java[править]
Java реализует концепцию замыкания с помощью анонимных классов. Анонимный класс имеет доступ к полям класса, в лексическом контексте которого он определён, а также к переменным с модификатором final в лексическом контексте метода.
class CalculationWindow extends JFrame {
private JButton btnSave;
...
public final void calculateInSeparateThread(final URI uri) {
// Выражение "new Thread() { ... }" представляет собой пример анонимного класса.
new Thread() {
public void run() {
// Имеет доступ к финальным (final) переменным:
calculate(uri);
// Имеет доступ к приватным членам содержащего класса:
btnSave.setEnabled(true);
}
}.start();
}
}
Python[править]
Пример с использованием замыканий и каррирования:
# Реализация с помощью именованных функций:
def taskerize(func_object):
def unbound_closure(*args, **kwarg):
def bound_closure():
return func_object(*args, **kwarg)
return bound_closure
return unbound_closure
# Равносильная реализация с использованием lambda:
taskerize = lambda func_object: (
lambda *args, **kwarg: (
lambda: func_object(*args, **kwarg)
)
)
@taskerize # применение декоратора равнозначно записи testfunc = taskerize(testfunc) после объявления функции.
def testfunc(a, b, c):
return a + b * c
f = testfunc(1, 2, 3)
print f() # выведет 7
Пример простого замыкания:
# Реализация с помощью именованных функций:
def make_adder(x):
def adder(n):
return x + n # захват переменной "x" из внешнего контекста
return adder
# То же самое, но через безымянные функции:
make_adder = lambda x: (
lambda n: x + n
)
f = make_adder(10)
print f(5) # 15
print f(-1) # 9
Пример каррирования:
# Функция с кучей аргументов (26 шт.), делающая что-то невразумительное.
def longfunc(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z):
print 'Меня вызвали с такими аргументами: ', a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z
return a + b * c - d / e + f / g - h * i - (j * (k - l) + m) + (n * o) / (p - q + r) + (s * (t + (u * (v + w)))) - (x * y * z)
def curry(func_object, *args):
def innerfunc(*local_args):
# в функции выполняется замыкание на args и func_object из внешнего контекста
return func_object(*(args + local_args)) # а еще нам нужно прилепить в конец тех аргументов, что у нас были, новые
return innerfunc
# По уже сложившейся традиции — то же самое, только лямбдами:
curry = lambda func_object, *args: (
lambda *local_args: (
func_object(
*(args + local_args)
)
)
)
# "достраиваем" функцию, как пожелаем.
f1 = curry(longfunc, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100)
f2 = curry(f1, 110, 120, 130, 140)
f3 = curry(f2, 150, 160, 170, 180, 190, 200)
f4 = curry(f3, 210)
# не обязательно использовать функцию, к которой было применено каррирование, только один раз.
f5 = curry(f4, 220, 230, 240, 250, 260) # раз
f5b = curry(f4, 220, 230, 240, 250) # два!
f6b = curry(f5b, 260)
print f5() # выведет 2387403
print f6b() # опять выведет 2387403
# контроль того, что каррирование всё сделало верно (вызываем функцию со всеми её 26-ю параметрами):
print longfunc( # перенос значений аргументов функций на несколько строк не имеет ничего общего с каррированием. Нет, правда.
10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120,
130, 140, 150, 160, 170, 180, 190, 200, 210, 220, 230,
240, 250, 260
) # да, опять выведет 2387403.
OCaml[править]
В следующем интерактивном примере (add 5) является замыканием, так как содержит как «функцию» (add x), так и «окружение» (x = 5)[1]:
# let add x = (fun y -> x + y) ;;
val add : int -> int -> int = <fun>
# (add 5) 3 ;;
- : int = 8
JavaScript[править]
В JavaScript областью видимости локальных переменных (объявляемых словом var) является тело функции, внутри которой они определены.
Если вы объявляете функцию внутри другой функции, первая получает доступ к переменным и аргументам последней:
function outerFn(myArg) {
var myVar;
function innerFn() {
// имеет доступ к myVar и myArg
}
}
При этом, такие переменные продолжают существовать и остаются доступными внутренней функции даже после того, как внешняя функция, в которой они определены, была исполнена.
Рассмотрим пример — функцию, возвращающую количество собственных вызовов:
function createCounter() {
var numberOfCalls = 0;
return function() {
return ++numberOfCalls;
}
}
var fn = createCounter();
fn(); // 1
fn(); // 2
fn(); // 3
Только после удаления переменной fn, которая ссылается на возвращенную функцию, переменная numberOfCalls будет удалена сборщиком мусора.
Perl[править]
Пример с использованием замыканий на Perl:
# возвращает анонимную функцию
sub adder($) {
my $x = shift(); # в котором x - свободная переменная,
return sub ($) {
my $y = shift(); # а y - связанная переменная
return $x + $y;
};
}
$add1 = adder(1); # делаем процедуру для прибавления 1
print $add1->(10); # печатает 11
$sub1 = adder(-1); # делаем процедуру для вычитания 1
print $sub1->(10); # печатает 9
Lua[править]
Пример с использованием замыканий на Lua:
function makeaddfunc(x)
-- Возвращает новую анонимную функцию, которая добавляет x к аргументу
return function(y)
-- Когда мы ссылаемся на переменную x, которая вне текущей области,
-- и время жизни которой меньше, чем этой анонимной функции,
-- Lua создаёт замыкание.
return x + y
end
end
plustwo = makeaddfunc(2)
print(plustwo(5)) -- Выводит 7
Haskell[править]
В Haskell замыкания используются повсеместно в виде частичного применения аргументов к функциям (также известного как каррирование).
sum3 :: Int -> Int -> Int -> Int
sum3 x y z = x + y + z
Определение функции «sum3» напоминает следующий код на C:
int sum3(int x, int y, int z)
{
return(x + y + z);
}
На самом деле «sum3» эквивалентна функции «sum3_desugared», по определению которой видно, что «sum3_desugared» принимает один аргумент «x» и возвращает новую функцию со связанной переменной «x». Новая функция также принимает только один аргумент «y» и возвращает функцию от одного аргумента «z».
sum3_desugared :: Int -> Int -> Int -> Int
sum3_desugared = \x -> \y -> \z -> x + y + z
Псевдоопределение таких функций выглядит следующим образом («bounded» — это некоторые фиксированные значения, которые неявно хранятся вместе с функциями):
sum2_closure :: Int -> Int -> Int
sum2_closure = \y -> \z -> bounded_from_sum3 + y + z
sum1_closure :: Int -> Int
sum1_closure = \z -> bounded_from_sum3 + bounded_from_sum2 + z
sum_value :: Int
sum_value = bounded_from_sum3 + bounded_from_sum2 + bounded_from_sum1
sum2_with42 = sum3 42
sum2_with42 = \y -> \z -> 42 + y + z
sum1_with42_with13 = sum3 42 13
sum1_with42_with13 = sum2_with42 13
sum1_with42_with13 = \z -> 42 + 13 + z
sum_with42_with13_with66 = sum3 42 13 66
sum_with42_with13_with66 = sum2_with42 13 66
sum_with42_with13_with66 = sum1_with42_with13 66
sum_with42_with13_with66 = 42 + 13 + 66
Такой подход очень часто применяется для создания «специализированных» функций из более общих:
-- (&&) :: Bool -> Bool -> Bool
-- liftM2 :: (Monad m) => (a -> b -> c) -> m a -> m b -> m c
(<&&>) (Monad m) => m Bool -> m Bool -> m Bool
(<&&>) = liftM2 (&&)
-- foldr :: (a -> b -> b) -> b -> [a] -> b
custom_fold :: [a] -> b
custom_fold = foldr k z
where
z = {- zero value -}
k x z = {- combining function -}
Для удобства использования общих функций рекомендуют располагать в них параметры в порядке от общих к частным. Например, сначала принимать функцию-обработчик перед самими данными.
Smalltalk[править]
Пример с использованием замыкания на Smalltalk:
createClosureWithComparator: aComparator
^[ :each | ^ each < aComparator ]
Выполнение метода создает замыкание, при использовании которого будет происходить сравнение произвольного аргумента each и связанного значения aComparator.
MATLAB[править]
Пример реализации замыкания в MATLAB с использованием вложенных функций:
function d = some_func(a)
function c = nested_func(b)
c = a + b;
end
d = @nested_func;
end
>> f = some_func(10);
f =
@some_func/nested_func
>> f(5)
ans =
15
Пример реализации замыкания в MATLAB с использованием анонимных функций:
>> f = @(x) @(y) x + y
f =
@(x)@(y)x+y
>> ff = f(10)
ff =
@(y)x+y
>> ff(5)
ans =
15
Objective-C[править]
Пример реализации замыкания в Objective-c с использованием блоков (blocks):
typedef int (^Add)();
- (Add)addFunction
{
__block int i = 0;
Add block = ^{
return i++;
};
return block;
}
int main(int argc, char * argv[])
{
Add block = [self addFunction];
NSLog(@"%i", block());
NSLog(@"%i", block());
NSLog(@"%i", block());
}
>>0
>>1
>>2
Common LISP[править]
(defun photon-energy-common (planck)
(lambda (freq)
(* planck freq)))
(setq photon-energy-hbar (photon-energy-common 1.054571726E-23))
(setq photon-energy-h (photon-energy-common 6.62606957E-23))
(funcall photon-energy-h 10E12)
Go[править]
package main
import "fmt"
func fibonacci() func() int {
a, b := 0, 1
return func() int {
a, b = b, a + b
return b
}
}
func main() {
f := fibonacci()
for i := 0; i < 10; i++ {
fmt.Println(f())
}
}
Visual Prolog[править]
F = {(Y) = {(X)=X+Y}},
G = F(2),
write(G(3)), % 5
write(G(8)) % 10
Swift[править]
// Вариант 1
reversed = sorted(names, { (s1: String, s2: String) -> Bool in
return s1 > s2
})
// Вариант 2
reversed = sorted(names, { (s1: String, s2: String) -> Bool in return s1 > s2 } )
// Вариант 3
reversed = sorted(names, { s1, s2 in return s1 > s2 } )
// Вариант 4
reversed = sorted(names, { s1, s2 in s1 > s2 } )
// Вариант 5
reversed = sorted(names, { $0 > $1 } )
// Вариант 6
reversed = sorted(names) { $0 > $1 }
Примечания[править]
- ↑ OCaml Closures and Currying. CMSC 330, Summer 2009