Функциональное программирование 3 - лямбда функции и замыкания

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

В C# разных версий лямбды эволюционировали до современного вида, пожалуй самого удобного из всех известных мне вариантов.

int[] ary = { 1, 2, 3 };
var x = 2;
var ary1 = ary.Select(elem => elem * x;);


Выражение "elem => elem*x" - типичная лямбда-функция. В нем до оператора => перечисляется список аргументов, после - собственно выражение, результат вычисления которого является возвращаемым значениям лямбды. Все лямбды передаются как делегаты.

В других языках синтаксис лямбд более громоздкий. Обычно используется ключевое слово типа function, lambda и т.д., после которого указывается список аргументов, а затем - тело функции. В C# роль определяющего ключевого слова играет оператор =>.

В данном примере лямбда-функции есть еще одна интересная особенность:  лямбда ссылается на локальную переменную x, объявленную вне самой лямбды. Такие функции называются замыканиями.

В общем случае замыкание — это функция, определенная в теле другой функции (т.е. не только лямбда, но и просто обычная вложенная функция). При этом вложенная внутренняя функция содержит ссылки на локальные переменные внешней функции.

Интересно, что вложенные функции существовали еще во времена Turbo Pascal. Уже тогда вложенные функции имели доступ к локальным переменным объемлющих функций (т.е. они как-бы являлись замыканиями), и были доступны только внутри объемлющих функций. Их реализация была довольно простой, потому что в Паскале не было делегатов. Дело в том, что с делегатами и замыканиями связана одна особенность: за счет делегатов вложенная функция может иметь время жизни дольше, чем объемлющая. Такое может быть, например, если объемлющая функция возвращает вложенную как результат своей работы.

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

Функциональное программирование 2 - о синтаксисе

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

Рассмотрим передачу делегатов в функции.

В C#, прежде чем использовать делегат как аргумент функции, нужно сначала объявить тип делегата. Например так:

delegate int MyDelegate(string s);

Здесь MyDelegate - тип, значениями которого могут быть любые методы, принимающие string и возвращающие int. Использовать его можно например так:

public void Process( MyDelegate  func)
{
    foreach (string s in someList)
    {
       func(b);
    }
}

В D тип делегата можно не объявлять, а объявлять прямо по месту использования.
int foo(int delegate(int x) dg)
{
    return dg(10) + 1;
}

В ObjC 2.0 существует аналогичное понятие "блоки". Подобно C# (и Си) можно определить тип блока (очень похоже на указатель на функцию):

typedef void (^MyBlock)(int);

Хотя можно определять блок и без типа. Например, функция  logBlock в качестве аргумента принимает другую функцию, принимающую int и возвращаюшую NSString*

void logBlock( NSString * ( ^theBlock )( int ) )
{
    NSLog( @"Block returned: %@", theBlock() );
}

В скриптовых языках все несколько проще. Объявлять типы не надо (так как это языки как правило с динамической типизацией).

function foo( callback )
{
    alert( callback() );
}
function bar()
{
    var str = 'hello, world';
    foo ( function() { return str; } );
}
bar();

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

Во всех рассмотренных случаях (а можно рассматривать и другие языки) построение делегата достаточно громоздко и неудобно. Фактически, эти варианты мало чем отличаются от синтаксиса обычных указателей на функции, с их нагромождением скобок. Между тем, существуют и более компактные варианты. Например, Nemerle:

public static void Sort[T](ary : array[T], comparison : T * T -> int);

или Scala:

def sum(f: Int => Int, a: Int, b: Int): Int

В обоих примерах тип делегата задавался максимально просто и естестенно: "список входных параметров", "стрелочка", "список возвращаемых параметров". Ничего лишнего, все максимально наглядно и прозрачно. Именно такой вариант синтаксиса и взят за основу в Neo.



Функциональное программирование 1 - функциональные типы

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

