Add lambdas and variables for higher-order scalar functions - #10502

Summary

Adds lambdas, the function arguments of higher-order scalar functions such as list_transform (#10503). A lambda is a list of parameter names and a body that reads them through variables. A function that takes a lambda keeps it in its options, binds it once when its node is bound, and runs the bound lambda over values it makes from its inputs.

Variables

• var("x") builds Expression::Variable("x"): a leaf, like $, that reads the parameter x of the enclosing lambda.
• It displays as @x, so @x (a parameter) and $.x (a field of the input) never look alike.
• A variable exists only in a written body. Binding the lambda turns @x into $.x, a field of the struct of the lambda's inputs (see below), so BoundExpression is unchanged.
• Anywhere else it fails to bind, type, apply and serialize with "variable @x is not a parameter of an enclosing lambda".

Lambdas

let lambda = Lambda::new(["x"], checked_add(var("x"), lit(1_i32)))?;
// (x) -> (@x + 1i32)
let bound = lambda.bind(&[DType::Primitive(PType::I32, NonNullable)])?;
// (x) -> ($.x + 1i32): an ordinary bound expression over the struct {x: i32}

• Lambda is the lambda as written: params() and body(), an Expression.
• Lambda::new rejects a repeated parameter, and a body that reads from outside the lambda: $ or a column, another lambda's parameter, or the scan's row_idx() and row_count(). Constants are fine, such as the literal set in x -> list_contains([2, 3], x).
• bind(param_dtypes) turns the lambda into an ordinary expression over a struct of its inputs, one field per parameter: each @x becomes $.x, and the body is bound to that struct. It returns a BoundLambda.
• return_dtype(param_dtypes) gives the body's dtype over the same struct, without binding it, the way Expression::return_dtype does for a whole expression.
• BoundLambda is the lambda bound: params() with their dtypes, body(), an ordinary BoundExpression over the struct, dtype(), the body's, and is_bound_to(param_dtypes).
• BoundLambda::evaluate(args, len) puts one array per parameter in that struct and applies the bound body to it. The arrays must have the dtypes the lambda is bound to. It binds nothing, and like any applied expression, the result is computed later.
• is_infallible(), on both, says whether nothing in the body can fail, so a function knows whether the body may run on values whose results are never read, such as dictionary values no row uses.

Using a lambda in a function

A function's options are an enum of the lambda as written and as bound. Its children are its ordinary inputs.

enum MyFnOptions {
    Lambda(Lambda),
    Bound(BoundLambda),
}

impl ScalarFnVTable for MyFn {
    type Options = MyFnOptions;

    fn bind_options(&self, options: &MyFnOptions, args: &[DType]) -> VortexResult<Option<MyFnOptions>> {
        match options {
            MyFnOptions::Lambda(lambda) => Ok(Some(MyFnOptions::Bound(lambda.bind(/* param dtypes, from args */)?))),
            MyFnOptions::Bound(lambda) => {
                vortex_ensure!(lambda.is_bound_to(/* param dtypes, from args */), "bound to other dtypes");
                Ok(None)
            }
        }
    }

    fn execute(&self, options: &MyFnOptions, args: &dyn ExecutionArgs, ctx: &mut ExecutionCtx) -> VortexResult<ArrayRef> {
        let MyFnOptions::Bound(lambda) = options else { vortex_bail!("not bound") };
        lambda.evaluate(vec![/* the parameters' arrays, made from args */], len)
    }
}

• ScalarFnVTable::bind_options(options, arg_dtypes) is new, hidden from the docs, and does nothing by default. It runs whenever a bound node is built, and whenever a ScalarFnArray is built from its children, before return_dtype. That's where a function binds its lambda, once, so execute finds it bound.
• A rebuilt node calls bind_options again, possibly with other dtypes, so a function checks that options already bound still fit, and errors if they don't. No rewrite today changes the dtype a lambda is bound to.
• An Expression holds the written lambda, and a BoundExpression or an array holds the bound one.
• The body reads only its parameters, so the function's children are everything it reads. Binding, traversal, replace, field pruning and pushdown see an ordinary node and never look inside the lambda.
• Lambdas nest: a call that takes a lambda is an ordinary node inside another lambda's body. Its children are part of the outer body, so they can read the outer parameters, and its own lambda reads only its own. Binding the outer lambda binds the inner one.

(xs) -> vortex.list.transform(@xs, (y) -> (@y + 1i32))

Not supported yet

• Reading anything outside the lambda, such as x -> x + $.a.
• Serializing a lambda: a function that takes one is not serializable yet.