Использование замыканий и функций высших порядков в Delphi
Данная статья является продолжением предыдущей публикации, которая была посвящена анонимным методам. В этот раз речь пойдет о примерах использования функций высших порядков и замыканий, показавшихся автору интересными.Delphi не является языком функционального программирования, но тот факт, что программы на нем могут манипулировать функциями как объектами означает, что в Delphi можно использовать приемы функциональной парадигмы. Цель статьи — не подтолкнуть к использованию этого стиля, но обозначить некоторые примеры и возможности.Конструирование функцийФункции высшего порядка (ФВП) — это функции, которые оперируют функциями, принимая одну или более функций и возвращая новую функцию.Следующий пример показывает, как с помощью ФВП можно конструировать другие функции.
type
TRef
// Определим порождающую функцию
Negate:= function (F: TRef
// Теперь сконструируем новую функцию IsEven:= Negate (IsOdd);
WriteLn (IsOdd (4)); // => False WriteLn (IsEven (4)); // => True end; Функция Negate в примере выше, является ФВП, потому что она принимает функцию IsOdd в виде аргумента и возвращает новую функцию IsEven, которая передает свои аргументы Negate и возвращает логическое отрицание значения, возвращаемого функцией IsOdd.Так как использование обобщенных типов не способствует ясности изложения, в последующих примерах будем по возможности их избегать.
Композиция функций Ниже приводится пример еще одной, более универсальной функции, которая принимает две функции, F и G, и возвращает новую функцию, которая возвращает результат F (G ()). type TOneArgRef = reference to function (X: Single): Single; TTwoArgRef = reference to function (X, Y: Single): Single; TCompose = reference to function (F: TOneArgRef; G: TTwoArgRef): TTwoArgRef; var Compose: TCompose; Square: TOneArgRef; Half: TOneArgRef; Sum: TTwoArgRef; SquareOfSum: TTwoArgRef; HalfSum: TTwoArgRef; begin // Определим функцию высшего порядка «Композиция» Compose:= function (F: TOneArgRef; G: TTwoArgRef): TTwoArgRef begin Result:= function (X, Y: Single): Single begin Result:= F (G (X, Y)); end; end;
// Определим базовые функции: // 1. возвращает квадрат аргумента Square:= function (X: Single): Single begin Result:= X * X; end; // 2. Возвращает половину аргумента Half:= function (X: Single): Single begin Result:= X / 2; end; // 3. возвращает сумму двух аргументов Sum:= function (X, Y: Single): Single begin Result:= X + Y; end;
// Определяем композицию «квадрат суммы» SquareOfSum:= Compose (Square, Sum); // Определяем композицию «полусумма» HalfSum:= Compose (Half, Sum);
WriteLn (SquareOfSum (2.0, 3.0)); // => 25.0
WriteLn (HalfSum (3.0, 7.0)); // => 5.0
end;
Здесь функция Compose вычисляет F (G (X, Y)). Возвращаемая функция передает все свои аргументы функции G, затем передает значение, полученное от G, функции F и возвращает результат вызова F.Частичное применение
Этот термин описывает преобразование функции с несколькими аргументами в функцию, которая принимает меньшее количество аргументов, при этом значения для опущенных аргументов задаются заранее. Этот прием вполне адекватен своему названию: он «частично применяет» некоторые аргументы функции, возвращая функцию, принимающую остающиеся аргументы.Функция BindLeft в примере ниже берет функцию Calc, принимающую n аргументов, связывает первые k из них с наперед заданными значениями и возвращает функцию Partial, которая может принять (n-k) аргументов (первые k аргументов будут уже применены к ней).
type
TManyArgRef = reference to function (Args: TArray
// Функция принимает массив аргументов
// и выполняет произвольные вычисления
Calc:= function (A: TArray
// Частичное применение слева
Partial:= BindLeft ([2, 3], Calc); // Фиксируем первый и второй аргумент
WriteLn (Partial ([4])); // => -2.0
// Вызов Partial эквивалентен вызову Calc ([2, 3, 4])
end;
Здесь интересен момент, когда после вызова BindLeft локальная переменная StoredArgs не прекращает свое существование и используется далее, сохраняя в себе значения аргументов, которые потом используются при вызове Partial и передаются в Calc. Этот эффект называется замыканием. При этом каждый вызов BindLeft будет порождать новые «экземпляры» StoredArgs. Замыкания использовались и в предыдущих примерах, когда в них сохранялись аргументы ФВП.Определить частичное применение справа можно следующим образом:
BindRight:= function (Args: TArray
// Определим функцию от трех аргументов, // выполняющую произвольные вычисления Calc:= function (A, B, C: Double): Double begin Result:= A + B + C; end;
// Теперь вычислим значение функции Calc, используя карринг F1:= Curry (Calc); F2:= F1(1); F3:= F2(2); Re:= F3(3);
WriteLn (Re); // => 6.0
end;
Чуть более компактно выглядит обобщенный вариант Curry.
type
TRef
// Функция, производящая относительно долгие вычисления Calc:= function (X: Integer): Double var I: Integer; begin Result:= 0; for I:= 1 to High (Word) do Result:= Result + Ln (I) / Sin (I) * X; end;
// Мемоизованный вариант функции Calc MemoizedCalc:= Memoize (Calc); end; Функция Memoize создает объект TCache для использования в качестве кэша и присваивает его локальной переменной, благодаря чему он остается доступным (через замыкание) только для возвращаемой функции. Возвращаемая функция преобразует свой аргумент в ключ. Если значение присутствует в кэше, оно просто возвращается в качестве результата. В противном случае вызывается оригинальная функция, вычисляющая значение для заданного аргумента; полученное значение помещается в кэш и возвращается.Реализация кэша interface
uses Generics.Collections;
type
// Интерфейсная обертка для автоматического освобождения объекта
ICache
TCache
implementation
constructor TCache
destructor TCache
procedure TCache
function TCache
// После мемоизации Time:= Now; for I:= 1 to 1000 do Res2:= Res2 + MemoizedCalc (I mod 100); Ms2:= MilliSecondsBetween (Now, Time);
WriteLn (Res1 = Res2); // => True WriteLn (Ms1 > Ms2); // => True end; Генераторы Здесь под генератором понимается ФВП, которая возвращает функцию, вызов которой приводит к получению следующего члена некоторой последовательности. В примере ниже создаются два генератора: для последовательности Фибоначчи и генератор факториалов. Предыдущие элементы генераторов запоминаются в замыкании. type TRef = reference to function: Cardinal; TGenRef = reference to function: TRef; var FibGen, FactGen: TGenRef; FibVal, FactVal: TRef; I: Integer; begin // Функция-генератор, создающая последовательность чисел Фибоначчи FibGen:= function: TRef var X, Y: Cardinal; begin X:= 0; Y:= 1; Result:= function: Cardinal begin Result:= Y; Y:= X + Y; X:= Result; end; end;
// Функция-генератор, создающая последовательность факториалов FactGen:= function: TRef var X, Y: Cardinal; begin X:= 1; Y:= 1; Result:= function: Cardinal begin Result:= Y; Y:= Y * X; Inc (X); end; end;
// Вызов создающей функции-генератора и получение собственно генератора. // Тот редкий случай в Delphi, когда необходимо поставить круглые скобки. FibVal:= FibGen (); FactVal:= FactGen ();
for I:= 1 to 10 do WriteLn (FibVal, #9, FactVal); end; Польза генераторов заключается в том, что для вычисления каждого следующего элемента не требуется вычислять всю последовательность с самого начала. Генераторы позволяют работать даже с бесконечными последовательностями, но они обеспечивают только последовательный доступ к своим элементам и не позволяют обращаться к своим элементам по индексу: чтобы получить n-e значение придется выполнить n-1 итераций.
Отложенные вычисления Генераторы бывает удобно использовать для последовательной обработки данных — элементов списка, строк текста, лексем в лексическом анализаторе и т.д. Генераторы можно объединять в цепочки, подобно конвейеру команд в Unix. Самое интересное в этом подходе заключается в том, что он следует принципу отложенных вычислений: значения «извлекаются» из генератора (или из конвейера) по мере необходимости, а не все сразу. Эту особенность демонстрирует следующий пример, в котором исходный текст фильтруется, построчно проходя через цепочку генераторов. type TStringRef = reference to function: string; TEachLineRef = reference to function (S: string): TStringRef; TArgMap = reference to function (S: string): string; TMap = reference to function (A: TStringRef; F: TArgMap): TStringRef; TArgSelect = reference to function (S: string): Boolean; TSelect = reference to function (A: TStringRef; F: TArgSelect): TStringRef;
const // Исходный текст, который нужно фильтровать TEXT = '#comment ' + sLineBreak + '' + sLineBreak + ' hello' + sLineBreak + ' world ' + sLineBreak + ' quit ' + sLineBreak + ' unreached'; var EachLine: TEachLineRef; Map: TMap; Select: TSelect; Lines, Trimmed, Nonblank: TStringRef; S: string; begin // Генератор, возвращающий строки текста по одной. EachLine:= function (S: string): TStringRef begin Result:= function: string begin Result:= S.Substring (0, S.IndexOf (sLineBreak)); S:= S.Substring (S.IndexOf (sLineBreak) + 1); end; end;
// ФВП, возвращает функцию, результат которой — применение F к A Map:= function (A: TStringRef; F: TArgMap): TStringRef begin Result:= function: string begin Result:= F (A); end; end;
// Функция-генератор, возвращает значение A, если F (A) = True Select:= function (A: TStringRef; F: TArgSelect): TStringRef begin Result:= function: string begin repeat Result:= A; until F (Result); end; end;
// Сконструируем конвейер генераторов для обработки текста: // Сначала разбить текст на строки Lines:= EachLine (TEXT); // Затем удалить начальные и конечные пробелы в каждой строке Trimmed:= Map (Lines, function (S: string): string begin Result:= S.Trim; end); // Наконец, игнорировать пустые строки и комментарии Nonblank:= Select (Trimmed, function (S: string): Boolean begin Result:= (S.Length > 0) and (S[1] <> '#'); end); // Теперь извлечь отфильтрованные строки из конвейера и обработать их, // остановиться, если встретится строка 'quit' repeat S:= Nonblank; if S = 'quit' then Break; WriteLn (S); until False; end; Исходники к статье можно скачать здесь.
