Higher Order Functions in Moto

	Here's a rough draft of the documentation I want to add to support 
site about HOFs. Comment, criticisms, edits :) Pass em along!

-Dave

Implicitly Valid Types
------------------------

Arrays are the simplest example of implicitly valid types in Moto. 
Given a valid type X, X[] is a valid type in Moto. Specifically X[] 
represents an array of X's . And X[][] is a type representing a two 
dimensional array of X's. This sort of dynamic type definition is 
common to many languages including Java.

There is another class of types in Moto that are 'implicitly valid' as 
long as their base types are valid. These are called functional types 
which can be described as follows:

1) If X is a valid type X() is a valid type -  It represents a function 
which takes no arguments and returns a value of type X
2) If X and Y are valid types X(Y) is a valid type - It represents a 
function which takes an argument of type Y and returns a value of type X
3) If X is a valid type and Z is comma delimited list of valid types 
than X(Z) is a valid type - It represents a function which takes 
arguments of the types listed in Z and returns a value of type X

Here are some concrete examples of declarations using functional types:

	int() f; // f can be assigned a function which takes no arguments and 
returns an int
	int(int) g; // g can be assigned a function which takes an int and 
returns an int
	int(int,String) h; // h can be assigned a function which takes an int 
and a String and returns an int
	int(int()) i; // i can be assigned a function which takes a function 
that takes no arguments but returns an int. i must also return an int.
	int(Vector(int),String()) j;
	Enumeration(StringBuffer(int),String())(String(),float) k;
	Object(int[](StringBuffer[][]),String())(String[](),float[]) l;

Functional Typed Variables
------------------------

As you might have guessed by the name (and the above examples) 
functionally typed variables can be assigned real functions or methods 
who's arguments and return types match. Consider to the function atoi 
in cstdlib which takes a String and returns an int. We could define a 
functional variable 'myatoi' and assign it atoi:

int(String) myatoi = atoi;

Functional variables can be called just like regular functions and 
methods.

int i = myatoi("3");

What is the 'type' of a Function.
------------------------

The type of a function or method in Moto is
- its return type
- followed by '('
- followed by the types of each of the arguments it takes separated by 
commas
- followed by ')'

Simple ... no ?

Function Identification
------------------------

The atoi example is simple in that there is only one function in the 
system named atoi. Moto however, like C++ and Java allows for multiple 
functions to have the same name but take different arguments. A good 
example of this is the getValue function from the codex.http library. 
There are two variants of getValue, one that takes one argument, and 
one that takes two. We can differentiate between the two by using the 
'?' or 'unknown argument' token.

String(String) myGetValue = getValue(?);
String(String,String) myGetValueWTwoArgs = getValue(?,?);

We can be even more specific by using casts in addition to the '?' 
token. Suppose we have two functions with the same name that take a 
single argument (but of two different types) :

void println(int i){ print i+"\n"; }
void println(String s) { print s+"\n"; }

We can specify which one we want to identify by casting the unknown:

void(int) myIntPrintln = println(<int>?);
void(String) myStringPrintln = println(<String>?);

The last thing worth noting here is that you can optionally use the '&' 
operator to make clear that you want to identify a function. The 
following are examples of fully qualified function identification:

void(int) myIntPrintln = &println(<int>?);
void(String) myStringPrintln = &println(<String>?);

The real reason for the '&' becomes clear in relation to partial 
application discussed later. For the sort of regular function 
identification that has been described using the '&' or 'function 
identification' operator can improve code readability but is generally 
optional. The only case where it is necessary is when we have multiple 
variants of a function with the same name and we need to identify the 
no-arg variant:

void println(){ print "<empty line>\n"; }

void() myPrintln = println; // No good ... this is ambiguous
void() myPrintln = &println() // Perfect ... this is fully qualified 
identification

Functions (and Methods) that take Functions as Arguments
------------------------------------------------

Since functional types are no different from other types, creating 
functions that take functions as arguments is done just like you might 
suspect. The following function takes an array of Strings and a 
function to perform on each element of the array:

	void each(String[] a,void(String) f){ for (int i=0;i<length(a);i++) 
f(a[i]); }	
We could pass this function a function println

	void println(String s) { print s+"\n"; }

To print out all the elements in an array:

	 each(<String[]>{"one","two","three"}, println);

The Enumeration class has an each() method built in as of Moto 0.19.0 
which calls the function passed to it on each element in the 
enumeration. Thus to print out all the keys in a hash you could now 
just write

	stab.keys().each(<void(Object)>println);

This is as opposed to

	Enumeration e = stab.keys();
	while(e.hasNext())
		println(<String>e.next());

Which is the 'non-functional' (Java) way of doing things.

Notice the explicit cast to type 'void(Object)' in the functional 
example . That is needed because that is the type of the function the 
each method expects to be passed while println has type 'void(String)'. 
Sometimes functions can be cast 'implicitly' but this is not one of 
those times.

