Josip Zohil, Koper, Slovenija, August 2013
In functional programming languages (FP) lazy evaluation is a basic way to evaluate functions. In VFP there are two main fields where lazy evaluation matter: VFP Evaluate (and similar) function and SQL queries. Composing functions in lazy evaluation means composing amplified functions or actions. Let us present some examples to illustrate the methods and the problems in composing VFP actions.
The functions in VFP depend on data types but also from the order of evaluation:
Example 1. Normal (strict or eager) evaluation
G(x)=x+5
Z=G(x)**2,
We call these two functions for a value x=2 and get Z=49.
X=2, g(x)=7, z=49
We can compose the two functions in this way:
fc(x)=(x+1)**2.
Example 2. Lazy evaluation in SQL
X is a numeric field in a table test. Its value in the first record is 2 and in the second record is 3.
In VFP SQL we can pass functions as an argument with some restrictions. The next two queries don't generate correct results.
SELECT f(g(x)) as res
FROM test INTO CURSOR xxx
&&& 1->1 x->f(x)
This SQL computes g=2 (for x=1) and then ignore this value and computes f(1)=1**2=1, which is not correct.
SELECT f(x+1) as res
FROM test INTO CURSOR xxx
&&& 1->1 x->f(x)
Also this query doesn't behave in an expected way: instead of x+1 it takes x as the argument and returns f (1) =1.
SELECT (x+1)**2 as res
FROM test INTO CURSOR xxx
&&& 1->4 (Q1)
In this example the function (x+1)**2 is without name, we can call it an anonymous function.
SELECT
evaluate(»(x+1)**2«) as res FROM test INTO CURSOR xxx &&& 1->4
Sometimes we pass a function as an expression enclosed in quotation marks.
SELECT fc(x) as res
FROM test INTO CURSOR xxx
&&& 1->4
The last three queries behave in an expected way. The VFP engine »understand« this method of passing functions.
Example 3.
Use test
?s1(5) && 2
(1+1)
The function s1 ignores its argument and returns 2. It takes the value from the table. We shall explain this behavior (a VFP convention) later.
From this example we can pose a question: How to compose functions in a SQL query (especially complicated functions)?
The function fc(x)=(x+1)**2 in a query (Q1) is evaluated when the VFP SQL executes. For example, when the SQL computes the second record, it takes the value x from the table and call the function fc(x); it will be evaluated (»later«) on a second record, then (later) on the third and so on. This kind of evaluation is called lazy.
Let us study the VFP function evaluate. It is more than a function, it is a mapping. Its arguments are amplified functions in various forms and it returns values in a form of values (or functions). We frequently use this function in composing lazy evaluated functions.
The simplest way to pass functions is to use closures, for example:
Example 4.
Function f(x)
Return x**2
Endfunc
Function g() && a closure
?"x",x
Return x+1
Endfunc
We modify the function g(x):
Function glazy() && a closure
?"x",x
Return "x+1"
Endfunc
F(evaluate(glazy())) (A)
We pass a function glazy() as an expression to evaluate. This expression is similar to a string, but we have not said it is a string!!! It is simply an expression: a VFP function enclosed in quotation marks. The function f accepts as arguments also functions written in a special way:
1) Enclosed in quotation marks,
2) Using the function evaluate.
A construction (A) is only logic, no values. It is similar to the construction in SQL statements. We can compose functions in a similar way as SQL statements.
Note. Behind the scene SQL composition is based on compositions of »functions« of a special kind.
Will VFP understand this construction? How will execute it?
Now we can run them:
Example 5.
CLEAR
CLOSE data
X=4
gl=glazy() && give us a function enclosed in
quotation marks
gg=g(x) && returns 5, is evaluated here
? f(gg) && returns 25, for x=4
x=5
?F(EVALUATE(gl))
&& returns 36, for x=5, glazy is evaluated here
?f(gg) && returns 25, glazy is not evaluated
here
The function f(gg) takes a value x=4 and returns 25. If we call a function f on a lazy evaluated function glazy, it takes the value x=5 and compute 36.
The function glazy or the composition f(glazy()) is like an application, for example, we apply it on a value x=6:
X=6
? F(EVALUATE(g))
&& returns 49, for x=6, glazy is evaluated here
And the result is 49. It computes, when we give it a value. We call this kind of computation: on demand. You can manage »infinite« streams using lazy evaluation.
You can look at a function f(glazy()) as a macro command: you create a macro and use it in appropriate places. This "macro" command can be seen as a VFP language inside extension.
Many times in VFP we prefer to manipulate functions as anonymous (without names), for example:
f (»x+1«) or f(x+1) where a function x+1 is without name.
Usually, the expressions are more readable when written as anonymous functions.
In=5
Evaluate(5)
Give us an error, because evaluate is »lookig for« a function to evaluate.
The expression can be written as a function, for example:
Xexpr=«long expresion«
Function f()
Return xexpr
Endfunc
Eval(»f()«) =
eval(xexpr)
Inside the expressions there can be other functions composed in a correct way.
We call evaluate a function, but it is a mapping and not a function. A function maps a set (subset) of real numbers to a set (subset) of real numbers( F: R->R). In VFP, for example, a function g(x) maps a set of type numeric (integer) to a type numeric(integer).
An example of a function that maps a function to a function (expression to expression):
Function M() && closure on x
Return »'x+1'«
Endfunc
Evaluate(»m()«) && return a function
(expression) 'x+1', not a value.
Function N()
If vartype(x)=«X«
Return null
Else
Return x
Endfunc
A function M(x) accepts as input a numeric value x, and returns a function (an expression) 'x+1'.
A function N() returns a new type (an option), for example an integer or null. Also evaluate(N()) return an option. A mapping N is an amplified function.
X=5
?EVALUATE("N()") && return 5
X=null
?EVALUATE("N()") &&return null
Evaluate accepts as an argument also values as character expressions, for example:
?evaluate(»7«) && returns 7
Evaluate don't manipulate only functions, but also amplified function. The VFP SQL engine has to manipulate values in a way similar to a function N(): it has also null values in a table.
The function evaluates operate in two ways:
Strict evaluation, for example evaluates (f (g (x)).
Lazy evaluation. When we use it in the lazy evaluation environment, it doesn't accept higher order functions in a »classic« way. Sometimes, if you use higher order functions as in 1) you get wrong results. How to manage high order functions in VFP?
We know a function composition, for example, addtwo(addone(x) is a composition of two functions addone and addtwo. We can compose the two functions also in another way and the result will be an equivalent function. The mathematical formula is:
FUNCTION fmap(v,f)
xx=LTRIM(STR(v))
&& transform it in a character expression
Return EVALUATE(f+"("+xx+")")
The function fmap takes a value (v) and a function (f) and return a value. An example:
FUNCTION addone(x)
RETURN x+1
FUNCTION addtwo(x)
RETURN x+2
FUNCTION addthree(x)
RETURN x+3
?fmap(addone(2),"addtwo") && returns 5
The function fmap
composes two functions addone and addtwo. It composes functions that maps
numeric values to numeric. You can create a similar fmap that maps values of
type characters to characters.
A composition of three
functions is:
Function
composition3(f1,f2,f3) &&helper
function
Return fmap(fmap(f1,f2),f3)
endfunc
Example 6.
CLEAR
x=2
? composition3(addone(x),"addtwo","addthree")
&& returns 8
A function composition3
is a binder, it composes three functions: it calls the first function and on the
result it applies a second function. The result is a new value, on which we call
the third function. All the three functions are of the type Numeric.
A composition3 is a helper
function (syntactic sugar). We can look at a function composition3(addone(x),"addtwo","addthree")
as a sequence of actions: the first action is addone(x) and then addtwo
and then addthree. Among the functions addone and addthree we have injected an
action addtwo. At every »,« we can inject another action. In OO version of this
composition we normally use a ». « ( something like: this.s.w.s1). The »,« or
».« are like bind operators. We can read them »and then«: addOne and then addTwo
and then addThree.
Instead of addthree(addtwo(addone(x))) we can now write an
equivalent function composition3(addone(x),"addtwo","addthree").
Sometimes this notation is better than the anonymous function, for example x+6.
The function composition can contain VFP commands, so it is better, if we speak about actions' composition.
Note. A function fmap(f1,f2) applied on two functions is a monad bind operation.
A function composition fmap(f1,f2) evaluates the two functions eagerly (immediately).
In VFP you can't pass functions as argument, for example this is possible:
?addOne(addTwo(3))
We pass a value addTwo(3) to a function addOne. But this code generate an error:
? addOne(addTwo(x)) && error variable x not found
In lazy evaluation we frequently use this kind of constructions, so the question is, how to compose functions for lazy evaluation?
FUNCTION fmapLazy(v,f)
xx=v
Return (f+"("+xx+")")
ENDFUNC
A function fmaplazy takes a value and a function, »compose« them and return a character expression: a function to be evaluated.
x=2
?fmapLazy("x","addtwo") && returns addtwo(x)
?EVALUATE(fmapLazy("x","addtwo")) &&returns 4
A fmapLazy("x","addtwo") returns a character expression addtwo(x). If we evaluate it on a value x=2, it returns 4.
We can compose functions using fmap:
?EVALUATE(fmapLazy("addone(x)","addtwo"))
&& returns 5
X=8
?EVALUATE(fmapLazy("addone(x)","addtwo"))
&& returns 11
When we evaluate the function fmapLazy("addone(x)","addtwo") on a value x=2 it returns 5 and on a value x=8 returns 11.
A composition EVALUATE(fmapLazy("addone(x)","addtwo")) is like a macro: we apply it and it returns a value.
Lazy evaluation helps us in managing infinite streams. When we don't know in advance how long will be a process, we model it as an infinite stream and we stopped it on demand.
An example.
Let us create a program that reads a field's id value of a record in a table test with 10.000 records. It reads the value id from a record till id is less than 1000.
Function idread()
&& takes a value from its environment – a table test
?id
Return id
Endfunc
Use test
Procedure runall
Do while .t.
Idread()
Skip
Enddo
Endproc
The procedure runall will run forever, if the table test has a very large number of records.
Function idread()
?id
If id=1000 or eof()
Exit
else
Return id
endif
Endfunc
We add an if statement in a function idread to end the process, when id is 1000 or end of file.
A function idread is a closure, it is like a lazy evaluated function. It takes its argument values from the environment where it is called. Le us observe this two functions applied on a first record
Function idlazy()
?id
Return »id«
Use test
?idread()
?evaluate(idlazy())
They behave in the same way and give us equal results. In VFP (sometimes) an evaluated expression can produce the results equal to a closure, p.e. »x+1« (expression) and return x+1 (closure).
With lazy evaluation you can manage promises (futures). Let us explain what it is in the code from example 4.
1)X=4
2)g=glazy() && give us a promise (future)
3)? f(g()) && returns 25, for x=4 , f(g(x)) is
evaluated here
4)*A computation
5)x=5 && value is produced by a
computation (is arrived)
6)?F(EVALUATE(g))
&& returns 36, for x=5
In the line 2 we have solved a problem involving values that didn't exist yet. We know only the logic (the function g) and its signature (a type of input and output) we have to apply for a value, eventually will »arrive« in the future. We read a function glazy() as a promise, we will have a value. We don't know, if the value will arrive (be produced) and when will this happen. The last problem »when« we usually solve by a time out: If the event doesn't happen in a time interval, we conclude, it will never happen and we react: a promise is broken.
On the other side, when the value »arrive« (line 5), we evaluate it (line 6) and it returns a value.
In line 4 we have switch the application to another program (thread of execution). When it ends, we eventually evaluate (6).
To be more realistic, we shall put the last three statements in a loop with a »time out«.
k=1
x=null
Do while k<10
K=k+1
computation(k) && A computation that eventually
produces x
If vartype(x)=«N«
?F(EVALUATE(g))
Endif
Enddo
If k>=10
Messagebox(»Time out«)
Endif
Function computation(x)
If k=3
Return X
Endif
endfunc
This program in a loop runs an application compute(1) and after that test, if x is created. If it is not, it repeats the loop by running another application and so on.
The command F (EVALUATE (g)) in the last program executes asynchrounosly. We have created the logic in line 2). It will be eventually executed asynchrounously when the value of x will be a numeric value. This program has an added value: The asynchronous process doesn't block. If the computer has another task to execute (function to compute), it can do that, instead of waiting for an »asynchrounous message«.
Lazy evaluation in programs like the last and promises or future are appropriate code to run asynchronous code in VFP.
Note. Promises (futures) are lazy evaluated function composition.
A function fmapL("addone(x)","addtwo") can be read also in this way: the function addtwo is a continuation of the function addone.
Let us analyze this question: What are the conditions a function addtwo can be a continuation of addone? There are multiple response to this question. Let us illustrate two:
The types of the two functions must match. The result of the first functions is numeric and the input of the function s1 has to be of type numeric.
How to solve the problem, if the result is of type logical or is null or void. For example:
Function f(x)
X=x+1
Endfunc
Function
callback(obj,func) as void
?func
endfunc
These two functions return:
F a logical value .T.
callback void.
The return values of these two functions are unusable. You can't compose them with a new function. It is better, if a function has a return value.
In this article we have shown a method of function composition when we evaluate them in a lazy way. In some programming languages this is called actions composition. Technically we transform a composition of nested functions in a sequence of actions. Between two actions we can inject new actions: injecting new actions become a very simple job. The code is readable.
From the point of view of the language this action sequencing and injecting is a language inside extension that gives a programmer the opportunity to create programs in a new way.
Lazy evaluated functions have a form of an expression, for example »x+1«. Instead of a set F of functions we have a set of expressions. Every function in a set F has its map in the set of expressions »F«. This set has also a subset of all numeric values. For example values 1,2,3 have a map in the set »F« »1«,«2«,«3«. The elements of a set »F« are »f(x)«, »g(x)«, »f(g(x))«, »1«,«2«....
Note. In VFP you can't pass functions as arguments. But there is a workaround that permits us to manipulate them. You can think this problem in this way. You can't send functions by post. You have to put them in an envelope. You put each function in an envelope and post them. The receiver has to extract a function from the envelope and use it. In our case the envelope is the quotation marks.
We manipulate these elements using the functions, we use in strings manipulation. For example, the function trim takes an expression (a value) and a function and return a character expression, for example:
?trim('x+1') && returns »x+1« as a character
expression
?trim(»aaa ») && returns »aaa«
A function trim('x+1') can be written as ftrim(x,f). It takes as input a numeric value and a function f=trim, apply the function on the value and returns a character expression. A function ftrim maps from a type »F« to »F«.
The function »+« (concatenate) takes two character expression x and y and returns a character expression x+y, for example:
x=«3«, y=«5«, x+y=«35«.
X=«3«, G(x)=«g(x)«, G(x)=«g«+«(»+x+«)«==«g«+«(»+«3«+«)«. In this example we unwrap the variable x from »g(x)«, replace it with »3« and concatenate the elements. The second method is to unwrap the function g(x), apply it on a value 3 and wrap the result in an expression.
We compose the elements of a set »F« in this way:
1) compose two values »a« and »b«: »a«+«b«=«ab«. We unwrap the two values, concatenate the two unwrapped values and then wrap the result in quotation marks.
2) compose two functions »f(x)« and »g(x)« : »f(g(x))«=«f«+«(»+«g(x)«+«)«.
We compose the elements by unwrapping them, composing in a »normal« way, using the operations defined for a numeric type and then encloseing the result in quotation marks. We are going to formalize this composition.
A function evaluates unwrap the elements of a set »F« and return values (or functions) of a set F, for example:
?evaluate(»f(3)«) && returns 4
?evaluate(»5«) &&returns 5
?evaluate(»f(g(2))«) && returns 5
The function fmapLazy:
-Takes a value v (an expression).
-Unwrap a function f from its expression and call it on the value v.
-Wraps the returned value of a function f in a character expression.
A functor is a function, given a value and a function, unwraps the values to get to its inner value(s), calls the given function with the inner value(s), wraps the returned values in a new expression, and returns the new expression.
A function fmapLazy is a functor: it takes a value from »N« and a function and returns a value from »N«.
FmapLazy operates also on the functions from »NF«, for example:
fmapLazy(f1,f2) compose (bind) two functions from »NF« and returns a function from »NF«. Concatenate is a morphism on type »N«. Because it maps from »N« to »N«, it is a homeomorphism. The fmapLazy preserve composition, for example:
?fmapLazy("3","addone")
&& returns addone(3)
?fmapLazy("4","addtwo")
&& returns addtwo(4)
?fmapLazy("addone(3)","addtwo")
&& addtwo(addone(3))
?fmapLazy("x","addtwo") && returns addtwo(x), a characte
expression
So now we have our expression, containing a character value (“3”), and we “open” the expression, throw a function (“addone”) into it, and now the value and the function react, resulting in an integer value inside that expression (“addone(3)“).
The functor fmapLazy takes a value »x« ( a character expression) and a function addtwo and returns a character expression addtwo(x).
Let us observe what happens when we pass to the functor fmapLazy a function instead of a value.
FUNCTION fukctorOfFunction(f1,f2) && a helper, function syntactic sugar
RETURN fmapLazy(f1,f2)
x=2
y=fukctorOfFunction("addTwo(x)","addthree")
?"foff",y &&returns addthree(addtwo(x))
x=5
?EVALUATE(y) && returns 10, takes 5 and evaluates
A fukctorOfFunction binds two functions in a lazy way. It returns a character expresion (a function enclosed in quotation marks). The result is a composable function.
FUNCTION ident(x)
RETURN x
ENDFUNC
The function ident maps every element form »NF« to itself. It is left and right associative.
?fmapLazy("2","ident") && returns ident(2)
?fmapLazy("ident(2)","addtwo") && returns addtwo(ident(2)), left associative
?fmapLazy("addtwo(2)","ident") && returns ident(addTwo(2)), right associative
So, if you want to cause any effect on an expression, for example “2”, you have to pass a transformation into the functor (“ident”). The result of the effect stays in the Functor (“ident(2)”).
We have a monad defined on a type expression. The type »NT« has a bind composition (fmapLazy) and an identity element ident so it is a monad.
Let us see a problem we have in lazy evaluation of composed functions.
Example.
FUNCTION s2(x)
?"before",x,m.x,x**2
xx=x**2
?"after",xx,x,m.x
return xx
endfunc
FUNCTION s1(x)
RETURN x +1
ENDFUNC
Let us compose two functions
using fmapLazy.
x=4
?EVALUATE(fmaplazy("s1(x)","s2")) &&
returns 25
In this example we can manipulate the argument of the first
function s(x). We can use, for examples s(x) or s(m.x). But we can't manipulate
the »name« of the variable of the second function. One solution to this problem
is to introduce a new argument, for example, s1(x,y).
We have a table test
with two fields: x I(6) and quantity I(6). In a third record we have the values
x=3 and quantity=8.
clear
CLOSE DATABASES
&& execute without a conflict between a memory and field variable
m.x=999
?"s1",s1(x)
&&returns 1000
?"r01",s1(s(x)) && returns 998002, a correct result,
no conflict
USE test && executes with a conflict
SKIP
SKIP
*x=3, quantity=8 are
two field values in a third record
?VARTYPE(m.x),m.x && returns N 999
?"r1",EVALUATE("s1(s2(x))") && returns 4, correct result is 10
?"rq",EVALUATE("s1(s2(quantity))") && 4
ignore the argument, the correct result is 65.
?"r1m",EVALUATE("s1m(s2m(x))") && returns 10, a correct result is
1+(999)**2, ignore m.x
?"r2m",EVALUATE("s2m(s1m(x))") && returns 16, a correct result is
1000**2, ignore m.x
?"r1mm",EVALUATE("s1m(s2m(m.x))") && returns 998002, a correct result
?"r2mm",EVALUATE("s2m(s1m(m.x))") && returns 1000000, a correct result
The functions s1 and s2 are not functioning in a mathematical sense. When we evaluate s1(s(x)) on a record with a field name x and a value x=3, we get a wrong result 4. If we change the argument to quantity (another field with a value 8), we get the wrong result 4. We can conclude that evaluate ignore the arguments and use variables from the environment (a closure).
Note. In VFP help, we can find the explanation that a filed's variable, in our case x, has precedence over a memory variable x. But millions of people over the world knows that s1(9) is 10.
The workarounds to this problem are:
1) Don' uses the same names in functions variables and field names. The function s1 is a »continuation« of the function s. It's argument and variable names must be different from the opened table fields names, for example s1(k).
2) Don't use composed functions, but write them in an explicit way:s1(s(x))=x**2 +1. Sometimes this is not a clever solution.
Note. In mathematics f(x)=X**2, give us always f(2)=4. The functions applied to values in a VFP table, don't behave in this way. It seems they behave as a closure, ignoring arguments. In non functional languages are very difficult to manage high order functions in a lazy way.
Note. VFP start for example with this variables m.x and x (a field). It computes a first function s(x), and creates a new closure with a new computed value mm.x. In the new closure it can access only the variable x and a new mm.x. The second function s1(x) can take as variables (concurrent) x and mm.x. Because of a convention, it takes x (if it has not an exact instruction to take from this closure a mm.x). If the function s1(x) has a notation m.x (p.e. m.x=x+1), a variable m.x is the computed m.x, not the original.
We have to manage multiple variables:
1) when we call the first function we have: m.x (a memory variable) and x a field variable,
2) when we call the second function, we have to add a new variable mm.x (the return value of the first function). At this level we have a conflict between mm.x and x.
3) when we call the next higher order function, we have to add a new variable and so on.