Простейшим ФТ является указатель на функцию. Указатели на функцию существуют в языке Си. Их синтаксис таков:
int (*pfunc)(float f);
Внутри такого объявления описывается имя переменной (pfunc), тип возвращаемого значения и аргументы ФТ. В принципе, этого могло бы быть достаточно, так как таким способом можно передать любую функцию. Но во многих случаях это бывает неудобно. Собственно, удобство - как раз то, из-за чего и появлились языки высокого уровня всесто Ассемблера.

Часто вместе с функцией хочется передать некоторые аргументы этой фунцкии.
Наиболее частый случай - функция является методом класса. Любой нестатический метод имеет один неявный аргумент, традиционно называемый "this". Это указатель (ссылка) на объект того класса, от которого вызывается метод. Указатель на функцию - это чистый адрес функции, места для каких-либо аргументов там нет. Для того, чтобы передать вместе с указателем еще и аргумент, вводится понятие "делегат".

Термин "делегат" возник в C# (хотя там понятие немного расширено - в C# это список указателей на функции с аргументами this). Я считаю, что список - это список, а разработчики C# немного намудрили. В языке D, к примеру, делегат - это именно одиночное значение.

Формально, делегаты могут быть указателями на глобальные функции (если они поддерживаются ЯП), статические методы или на нестатические методы классов. То есть это структуры данных, имеющие поле - указатель на функцию, и поле для указателя this. Что интересно, в C++ Builder какой-то довольно старой версии появилось ключевое слово __closure, с помощью которого можно было создавать как раз такие объекты.

Но не всегда передачи одного this достаточно. В самом деле, чем указатель this отличается от других параметров? Что делать, если хочется сохранить вместе с указателем на функцию и часть обычных параметров этой функции? В функциональном программировании это называется "частичное применение": когда новая функция создается на основе существующей путем частичного указания аргументов. Самое интересное, что такое можно сделать и на старом добром Си, просто определив новую функцию, которая вызывает старую:

int Sum(int x, int y) { return x+y; }
int Inc(int x) { return Sum(x,1); }

Но интересный вопрос - почему-бы не сделать такое с помощью делегатов?
Если пользоваться терминологией C#/D, то такие объекты уже правильнее называть именно "функциональными объектами". Они действительно полноценные объекты ООП - имеют поля (указатель на функцию и поля, которые нужно передать в качестве аргументов этой функции). Теоретически, они могут иметь собственные методы, т.е. функциональные типы могут являться полноценными классами. Здесь они пересекаются с функторами - классами, у которых переопределен оператор "круглые скобки" (). За счет этого с такими объектами можно работать как с обычными функциями.

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

О синтаксисе

Каким должен быть синтаксис языка программирования?
Я считаю, что синтаксис должен быть кратким, чистым и си-подобным.

Краткость - это удобство программирования. Программы с длинными ключевыми словами и многословными конструкциями выглядят тяжело и неподъемно. В большинстве случаев программист знает, что он хочет написать, и заставлять его набивать текст  не есть хорошо (даже в современных IDE с автодополнением!).

Чистота синтаксиса - это особое, плохо формализуемое свойство, которое, тем ни менее, можно выразить так: все конструкции языка подчиняются небольшому, компактному набору "правил"; изучив одну конструкцию, можно предположить, как должна выгдядеть другая, подобная ей. Не должно быть исключений. Например, в Си аргументы операторов заключаются в круглые скобки. Это правило едино для всех операторов: if, for, while, switch, catch. Если в далеком будущем, в какой-то новой версии С++ появится еще какой-нибудь оператор, можно быть уверенным, что его аргументы будут заключены именно в круглые скобки.

Си-подобие - это своего рода стандарт де-факто. Думаю, больше 90% кода - т.е. код на самых распространенных языках, таких как C, C++, C#, Java, Objective C, PHP, Perl, JavaScript - построены на си-подобном синтаксисе.


Цели проекта Neo - 2

Продолжу о целях.
Первое - разработка своего собственного языка программирования. Задача сама по себе крайне интересная и непростая (даже без разработки компилятора). И, что самое главное, включающая в себя очень большую и важную подзадачу - исследование и изучение множества других языков программирования.

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