No example of passing functions to functions would be complete without 
the classic example of sorting. As of Moto 0.19.0 Vectors have a sort() 
method. This method takes a function which can be used to compare two 
Objects in the Vector. Why does it need to take a function you ask ? 
Because there is no way to compare two arbitrary objects.

The function must take two Objects and return 0 if they are equal, 1 if 
the first one is 'greater' than the second, -1 if the first one is 
'less' than the second. What 'less','greater', and 'equal' really mean 
in this context is that you want the the first element to appear 
before, after, or next to the second element in the final sorted list.

Luckily the is a function that does just that for Strings in the 
cstdlib extension called strcmp.

Thus to sort a Vector of Strings in Moto all you need to do is say

	v.sort(<int(Object,Object)>strcmp)

Again we need to explicitly cast strcmp to 'int(Object,Object)' from 
'int(String,String)' . The reason is that the Vector doesn't know its 
holding Strings. For all it knows its holding Dates or any other kind 
of Object and so it expects functions that work on 'Object's not 
sub-classes of Object. If it were holding dates however you might sort 
them as follows:

	int dcompare (Object a,Object b){
		Date l = <Date>a, r=<Date>b;
		return atoi(l.format("%Y%m%d")) - atoi(r.format("%Y%m%d")) ;
	}
	v.sort(dcompare);		

Implicit Casting Rules
------------------------

You don't need to 'explicitly cast' functions (or functionally typed 
expressions) when assigning them or passing them to functions when they 
can be 'implicitly cast'. The implicit casting rules for functional 
types are as follows:

1) Like all reference types (yes, functional types are reference types) 
values with functional types can be implicitly cast to 'Object'
2) Any type X(...) can be implicitly cast to void(...) since 'void' 
really means we don't care what if anything the function returned
3) Any type X(...) can be implicitly cast to Y(...) as long as X is a 
descendent of Y. The reason is if we have a function foo, which for the 
sake of argument takes no arguments and returns a String, and we assign 
it to a variable of type 'Object()' that assignment should of course be 
valid since everything foo could return would also be an Object.
4) Any type X(... Y ...) can be implicitly cast to X(... Z ...) as long 
as Y is an ancestor of Z. This may seem counter-intuitive be the 
rationale is as follows. Suppose we have a variable of type 
'void(String)'. This functional variable must be callable with any 
String. If we assigned to it a function of type 'void(Object)' than the 
requirement that 'any function assigned to it must handle all values of 
type String' is not broken. The function we assigned to it can handle 
all Strings and then some.

Explicit Casting Rules
------------------------

The explicit casting rules are like the implicit casting rules and 
their mirror image.

1) If X can be implicitly cast to Y then X can be explicitly cast to Y
2) If X can be implicitly cast to Y then Y can be explicitly cast to X

Partial Application
------------------------

In cstdlib there is a function pow

	double pow(double x, double y)

which returns x to the power y (x^y). Suppose we wanted to define a 
function 'square' which simply squares (x^2) its input. We could say:

	double square(double x) { return pow(x,2); }

Or we could do this:

	double(double) square = pow(?,2);

What we've done is created a new function by 'partially applying' the 
arguments to an existing function. We could partially apply the other 
argument to create a function twoToThePow (2^x)

	double(double) twoToThePow = pow(2,?);

We could even apply both arguments to give us a function that returns 
the same thing all the time:

	double() nine = pow(3,2) // No no no ... this won't work

The above actually generates an error saying 'Expression of type double 
cannot be assigned to variable of type double()' . Thats because moto 
thinks the expression 'pow(3,2)' is a function call, not a function 
identifier. To clarify the situation you need to use the '&' operator.

	double() nine = &pow(3,2) // Bingo!

Congratulations, we've crated a function that returns 9 all the time :)

Callbacks
------------------------

Suppose we have a Vector v. We can say

	void(Object) add = v.add;

The above defines a new function add() which, every time it is called, 
adds an Object to v. This is actually a powerful example of partial 
application. Behind the scenes all methods secretly take the instance 
of the object they are called on as an argument. By identifying 'v.add' 
we are saying we want the 'add method on the Vector currently assigned 
to v'.  If v were to be assigned a different vector later on the add 
function we just defined would still add objects to the original Vector.

So what makes this so powerful ? Lets look at some examples

// Cloning a Vector
v1.elements().each(v2.add);

// Pruning a Vector of duplicates
Stringset s1 = new Stringset()
v1.elements().each(<void(Object)>s1.add);
s1.elements().each(v2.add);

// Printing out the elements in a hash (SymbolTable)
void outputNV(Object n,SymbolTable s) { print <String>n +" => 
"+<String>s.get(<String>n)+"\n"; }
stab.keys().each(outputNV(?,stab));

// Inverting a hash
void valueToKey(Object oldkey, SymbolTable src, SymbolTable dest) {
	dest.put(<String>src.get(<String>oldkey),oldkey);  }
SymbolTable namesur = new SymbolTable();
surname.keys().each(valueToKey(?,surname,namesur));