Stress testing function application in VeLa yields errors

[dbenn]

VeLa implements higher order functions (HOFs). When "stress testing" function handling by implementing the Y combinator in VeLa, a bug in HOF function application was revealed.

Essentially, when a function returns a function, so long as it is then bound to a variable, it can subsequently be applied to a parameter list. But if it is not bound to a variable, the function application does not work. This is because there is an ambiguity in the mere appearance of adjacent expressions vs the necessity of function application. Whereas in LISP, this:

(print (arbitrary-expression1 arbitrary-expression2))

implies that before println is applied, there is an application of a function represented by arbitrary-expression1 to the rest of the expressions in the list, in VeLa, we have:

print(arbitrary-expression1(arbitrary-expression2))

arbitrary-expression1 could be an anonymous function specified by the function keyword, or a function that returns a function. Consider:

g(f:function):function {
  function(n:integer):integer {
    f(n)
  }
}

cube(n:integer):integer {
  n*n*n
}

g(cube) returns a function that when applied to an integer, returns an integer (a function that applies cube to a single integer parameter in this case). The following works as expected, returning 27:

h <- g(cube)
println(h(3))

while the following does not:

println(g(cube)(3))

Instead, this is what is printed:

3

since the unformatted println outputs an arbitrary number of values, in this case the result of g(cube) (an anonymous function) followed by 3, whereas my intention above was for the result of g(cube) to be applied to 3.

So, either the VeLa interpreter must be modified to inspect println's parameter list and perform another round of evaluation before println is applied to the final result, or another special form, such as apply should be added to the language signifying that function application is required. This would give us:

println(apply(g(cube) 3))

Some problems with performing a second round of evaluation before println is called, are:

• this would make a special case out of what appears in a parameter list; if VeLa becomes a compiled language, this would complicate the generated code (whether native or VM byte codes);
• it may really be that the programmer intended g(cube)'s result and 3 to be printed separately by println;
• when should the evaluation stop?; e.g. if g(cube) applied to 3 yielded another function, should that be evaluated too?; an infinite loop could result.

Adding delimiters to parameter lists and other lists (commas, semi-colons) could be used to give VeLa cues to implicit function evaluation, but would not help with the 3rd point above re: the end of evaluation.

apply may also help in program understanding in cases where ambiguity is possible.

It may be that there will be other problems arising from the implementation of the Y combinator in VeLa, but this same error does occur at one of the stages of Y combinator evaluation and my suspicion is that the current implementation is the cause. See https://github.com/AAVSO/VStar/tree/issue-105-function-application/script/VeLa/Y for example test VeLa code.

[dbenn]

Adding an apply alternative to this parser rule would make sense:

funcall
:
    funobj LPAREN
    (
        expression
    )* RPAREN
;

e.g.

funcall
:
    ((funobj LPAREN) | (APPLY LPAREN expression))
    (
        expression
    )* RPAREN)
;

The VeLa parse tree visitor could turn both into ASTs with the root node FUNCALL or probably simpler, an APPLY special form could be added to the interpreter. FUNCALL is already complicated enough.

[dbenn]

Note that special forms or functions such as apply are not uncommon in languages with HOFs.

[dbenn]

This last example and the print(g(cube)(3)) example now works, however g(cube) must be wrapped in parentheses currently, e.g. print((g(cube))(3)) in lieu of APPLY. Even this did not work before changing the grammar and expression visitor code. Code commits pending.

[dbenn]

Will next return to the Y Combinator to see what still breaks.

[dbenn]

Y Combinator (steps-along-the-way) test files: https://github.com/AAVSO/VStar/tree/105-may-need-apply-in-vela/script/VeLa/Y

[dbenn]

The problem has has been addressed via a VeLa grammar and interpreter modification.

An apply function may make some code easier to understand but variant types for parameters and return types would be necessary first, unless treated as a special form by the interpreter.

In the interest of moving on and since the code changes have fixed the problem for which this issue was raised, I will create a pull request for this issue and a new issue for apply.