Skip to main content

vortex_array/expr/lambda/
mod.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4//! Lambdas, the function arguments of higher-order scalar functions such as `list_transform`.
5//!
6//! A [`Lambda`] is a list of parameter names and a body that reads them with
7//! [`var`](crate::expr::var). A function that takes a lambda keeps it in its options. When the
8//! function's node is bound, it binds the lambda to its parameters' dtypes, once, and keeps the
9//! [`BoundLambda`] instead.
10//!
11//! Binding turns the lambda into an ordinary expression over a struct of its inputs, one field per
12//! parameter: `@x` becomes `$.x`. To run it, the function puts the parameters' arrays in that
13//! struct, such as one row per list element, and applies the bound body to it. The body reads
14//! nothing but its parameters, so the function's children are everything it reads.
15
16#[cfg(test)]
17mod tests;
18
19use std::fmt;
20use std::fmt::Display;
21use std::fmt::Formatter;
22
23use itertools::Itertools;
24use vortex_error::VortexExpect;
25use vortex_error::VortexResult;
26use vortex_error::vortex_bail;
27use vortex_error::vortex_ensure;
28
29use crate::ArrayRef;
30use crate::IntoArray;
31use crate::arrays::StructArray;
32use crate::dtype::DType;
33use crate::dtype::FieldName;
34use crate::dtype::FieldNames;
35use crate::dtype::Nullability;
36use crate::dtype::StructFields;
37use crate::expr::BoundExpression;
38use crate::expr::Expression;
39use crate::expr::get_item;
40use crate::expr::root;
41use crate::expr::traversal::NodeExt;
42use crate::expr::traversal::Transformed;
43use crate::expr::traversal::TraversalOrder;
44use crate::expr::traversal::pre_order_visit_down;
45use crate::scalar_fn::internal::row_count::RowCount;
46use crate::validity::Validity;
47
48/// Parameter names and a body: the function argument of a higher-order scalar function, as
49/// written.
50///
51/// The body is an ordinary [`Expression`] that reads its parameters with
52/// [`var`](crate::expr::var), and nothing else from outside the lambda.
53///
54/// ```rust
55/// # use vortex_array::expr::{Lambda, checked_add, lit, var};
56/// let lambda = Lambda::new(["x"], checked_add(var("x"), lit(1_i32))).unwrap();
57/// assert_eq!(lambda.to_string(), "(x) -> (@x + 1i32)");
58/// ```
59#[derive(Clone, Debug, PartialEq, Eq, Hash)]
60pub struct Lambda {
61    params: FieldNames,
62    body: Expression,
63}
64
65impl Lambda {
66    /// Create a lambda with these parameters and body.
67    ///
68    /// Returns an error when a parameter repeats, or when the body reads from outside the lambda:
69    /// `$` or a column, another lambda's parameter, or the scan's `row_idx()` or `row_count()`.
70    pub fn new(
71        params: impl IntoIterator<Item = impl Into<FieldName>>,
72        body: Expression,
73    ) -> VortexResult<Self> {
74        let params: FieldNames = params.into_iter().map(Into::into).collect();
75        if let Some(param) = params.iter().duplicates().next() {
76            vortex_bail!("lambda parameter {param} is declared more than once");
77        }
78        pre_order_visit_down(&body, |node: &Expression| {
79            vortex_ensure!(
80                !reads_outside_lambda(node, params.as_ref()),
81                "lambda ({}) can only read its parameters, not {node}; reading anything else is \
82                 not supported yet",
83                params.iter().format(", ")
84            );
85            Ok(TraversalOrder::Continue)
86        })?;
87
88        Ok(Self { params, body })
89    }
90
91    /// The parameter names, in order.
92    pub fn params(&self) -> &[FieldName] {
93        self.params.as_ref()
94    }
95
96    /// The body, as written.
97    pub fn body(&self) -> &Expression {
98        &self.body
99    }
100
101    /// The dtype of the body, given the parameters' dtypes, without binding it.
102    pub fn return_dtype(&self, param_dtypes: &[DType]) -> VortexResult<DType> {
103        let inputs = inputs_dtype(self.param_fields(param_dtypes)?);
104        self.body_over_inputs().return_dtype(&inputs)
105    }
106
107    /// Bind the body to these parameter dtypes: `@x` becomes `$.x`, a field of the struct of the
108    /// lambda's inputs.
109    ///
110    /// A function that takes a lambda calls this from its `bind_options`, so the body is bound
111    /// once, with the node that holds it, and never while the function runs.
112    pub fn bind(&self, param_dtypes: &[DType]) -> VortexResult<BoundLambda> {
113        let params = self.param_fields(param_dtypes)?;
114        let body = self
115            .body_over_inputs()
116            .bind(&inputs_dtype(params.clone()))?;
117        Ok(BoundLambda { params, body })
118    }
119
120    /// Whether nothing in the body can fail, so that the body may run over values whose results
121    /// are never read, such as dictionary values that no row uses.
122    pub fn is_infallible(&self) -> bool {
123        let mut infallible = true;
124        pre_order_visit_down(&self.body, |node: &Expression| {
125            infallible &= node
126                .as_scalar()
127                .is_none_or(|scalar_fn| scalar_fn.signature().is_infallible());
128            Ok(if infallible {
129                TraversalOrder::Continue
130            } else {
131                TraversalOrder::Stop
132            })
133        })
134        .vortex_expect("expression traversal cannot fail");
135        infallible
136    }
137
138    fn param_fields(&self, param_dtypes: &[DType]) -> VortexResult<StructFields> {
139        vortex_ensure!(
140            param_dtypes.len() == self.params.len(),
141            "lambda {self} needs one dtype per parameter, got {}",
142            param_dtypes.len()
143        );
144        Ok(StructFields::new(
145            self.params.clone(),
146            param_dtypes.to_vec(),
147        ))
148    }
149
150    /// The body over the struct of the lambda's inputs, where `@x` reads the field `x`.
151    ///
152    /// A lambda in the body is a function's options, which this leaves alone: its variables are its
153    /// own parameters.
154    fn body_over_inputs(&self) -> Expression {
155        self.body
156            .clone()
157            .transform_down(|node| {
158                Ok(match &node {
159                    Expression::Variable(name) => Transformed {
160                        value: get_item(name.clone(), root()),
161                        changed: true,
162                        order: TraversalOrder::Skip,
163                    },
164                    _ => Transformed::no(node),
165                })
166            })
167            .vortex_expect("expression traversal cannot fail")
168            .into_inner()
169    }
170}
171
172/// The struct of a lambda's inputs, one field per parameter.
173fn inputs_dtype(params: StructFields) -> DType {
174    DType::Struct(params, Nullability::NonNullable)
175}
176
177impl Display for Lambda {
178    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
179        write!(f, "({}) -> {}", self.params.iter().format(", "), self.body)
180    }
181}
182
183/// A [`Lambda`] bound to its parameters' dtypes, ready to run.
184///
185/// The body is a [`BoundExpression`] over the struct of the lambda's inputs, one field per
186/// parameter: `@x` was bound as `$.x`.
187#[derive(Clone, Debug, PartialEq, Eq, Hash)]
188pub struct BoundLambda {
189    params: StructFields,
190    body: BoundExpression,
191}
192
193impl BoundLambda {
194    /// The parameters' names and dtypes, in order.
195    pub fn params(&self) -> &StructFields {
196        &self.params
197    }
198
199    /// The bound body, over the struct of the lambda's inputs.
200    pub fn body(&self) -> &BoundExpression {
201        &self.body
202    }
203
204    /// The dtype of the body.
205    pub fn dtype(&self) -> &DType {
206        self.body.dtype()
207    }
208
209    /// Whether the lambda is bound to these parameter dtypes.
210    pub fn is_bound_to(&self, param_dtypes: &[DType]) -> bool {
211        self.params.fields().eq(param_dtypes.iter().cloned())
212    }
213
214    /// Whether nothing in the body can fail. See [`Lambda::is_infallible`].
215    pub fn is_infallible(&self) -> bool {
216        let mut infallible = true;
217        pre_order_visit_down(&self.body, |node: &BoundExpression| {
218            infallible &= node
219                .as_scalar()
220                .is_none_or(|scalar_fn| scalar_fn.signature().is_infallible());
221            Ok(if infallible {
222                TraversalOrder::Continue
223            } else {
224                TraversalOrder::Stop
225            })
226        })
227        .vortex_expect("bound expression traversal cannot fail");
228        infallible
229    }
230
231    /// Evaluate the body over `len` rows of `args`, one array per parameter, with the dtypes the
232    /// lambda is bound to. They become the fields of the struct the body is applied to.
233    ///
234    /// The result is computed later, like any applied expression, so errors from running the body
235    /// come from executing it.
236    pub fn evaluate(&self, args: Vec<ArrayRef>, len: usize) -> VortexResult<ArrayRef> {
237        vortex_ensure!(
238            args.len() == self.params.nfields(),
239            "lambda {self} needs one array per parameter, got {}",
240            args.len()
241        );
242        for ((name, dtype), arg) in self
243            .params
244            .names()
245            .iter()
246            .zip(self.params.fields())
247            .zip(&args)
248        {
249            vortex_ensure!(
250                arg.dtype() == &dtype,
251                "lambda {self}: parameter {name} is bound to {dtype}, not {}",
252                arg.dtype()
253            );
254        }
255        let inputs = StructArray::try_new(
256            self.params.names().clone(),
257            args,
258            len,
259            Validity::NonNullable,
260        )?
261        .into_array();
262        inputs.apply_bound(&self.body)
263    }
264}
265
266impl Display for BoundLambda {
267    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
268        write!(
269            f,
270            "({}) -> {}",
271            self.params.names().iter().format(", "),
272            self.body
273        )
274    }
275}
276
277/// Whether `node`, in the body of a lambda with these parameters, reads a value from outside the
278/// lambda, which lambdas can't do yet: `$`, another lambda's parameter, or the scan's `row_idx()`
279/// or `row_count()`. The scan replaces those two before anything runs, but never looks inside a
280/// lambda's body.
281fn reads_outside_lambda(node: &Expression, params: &[FieldName]) -> bool {
282    match node {
283        Expression::Root => true,
284        Expression::Variable(name) => !params.contains(name),
285        // `row_idx` is defined in vortex-layout, so it is recognized by its id.
286        Expression::Scalar { scalar_fn, .. } => {
287            scalar_fn.is::<RowCount>() || scalar_fn.id().as_ref() == "vortex.row_idx"
288        }
289    }
290}