Замыкания: расшифровка

Персональный блог одноименного форумчанина. Человека и парохода, не побоюсь этого сравнения :)

Модератор: tyomitch

tyomitch
Пользователь #1352
Пользователь #1352
Аватара пользователя
 
Сообщения: 12822
Зарегистрирован: 20.10.2002 (Вс) 17:02
Откуда: חיפה

Замыкания: расшифровка

Сообщение tyomitch » 16.06.2006 (Пт) 16:23

Получил комментарий, что в моём коде, иллюстрирующем моё понимание преимуществ ФП на примере перлового синтаксиса, "ничего не понятно вообще. То есть совсем. Только верить объяснениям на слово остаётся." Поясню.

* Замыкания -- это функции, чьи статические локальные переменные связываются (т.е. ассоциируются с конкретными адресами памяти) на этапе выполнения. Замыкания в ФП можно уподобить виртуальным методам в ООП: что именно будет вызываться, неизвестно до тех пор, пока оно не вызовется.

Замыкания позволяют создавать экземпляры функций, отличающиеся привязкой их переменных; при создании эклемпляра функция замыкается на конкретные переменные. Каждый такой экземпляр -- как будто бы объект с одним методом; но синтаксис замыканий позволяет работать с ними проще, чем с настоящими объектами. Замыкания есть в C# 2.0, и там они компилируются именно в невидимые классы с одним методом.

Таким образом, взаимоотношения между ФП и ООП такие же, как между ООП и процедурным программированием: первый член каждой пары можно достаточно прозрачно реализовать в рамках второго, потеряв при этом синтаксическое удобство более прогрессивного подхода.

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


* Теперь рассмотрим конкретные примеры. Я пользуюсь синтаксисом Перла как единственного доступного мне языка с поддержкой замыканий; у этого синтаксиса есть ряд неочевидных с первого взгляда особенностей. Типов нет. Функция объявляется ключевым словом sub, и её возвращаемое значение соответствует значению последнего вычисленного выражения. Список параметров, передаваемых в функцию, доступен под именем @_. Первый символ имени указывает на его сущность: $scalar, %hash, @list, &sub. Хеш ("ассоциативный массив", аналог коллекции) и список (аналог обычного одномерного массива) могут содержать только скаляры; частным случаем скаляра является ссылка. Можно создавать ссылки на объекты любого рода. Определённые комбинации символов имеют собственный смысл: $#list -- индекс последнего элемента списка; $ref-> -- разыменование ссылки; &$ref -- вызов функции по ссылке, это синоним для $ref->(). Индекс списка указывается в квадратных скобках, ключ хеша -- в фигурных. Локальные переменные функции объявляются ключевым словом my.

