How would you add HOFs to moto ?

	I just wrote up and sent out the following message to some former 
professors of mine. I thought it was a good enough round up of where 
the HOF support in moto is and where its going that I'd re-post it here 
and perhaps you guys might be able to comment or send it out to others 
'in the know' about such things.

-Dave

	As you know I'm working to add Higher Order Function support to my 
programming language, moto (www.projectmoto.org), for it's next 
release. The syntax of moto is very much like that of Java so I went 
looking for languages with a similar syntax that had HOF support. 
However I couldn't find anything I liked very much. Most seemed too 
mathematical and not very practical . So I've come up with a rough 
sketch as to what I would have higher order function / method syntax 
look like in my ideal world and I was hoping to get some expert 
opinions on it.

Problem: Construct a syntax consistent with Java / C++ (sans pointers) 
syntax that can be used to:

1) Define variables that can hold functions / methods
2) Assign existing functions / methods to these variables
3) Define functions that can take functions as arguments and / or 
return functions
4) Create new functions through 'partial application' of more general 
functions
5) Construct anonymous functions inline

Secondary Problem : Provide a syntax that solves the above problems in 
a way that doesn't introduce too many new operators or syntactic ideas. 
Most importantly try to provide the above functionality in a way that 
Java / C++ programmers will at least find familiar if not intuitive.

Proposed Solution:

1) Variable Declaration / Dynamic Type Declaration :

	int() f; // f can hold a function which takes no arguments and returns 
an int
	int(int) g; // g can hold a function which takes an int and returns an 
int
	int(int,String) h; // h can hold a function which takes an int and a 
String and returns an int
	
	int(int()) i; // i can hold a function which takes a function that 
takes no arguments but returns an int. i must also return an int.
	int(int,int()) j;
	int(int(int),String()) k;
	
	int(int())() l;
	int(int,int())(String) m;
	int(int(int),String())(String(),float) n;
	
	int[]() o;
	int[][](int) p;
	int[][][](int,String) q;
	
	int[](int[]()) r;
	int[](int[][],int[]()) s;
	int[][](int(int[]),String[]()) t;
	
	int[](int())() u[];
	int(int[],int())(String[]) v[][];
	int(int[](int[][]),String())(String[](),float[]) w;

The key idea here is that types can be dynamically added to the type 
system / checked based on the following rules:

if X is a type than X[] is a type ... e.g. an array of Xs
if X is a type than X() is a type ... e.g. a function that returns X
if X and Y are types than X(Y) is a type ... e.g. a function that takes 
Y and returns X
if X is a type and Z is a comma delimited list of types than X(Z) is a 
type ... e.g. a function that takes Z and returns X

This allows for avoidance of the C strategy of having to typedef a slew 
of smaller functional types prior to being able to define complex 
higher order types. These types are not really LRk parseable but they 
are parseable with enough flex / bison hackery.

2) Casts to Functional Types :
	
	Object O;

	<int()>O;
	<int(int)>O;
	<int(int,String)>O;
	
	<int(int())>O;
	<int(int,int())>O;
	<int(int(int),String())>O;
	
	<int(int())()>O;
	<int(int,int())(String)>O;
	<int(int(int),String())(String(),float)>O;
	
	<int[]()>O;
	<int[][](int)>O;
	<int[][][](int,String)>O;
	
	<int[](int[]())>O;
	<int[](int[][],int[]())>O;
	<int[][](int(int[]),String[]())>O;
	
	<int[](int())()[]>O;
	<int(int[],int())(String[])[][]>O;
	<int(int[](int[][]),String())(String[](),float[])>O;

Casting in moto is done with angle brackets.

3) Functions that take functions as arguments :
	
	int f1 (int() arg1) {} // f1 is a function that takes the function 
arg1 that takes no arguments and returns an int. f1 returns an int
	int f2 (int() arg1,float() arg2) {}
	int f3 (int(int) arg1,float(String) arg2) {}	
	int f4 (int() arg1,float() arg2) {}
	int f5 (int(int)() arg1,float()(String) arg2) {}

4) Function Identification :
	
	&atoi(<String> ?);
	&isupper(<char> ?);
	&f1 (<int()> ?);
	&f2 (<int()> ?,<float()> ?);
	&f3 (<int(int)> ?,<float(String)> ?);	
	&f4 (<int()> ?,<float()> ?);
	&f5 (<int(int)()> ?,<float()(String)> ?);		
	
	&rf1 (<int()> ?);
	&rf2 (<int()> ?,<float()> ?);
	&rf3 (<int(int)> ?,<float(String)> ?);	
	&rf4 (<int()> ?,<float()> ?);
	&rf5 (<int(int)()> ?,<float()(String)> ?);	

Here the '?' token represents an 'unfilled argument'. Since moto, like 
Java and C++, allows multiple functions with the same name, 
differentiated by the argument count and types, we need a way to 
identify which function we're talking about. Angle brackets surrounding 
a type is the cast operator in moto so the idea behind the above syntax 
is

