Re: Functions as first-class objects

[John Jones <jj@asu.edu>]

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!
>