This article is written in the time I just learnt the lua.
Lua is a widely used embeded script language, and it supports almost all the modern features. although it does not integrated functional programming support, but it's features like built-in table type, stack-based vm, high order function and etcs makes functional possible.
First, look at an example about how high-order function is used in lua
function double(a)
return a*2;
end;
function add(a,b)
return a+b;
end;
function make_f(unop,binop)
return function(a,b) return unop(binop(a,b)); end
end;
f=make_f(double,add);
print(f(1,2))
Here we have three functions, their prototypes are
double:
R->
R add:
R*
R->
Rmake_f: (
R*
R->
R) * (
R->
R) ->
R*
RWe use function as variant and do algorithm on them.
With how to use high-order function in lua, now let's see how to implement the most commonly used functional operators, like
map,
filter and
reduce( as an explanation, therefore I only use
foldl), after we've done these fundamentals, we can try some *advanced* tricks to implement some interesting stuff, like function currying.
Before implement the elemental operators, we shall see the definition of them.
The
map is defined as: for each number i in a range, there always exists
V[
i]=
f(
D[
i]), then we use operator
map to describe this behavior as
V=
map(
f,
D);
So we have a corresponding code like:
fps={}; -- abbreviation for functional programming support
fps.map=function(fn,list)
local result={}
local i;
for i=1,table.getn(list) do
result[i]=fn(list[i]);
end
return result;
end
The
filter is defined as: for a sequence of numbers
D, any of them will exists in a sequence
V if and only if
f(
d) is true, here
d is a item in the sequence
D, abbreviated as
V=
filter(
f,
D)
The code is:
fps.filter=function(fn,list)
local result={}
local c=1;
local i;
for i=1,table.getn(list) do
if(fn(list[i])) then
result[c]=list[i];
c=c+1;
end
end
return result;
end
And the last
reduce have two forms, fold left and fold right. the fold left looks like:
operator {operand_1 operand_2 operand_3 ... ...operand_n}
->
{(operand_1 operator operand_2) operand_3 ... ...operand_n} ->
{((operand_1 operator operand_2) operator operand_3) ... ...operand_n} ->
((....((operand_1 operator operand_2) operator operand_3) operator... ) operator operand_n) and the fold right is totally reversed, from right to left to reduce.
The
foldl is:
fps.foldl=function(fn,init,list)
local ret=init;
local i;
for i=1,table.getn(list) do
ret=fn(ret,list[i])
end
return ret
end
After these definition is clear, the implementation of them is now wisable.
Now we want to caculate
f(
x)=
x/(
x+
1) with
x in range [
1,7]:
function fps.range(lower,upper) -- we use this to create a ranged interval
local ret={}
local c=lower;
for i=1,upper-lower+1 do
ret[i]=c;
c=c+1;
end;
return ret
end;
f=function(x) return x/(x+1) end; --define the function f
f2=fps.map(f,fps.range(1,10));--caculate
for i=1,table.getn(f2) do --display them
print(f2[i])
end;
now we got the expected result. here we can simplify the output statements by using
map operator:
fps.map(print,f2);
ok, let's combine these operators to see how strong functional programming is, now I give you an question, caculate
Σ(Σ(1 to x)+3) for x in interval [1,1000] and x is even, you can try this in imperative style language, how long will you take it and ensure correctness?By using these operator, the final code in lua would like:
add=function(a,b) return a+b;end;
is_even=function(v) return math.mod(v,2)==0; end;
sum_add_3=function(v) return foldl(add,0,range(1,v))+3; end;
print (
foldl (add,0,
map(sum_add_3,
filter (is_even,
range(1,1000)
) ) ) )
The result is 83710250.
Many parentheses, looks like lisp o(*^-^*)o
Ok, now we know much about these operators and their power, let's see a more powerful weapon. function currying.
Before begin implementing the function currying, we need to prepare some concepts, function closure. you can get the details of closures in lua in online ebook
Programming in Lua.
First, let me explain what is function currying, so far as I know, that's the theory of a man called
Haskell Brooks Curry #-_-, yeah, there's an great functional language Haskell, it's named after this brilliant logician.
Assume there is a function
f with prototype
ΠR^
n->
R (notation
Π here indicates the R appears for n times in the domain), curry function f with ΠR^m (0<m<=n) will generate an high order function ΠR^m ->ΠR^(n-m)->R, or represent as prototype: (ΠR^n->R)*(ΠR^m) -> (ΠR^m ->ΠR^(n-m)->R)This is my understand, may be it's not mathematically right :P
For a simple example,
f(
x,
y,
z)=
x+
y+
z, curry this function with parameter 1 and 2, this will become
f'(z)=1+2+
z, the parameter x and y are reduced by the curry parameters, it becomes another function.
So we can imagine, implement a currying function, is actually stored the curry parameters in the function closure, and returns an high order function that accept the rest parameters to makes it looks like mathematically curried.
The lua has a stack based vm, all the operations are done via stack, what ever parameter passing or returnning values. and lua provides a function unpack, this function accept a table type parameter, and put all elements on the stack, so we can invoke a function like this:
function test(a,b,c,d,e,f,g)
print('a='..a);
print('b='..b);
print('c='..c);
print('d='..d);
print('e='..e);
print('f='..f);
print('g='..g);
end
test(unpack({1,2,3,4,5,6,7})) ;
The unpack returns data in the array parameter by pushing them on stack, and immediately call test, then the data in the array become the parameters of function test;
This is a very good mechanism to implement currying function, merge the curry parameters stored in the closure and passing parameters of the currying function into one array, unpack the array to stack and call the function being curried.
It seems the lua doesn't provide a direct function to merge two array into single one, so I wrote one:
table.merge=function(array1,array2)
local ret={}
local c=1;
for i=1,table.getn(array1) do
ret[c]=array1[i];
c=c+1;
end
for i=1,table.getn(array2) do
ret[c]=array2[i];
c=c+1;
end
return ret;
end;
With previous works, now write a curry procedure is no more difficult, only merge two kinds of parameters into one, and pass it to the original function and call it:
-- this curry function accepts a packed sequence of parameters
fps.curry2=function(fn,args)
local i;
return function(...)
local a=table.merge(args,arg);
local ret=fn(unpack(a));
return ret
end;
end;
-- this curry function accepts general passing parameters
fps.curry=function(fn,...)
return fps.curry2(fn,arg)
end;
Because this kind of implementation dont care the original function, the curry procedure can be nested.
How does this work? see some examples.
Sum numbers from 1 to 1000:
add=function(a,b) return a+b; end;--used to add two number
sum=curry(foldl,add,0);--make a curried function
print(sum(range(1,1000)))--caculate and display result
The code is pretty beautiful :) How does this done? the second parameter and nexts are stored in the closure
sum as function
foldl did, when applying the closure
sum with parameter range(
1,1000), the closure combine the previous parameters and the new incoming pararmeters together, and invoke the original function with them, return the function result. This is how the magic is done, it's amazing and attractive, isn't it?
Does the currying will effect the performance? Yes, but the costs definitely can be ignore.
The curry version of previous complex caculation is:
add=function(a,b) return a+b;end;
is_even=function(v) return math.mod(v,2)==0; end;
sum=curry(foldl,add,0);
sum_add_3=function(v) return sum(range(1,v))+3; end;
print(
sum(
map(sum_add_3,
filter (is_even,
range(1,1000)
))))
Compare the caculation time with previous
clean version, the curry version doesn't bring down too much, almost the same time with that.
After two weeks, my examinations will be done, I will have enough time to write technical articles on my blog, yeah~~~ there were almost for four months I ain't have time to write blog.
