John Jones on Thu, 11 Oct 2007 22:52:30 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Functions as first-class objects


Hi,

I may be doing something stupid, but I couldn't successfully apply the patch (I tried against 2.3.2 and against cvs and parts were rejected in both cases).

But, this is a feature I wished gp had so I am glad to see it might be incorporated. Hopefully "map(function, vector)" and "select(vector, function)" can then become standard gp functions.

John

Bill Allombert wrote:
Hello PARI-dev,

I would like to discuss moving user functions to first-class objects,
and add support for anonymous functions and closures.
The attached (-p1) patch implement that. Interestingly this patch
reduces the code size while adding features.

The idea is to remove the distinction between variables and functions:
a function would just be a variable that hold a function object
(of type t_CLOSURE in my patch). This means that functions could be
passed as parameter, store in local variable and returned by a function.

The consequence are far-reaching, so I would really appreciate comments.
I would like to keep the syntax in the spirit of GP.

1) We need new syntax to define anonymous functions:
The patch adds the following syntax:
 * (x1,...,xn)->EXPR : create an anonymous function.
 * x1->EXPR is accepted as a short-hand for (x1)->EXPR
 * f(x1,...,xn)=EXPR is accepted as a short-hand for f=(x1,...,xn)->EXPR
 * (EXPR)(x1,...,xn) evaluate the expression EXPR. If the result is a
   function, it call it on (x1,...,xn), else it fails.
Oddity:
 * Nullary anonymous functions are defined by
()->EXPR
 * The parens in (EXPR)(x1,...,xn) tend to be annoying:
 (%34)(5), (f(5))(6), etc.
 * GP does not know about tuples thought the left part of (x1,...,xn)->EXPR
looks like a tuple and the patch provide no support for currying/uncurrying:
x->y->x+y and (x,y)->x+y require different calling syntax.
 * There is no syntactic sugar for basic operations on functions like
 slice: x->f(x,56), composition x->f(g(x)), etc.

2) We have to print functions since they are objects now.
 * The patch call all function to be printed as
(x1,...,xn)->EXPR even if they were defined through f(x1,...,xn)=EXPR
because the latter is actually an affectation and that would break
copy-paste:
? f(x)=x^4+1
%1 = (x) -> x^4+1
? g=(x) -> x^4+1
%2 = (x) -> x^4+1
? f(x)==g(x)
%3 = 1
 * Actually closures break copy-paste because they refer to 'hidden'
data:
? f(x)=y->x+y
%4 = (x) -> y->x+y
? f(5)
%5 = (y) -> x+y
? (%5)(6)
%6 = 11
? ((y) -> x+y)(6)
%7 = x + 6

3) Incompatibilities:
 * f(x)=x^4+1 is equivalent to f=(x)->x^4+1 which return the 'value'
(x)->x^4+1 instead of void:
? f(x)=x^4+1
%1 = (x) -> x^4+1
 * Calling a function without () no more evaluate it:
? f
%2 = (x) -> x^4+1

4) Deficiencies
 * The patch does not provide any low-level operations on closures.
 * Built-in functions are not first-class objects, and there are no
obvious way to encapsulate them in a user function, due to some
prototype code which have now user functions equivalent.
 * While functions act as closure with respect to lexically-scoped local
variables, variables values changes occuring after the function is
defined are ignored.
 * It is not possible to define recursive anonymous functions (short
of the Y combinator). Maybe we need to add a 'self' construction:

? g(f)=x->if(x,x*f(x-1),1)
%17 = (f) -> x->if(x,x*f(x-1),1)
? fix=f->(x->f(y->(x(x))(y)))(x->f(y->(x(x))(y)))
%18 = (f) -> (x->f(y->(x(x))(y)))(x->f(y->(x(x))(y)))
? (fix(g))(6)
%19 = 720

That's all for today :)

Cheers,
Bill

PS: I dedicate this patch to Henri Cohen for his birthday.
Happy birthday, Henri!