Using closures and higher-order functions in Delphi
This article is a continuation of the previous publication , which was devoted to anonymous methods. This time we will discuss examples of the use of higher-order functions and closures that seemed interesting to the author.
Delphi is not a functional programming language, but the fact that programs on it can manipulate functions as objects means that you can use the techniques of the functional paradigm in Delphi. The purpose of the article is not to push to use this style, but to identify some examples and possibilities.
Higher-order functions (FVPs) are functions that operate on functions, taking one or more functions, and returning a new function.
The following example shows how other functions can be constructed with the help of an AFP.
The Negate function in the example above is a FER, because it takes the function IsOdd as an argument and returns a new function IsEven, which passes its arguments to Negate and returns a logical negation of the value returned by the function IsOdd.
')
Since the use of generic types does not contribute to clarity of presentation, in the following examples we will avoid them if possible.
Below is an example of another, more universal function that takes two functions, F and G, and returns a new function that returns the result F (G ()).
Here, the Compose function calculates F (G (X, Y)). The returned function passes all its arguments to the function G, then passes the value received from G to function F and returns the result of calling F.
This term describes the conversion of a function with several arguments to a function that takes a smaller number of arguments, with the values ​​for the omitted arguments set in advance. This technique is quite adequate to its name: it "partially applies" some of the arguments of the function, returning a function that takes the remaining arguments.
In the example below, the BindLeft function takes a Calc function that takes n arguments, connects the first k of them with pre-specified values, and returns a Partial function that can take (nk) arguments (the first k arguments will already be applied to it).
Here the moment is interesting when, after a call to BindLeft, the local variable StoredArgs does not cease to exist and is used further, keeping in itself the values ​​of the arguments, which are then used in the call to Partial and passed to Calc. This effect is called closure. In addition, each call to BindLeft will generate new “instances” of StoredArgs. Closures were also used in the previous examples, when the arguments of the PID were stored in them.
Partial application on the right can be determined as follows:
While partial application converts a function with n parameters into a function with nk parameters, applying k arguments, currying decomposes the function into functions from a single argument. We do not pass any additional arguments to the Curry method, except for the function being converted:
Memoisated function is a function that stores previously calculated results. In other words, a result table is created for the function, and, being calculated for certain values ​​of parameters, the result is recorded in this table. In the future, the result is taken from this table. This technique allows using the additional memory to speed up the program. Of course, the function to be memorized must work without side effects and it is desirable for it to have a discrete domain of definition.
The following example demonstrates the higher-order Memoize function, which takes a function as an argument and returns its memoized version.
The Memoize function creates a TCache object for use as a cache and assigns it to a local variable, so that it remains available (through a closure) only for the returned function. The returned function converts its argument to the key. If the value is present in the cache, it is simply returned as a result. Otherwise, the original function is called, which calculates the value for the given argument; The resulting value is cached and returned.
A program with a memosized function that is periodically called with the same arguments must run faster than a similar program without the use of memoization. Check the difference:
Here, a generator is understood as a FER, which returns a function, the call of which results in the next member of some sequence. In the example below, two generators are created: for the Fibonacci sequence and factorial generator. The previous elements of the generators are stored in the circuit.
The advantage of generators is that to calculate each next element it is not required to calculate the entire sequence from the very beginning. Generators allow you to work even with infinite sequences, but they provide only sequential access to their elements and do not allow you to access your elements by index: to get ne value you have to perform n-1 iterations.
Generators can be conveniently used for sequential processing of data - elements of a list, strings of text, lexemes in a lexical analyzer, etc. Generators can be chained together, like a command pipeline to Unix. The most interesting thing about this approach is that it follows the principle of deferred calculations : the values ​​are “extracted” from the generator (or from the conveyor) as needed, and not all at once. This feature is demonstrated by the following example, in which the source text is filtered, passing line by line through a chain of generators.
The source for the article can be downloaded here.
Delphi is not a functional programming language, but the fact that programs on it can manipulate functions as objects means that you can use the techniques of the functional paradigm in Delphi. The purpose of the article is not to push to use this style, but to identify some examples and possibilities.
Construction of functions
Higher-order functions (FVPs) are functions that operate on functions, taking one or more functions, and returning a new function.
The following example shows how other functions can be constructed with the help of an AFP.
type TRef<AT, RT> = reference to function(X: AT): RT; var Negate: TRef<TRef<Integer, Boolean>, TRef<Integer, Boolean>>; IsOdd, IsEven: TRef<Integer, Boolean>; begin // , IsOdd := function(X: Integer): Boolean begin Result := X mod 2 <> 0; end; // Negate := function(F: TRef<Integer, Boolean>): TRef<Integer, Boolean> begin Result := function(X: Integer): Boolean begin Result := not F(X); end; end; // IsEven := Negate(IsOdd); WriteLn(IsOdd(4)); // => False WriteLn(IsEven(4)); // => True end; The Negate function in the example above is a FER, because it takes the function IsOdd as an argument and returns a new function IsEven, which passes its arguments to Negate and returns a logical negation of the value returned by the function IsOdd.
')
Since the use of generic types does not contribute to clarity of presentation, in the following examples we will avoid them if possible.
Composition of functions
Below is an example of another, more universal function that takes two functions, F and G, and returns a new function that returns the result 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; Here, the Compose function calculates F (G (X, Y)). The returned function passes all its arguments to the function G, then passes the value received from G to function F and returns the result of calling F.
Partial application
This term describes the conversion of a function with several arguments to a function that takes a smaller number of arguments, with the values ​​for the omitted arguments set in advance. This technique is quite adequate to its name: it "partially applies" some of the arguments of the function, returning a function that takes the remaining arguments.
In the example below, the BindLeft function takes a Calc function that takes n arguments, connects the first k of them with pre-specified values, and returns a Partial function that can take (nk) arguments (the first k arguments will already be applied to it).
type TManyArgRef = reference to function(Args: TArray<Double>): Double; TBindRef = reference to function(Args: TArray<Double>; F: TManyArgRef): TManyArgRef; var BindLeft: TBindRef; Calc, Partial: TManyArgRef; begin // , Args // F . BindLeft := function(Args: TArray<Double>; F: TManyArgRef): TManyArgRef var StoredArgs: TArray<Double>; begin StoredArgs := Args; Result := function(Args: TArray<Double>): Double begin Result := F(StoredArgs + Args); end; end; // // Calc := function(A: TArray<Double>): Double begin Result := A[0] * (A[1] - A[2]); end; // Partial := BindLeft([2, 3], Calc); // WriteLn(Partial([4])); // => -2.0 // Partial Calc([2, 3, 4]) end; Here the moment is interesting when, after a call to BindLeft, the local variable StoredArgs does not cease to exist and is used further, keeping in itself the values ​​of the arguments, which are then used in the call to Partial and passed to Calc. This effect is called closure. In addition, each call to BindLeft will generate new “instances” of StoredArgs. Closures were also used in the previous examples, when the arguments of the PID were stored in them.
Partial application on the right can be determined as follows:
BindRight := function(Args: TArray<Double>; F: TManyArgRef): TManyArgRef var StoredArgs: TArray<Double>; begin StoredArgs := Args; Result := function(Args: TArray<Double>): Double begin Result := F(Args + StoredArgs); // end; end; Carring
While partial application converts a function with n parameters into a function with nk parameters, applying k arguments, currying decomposes the function into functions from a single argument. We do not pass any additional arguments to the Curry method, except for the function being converted:
- Curry (F) returns a function F1, such that ...
- F1 (A) returns the function F2, such that ...
- F2 (B) returns a function F3, such that ...
- F3 (C) causes F (A, B, C)
type TOneArgRef = reference to function(X: Double): Double; TThreeArgRef = reference to function(X, Y, Z: Double): Double; TSecondStepRef = reference to function(X: Double): TOneArgRef; TFirstStepRef = reference to function(X: Double): TSecondStepRef; TCurryRef = reference to function(F: TThreeArgRef): TFirstStepRef; var Curry: TCurryRef; Calc: TThreeArgRef; F1: TFirstStepRef; F2: TSecondStepRef; F3: TOneArgRef; Re: Double; begin // Curry := function(F: TThreeArgRef): TFirstStepRef begin Result := function(A: Double): TSecondStepRef begin Result := function(B: Double): TOneArgRef begin Result := function(C: Double): Double begin Result := F(A, B, C); end; end; end; end; // , // 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; Slightly more compact looks like a generalized version of Curry.
type TRef<AT, RT> = reference to function(Args: AT): RT; TCalc<T> = reference to function(X, Y, Z: T): T; var Curry: TRef<TCalc<Double>,TRef<Double,TRef<Double,TRef<Double,Double>>>>; Calc: TCalc<Double>; begin // Curry := function(F: TCalc<Double>): TRef<Double,TRef<Double,TRef<Double,Double>>> begin Result := function(A: Double): TRef<Double,TRef<Double,Double>> begin Result := function(B: Double): TRef<Double,Double> begin Result := function(C: Double): Double begin Result := F(A, B, C); end; end; end; end; // Calc := function(A, B, C: Double): Double begin Result := A + B + C; end; // WriteLn(Curry(Calc)(1)(2)(3)); // => 6.0 end; Memoization
Memoisated function is a function that stores previously calculated results. In other words, a result table is created for the function, and, being calculated for certain values ​​of parameters, the result is recorded in this table. In the future, the result is taken from this table. This technique allows using the additional memory to speed up the program. Of course, the function to be memorized must work without side effects and it is desirable for it to have a discrete domain of definition.
The following example demonstrates the higher-order Memoize function, which takes a function as an argument and returns its memoized version.
type TRef = reference to function(X: Integer): Double; TMemoize = reference to function(F: TRef): TRef; var Memoize: TMemoize; Calc: TRef; MemoizedCalc: TRef; begin // Memoize Memoize := function(F: TRef): TRef var Cache: ICache<Integer, Double>; begin Cache := TCache<Integer, Double>.Create; Result := function(X: Integer): Double begin // ... if not Cache.TryGetValue(X, Result) then begin Result := F(X); // ... Cache.Add(X, Result); // end; end; end; // , 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; The Memoize function creates a TCache object for use as a cache and assigns it to a local variable, so that it remains available (through a closure) only for the returned function. The returned function converts its argument to the key. If the value is present in the cache, it is simply returned as a result. Otherwise, the original function is called, which calculates the value for the given argument; The resulting value is cached and returned.
Cache implementation
interface uses Generics.Collections; type // ICache<TKey, TValue> = interface function TryGetValue(Key: TKey; out Value: TValue): Boolean; procedure Add(Key: TKey; Value: TValue); end; TCache<TKey, TValue> = class(TInterfacedObject, ICache<TKey, TValue>) private FDictionary: TDictionary<TKey, TValue>; public constructor Create; destructor Destroy; override; function TryGetValue(Key: TKey; out Value: TValue): Boolean; procedure Add(Key: TKey; Value: TValue); end; implementation constructor TCache<TKey, TValue>.Create; begin FDictionary := TDictionary<TKey, TValue>.Create; end; destructor TCache<TKey, TValue>.Destroy; begin FDictionary.Free; inherited; end; procedure TCache<TKey, TValue>.Add(Key: TKey; Value: TValue); begin FDictionary.Add(Key, Value); end; function TCache<TKey, TValue>.TryGetValue(Key: TKey; out Value: TValue): Boolean; begin Result := FDictionary.TryGetValue(Key, Value); end; A program with a memosized function that is periodically called with the same arguments must run faster than a similar program without the use of memoization. Check the difference:
uses SysUtils, DateUtils; var I: Integer; Time: TDateTime; Ms1, Ms2: Int64; Res1, Res2: Double; begin Res1 := 0; Res2 := 0; // Time := Now; for I := 1 to 1000 do Res1 := Res1 + Calc(I mod 100); Ms1 := MilliSecondsBetween(Now, Time); // 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; Generators
Here, a generator is understood as a FER, which returns a function, the call of which results in the next member of some sequence. In the example below, two generators are created: for the Fibonacci sequence and factorial generator. The previous elements of the generators are stored in the circuit.
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; The advantage of generators is that to calculate each next element it is not required to calculate the entire sequence from the very beginning. Generators allow you to work even with infinite sequences, but they provide only sequential access to their elements and do not allow you to access your elements by index: to get ne value you have to perform n-1 iterations.
Deferred calculations
Generators can be conveniently used for sequential processing of data - elements of a list, strings of text, lexemes in a lexical analyzer, etc. Generators can be chained together, like a command pipeline to Unix. The most interesting thing about this approach is that it follows the principle of deferred calculations : the values ​​are “extracted” from the generator (or from the conveyor) as needed, and not all at once. This feature is demonstrated by the following example, in which the source text is filtered, passing line by line through a chain of generators.
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; The source for the article can be downloaded here.
Source: https://habr.com/ru/post/244945/
All Articles