Chapter 18: A-Normal Form and Join Points
New files
src/erase.rssrc/anf.rssrc/anf_simplify.rssrc/anf_machine.rssrc/anf_lint.rsChanged files
src/lib.rssrc/main.rs
Motivation
Consider f (g x) (h y). To run it, we need to evaluate the function and its
arguments in the right order, keep the result of g x while computing h y,
and finally make the call. Our interpreter has been doing that bookkeeping
for us. A code generator needs to see the steps.
A-normal form, usually shortened to ANF, writes those intermediate results down as named bindings. Function calls and other operations then take simple operands rather than nested computations. The name sounds rather grand for what amounts to introducing some useful local variables.
This also gives us a good place to bring back the CEK machine from Chapter 5. We’ll run ANF with an explicit continuation stack, now with all of Fun’s data, dictionaries, IO, and join points. We can compare its answers with Core while getting the program ready for native code.
The Language, Now
Let’s follow a case expression whose result is used by another computation.
main = print (3 + (case Just 4 of { Just x -> x; Nothing -> 0 }))
Whichever alternative returns a value, the program must add three and print
once. ANF makes that common continuation explicit as a join rather than copying
it into each alternative. The new --engine=anf selects the iterative machine
and is the default. --engine=core retains the reference interpreter.
--no-simplify exposes the ANF produced before the optional rewrites. Both forms
must preserve stdout, the first stderr line, and process status. In particular,
strict evaluation still runs an unused binding’s initializer. A failing division
cannot disappear merely because its result has no uses.
Theory
In f (g x) (h y), the interesting work is in the calls. The names themselves
just refer to values. ANF makes that distinction part of the syntax. An atom
is a literal or a reference to an available value. A right-hand side performs
one operation on atoms, and a Let gives the result a name. Nested evaluation
has become an explicit sequence (Flanagan et al. 1993).
Conversion receives a context describing what to do with a result. At the end of a function it returns the atom. Inside an expression it binds the atom and continues. At the end of a case alternative it can jump to a shared continuation. This representation keeps joins local and second-class, following the motivation for join points discussed by Maurer and colleagues (Maurer et al. 2017). It does not turn every function into a function that explicitly receives a continuation.
Type erasure is justified by the role of System F’s type abstractions and applications: they select and describe computations but do not themselves perform runtime work (Pierce 2002). Dictionary arguments are different. They contain actual method implementations and must remain as ordinary values. IO already has its unit-function representation before erasure.
Tail position is a property of the remaining work. If a function call supplies the current function’s result directly, the machine needs no return frame for that activation. A non-tail call must remember its pending computation. Constant host-stack use therefore does not imply constant memory for every recursive program. Pending non-tail work can still grow the explicit continuation stack. This is the practical advantage of making the CEK continuation visible (Felleisen and Friedman 1986).
Implementation
erase::erase preserves the order of global initialization while removing
executable type information. A postorder worklist drops TyLam and TyApp,
keeps dictionary terms, and rejects any nested Match that escaped the previous
pass. Read-only constructor and location metadata remains available for
primitives, printers, and diagnostics.
#![allow(unused)]
fn main() {
use crate::{ast::Op, core, data::ConId, names::Id, source::Span};
#[derive(Clone, Debug)]
/// Untyped Core retains strict evaluation order and lexical join points.
pub enum Expr {
Var(Id),
Global(Id),
Lit(core::Lit),
Lam(Id, Box<Expr>),
App(Box<Expr>, Box<Expr>),
Let(bool, Vec<(Id, Expr)>, Box<Expr>),
Con(ConId, Vec<Expr>),
Prim(Op, Vec<Expr>, Span),
Case(Box<Expr>, Id, Vec<(core::AltCon, Vec<Id>, Expr)>),
Join(Id, Vec<Id>, Box<Expr>, Box<Expr>),
Jump(Id, Vec<Expr>),
Fail(Span),
}
#[derive(Clone, Debug)]
/// Ordered globals and runtime constructor/location metadata.
pub struct Program {
pub globals: Vec<(Id, Expr)>,
pub metadata: core::Program,
}
/// Postorder erasure uses an explicit worklist, including long constructor spines.
fn expr(root: &core::Expr) -> Expr {
use core::Expr as C;
let mut todo = vec![(root, false)];
let mut results: Vec<Expr> = vec![];
while let Some((e, done)) = todo.pop() {
let children: Vec<&core::Expr> = match e {
C::Lam(_, e) | C::TyLam(_, e) | C::TyApp(e, _) => vec![e],
C::App(f, a) => vec![f, a],
C::Let(g, b) => g
.binds
.iter()
.map(|b| b.rhs.as_ref())
.chain(std::iter::once(b.as_ref()))
.collect(),
C::Con(_, _, es) | C::Prim(_, _, es, _) | C::Jump(_, es, _) => {
es.iter().collect()
}
C::Case(e, _, _, alts) => std::iter::once(e.as_ref())
.chain(alts.iter().map(|a| &a.rhs))
.collect(),
C::Join(_, _, b, r) => vec![b, r],
C::Match(_) => panic!("match compilation precedes erasure"),
_ => vec![],
};
if !done {
todo.push((e, true));
todo.extend(children.into_iter().rev().map(|c| (c, false)));
continue;
}
let start = results.len() - children.len();
let mut parts = results.split_off(start).into_iter();
let result = match e {
C::Var(i) => Expr::Var(i.name.clone()),
C::Global(i) => Expr::Global(i.name.clone()),
C::Lit(l) => Expr::Lit(l.clone()),
C::TyLam(..) | C::TyApp(..) => parts.next().unwrap(),
C::Lam(i, _) => {
Expr::Lam(i.name.clone(), Box::new(parts.next().unwrap()))
}
C::App(..) => Expr::App(
Box::new(parts.next().unwrap()),
Box::new(parts.next().unwrap()),
),
C::Let(g, _) => {
let bs = g
.binds
.iter()
.map(|b| (b.name.name.clone(), parts.next().unwrap()))
.collect();
Expr::Let(g.recursive, bs, Box::new(parts.next().unwrap()))
}
C::Con(c, _, _) => Expr::Con(c.clone(), parts.collect()),
C::Prim(p, _, _, s) => Expr::Prim(*p, parts.collect(), *s),
C::Case(_, i, _, alts) => {
let e = parts.next().unwrap();
let alts = alts
.iter()
.map(|a| {
(
a.con.clone(),
a.binders
.iter()
.map(|i| i.name.clone())
.collect(),
parts.next().unwrap(),
)
})
.collect();
Expr::Case(Box::new(e), i.name.clone(), alts)
}
C::Join(j, ps, _, _) => Expr::Join(
j.clone(),
ps.iter().map(|i| i.name.clone()).collect(),
Box::new(parts.next().unwrap()),
Box::new(parts.next().unwrap()),
),
C::Jump(j, _, _) => Expr::Jump(j.clone(), parts.collect()),
C::PatternFail(s, _) => Expr::Fail(*s),
C::Match(_) => {
unreachable!("match compilation precedes erasure")
}
};
results.push(result);
}
results.pop().unwrap()
}
/// Compact syntax uses an explicit print stack and bounded indentation. Debug's
/// indentation grows with depth and makes even a linear tree quadratic in bytes.
impl std::fmt::Display for Expr {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
enum Work<'a> {
Expr(&'a Expr),
Text(String),
}
let mut todo = vec![Work::Expr(self)];
while let Some(work) = todo.pop() {
match work {
Work::Text(s) => write!(f, "{s}")?,
Work::Expr(e) => {
let mut parts = vec![];
match e {
Expr::Var(v) => write!(f, "{v}")?,
Expr::Global(v) => write!(f, "@{v}")?,
Expr::Lit(l) => write!(f, "{l}")?,
Expr::Lam(v, b) => {
write!(f, "(lambda {v}. ")?;
parts.push(Work::Expr(b));
parts.push(Work::Text(")".into()));
}
Expr::App(a, b) => {
write!(f, "(")?;
parts.extend([
Work::Expr(a),
Work::Text(" ".into()),
Work::Expr(b),
Work::Text(")".into()),
]);
}
Expr::Con(c, es) => {
write!(f, "({}", c.name)?;
for e in es {
parts.push(Work::Text(" ".into()));
parts.push(Work::Expr(e));
}
parts.push(Work::Text(")".into()));
}
Expr::Prim(p, es, _) => {
write!(f, "({}", p.text())?;
for e in es {
parts.push(Work::Text(" ".into()));
parts.push(Work::Expr(e));
}
parts.push(Work::Text(")".into()));
}
Expr::Jump(j, es) => {
write!(f, "(jump {j}")?;
for e in es {
parts.push(Work::Text(" ".into()));
parts.push(Work::Expr(e));
}
parts.push(Work::Text(")".into()));
}
Expr::Let(rec, bs, b) => {
write!(
f,
"(let{} ",
if *rec { "rec" } else { "" }
)?;
for (v, e) in bs {
parts.push(Work::Text(format!("{v} = ")));
parts.push(Work::Expr(e));
parts.push(Work::Text(";\n".into()));
}
parts.extend([
Work::Text("in ".into()),
Work::Expr(b),
Work::Text(")".into()),
]);
}
Expr::Case(e, v, alts) => {
write!(f, "(case ")?;
parts.extend([
Work::Expr(e),
Work::Text(format!(" as {v} {{\n")),
]);
for (c, ps, e) in alts {
let c = match c {
core::AltCon::Con(c) => c.name.clone(),
core::AltCon::Lit(l) => l.to_string(),
core::AltCon::Default => "_".into(),
};
parts.push(Work::Text(c));
for p in ps {
parts.push(Work::Text(format!(" {p}")));
}
parts.extend([
Work::Text(" -> ".into()),
Work::Expr(e),
Work::Text(";\n".into()),
]);
}
parts.push(Work::Text("})".into()));
}
Expr::Join(j, ps, b, r) => {
write!(f, "(join {j}")?;
for p in ps {
write!(f, " {p}")?;
}
write!(f, " = ")?;
parts.extend([
Work::Expr(b),
Work::Text("\nin ".into()),
Work::Expr(r),
Work::Text(")".into()),
]);
}
Expr::Fail(s) => write!(f, "fail {s:?}")?,
}
todo.extend(parts.into_iter().rev());
}
}
}
Ok(())
}
}
/// Destroy an owned erased tree without recursively following Box edges.
pub fn discard(root: Expr) {
let mut todo = vec![root];
while let Some(e) = todo.pop() {
match e {
Expr::Lam(_, b) => todo.push(*b),
Expr::App(a, b) | Expr::Join(_, _, a, b) => {
todo.push(*a);
todo.push(*b);
}
Expr::Let(_, bs, b) => {
todo.push(*b);
todo.extend(bs.into_iter().map(|(_, e)| e));
}
Expr::Con(_, es) | Expr::Prim(_, es, _) | Expr::Jump(_, es) => {
todo.extend(es)
}
Expr::Case(e, _, alts) => {
todo.push(*e);
todo.extend(alts.into_iter().map(|(_, _, e)| e));
}
_ => {}
}
}
}
/// Erase executable types only; read-only metadata supports diagnostics and printers.
pub fn erase(mut program: core::Program) -> Program {
let globals = program
.groups
.iter()
.flat_map(|g| &g.binds)
.map(|b| (b.name.name.clone(), expr(&b.rhs)))
.collect();
// Consuming Core must not recursively destroy its nested expressions.
let mut todo = program
.groups
.drain(..)
.flat_map(|g| g.binds.into_iter().map(|b| *b.rhs))
.collect::<Vec<_>>();
while let Some(e) = todo.pop() {
use core::Expr as C;
match e {
C::Lam(_, b) | C::TyLam(_, b) | C::TyApp(b, _) => todo.push(*b),
C::App(a, b) | C::Join(_, _, a, b) => {
todo.push(*a);
todo.push(*b);
}
C::Let(g, b) => {
todo.push(*b);
todo.extend(g.binds.into_iter().map(|b| *b.rhs));
}
C::Con(_, _, es) | C::Prim(_, _, es, _) | C::Jump(_, es, _) => {
todo.extend(es)
}
C::Case(e, _, _, alts) => {
todo.push(*e);
todo.extend(alts.into_iter().map(|a| a.rhs));
}
C::Match(_) => {
unreachable!("match compilation precedes erasure")
}
_ => {}
}
}
Program {
globals,
metadata: program,
}
}
}The ANF Grammar
Here is the control language in symbolic form. We use for an atom, for a right-hand side, and for a complete ANF body. Each row corresponds to a Rust variant below.
An overbar means a sequence. The name identifies a join point, while is an alternative’s constructor tag, literal, or default marker. Constructor alternatives bind their fields to . Literal and default alternatives have no field binders.
The smaller pieces explain the “normal form” part of the name. An operand is always an atom, never another call waiting to happen.
Here names a constructor and a primitive. Primitive source spans are omitted from the grammar. Unlike Core’s lambdas, these lambdas can take several parameters, and there are no type abstractions or type applications left.
The distinction between a call and a tail call is now visible in the syntax. saves work to do after the call. has no such body. A jump also has no following body, but stays inside the current function and transfers to a local join point.
The ANF control language separates ordinary bindings, recursive closures,
branches, joins, and terminal transfers. Fail preserves the source span of a
pattern failure:
#![allow(unused)]
fn main() {
use crate::{
ast::Op,
core::{self, AltCon, Lit},
data::ConId,
erase,
names::Id,
session::Session,
source::Span,
};
use std::{collections::BTreeMap, rc::Rc};
/// An erased binder keeps its unique identity and diagnostic spelling.
pub type Var = Id;
/// Syntax is immutable and shared between closures and machine states.
pub type Body = Rc<Anf>;
#[derive(Clone, Debug, PartialEq, Eq)]
/// Atoms cannot perform work or fail when read from a well-scoped environment.
pub enum Atom {
Var(Var),
Global(Id),
Lit(Lit),
}
#[derive(Clone, Debug)]
/// Lambda parameters are merged only across syntactically adjacent lambdas.
pub struct Lambda {
pub params: Vec<Var>,
pub body: Body,
}
#[derive(Clone, Debug)]
/// One strict computation whose operands have already been evaluated.
pub enum Rhs {
Atom(Atom),
Call(Atom, Vec<Atom>),
Con(ConId, Vec<Atom>),
Prim(Op, Vec<Atom>, Span),
Lambda(Lambda),
Field(Atom, u32),
}
#[derive(Clone, Debug)]
/// Global initialization order is preserved from typed Core.
pub struct Program {
pub globals: Vec<(Id, Body)>,
pub metadata: core::Program,
}
#[derive(Clone)]
enum Context {
Return,
Jump(Id),
Bind(Var, Body),
}
struct Convert<'a> {
sess: &'a mut Session,
arities: BTreeMap<Id, usize>,
}
fn arity(mut e: &erase::Expr) -> usize {
let mut n = 0;
while let erase::Expr::Lam(_, b) = e {
n += 1;
e = b;
}
n
}
fn collect(e: &erase::Expr, out: &mut BTreeMap<Id, usize>) {
use erase::Expr as E;
let mut todo = vec![e];
while let Some(e) = todo.pop() {
match e {
E::Let(_, bs, b) => {
for (v, e) in bs {
let n = arity(e);
if n > 0 {
out.insert(v.clone(), n);
}
todo.push(e);
}
todo.push(b);
}
E::Lam(_, b) => todo.push(b),
E::App(a, b) | E::Join(_, _, a, b) => {
todo.push(a);
todo.push(b);
}
E::Con(_, es) | E::Prim(_, es, _) | E::Jump(_, es) => {
todo.extend(es)
}
E::Case(e, _, alts) => {
todo.push(e);
todo.extend(alts.iter().map(|(_, _, e)| e));
}
_ => {}
}
}
}
impl Convert<'_> {
fn fresh(&mut self) -> Var {
self.sess.fresh_id("$a")
}
fn finish(&mut self, a: Atom, k: Context) -> Body {
Rc::new(match k {
Context::Return => Anf::Ret(a),
Context::Jump(j) => Anf::Jump(j, vec![a]),
Context::Bind(v, b) => Anf::Let(v, Rhs::Atom(a), b),
})
}
fn rhs(&mut self, r: Rhs, k: Context) -> Body {
if let Context::Bind(v, b) = k {
return Rc::new(Anf::Let(v, r, b));
}
if let (Rhs::Call(f, args), Context::Return) = (&r, &k) {
return Rc::new(Anf::TailCall(f.clone(), args.clone()));
}
let v = self.fresh();
let rest = self.finish(Atom::Var(v.clone()), k);
Rc::new(Anf::Let(v, r, rest))
}
/// Tasks hold pending compiler work. Neither expression depth nor the
/// number of operands adds a Rust call frame.
fn expr(&mut self, e: erase::Expr, k: Context) -> Body {
use erase::Expr as E;
enum Work {
Expr(erase::Expr, Context),
Bindings(Vec<(Var, erase::Expr)>),
Lambda(Vec<Var>, Context),
Rec(Vec<(Var, Vec<Var>)>),
Case(
erase::Expr,
Var,
Vec<(AltCon, Vec<Var>)>,
Option<(Id, Var, Body)>,
),
Join(Id, Vec<Var>, Option<(Id, Var, Body)>),
Call(erase::Expr, Var, Vec<erase::Expr>, Var),
}
fn peel(mut e: erase::Expr) -> (Vec<Var>, erase::Expr) {
let mut ps = vec![];
while let E::Lam(v, b) = e {
ps.push(v);
e = *b;
}
(ps, e)
}
fn branch(
k: Context,
sess: &mut Session,
) -> (Context, Option<(Id, Var, Body)>) {
match k {
Context::Bind(v, b) => {
let j = sess.fresh_id("$cont");
(Context::Jump(j.clone()), Some((j, v, b)))
}
k => (k, None),
}
}
fn wrap(body: Body, cont: Option<(Id, Var, Body)>) -> Body {
match cont {
Some((j, v, b)) => Rc::new(Anf::Join(j, vec![v], b, body)),
None => body,
}
}
let mut todo = vec![Work::Expr(e, k)];
let mut results: Vec<Body> = vec![];
while let Some(work) = todo.pop() {
match work {
Work::Bindings(mut bs) => {
if let Some((v, e)) = bs.pop() {
let b = results.pop().unwrap();
todo.push(Work::Bindings(bs));
todo.push(Work::Expr(e, Context::Bind(v, b)));
}
}
Work::Lambda(params, k) => {
let body = results.pop().unwrap();
results.push(
self.rhs(Rhs::Lambda(Lambda { params, body }), k),
);
}
Work::Rec(bs) => {
let bodies =
results.split_off(results.len() - bs.len());
let rest = results.pop().unwrap();
let bs = bs
.into_iter()
.zip(bodies)
.map(|((v, params), body)| {
(v, Lambda { params, body })
})
.collect();
results.push(Rc::new(Anf::LetRec(bs, rest)));
}
Work::Case(e, v, heads, cont) => {
let bodies =
results.split_off(results.len() - heads.len());
let alts = heads
.into_iter()
.zip(bodies)
.map(|((c, ps), b)| (c, ps, b))
.collect();
let b = wrap(
Rc::new(Anf::Case(Atom::Var(v.clone()), alts)),
cont,
);
todo.push(Work::Expr(e, Context::Bind(v, b)));
}
Work::Join(j, ps, cont) => {
let rest = results.pop().unwrap();
let body = results.pop().unwrap();
results.push(wrap(
Rc::new(Anf::Join(j, ps, body, rest)),
cont,
));
}
Work::Call(head, f, args, result) => {
let rest = results.pop().unwrap();
let vars: Vec<_> =
args.iter().map(|_| self.fresh()).collect();
let atoms =
vars.iter().cloned().map(Atom::Var).collect();
let b = self.rhs(
Rhs::Call(Atom::Var(f.clone()), atoms),
Context::Bind(result, rest),
);
let bs = std::iter::once((f, head))
.chain(vars.into_iter().zip(args))
.collect();
results.push(b);
todo.push(Work::Bindings(bs));
}
Work::Expr(e, k) => {
match e {
E::Var(v) => {
results.push(self.finish(Atom::Var(v), k))
}
E::Global(v) => {
results.push(self.finish(Atom::Global(v), k))
}
E::Lit(l) => {
results.push(self.finish(Atom::Lit(l), k))
}
node @ E::Lam(..) => {
let (ps, body) = peel(node);
todo.push(Work::Lambda(ps, k));
todo.push(Work::Expr(body, Context::Return));
}
node @ E::App(..) => {
let mut head = node;
let mut args = vec![];
while let E::App(f, a) = head {
args.push(*a);
head = *f;
}
args.reverse();
let known = match &head {
E::Var(v) | E::Global(v) => {
self.arities.get(v).copied()
}
E::Lam(..) => Some(arity(&head)),
_ => None,
};
// Unknown calls execute before evaluating their next argument.
let n = known.unwrap_or(1).min(args.len());
let extra = args.split_off(n);
let f = self.fresh();
if extra.is_empty() {
let vars: Vec<_> = args
.iter()
.map(|_| self.fresh())
.collect();
let atoms = vars
.iter()
.cloned()
.map(Atom::Var)
.collect();
results.push(self.rhs(
Rhs::Call(Atom::Var(f.clone()), atoms),
k,
));
todo.push(Work::Bindings(
std::iter::once((f, head))
.chain(vars.into_iter().zip(args))
.collect(),
));
} else {
let result = self.fresh();
let application = extra.into_iter().fold(
E::Var(result.clone()),
|f, a| E::App(Box::new(f), Box::new(a)),
);
todo.push(Work::Call(
head, f, args, result,
));
todo.push(Work::Expr(application, k));
}
}
E::Let(rec, bs, b) => {
if rec {
let (heads, bodies): (Vec<_>, Vec<_>) = bs
.into_iter()
.map(|(v, e)| {
let (ps, e) = peel(e);
((v, ps), e)
})
.unzip();
todo.push(Work::Rec(heads));
todo.extend(bodies.into_iter().rev().map(
|e| Work::Expr(e, Context::Return),
));
} else {
todo.push(Work::Bindings(bs));
}
todo.push(Work::Expr(*b, k));
}
node @ (E::Con(..) | E::Prim(..) | E::Jump(..)) => {
let args = match &node {
E::Con(_, es)
| E::Prim(_, es, _)
| E::Jump(_, es) => es,
_ => unreachable!(),
};
let vars: Vec<_> =
args.iter().map(|_| self.fresh()).collect();
let atoms = vars
.iter()
.cloned()
.map(Atom::Var)
.collect();
let (args, body) = match node {
E::Con(c, es) => {
(es, self.rhs(Rhs::Con(c, atoms), k))
}
E::Prim(p, es, s) => (
es,
self.rhs(Rhs::Prim(p, atoms, s), k),
),
E::Jump(j, es) => {
(es, Rc::new(Anf::Jump(j, atoms)))
}
_ => unreachable!(),
};
results.push(body);
todo.push(Work::Bindings(
vars.into_iter().zip(args).collect(),
));
}
E::Case(e, v, alts) => {
let (k, cont) = branch(k, self.sess);
let (heads, bodies): (Vec<_>, Vec<_>) = alts
.into_iter()
.map(|(c, ps, b)| ((c, ps), b))
.unzip();
todo.push(Work::Case(*e, v, heads, cont));
todo.extend(
bodies
.into_iter()
.rev()
.map(|e| Work::Expr(e, k.clone())),
);
}
E::Join(j, ps, b, r) => {
let (k, cont) = branch(k, self.sess);
todo.push(Work::Join(j, ps, cont));
todo.push(Work::Expr(*r, k.clone()));
todo.push(Work::Expr(*b, k));
}
E::Fail(s) => results.push(Rc::new(Anf::Fail(s))),
}
}
}
}
assert_eq!(results.len(), 1);
results.pop().unwrap()
}
}
/// Normalize left-to-right, sharing every non-tail continuation exactly once.
pub fn convert(sess: &mut Session, program: erase::Program) -> Program {
let mut arities = BTreeMap::new();
for (v, e) in &program.globals {
if arity(e) > 0 {
arities.insert(v.clone(), arity(e));
}
collect(e, &mut arities);
}
let mut c = Convert { sess, arities };
let globals = program
.globals
.into_iter()
.map(|(v, e)| (v, c.expr(e, Context::Return)))
.collect();
Program {
globals,
metadata: program.metadata,
}
}
impl std::fmt::Display for Atom {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Var(v) => write!(f, "{v}"),
Self::Global(v) => write!(f, "@{v}"),
Self::Lit(l) => write!(f, "{l}"),
}
}
}
fn list<T: std::fmt::Display>(items: &[T]) -> String {
items
.iter()
.map(ToString::to_string)
.collect::<Vec<_>>()
.join(", ")
}
impl std::fmt::Display for Rhs {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Atom(a) => write!(f, "{a}"),
Self::Call(a, args) => write!(f, "call {a}({})", list(args)),
Self::Con(c, args) => write!(f, "{}({})", c.name, list(args)),
Self::Prim(p, args, _) => {
write!(f, "{}({})", p.text(), list(args))
}
Self::Lambda(l) => {
write!(f, "lambda ({}) {{ {} }}", list(&l.params), l.body)
}
Self::Field(a, i) => write!(f, "field {a}[{i}]"),
}
}
}
impl std::fmt::Display for Anf {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
enum Work<'a> {
Body(&'a Anf),
Rhs(&'a Rhs),
Text(String),
}
let mut todo = vec![Work::Body(self)];
while let Some(work) = todo.pop() {
let mut parts = vec![];
match work {
Work::Text(s) => write!(f, "{s}")?,
Work::Rhs(Rhs::Lambda(l)) => {
write!(f, "lambda ({}) {{ ", list(&l.params))?;
parts.extend([
Work::Body(&l.body),
Work::Text(" }".into()),
]);
}
Work::Rhs(r) => write!(f, "{r}")?,
Work::Body(b) => match b {
Self::Let(v, r, b) => {
write!(f, "let {v} = ")?;
parts.extend([
Work::Rhs(r),
Work::Text(";\n".into()),
Work::Body(b),
]);
}
Self::LetRec(bs, b) => {
for (v, l) in bs {
parts.extend([
Work::Text(format!(
"rec {v}({}) = {{ ",
list(&l.params)
)),
Work::Body(&l.body),
Work::Text(" }\n".into()),
]);
}
parts.push(Work::Body(b));
}
Self::Join(j, ps, b, r) => {
write!(f, "join {j}({}) = {{ ", list(ps))?;
parts.extend([
Work::Body(b),
Work::Text(" };\n".into()),
Work::Body(r),
]);
}
Self::Jump(j, args) => {
write!(f, "jump {j}({})", list(args))?
}
Self::Case(a, alts) => {
writeln!(f, "case {a} {{")?;
for (c, ps, b) in alts {
let head = match c {
AltCon::Con(c) => c.name.clone(),
AltCon::Lit(l) => l.to_string(),
AltCon::Default => "_".into(),
};
parts.extend([
Work::Text(format!(
"{head}({}) -> {{ ",
list(ps)
)),
Work::Body(b),
Work::Text(" }\n".into()),
]);
}
parts.push(Work::Text("}".into()));
}
Self::Ret(a) => write!(f, "return {a}")?,
Self::TailCall(fun, args) => {
write!(f, "tail {fun}({})", list(args))?
}
Self::Fail(s) => write!(f, "fail {s:?}")?,
},
}
todo.extend(parts.into_iter().rev());
}
Ok(())
}
}
/// Drain child edges explicitly when the last owner releases a deep ANF tree.
impl Drop for Anf {
fn drop(&mut self) {
fn edges(node: &mut Anf, todo: &mut Vec<Body>) {
fn take(b: &mut Body) -> Body {
std::mem::replace(
b,
Rc::new(Anf::Ret(Atom::Lit(Lit::Int(0)))),
)
}
match node {
Anf::Let(_, r, b) => {
todo.push(take(b));
if let Rhs::Lambda(l) = r {
todo.push(take(&mut l.body));
}
}
Anf::LetRec(bs, b) => {
todo.push(take(b));
todo.extend(bs.drain(..).map(|(_, l)| l.body));
}
Anf::Join(_, _, b, r) => {
todo.push(take(b));
todo.push(take(r));
}
Anf::Case(_, alts) => {
todo.extend(alts.drain(..).map(|(_, _, b)| b))
}
_ => {}
}
}
let mut todo = vec![];
edges(self, &mut todo);
while let Some(b) = todo.pop() {
if let Ok(mut node) = Rc::try_unwrap(b) {
edges(&mut node, &mut todo);
// Empty this node before Drop runs again on the local variable.
// Its remaining children are only leaf placeholders.
}
}
}
}
#[derive(Clone, Debug)]
/// Jumps transfer within a function; tail calls replace its activation.
pub enum Anf {
Let(Var, Rhs, Body),
LetRec(Vec<(Var, Lambda)>, Body),
Join(Id, Vec<Var>, Body, Body),
Jump(Id, Vec<Atom>),
Case(Atom, Vec<(AltCon, Vec<Var>, Body)>),
Ret(Atom),
TailCall(Atom, Vec<Atom>),
Fail(Span),
}
}The converter’s context has only three cases. finish interprets a context once
the result has become an atom. Pending conversions live in a work vector, so a
long expression does not become a long chain of Rust calls:
#![allow(unused)]
fn main() {
use crate::{
ast::Op,
core::{self, AltCon, Lit},
data::ConId,
erase,
names::Id,
session::Session,
source::Span,
};
use std::{collections::BTreeMap, rc::Rc};
/// An erased binder keeps its unique identity and diagnostic spelling.
pub type Var = Id;
/// Syntax is immutable and shared between closures and machine states.
pub type Body = Rc<Anf>;
#[derive(Clone, Debug, PartialEq, Eq)]
/// Atoms cannot perform work or fail when read from a well-scoped environment.
pub enum Atom {
Var(Var),
Global(Id),
Lit(Lit),
}
#[derive(Clone, Debug)]
/// Lambda parameters are merged only across syntactically adjacent lambdas.
pub struct Lambda {
pub params: Vec<Var>,
pub body: Body,
}
#[derive(Clone, Debug)]
/// One strict computation whose operands have already been evaluated.
pub enum Rhs {
Atom(Atom),
Call(Atom, Vec<Atom>),
Con(ConId, Vec<Atom>),
Prim(Op, Vec<Atom>, Span),
Lambda(Lambda),
Field(Atom, u32),
}
#[derive(Clone, Debug)]
/// Jumps transfer within a function; tail calls replace its activation.
pub enum Anf {
Let(Var, Rhs, Body),
LetRec(Vec<(Var, Lambda)>, Body),
Join(Id, Vec<Var>, Body, Body),
Jump(Id, Vec<Atom>),
Case(Atom, Vec<(AltCon, Vec<Var>, Body)>),
Ret(Atom),
TailCall(Atom, Vec<Atom>),
Fail(Span),
}
#[derive(Clone, Debug)]
/// Global initialization order is preserved from typed Core.
pub struct Program {
pub globals: Vec<(Id, Body)>,
pub metadata: core::Program,
}
struct Convert<'a> {
sess: &'a mut Session,
arities: BTreeMap<Id, usize>,
}
fn arity(mut e: &erase::Expr) -> usize {
let mut n = 0;
while let erase::Expr::Lam(_, b) = e {
n += 1;
e = b;
}
n
}
fn collect(e: &erase::Expr, out: &mut BTreeMap<Id, usize>) {
use erase::Expr as E;
let mut todo = vec![e];
while let Some(e) = todo.pop() {
match e {
E::Let(_, bs, b) => {
for (v, e) in bs {
let n = arity(e);
if n > 0 {
out.insert(v.clone(), n);
}
todo.push(e);
}
todo.push(b);
}
E::Lam(_, b) => todo.push(b),
E::App(a, b) | E::Join(_, _, a, b) => {
todo.push(a);
todo.push(b);
}
E::Con(_, es) | E::Prim(_, es, _) | E::Jump(_, es) => {
todo.extend(es)
}
E::Case(e, _, alts) => {
todo.push(e);
todo.extend(alts.iter().map(|(_, _, e)| e));
}
_ => {}
}
}
}
impl Convert<'_> {
fn fresh(&mut self) -> Var {
self.sess.fresh_id("$a")
}
fn finish(&mut self, a: Atom, k: Context) -> Body {
Rc::new(match k {
Context::Return => Anf::Ret(a),
Context::Jump(j) => Anf::Jump(j, vec![a]),
Context::Bind(v, b) => Anf::Let(v, Rhs::Atom(a), b),
})
}
fn rhs(&mut self, r: Rhs, k: Context) -> Body {
if let Context::Bind(v, b) = k {
return Rc::new(Anf::Let(v, r, b));
}
if let (Rhs::Call(f, args), Context::Return) = (&r, &k) {
return Rc::new(Anf::TailCall(f.clone(), args.clone()));
}
let v = self.fresh();
let rest = self.finish(Atom::Var(v.clone()), k);
Rc::new(Anf::Let(v, r, rest))
}
/// Tasks hold pending compiler work. Neither expression depth nor the
/// number of operands adds a Rust call frame.
fn expr(&mut self, e: erase::Expr, k: Context) -> Body {
use erase::Expr as E;
enum Work {
Expr(erase::Expr, Context),
Bindings(Vec<(Var, erase::Expr)>),
Lambda(Vec<Var>, Context),
Rec(Vec<(Var, Vec<Var>)>),
Case(
erase::Expr,
Var,
Vec<(AltCon, Vec<Var>)>,
Option<(Id, Var, Body)>,
),
Join(Id, Vec<Var>, Option<(Id, Var, Body)>),
Call(erase::Expr, Var, Vec<erase::Expr>, Var),
}
fn peel(mut e: erase::Expr) -> (Vec<Var>, erase::Expr) {
let mut ps = vec![];
while let E::Lam(v, b) = e {
ps.push(v);
e = *b;
}
(ps, e)
}
fn branch(
k: Context,
sess: &mut Session,
) -> (Context, Option<(Id, Var, Body)>) {
match k {
Context::Bind(v, b) => {
let j = sess.fresh_id("$cont");
(Context::Jump(j.clone()), Some((j, v, b)))
}
k => (k, None),
}
}
fn wrap(body: Body, cont: Option<(Id, Var, Body)>) -> Body {
match cont {
Some((j, v, b)) => Rc::new(Anf::Join(j, vec![v], b, body)),
None => body,
}
}
let mut todo = vec![Work::Expr(e, k)];
let mut results: Vec<Body> = vec![];
while let Some(work) = todo.pop() {
match work {
Work::Bindings(mut bs) => {
if let Some((v, e)) = bs.pop() {
let b = results.pop().unwrap();
todo.push(Work::Bindings(bs));
todo.push(Work::Expr(e, Context::Bind(v, b)));
}
}
Work::Lambda(params, k) => {
let body = results.pop().unwrap();
results.push(
self.rhs(Rhs::Lambda(Lambda { params, body }), k),
);
}
Work::Rec(bs) => {
let bodies =
results.split_off(results.len() - bs.len());
let rest = results.pop().unwrap();
let bs = bs
.into_iter()
.zip(bodies)
.map(|((v, params), body)| {
(v, Lambda { params, body })
})
.collect();
results.push(Rc::new(Anf::LetRec(bs, rest)));
}
Work::Case(e, v, heads, cont) => {
let bodies =
results.split_off(results.len() - heads.len());
let alts = heads
.into_iter()
.zip(bodies)
.map(|((c, ps), b)| (c, ps, b))
.collect();
let b = wrap(
Rc::new(Anf::Case(Atom::Var(v.clone()), alts)),
cont,
);
todo.push(Work::Expr(e, Context::Bind(v, b)));
}
Work::Join(j, ps, cont) => {
let rest = results.pop().unwrap();
let body = results.pop().unwrap();
results.push(wrap(
Rc::new(Anf::Join(j, ps, body, rest)),
cont,
));
}
Work::Call(head, f, args, result) => {
let rest = results.pop().unwrap();
let vars: Vec<_> =
args.iter().map(|_| self.fresh()).collect();
let atoms =
vars.iter().cloned().map(Atom::Var).collect();
let b = self.rhs(
Rhs::Call(Atom::Var(f.clone()), atoms),
Context::Bind(result, rest),
);
let bs = std::iter::once((f, head))
.chain(vars.into_iter().zip(args))
.collect();
results.push(b);
todo.push(Work::Bindings(bs));
}
Work::Expr(e, k) => {
match e {
E::Var(v) => {
results.push(self.finish(Atom::Var(v), k))
}
E::Global(v) => {
results.push(self.finish(Atom::Global(v), k))
}
E::Lit(l) => {
results.push(self.finish(Atom::Lit(l), k))
}
node @ E::Lam(..) => {
let (ps, body) = peel(node);
todo.push(Work::Lambda(ps, k));
todo.push(Work::Expr(body, Context::Return));
}
node @ E::App(..) => {
let mut head = node;
let mut args = vec![];
while let E::App(f, a) = head {
args.push(*a);
head = *f;
}
args.reverse();
let known = match &head {
E::Var(v) | E::Global(v) => {
self.arities.get(v).copied()
}
E::Lam(..) => Some(arity(&head)),
_ => None,
};
// Unknown calls execute before evaluating their next argument.
let n = known.unwrap_or(1).min(args.len());
let extra = args.split_off(n);
let f = self.fresh();
if extra.is_empty() {
let vars: Vec<_> = args
.iter()
.map(|_| self.fresh())
.collect();
let atoms = vars
.iter()
.cloned()
.map(Atom::Var)
.collect();
results.push(self.rhs(
Rhs::Call(Atom::Var(f.clone()), atoms),
k,
));
todo.push(Work::Bindings(
std::iter::once((f, head))
.chain(vars.into_iter().zip(args))
.collect(),
));
} else {
let result = self.fresh();
let application = extra.into_iter().fold(
E::Var(result.clone()),
|f, a| E::App(Box::new(f), Box::new(a)),
);
todo.push(Work::Call(
head, f, args, result,
));
todo.push(Work::Expr(application, k));
}
}
E::Let(rec, bs, b) => {
if rec {
let (heads, bodies): (Vec<_>, Vec<_>) = bs
.into_iter()
.map(|(v, e)| {
let (ps, e) = peel(e);
((v, ps), e)
})
.unzip();
todo.push(Work::Rec(heads));
todo.extend(bodies.into_iter().rev().map(
|e| Work::Expr(e, Context::Return),
));
} else {
todo.push(Work::Bindings(bs));
}
todo.push(Work::Expr(*b, k));
}
node @ (E::Con(..) | E::Prim(..) | E::Jump(..)) => {
let args = match &node {
E::Con(_, es)
| E::Prim(_, es, _)
| E::Jump(_, es) => es,
_ => unreachable!(),
};
let vars: Vec<_> =
args.iter().map(|_| self.fresh()).collect();
let atoms = vars
.iter()
.cloned()
.map(Atom::Var)
.collect();
let (args, body) = match node {
E::Con(c, es) => {
(es, self.rhs(Rhs::Con(c, atoms), k))
}
E::Prim(p, es, s) => (
es,
self.rhs(Rhs::Prim(p, atoms, s), k),
),
E::Jump(j, es) => {
(es, Rc::new(Anf::Jump(j, atoms)))
}
_ => unreachable!(),
};
results.push(body);
todo.push(Work::Bindings(
vars.into_iter().zip(args).collect(),
));
}
E::Case(e, v, alts) => {
let (k, cont) = branch(k, self.sess);
let (heads, bodies): (Vec<_>, Vec<_>) = alts
.into_iter()
.map(|(c, ps, b)| ((c, ps), b))
.unzip();
todo.push(Work::Case(*e, v, heads, cont));
todo.extend(
bodies
.into_iter()
.rev()
.map(|e| Work::Expr(e, k.clone())),
);
}
E::Join(j, ps, b, r) => {
let (k, cont) = branch(k, self.sess);
todo.push(Work::Join(j, ps, cont));
todo.push(Work::Expr(*r, k.clone()));
todo.push(Work::Expr(*b, k));
}
E::Fail(s) => results.push(Rc::new(Anf::Fail(s))),
}
}
}
}
assert_eq!(results.len(), 1);
results.pop().unwrap()
}
}
/// Normalize left-to-right, sharing every non-tail continuation exactly once.
pub fn convert(sess: &mut Session, program: erase::Program) -> Program {
let mut arities = BTreeMap::new();
for (v, e) in &program.globals {
if arity(e) > 0 {
arities.insert(v.clone(), arity(e));
}
collect(e, &mut arities);
}
let mut c = Convert { sess, arities };
let globals = program
.globals
.into_iter()
.map(|(v, e)| (v, c.expr(e, Context::Return)))
.collect();
Program {
globals,
metadata: program.metadata,
}
}
impl std::fmt::Display for Atom {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Var(v) => write!(f, "{v}"),
Self::Global(v) => write!(f, "@{v}"),
Self::Lit(l) => write!(f, "{l}"),
}
}
}
fn list<T: std::fmt::Display>(items: &[T]) -> String {
items
.iter()
.map(ToString::to_string)
.collect::<Vec<_>>()
.join(", ")
}
impl std::fmt::Display for Rhs {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Atom(a) => write!(f, "{a}"),
Self::Call(a, args) => write!(f, "call {a}({})", list(args)),
Self::Con(c, args) => write!(f, "{}({})", c.name, list(args)),
Self::Prim(p, args, _) => {
write!(f, "{}({})", p.text(), list(args))
}
Self::Lambda(l) => {
write!(f, "lambda ({}) {{ {} }}", list(&l.params), l.body)
}
Self::Field(a, i) => write!(f, "field {a}[{i}]"),
}
}
}
impl std::fmt::Display for Anf {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
enum Work<'a> {
Body(&'a Anf),
Rhs(&'a Rhs),
Text(String),
}
let mut todo = vec![Work::Body(self)];
while let Some(work) = todo.pop() {
let mut parts = vec![];
match work {
Work::Text(s) => write!(f, "{s}")?,
Work::Rhs(Rhs::Lambda(l)) => {
write!(f, "lambda ({}) {{ ", list(&l.params))?;
parts.extend([
Work::Body(&l.body),
Work::Text(" }".into()),
]);
}
Work::Rhs(r) => write!(f, "{r}")?,
Work::Body(b) => match b {
Self::Let(v, r, b) => {
write!(f, "let {v} = ")?;
parts.extend([
Work::Rhs(r),
Work::Text(";\n".into()),
Work::Body(b),
]);
}
Self::LetRec(bs, b) => {
for (v, l) in bs {
parts.extend([
Work::Text(format!(
"rec {v}({}) = {{ ",
list(&l.params)
)),
Work::Body(&l.body),
Work::Text(" }\n".into()),
]);
}
parts.push(Work::Body(b));
}
Self::Join(j, ps, b, r) => {
write!(f, "join {j}({}) = {{ ", list(ps))?;
parts.extend([
Work::Body(b),
Work::Text(" };\n".into()),
Work::Body(r),
]);
}
Self::Jump(j, args) => {
write!(f, "jump {j}({})", list(args))?
}
Self::Case(a, alts) => {
writeln!(f, "case {a} {{")?;
for (c, ps, b) in alts {
let head = match c {
AltCon::Con(c) => c.name.clone(),
AltCon::Lit(l) => l.to_string(),
AltCon::Default => "_".into(),
};
parts.extend([
Work::Text(format!(
"{head}({}) -> {{ ",
list(ps)
)),
Work::Body(b),
Work::Text(" }\n".into()),
]);
}
parts.push(Work::Text("}".into()));
}
Self::Ret(a) => write!(f, "return {a}")?,
Self::TailCall(fun, args) => {
write!(f, "tail {fun}({})", list(args))?
}
Self::Fail(s) => write!(f, "fail {s:?}")?,
},
}
todo.extend(parts.into_iter().rev());
}
Ok(())
}
}
/// Drain child edges explicitly when the last owner releases a deep ANF tree.
impl Drop for Anf {
fn drop(&mut self) {
fn edges(node: &mut Anf, todo: &mut Vec<Body>) {
fn take(b: &mut Body) -> Body {
std::mem::replace(
b,
Rc::new(Anf::Ret(Atom::Lit(Lit::Int(0)))),
)
}
match node {
Anf::Let(_, r, b) => {
todo.push(take(b));
if let Rhs::Lambda(l) = r {
todo.push(take(&mut l.body));
}
}
Anf::LetRec(bs, b) => {
todo.push(take(b));
todo.extend(bs.drain(..).map(|(_, l)| l.body));
}
Anf::Join(_, _, b, r) => {
todo.push(take(b));
todo.push(take(r));
}
Anf::Case(_, alts) => {
todo.extend(alts.drain(..).map(|(_, _, b)| b))
}
_ => {}
}
}
let mut todo = vec![];
edges(self, &mut todo);
while let Some(b) = todo.pop() {
if let Ok(mut node) = Rc::try_unwrap(b) {
edges(&mut node, &mut todo);
// Empty this node before Drop runs again on the local variable.
// Its remaining children are only leaf placeholders.
}
}
}
}
#[derive(Clone)]
enum Context {
Return,
Jump(Id),
Bind(Var, Body),
}
fn finish(&mut self, a: Atom, k: Context) -> Body {
Rc::new(match k {
Context::Return => Anf::Ret(a),
Context::Jump(j) => Anf::Jump(j, vec![a]),
Context::Bind(v, b) => Anf::Let(v, Rhs::Atom(a), b),
})
}
}For a non-tail case, conversion gives the remaining context a fresh join parameter and converts each alternative with a jump context. Existing Core joins survive. Adjacent lambdas merge into a multi-parameter lambda. This is syntactic arity, not arity inferred from a function type.
Application conversion must respect the order of curried calls. In f a b,
the call f a may fail before b is evaluated. Combining both arguments into a
single eager batch would change which error appears first. The converter batches
only up to a known syntactic arity. Unknown calls consume one argument at a time,
and over-application preserves the boundary after the known prefix. The
known-prefix-error regression checks this ordering explicitly.
anf_simplify propagates atoms, selects known-constructor branches, removes
unused total right-hand sides, and reduces immediately applied saturated
lambdas. Calls, effects, and potentially failing primitives are retained. The
beta rule also checks whether the function escapes: passing a function to itself,
as in the inherited id id example, means its binding cannot simply be deleted.
Structural ANF lint independently checks names, scopes, join arities, and fresh
binders before execution.
The machine is a loop over code, application, and return states. Its frames remember a non-tail binding continuation or arguments left after an oversaturated call:
#![allow(unused)]
fn main() {
use crate::{
anf::{self, Anf, Atom, Body, Lambda, Rhs, Var},
ast::Op,
core::{AltCon, Lit},
data::ConId,
eval::Failure,
};
use std::{collections::BTreeMap, rc::Rc};
type Env = crate::env::Env<u32, Value>;
type Joins = BTreeMap<u32, Rc<Join>>;
#[derive(Clone, Debug)]
/// Strict data, lexical closures, and partial applications.
pub enum Value {
Lit(Lit),
Con(ConId, Rc<Vec<Value>>, Option<Vec<String>>),
Closure(Rc<Closure>),
Pap(Rc<Value>, Vec<Value>),
}
impl Drop for Value {
fn drop(&mut self) {
fn children(value: &mut Value, todo: &mut Vec<Value>) {
match value {
Value::Con(_, fields, _) => {
if !fields.is_empty()
&& let Ok(values) = Rc::try_unwrap(
std::mem::replace(fields, Rc::new(vec![])),
)
{
todo.extend(values);
}
}
Value::Pap(base, args) => {
todo.append(args);
if let Some(value) = Rc::get_mut(base) {
todo.push(std::mem::replace(
value,
Value::Lit(Lit::Int(0)),
));
}
}
Value::Closure(c) => {
if let Some(c) = Rc::get_mut(c)
&& let Some(env) = Rc::get_mut(&mut c.env)
{
env.drain_unique(todo);
}
}
_ => {}
}
}
let mut todo = vec![];
children(self, &mut todo);
while let Some(mut value) = todo.pop() {
children(&mut value, &mut todo);
}
}
}
#[derive(Clone, Debug)]
/// Recursive groups are shared by index, avoiding reference-count cycles.
pub struct Closure {
lambda: Lambda,
env: Rc<Env>,
recursive: Option<usize>,
}
#[derive(Clone)]
struct Join {
params: Vec<Var>,
body: Body,
env: Env,
joins: Joins,
}
enum Frame {
Bind(Var, Body, Env, Joins),
Apply(Vec<Value>),
}
#[derive(Clone, Copy, Debug, Default)]
/// Continuation depth counts pending non-tail calls, not recursive tail transfers.
pub struct Stats {
pub steps: usize,
pub max_continuations: usize,
}
struct Machine<'a> {
groups: Vec<Env>,
program: &'a anf::Program,
globals: Env,
env: Env,
joins: Joins,
stack: Vec<Frame>,
fuel: usize,
stats: Stats,
}
fn key(v: &Var) -> u32 {
v.name.unique
}
fn closure(
lambda: Lambda,
env: Rc<Env>,
recursive: Option<usize>,
) -> Value {
Value::Closure(Rc::new(Closure {
lambda,
env,
recursive,
}))
}
fn function(body: &Body) -> Option<Lambda> {
if let Anf::Let(v, Rhs::Lambda(l), b) = body.as_ref()
&& matches!(b.as_ref(),Anf::Ret(Atom::Var(w)) if v==w)
{
Some(l.clone())
} else {
None
}
}
impl Machine<'_> {
fn atom(&self, a: &Atom) -> Result<Value, Failure> {
match a {
Atom::Lit(l) => Ok(Value::Lit(l.clone())),
Atom::Var(v) => {
self.env.get(&key(v)).cloned().ok_or_else(|| {
format!("internal error: unbound ANF variable {v}")
.into()
})
}
Atom::Global(v) => {
self.globals.get(&key(v)).cloned().ok_or_else(|| {
format!("internal error: uninitialized ANF global {v}")
.into()
})
}
}
}
fn atoms(&self, args: &[Atom]) -> Result<Vec<Value>, Failure> {
args.iter().map(|a| self.atom(a)).collect()
}
fn rhs(&self, r: &Rhs) -> Result<Value, Failure> {
match r {
Rhs::Atom(a) => self.atom(a),
Rhs::Con(c, args) => Ok(Value::Con(
c.clone(),
Rc::new(self.atoms(args)?),
self.program.metadata.constructors[c.index as usize]
.labels
.clone(),
)),
Rhs::Lambda(l) => {
Ok(closure(l.clone(), Rc::new(self.env.clone()), None))
}
Rhs::Field(a, i) => match &self.atom(a)? {
Value::Con(_, fields, _) => {
fields.get(*i as usize).cloned().ok_or_else(|| {
"internal error: invalid field index".into()
})
}
_ => Err("internal error: field on non-constructor".into()),
},
Rhs::Prim(op, args, _) => {
let p = match op {
Op::Runtime(p) => *p,
Op::Add => crate::primitives::Prim::IntAdd,
Op::Sub => crate::primitives::Prim::IntSub,
Op::Mul => crate::primitives::Prim::IntMul,
Op::Div => crate::primitives::Prim::IntDiv,
Op::Mod => crate::primitives::Prim::IntMod,
Op::Eq => crate::primitives::Prim::IntEq,
Op::Lt => crate::primitives::Prim::IntLt,
Op::Le => crate::primitives::Prim::IntLe,
Op::Append => crate::primitives::Prim::StrAppend,
};
let values = self.atoms(args)?;
let args = values
.iter()
.map(to_core)
.collect::<Result<Vec<_>, _>>()?;
crate::primitives::evaluate(
p,
&args,
&self.program.metadata,
)
.map(from_core)
}
Rhs::Call(..) => unreachable!("calls are machine transitions"),
}
}
fn run(&mut self, mut state: State) -> Result<Value, Failure> {
loop {
if self.fuel == 0 {
return Err("step limit exceeded".into());
}
self.fuel -= 1;
self.stats.steps += 1;
self.stats.max_continuations =
self.stats.max_continuations.max(self.stack.len());
state = match state {
State::Code(body) => match body.as_ref() {
Anf::Ret(a) => State::Return(self.atom(a)?),
Anf::TailCall(f, args) => {
State::Apply(self.atom(f)?, self.atoms(args)?)
}
Anf::Let(v, Rhs::Call(f, args), rest) => {
let f = self.atom(f)?;
let args = self.atoms(args)?;
self.stack.push(Frame::Bind(
v.clone(),
rest.clone(),
std::mem::take(&mut self.env),
std::mem::take(&mut self.joins),
));
State::Apply(f, args)
}
Anf::Let(v, r, rest) => {
let value = self.rhs(r)?;
self.env.insert(key(v), value);
State::Code(rest.clone())
}
Anf::LetRec(bindings, rest) => {
let index = self.groups.len();
let env = Rc::new(self.env.clone());
for (v, l) in bindings {
self.env.insert(
key(v),
closure(
l.clone(),
env.clone(),
Some(index),
),
);
}
self.groups.push(self.env.clone());
State::Code(rest.clone())
}
Anf::Join(j, params, body, rest) => {
let join = Join {
params: params.clone(),
body: body.clone(),
env: self.env.clone(),
joins: self.joins.clone(),
};
self.joins.insert(key(j), Rc::new(join));
State::Code(rest.clone())
}
Anf::Jump(j, args) => {
let values = self.atoms(args)?;
let join =
self.joins.get(&key(j)).cloned().ok_or(
"internal error: unbound ANF join",
)?;
if values.len() != join.params.len() {
return Err(
"internal error: ANF jump arity".into()
);
}
self.env = join.env.clone();
self.joins = join.joins.clone();
self.env.extend(
join.params.iter().map(key).zip(values),
);
State::Code(join.body.clone())
}
Anf::Case(a, alts) => {
let value = self.atom(a)?;
let mut chosen = None;
for (c, ps, b) in alts {
let fields = match (c, &value) {
(AltCon::Default, _) => Some(vec![]),
(
AltCon::Con(c),
Value::Con(d, fields, _),
) if c == d => Some((**fields).clone()),
(AltCon::Lit(a), Value::Lit(b))
if a == b =>
{
Some(vec![])
}
_ => None,
};
if let Some(fields) = fields {
self.env
.extend(ps.iter().map(key).zip(fields));
chosen = Some(b.clone());
break;
}
}
State::Code(chosen.ok_or(
"internal error: ANF case has no alternative",
)?)
}
Anf::Fail(span) => {
let site = self
.program
.metadata
.locations
.iter()
.find(|(s, _)| s == span)
.map(|(_, s)| s.as_str())
.unwrap_or("<unknown>:1:1");
return Err(format!(
"pattern match failure at {site}"
)
.into());
}
},
State::Apply(f, args) => match &f {
Value::Pap(base, earlier) => {
let mut earlier = earlier.clone();
earlier.extend(args);
State::Apply((**base).clone(), earlier)
}
Value::Closure(c) => {
let arity = c.lambda.params.len();
if args.len() < arity {
State::Return(Value::Pap(
Rc::new(Value::Closure(c.clone())),
args,
))
} else {
let mut args = args;
let extra = args.split_off(arity);
if !extra.is_empty() {
self.stack.push(Frame::Apply(extra));
}
self.env = (*c.env).clone();
self.joins.clear();
if let Some(index) = c.recursive {
self.env = self.groups[index].clone();
}
self.env.extend(
c.lambda.params.iter().map(key).zip(args),
);
State::Code(c.lambda.body.clone())
}
}
_ => {
return Err(
"internal error: application of non-function"
.into(),
);
}
},
State::Return(value) => match self.stack.pop() {
None => return Ok(value),
Some(Frame::Apply(args)) => State::Apply(value, args),
Some(Frame::Bind(v, b, mut env, joins)) => {
env.insert(key(&v), value);
self.env = env;
self.joins = joins;
State::Code(b)
}
},
};
}
}
}
/// Independent control flow, with shared monomorphic primitive definitions.
pub fn run(
program: &anf::Program,
fuel: usize,
io: bool,
) -> Result<(Value, Stats), Failure> {
let mut m = Machine {
groups: vec![],
program,
globals: Env::new(),
env: Env::new(),
joins: Joins::new(),
stack: vec![],
fuel,
stats: Stats::default(),
};
for (v, b) in &program.globals {
if let Some(l) = function(b) {
m.globals
.insert(key(v), closure(l, Rc::new(Env::new()), None));
}
}
for (v, b) in &program.globals {
if function(b).is_none() {
m.env.clear();
m.joins.clear();
let value = m.run(State::Code(b.clone()))?;
m.globals.insert(key(v), value);
}
}
let main = m
.globals
.get(&program.metadata.main.unique())
.cloned()
.ok_or("internal error: missing main")?;
let value = if io {
let unit = program
.metadata
.constructors
.iter()
.find(|c| c.id.name == "()")
.ok_or("internal error: missing unit")?;
m.run(State::Apply(
main,
vec![Value::Con(unit.id.clone(), Rc::new(vec![]), None)],
))?
} else {
main
};
Ok((value, m.stats))
}
fn to_core(v: &Value) -> Result<crate::eval::Value, Failure> {
Ok(match v {
Value::Lit(l) => crate::eval::Value::Lit(l.clone()),
Value::Con(c, fields, labels) => crate::eval::Value::Con(
c.clone(),
Rc::new(fields.iter().map(to_core).collect::<Result<_, _>>()?),
labels.clone(),
),
_ => {
return Err(
"internal error: function passed to a data primitive"
.into(),
);
}
})
}
fn from_core(v: crate::eval::Value) -> Value {
match &v {
crate::eval::Value::Lit(l) => Value::Lit(l.clone()),
crate::eval::Value::Con(c, fields, labels) => Value::Con(
c.clone(),
Rc::new(fields.iter().cloned().map(from_core).collect()),
labels.clone(),
),
_ => unreachable!("primitive cannot return a closure"),
}
}
impl std::fmt::Display for Value {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
self.print(f, 0)
}
}
impl Value {
fn print(
&self,
f: &mut std::fmt::Formatter<'_>,
precedence: u8,
) -> std::fmt::Result {
match self {
Self::Lit(Lit::Double(n))
if f64::from_bits(*n).is_sign_negative()
&& precedence > 6 =>
{
write!(
f,
"({})",
crate::primitives::show_double(f64::from_bits(*n))
)
}
Self::Lit(Lit::Int(n)) if *n < 0 && precedence > 6 => {
write!(f, "({n})")
}
Self::Lit(l) => write!(f, "{l}"),
Self::Closure(_) | Self::Pap(..) => write!(f, "<function>"),
Self::Con(id, fields, Some(labels)) => {
if precedence > 10 {
write!(f, "(")?;
}
write!(f, "{} {{", id.name)?;
for (i, (name, value)) in
labels.iter().zip(fields.iter()).enumerate()
{
if i > 0 {
write!(f, ", ")?;
}
write!(f, "{name} = ")?;
value.print(f, 0)?;
}
write!(f, "}}")?;
if precedence > 10 {
write!(f, ")")?;
}
Ok(())
}
Self::Con(id, fields, None) => match id.name.as_str() {
"[]" => write!(f, "[]"),
":" => {
write!(f, "[")?;
let mut value = self;
let mut first = true;
while let Self::Con(c, fs, _) = value {
if c.name == "[]" {
break;
}
if !first {
write!(f, ",")?;
}
first = false;
fs[0].print(f, 0)?;
value = &fs[1];
}
write!(f, "]")
}
"()" | "(,)" | "(,,)" => {
write!(f, "(")?;
for (i, v) in fields.iter().enumerate() {
if i > 0 {
write!(f, ",")?;
}
v.print(f, 0)?;
}
write!(f, ")")
}
_ => {
let parens = precedence > 10 && !fields.is_empty();
if parens {
write!(f, "(")?;
}
write!(f, "{}", id.name)?;
for v in fields.iter() {
write!(f, " ")?;
v.print(f, 11)?;
}
if parens {
write!(f, ")")?;
}
Ok(())
}
},
}
}
}
enum State {
Code(Body),
Apply(Value, Vec<Value>),
Return(Value),
}
use crate::{
anf::{self, Anf, Atom, Body, Lambda, Rhs, Var},
ast::Op,
core::{AltCon, Lit},
data::ConId,
eval::Failure,
};
use std::{collections::BTreeMap, rc::Rc};
type Env = crate::env::Env<u32, Value>;
type Joins = BTreeMap<u32, Rc<Join>>;
#[derive(Clone, Debug)]
/// Strict data, lexical closures, and partial applications.
pub enum Value {
Lit(Lit),
Con(ConId, Rc<Vec<Value>>, Option<Vec<String>>),
Closure(Rc<Closure>),
Pap(Rc<Value>, Vec<Value>),
}
impl Drop for Value {
fn drop(&mut self) {
fn children(value: &mut Value, todo: &mut Vec<Value>) {
match value {
Value::Con(_, fields, _) => {
if !fields.is_empty()
&& let Ok(values) = Rc::try_unwrap(
std::mem::replace(fields, Rc::new(vec![])),
)
{
todo.extend(values);
}
}
Value::Pap(base, args) => {
todo.append(args);
if let Some(value) = Rc::get_mut(base) {
todo.push(std::mem::replace(
value,
Value::Lit(Lit::Int(0)),
));
}
}
Value::Closure(c) => {
if let Some(c) = Rc::get_mut(c)
&& let Some(env) = Rc::get_mut(&mut c.env)
{
env.drain_unique(todo);
}
}
_ => {}
}
}
let mut todo = vec![];
children(self, &mut todo);
while let Some(mut value) = todo.pop() {
children(&mut value, &mut todo);
}
}
}
#[derive(Clone, Debug)]
/// Recursive groups are shared by index, avoiding reference-count cycles.
pub struct Closure {
lambda: Lambda,
env: Rc<Env>,
recursive: Option<usize>,
}
#[derive(Clone)]
struct Join {
params: Vec<Var>,
body: Body,
env: Env,
joins: Joins,
}
enum State {
Code(Body),
Apply(Value, Vec<Value>),
Return(Value),
}
#[derive(Clone, Copy, Debug, Default)]
/// Continuation depth counts pending non-tail calls, not recursive tail transfers.
pub struct Stats {
pub steps: usize,
pub max_continuations: usize,
}
struct Machine<'a> {
groups: Vec<Env>,
program: &'a anf::Program,
globals: Env,
env: Env,
joins: Joins,
stack: Vec<Frame>,
fuel: usize,
stats: Stats,
}
fn key(v: &Var) -> u32 {
v.name.unique
}
fn closure(
lambda: Lambda,
env: Rc<Env>,
recursive: Option<usize>,
) -> Value {
Value::Closure(Rc::new(Closure {
lambda,
env,
recursive,
}))
}
fn function(body: &Body) -> Option<Lambda> {
if let Anf::Let(v, Rhs::Lambda(l), b) = body.as_ref()
&& matches!(b.as_ref(),Anf::Ret(Atom::Var(w)) if v==w)
{
Some(l.clone())
} else {
None
}
}
impl Machine<'_> {
fn atom(&self, a: &Atom) -> Result<Value, Failure> {
match a {
Atom::Lit(l) => Ok(Value::Lit(l.clone())),
Atom::Var(v) => {
self.env.get(&key(v)).cloned().ok_or_else(|| {
format!("internal error: unbound ANF variable {v}")
.into()
})
}
Atom::Global(v) => {
self.globals.get(&key(v)).cloned().ok_or_else(|| {
format!("internal error: uninitialized ANF global {v}")
.into()
})
}
}
}
fn atoms(&self, args: &[Atom]) -> Result<Vec<Value>, Failure> {
args.iter().map(|a| self.atom(a)).collect()
}
fn rhs(&self, r: &Rhs) -> Result<Value, Failure> {
match r {
Rhs::Atom(a) => self.atom(a),
Rhs::Con(c, args) => Ok(Value::Con(
c.clone(),
Rc::new(self.atoms(args)?),
self.program.metadata.constructors[c.index as usize]
.labels
.clone(),
)),
Rhs::Lambda(l) => {
Ok(closure(l.clone(), Rc::new(self.env.clone()), None))
}
Rhs::Field(a, i) => match &self.atom(a)? {
Value::Con(_, fields, _) => {
fields.get(*i as usize).cloned().ok_or_else(|| {
"internal error: invalid field index".into()
})
}
_ => Err("internal error: field on non-constructor".into()),
},
Rhs::Prim(op, args, _) => {
let p = match op {
Op::Runtime(p) => *p,
Op::Add => crate::primitives::Prim::IntAdd,
Op::Sub => crate::primitives::Prim::IntSub,
Op::Mul => crate::primitives::Prim::IntMul,
Op::Div => crate::primitives::Prim::IntDiv,
Op::Mod => crate::primitives::Prim::IntMod,
Op::Eq => crate::primitives::Prim::IntEq,
Op::Lt => crate::primitives::Prim::IntLt,
Op::Le => crate::primitives::Prim::IntLe,
Op::Append => crate::primitives::Prim::StrAppend,
};
let values = self.atoms(args)?;
let args = values
.iter()
.map(to_core)
.collect::<Result<Vec<_>, _>>()?;
crate::primitives::evaluate(
p,
&args,
&self.program.metadata,
)
.map(from_core)
}
Rhs::Call(..) => unreachable!("calls are machine transitions"),
}
}
fn run(&mut self, mut state: State) -> Result<Value, Failure> {
loop {
if self.fuel == 0 {
return Err("step limit exceeded".into());
}
self.fuel -= 1;
self.stats.steps += 1;
self.stats.max_continuations =
self.stats.max_continuations.max(self.stack.len());
state = match state {
State::Code(body) => match body.as_ref() {
Anf::Ret(a) => State::Return(self.atom(a)?),
Anf::TailCall(f, args) => {
State::Apply(self.atom(f)?, self.atoms(args)?)
}
Anf::Let(v, Rhs::Call(f, args), rest) => {
let f = self.atom(f)?;
let args = self.atoms(args)?;
self.stack.push(Frame::Bind(
v.clone(),
rest.clone(),
std::mem::take(&mut self.env),
std::mem::take(&mut self.joins),
));
State::Apply(f, args)
}
Anf::Let(v, r, rest) => {
let value = self.rhs(r)?;
self.env.insert(key(v), value);
State::Code(rest.clone())
}
Anf::LetRec(bindings, rest) => {
let index = self.groups.len();
let env = Rc::new(self.env.clone());
for (v, l) in bindings {
self.env.insert(
key(v),
closure(
l.clone(),
env.clone(),
Some(index),
),
);
}
self.groups.push(self.env.clone());
State::Code(rest.clone())
}
Anf::Join(j, params, body, rest) => {
let join = Join {
params: params.clone(),
body: body.clone(),
env: self.env.clone(),
joins: self.joins.clone(),
};
self.joins.insert(key(j), Rc::new(join));
State::Code(rest.clone())
}
Anf::Jump(j, args) => {
let values = self.atoms(args)?;
let join =
self.joins.get(&key(j)).cloned().ok_or(
"internal error: unbound ANF join",
)?;
if values.len() != join.params.len() {
return Err(
"internal error: ANF jump arity".into()
);
}
self.env = join.env.clone();
self.joins = join.joins.clone();
self.env.extend(
join.params.iter().map(key).zip(values),
);
State::Code(join.body.clone())
}
Anf::Case(a, alts) => {
let value = self.atom(a)?;
let mut chosen = None;
for (c, ps, b) in alts {
let fields = match (c, &value) {
(AltCon::Default, _) => Some(vec![]),
(
AltCon::Con(c),
Value::Con(d, fields, _),
) if c == d => Some((**fields).clone()),
(AltCon::Lit(a), Value::Lit(b))
if a == b =>
{
Some(vec![])
}
_ => None,
};
if let Some(fields) = fields {
self.env
.extend(ps.iter().map(key).zip(fields));
chosen = Some(b.clone());
break;
}
}
State::Code(chosen.ok_or(
"internal error: ANF case has no alternative",
)?)
}
Anf::Fail(span) => {
let site = self
.program
.metadata
.locations
.iter()
.find(|(s, _)| s == span)
.map(|(_, s)| s.as_str())
.unwrap_or("<unknown>:1:1");
return Err(format!(
"pattern match failure at {site}"
)
.into());
}
},
State::Apply(f, args) => match &f {
Value::Pap(base, earlier) => {
let mut earlier = earlier.clone();
earlier.extend(args);
State::Apply((**base).clone(), earlier)
}
Value::Closure(c) => {
let arity = c.lambda.params.len();
if args.len() < arity {
State::Return(Value::Pap(
Rc::new(Value::Closure(c.clone())),
args,
))
} else {
let mut args = args;
let extra = args.split_off(arity);
if !extra.is_empty() {
self.stack.push(Frame::Apply(extra));
}
self.env = (*c.env).clone();
self.joins.clear();
if let Some(index) = c.recursive {
self.env = self.groups[index].clone();
}
self.env.extend(
c.lambda.params.iter().map(key).zip(args),
);
State::Code(c.lambda.body.clone())
}
}
_ => {
return Err(
"internal error: application of non-function"
.into(),
);
}
},
State::Return(value) => match self.stack.pop() {
None => return Ok(value),
Some(Frame::Apply(args)) => State::Apply(value, args),
Some(Frame::Bind(v, b, mut env, joins)) => {
env.insert(key(&v), value);
self.env = env;
self.joins = joins;
State::Code(b)
}
},
};
}
}
}
/// Independent control flow, with shared monomorphic primitive definitions.
pub fn run(
program: &anf::Program,
fuel: usize,
io: bool,
) -> Result<(Value, Stats), Failure> {
let mut m = Machine {
groups: vec![],
program,
globals: Env::new(),
env: Env::new(),
joins: Joins::new(),
stack: vec![],
fuel,
stats: Stats::default(),
};
for (v, b) in &program.globals {
if let Some(l) = function(b) {
m.globals
.insert(key(v), closure(l, Rc::new(Env::new()), None));
}
}
for (v, b) in &program.globals {
if function(b).is_none() {
m.env.clear();
m.joins.clear();
let value = m.run(State::Code(b.clone()))?;
m.globals.insert(key(v), value);
}
}
let main = m
.globals
.get(&program.metadata.main.unique())
.cloned()
.ok_or("internal error: missing main")?;
let value = if io {
let unit = program
.metadata
.constructors
.iter()
.find(|c| c.id.name == "()")
.ok_or("internal error: missing unit")?;
m.run(State::Apply(
main,
vec![Value::Con(unit.id.clone(), Rc::new(vec![]), None)],
))?
} else {
main
};
Ok((value, m.stats))
}
fn to_core(v: &Value) -> Result<crate::eval::Value, Failure> {
Ok(match v {
Value::Lit(l) => crate::eval::Value::Lit(l.clone()),
Value::Con(c, fields, labels) => crate::eval::Value::Con(
c.clone(),
Rc::new(fields.iter().map(to_core).collect::<Result<_, _>>()?),
labels.clone(),
),
_ => {
return Err(
"internal error: function passed to a data primitive"
.into(),
);
}
})
}
fn from_core(v: crate::eval::Value) -> Value {
match &v {
crate::eval::Value::Lit(l) => Value::Lit(l.clone()),
crate::eval::Value::Con(c, fields, labels) => Value::Con(
c.clone(),
Rc::new(fields.iter().cloned().map(from_core).collect()),
labels.clone(),
),
_ => unreachable!("primitive cannot return a closure"),
}
}
impl std::fmt::Display for Value {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
self.print(f, 0)
}
}
impl Value {
fn print(
&self,
f: &mut std::fmt::Formatter<'_>,
precedence: u8,
) -> std::fmt::Result {
match self {
Self::Lit(Lit::Double(n))
if f64::from_bits(*n).is_sign_negative()
&& precedence > 6 =>
{
write!(
f,
"({})",
crate::primitives::show_double(f64::from_bits(*n))
)
}
Self::Lit(Lit::Int(n)) if *n < 0 && precedence > 6 => {
write!(f, "({n})")
}
Self::Lit(l) => write!(f, "{l}"),
Self::Closure(_) | Self::Pap(..) => write!(f, "<function>"),
Self::Con(id, fields, Some(labels)) => {
if precedence > 10 {
write!(f, "(")?;
}
write!(f, "{} {{", id.name)?;
for (i, (name, value)) in
labels.iter().zip(fields.iter()).enumerate()
{
if i > 0 {
write!(f, ", ")?;
}
write!(f, "{name} = ")?;
value.print(f, 0)?;
}
write!(f, "}}")?;
if precedence > 10 {
write!(f, ")")?;
}
Ok(())
}
Self::Con(id, fields, None) => match id.name.as_str() {
"[]" => write!(f, "[]"),
":" => {
write!(f, "[")?;
let mut value = self;
let mut first = true;
while let Self::Con(c, fs, _) = value {
if c.name == "[]" {
break;
}
if !first {
write!(f, ",")?;
}
first = false;
fs[0].print(f, 0)?;
value = &fs[1];
}
write!(f, "]")
}
"()" | "(,)" | "(,,)" => {
write!(f, "(")?;
for (i, v) in fields.iter().enumerate() {
if i > 0 {
write!(f, ",")?;
}
v.print(f, 0)?;
}
write!(f, ")")
}
_ => {
let parens = precedence > 10 && !fields.is_empty();
if parens {
write!(f, "(")?;
}
write!(f, "{}", id.name)?;
for v in fields.iter() {
write!(f, " ")?;
v.print(f, 11)?;
}
if parens {
write!(f, ")")?;
}
Ok(())
}
},
}
}
}
enum Frame {
Bind(Var, Body, Env, Joins),
Apply(Vec<Value>),
}
}Closures carry a lambda and a shared lexical environment. Recursive groups are built once in a machine-owned table. Their closures hold the group’s index, which avoids reference-count cycles and rebuilding closures at every call. Applying too few arguments returns a partial application. Excess arguments are applied to the returned function. Tail calls replace the current state, and jumps enter a lexically captured join environment. Neither transfer recursively invokes the Rust interpreter. Primitive values cross a data-only adapter to the existing primitive implementation. Control flow does not call the Core evaluator.
Running It
$ cd crates/ch18_anf
$ cargo run -q -- run tests/programs/anf/case-continuation.fun --lint
7
$ cargo run -q -- dump --pass=types tests/programs/anf/case-continuation.fun
main : IO ()
Use --pass=erase to see type-free Core and --pass=anf to see named operations.
Repeat the latter with --no-simplify to distinguish conversion from rewriting.
Repeat execution with --engine=core to compare the reference result. Dumps
include the Prelude. The small snapshots in tests/anf.rs isolate individual
transformations such as a non-tail case and a guard-failure join.
Alongside the handwritten examples, testkit/src/gen.rs generates small
well-typed programs containing arithmetic, local bindings, branches, recursion,
and lists. Both engines must agree with an independent wrapping-integer
calculation. We save the source and seed of a failure so an unexpected answer
becomes a program we can debug.
A million-call sum is a useful test of the machine’s control flow. We measure the number of pending continuations, rather than just checking that it finishes. A tail call should replace the current computation. A non-tail call may add pending work to the heap-allocated continuation stack. Neither needs another Rust call frame. Core uses its own explicit machine, so comparing it with ANF also checks that conversion hasn’t changed the answer.
Exercises
- Warm-up. Locate the continuation after the example’s case in an unsimplified ANF dump.
- Intermediate. Make two arguments fail with different messages and check which must run first for a known call and an unknown call.
- Intermediate. Explain why removing an unused division can be wrong even though integer division has no IO effects.
- Advanced. Instrument the machine on tail-recursive and non-tail-recursive sums and compare maximum continuation depth.
- Advanced. Extend the deterministic generator with one new well-typed construct and an independent expected-result calculation.
Further Reading
- Direct representations and continuation-based compilation (Flanagan et al. 1993).
- Join points and shared continuations (Maurer et al. 2017).
- The CEK machine’s control, environment, and continuation (Felleisen and Friedman 1986).
- Continuation-based compiler construction (Appel 1992).
- Polymorphism and type erasure (Pierce 2002).