* Вот первый пример:
Код: Выделить всё
#  Объявляется функция с именем iterator
sub iterator {
#  Локальные переменные: список @array, инициализируемый списком
#  переданных параметров, и скаляр $index, инициализируемый значением 0
  my @array=@_, $index=0;
#  Это последнее выражение в функции iterator, поэтому его значение будет
#  возвращено из функции. Само значение -- ссылка на безымянную функцию,
#  замкнутую на переменные @array и $index и не имеющую собственных
#  локальных переменных.
  sub { $index>$#array? undef: $array[$index++]; }
#  Тело возвращаемой функции: "если мы вышли за границы списка @array,
#  вернуть undef, иначе вернуть текущий элемент и увеличить индекс."
}


#  Вызывается функция iterator со списком параметров (1,2,"moo").
#  Возвращаемое значение (ссылка на функцию) сохраняется в $i.
$i = iterator(1,2,"moo");
#  В цикле вызывается возвращённая нам функция, и возвращённое ей
#  значение сохраняется в $next.
while (defined($next=&$i)) { print $next; }
#  Пока эта функция не вернёт undef, будет печататься возвращаемое
#  ей значение.


* Второй пример:
Код: Выделить всё
#  Функция mysort первый принятый параметр сохраняет в $key, а все
#  остальные -- в @array. Вызывать её можно так: mysort("foo",@myarray);
#  Мы полагаем, что переданный массив содержит ссылки на хеши (структур
#  в перле нет).
sub mysort {
  my ($key,@array)=@_;
#  Предположим, что у нас есть функция qsort, принимающая первым
#  параметром сравнивающую функцию, а затем сортируемый список.
#  $a <=> $b означает то же, что $a==$b?0:$a<$b?-1:1
  qsort (sub { my($a,$b)=@_; ($a->{$key})<=>($b->{$key}); }, @array);
#  Передаваемая первым параметром в qsort безымянная функция замыкается
#  на $key, и имеет две локальные переменные: $a и $b, инициализируемые
#  переданными в эту функцию параметрами.  Возвращаемое ей значение --
#  результат сравнения $a->{$key} и $b->{$key}
}


* Последний пример:
Код: Выделить всё
#  Функция new сохраняет два первых переданных в неё параметра в $a и $b
sub new {
#  В данном контексте, фигурные скобки задают литерал типа "ссылка на
#  хеш". Слева от оператора => идут ключи хеша, справа -- соответствующие
#  значения. Синонимом было бы {"add", sub{$a+$b}, "sub", sub{$a-$b},
#  и т.д.} -- но оператор => автоматически "закавычивает" ключи.
  my($a,$b)=@_; {
#  Каждое значение в нашем хеше -- ссылка на функцию, замкнутую на $a и $b
  add => sub { $a+$b; },
  sub => sub { $a-$b; },
#  Это процедуры свойств. Если передан параметр, то он считается новым
#  значением свойства, иначе возвращается старое значение свойства.
#  Ключевое слово shift возвращает первый элемент из списка @_, и удаляет
#  его оттуда, сдвигая список. Вместо него можно было использовать $_[0]
  a   => sub { @_? $a=shift: $a },
  b   => sub { @_? $b=shift: $b }
}}

# Создание "объекта": в $obj записывается ссылка на созданный хеш.
# Функцию new можно вызывать и без параметров, тогда поля нашего объекта
# не будут инициализированы.
$obj =new(1,2);
# Разыменовываем ссылку на хеш, извлекаем из него элемент по ключу "add",
# и используем его как ссылку на функцию.
print &{$obj->{add}};
# Поступаем аналогично с процедурой свойства "a". Поскольку параметры не
# передаются, печатается старое значение свойства.
print &{$obj->{a}};
# Вызываем процедуру свойства "b", пользуясь альтернативным синтаксисом.
# Переданный параметр записывается в свойство.
$obj->{b}->(4);
# Тут можно было бы написать print $obj->{sub}->();
print &{$obj->{sub}};




Рассчитываю на поток аргументированной критики данного подхода.
Изображение

tyomitch
Пользователь #1352
Пользователь #1352
Аватара пользователя
 
Сообщения: 12822
Зарегистрирован: 20.10.2002 (Вс) 17:02
Откуда: חיפה

Сообщение tyomitch » 17.06.2006 (Сб) 0:25

Дописка

Замыкания -- не "основа" ФП; это способ привнести функциональный подход в привычное (объектное ли, процедурное ли) программирование.

В "истинно функциональном" языке нет переменных, значит и замыкаться функциям не на что. Хотя частный случай замыкания -- срез функции (фиксирование некоторых из её аргументов, получая функцию с меньшим числом аргументов), или "замыкание на константу", -- в таком "истинно функциональном" языке является одной из конструкций языка.

(К слову, без виртуальных методов в ООП тоже можно обойтись -- хоть и криво, но получится.)

В "истинно функциональном" языке единственная операция над функциями -- их композиция, и функция main() тоже расписывается как некоторая (возможно, циклическая) композиция элементарных функций. Программа на таком языке -- это просто перечень объявлений составляющих её функций, в произвольном порядке.

Таким образом, программа на "истинно функциональном" языке определяет лишь шаги на пути к решению задачи, а последовательность их применения и количество применений каждого шага определяет компилятор. Это помещает "чистое ФП" посередине между традиционным, императивным программированием -- и декларативным программированием, при котором программист описывает только условие задачи, а решение полностью составляется компилятором.

Очень много прикладных задач нельзя описать в терминах чистого, stateless ФП: даже вывод на экран непонятно как организовывать, если функции могут выполняться в произвольном порядке. Поэтому во всех практических реализациях ФП либо строго оговаривается порядок выполнения функций (таков наиболее чистый из функциональных языков, Unlambda), превращая язык в императивный, либо добавляются объекты-состояния наподобие семафоров (таков наиболее популярный из функциональных языков, Haskell), превращая язык в неполностью функциональный.

Хотя такие попытки "починить" ФП, добавляя в него элементы традиционного программирования, и пользуются определённым успехом, мне более продуктивными кажутся попытки движения в противоположном направлении -- "починка" ООП добавлением в него элементов ФП. Как показывает история, многие ОО-языки движутся именно в этом направлении.


-----
Наконец, хотелось бы отвязать ФП от Перла, использованного мной для примеров кода. Перл -- не функциональный язык, хотя элементы ФП в нём есть. Ещё Перл -- не объектный язык, хотя элементы ООП в нём есть. Перл -- даже не структурный язык, хотя при желании на нём можно писать и структурные программы. Ни в коем случае нельзя рассматривать недостатки Перла как недостатки ФП, и наоборот.
Изображение


Вернуться в Tyomitch

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 10

    TopList