Infer closure captures for quotations passed to list combinators #395

New issue

Closed

opened 2026-04-10 23:43:02 +00:00 by navicore · 2 comments

navicore commented

2026-04-10 23:43:02 +00:00

(Migrated from github.com)

Summary

When a quotation is passed directly to list.fold, list.map, or list.filter, and its body needs more inputs than the combinator provides, the compiler should auto-capture the excess from the stack — promoting the quotation to a closure without requiring an explicit Closure[T -- U] type annotation.

Motivation

Currently, closure capture only triggers when the programmer explicitly declares a Closure[...] return type on a word. Quotations passed inline to combinators are always treated as stateless, so any extra context must be threaded through packed accumulators or manual recursion.

Example — evaluating a polynomial with Horner's method during list.fold. The fold quotation needs x (the evaluation point) at every step, but fold only provides (acc, coeff):

# What you want to write:
: eval-poly ( List Int -- Int )
  swap list.reverse swap       # reversed x
  0 [ swap rot gf256-mul bxor ] list.fold
  # ↑ quotation body needs (x, acc, coeff) → 3 inputs
  #   fold provides (acc, coeff) → 2 inputs
  #   x should be auto-captured from the stack
;

# What you have to write today (packed accumulator workaround):
: eval-poly ( List Int -- Int )
  over list.length 1 i.-
  0 eval-poly-loop    # 4-item recursive loop with pick/roll
;

The packed-accumulator approach works but it obscures the algorithm and is error-prone (pick-depth bugs caused an infinite loop during development).

Proposed Change

Typechecker

When type-checking a quotation argument to a combinator whose expected quotation type is fully known:

Infer the quotation body's natural effect (e.g., ( Int Int Int -- Int ))
Compare against the combinator's expected effect (e.g., ( Int Int -- Int ) for fold)
If the body needs more inputs than the combinator provides, run calculate_captures (which already exists in capture_analysis.rs) to determine what to capture
Promote the quotation's type from Type::Quotation to Type::Closure with the inferred captures

Codegen

No changes needed — the closure codegen path already handles captures, environment creation, and invoke_callable dispatch. list.fold and friends already accept both Value::Quotation and Value::Closure via invoke_callable.

Scope

A conservative first version could limit auto-capture to the built-in list combinators (list.fold, list.map, list.filter, list.each) where the expected quotation signature is statically known. This avoids ambiguity in the general case.

Supported Capture Types

Per the existing closure codegen (codegen/words.rs lines 340-379), these types can already be captured: Int, Bool, Float, String, Quotation. Variant and nested Closure captures are not yet supported and would remain an error.

Risk

Medium. The type inference machinery is the most delicate part of the compiler. The key constraint: capture analysis must only trigger when the expected quotation type is unambiguous (i.e., the combinator's signature fully determines the expected effect). Starting with only the built-in list combinators keeps the scope narrow and testable.

Example: What This Enables

# Lagrange basis product via fold (currently requires manual recursion):
: lagrange-basis ( List Int -- Int )
  256 i.+
  [ lagrange-basis-step ] list.fold   # works today (no capture needed)
  8 shr
;

# Polynomial evaluation via fold (currently requires 4-item recursive loop):
: eval-poly ( List Int -- Int )
  swap list.reverse swap
  0 [ swap rot gf256-mul bxor ] list.fold   # x auto-captured
;

# Parameterized filter (currently must hardcode the threshold):
: keep-above ( List Int -- List )
  [ i.> ] list.filter   # threshold auto-captured
;

Context: discovered while implementing Shamir's Secret Sharing in Seq. The Lagrange interpolation and polynomial evaluation algorithms are natural fits for list.fold, but the lack of auto-capture forced fallback to manual recursion with deep pick/roll stack juggling.

## Summary When a quotation is passed directly to `list.fold`, `list.map`, or `list.filter`, and its body needs more inputs than the combinator provides, the compiler should auto-capture the excess from the stack — promoting the quotation to a closure without requiring an explicit `Closure[T -- U]` type annotation. ## Motivation Currently, closure capture only triggers when the programmer explicitly declares a `Closure[...]` return type on a word. Quotations passed inline to combinators are always treated as stateless, so any extra context must be threaded through packed accumulators or manual recursion. Example — evaluating a polynomial with Horner's method during `list.fold`. The fold quotation needs `x` (the evaluation point) at every step, but fold only provides `(acc, coeff)`: ```seq # What you want to write: : eval-poly ( List Int -- Int ) swap list.reverse swap # reversed x 0 [ swap rot gf256-mul bxor ] list.fold # ↑ quotation body needs (x, acc, coeff) → 3 inputs # fold provides (acc, coeff) → 2 inputs # x should be auto-captured from the stack ; ``` ```seq # What you have to write today (packed accumulator workaround): : eval-poly ( List Int -- Int ) over list.length 1 i.- 0 eval-poly-loop # 4-item recursive loop with pick/roll ; ``` The packed-accumulator approach works but it obscures the algorithm and is error-prone (pick-depth bugs caused an infinite loop during development). ## Proposed Change ### Typechecker When type-checking a quotation argument to a combinator whose expected quotation type is fully known: 1. Infer the quotation body's natural effect (e.g., `( Int Int Int -- Int )`) 2. Compare against the combinator's expected effect (e.g., `( Int Int -- Int )` for fold) 3. If the body needs more inputs than the combinator provides, run `calculate_captures` (which already exists in `capture_analysis.rs`) to determine what to capture 4. Promote the quotation's type from `Type::Quotation` to `Type::Closure` with the inferred captures ### Codegen No changes needed — the closure codegen path already handles captures, environment creation, and `invoke_callable` dispatch. `list.fold` and friends already accept both `Value::Quotation` and `Value::Closure` via `invoke_callable`. ### Scope A conservative first version could limit auto-capture to the built-in list combinators (`list.fold`, `list.map`, `list.filter`, `list.each`) where the expected quotation signature is statically known. This avoids ambiguity in the general case. ## Supported Capture Types Per the existing closure codegen (`codegen/words.rs` lines 340-379), these types can already be captured: `Int`, `Bool`, `Float`, `String`, `Quotation`. `Variant` and nested `Closure` captures are not yet supported and would remain an error. ## Risk Medium. The type inference machinery is the most delicate part of the compiler. The key constraint: capture analysis must only trigger when the expected quotation type is unambiguous (i.e., the combinator's signature fully determines the expected effect). Starting with only the built-in list combinators keeps the scope narrow and testable. ## Example: What This Enables ```seq # Lagrange basis product via fold (currently requires manual recursion): : lagrange-basis ( List Int -- Int ) 256 i.+ [ lagrange-basis-step ] list.fold # works today (no capture needed) 8 shr ; # Polynomial evaluation via fold (currently requires 4-item recursive loop): : eval-poly ( List Int -- Int ) swap list.reverse swap 0 [ swap rot gf256-mul bxor ] list.fold # x auto-captured ; # Parameterized filter (currently must hardcode the threshold): : keep-above ( List Int -- List ) [ i.> ] list.filter # threshold auto-captured ; ``` --- *Context: discovered while implementing Shamir's Secret Sharing in Seq. The Lagrange interpolation and polynomial evaluation algorithms are natural fits for `list.fold`, but the lack of auto-capture forced fallback to manual recursion with deep `pick`/`roll` stack juggling.*

navicore commented

2026-04-11 12:46:15 +00:00

(Migrated from github.com)

accepted as an enhancement. see https://github.com/navicore/patch-seq/blob/main/docs/design/AUTO_CAPTURE_COMBINATORS.md for implementation plan