Lines
81.82 %
Functions
30.95 %
Branches
100 %
//! `FOLD` — left fold over a list. `(fold f init list)` returns the
//! accumulator after applying `f(acc, item)` left-to-right.
//!
//! Three paths matching MAP / FILTER:
//! - **Constant-fold**: function + list both resolve at compile time;
//! walk element-by-element calling `f` via the eval `call` pipeline,
//! threading `init` through.
//! - **Runtime closure, literal list**: emit FUNCALL per element,
//! threading the accumulator through a fresh local each iteration.
//! - **Runtime closure or runtime `PairRef` list**: walk the input
//! chain at runtime, calling `f` on each car with the accumulator.
use crate::ast::{Expr, PairElement, WasmType};
use crate::compiler::context::CompileContext;
use crate::compiler::emit::FunctionEmitter;
use crate::compiler::expr::{
as_literal_arg, call, compile_expr, compile_for_effect, compile_for_stack,
compile_for_stack_as, emit_nil_default, eval_value, format_expr,
};
use crate::error::{Error, Result};
use crate::runtime::SymbolTable;
pub(super) fn fold(symbols: &mut SymbolTable, args: &[Expr]) -> Result<Expr> {
if args.len() != 3 {
return Err(Error::Arity {
name: "FOLD".to_string(),
expected: 3,
actual: args.len(),
});
}
let fn_resolved = eval_value(symbols, &args[0])?;
let init_resolved = eval_value(symbols, &args[1])?;
let list_resolved = eval_value(symbols, &args[2])?;
let runtime_closure = matches!(fn_resolved.wasm_type(), Some(WasmType::Closure(_)));
let runtime_list = matches!(list_resolved.wasm_type(), Some(WasmType::PairRef(_)));
if runtime_closure || runtime_list {
let acc_ty = eval_fold_result_type(
symbols,
&fn_resolved,
&args[0],
&init_resolved,
&list_resolved,
)?;
return Ok(Expr::WasmRuntime(acc_ty));
// Static fn + constant list: try to fully reduce. If the body produces a
// runtime value (a side-effecting native like `print`, or any host-fn
// result), the fold ISN'T constant-foldable — surface a runtime placeholder
// so the compile path takes the per-element FUNCALL runtime lowering
// instead of baking a bare `WasmRuntime` placeholder into the result.
let folded = constant_fold_fold(symbols, &args[0], &init_resolved, &list_resolved)?;
if folded.is_wasm_runtime() {
Ok(folded)
/// Eval-path fold result type, kept in lockstep with `compile_fold_to_stack`:
/// a runtime closure's accumulator type IS its signature's result type. The
/// eval surface has no `CompileContext`, so it reads the result the closure-emit
/// site recorded into the symbol table (`SymbolTable::closure_result`); without
/// it (closure not recorded) it falls back to the body/seed probe. This stops
/// the eval mirror sizing a fold accumulator from the seed (e.g. `0` → Index)
/// while codegen emits the closure's real (e.g. Ratio) result.
fn eval_fold_result_type(
symbols: &mut SymbolTable,
fn_resolved: &Expr,
fn_arg: &Expr,
init_resolved: &Expr,
list_resolved: &Expr,
) -> Result<WasmType> {
if let Some(WasmType::Closure(sig)) = fn_resolved.wasm_type()
&& let Some(result) = symbols.closure_result(sig)
{
return Ok(result);
accumulator_type(symbols, fn_arg, init_resolved, list_resolved)
/// The accumulator/result `WasmType` of a fold. A concrete (non-nil) init
/// fixes it. A `nil` init is POLYMORPHIC — its `Bool` type is just "empty" —
/// so the real accumulator type is whatever the fold body returns; probe it by
/// classifying one application `f(init, <sample-elem>)` on a clone (no
/// live-table mutation). Falls back to the init's own type when the body can't
/// be probed. Shared by the eval mirror and the codegen path so they agree.
fn accumulator_type(
// A concrete runtime-typed init (a `WasmLocal`/`WasmRuntime`, NOT nil)
// fixes the accumulator type directly.
if let Some(ty) = init_resolved.wasm_type()
&& !matches!(init_resolved, Expr::Nil)
return Ok(ty);
// Otherwise (a `nil` polymorphic seed, or a literal init like `0` whose
// own classified type may still be refined by the body) the accumulator
// type is what the body returns — probe one application.
if let Some(elem) = sample_element(list_resolved)?
&& let Some(ty) = probe_body_type(symbols, fn_arg, init_resolved, &elem)?
return widen_with_seed(ty, init_resolved);
// Empty list or un-probeable body: fall back to the init's own stack type
// (a literal → its classified type, e.g. `0` → Ratio; nil → Bool).
Ok(crate::compiler::expr::classify_stack_type(init_resolved).unwrap_or(WasmType::Ratio))
/// A constant-list seed's members share the accumulator chain with the body's
/// cells, so they widen a pair accumulator's element: `'(nil)` seeding an
/// index chain is heterogeneous, never a zero.
fn widen_with_seed(ty: WasmType, init_resolved: &Expr) -> Result<WasmType> {
let (WasmType::PairRef(elem), Expr::Quote(seed)) = (ty, init_resolved) else {
let Expr::List(members) = seed.as_ref() else {
let mut cells = members.clone();
cells.push(Expr::WasmRuntime(elem.as_wasm_type()));
Ok(WasmType::PairRef(super::infer::chain_pair_element(&cells)?))
/// A representative element value for probing the fold body's return type:
/// the runtime element's placeholder for a `PairRef` list, else the first
/// constant element. `None` for an empty list (nothing to probe).
fn sample_element(list_resolved: &Expr) -> Result<Option<Expr>> {
if let Some(WasmType::PairRef(elem)) = list_resolved.wasm_type() {
return Ok(Some(Expr::WasmRuntime(elem.as_wasm_type())));
Ok(extract_list_elements(list_resolved)?.into_iter().next())
/// Classify the type of one fold application `f(acc, elem)` without emitting —
/// evaluated on a CLONE so no live-table mutation, then run through the shared
/// stack-type classifier so the prediction matches codegen.
fn probe_body_type(
acc: &Expr,
elem: &Expr,
) -> Result<Option<WasmType>> {
let call_args = vec![fn_arg.clone(), as_literal_arg(acc), as_literal_arg(elem)];
let mut probe = symbols.clone();
let Ok(result) = call(&mut probe, &call_args) else {
return Ok(None);
Ok(crate::compiler::expr::classify_stack_type(&result))
fn constant_fold_fold(
) -> Result<Expr> {
let elements = extract_list_elements(list_resolved)?;
let mut acc = init_resolved.clone();
for elem in elements {
let call_args = vec![fn_arg.clone(), as_literal_arg(&acc), as_literal_arg(&elem)];
let result = call(symbols, &call_args)?;
acc = eval_value(symbols, &result)?;
Ok(acc)
/// Seed the accumulator local from `init`, coercing the init to the resolved
/// accumulator type. For a `PairRef` accumulator a constant-list seed (`nil`,
/// or a quoted literal list) is materialized into a runtime `$pair` chain —
/// `nil` is the empty chain (`ref.null pair`). For any other `acc_ty` the init
/// must already match.
fn emit_fold_init(
ctx: &mut CompileContext,
emit: &mut FunctionEmitter,
init_arg: &Expr,
acc_ty: WasmType,
) -> Result<()> {
// Probe the seed's resolved value on a CLONE so a seed that mutates the
// table (SETF/DEFVAR) isn't applied here AND again by the emission path.
let resolved = eval_value(&mut symbols.clone(), init_arg)?;
// A nil seed (for ANY accumulator type, including PairRef where it is the
// empty `$pair` chain) must first emit the effects of a non-literal seed
// that merely *resolves* to nil, then push the typed nil default. Checked
// before the PairRef constant-list materialization so a `(progn …effects… nil)`
// seed isn't silently collapsed to `ref.null`.
if matches!(resolved, Expr::Nil) {
if !matches!(init_arg, Expr::Nil) {
compile_for_effect(ctx, emit, symbols, init_arg)?;
return emit_nil_default(ctx, emit, acc_ty);
if let WasmType::PairRef(elem) = acc_ty
&& !matches!(resolved.wasm_type(), Some(WasmType::PairRef(_)))
// A constant-list seed for a runtime pair accumulator: materialize it
// with cells at the accumulator's element, so a fold forced onto the
// runtime path by a side-effecting body can still seed a non-nil
// literal-list accumulator. See `append::push_list_arg`.
let elements = super::map::extract_list_elements(&resolved)?;
return super::cons::emit_constant_chain(ctx, emit, symbols, elements, elem);
// Scalar / Index / Money / nil seed: coerce to the accumulator type (an
// integer/fractional literal crosses the sanctioned Index↔Scalar boundary).
compile_for_stack_as(ctx, emit, symbols, init_arg, acc_ty).map_err(|_| {
Error::Compile(format!(
"FOLD: init does not match accumulator type {acc_ty}"
))
})
fn extract_list_elements(expr: &Expr) -> Result<Vec<Expr>> {
match expr {
Expr::List(elems) => Ok(elems.clone()),
Expr::Nil => Ok(vec![]),
Expr::Quote(inner) => match inner.as_ref() {
other => Err(Error::Compile(format!(
"FOLD expects a list, got quoted {}",
format_expr(other)
))),
},
"FOLD expects a list, got {}",
pub(super) fn compile_fold(
args: &[Expr],
let ty = compile_fold_to_stack(ctx, emit, symbols, args)?;
return crate::compiler::expr::serialize_stack_to_output(ctx, emit, ty);
let result = constant_fold_fold(symbols, &args[0], &init_resolved, &list_resolved)?;
if result.is_wasm_runtime() {
// Body produced a runtime value — not constant-foldable. Lower the
// static fn + constant list element-by-element via the runtime path.
compile_expr(ctx, emit, symbols, &result)
pub(super) fn compile_fold_to_stack(
return Err(Error::Compile(
"FOLD: stack-position lowering needs (fn init list)".to_string(),
));
// A runtime closure declares its accumulator type in its signature (the
// result type the body returns under its parameter types). Use that rather
// than the eval-side body probe, which sees literal-typed sample args and
// would mis-infer Index where the closure params are Scalar/Money.
let acc_ty = match fn_resolved.wasm_type() {
Some(WasmType::Closure(sig)) => ctx.closure_sig(sig).result,
_ => accumulator_type(symbols, &args[0], &init_resolved, &list_resolved)?,
// A let-bound closure has a FIXED signature; applying it via `call_ref` over
// a non-Ratio list mismatches its iteration param. If its source body is
// recoverable, inline it per element instead — `compile_lambda_call` binds
// the iteration param to the actual element type. The accumulator type stays
// the closure's declared result (it threads through unchanged).
let call_fn = super::inline_closure_fn(ctx, symbols, &args[0])?;
return compile_fold_runtime_list(
ctx,
emit,
FoldRuntimeArgs {
fn_arg: &call_fn,
init_arg: &args[1],
list_expr: &args[2],
elem,
acc_ty,
);
// Any callable over a constant list — runtime closure OR a bare lambda /
// defun whose body isn't constant-foldable (const-fold bailed here). Each
// element is applied via FUNCALL, which serves both shapes.
compile_fold_literal(
&call_fn,
&args[1],
)
/// Lower `(fold <fn> init '(e0 e1 ...))` element-by-element. Each per-element
/// call rides FUNCALL (→ `call_ref` for a closure, inline for a bare lambda)
/// and threads the accumulator through a fresh local.
fn compile_fold_literal(
let acc_local = ctx.alloc_local(acc_ty)?;
emit_fold_init(ctx, emit, symbols, init_arg, acc_ty)?;
emit.local_set(acc_local);
for elem_expr in &elements {
let funcall = Expr::List(vec![
Expr::Symbol("FUNCALL".to_string()),
fn_arg.clone(),
Expr::WasmLocal(acc_local, acc_ty),
as_literal_arg(elem_expr),
]);
let result_ty = compile_for_stack(ctx, emit, symbols, &funcall)?;
if result_ty != acc_ty {
return Err(Error::Compile(format!(
"FOLD: closure return type {result_ty} doesn't match accumulator type {acc_ty}"
)));
emit.local_get(acc_local);
Ok(acc_ty)
struct FoldRuntimeArgs<'a> {
fn_arg: &'a Expr,
init_arg: &'a Expr,
list_expr: &'a Expr,
elem: PairElement,
/// Walks a runtime `PairRef(elem)` input. Calls `f(acc, car)` per cell,
/// threading the accumulator through a fresh local.
fn compile_fold_runtime_list(
args: FoldRuntimeArgs<'_>,
let FoldRuntimeArgs {
fn_arg,
init_arg,
list_expr,
} = args;
let pair_idx = ctx.ids.ty_pair;
let pair_local = ctx.alloc_local(WasmType::PairRef(elem))?;
let car_local = ctx.alloc_local(elem.as_wasm_type())?;
compile_for_stack(ctx, emit, symbols, list_expr)?;
emit.local_set(pair_local);
emit.block_start();
emit.loop_start();
emit.local_get(pair_local);
emit.ref_is_null();
emit.br_if(1);
emit.struct_get(pair_idx, 0);
crate::compiler::native::list::emit_pair_car_downcast(ctx, emit, elem);
emit.local_set(car_local);
Expr::WasmLocal(car_local, elem.as_wasm_type()),
emit.struct_get(pair_idx, 1);
emit.br(0);
emit.block_end();