'&' signals we want a function pointer as opposed to calling the 
function
<type> '?' signals that the i'th argument to the variant of the 
function we're looking for is of the specified type

I have real questions about the need for the '&' operator and have 
attached a separate document on that issue in particular. If possible I 
think I'd like to get rid of it. Its already been pointed out to me 
that with the casts present the '?' token is not needed. However I 
think I want to keep that as '?' takes on additional meaning with 
regard to partial application

5) Assignments of function typed expressions :
	
	boolean(char) myisdigit = &isdigit(<char> ?);
	double(double) mysqrt = &sqrt(<double> ?);
	double(double,int) myldexp = &ldexp(<double> ?,<int> ?);

6) Partial Application used to define new functions :

Suppose pow is a function which takes two doubles and returns the first 
input to the power of the second.

	double(double) square = &pow(<double>?,2);
	double(double) twoToThePower = &pow(2,<double>?);

7) Method Identification / Partial Application with regard to Methods :

	Vector v;
	Enumeration() f = &v.elements();

I really have no idea whether the above syntax will / can work in the 
general case. I have not given it a great deal of thought knowing that 
I will definitely be able to accomplish the necessary functionality 
with anonymous functions.  The basic idea I'm trying represent above is 
that I want to treat methods like partially applied functions i.e. 
their first (hidden) argument is fixed to the value of the object it 
would be called on.

8) Anonymous Functions :

	<double(double)> { return @1 * @1; }; // squares then returns the one 
input
	<int(String)> { return @1 eq @2 ? 0 : @1 gt @2 ? 1 : 0 ; }; // strcmp

I'm introducing the concept of context sensitive variables here which 
I'm not entirely comfortable with. In the above examples @x refers to 
the xth argument passed to the anonymous function. This would be the 
first case in the language in which context sensitive arguments are 
used. Argument typing is preserved because the type of the xth argument 
is retrieved from the cast preceding the function definition. The idea 
behind the syntax comes from inline array instantiation which can be 
triggered by an appropriate cast

<int[]>{1,3,5,7};

I believe you can do the above with (array type){...} in Java. In the 
above example, if the cast is to a functional type, what follows is 
expected to be an embedded block defining the function. Of course there 
is no place in the above syntax for me give the arguments names ... but 
it is an awful concise syntax which I like a lot.

So, I guess my question comes down to: What do you guys think ? Are the 
above syntax ideas intuitive ? sensible ? complete (at least at first 
glance) ?

Thanks again for all your help and advice!

-Dave

Bonus Problem : Can / Should the '&' token be removed from the above 
syntax ?

	This is my question ... I'm trying to consider whether I can get rid 
of the & used for function identifiers. Right now to get the 'address 
of a function' in moto you need to precede the function name with an 
'&' e.g.

int(String) myatoi = &atoi(<String> ?)

The above case would be clear enough without the &

int(String) myatoi = atoi(<String> ?)

and in fact since there is only one variant of the atoi function 
neither of the following would be ambiguous either

int(String) myatoi = atoi(?)
int(String) myatoi = atoi

The problem with doing away with the ampersand comes up with basic 
function pointers when we have a function with two forms, one that 
takes no arguments, and one that takes one or more arguments

void func(){ print 3; }
void func(int i){ print i; }

Object myfunc;
myfunc = func;

'func' in the last case has the potential at least to be ambiguous. We 
could make a rule that 'when multiple variants of a function exist, the 
function name alone identifies the zero-argument variant'

However while the previous rule may disambiguate function pointers, I 
don't think it does so in a very intuitive way ... Also, it doesn't 
begin to address the issues we run into with partial function 
application.

Partial function application is like super currying (its probably 
really just a type of closure ... I don't know enough about functional 
terminology to say this for sure though :) ) . The idea here is to 
create new functions by 'fixing the inputs' of more general functions. 
Consider a function

double pow(double,double)

which returns the first input to the power of the second input. With 
partial application I could define the following two functions

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

Thats pretty darn powerful stuff :) . Now suppose we have a one arg 
function with side effects:

global int count;
void hello(String s ){ print "hello "+s +" "+count++; }

Its clear that calling the above function has the side effect of 
incrementing count. Suppose I want to use the mechanism of partial 
application to 'fix' the function's one input creating another function 
I can call later.

void() myhello = hello("Dave");

but that won't work because the type of the expression 'hello("Dave")' 
is 'void' and not 'void()' i.e. the return value of the hello function. 
I need the '&' to distinguish between a function I'm calling right away 
vs a function I'm defining to call later

void() myhello = &hello("Dave");

Or do I ? With any one of the anonymous function syntaxes I've 
discussed with people I could accomplish the same thing by doing:

void() myhello = <void()>{hello("Dave");} ;

or maybe even

void() myhello = {hello("Dave");} ;

That is, if I can convince the parser not to expect an inline array 
declaration when it sees '{' :) . So its at least clear to me that I 
can do away with the necessity for '&' once I have a way to create more 
general anonymous functions. At the same time '&' may be both clearer 
and shorter in at least some circumstances.

What do you guys think ? Should the '&' stay or go ?