Higher-order functions

Blitz3D Forums/Blitz3D Programming/Higher-order functions

Yasha(Posted 2009) [#1]
Just fiddling around a bit... I make no guarantee that any of this is sensible or even accurate.

For those who aren't aware, a higher-order function is one which can take functions as parameters, or return a function as a result. While this sort of thing is possible in BlitzMax, Blitz3D doesn't offer any such functionality, largely due to not supporting function pointers (until recently, with the introduction of a couple of rather nice DLLs, but let's ignore this).

Now there's a long-established way around the lack of function pointers which will be familiar to anyone who's attempted to build a scripting language, which is to set constants to represent your functions and execute them via an Eval() or Apply() (or whatever) function, using a Select structure to choose the right function to call (I suggest you stop reading now if you don't like this method). The automatic type conversion in Blitz3D makes strings the logical (if rather slow) choice for passing parameters through Eval().

;Function pointer list - making these Globals might look tidier?
Const PTR_NullFunction=0
Const PTR_Add=1:NewFunction("Add",PTR_Add,2)
Const PTR_Mul=2:NewFunction("Mul",PTR_Mul,2)
Const PTR_Pow=3:NewFunction("Pow",PTR_Pow,2)
Const PTR_Max=4:NewFunction("Max",PTR_Max,2)
Const PTR_Square=5:NewFunction("Square",PTR_Square,1)



;Simple example functions - all very trivial
Function Add(x,y)
	Return x+y
End Function

Function Mul(x,y)
	Return x*y
End Function

Function Pow(x,y)
	Return x^y
End Function

Function Max(x,y)
	If x>y Then Return x:Else Return y
End Function

Function Square(x)
	Return x*x
End Function

Then we could do something like this, to use the constants as function pointers (not that this is very pointful in itself):
Print Add(5,8)
Print Eval(PTR_Add,5,8)
Print Max(5,8)
Print Eval(PTR_Max,5,8)
Print Pow(5,8)
Print Eval(PTR_Pow,5,8)

WaitKey
End

Calling the functions directly, as above, is not especially useful. However, with a means to call a function from an integer variable, it becomes much easier to write a map or fold function - a higher-order function taking a function as one of its parameters. The map function takes a list and applies the specified function to each element of the list:
;Examples of higher-order functions
Function Map(func,list[5],arg$=NULLSTR)		;Given the highly limited nature of Blitz arrays, use a bank for this in a real program
	Local i
	For i=0 To 5
		list[i]=Eval(func,list[i],arg)
	Next
End Function

Function LeftFold$(func,list[5],rval$)
	Local i
	For i=0 To 5
		rval=Eval(func,rval,list[i])
	Next
	Return rval
End Function

The other advantage of using Eval() to call functions rather than doing it directly, is that they don't necessarily need to be fully applied. Higher-order functions can also return functions as their results - partial application means that a function that isn't given enough arguments to return a value will instead return a function that can be given more arguments:
Print Add(5,3)
Print Eval(PTR_Add,5,3)
Local add5=Eval(PTR_Add,5)
Print Eval(add5,3)
Print Eval(add5,5)

WaitKey
End

This is closely connected to "currying". Since obviously the add5() function is not a real Blitz3D function, it needs to be created as a function type-object. While it can't be called directly in code, it can be called through Eval() exactly the same way as any other function with an integer pointer. However, if we can create function objects, there's also no reason to be limited to just partial application of existing functions; we can also compose them together using a technique known as lambda abstraction:
add5=Lambda("x","add(x,5)")
Print Eval(add5,3)

Print Eval(Lambda("x,y,f","f(ARG_0,square(f(x,y)))",1),5,2,PTR_Add)

WaitKey
End

The string on the left is a list of parameters in the order they are passed when the function is called. The function returns the ultimate value of the expression in the string on the right. For the sake of elegance, this implementation accepts more arguments which it will swap out for specific names ("arg_0", "arg_1" etc), but since the two main fields are strings, it would be perfectly possible to simply concatenate any values in directly if desired. Do notice that in the second example, the outermost function f() is also a variable, called by integer handle as in the map() example above - functions are first-class (but typed) objects in this system and can be passed anywhere any other free variable can.

Aside from providing a slightly more interesting way to declare functions, function literals (anonymous functions) have other uses. They can be passed directly into calls to other higher-order functions such as map(), when the function required doesn't really need its own declaration. Or they can be returned from other "factory" functions, having had some of the free variables bound, to create what is known as a closure:
Function AddN(n)
	Return Lambda("x","add(x,arg_0)",n)
End Function

Local add2=AddN(2)
Print Eval(add2,5)
Local add3=AddN(3)
Print Eval(add3,5)
Local add4=AddN(4)
Print Eval(add4,5)

WaitKey
End

This is again connected to currying (although they are distinct concepts, this system doesn't really demonstrate the difference). The idea is to create new functions with fewer arguments, having "bound over" the ones that aren't required to change for the time being, thus having a function that more closely reflects what it's being used for. The ability to close over variables and quickly compose functions together into temporary objects has endless applications, anyway, and is a large part of the basis of functional programming.

OK, enough teasing, here is the (horrible, slow and inefficient) code that powers this abomination:


You should define a constant for all your native Blitz3D functions that you want to make accessible to this system, and call NewFunction() in the same order (NewFunction() increments a global variable so doing this out of order will break things). You'll also have to add these functions to the main Select/Case list inside Eval(), which ought to be fairly straightforward.

The Lambda() function has two syntactic quirks (by necessity - as far as possible the goal of this system is to make the syntax look natural, to actually speed up programming). Firstly, since the arguments are string literals, there is no access to any Blitz3D variables or globals. This is not a bad thing, as it helps maintain functional purity. Also because they are literals, to get values into the function definition, you'll need to either use string concatenation ( Lambda ("x", "add ( x , "+N+")") ) or the known constant names, passing the values as extra arguments ( Lambda ( "x", "add ( x , arg_0 )" , N ) ). I think the second looks much nicer, but they are effectively identical (actually the first should be slightly faster). The second quirk is that there are no infix operators - if you want to write a complex parser go ahead, but currently it only supports function calls, so any simple operations will still need to have a function defined (eg. add(x,y) - with a little imagination you could also devise functions for If/Then/Else, sequential execution of commands, etc.). Anonymous functions should be case-insensitive, achieved by using the Lower() command - if you want to change the known constant names, make sure their definitions are lower-case.

Because functions are created by the bucketload (Lambda() creates loads of helper-functions) and there is no garbage collection in Blitz3D (not for this, anyway), you'll need to get rid of function objects manually. You can use FreeFunction(ID), or ClearFunctions, which deletes all functions that haven't been explicitly named (so if you want to save a function, name it with NameFunction(ID,name) - to expose it for deletion, rename it as ""). NameFunction and FreeFunction are recursive and should cover helper functions too. You don't need to call ClearFunctions constantly though, as Lambda() will not create a new anonymous function object if an identical one already exists.

I make no guarantee that I have understood the concepts involved correctly, so take anything I say above with a pinch of salt (except for the fact that functional programming rules, because it simply does). For further reading on the subject, see:

http://haskell.org/haskellwiki/Functional_programming
http://en.wikipedia.org/wiki/Functional_programming
http://haskell.org/haskellwiki/Lambda_abstraction
http://en.wikipedia.org/wiki/Anonymous_function

...which were my main points of reference while doing this.

Have fun...


EDIT: All of this is supposed to work out-of-the-box as include files, hence the horrible syntax. I'm now working on a preprocessor (almost a source-to-source translator, really) that will hopefully make things a little prettier, and a lot faster, but obviously that's a very different undertaking (will include OOP).

EDIT2: OK so the preprocessor turned into something else entirely. Still trying to think of ways to make this practical though. Can't think of any good ways to imitate garbage collection...


Warpy(Posted 2009) [#2]
Niiiiice.

Disappointed you didn't find a way to work with real blitz functions, but very clever anyway.


WERDNA(Posted 2009) [#3]
partial application means that a function that isn't given enough arguments to return a value will instead return a function that can be given more arguments:


I was just about to ask if there was a way to do this, lol.

You just saved me the trouble :)

Awesome post Yasha!

W E R D N A


Yasha(Posted 2009) [#4]
Glad you guys liked it! A little more testing revealed some bugs, which I found and fixed; if you're playing with this (or, God forbid, found a practical use for it), please copy the code again. The main problem was in ParseLambda(), not handling function composition properly.



And now for something completely stupid...

The idea of using FP style in Blitz3D got me thinking along a very, very odd path. Best illustrated by (a very messy and largely uncommented) example. First, you'll need to update the list of functions available to Eval() (this is its Select/Case structure, inside the function):

Case PTR_Add:rFunc=Add(c_arg[0],c_arg[1])
Case PTR_Mul:rFunc=Mul(c_arg[0],c_arg[1])
Case PTR_Pow:rFunc=Pow(c_arg[0],c_arg[1])
Case PTR_Max:rFunc=Max(c_arg[0],c_arg[1])
Case PTR_Identity:rFunc=Identity(c_arg[0])
Case PTR_ConcStr:rFunc=ConcStr(c_arg[0],c_arg[1])
Case PTR_IIf:rFunc=IIf(c_arg[0],c_arg[1],c_arg[2])
Case PTR_Eq:rFunc=Eq(c_arg[0],c_arg[1])
Case PTR_Right:rFunc=Right(c_arg[0],c_arg[1])
Case PTR_maybeUnit:rFunc=maybeUnit(c_arg[0])
Case PTR_maybeBind:rFunc=maybeBind(c_arg[0],c_arg[1])
Case PTR_maybeDiv:rFunc=maybeDiv(c_arg[0],c_arg[1])
Case PTR_stateUnit:rFunc=stateUnit(c_arg[0])
Case PTR_stateBind:rFunc=stateBind(c_arg[0],c_arg[1])
Case PTR_Random:rFunc=Random(c_arg[0])

That goes in the library in the post above, which is the file referred to below as "HOF.bb". Next, an include file (no real reason other than to keep it organised) - "Monad.bb":



And finally, the example:



That increasingly-unwieldy list of function pointers is making me think a program to read source code and build the list automatically would be a nice idea...

Anyway, I cannot think of a single practical use for this, but it was an amusing thought-experiment, and now you can all tell me how I've completely misunderstood my own idea. I'm now going to stop messing about before my brain melts, because I'm really quite new to FP, as is painfully obvious.

Further reading:
http://haskell.org/haskellwiki/Monad
http://en.wikipedia.org/wiki/Monad_(functional_programming)