Реализации алгоритмов/Замыкание

Замыкание (англ. 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):

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