Skip to content

[SQL] Support for nested (pure) lambda expressions APPLY(a, a -> APPLY(b -> b + 1)) - #6723

Merged
mihaibudiu merged 1 commit into
feldera:mainfrom
mihaibudiu:nested-lambda
Aug 1, 2026
Merged

[SQL] Support for nested (pure) lambda expressions APPLY(a, a -> APPLY(b -> b + 1))#6723
mihaibudiu merged 1 commit into
feldera:mainfrom
mihaibudiu:nested-lambda

Conversation

@mihaibudiu

Copy link
Copy Markdown
Contributor

The syntax allows them, but the implementation had a few bugs.
This needs a Calcite fix as well: apache/calcite#5119

I also used Claude to perform a very broad audit of the handling of lambda expressions in the compiler, which uncovered some bugs, in particular in the implementation of CSE.

  • Unit tests added/updated

@mihaibudiu
mihaibudiu marked this pull request as draft July 25, 2026 00:55

@mythical-fred mythical-fred left a comment

Copy link
Copy Markdown

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Draft review, high-level only.

Nice work. The invariants block on DBSPClosureExpression is the kind of documentation this codebase should have more of — it makes the rest of the diff auditable rather than "trust me". Two design-level thoughts worth chewing on before this leaves draft:

1. deepCopy() semantics are a footgun. The docstring correctly notes that copies share DBSPParameter objects because ParameterFieldUse keys results by them, and that callers who insert a copy into a tree containing the original must remember to freshen. In this PR you added exactly that freshen step in BetaReduction (for needsDeepCopy) and ensureTree (for duplicated subtrees). That's two use sites already. Every future caller of deepCopy() that keeps both trees will hit the same invariant, silently produce a malformed IR, and only crash in CanonicalForm — which is exactly what testEnsureTreeWithLambda documents. Worth considering:

  • Split into deepCopyReplacing() (shares params — used when the copy replaces the original) vs deepCopyEmbedding() / deepCopyFresh() (freshens nested closures — used when both copies coexist), or
  • Have deepCopy() freshen by default and add an explicit deepCopyForReplacement() for the ParameterFieldUse case (which is the rarer, more specialised path).

Either way, encode the invariant in the type / API name rather than in a comment.

2. Per-closure CSE map — correctness is clear, but re-check the "outermost gets everything left over" rule. In ExpressionsCSE.postorder(DBSPClosureExpression) you decide insert = outer || assign.owner == node. That's right for lambdas whose bodies don't reference outer variables (the "pure" case documented in the new invariant). But the invariant explicitly carves out post-lowering flatmaps that DO capture. In that case an assignment owner may be a nested-and-capturing closure and the outer closure is still marked outer. Is there a test after LowerCircuitVisitor that exercises this path? testLambdaCse and testNestedLambdaStreaming are pre-lowering. If the post-lowering DAG happens to work today it's by accident, and the "purity" invariant on DBSPClosureExpression says as much — but the invariant only warns readers, it doesn't guard ExpressionsCSE itself. Worth an explicit Utilities.enforce(closure.isPure()) or equivalent in the CSE entry point, or a targeted test after lowering.

Smaller stuff:

  • MonotoneTransferFunctions.preorder(DBSPClosureExpression) now treats a nested closure as opaque non-monotone. Good, but the comment should say why the analysis is safe (the operator function's monotonicity does not depend on the lambda body's monotonicity because…) rather than just what it does. Future maintainers will otherwise wonder if they can improve precision here.
  • RewriteNow correctly upgrades the internal-error assertion into a CompilationError. Good user-facing message, and the position range from closure.getNode() should give a decent squiggle.
  • queryFailingInCompilation("SELECT transform(array[array[1]], a -> transform(a, a -> a + 1))", "Duplicate lambda parameter 'a'") — is that shadowing prohibition principled, or a workaround for the ResolveReferences implementation? SQL scoping is usually happy with inner-lambda shadowing (see e.g. Snowflake's HOFs). Not a blocker, but worth a sentence in the release notes.

Leaving as COMMENT since it's a draft. I'll do a proper line-by-line pass once you flip it to ready.

@mihaibudiu
mihaibudiu marked this pull request as ready for review July 28, 2026 20:52
@Override
protected void map(DBSPExpression expression, DBSPExpression result) {
ValueNumbering.CanonicalExpression canon = this.numbering.get(expression);
DBSPClosureExpression owner = this.enclosingClosure();

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

you know what would be nice, an doc comment on this function with an example of how an expression gets transformed

// This may be called without an operator context, when e.g.,
// analyzing user-defined functions.
if (canon != null) {
if (canon != null && owner != null) {

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

missed opportunity to name it cannon
but canon is odd because it's also an english word maybe you call it canon_expr or canonExpr in java style I guess

@mihaibudiu
mihaibudiu enabled auto-merge July 30, 2026 19:01
@mihaibudiu
mihaibudiu added this pull request to the merge queue Jul 30, 2026
@github-merge-queue
github-merge-queue Bot removed this pull request from the merge queue due to failed status checks Jul 30, 2026

@mythical-fred mythical-fred left a comment

Copy link
Copy Markdown

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

All three concerns from my draft review are addressed:

  1. deepCopy semantics: documented in the DBSPClosureExpression invariant docstring + FreshenParameters helper freshens nested closure params wherever needed (ensureTree, BetaReduction). Not the API split I floated, but the approach is coherent and the helper makes it hard to forget.
  2. Per-closure CSE: cseVariables keyed by DBSPClosureExpression + enclosingClosure() scoping + assign.owner == node insertion guard. Correct for move-capture Rust closures.
  3. MonotoneTransferFunctions: comment now explains why opaque non-monotone is safe ("variables are not tracked by this analysis").

Tests cover the important cases: context cloning (testLetEquivalenceContextUnchanged), parameter freshening on DAG→tree (testEnsureTreeWithLambda), per-closure CSE (testLambdaCse), monotone acceptance (testNestedLambdaStreaming), duplication (testLambdaDuplication), and error paths (duplicate params, NOW() in lambda, enclosing-scope references).

LGTM.

…Y(b -> b + 1))

Signed-off-by: Mihai Budiu <mbudiu@feldera.com>
@mihaibudiu
mihaibudiu enabled auto-merge July 31, 2026 22:28
@mihaibudiu
mihaibudiu added this pull request to the merge queue Jul 31, 2026
@github-merge-queue
github-merge-queue Bot removed this pull request from the merge queue due to failed status checks Jul 31, 2026
@mihaibudiu
mihaibudiu added this pull request to the merge queue Jul 31, 2026
Merged via the queue into feldera:main with commit 3c0f128 Aug 1, 2026
1 check passed
@mihaibudiu
mihaibudiu deleted the nested-lambda branch August 1, 2026 02:36
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants