[Omake] Semantics for curried functions, partial applications and keyword argument.

[Jason Hickey]

Hi Aleksey,

Before making radical changes to keyword arguments, let me explain  
how they currently work.  Of course it is open to discussion/revision.

Here is the current semantics.

    - All parameters, keyword or not, are private.
    - The order of keyword parameters/arguments does not matter.
    - Non-keyword parameters cannot be named as keyword parameters.
    - It is illegal to provide an argument for a non-existent keyword  
parameter.
    - Functions with only keyword parameters are considered 0-arity.
    - primitives are passed keyword arguments -- but currently all
      of them abort if they get any

I tried other semantics, but the reasons for these choices are to  
keep both the semantics and implementation simple.

The function value describes a lot about the implementation.

>  | ValFun         of arity * env * keyword_set * var list * exp  
> list * export

    arity: number of "real" arguments (used only by Sequence.length)
    env: private environment
    keyword_set: allowed keywords
    var list: parameters, in order
    exp list: function body
    export: exports

A function definition f(x = e, ...) = ... adds x to env, x is always  
private.
In an application f(x = e, ...), x must be in the keyword_set.  If it  
is, then the definition is added to the env.

-------

Before describing the implementation, there is the basic question  
about semantics of partial application and what exactly is  
supported.  Let's call a function that is can be used with too many/ 
too few arguments a "partial function".  Bad terminology, but I don't  
know what else to call it.

My current inclination is as follows.

    - Partial functions must be annotated.
    - The partial status of a function is dynamically determined.
    - Application is eager; keyword arguments are taken aggressively.

* If there are enough/too many arguments, the application happens,  
and keywords are selected aggressively.  Order does not matter.

    partial.f(A=2, x) = ...

    f(B=4, 1, 2, A=3)    # f gets (A=3, 1), but not (B=4, 2)
    f(0)                 # f is applied, with A=2

* Normal non-partial functions are checked strictly, as they are now.

    partial.f(A=2, x) =
       fun(y, z, B=3, C=4) => ...

    f(0, 1, D=5)   # error: no D argument
    f(0, 1)        # error: too few arguments
    f(0, 1, 2, 3)  # error: too many arguments

* What happens with too few arguments?

   partial.f(A=2, B=3, x, y) =
      add($A, $B, $x, $y)

   g1 = $(f 0, A=4)   # g1's remaining parameters are (B=4, y)
   g2 = $(f C=5)      # legal, but it may raise an error later
   f(0)               # is this an error?

As I say, this is my inclination.  The implementation seems  
reasonable.  If there are enough arguments, a partial function is  
applied; any remaining arguments are passed to the returned value.   
If too few arguments, they are collected in the environment.  Partial  
functions would be slightly more expensive to apply than normal ones,  
but normal ones would not be affected.

Bonus: we could add some varargs-like primitives.

    partial.my-printf() =
        argv = $(va-list)
        ...

There are other kinds of restrictions that could be used instead.
    - partial functions can have no parameters of any form
    - partial functions can have only keyword parameters
    - partial functions can have only normal parameters

----------

Now some specific comments.

On Aug 7, 2007, at 10:14 AM, Aleksey Nogin wrote:

> Here is sketch for a consistent semantics and implementation scheme  
> for curried functions, partial applications and keyword arguments  
> in OMake.
>
> Please let me know what you think.
>
> - Keyword arguments are taken as a way to shadow an "extra" binding  
> in the environment in which the function body will be evaluated.
>   **OPTIONALLY**: The default is to shadow a "private" binding, but  
> other bindings may be specified. E.g.
>    CProgram(..., public.LDFLAGS = ...)
> would be roughly equivalent to
>   section
>     public.LDFLAGS = ...
>     CProgram(...)
> (and if we go with this, we'd probably want to support a "+=" form  
> as well).

I had considered this (the public.LDFLAGS kind of thing), but I think  
it is too complicated.  I suppose it would be ok to do the static  
translation that does this, but that would be unrelated to keyword  
arguments.

For the implementation, if keywords were allowed from all 3 scopes,  
then the keyword table would be separate from the private  
environment, and it would take linear time to process--in the # of  
parameters, not the # of arguments.

Basically, I'm just saying "keep it simple".  However, a omake-style  
"env" function could be pretty cool.  I'm not entirely sure of the  
syntax.

> - **Optional**: We may want to allow referring to even regular  
> arguments by name:
>   f(x, y) =
>     ...
>   g = $(f y = bar)
>   g(foo)
>
>   becomes roughly equivalent to
>   f(x, y) =
>      ...
>   f(foo, bar)

I did this in the old 0.9.9, before all the jumbo branches.  I now  
believe it is a bad idea, because it takes either quadratic time or  
quadratic space to implement.

In addition, it is reasonable to say that a programmer is free to  
reimplement a function.  Its kind of terrible to say that parameter  
names are decided once, and can never be changed.

> - **Optional**: Special syntax for partial applications:
>   I am a bit concerned that without static checking and now with  
> relaxed dynamic checking of the argument counts, mistakes in  
> argument numbers would become too hard to track. One option is to  
> require a special syntax (e.g. use {} in place of () ):
>   - Definitions:
>       f{...} =
>         ...
>     allow f to be curried (applied to "too many" arguments).
>   - Applications:
>       ${f ...}
>     are allowed to be partial (note that there is no f{...} form,  
> only explicit "value ${f ...}" ).
>   - If we go with this, it would be natural to say that referring  
> to arguments by name (previous "option") is allowed only inside $ 
> {...} applications.

I feel the same way.  I'm not sure about the syntax though.   
Alternatively, if we went with the partial.f at a definition, we  
could also use

    $(partial.f ...)

to perform a partial application on any kind of function.

    add1 = $(partial.add 1)

Jason

--
Jason Hickey                  http://www.cs.caltech.edu/~jyh
Caltech Computer Science      Tel: 626-395-6568 FAX: 626-792-4257