Третье - изучение проектирования компиляторов и разработка собственного компилятора. Здесь сразу две подзадачи: во-первых, в процессе разработки компилятора (как и любого другого проекта, кстати) возникают идеи по улучшению самого языка; во-вторых, в будущем имеет смысл переписать компилятор на свой собственный язык (http://en.wikipedia.org/wiki/Bootstrapping).

К числу других задач относятся - изучение "стандартных библиотек" и "фреймворков" (таких как STL, MFC, VCL, QT, Java, .NET) и попытка выделить из них нечто "самое лучшее". Исследование и сравнение фреймворков - также интересная тема, которой я почти не касался.

Цели проекта Neo

Когда я попытался сформулировать цели данного проекта, в голову пришло интересное определение: создать современный продвинутый язык для старого доброго программирования.

Что такое "старое доброе программирование"?
На самом деле, у каждого это что-то свое. Возможно, то, с чего программист начинал свой путь. Или то, в чем удалось достичь наиболее выдающихся результатов. Или что-то еще. Но, в любом случае, это то, чем приятно заниматься.

Итак, что бы я хотел создать:
1. Это язык в том числе и для системного программирования. Т.е. включающий в себя достаточно низкоуровневые возможности.
2. Это максимально си-подобный язык. Несмотря на множества различных синтаксисов, сишный мне как-то ближе. Да и большинству программистов, думаю, тоже.
3. Это язык, компилируемый в машинный код. Точнее, в машинные коды - под множество различных аппаратных и системных платформ.  Я с интересом изучаю современные скриптовые языки, но это не то, что бы я хотел создать. И это не фреймворк типа .NET или Java.
4. Это не академическая разработка, а скорее "хакерская". Я не ставлю целью "обезопасить" программиста от возможных ошибок, "научить" его чему-то... Но в то же время я не хочу, чтобы люди ломали мозг над чем-то сложным и непривычным. Это скорее попытка собрать и объединить все самое лучшее, что мне известно, учесть даже мельчайшие мелочи, на которые обычно мало обращают внимания. Сделать нечто идеальное:) ну или по крайней мере, стремящееся к идеалу.
Вот как-то так.


Немного истории

Идея написать свой язык программирования у меня есть уже давно. Можно сказать - с первого курса института, когда нам преподавали язык Си, и я невольно сравнивал его с уже известным мне из школы Паскалем. Тогда это были единственные языки, которые я знал, но уже тогда часто возникали мысли: "в Паскале это есть, а в Си нет... а вот если бы добавить такую возможность из Паскаля в Си!".
Затем появились Java, C#, Perl, PHP, Python и другие языки. На просторах интернета я находил и скачивал различную документацию по менее известным языкам - самым разным, например Ada, Sather, С--...
С самого начала и сейчас основным моим языком программирования является С++. Си-подобный синтаксис сразу понравился мне гораздо больше паскалевского (и, надо полагать, не только мне - практически все мейнстримовые языки имеют именно си-подобный синтаксис).

Сейчас за основу разработки я беру в первую очередь следующие языки
С,С++,C#,D,Java - основы основ. 90% синтаксических решений в той или иной степени взяты из этих языков.
Pascal, Delphi, а также Ada, Oberon, Modula - скорее как дань уважения, но кое-что интересное там есть; кроме того, в Ada есть языковая поддержка параллельности
ObjectiveC, Smalltalk - объектная модель "сообщений". В особенности мне нравится ObjC
Alef, Go - в связи с разработкой Гуглом нового языка обратил внимание и на его предшественников. Очень интересные решения в области параллельности, ну и синтаксические решения в Go очень даже ничего
Assemblers - да, кое что взял и из Ассемблера напрямую
Comega - экспериментальная разработка Microsoft, весьма интересная
Perl, PHP - тоже скорее дань уважения. Но кое что интересное там есть.
Python, Ruby - множество интересных решений в разных парадигмах программирования.
Scala, Nemerle - новые и весьма продвинутые языки. Nemerle - потрясающая система метапрограммирования, в которой, тем ни менее, меня далеко не все устраивает.