Lambda

BlitzMax Forums/BlitzMax Programming/Lambda

Yasha(Posted 2013) [#1]
Update: this has been much improved since the original post, see post #6 for the current version.

DO NOT USE THE VERSION IN THIS POST: it is here for thread-historical purposes only.


----


From the same school of thought as before...

This is really silly, but anyway, just for fun: lambda functions in BlitzMax, attempt 1:

lambda.bmx:


lambda.S (compile this with GCC to lambda.o, for the Import - and note the capital S in the filename, it's important):


An example:

Import "lambda.bmx"
SuperStrict


Global FN:TLambda(_:TFnArg[]) = TLambda.FN		'Shorten the constructor names into something manageable
Global I:TBoxVal(_:Int) = TBoxVal.BI, O:TBoxVal(_:Object) = TBoxVal.BO	'These will get a lot of use

Global X:TFnArg = New TFnArg, Y:TFnArg = New TFnArg, Z:TFnArg = New TFnArg	'Some "variable" objects


Local f:TLambda = FN([X, Y, Z]).as(I( X.i + Y.i * Z.i ))	'Simple function
Print f.call([I(4), I(5), I(6)]).i

Local f2:TLambda = TLambda(f.call([I(4)]).o)	'Calling with fewer arguments = currying
Print f2.call([I(5), I(6)]).i

X.i = 4 ; Local f3:TLambda = FN([Y]).as(I( X.i + Y.i )).over([X])	'Forming a closure needs to be done manually
Print f3.call([I(5)]).i

Local f4:TLambda = FN([X]).as( SideEffects(42) )	'Because the body runs, this will print now, even though we don't want it to yet
Print f4.call([I(0)]).i	'Still prints again OK though

Print UseLam( FN([X]).as(I( X.i + 13 )) )	'Use a lambda as part of an expression


Function SideEffects:TBoxVal(n:Int)	'Used with f4: this function has a side effect
	Print "function is running!"
	Return I(n + 1)
End Function

Function UseLam:Int(f:TLambda)		'Pass a lambda to a higher-order function
	Return f.call([I(4)]).i
End Function


Good grief, it somehow actually worked (tested on OSX and Linux).

If you don't know what lambdas are, this is (as with the other thing) definitely not the way to learn. This is for interest purposes only.


How to use:
- "variables" are actually TFnArg objects. They need to live in globals, so create some global TFnArgs with the names you want to use for lambda parameters (as in the example where X, Y and Z are used).
- "lambdas" are created with FN().as(), where FN (assuming you've shortened the name) takes an array of parameters and .as takes an expression to use as the body. Argument values are TBoxVals, so to get at an integer, object, or double respectively, use the .i, .o, .d fields. etc. The result needs to be packed into a TBoxVal as well.
- invoke the lambda with .call(array of argument values), and get its result with .i, .f, whatever.
- Currying is automatic if fewer than the expected number of arguments are passed, and the result of the curry call will be a TBoxVal with the new TLambda in its .o field
- closures are not automatic (left to itself, free variables will bind dynamically), and must be formed explicitly by putting a value in the variable(s) to bind, then calling .clos(variable array)
- it is "safe" to refer to globals in a lambda body
- it is absolutely not safe to refer to locals in a lambda body, and BlitzMax variables cannot be used to create closures in this way (must be done manually with .clos)
- the heavy reliance on global variables means it is absolutely not thread safe. (might not even be possible to make, haven't thought about it)
- code in the body will run when the lambda is created, so stick to "pure" (side-effect free, math) operations
- there are no control structures. Try writing an IfThenElse function or something.
- recursion and nested calls should be OK, as TFnArgs maintain a hidden stack
- X86 only


How does it actually work?
Ahahahaha. Using one of the most dirty and evil hacks I've ever tried in BlitzMax.
FN stores its own return pointer (as in, the address of the machine code the program is supposed to jump back to when FN is done running) as the lambda's .start field. .as doesn't actually do anything at this point, it only guarantees (weakly, a different compiler might not do this) that the expression's code will appear after the call to FN because it's a method on the returned object.
When the lambda is invoked, assuming it's not being curried, the .call method stores the current stack frame, puts Self in EAX (as though it were being returned from FN), and jumps to the instruction held in .start. This is the code for the lambda body, which then runs. You can see why local variables are forbidden - mutilating the stack frame like this means it's impossible to access them.
When the code eventually gets around to .as, it detects that it's coming in from an invocation rather than creating the function, and restores the stack to where it was before the call (and jumps back to the body of .call).

Pure evil.

This method is entirely reliant on the fact that BlitzMax generates predictable code and doesn't perform optimisations. If it did anything "interesting", this would break. If it does anything "interesting" in places I haven't tested (most), this will break.


And yes, it would be much, much more sensible (and sane, and practical...) to represent lambdas as strings or computation-builders and then interpret or JIT them... but that way I wouldn't be able to use real BlitzMax operators like + in expressions (note that if BlitzMax supported operator overloading this would actually be quite easy to fake, c.f. Boost::Phoenix - but it doesn't).


GW(Posted 2013) [#2]
I like it! I wouldn't use it over lua/bvm/coocoo, but its an impressive feat.


BLaBZ(Posted 2013) [#3]
Yasha you are an evil genius.


Danny(Posted 2013) [#4]
Hats off!


Who was John Galt?(Posted 2013) [#5]
Genius and insanity are divided by a fine line, which Yasha seems to crossing all too often. ;)


Yasha(Posted 2014) [#6]
Attempt 2: substantially improved. Now features:

-- much better syntax (completely dropped the TFnArg objects and wrapper types, fewer brackets)
-- full integration with BlitzMax variables
-- closures over BlitzMax local variables
-- thread safe (not for individual lambdas, but the library as a whole is, except for...)
-- reification (i.e. you can convert a lambda into a "real" BlitzMax function pointer, as long as it's not a closure)
-- should be faster

lambda.bmx:


lambda.S (compile with 'gcc -m32 -c lambda.S -o lambda.o'):


The reification functionality also depends on the simple Alloc/Protect wrapper C file used by TInterface (don't need to duplicate it): http://www.blitzbasic.com/Community/posts.php?topic=100385


...and an updated example:



Individual TLambda objects are non-reentrant, so don't attempt to make them recursive, and don't call the same object from different threads. The library itself no longer uses any global variables so it should be fine to create lambdas in different threads and use them separately.

The autocurrying feature is gone; it didn't add much anyway that you couldn't do by hand. In its stead is the ability to form closures over real BlitzMax local variables, which is a pretty good trade. Parameters are now real locals - they still have to be declared in the surrounding scope (there are limits to my magic), but they otherwise work normally, and both globals and locals can appear in lambda bodies. You can select the types of arguments and the return type of the lambda using the selection of different FN_... and as... constructors (argument types are not checked at runtime, because effort, so be careful).

It strikes me that this library probably doesn't do good things when exceptions try to rise through a lambda's call frame. I suggest avoiding this scenario.