Implement Bound Expressions

[mhk197]

Introduce BoundExpression and Expression::bind. Binding an Expression walks the expression tree and resolves scope-dependent references (e.g. for upcoming lambda variables), type-checks the tree, and records a dtype on every node. It should be bound once, before an expression is actually applied.

In addition, make root an expression rather than a scalar function. root cannot be executed and does not derive dtype from its children.

Motivation

• Types are derived on demand, repeatedly. return_dtype re-walks the whole subtree on every call with no memoization, so any pass wanting types at more than one node re-walks overlapping subtrees.
• No validated form exists. Nothing sits between a tree someone constructed and arrays, so no consumer can assume well-typedness.
• Prepare for introducing lambda variables, lambdas, and higher-order functions. A lambda's type isn't knowable from itself or its body, it comes from the enclosing higher order function and its arguments. For example, in list_transform(col("values"), λx. …), x's type is the element type of col("values"). This means that typing is not a bottom-up fold anymore, as is assumed by return_dtype today.

Proposed API

Change Expression to:

pub enum Expression {
    Scalar {
        scalar_fn: ScalarFnRef,
        children: Arc<Vec<Expression>>,
    },
    Root,
}

Implement BoundExpression as:

pub struct Scope {
    root: DType,
}

pub struct BoundExpression {
    kind: BoundKind,
    dtype: DType,
}

pub enum BoundKind {
    Scalar {
        scalar_fn: ScalarFnRef,
        children: Arc<Vec<BoundExpression>>,
    },
    Root,
}

impl Expression {
    /// Type-check the whole tree in one walk, resolving `Root` against the scope.
    pub fn bind(&self, scope: &Scope) -> VortexResult<BoundExpression>;
}

[joseph-isaacs]

The thing I am not 100% sure about is

pub struct BoundExpression {
    kind: BoundKind,
    dtype: DType, // <--- should this be at the root and derived each time or cache at each level?
}