Support for lambdas

[divarvel]

Adding support for .any() / .all() on sets (and the upcoming list and map types) would require higher order functions, to pass arbitrary predicates.

Making && and || lazy in their second argument could also be implemented through lambdas (laziness can be implemented with a lambda taking no arguments). Directly implementing lazy evaluation in the stack machine is not possible, as far as I know. The best we can do is making evaluation non-strict and capable of recovering from errors, but not actually lazy.

Those two use cases would benefit greatly from lambdas. Thankfully the expression evaluation model is quite simple, with no local bindings, mutability nor lifetime management, so we wouldn't run into typical issues with closures.

How

Stack machine

• introduce new Closure operation that carries a list of parameters and a list of ops
• modify the stack machine evaluator to push the closure op to the stack
• provide the ability to perform a nested run with the closure
• reuse the existing variables to access closure parameters

Note: nested lambdas is necessary for laziness. Nested lambdas for higher-order functions might be restricted if we're not comfortable with it. Since we are using variables for lambda parameters, the simplest solution is to forbid variable shadowing completely. This way we don't have to normalize variable names (eg with DeBruijn indices) and use them directly. Even with normalization, we would have to carry variable names around to be able to print expressions.

Recursive calls

Running closures as recursive calls to Expression.evaluate() works well, but it introduces recursion in the model.

Unrolling recursion for boolean operators works, by making the ops stack mutable and pushing ops to it when evaluating a closure. This seems to break stuff when combined with recursive evaluation in .all() / .any().

For .all() (resp .any()), it was possible to unroll the recursive call by generating a chain of && (resp ||) but that generated a lot of work for the op evaluator. It was simpler to recurse here.

To summarize: while it is beneficial to remove recursion, doing so makes the evaluator way more complex and do a lot of work that the rust compiler would do for us at runtime.

Parser

• introduce a new sigil for lambda parameters (eg $ _), or a new syntax for introducing local bindings
• modify the ops generation code to bracket && and || right branches with Closure and emit new operations that work with lambdas

Examples

Laziness

true || "x" == false would be turned into [true, Closure([], ["x", false, ==]), LazyOr] after parsing.

Op	Stack after
	[]
true	[Term(true)]
Closure([], ["x", false, ==])	[Term(true), Closure([], ["x", false, ==])]
LazyOr	[true]

Here, the Closure() stack element is completely dropped because it does not need to be evaluated

true && ("x" == "y" || true) would be turned into true, Closure([], ["x", "y", ==, Closure([], [true]), LazyOr]), LazyAnd after parsing.

Op	Stack after
	[]
true	[true]
Closure(…)	[true, Closure([], ["x", "y", ==, Closure([], [true]), LazyOr])]
LazyAnd	recursion starts
	[]
"x"	["x"]
"y"	["x", "y"]
"=="	[false]
Closure(…)	[false, Closure([], [true])]
LazyOr	recursion starts
	[]
true	[true]
LazyOr	[true] recursion ends
LazyAnd	[true] recursion ends

Higher-order function

[1,2,3].any($p -> $p >= 2) would be turned into [1,2,3], Closure([p], [$p, 2, >=]), any after parsing.

Op	Stack after	Context
	[]	{}
[1,2,3]	[1,2,3]	{}
Closure(…)	[1,2,3], Closure([p], [$p, 2, >=])]	{}
any	recursion starts	{}
	[]	{p: 1}
$p	[1]	{p: 1}
2	[1,2]	{p: 1}
>=	[false]	{p: 1}
	[]	{p: 2}
$p	[2]	{p: 2}
2	[2,2]	{p: 2}
>=	[true]	{p: 2}
any	[true] recursion ends	{}