Appendix C: Intermediate Representations
The final compiler has three executable intermediate languages. Each removes a specific obligation from the next pass. These definitions are included from Chapter 24, so the reference and implementation stay together.
| Representation | Makes explicit | Still leaves implicit |
|---|---|---|
| System F Core | Types, dictionaries, constructors, control flow | Evaluation temporaries and closure environments |
| ANF | Evaluation order, intermediate results, joins, tail calls | Captured variables and application dispatch |
| Flat | Lifted code, closure fields, known and unknown calls | Physical storage and machine instructions |
Typed Core
A value identifier carries its type. A type application instantiates a type
abstraction. Dictionary arguments are ordinary value arguments, so erasing
TyLam and TyApp does not erase class evidence.
#![allow(unused)]
fn main() {
pub use crate::core_type::Type;
use crate::{ast::Op, source::Span};
impl std::fmt::Display for Id {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{} : {}", self.name, self.ty)
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
/// Immediate source values; strings are primitive UTF-8 values, not character lists.
pub enum Lit {
Double(u64),
Int(i64),
Char(char),
String(String),
}
#[derive(Clone, Debug)]
/// System F Core makes type abstraction and instantiation explicit.
pub enum Expr {
Var(Id),
Global(Id),
TyLam(u32, Box<Expr>),
TyApp(Box<Expr>, Type),
Lit(Lit),
Lam(Id, Box<Expr>),
App(Box<Expr>, Box<Expr>),
Let(BindGroup, Box<Expr>),
Con(crate::data::ConId, Vec<Type>, Vec<Expr>),
Match(Match),
Case(Box<Expr>, Id, Type, Vec<Alt>),
Join(crate::names::Id, Vec<Id>, Box<Expr>, Box<Expr>),
Jump(crate::names::Id, Vec<Expr>, Type),
PatternFail(Span, Type),
Prim(Op, Vec<Type>, Vec<Expr>, Span),
}
/// Flat alternatives inspect one constructor or literal, never nested patterns.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum AltCon {
Con(crate::data::ConId),
Lit(Lit),
Default,
}
/// Constructor slots become typed binders scoped over the alternative body.
#[derive(Clone, Debug)]
pub struct Alt {
pub con: AltCon,
pub binders: Vec<Id>,
pub rhs: Expr,
}
#[derive(Clone, Debug)]
/// A recursive binding is guaranteed to have a lambda right-hand side.
pub struct Bind {
pub name: Id,
pub rhs: Box<Expr>,
}
#[derive(Clone, Debug)]
/// An ordered component; recursive members are in scope in every right-hand side.
pub struct BindGroup {
pub recursive: bool,
pub binds: Vec<Bind>,
}
#[derive(Clone, Debug)]
/// Globals are initialized in dependency order, with explicit recursive components.
pub struct Program {
pub groups: Vec<BindGroup>,
/// Flat type fingerprints survive erasure for cross-module ABI checks.
pub global_types:
std::collections::BTreeMap<crate::names::Id, Vec<String>>,
pub main: Id,
pub data_types: Vec<(crate::data::TyConId, crate::kinds::Kind)>,
pub type_kinds: std::collections::BTreeMap<u32, crate::kinds::Kind>,
pub constructors: Vec<ConDecl>,
pub locations: Vec<(Span, String)>,
}
impl std::fmt::Display for Expr {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Case(scrut, binder, ty, alts) => {
write!(f, "(case {scrut} as {binder} -> {ty}")?;
for alt in alts {
write!(f, " [ {:?}", alt.con)?;
for id in &alt.binders {
write!(f, " {id}")?;
}
write!(f, " -> {} ]", alt.rhs)?;
}
write!(f, ")")
}
Self::Join(id, params, body, rest) => {
write!(f, "(join {id} (")?;
for p in params {
write!(f, " {p}")?;
}
write!(f, ") = {body} in {rest})")
}
Self::Jump(id, args, ty) => {
write!(f, "(jump {id} : {ty}")?;
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
Self::Var(n) => write!(f, "{}", n.name),
Self::Global(n) => write!(f, "@{}", n.name),
Self::TyLam(v, b) => write!(f, "(type-lambda t{v} {b})"),
Self::TyApp(a, t) => write!(f, "(type-app {a} {t})"),
Self::Lit(l) => write!(f, "{l}"),
Self::Lam(n, b) => write!(f, "(lambda {n} {b})"),
Self::App(a, b) => write!(f, "(app {a} {b})"),
Self::Let(group, body) => write!(f, "(let {group} in {body})"),
Self::Con(id, types, args) => {
write!(f, "(con {}", id.name)?;
for t in types {
write!(f, " [{t}]")?;
}
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
Self::Match(m) => {
write!(f, "(match")?;
for s in &m.scruts {
write!(f, " {}", s.name)?;
}
for row in &m.rows {
write!(f, " {row}")?;
}
write!(f, ")")
}
Self::PatternFail(_, ty) => write!(f, "(pattern-fail : {ty})"),
Self::Prim(op, _, args, _) => {
write!(f, "(prim {}", op.text())?;
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
}
}
}
impl std::fmt::Display for Lit {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Double(bits) => write!(
f,
"{}",
crate::primitives::show_double(f64::from_bits(*bits))
),
Self::Int(n) => write!(f, "{n}"),
Self::Char(c) => {
write!(f, "{}", crate::ast::quote(&c.to_string(), '\''))
}
Self::String(s) => write!(f, "{}", crate::ast::quote(s, '"')),
}
}
}
impl std::fmt::Display for BindGroup {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{} {{", if self.recursive { "rec" } else { "nonrec" })?;
for b in &self.binds {
write!(f, " {} = {};", b.name, b.rhs)?;
}
write!(f, " }}")
}
}
/// Independently typecheck System F Core after each Core-producing pass.
pub fn lint(program: &Program) -> Result<(), String> {
crate::core_lint::lint(program)
}
impl Id {
pub fn unique(&self) -> u32 {
self.name.name.unique
}
}
/// Constructor typing is immutable and contains no inference metavariables.
#[derive(Clone, Debug)]
pub struct ConDecl {
pub labels: Option<Vec<String>>,
pub id: crate::data::ConId,
pub tag: u32,
pub parameters: Vec<u32>,
pub fields: Vec<Type>,
pub result: Type,
}
/// Nested patterns remain until the decision-tree compiler in Chapter 16.
#[derive(Clone, Debug)]
pub enum Pat {
Var(Id),
Wild,
As(Id, Box<Pat>),
Con(crate::data::ConId, Vec<Pat>),
Lit(Lit),
}
/// A guarded row falls through when all its Boolean tests fail.
#[derive(Clone, Debug)]
pub enum RowBody {
Plain(Box<Expr>),
Guarded(Vec<(Expr, Expr)>),
}
/// Row-local declarations run after patterns match and are shared by the guards.
#[derive(Clone, Debug)]
pub struct Row {
pub pats: Vec<Pat>,
pub locals: Vec<BindGroup>,
pub body: RowBody,
pub span: Span,
}
/// Scrutinees name strict preceding lets; the match records its result type and failure site.
#[derive(Clone, Debug)]
pub struct Match {
pub scruts: Vec<Id>,
pub rows: Vec<Row>,
pub result: Type,
pub span: Span,
}
impl std::fmt::Display for Pat {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Var(id) => write!(f, "{}", id.name),
Self::Wild => write!(f, "_"),
Self::As(id, p) => write!(f, "{}@{p}", id.name),
Self::Lit(l) => write!(f, "{l}"),
Self::Con(id, ps) => {
write!(f, "({}", id.name)?;
for p in ps {
write!(f, " {p}")?;
}
write!(f, ")")
}
}
}
}
impl std::fmt::Display for Row {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "[ ")?;
for p in &self.pats {
write!(f, "{p} ")?;
}
for local in &self.locals {
write!(f, "{local} ")?;
}
match &self.body {
RowBody::Plain(e) => write!(f, "-> {e}")?,
RowBody::Guarded(gs) => {
for (g, e) in gs {
write!(f, "| {g} -> {e} ")?;
}
}
}
write!(f, " ]")
}
}
/// Type abstractions erase; a constrained value is an ordinary dictionary function.
pub fn is_function(mut e: &Expr) -> bool {
while let Expr::TyLam(_, body) = e {
e = body;
}
matches!(e, Expr::Lam(..))
}
/// Dictionary calls introduce global dependencies absent from the source graph.
pub fn order(groups: Vec<BindGroup>) -> Vec<BindGroup> {
fn refs(e: &Expr, out: &mut std::collections::BTreeSet<u32>) {
match e {
Expr::Case(s, _, _, alts) => {
refs(s, out);
for a in alts {
refs(&a.rhs, out)
}
}
Expr::Join(_, _, b, r) => {
refs(b, out);
refs(r, out)
}
Expr::Jump(_, args, _) => {
for a in args {
refs(a, out)
}
}
Expr::Global(id) => {
out.insert(id.unique());
}
Expr::Lam(_, b) | Expr::TyLam(_, b) | Expr::TyApp(b, _) => {
refs(b, out)
}
Expr::App(a, b) => {
refs(a, out);
refs(b, out);
}
Expr::Let(g, b) => {
for bind in &g.binds {
refs(&bind.rhs, out);
}
refs(b, out);
}
Expr::Con(_, _, args) | Expr::Prim(_, _, args, _) => {
for a in args {
refs(a, out);
}
}
Expr::Match(m) => {
for row in &m.rows {
for g in &row.locals {
for b in &g.binds {
refs(&b.rhs, out);
}
}
match &row.body {
RowBody::Plain(e) => refs(e, out),
RowBody::Guarded(gs) => {
for (g, e) in gs {
refs(g, out);
refs(e, out);
}
}
}
}
}
_ => {}
}
}
let binds =
groups.into_iter().flat_map(|g| g.binds).collect::<Vec<_>>();
let indices = binds
.iter()
.enumerate()
.map(|(i, b)| (b.name.unique(), i))
.collect::<std::collections::BTreeMap<_, _>>();
let edges = binds
.iter()
.map(|b| {
let mut names = std::collections::BTreeSet::new();
refs(&b.rhs, &mut names);
names
.into_iter()
.filter_map(|n| indices.get(&n).copied())
.collect::<Vec<_>>()
})
.collect::<Vec<_>>();
let mut binds = binds.into_iter().map(Some).collect::<Vec<_>>();
crate::scc::components(&edges)
.into_iter()
.map(|xs| BindGroup {
recursive: (xs.len() > 1 || edges[xs[0]].contains(&xs[0]))
&& xs
.iter()
.all(|i| is_function(&binds[*i].as_ref().unwrap().rhs)),
binds: xs
.into_iter()
.map(|i| binds[i].take().unwrap())
.collect(),
})
.collect()
}
/// A Core identifier carries its independently checkable type.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Id {
pub name: crate::names::Id,
pub ty: Type,
}
use std::collections::BTreeSet;
impl Type {
pub fn apply(f: Self, a: Self) -> Self {
match f {
Self::Con(id, mut args) => {
args.push(a);
if id.name == "(->)" && args.len() == 2 {
Self::arrow(args.remove(0), args.remove(0))
} else {
Self::Con(id, args)
}
}
f => Self::App(Box::new(f), Box::new(a)),
}
}
pub fn arrow(a: Self, b: Self) -> Self {
Self::Arrow(Box::new(a), Box::new(b))
}
pub fn free(&self) -> BTreeSet<u32> {
match self {
Self::Var(v) => BTreeSet::from([*v]),
Self::Con(_, args) => {
args.iter().flat_map(Self::free).collect()
}
Self::Arrow(a, b) | Self::App(a, b) => {
let mut vars = a.free();
vars.extend(b.free());
vars
}
Self::Forall(v, b) => {
let mut vars = b.free();
vars.remove(v);
vars
}
_ => BTreeSet::new(),
}
}
fn largest(&self) -> u32 {
match self {
Self::Var(v) => *v,
Self::Con(_, args) => {
args.iter().map(Self::largest).max().unwrap_or(0)
}
Self::Arrow(a, b) | Self::App(a, b) => {
a.largest().max(b.largest())
}
Self::Forall(v, b) => (*v).max(b.largest()),
_ => 0,
}
}
/// Substitute without capturing a free variable of the replacement.
// ANCHOR: type-substitution
pub fn substitute(&self, variable: u32, replacement: &Type) -> Type {
match self {
Self::Var(v) if *v == variable => replacement.clone(),
Self::Con(id, args) => Self::Con(
id.clone(),
args.iter()
.map(|a| a.substitute(variable, replacement))
.collect(),
),
Self::App(a, b) => Self::apply(
a.substitute(variable, replacement),
b.substitute(variable, replacement),
),
Self::Arrow(a, b) => Self::arrow(
a.substitute(variable, replacement),
b.substitute(variable, replacement),
),
Self::Forall(v, _) if *v == variable => self.clone(),
Self::Forall(v, body) => {
let (v, body) = if replacement.free().contains(v) {
let fresh = self
.largest()
.max(replacement.largest())
.max(variable)
.checked_add(1)
.expect("type variable supply exhausted");
(fresh, body.substitute(*v, &Self::Var(fresh)))
} else {
(*v, *body.clone())
};
Self::Forall(
v,
Box::new(body.substitute(variable, replacement)),
)
}
_ => self.clone(),
}
}
// ANCHOR_END: type-substitution
/// Alpha equivalence compares bound identities by their scope, not spelling.
pub fn equivalent(&self, other: &Self) -> bool {
fn go(a: &Type, b: &Type, scope: &mut Vec<(u32, u32)>) -> bool {
match (a, b) {
(Type::Var(a), Type::Var(b)) => {
let left = scope.iter().rposition(|(v, _)| v == a);
let right = scope.iter().rposition(|(_, v)| v == b);
match (left, right) {
(Some(a), Some(b)) => a == b,
(None, None) => a == b,
_ => false,
}
}
(Type::Con(a, xs), Type::Con(b, ys)) => {
a == b
&& xs.len() == ys.len()
&& xs.iter().zip(ys).all(|(x, y)| go(x, y, scope))
}
(Type::Arrow(a, b), Type::Arrow(c, d))
| (Type::App(a, b), Type::App(c, d)) => {
go(a, c, scope) && go(b, d, scope)
}
(Type::Forall(a, b), Type::Forall(c, d)) => {
scope.push((*a, *c));
let same = go(b, d, scope);
scope.pop();
same
}
_ => a == b,
}
}
go(self, other, &mut Vec::new())
}
}
impl std::fmt::Display for Type {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Double => write!(f, "Double"),
Self::Int => write!(f, "Int"),
Self::Bool => write!(f, "Bool"),
Self::Char => write!(f, "Char"),
Self::String => write!(f, "String"),
Self::Var(v) => write!(f, "t{v}"),
Self::Con(id, args) => {
if id.name == "[]" && args.len() == 1 {
return write!(f, "[{}]", args[0]);
}
if matches!(id.name.as_str(), "(,)" | "(,,)")
&& args.len() == id.name.len() - 1
{
write!(f, "(")?;
for (i, t) in args.iter().enumerate() {
if i > 0 {
write!(f, ",")?;
}
write!(f, "{t}")?;
}
return write!(f, ")");
}
write!(f, "{}", id.name)?;
for t in args {
if matches!(t, Self::Arrow(..) | Self::Forall(..))
|| matches!(t,Self::Con(_,v) if !v.is_empty())
{
write!(f, " ({t})")?;
} else {
write!(f, " {t}")?;
}
}
Ok(())
}
Self::Forall(v, b) => write!(f, "forall t{v}. {b}"),
Self::App(a, b) => write!(f, "{a} ({b})"),
Self::Arrow(a, b) => {
if matches!(**a, Self::Arrow(..) | Self::Forall(..)) {
write!(f, "({a})")?;
} else {
write!(f, "{a}")?;
}
write!(f, " -> {b}")
}
}
}
}
/// A flat, alpha-normalized key protects imported ABIs when source is rechecked.
/// Both traversal and ownership use vectors, without recursively cloning types.
pub fn fingerprint(ty: &Type) -> Vec<String> {
enum Work<'a> {
Visit(&'a Type),
Leave,
}
let mut work = vec![Work::Visit(ty)];
let mut scope = vec![];
let mut key = vec![];
while let Some(item) = work.pop() {
let Work::Visit(ty) = item else {
scope.pop();
continue;
};
match ty {
Type::Var(n) => {
key.push(match scope.iter().rev().position(|v| v == n) {
Some(depth) => format!("bound:{depth}"),
None => format!("free:{n}"),
})
}
Type::Con(id, args) => {
key.push(format!("con:{}:{}", id.name, args.len()));
work.extend(args.iter().rev().map(Work::Visit));
}
Type::Arrow(a, b) | Type::App(a, b) => {
key.push(
if matches!(ty, Type::Arrow(..)) {
"arrow"
} else {
"app"
}
.into(),
);
work.push(Work::Visit(b));
work.push(Work::Visit(a));
}
Type::Forall(n, body) => {
key.push("forall".into());
scope.push(*n);
work.push(Work::Leave);
work.push(Work::Visit(body));
}
Type::Int => key.push("Int".into()),
Type::Double => key.push("Double".into()),
Type::Bool => key.push("Bool".into()),
Type::Char => key.push("Char".into()),
Type::String => key.push("String".into()),
}
}
key
}
/// Core type applications retain kinds in the program's binder table.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Type {
Double,
Int,
Bool,
Char,
String,
Var(u32),
Con(crate::data::TyConId, Vec<Type>),
App(Box<Type>, Box<Type>),
Arrow(Box<Type>, Box<Type>),
Forall(u32, Box<Type>),
}
pub use crate::core_type::Type;
use crate::{ast::Op, source::Span};
/// A Core identifier carries its independently checkable type.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Id {
pub name: crate::names::Id,
pub ty: Type,
}
impl std::fmt::Display for Id {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{} : {}", self.name, self.ty)
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
/// Immediate source values; strings are primitive UTF-8 values, not character lists.
pub enum Lit {
Double(u64),
Int(i64),
Char(char),
String(String),
}
/// Flat alternatives inspect one constructor or literal, never nested patterns.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum AltCon {
Con(crate::data::ConId),
Lit(Lit),
Default,
}
/// Constructor slots become typed binders scoped over the alternative body.
#[derive(Clone, Debug)]
pub struct Alt {
pub con: AltCon,
pub binders: Vec<Id>,
pub rhs: Expr,
}
#[derive(Clone, Debug)]
/// A recursive binding is guaranteed to have a lambda right-hand side.
pub struct Bind {
pub name: Id,
pub rhs: Box<Expr>,
}
#[derive(Clone, Debug)]
/// An ordered component; recursive members are in scope in every right-hand side.
pub struct BindGroup {
pub recursive: bool,
pub binds: Vec<Bind>,
}
#[derive(Clone, Debug)]
/// Globals are initialized in dependency order, with explicit recursive components.
pub struct Program {
pub groups: Vec<BindGroup>,
/// Flat type fingerprints survive erasure for cross-module ABI checks.
pub global_types:
std::collections::BTreeMap<crate::names::Id, Vec<String>>,
pub main: Id,
pub data_types: Vec<(crate::data::TyConId, crate::kinds::Kind)>,
pub type_kinds: std::collections::BTreeMap<u32, crate::kinds::Kind>,
pub constructors: Vec<ConDecl>,
pub locations: Vec<(Span, String)>,
}
impl std::fmt::Display for Expr {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Case(scrut, binder, ty, alts) => {
write!(f, "(case {scrut} as {binder} -> {ty}")?;
for alt in alts {
write!(f, " [ {:?}", alt.con)?;
for id in &alt.binders {
write!(f, " {id}")?;
}
write!(f, " -> {} ]", alt.rhs)?;
}
write!(f, ")")
}
Self::Join(id, params, body, rest) => {
write!(f, "(join {id} (")?;
for p in params {
write!(f, " {p}")?;
}
write!(f, ") = {body} in {rest})")
}
Self::Jump(id, args, ty) => {
write!(f, "(jump {id} : {ty}")?;
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
Self::Var(n) => write!(f, "{}", n.name),
Self::Global(n) => write!(f, "@{}", n.name),
Self::TyLam(v, b) => write!(f, "(type-lambda t{v} {b})"),
Self::TyApp(a, t) => write!(f, "(type-app {a} {t})"),
Self::Lit(l) => write!(f, "{l}"),
Self::Lam(n, b) => write!(f, "(lambda {n} {b})"),
Self::App(a, b) => write!(f, "(app {a} {b})"),
Self::Let(group, body) => write!(f, "(let {group} in {body})"),
Self::Con(id, types, args) => {
write!(f, "(con {}", id.name)?;
for t in types {
write!(f, " [{t}]")?;
}
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
Self::Match(m) => {
write!(f, "(match")?;
for s in &m.scruts {
write!(f, " {}", s.name)?;
}
for row in &m.rows {
write!(f, " {row}")?;
}
write!(f, ")")
}
Self::PatternFail(_, ty) => write!(f, "(pattern-fail : {ty})"),
Self::Prim(op, _, args, _) => {
write!(f, "(prim {}", op.text())?;
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
}
}
}
impl std::fmt::Display for Lit {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Double(bits) => write!(
f,
"{}",
crate::primitives::show_double(f64::from_bits(*bits))
),
Self::Int(n) => write!(f, "{n}"),
Self::Char(c) => {
write!(f, "{}", crate::ast::quote(&c.to_string(), '\''))
}
Self::String(s) => write!(f, "{}", crate::ast::quote(s, '"')),
}
}
}
impl std::fmt::Display for BindGroup {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{} {{", if self.recursive { "rec" } else { "nonrec" })?;
for b in &self.binds {
write!(f, " {} = {};", b.name, b.rhs)?;
}
write!(f, " }}")
}
}
/// Independently typecheck System F Core after each Core-producing pass.
pub fn lint(program: &Program) -> Result<(), String> {
crate::core_lint::lint(program)
}
impl Id {
pub fn unique(&self) -> u32 {
self.name.name.unique
}
}
/// Constructor typing is immutable and contains no inference metavariables.
#[derive(Clone, Debug)]
pub struct ConDecl {
pub labels: Option<Vec<String>>,
pub id: crate::data::ConId,
pub tag: u32,
pub parameters: Vec<u32>,
pub fields: Vec<Type>,
pub result: Type,
}
/// Nested patterns remain until the decision-tree compiler in Chapter 16.
#[derive(Clone, Debug)]
pub enum Pat {
Var(Id),
Wild,
As(Id, Box<Pat>),
Con(crate::data::ConId, Vec<Pat>),
Lit(Lit),
}
/// A guarded row falls through when all its Boolean tests fail.
#[derive(Clone, Debug)]
pub enum RowBody {
Plain(Box<Expr>),
Guarded(Vec<(Expr, Expr)>),
}
/// Row-local declarations run after patterns match and are shared by the guards.
#[derive(Clone, Debug)]
pub struct Row {
pub pats: Vec<Pat>,
pub locals: Vec<BindGroup>,
pub body: RowBody,
pub span: Span,
}
/// Scrutinees name strict preceding lets; the match records its result type and failure site.
#[derive(Clone, Debug)]
pub struct Match {
pub scruts: Vec<Id>,
pub rows: Vec<Row>,
pub result: Type,
pub span: Span,
}
impl std::fmt::Display for Pat {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Var(id) => write!(f, "{}", id.name),
Self::Wild => write!(f, "_"),
Self::As(id, p) => write!(f, "{}@{p}", id.name),
Self::Lit(l) => write!(f, "{l}"),
Self::Con(id, ps) => {
write!(f, "({}", id.name)?;
for p in ps {
write!(f, " {p}")?;
}
write!(f, ")")
}
}
}
}
impl std::fmt::Display for Row {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "[ ")?;
for p in &self.pats {
write!(f, "{p} ")?;
}
for local in &self.locals {
write!(f, "{local} ")?;
}
match &self.body {
RowBody::Plain(e) => write!(f, "-> {e}")?,
RowBody::Guarded(gs) => {
for (g, e) in gs {
write!(f, "| {g} -> {e} ")?;
}
}
}
write!(f, " ]")
}
}
/// Type abstractions erase; a constrained value is an ordinary dictionary function.
pub fn is_function(mut e: &Expr) -> bool {
while let Expr::TyLam(_, body) = e {
e = body;
}
matches!(e, Expr::Lam(..))
}
/// Dictionary calls introduce global dependencies absent from the source graph.
pub fn order(groups: Vec<BindGroup>) -> Vec<BindGroup> {
fn refs(e: &Expr, out: &mut std::collections::BTreeSet<u32>) {
match e {
Expr::Case(s, _, _, alts) => {
refs(s, out);
for a in alts {
refs(&a.rhs, out)
}
}
Expr::Join(_, _, b, r) => {
refs(b, out);
refs(r, out)
}
Expr::Jump(_, args, _) => {
for a in args {
refs(a, out)
}
}
Expr::Global(id) => {
out.insert(id.unique());
}
Expr::Lam(_, b) | Expr::TyLam(_, b) | Expr::TyApp(b, _) => {
refs(b, out)
}
Expr::App(a, b) => {
refs(a, out);
refs(b, out);
}
Expr::Let(g, b) => {
for bind in &g.binds {
refs(&bind.rhs, out);
}
refs(b, out);
}
Expr::Con(_, _, args) | Expr::Prim(_, _, args, _) => {
for a in args {
refs(a, out);
}
}
Expr::Match(m) => {
for row in &m.rows {
for g in &row.locals {
for b in &g.binds {
refs(&b.rhs, out);
}
}
match &row.body {
RowBody::Plain(e) => refs(e, out),
RowBody::Guarded(gs) => {
for (g, e) in gs {
refs(g, out);
refs(e, out);
}
}
}
}
}
_ => {}
}
}
let binds =
groups.into_iter().flat_map(|g| g.binds).collect::<Vec<_>>();
let indices = binds
.iter()
.enumerate()
.map(|(i, b)| (b.name.unique(), i))
.collect::<std::collections::BTreeMap<_, _>>();
let edges = binds
.iter()
.map(|b| {
let mut names = std::collections::BTreeSet::new();
refs(&b.rhs, &mut names);
names
.into_iter()
.filter_map(|n| indices.get(&n).copied())
.collect::<Vec<_>>()
})
.collect::<Vec<_>>();
let mut binds = binds.into_iter().map(Some).collect::<Vec<_>>();
crate::scc::components(&edges)
.into_iter()
.map(|xs| BindGroup {
recursive: (xs.len() > 1 || edges[xs[0]].contains(&xs[0]))
&& xs
.iter()
.all(|i| is_function(&binds[*i].as_ref().unwrap().rhs)),
binds: xs
.into_iter()
.map(|i| binds[i].take().unwrap())
.collect(),
})
.collect()
}
#[derive(Clone, Debug)]
/// System F Core makes type abstraction and instantiation explicit.
pub enum Expr {
Var(Id),
Global(Id),
TyLam(u32, Box<Expr>),
TyApp(Box<Expr>, Type),
Lit(Lit),
Lam(Id, Box<Expr>),
App(Box<Expr>, Box<Expr>),
Let(BindGroup, Box<Expr>),
Con(crate::data::ConId, Vec<Type>, Vec<Expr>),
Match(Match),
Case(Box<Expr>, Id, Type, Vec<Alt>),
Join(crate::names::Id, Vec<Id>, Box<Expr>, Box<Expr>),
Jump(crate::names::Id, Vec<Expr>, Type),
PatternFail(Span, Type),
Prim(Op, Vec<Type>, Vec<Expr>, Span),
}
}Match belongs to elaborated Core. Match compilation removes it, leaving flat
Case alternatives and lexical Join/Jump. Constructors and primitives are
saturated. A jump is fully applied and appears only in tail position within the
scope of its join. The lint pass checks these properties independently of the
source type checker.
#![allow(unused)]
fn main() {
pub use crate::core_type::Type;
use crate::{ast::Op, source::Span};
/// A Core identifier carries its independently checkable type.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Id {
pub name: crate::names::Id,
pub ty: Type,
}
impl std::fmt::Display for Id {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{} : {}", self.name, self.ty)
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
/// Immediate source values; strings are primitive UTF-8 values, not character lists.
pub enum Lit {
Double(u64),
Int(i64),
Char(char),
String(String),
}
#[derive(Clone, Debug)]
/// System F Core makes type abstraction and instantiation explicit.
pub enum Expr {
Var(Id),
Global(Id),
TyLam(u32, Box<Expr>),
TyApp(Box<Expr>, Type),
Lit(Lit),
Lam(Id, Box<Expr>),
App(Box<Expr>, Box<Expr>),
Let(BindGroup, Box<Expr>),
Con(crate::data::ConId, Vec<Type>, Vec<Expr>),
Match(Match),
Case(Box<Expr>, Id, Type, Vec<Alt>),
Join(crate::names::Id, Vec<Id>, Box<Expr>, Box<Expr>),
Jump(crate::names::Id, Vec<Expr>, Type),
PatternFail(Span, Type),
Prim(Op, Vec<Type>, Vec<Expr>, Span),
}
/// Constructor slots become typed binders scoped over the alternative body.
#[derive(Clone, Debug)]
pub struct Alt {
pub con: AltCon,
pub binders: Vec<Id>,
pub rhs: Expr,
}
#[derive(Clone, Debug)]
/// A recursive binding is guaranteed to have a lambda right-hand side.
pub struct Bind {
pub name: Id,
pub rhs: Box<Expr>,
}
#[derive(Clone, Debug)]
/// An ordered component; recursive members are in scope in every right-hand side.
pub struct BindGroup {
pub recursive: bool,
pub binds: Vec<Bind>,
}
#[derive(Clone, Debug)]
/// Globals are initialized in dependency order, with explicit recursive components.
pub struct Program {
pub groups: Vec<BindGroup>,
/// Flat type fingerprints survive erasure for cross-module ABI checks.
pub global_types:
std::collections::BTreeMap<crate::names::Id, Vec<String>>,
pub main: Id,
pub data_types: Vec<(crate::data::TyConId, crate::kinds::Kind)>,
pub type_kinds: std::collections::BTreeMap<u32, crate::kinds::Kind>,
pub constructors: Vec<ConDecl>,
pub locations: Vec<(Span, String)>,
}
impl std::fmt::Display for Expr {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Case(scrut, binder, ty, alts) => {
write!(f, "(case {scrut} as {binder} -> {ty}")?;
for alt in alts {
write!(f, " [ {:?}", alt.con)?;
for id in &alt.binders {
write!(f, " {id}")?;
}
write!(f, " -> {} ]", alt.rhs)?;
}
write!(f, ")")
}
Self::Join(id, params, body, rest) => {
write!(f, "(join {id} (")?;
for p in params {
write!(f, " {p}")?;
}
write!(f, ") = {body} in {rest})")
}
Self::Jump(id, args, ty) => {
write!(f, "(jump {id} : {ty}")?;
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
Self::Var(n) => write!(f, "{}", n.name),
Self::Global(n) => write!(f, "@{}", n.name),
Self::TyLam(v, b) => write!(f, "(type-lambda t{v} {b})"),
Self::TyApp(a, t) => write!(f, "(type-app {a} {t})"),
Self::Lit(l) => write!(f, "{l}"),
Self::Lam(n, b) => write!(f, "(lambda {n} {b})"),
Self::App(a, b) => write!(f, "(app {a} {b})"),
Self::Let(group, body) => write!(f, "(let {group} in {body})"),
Self::Con(id, types, args) => {
write!(f, "(con {}", id.name)?;
for t in types {
write!(f, " [{t}]")?;
}
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
Self::Match(m) => {
write!(f, "(match")?;
for s in &m.scruts {
write!(f, " {}", s.name)?;
}
for row in &m.rows {
write!(f, " {row}")?;
}
write!(f, ")")
}
Self::PatternFail(_, ty) => write!(f, "(pattern-fail : {ty})"),
Self::Prim(op, _, args, _) => {
write!(f, "(prim {}", op.text())?;
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
}
}
}
impl std::fmt::Display for Lit {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Double(bits) => write!(
f,
"{}",
crate::primitives::show_double(f64::from_bits(*bits))
),
Self::Int(n) => write!(f, "{n}"),
Self::Char(c) => {
write!(f, "{}", crate::ast::quote(&c.to_string(), '\''))
}
Self::String(s) => write!(f, "{}", crate::ast::quote(s, '"')),
}
}
}
impl std::fmt::Display for BindGroup {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{} {{", if self.recursive { "rec" } else { "nonrec" })?;
for b in &self.binds {
write!(f, " {} = {};", b.name, b.rhs)?;
}
write!(f, " }}")
}
}
/// Independently typecheck System F Core after each Core-producing pass.
pub fn lint(program: &Program) -> Result<(), String> {
crate::core_lint::lint(program)
}
impl Id {
pub fn unique(&self) -> u32 {
self.name.name.unique
}
}
/// Constructor typing is immutable and contains no inference metavariables.
#[derive(Clone, Debug)]
pub struct ConDecl {
pub labels: Option<Vec<String>>,
pub id: crate::data::ConId,
pub tag: u32,
pub parameters: Vec<u32>,
pub fields: Vec<Type>,
pub result: Type,
}
/// Nested patterns remain until the decision-tree compiler in Chapter 16.
#[derive(Clone, Debug)]
pub enum Pat {
Var(Id),
Wild,
As(Id, Box<Pat>),
Con(crate::data::ConId, Vec<Pat>),
Lit(Lit),
}
/// A guarded row falls through when all its Boolean tests fail.
#[derive(Clone, Debug)]
pub enum RowBody {
Plain(Box<Expr>),
Guarded(Vec<(Expr, Expr)>),
}
/// Row-local declarations run after patterns match and are shared by the guards.
#[derive(Clone, Debug)]
pub struct Row {
pub pats: Vec<Pat>,
pub locals: Vec<BindGroup>,
pub body: RowBody,
pub span: Span,
}
/// Scrutinees name strict preceding lets; the match records its result type and failure site.
#[derive(Clone, Debug)]
pub struct Match {
pub scruts: Vec<Id>,
pub rows: Vec<Row>,
pub result: Type,
pub span: Span,
}
impl std::fmt::Display for Pat {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Var(id) => write!(f, "{}", id.name),
Self::Wild => write!(f, "_"),
Self::As(id, p) => write!(f, "{}@{p}", id.name),
Self::Lit(l) => write!(f, "{l}"),
Self::Con(id, ps) => {
write!(f, "({}", id.name)?;
for p in ps {
write!(f, " {p}")?;
}
write!(f, ")")
}
}
}
}
impl std::fmt::Display for Row {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "[ ")?;
for p in &self.pats {
write!(f, "{p} ")?;
}
for local in &self.locals {
write!(f, "{local} ")?;
}
match &self.body {
RowBody::Plain(e) => write!(f, "-> {e}")?,
RowBody::Guarded(gs) => {
for (g, e) in gs {
write!(f, "| {g} -> {e} ")?;
}
}
}
write!(f, " ]")
}
}
/// Type abstractions erase; a constrained value is an ordinary dictionary function.
pub fn is_function(mut e: &Expr) -> bool {
while let Expr::TyLam(_, body) = e {
e = body;
}
matches!(e, Expr::Lam(..))
}
/// Dictionary calls introduce global dependencies absent from the source graph.
pub fn order(groups: Vec<BindGroup>) -> Vec<BindGroup> {
fn refs(e: &Expr, out: &mut std::collections::BTreeSet<u32>) {
match e {
Expr::Case(s, _, _, alts) => {
refs(s, out);
for a in alts {
refs(&a.rhs, out)
}
}
Expr::Join(_, _, b, r) => {
refs(b, out);
refs(r, out)
}
Expr::Jump(_, args, _) => {
for a in args {
refs(a, out)
}
}
Expr::Global(id) => {
out.insert(id.unique());
}
Expr::Lam(_, b) | Expr::TyLam(_, b) | Expr::TyApp(b, _) => {
refs(b, out)
}
Expr::App(a, b) => {
refs(a, out);
refs(b, out);
}
Expr::Let(g, b) => {
for bind in &g.binds {
refs(&bind.rhs, out);
}
refs(b, out);
}
Expr::Con(_, _, args) | Expr::Prim(_, _, args, _) => {
for a in args {
refs(a, out);
}
}
Expr::Match(m) => {
for row in &m.rows {
for g in &row.locals {
for b in &g.binds {
refs(&b.rhs, out);
}
}
match &row.body {
RowBody::Plain(e) => refs(e, out),
RowBody::Guarded(gs) => {
for (g, e) in gs {
refs(g, out);
refs(e, out);
}
}
}
}
}
_ => {}
}
}
let binds =
groups.into_iter().flat_map(|g| g.binds).collect::<Vec<_>>();
let indices = binds
.iter()
.enumerate()
.map(|(i, b)| (b.name.unique(), i))
.collect::<std::collections::BTreeMap<_, _>>();
let edges = binds
.iter()
.map(|b| {
let mut names = std::collections::BTreeSet::new();
refs(&b.rhs, &mut names);
names
.into_iter()
.filter_map(|n| indices.get(&n).copied())
.collect::<Vec<_>>()
})
.collect::<Vec<_>>();
let mut binds = binds.into_iter().map(Some).collect::<Vec<_>>();
crate::scc::components(&edges)
.into_iter()
.map(|xs| BindGroup {
recursive: (xs.len() > 1 || edges[xs[0]].contains(&xs[0]))
&& xs
.iter()
.all(|i| is_function(&binds[*i].as_ref().unwrap().rhs)),
binds: xs
.into_iter()
.map(|i| binds[i].take().unwrap())
.collect(),
})
.collect()
}
/// Flat alternatives inspect one constructor or literal, never nested patterns.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum AltCon {
Con(crate::data::ConId),
Lit(Lit),
Default,
}
pub use crate::core_type::Type;
use crate::{ast::Op, source::Span};
/// A Core identifier carries its independently checkable type.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Id {
pub name: crate::names::Id,
pub ty: Type,
}
impl std::fmt::Display for Id {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{} : {}", self.name, self.ty)
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
/// Immediate source values; strings are primitive UTF-8 values, not character lists.
pub enum Lit {
Double(u64),
Int(i64),
Char(char),
String(String),
}
#[derive(Clone, Debug)]
/// System F Core makes type abstraction and instantiation explicit.
pub enum Expr {
Var(Id),
Global(Id),
TyLam(u32, Box<Expr>),
TyApp(Box<Expr>, Type),
Lit(Lit),
Lam(Id, Box<Expr>),
App(Box<Expr>, Box<Expr>),
Let(BindGroup, Box<Expr>),
Con(crate::data::ConId, Vec<Type>, Vec<Expr>),
Match(Match),
Case(Box<Expr>, Id, Type, Vec<Alt>),
Join(crate::names::Id, Vec<Id>, Box<Expr>, Box<Expr>),
Jump(crate::names::Id, Vec<Expr>, Type),
PatternFail(Span, Type),
Prim(Op, Vec<Type>, Vec<Expr>, Span),
}
/// Flat alternatives inspect one constructor or literal, never nested patterns.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum AltCon {
Con(crate::data::ConId),
Lit(Lit),
Default,
}
#[derive(Clone, Debug)]
/// A recursive binding is guaranteed to have a lambda right-hand side.
pub struct Bind {
pub name: Id,
pub rhs: Box<Expr>,
}
#[derive(Clone, Debug)]
/// An ordered component; recursive members are in scope in every right-hand side.
pub struct BindGroup {
pub recursive: bool,
pub binds: Vec<Bind>,
}
#[derive(Clone, Debug)]
/// Globals are initialized in dependency order, with explicit recursive components.
pub struct Program {
pub groups: Vec<BindGroup>,
/// Flat type fingerprints survive erasure for cross-module ABI checks.
pub global_types:
std::collections::BTreeMap<crate::names::Id, Vec<String>>,
pub main: Id,
pub data_types: Vec<(crate::data::TyConId, crate::kinds::Kind)>,
pub type_kinds: std::collections::BTreeMap<u32, crate::kinds::Kind>,
pub constructors: Vec<ConDecl>,
pub locations: Vec<(Span, String)>,
}
impl std::fmt::Display for Expr {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Case(scrut, binder, ty, alts) => {
write!(f, "(case {scrut} as {binder} -> {ty}")?;
for alt in alts {
write!(f, " [ {:?}", alt.con)?;
for id in &alt.binders {
write!(f, " {id}")?;
}
write!(f, " -> {} ]", alt.rhs)?;
}
write!(f, ")")
}
Self::Join(id, params, body, rest) => {
write!(f, "(join {id} (")?;
for p in params {
write!(f, " {p}")?;
}
write!(f, ") = {body} in {rest})")
}
Self::Jump(id, args, ty) => {
write!(f, "(jump {id} : {ty}")?;
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
Self::Var(n) => write!(f, "{}", n.name),
Self::Global(n) => write!(f, "@{}", n.name),
Self::TyLam(v, b) => write!(f, "(type-lambda t{v} {b})"),
Self::TyApp(a, t) => write!(f, "(type-app {a} {t})"),
Self::Lit(l) => write!(f, "{l}"),
Self::Lam(n, b) => write!(f, "(lambda {n} {b})"),
Self::App(a, b) => write!(f, "(app {a} {b})"),
Self::Let(group, body) => write!(f, "(let {group} in {body})"),
Self::Con(id, types, args) => {
write!(f, "(con {}", id.name)?;
for t in types {
write!(f, " [{t}]")?;
}
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
Self::Match(m) => {
write!(f, "(match")?;
for s in &m.scruts {
write!(f, " {}", s.name)?;
}
for row in &m.rows {
write!(f, " {row}")?;
}
write!(f, ")")
}
Self::PatternFail(_, ty) => write!(f, "(pattern-fail : {ty})"),
Self::Prim(op, _, args, _) => {
write!(f, "(prim {}", op.text())?;
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
}
}
}
impl std::fmt::Display for Lit {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Double(bits) => write!(
f,
"{}",
crate::primitives::show_double(f64::from_bits(*bits))
),
Self::Int(n) => write!(f, "{n}"),
Self::Char(c) => {
write!(f, "{}", crate::ast::quote(&c.to_string(), '\''))
}
Self::String(s) => write!(f, "{}", crate::ast::quote(s, '"')),
}
}
}
impl std::fmt::Display for BindGroup {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{} {{", if self.recursive { "rec" } else { "nonrec" })?;
for b in &self.binds {
write!(f, " {} = {};", b.name, b.rhs)?;
}
write!(f, " }}")
}
}
/// Independently typecheck System F Core after each Core-producing pass.
pub fn lint(program: &Program) -> Result<(), String> {
crate::core_lint::lint(program)
}
impl Id {
pub fn unique(&self) -> u32 {
self.name.name.unique
}
}
/// Constructor typing is immutable and contains no inference metavariables.
#[derive(Clone, Debug)]
pub struct ConDecl {
pub labels: Option<Vec<String>>,
pub id: crate::data::ConId,
pub tag: u32,
pub parameters: Vec<u32>,
pub fields: Vec<Type>,
pub result: Type,
}
/// Nested patterns remain until the decision-tree compiler in Chapter 16.
#[derive(Clone, Debug)]
pub enum Pat {
Var(Id),
Wild,
As(Id, Box<Pat>),
Con(crate::data::ConId, Vec<Pat>),
Lit(Lit),
}
/// A guarded row falls through when all its Boolean tests fail.
#[derive(Clone, Debug)]
pub enum RowBody {
Plain(Box<Expr>),
Guarded(Vec<(Expr, Expr)>),
}
/// Row-local declarations run after patterns match and are shared by the guards.
#[derive(Clone, Debug)]
pub struct Row {
pub pats: Vec<Pat>,
pub locals: Vec<BindGroup>,
pub body: RowBody,
pub span: Span,
}
/// Scrutinees name strict preceding lets; the match records its result type and failure site.
#[derive(Clone, Debug)]
pub struct Match {
pub scruts: Vec<Id>,
pub rows: Vec<Row>,
pub result: Type,
pub span: Span,
}
impl std::fmt::Display for Pat {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Var(id) => write!(f, "{}", id.name),
Self::Wild => write!(f, "_"),
Self::As(id, p) => write!(f, "{}@{p}", id.name),
Self::Lit(l) => write!(f, "{l}"),
Self::Con(id, ps) => {
write!(f, "({}", id.name)?;
for p in ps {
write!(f, " {p}")?;
}
write!(f, ")")
}
}
}
}
impl std::fmt::Display for Row {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "[ ")?;
for p in &self.pats {
write!(f, "{p} ")?;
}
for local in &self.locals {
write!(f, "{local} ")?;
}
match &self.body {
RowBody::Plain(e) => write!(f, "-> {e}")?,
RowBody::Guarded(gs) => {
for (g, e) in gs {
write!(f, "| {g} -> {e} ")?;
}
}
}
write!(f, " ]")
}
}
/// Type abstractions erase; a constrained value is an ordinary dictionary function.
pub fn is_function(mut e: &Expr) -> bool {
while let Expr::TyLam(_, body) = e {
e = body;
}
matches!(e, Expr::Lam(..))
}
/// Dictionary calls introduce global dependencies absent from the source graph.
pub fn order(groups: Vec<BindGroup>) -> Vec<BindGroup> {
fn refs(e: &Expr, out: &mut std::collections::BTreeSet<u32>) {
match e {
Expr::Case(s, _, _, alts) => {
refs(s, out);
for a in alts {
refs(&a.rhs, out)
}
}
Expr::Join(_, _, b, r) => {
refs(b, out);
refs(r, out)
}
Expr::Jump(_, args, _) => {
for a in args {
refs(a, out)
}
}
Expr::Global(id) => {
out.insert(id.unique());
}
Expr::Lam(_, b) | Expr::TyLam(_, b) | Expr::TyApp(b, _) => {
refs(b, out)
}
Expr::App(a, b) => {
refs(a, out);
refs(b, out);
}
Expr::Let(g, b) => {
for bind in &g.binds {
refs(&bind.rhs, out);
}
refs(b, out);
}
Expr::Con(_, _, args) | Expr::Prim(_, _, args, _) => {
for a in args {
refs(a, out);
}
}
Expr::Match(m) => {
for row in &m.rows {
for g in &row.locals {
for b in &g.binds {
refs(&b.rhs, out);
}
}
match &row.body {
RowBody::Plain(e) => refs(e, out),
RowBody::Guarded(gs) => {
for (g, e) in gs {
refs(g, out);
refs(e, out);
}
}
}
}
}
_ => {}
}
}
let binds =
groups.into_iter().flat_map(|g| g.binds).collect::<Vec<_>>();
let indices = binds
.iter()
.enumerate()
.map(|(i, b)| (b.name.unique(), i))
.collect::<std::collections::BTreeMap<_, _>>();
let edges = binds
.iter()
.map(|b| {
let mut names = std::collections::BTreeSet::new();
refs(&b.rhs, &mut names);
names
.into_iter()
.filter_map(|n| indices.get(&n).copied())
.collect::<Vec<_>>()
})
.collect::<Vec<_>>();
let mut binds = binds.into_iter().map(Some).collect::<Vec<_>>();
crate::scc::components(&edges)
.into_iter()
.map(|xs| BindGroup {
recursive: (xs.len() > 1 || edges[xs[0]].contains(&xs[0]))
&& xs
.iter()
.all(|i| is_function(&binds[*i].as_ref().unwrap().rhs)),
binds: xs
.into_iter()
.map(|i| binds[i].take().unwrap())
.collect(),
})
.collect()
}
/// Constructor slots become typed binders scoped over the alternative body.
#[derive(Clone, Debug)]
pub struct Alt {
pub con: AltCon,
pub binders: Vec<Id>,
pub rhs: Expr,
}
pub use crate::core_type::Type;
use crate::{ast::Op, source::Span};
/// A Core identifier carries its independently checkable type.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Id {
pub name: crate::names::Id,
pub ty: Type,
}
impl std::fmt::Display for Id {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{} : {}", self.name, self.ty)
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
/// Immediate source values; strings are primitive UTF-8 values, not character lists.
pub enum Lit {
Double(u64),
Int(i64),
Char(char),
String(String),
}
#[derive(Clone, Debug)]
/// System F Core makes type abstraction and instantiation explicit.
pub enum Expr {
Var(Id),
Global(Id),
TyLam(u32, Box<Expr>),
TyApp(Box<Expr>, Type),
Lit(Lit),
Lam(Id, Box<Expr>),
App(Box<Expr>, Box<Expr>),
Let(BindGroup, Box<Expr>),
Con(crate::data::ConId, Vec<Type>, Vec<Expr>),
Match(Match),
Case(Box<Expr>, Id, Type, Vec<Alt>),
Join(crate::names::Id, Vec<Id>, Box<Expr>, Box<Expr>),
Jump(crate::names::Id, Vec<Expr>, Type),
PatternFail(Span, Type),
Prim(Op, Vec<Type>, Vec<Expr>, Span),
}
/// Flat alternatives inspect one constructor or literal, never nested patterns.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum AltCon {
Con(crate::data::ConId),
Lit(Lit),
Default,
}
/// Constructor slots become typed binders scoped over the alternative body.
#[derive(Clone, Debug)]
pub struct Alt {
pub con: AltCon,
pub binders: Vec<Id>,
pub rhs: Expr,
}
#[derive(Clone, Debug)]
/// An ordered component; recursive members are in scope in every right-hand side.
pub struct BindGroup {
pub recursive: bool,
pub binds: Vec<Bind>,
}
#[derive(Clone, Debug)]
/// Globals are initialized in dependency order, with explicit recursive components.
pub struct Program {
pub groups: Vec<BindGroup>,
/// Flat type fingerprints survive erasure for cross-module ABI checks.
pub global_types:
std::collections::BTreeMap<crate::names::Id, Vec<String>>,
pub main: Id,
pub data_types: Vec<(crate::data::TyConId, crate::kinds::Kind)>,
pub type_kinds: std::collections::BTreeMap<u32, crate::kinds::Kind>,
pub constructors: Vec<ConDecl>,
pub locations: Vec<(Span, String)>,
}
impl std::fmt::Display for Expr {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Case(scrut, binder, ty, alts) => {
write!(f, "(case {scrut} as {binder} -> {ty}")?;
for alt in alts {
write!(f, " [ {:?}", alt.con)?;
for id in &alt.binders {
write!(f, " {id}")?;
}
write!(f, " -> {} ]", alt.rhs)?;
}
write!(f, ")")
}
Self::Join(id, params, body, rest) => {
write!(f, "(join {id} (")?;
for p in params {
write!(f, " {p}")?;
}
write!(f, ") = {body} in {rest})")
}
Self::Jump(id, args, ty) => {
write!(f, "(jump {id} : {ty}")?;
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
Self::Var(n) => write!(f, "{}", n.name),
Self::Global(n) => write!(f, "@{}", n.name),
Self::TyLam(v, b) => write!(f, "(type-lambda t{v} {b})"),
Self::TyApp(a, t) => write!(f, "(type-app {a} {t})"),
Self::Lit(l) => write!(f, "{l}"),
Self::Lam(n, b) => write!(f, "(lambda {n} {b})"),
Self::App(a, b) => write!(f, "(app {a} {b})"),
Self::Let(group, body) => write!(f, "(let {group} in {body})"),
Self::Con(id, types, args) => {
write!(f, "(con {}", id.name)?;
for t in types {
write!(f, " [{t}]")?;
}
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
Self::Match(m) => {
write!(f, "(match")?;
for s in &m.scruts {
write!(f, " {}", s.name)?;
}
for row in &m.rows {
write!(f, " {row}")?;
}
write!(f, ")")
}
Self::PatternFail(_, ty) => write!(f, "(pattern-fail : {ty})"),
Self::Prim(op, _, args, _) => {
write!(f, "(prim {}", op.text())?;
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
}
}
}
impl std::fmt::Display for Lit {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Double(bits) => write!(
f,
"{}",
crate::primitives::show_double(f64::from_bits(*bits))
),
Self::Int(n) => write!(f, "{n}"),
Self::Char(c) => {
write!(f, "{}", crate::ast::quote(&c.to_string(), '\''))
}
Self::String(s) => write!(f, "{}", crate::ast::quote(s, '"')),
}
}
}
impl std::fmt::Display for BindGroup {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{} {{", if self.recursive { "rec" } else { "nonrec" })?;
for b in &self.binds {
write!(f, " {} = {};", b.name, b.rhs)?;
}
write!(f, " }}")
}
}
/// Independently typecheck System F Core after each Core-producing pass.
pub fn lint(program: &Program) -> Result<(), String> {
crate::core_lint::lint(program)
}
impl Id {
pub fn unique(&self) -> u32 {
self.name.name.unique
}
}
/// Constructor typing is immutable and contains no inference metavariables.
#[derive(Clone, Debug)]
pub struct ConDecl {
pub labels: Option<Vec<String>>,
pub id: crate::data::ConId,
pub tag: u32,
pub parameters: Vec<u32>,
pub fields: Vec<Type>,
pub result: Type,
}
/// Nested patterns remain until the decision-tree compiler in Chapter 16.
#[derive(Clone, Debug)]
pub enum Pat {
Var(Id),
Wild,
As(Id, Box<Pat>),
Con(crate::data::ConId, Vec<Pat>),
Lit(Lit),
}
/// A guarded row falls through when all its Boolean tests fail.
#[derive(Clone, Debug)]
pub enum RowBody {
Plain(Box<Expr>),
Guarded(Vec<(Expr, Expr)>),
}
/// Row-local declarations run after patterns match and are shared by the guards.
#[derive(Clone, Debug)]
pub struct Row {
pub pats: Vec<Pat>,
pub locals: Vec<BindGroup>,
pub body: RowBody,
pub span: Span,
}
/// Scrutinees name strict preceding lets; the match records its result type and failure site.
#[derive(Clone, Debug)]
pub struct Match {
pub scruts: Vec<Id>,
pub rows: Vec<Row>,
pub result: Type,
pub span: Span,
}
impl std::fmt::Display for Pat {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Var(id) => write!(f, "{}", id.name),
Self::Wild => write!(f, "_"),
Self::As(id, p) => write!(f, "{}@{p}", id.name),
Self::Lit(l) => write!(f, "{l}"),
Self::Con(id, ps) => {
write!(f, "({}", id.name)?;
for p in ps {
write!(f, " {p}")?;
}
write!(f, ")")
}
}
}
}
impl std::fmt::Display for Row {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "[ ")?;
for p in &self.pats {
write!(f, "{p} ")?;
}
for local in &self.locals {
write!(f, "{local} ")?;
}
match &self.body {
RowBody::Plain(e) => write!(f, "-> {e}")?,
RowBody::Guarded(gs) => {
for (g, e) in gs {
write!(f, "| {g} -> {e} ")?;
}
}
}
write!(f, " ]")
}
}
/// Type abstractions erase; a constrained value is an ordinary dictionary function.
pub fn is_function(mut e: &Expr) -> bool {
while let Expr::TyLam(_, body) = e {
e = body;
}
matches!(e, Expr::Lam(..))
}
/// Dictionary calls introduce global dependencies absent from the source graph.
pub fn order(groups: Vec<BindGroup>) -> Vec<BindGroup> {
fn refs(e: &Expr, out: &mut std::collections::BTreeSet<u32>) {
match e {
Expr::Case(s, _, _, alts) => {
refs(s, out);
for a in alts {
refs(&a.rhs, out)
}
}
Expr::Join(_, _, b, r) => {
refs(b, out);
refs(r, out)
}
Expr::Jump(_, args, _) => {
for a in args {
refs(a, out)
}
}
Expr::Global(id) => {
out.insert(id.unique());
}
Expr::Lam(_, b) | Expr::TyLam(_, b) | Expr::TyApp(b, _) => {
refs(b, out)
}
Expr::App(a, b) => {
refs(a, out);
refs(b, out);
}
Expr::Let(g, b) => {
for bind in &g.binds {
refs(&bind.rhs, out);
}
refs(b, out);
}
Expr::Con(_, _, args) | Expr::Prim(_, _, args, _) => {
for a in args {
refs(a, out);
}
}
Expr::Match(m) => {
for row in &m.rows {
for g in &row.locals {
for b in &g.binds {
refs(&b.rhs, out);
}
}
match &row.body {
RowBody::Plain(e) => refs(e, out),
RowBody::Guarded(gs) => {
for (g, e) in gs {
refs(g, out);
refs(e, out);
}
}
}
}
}
_ => {}
}
}
let binds =
groups.into_iter().flat_map(|g| g.binds).collect::<Vec<_>>();
let indices = binds
.iter()
.enumerate()
.map(|(i, b)| (b.name.unique(), i))
.collect::<std::collections::BTreeMap<_, _>>();
let edges = binds
.iter()
.map(|b| {
let mut names = std::collections::BTreeSet::new();
refs(&b.rhs, &mut names);
names
.into_iter()
.filter_map(|n| indices.get(&n).copied())
.collect::<Vec<_>>()
})
.collect::<Vec<_>>();
let mut binds = binds.into_iter().map(Some).collect::<Vec<_>>();
crate::scc::components(&edges)
.into_iter()
.map(|xs| BindGroup {
recursive: (xs.len() > 1 || edges[xs[0]].contains(&xs[0]))
&& xs
.iter()
.all(|i| is_function(&binds[*i].as_ref().unwrap().rhs)),
binds: xs
.into_iter()
.map(|i| binds[i].take().unwrap())
.collect(),
})
.collect()
}
#[derive(Clone, Debug)]
/// A recursive binding is guaranteed to have a lambda right-hand side.
pub struct Bind {
pub name: Id,
pub rhs: Box<Expr>,
}
pub use crate::core_type::Type;
use crate::{ast::Op, source::Span};
/// A Core identifier carries its independently checkable type.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Id {
pub name: crate::names::Id,
pub ty: Type,
}
impl std::fmt::Display for Id {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{} : {}", self.name, self.ty)
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
/// Immediate source values; strings are primitive UTF-8 values, not character lists.
pub enum Lit {
Double(u64),
Int(i64),
Char(char),
String(String),
}
#[derive(Clone, Debug)]
/// System F Core makes type abstraction and instantiation explicit.
pub enum Expr {
Var(Id),
Global(Id),
TyLam(u32, Box<Expr>),
TyApp(Box<Expr>, Type),
Lit(Lit),
Lam(Id, Box<Expr>),
App(Box<Expr>, Box<Expr>),
Let(BindGroup, Box<Expr>),
Con(crate::data::ConId, Vec<Type>, Vec<Expr>),
Match(Match),
Case(Box<Expr>, Id, Type, Vec<Alt>),
Join(crate::names::Id, Vec<Id>, Box<Expr>, Box<Expr>),
Jump(crate::names::Id, Vec<Expr>, Type),
PatternFail(Span, Type),
Prim(Op, Vec<Type>, Vec<Expr>, Span),
}
/// Flat alternatives inspect one constructor or literal, never nested patterns.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum AltCon {
Con(crate::data::ConId),
Lit(Lit),
Default,
}
/// Constructor slots become typed binders scoped over the alternative body.
#[derive(Clone, Debug)]
pub struct Alt {
pub con: AltCon,
pub binders: Vec<Id>,
pub rhs: Expr,
}
#[derive(Clone, Debug)]
/// A recursive binding is guaranteed to have a lambda right-hand side.
pub struct Bind {
pub name: Id,
pub rhs: Box<Expr>,
}
#[derive(Clone, Debug)]
/// Globals are initialized in dependency order, with explicit recursive components.
pub struct Program {
pub groups: Vec<BindGroup>,
/// Flat type fingerprints survive erasure for cross-module ABI checks.
pub global_types:
std::collections::BTreeMap<crate::names::Id, Vec<String>>,
pub main: Id,
pub data_types: Vec<(crate::data::TyConId, crate::kinds::Kind)>,
pub type_kinds: std::collections::BTreeMap<u32, crate::kinds::Kind>,
pub constructors: Vec<ConDecl>,
pub locations: Vec<(Span, String)>,
}
impl std::fmt::Display for Expr {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Case(scrut, binder, ty, alts) => {
write!(f, "(case {scrut} as {binder} -> {ty}")?;
for alt in alts {
write!(f, " [ {:?}", alt.con)?;
for id in &alt.binders {
write!(f, " {id}")?;
}
write!(f, " -> {} ]", alt.rhs)?;
}
write!(f, ")")
}
Self::Join(id, params, body, rest) => {
write!(f, "(join {id} (")?;
for p in params {
write!(f, " {p}")?;
}
write!(f, ") = {body} in {rest})")
}
Self::Jump(id, args, ty) => {
write!(f, "(jump {id} : {ty}")?;
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
Self::Var(n) => write!(f, "{}", n.name),
Self::Global(n) => write!(f, "@{}", n.name),
Self::TyLam(v, b) => write!(f, "(type-lambda t{v} {b})"),
Self::TyApp(a, t) => write!(f, "(type-app {a} {t})"),
Self::Lit(l) => write!(f, "{l}"),
Self::Lam(n, b) => write!(f, "(lambda {n} {b})"),
Self::App(a, b) => write!(f, "(app {a} {b})"),
Self::Let(group, body) => write!(f, "(let {group} in {body})"),
Self::Con(id, types, args) => {
write!(f, "(con {}", id.name)?;
for t in types {
write!(f, " [{t}]")?;
}
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
Self::Match(m) => {
write!(f, "(match")?;
for s in &m.scruts {
write!(f, " {}", s.name)?;
}
for row in &m.rows {
write!(f, " {row}")?;
}
write!(f, ")")
}
Self::PatternFail(_, ty) => write!(f, "(pattern-fail : {ty})"),
Self::Prim(op, _, args, _) => {
write!(f, "(prim {}", op.text())?;
for a in args {
write!(f, " {a}")?;
}
write!(f, ")")
}
}
}
}
impl std::fmt::Display for Lit {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Double(bits) => write!(
f,
"{}",
crate::primitives::show_double(f64::from_bits(*bits))
),
Self::Int(n) => write!(f, "{n}"),
Self::Char(c) => {
write!(f, "{}", crate::ast::quote(&c.to_string(), '\''))
}
Self::String(s) => write!(f, "{}", crate::ast::quote(s, '"')),
}
}
}
impl std::fmt::Display for BindGroup {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{} {{", if self.recursive { "rec" } else { "nonrec" })?;
for b in &self.binds {
write!(f, " {} = {};", b.name, b.rhs)?;
}
write!(f, " }}")
}
}
/// Independently typecheck System F Core after each Core-producing pass.
pub fn lint(program: &Program) -> Result<(), String> {
crate::core_lint::lint(program)
}
impl Id {
pub fn unique(&self) -> u32 {
self.name.name.unique
}
}
/// Constructor typing is immutable and contains no inference metavariables.
#[derive(Clone, Debug)]
pub struct ConDecl {
pub labels: Option<Vec<String>>,
pub id: crate::data::ConId,
pub tag: u32,
pub parameters: Vec<u32>,
pub fields: Vec<Type>,
pub result: Type,
}
/// Nested patterns remain until the decision-tree compiler in Chapter 16.
#[derive(Clone, Debug)]
pub enum Pat {
Var(Id),
Wild,
As(Id, Box<Pat>),
Con(crate::data::ConId, Vec<Pat>),
Lit(Lit),
}
/// A guarded row falls through when all its Boolean tests fail.
#[derive(Clone, Debug)]
pub enum RowBody {
Plain(Box<Expr>),
Guarded(Vec<(Expr, Expr)>),
}
/// Row-local declarations run after patterns match and are shared by the guards.
#[derive(Clone, Debug)]
pub struct Row {
pub pats: Vec<Pat>,
pub locals: Vec<BindGroup>,
pub body: RowBody,
pub span: Span,
}
/// Scrutinees name strict preceding lets; the match records its result type and failure site.
#[derive(Clone, Debug)]
pub struct Match {
pub scruts: Vec<Id>,
pub rows: Vec<Row>,
pub result: Type,
pub span: Span,
}
impl std::fmt::Display for Pat {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Var(id) => write!(f, "{}", id.name),
Self::Wild => write!(f, "_"),
Self::As(id, p) => write!(f, "{}@{p}", id.name),
Self::Lit(l) => write!(f, "{l}"),
Self::Con(id, ps) => {
write!(f, "({}", id.name)?;
for p in ps {
write!(f, " {p}")?;
}
write!(f, ")")
}
}
}
}
impl std::fmt::Display for Row {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "[ ")?;
for p in &self.pats {
write!(f, "{p} ")?;
}
for local in &self.locals {
write!(f, "{local} ")?;
}
match &self.body {
RowBody::Plain(e) => write!(f, "-> {e}")?,
RowBody::Guarded(gs) => {
for (g, e) in gs {
write!(f, "| {g} -> {e} ")?;
}
}
}
write!(f, " ]")
}
}
/// Type abstractions erase; a constrained value is an ordinary dictionary function.
pub fn is_function(mut e: &Expr) -> bool {
while let Expr::TyLam(_, body) = e {
e = body;
}
matches!(e, Expr::Lam(..))
}
/// Dictionary calls introduce global dependencies absent from the source graph.
pub fn order(groups: Vec<BindGroup>) -> Vec<BindGroup> {
fn refs(e: &Expr, out: &mut std::collections::BTreeSet<u32>) {
match e {
Expr::Case(s, _, _, alts) => {
refs(s, out);
for a in alts {
refs(&a.rhs, out)
}
}
Expr::Join(_, _, b, r) => {
refs(b, out);
refs(r, out)
}
Expr::Jump(_, args, _) => {
for a in args {
refs(a, out)
}
}
Expr::Global(id) => {
out.insert(id.unique());
}
Expr::Lam(_, b) | Expr::TyLam(_, b) | Expr::TyApp(b, _) => {
refs(b, out)
}
Expr::App(a, b) => {
refs(a, out);
refs(b, out);
}
Expr::Let(g, b) => {
for bind in &g.binds {
refs(&bind.rhs, out);
}
refs(b, out);
}
Expr::Con(_, _, args) | Expr::Prim(_, _, args, _) => {
for a in args {
refs(a, out);
}
}
Expr::Match(m) => {
for row in &m.rows {
for g in &row.locals {
for b in &g.binds {
refs(&b.rhs, out);
}
}
match &row.body {
RowBody::Plain(e) => refs(e, out),
RowBody::Guarded(gs) => {
for (g, e) in gs {
refs(g, out);
refs(e, out);
}
}
}
}
}
_ => {}
}
}
let binds =
groups.into_iter().flat_map(|g| g.binds).collect::<Vec<_>>();
let indices = binds
.iter()
.enumerate()
.map(|(i, b)| (b.name.unique(), i))
.collect::<std::collections::BTreeMap<_, _>>();
let edges = binds
.iter()
.map(|b| {
let mut names = std::collections::BTreeSet::new();
refs(&b.rhs, &mut names);
names
.into_iter()
.filter_map(|n| indices.get(&n).copied())
.collect::<Vec<_>>()
})
.collect::<Vec<_>>();
let mut binds = binds.into_iter().map(Some).collect::<Vec<_>>();
crate::scc::components(&edges)
.into_iter()
.map(|xs| BindGroup {
recursive: (xs.len() > 1 || edges[xs[0]].contains(&xs[0]))
&& xs
.iter()
.all(|i| is_function(&binds[*i].as_ref().unwrap().rhs)),
binds: xs
.into_iter()
.map(|i| binds[i].take().unwrap())
.collect(),
})
.collect()
}
#[derive(Clone, Debug)]
/// An ordered component; recursive members are in scope in every right-hand side.
pub struct BindGroup {
pub recursive: bool,
pub binds: Vec<Bind>,
}
}A recursive group contains functions. A nonrecursive group’s right-hand sides are evaluated in dependency order. Case binders name the already evaluated scrutinee. Pattern failure and failing primitives retain source locations.
A-Normal Form
Atoms cannot perform an effect or fail when read from a well-scoped environment.
A Let names one strict computation. The body type is Rc<Anf>, allowing the
machine and transformation worklists to share immutable syntax.
#![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)]
/// 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,
pub reps: BTreeMap<Var, crate::rep::Rep>,
}
#[derive(Clone)]
enum Context {
Return,
Jump(Id),
Bind(Var, Body),
}
struct Convert<'a> {
sess: &'a mut Session,
arities: BTreeMap<Id, usize>,
reps: BTreeMap<Var, crate::rep::Rep>,
}
fn arity(mut e: &erase::Expr) -> usize {
let mut n = 0;
while let erase::Node::Lam(_, b) = &e.node {
n += 1;
e = b;
}
n
}
fn collect(e: &erase::Expr, out: &mut BTreeMap<Id, usize>) {
use erase::Node as E;
let mut todo = vec![e];
while let Some(e) = todo.pop() {
match &e.node {
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, rep: crate::rep::Rep) -> Var {
let id = self.sess.fresh_id("$a");
self.reps.insert(id.clone(), rep);
id
}
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, rep: crate::rep::Rep) -> 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(rep);
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 crate::rep::Rep;
use erase::Node as E;
enum Work {
Expr(erase::Expr, Context),
Bindings(Vec<(Var, erase::Expr)>),
Lambda(Vec<Var>, Context, Rep),
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, Rep),
}
fn peel(mut e: erase::Expr) -> (Vec<Var>, erase::Expr) {
let mut ps = vec![];
while let E::Lam(v, b) = e.node {
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, rep) => {
let body = results.pop().unwrap();
results.push(self.rhs(
Rhs::Lambda(Lambda { params, body }),
k,
rep,
));
}
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, rep) => {
let rest = results.pop().unwrap();
let vars: Vec<_> =
args.iter().map(|e| self.fresh(e.rep)).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),
rep,
);
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) => {
let rep = e.rep;
match e.node {
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(erase::Expr { node, rep });
todo.push(Work::Lambda(ps, k, rep));
todo.push(Work::Expr(body, Context::Return));
}
node @ E::App(..) => {
let mut head = erase::Expr { node, rep };
let mut args = vec![];
let mut reps = vec![];
while let E::App(f, a) = head.node {
reps.push(head.rep);
args.push(*a);
head = *f;
}
args.reverse();
reps.reverse();
let known = match &head.node {
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 extra_reps = reps.split_off(n);
let f = self.fresh(head.rep);
if extra.is_empty() {
let vars: Vec<_> = args
.iter()
.map(|e| self.fresh(e.rep))
.collect();
let atoms = vars
.iter()
.cloned()
.map(Atom::Var)
.collect();
results.push(self.rhs(
Rhs::Call(Atom::Var(f.clone()), atoms),
k,
rep,
));
todo.push(Work::Bindings(
std::iter::once((f, head))
.chain(vars.into_iter().zip(args))
.collect(),
));
} else {
let result = self.fresh(Rep::Word);
let application =
extra.into_iter().zip(extra_reps).fold(
erase::Expr {
node: E::Var(result.clone()),
rep: Rep::Word,
},
|f, (a, rep)| erase::Expr {
node: E::App(
Box::new(f),
Box::new(a),
),
rep,
},
);
todo.push(Work::Call(
head,
f,
args,
result,
Rep::Word,
));
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(|e| self.fresh(e.rep))
.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, rep),
),
E::Prim(p, es, s) => (
es,
self.rhs(
Rhs::Prim(p, atoms, s),
k,
rep,
),
),
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,
reps: program.reps,
};
let globals = program
.globals
.into_iter()
.map(|(v, e)| (v, c.expr(e, Context::Return)))
.collect();
Program {
reps: c.reps,
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, PartialEq, Eq)]
/// Atoms cannot perform work or fail when read from a well-scoped environment.
pub enum Atom {
Var(Var),
Global(Id),
Lit(Lit),
}
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)]
/// 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,
pub reps: BTreeMap<Var, crate::rep::Rep>,
}
#[derive(Clone)]
enum Context {
Return,
Jump(Id),
Bind(Var, Body),
}
struct Convert<'a> {
sess: &'a mut Session,
arities: BTreeMap<Id, usize>,
reps: BTreeMap<Var, crate::rep::Rep>,
}
fn arity(mut e: &erase::Expr) -> usize {
let mut n = 0;
while let erase::Node::Lam(_, b) = &e.node {
n += 1;
e = b;
}
n
}
fn collect(e: &erase::Expr, out: &mut BTreeMap<Id, usize>) {
use erase::Node as E;
let mut todo = vec![e];
while let Some(e) = todo.pop() {
match &e.node {
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, rep: crate::rep::Rep) -> Var {
let id = self.sess.fresh_id("$a");
self.reps.insert(id.clone(), rep);
id
}
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, rep: crate::rep::Rep) -> 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(rep);
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 crate::rep::Rep;
use erase::Node as E;
enum Work {
Expr(erase::Expr, Context),
Bindings(Vec<(Var, erase::Expr)>),
Lambda(Vec<Var>, Context, Rep),
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, Rep),
}
fn peel(mut e: erase::Expr) -> (Vec<Var>, erase::Expr) {
let mut ps = vec![];
while let E::Lam(v, b) = e.node {
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, rep) => {
let body = results.pop().unwrap();
results.push(self.rhs(
Rhs::Lambda(Lambda { params, body }),
k,
rep,
));
}
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, rep) => {
let rest = results.pop().unwrap();
let vars: Vec<_> =
args.iter().map(|e| self.fresh(e.rep)).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),
rep,
);
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) => {
let rep = e.rep;
match e.node {
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(erase::Expr { node, rep });
todo.push(Work::Lambda(ps, k, rep));
todo.push(Work::Expr(body, Context::Return));
}
node @ E::App(..) => {
let mut head = erase::Expr { node, rep };
let mut args = vec![];
let mut reps = vec![];
while let E::App(f, a) = head.node {
reps.push(head.rep);
args.push(*a);
head = *f;
}
args.reverse();
reps.reverse();
let known = match &head.node {
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 extra_reps = reps.split_off(n);
let f = self.fresh(head.rep);
if extra.is_empty() {
let vars: Vec<_> = args
.iter()
.map(|e| self.fresh(e.rep))
.collect();
let atoms = vars
.iter()
.cloned()
.map(Atom::Var)
.collect();
results.push(self.rhs(
Rhs::Call(Atom::Var(f.clone()), atoms),
k,
rep,
));
todo.push(Work::Bindings(
std::iter::once((f, head))
.chain(vars.into_iter().zip(args))
.collect(),
));
} else {
let result = self.fresh(Rep::Word);
let application =
extra.into_iter().zip(extra_reps).fold(
erase::Expr {
node: E::Var(result.clone()),
rep: Rep::Word,
},
|f, (a, rep)| erase::Expr {
node: E::App(
Box::new(f),
Box::new(a),
),
rep,
},
);
todo.push(Work::Call(
head,
f,
args,
result,
Rep::Word,
));
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(|e| self.fresh(e.rep))
.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, rep),
),
E::Prim(p, es, s) => (
es,
self.rhs(
Rhs::Prim(p, atoms, s),
k,
rep,
),
),
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,
reps: program.reps,
};
let globals = program
.globals
.into_iter()
.map(|(v, e)| (v, c.expr(e, Context::Return)))
.collect();
Program {
reps: c.reps,
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)]
/// Lambda parameters are merged only across syntactically adjacent lambdas.
pub struct Lambda {
pub params: Vec<Var>,
pub body: Body,
}
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)]
/// 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,
pub reps: BTreeMap<Var, crate::rep::Rep>,
}
#[derive(Clone)]
enum Context {
Return,
Jump(Id),
Bind(Var, Body),
}
struct Convert<'a> {
sess: &'a mut Session,
arities: BTreeMap<Id, usize>,
reps: BTreeMap<Var, crate::rep::Rep>,
}
fn arity(mut e: &erase::Expr) -> usize {
let mut n = 0;
while let erase::Node::Lam(_, b) = &e.node {
n += 1;
e = b;
}
n
}
fn collect(e: &erase::Expr, out: &mut BTreeMap<Id, usize>) {
use erase::Node as E;
let mut todo = vec![e];
while let Some(e) = todo.pop() {
match &e.node {
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, rep: crate::rep::Rep) -> Var {
let id = self.sess.fresh_id("$a");
self.reps.insert(id.clone(), rep);
id
}
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, rep: crate::rep::Rep) -> 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(rep);
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 crate::rep::Rep;
use erase::Node as E;
enum Work {
Expr(erase::Expr, Context),
Bindings(Vec<(Var, erase::Expr)>),
Lambda(Vec<Var>, Context, Rep),
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, Rep),
}
fn peel(mut e: erase::Expr) -> (Vec<Var>, erase::Expr) {
let mut ps = vec![];
while let E::Lam(v, b) = e.node {
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, rep) => {
let body = results.pop().unwrap();
results.push(self.rhs(
Rhs::Lambda(Lambda { params, body }),
k,
rep,
));
}
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, rep) => {
let rest = results.pop().unwrap();
let vars: Vec<_> =
args.iter().map(|e| self.fresh(e.rep)).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),
rep,
);
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) => {
let rep = e.rep;
match e.node {
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(erase::Expr { node, rep });
todo.push(Work::Lambda(ps, k, rep));
todo.push(Work::Expr(body, Context::Return));
}
node @ E::App(..) => {
let mut head = erase::Expr { node, rep };
let mut args = vec![];
let mut reps = vec![];
while let E::App(f, a) = head.node {
reps.push(head.rep);
args.push(*a);
head = *f;
}
args.reverse();
reps.reverse();
let known = match &head.node {
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 extra_reps = reps.split_off(n);
let f = self.fresh(head.rep);
if extra.is_empty() {
let vars: Vec<_> = args
.iter()
.map(|e| self.fresh(e.rep))
.collect();
let atoms = vars
.iter()
.cloned()
.map(Atom::Var)
.collect();
results.push(self.rhs(
Rhs::Call(Atom::Var(f.clone()), atoms),
k,
rep,
));
todo.push(Work::Bindings(
std::iter::once((f, head))
.chain(vars.into_iter().zip(args))
.collect(),
));
} else {
let result = self.fresh(Rep::Word);
let application =
extra.into_iter().zip(extra_reps).fold(
erase::Expr {
node: E::Var(result.clone()),
rep: Rep::Word,
},
|f, (a, rep)| erase::Expr {
node: E::App(
Box::new(f),
Box::new(a),
),
rep,
},
);
todo.push(Work::Call(
head,
f,
args,
result,
Rep::Word,
));
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(|e| self.fresh(e.rep))
.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, rep),
),
E::Prim(p, es, s) => (
es,
self.rhs(
Rhs::Prim(p, atoms, s),
k,
rep,
),
),
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,
reps: program.reps,
};
let globals = program
.globals
.into_iter()
.map(|(v, e)| (v, c.expr(e, Context::Return)))
.collect();
Program {
reps: c.reps,
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)]
/// 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),
}
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,
pub reps: BTreeMap<Var, crate::rep::Rep>,
}
#[derive(Clone)]
enum Context {
Return,
Jump(Id),
Bind(Var, Body),
}
struct Convert<'a> {
sess: &'a mut Session,
arities: BTreeMap<Id, usize>,
reps: BTreeMap<Var, crate::rep::Rep>,
}
fn arity(mut e: &erase::Expr) -> usize {
let mut n = 0;
while let erase::Node::Lam(_, b) = &e.node {
n += 1;
e = b;
}
n
}
fn collect(e: &erase::Expr, out: &mut BTreeMap<Id, usize>) {
use erase::Node as E;
let mut todo = vec![e];
while let Some(e) = todo.pop() {
match &e.node {
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, rep: crate::rep::Rep) -> Var {
let id = self.sess.fresh_id("$a");
self.reps.insert(id.clone(), rep);
id
}
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, rep: crate::rep::Rep) -> 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(rep);
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 crate::rep::Rep;
use erase::Node as E;
enum Work {
Expr(erase::Expr, Context),
Bindings(Vec<(Var, erase::Expr)>),
Lambda(Vec<Var>, Context, Rep),
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, Rep),
}
fn peel(mut e: erase::Expr) -> (Vec<Var>, erase::Expr) {
let mut ps = vec![];
while let E::Lam(v, b) = e.node {
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, rep) => {
let body = results.pop().unwrap();
results.push(self.rhs(
Rhs::Lambda(Lambda { params, body }),
k,
rep,
));
}
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, rep) => {
let rest = results.pop().unwrap();
let vars: Vec<_> =
args.iter().map(|e| self.fresh(e.rep)).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),
rep,
);
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) => {
let rep = e.rep;
match e.node {
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(erase::Expr { node, rep });
todo.push(Work::Lambda(ps, k, rep));
todo.push(Work::Expr(body, Context::Return));
}
node @ E::App(..) => {
let mut head = erase::Expr { node, rep };
let mut args = vec![];
let mut reps = vec![];
while let E::App(f, a) = head.node {
reps.push(head.rep);
args.push(*a);
head = *f;
}
args.reverse();
reps.reverse();
let known = match &head.node {
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 extra_reps = reps.split_off(n);
let f = self.fresh(head.rep);
if extra.is_empty() {
let vars: Vec<_> = args
.iter()
.map(|e| self.fresh(e.rep))
.collect();
let atoms = vars
.iter()
.cloned()
.map(Atom::Var)
.collect();
results.push(self.rhs(
Rhs::Call(Atom::Var(f.clone()), atoms),
k,
rep,
));
todo.push(Work::Bindings(
std::iter::once((f, head))
.chain(vars.into_iter().zip(args))
.collect(),
));
} else {
let result = self.fresh(Rep::Word);
let application =
extra.into_iter().zip(extra_reps).fold(
erase::Expr {
node: E::Var(result.clone()),
rep: Rep::Word,
},
|f, (a, rep)| erase::Expr {
node: E::App(
Box::new(f),
Box::new(a),
),
rep,
},
);
todo.push(Work::Call(
head,
f,
args,
result,
Rep::Word,
));
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(|e| self.fresh(e.rep))
.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, rep),
),
E::Prim(p, es, s) => (
es,
self.rhs(
Rhs::Prim(p, atoms, s),
k,
rep,
),
),
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,
reps: program.reps,
};
let globals = program
.globals
.into_iter()
.map(|(v, e)| (v, c.expr(e, Context::Return)))
.collect();
Program {
reps: c.reps,
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),
}
}Ret returns to the current continuation. TailCall replaces the current
activation. Jump stays inside it. A non-tail source case sends its alternatives
to one join representing the rest of the computation. The iterative ANF machine
uses this distinction to run deep tail recursion without recursive Rust calls.
Flat IR
Every lambda has become a lifted function. Its environment is explicit when it captures values. Function indices refer to the program’s function table.
#![allow(unused)]
fn main() {
pub use crate::anf::{Atom, Var};
use crate::{
ast::Op,
core::{self, AltCon},
data::ConId,
source::Span,
};
use std::rc::Rc;
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
/// An index into this program's lifted function table.
pub struct FuncId(pub u32);
pub type Body = Rc<Flat>;
#[derive(Clone, Debug)]
/// Function globals are installed before ordered strict value initializers run.
pub struct GlobalInit {
pub name: Var,
pub function: Option<FuncId>,
pub body: Body,
}
#[derive(Clone, Debug)]
pub struct Program {
pub funcs: Vec<Func>,
pub globals: Vec<GlobalInit>,
pub metadata: core::Program,
pub reps: crate::rep::Table,
}
#[derive(Clone, Debug)]
/// PatchClosure is a compiler-only operation used after all letrec allocations.
pub enum Rhs {
Atom(Atom),
CallKnown(FuncId, Option<Atom>, Vec<Atom>),
CallUnknown(Atom, Vec<Atom>),
AllocCon(ConId, Vec<Atom>),
AllocClosure(FuncId, Vec<Atom>),
EnvField(Var, u32),
Field(Atom, u32),
Prim(Op, Vec<Atom>, Span),
PatchClosure(Atom, u32, Atom),
}
#[derive(Clone, Debug)]
/// Control transfers are explicit and joins remain local to each function.
pub enum Flat {
Let(Var, Rhs, Body),
Case(Atom, Vec<(AltCon, Vec<Var>, Body)>),
Join(Var, Vec<Var>, Body, Body),
Jump(Var, Vec<Atom>),
Ret(Atom),
TailCallKnown(FuncId, Option<Atom>, Vec<Atom>),
TailCallUnknown(Atom, Vec<Atom>),
Fail(Span),
}
impl std::fmt::Display for FuncId {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "f{}", self.0)
}
}
fn list<T: std::fmt::Display>(xs: &[T]) -> String {
xs.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::CallKnown(id, env, args) => write!(
f,
"call {id}[{}]({})",
env.as_ref().map(ToString::to_string).unwrap_or_default(),
list(args)
),
Self::CallUnknown(a, args) => {
write!(f, "apply {a}({})", list(args))
}
Self::AllocCon(c, args) => {
write!(f, "{}({})", c.name, list(args))
}
Self::AllocClosure(id, args) => {
write!(f, "closure {id}[{}]", list(args))
}
Self::EnvField(v, i) => write!(f, "env {v}[{i}]"),
Self::Field(a, i) => write!(f, "field {a}[{i}]"),
Self::Prim(p, args, _) => {
write!(f, "{}({})", p.text(), list(args))
}
Self::PatchClosure(a, i, v) => {
write!(f, "patch {a}[{i}] = {v}")
}
}
}
}
impl std::fmt::Display for Flat {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
enum Visit<'a> {
Body(&'a Flat),
Text(String),
}
let mut work = vec![Visit::Body(self)];
while let Some(next) = work.pop() {
let Visit::Body(node) = next else {
if let Visit::Text(text) = next {
f.write_str(&text)?;
}
continue;
};
match node {
Self::Let(v, r, b) => {
writeln!(f, "let {v} = {r};")?;
work.push(Visit::Body(b));
}
Self::Join(j, ps, b, r) => {
write!(f, "join {j}({}) = {{ ", list(ps))?;
work.extend([
Visit::Body(r),
Visit::Text(" };\n".into()),
Visit::Body(b),
]);
}
Self::Jump(j, args) => {
write!(f, "jump {j}({})", list(args))?
}
Self::Ret(a) => write!(f, "return {a}")?,
Self::TailCallKnown(id, env, args) => write!(
f,
"tail {id}[{}]({})",
env.as_ref()
.map(ToString::to_string)
.unwrap_or_default(),
list(args)
)?,
Self::TailCallUnknown(a, args) => {
write!(f, "tail-apply {a}({})", list(args))?
}
Self::Fail(s) => write!(f, "fail {s:?}")?,
Self::Case(a, alts) => {
writeln!(f, "case {a} {{")?;
work.push(Visit::Text("}".into()));
for (c, ps, b) in alts.iter().rev() {
let head = match c {
AltCon::Con(c) => c.name.clone(),
AltCon::Lit(l) => l.to_string(),
AltCon::Default => "_".into(),
};
work.extend([
Visit::Text(" }\n".into()),
Visit::Body(b),
Visit::Text(format!(
"{head}({}) -> {{ ",
list(ps)
)),
]);
}
}
}
}
Ok(())
}
}
/// Drain owned IR edges explicitly: even Rc destruction can otherwise recurse deeply.
impl Drop for Program {
fn drop(&mut self) {
let mut work = self
.funcs
.drain(..)
.map(|f| f.body)
.chain(self.globals.drain(..).map(|g| g.body))
.collect::<Vec<_>>();
while let Some(body) = work.pop() {
let Ok(node) = Rc::try_unwrap(body) else {
continue;
};
match node {
Flat::Let(_, _, rest) => work.push(rest),
Flat::Join(_, _, body, rest) => work.extend([body, rest]),
Flat::Case(_, alts) => {
work.extend(alts.into_iter().map(|(_, _, b)| b))
}
_ => {}
}
}
}
}
#[derive(Clone, Debug)]
/// Only lifted local lambdas receive an environment parameter.
pub struct Func {
pub name: FuncId,
pub source: Var,
pub env: Option<Var>,
pub params: Vec<Var>,
pub body: Body,
pub captures: Vec<Var>,
}
pub use crate::anf::{Atom, Var};
use crate::{
ast::Op,
core::{self, AltCon},
data::ConId,
source::Span,
};
use std::rc::Rc;
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
/// An index into this program's lifted function table.
pub struct FuncId(pub u32);
pub type Body = Rc<Flat>;
#[derive(Clone, Debug)]
/// Only lifted local lambdas receive an environment parameter.
pub struct Func {
pub name: FuncId,
pub source: Var,
pub env: Option<Var>,
pub params: Vec<Var>,
pub body: Body,
pub captures: Vec<Var>,
}
#[derive(Clone, Debug)]
pub struct Program {
pub funcs: Vec<Func>,
pub globals: Vec<GlobalInit>,
pub metadata: core::Program,
pub reps: crate::rep::Table,
}
#[derive(Clone, Debug)]
/// PatchClosure is a compiler-only operation used after all letrec allocations.
pub enum Rhs {
Atom(Atom),
CallKnown(FuncId, Option<Atom>, Vec<Atom>),
CallUnknown(Atom, Vec<Atom>),
AllocCon(ConId, Vec<Atom>),
AllocClosure(FuncId, Vec<Atom>),
EnvField(Var, u32),
Field(Atom, u32),
Prim(Op, Vec<Atom>, Span),
PatchClosure(Atom, u32, Atom),
}
#[derive(Clone, Debug)]
/// Control transfers are explicit and joins remain local to each function.
pub enum Flat {
Let(Var, Rhs, Body),
Case(Atom, Vec<(AltCon, Vec<Var>, Body)>),
Join(Var, Vec<Var>, Body, Body),
Jump(Var, Vec<Atom>),
Ret(Atom),
TailCallKnown(FuncId, Option<Atom>, Vec<Atom>),
TailCallUnknown(Atom, Vec<Atom>),
Fail(Span),
}
impl std::fmt::Display for FuncId {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "f{}", self.0)
}
}
fn list<T: std::fmt::Display>(xs: &[T]) -> String {
xs.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::CallKnown(id, env, args) => write!(
f,
"call {id}[{}]({})",
env.as_ref().map(ToString::to_string).unwrap_or_default(),
list(args)
),
Self::CallUnknown(a, args) => {
write!(f, "apply {a}({})", list(args))
}
Self::AllocCon(c, args) => {
write!(f, "{}({})", c.name, list(args))
}
Self::AllocClosure(id, args) => {
write!(f, "closure {id}[{}]", list(args))
}
Self::EnvField(v, i) => write!(f, "env {v}[{i}]"),
Self::Field(a, i) => write!(f, "field {a}[{i}]"),
Self::Prim(p, args, _) => {
write!(f, "{}({})", p.text(), list(args))
}
Self::PatchClosure(a, i, v) => {
write!(f, "patch {a}[{i}] = {v}")
}
}
}
}
impl std::fmt::Display for Flat {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
enum Visit<'a> {
Body(&'a Flat),
Text(String),
}
let mut work = vec![Visit::Body(self)];
while let Some(next) = work.pop() {
let Visit::Body(node) = next else {
if let Visit::Text(text) = next {
f.write_str(&text)?;
}
continue;
};
match node {
Self::Let(v, r, b) => {
writeln!(f, "let {v} = {r};")?;
work.push(Visit::Body(b));
}
Self::Join(j, ps, b, r) => {
write!(f, "join {j}({}) = {{ ", list(ps))?;
work.extend([
Visit::Body(r),
Visit::Text(" };\n".into()),
Visit::Body(b),
]);
}
Self::Jump(j, args) => {
write!(f, "jump {j}({})", list(args))?
}
Self::Ret(a) => write!(f, "return {a}")?,
Self::TailCallKnown(id, env, args) => write!(
f,
"tail {id}[{}]({})",
env.as_ref()
.map(ToString::to_string)
.unwrap_or_default(),
list(args)
)?,
Self::TailCallUnknown(a, args) => {
write!(f, "tail-apply {a}({})", list(args))?
}
Self::Fail(s) => write!(f, "fail {s:?}")?,
Self::Case(a, alts) => {
writeln!(f, "case {a} {{")?;
work.push(Visit::Text("}".into()));
for (c, ps, b) in alts.iter().rev() {
let head = match c {
AltCon::Con(c) => c.name.clone(),
AltCon::Lit(l) => l.to_string(),
AltCon::Default => "_".into(),
};
work.extend([
Visit::Text(" }\n".into()),
Visit::Body(b),
Visit::Text(format!(
"{head}({}) -> {{ ",
list(ps)
)),
]);
}
}
}
}
Ok(())
}
}
/// Drain owned IR edges explicitly: even Rc destruction can otherwise recurse deeply.
impl Drop for Program {
fn drop(&mut self) {
let mut work = self
.funcs
.drain(..)
.map(|f| f.body)
.chain(self.globals.drain(..).map(|g| g.body))
.collect::<Vec<_>>();
while let Some(body) = work.pop() {
let Ok(node) = Rc::try_unwrap(body) else {
continue;
};
match node {
Flat::Let(_, _, rest) => work.push(rest),
Flat::Join(_, _, body, rest) => work.extend([body, rest]),
Flat::Case(_, alts) => {
work.extend(alts.into_iter().map(|(_, _, b)| b))
}
_ => {}
}
}
}
}
#[derive(Clone, Debug)]
/// Function globals are installed before ordered strict value initializers run.
pub struct GlobalInit {
pub name: Var,
pub function: Option<FuncId>,
pub body: Body,
}
pub use crate::anf::{Atom, Var};
use crate::{
ast::Op,
core::{self, AltCon},
data::ConId,
source::Span,
};
use std::rc::Rc;
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
/// An index into this program's lifted function table.
pub struct FuncId(pub u32);
pub type Body = Rc<Flat>;
#[derive(Clone, Debug)]
/// Only lifted local lambdas receive an environment parameter.
pub struct Func {
pub name: FuncId,
pub source: Var,
pub env: Option<Var>,
pub params: Vec<Var>,
pub body: Body,
pub captures: Vec<Var>,
}
#[derive(Clone, Debug)]
/// Function globals are installed before ordered strict value initializers run.
pub struct GlobalInit {
pub name: Var,
pub function: Option<FuncId>,
pub body: Body,
}
#[derive(Clone, Debug)]
/// PatchClosure is a compiler-only operation used after all letrec allocations.
pub enum Rhs {
Atom(Atom),
CallKnown(FuncId, Option<Atom>, Vec<Atom>),
CallUnknown(Atom, Vec<Atom>),
AllocCon(ConId, Vec<Atom>),
AllocClosure(FuncId, Vec<Atom>),
EnvField(Var, u32),
Field(Atom, u32),
Prim(Op, Vec<Atom>, Span),
PatchClosure(Atom, u32, Atom),
}
#[derive(Clone, Debug)]
/// Control transfers are explicit and joins remain local to each function.
pub enum Flat {
Let(Var, Rhs, Body),
Case(Atom, Vec<(AltCon, Vec<Var>, Body)>),
Join(Var, Vec<Var>, Body, Body),
Jump(Var, Vec<Atom>),
Ret(Atom),
TailCallKnown(FuncId, Option<Atom>, Vec<Atom>),
TailCallUnknown(Atom, Vec<Atom>),
Fail(Span),
}
impl std::fmt::Display for FuncId {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "f{}", self.0)
}
}
fn list<T: std::fmt::Display>(xs: &[T]) -> String {
xs.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::CallKnown(id, env, args) => write!(
f,
"call {id}[{}]({})",
env.as_ref().map(ToString::to_string).unwrap_or_default(),
list(args)
),
Self::CallUnknown(a, args) => {
write!(f, "apply {a}({})", list(args))
}
Self::AllocCon(c, args) => {
write!(f, "{}({})", c.name, list(args))
}
Self::AllocClosure(id, args) => {
write!(f, "closure {id}[{}]", list(args))
}
Self::EnvField(v, i) => write!(f, "env {v}[{i}]"),
Self::Field(a, i) => write!(f, "field {a}[{i}]"),
Self::Prim(p, args, _) => {
write!(f, "{}({})", p.text(), list(args))
}
Self::PatchClosure(a, i, v) => {
write!(f, "patch {a}[{i}] = {v}")
}
}
}
}
impl std::fmt::Display for Flat {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
enum Visit<'a> {
Body(&'a Flat),
Text(String),
}
let mut work = vec![Visit::Body(self)];
while let Some(next) = work.pop() {
let Visit::Body(node) = next else {
if let Visit::Text(text) = next {
f.write_str(&text)?;
}
continue;
};
match node {
Self::Let(v, r, b) => {
writeln!(f, "let {v} = {r};")?;
work.push(Visit::Body(b));
}
Self::Join(j, ps, b, r) => {
write!(f, "join {j}({}) = {{ ", list(ps))?;
work.extend([
Visit::Body(r),
Visit::Text(" };\n".into()),
Visit::Body(b),
]);
}
Self::Jump(j, args) => {
write!(f, "jump {j}({})", list(args))?
}
Self::Ret(a) => write!(f, "return {a}")?,
Self::TailCallKnown(id, env, args) => write!(
f,
"tail {id}[{}]({})",
env.as_ref()
.map(ToString::to_string)
.unwrap_or_default(),
list(args)
)?,
Self::TailCallUnknown(a, args) => {
write!(f, "tail-apply {a}({})", list(args))?
}
Self::Fail(s) => write!(f, "fail {s:?}")?,
Self::Case(a, alts) => {
writeln!(f, "case {a} {{")?;
work.push(Visit::Text("}".into()));
for (c, ps, b) in alts.iter().rev() {
let head = match c {
AltCon::Con(c) => c.name.clone(),
AltCon::Lit(l) => l.to_string(),
AltCon::Default => "_".into(),
};
work.extend([
Visit::Text(" }\n".into()),
Visit::Body(b),
Visit::Text(format!(
"{head}({}) -> {{ ",
list(ps)
)),
]);
}
}
}
}
Ok(())
}
}
/// Drain owned IR edges explicitly: even Rc destruction can otherwise recurse deeply.
impl Drop for Program {
fn drop(&mut self) {
let mut work = self
.funcs
.drain(..)
.map(|f| f.body)
.chain(self.globals.drain(..).map(|g| g.body))
.collect::<Vec<_>>();
while let Some(body) = work.pop() {
let Ok(node) = Rc::try_unwrap(body) else {
continue;
};
match node {
Flat::Let(_, _, rest) => work.push(rest),
Flat::Join(_, _, body, rest) => work.extend([body, rest]),
Flat::Case(_, alts) => {
work.extend(alts.into_iter().map(|(_, _, b)| b))
}
_ => {}
}
}
}
}
#[derive(Clone, Debug)]
pub struct Program {
pub funcs: Vec<Func>,
pub globals: Vec<GlobalInit>,
pub metadata: core::Program,
pub reps: crate::rep::Table,
}
pub use crate::anf::{Atom, Var};
use crate::{
ast::Op,
core::{self, AltCon},
data::ConId,
source::Span,
};
use std::rc::Rc;
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
/// An index into this program's lifted function table.
pub struct FuncId(pub u32);
pub type Body = Rc<Flat>;
#[derive(Clone, Debug)]
/// Only lifted local lambdas receive an environment parameter.
pub struct Func {
pub name: FuncId,
pub source: Var,
pub env: Option<Var>,
pub params: Vec<Var>,
pub body: Body,
pub captures: Vec<Var>,
}
#[derive(Clone, Debug)]
/// Function globals are installed before ordered strict value initializers run.
pub struct GlobalInit {
pub name: Var,
pub function: Option<FuncId>,
pub body: Body,
}
#[derive(Clone, Debug)]
pub struct Program {
pub funcs: Vec<Func>,
pub globals: Vec<GlobalInit>,
pub metadata: core::Program,
pub reps: crate::rep::Table,
}
#[derive(Clone, Debug)]
/// Control transfers are explicit and joins remain local to each function.
pub enum Flat {
Let(Var, Rhs, Body),
Case(Atom, Vec<(AltCon, Vec<Var>, Body)>),
Join(Var, Vec<Var>, Body, Body),
Jump(Var, Vec<Atom>),
Ret(Atom),
TailCallKnown(FuncId, Option<Atom>, Vec<Atom>),
TailCallUnknown(Atom, Vec<Atom>),
Fail(Span),
}
impl std::fmt::Display for FuncId {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "f{}", self.0)
}
}
fn list<T: std::fmt::Display>(xs: &[T]) -> String {
xs.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::CallKnown(id, env, args) => write!(
f,
"call {id}[{}]({})",
env.as_ref().map(ToString::to_string).unwrap_or_default(),
list(args)
),
Self::CallUnknown(a, args) => {
write!(f, "apply {a}({})", list(args))
}
Self::AllocCon(c, args) => {
write!(f, "{}({})", c.name, list(args))
}
Self::AllocClosure(id, args) => {
write!(f, "closure {id}[{}]", list(args))
}
Self::EnvField(v, i) => write!(f, "env {v}[{i}]"),
Self::Field(a, i) => write!(f, "field {a}[{i}]"),
Self::Prim(p, args, _) => {
write!(f, "{}({})", p.text(), list(args))
}
Self::PatchClosure(a, i, v) => {
write!(f, "patch {a}[{i}] = {v}")
}
}
}
}
impl std::fmt::Display for Flat {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
enum Visit<'a> {
Body(&'a Flat),
Text(String),
}
let mut work = vec![Visit::Body(self)];
while let Some(next) = work.pop() {
let Visit::Body(node) = next else {
if let Visit::Text(text) = next {
f.write_str(&text)?;
}
continue;
};
match node {
Self::Let(v, r, b) => {
writeln!(f, "let {v} = {r};")?;
work.push(Visit::Body(b));
}
Self::Join(j, ps, b, r) => {
write!(f, "join {j}({}) = {{ ", list(ps))?;
work.extend([
Visit::Body(r),
Visit::Text(" };\n".into()),
Visit::Body(b),
]);
}
Self::Jump(j, args) => {
write!(f, "jump {j}({})", list(args))?
}
Self::Ret(a) => write!(f, "return {a}")?,
Self::TailCallKnown(id, env, args) => write!(
f,
"tail {id}[{}]({})",
env.as_ref()
.map(ToString::to_string)
.unwrap_or_default(),
list(args)
)?,
Self::TailCallUnknown(a, args) => {
write!(f, "tail-apply {a}({})", list(args))?
}
Self::Fail(s) => write!(f, "fail {s:?}")?,
Self::Case(a, alts) => {
writeln!(f, "case {a} {{")?;
work.push(Visit::Text("}".into()));
for (c, ps, b) in alts.iter().rev() {
let head = match c {
AltCon::Con(c) => c.name.clone(),
AltCon::Lit(l) => l.to_string(),
AltCon::Default => "_".into(),
};
work.extend([
Visit::Text(" }\n".into()),
Visit::Body(b),
Visit::Text(format!(
"{head}({}) -> {{ ",
list(ps)
)),
]);
}
}
}
}
Ok(())
}
}
/// Drain owned IR edges explicitly: even Rc destruction can otherwise recurse deeply.
impl Drop for Program {
fn drop(&mut self) {
let mut work = self
.funcs
.drain(..)
.map(|f| f.body)
.chain(self.globals.drain(..).map(|g| g.body))
.collect::<Vec<_>>();
while let Some(body) = work.pop() {
let Ok(node) = Rc::try_unwrap(body) else {
continue;
};
match node {
Flat::Let(_, _, rest) => work.push(rest),
Flat::Join(_, _, body, rest) => work.extend([body, rest]),
Flat::Case(_, alts) => {
work.extend(alts.into_iter().map(|(_, _, b)| b))
}
_ => {}
}
}
}
}
#[derive(Clone, Debug)]
/// PatchClosure is a compiler-only operation used after all letrec allocations.
pub enum Rhs {
Atom(Atom),
CallKnown(FuncId, Option<Atom>, Vec<Atom>),
CallUnknown(Atom, Vec<Atom>),
AllocCon(ConId, Vec<Atom>),
AllocClosure(FuncId, Vec<Atom>),
EnvField(Var, u32),
Field(Atom, u32),
Prim(Op, Vec<Atom>, Span),
PatchClosure(Atom, u32, Atom),
}
pub use crate::anf::{Atom, Var};
use crate::{
ast::Op,
core::{self, AltCon},
data::ConId,
source::Span,
};
use std::rc::Rc;
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
/// An index into this program's lifted function table.
pub struct FuncId(pub u32);
pub type Body = Rc<Flat>;
#[derive(Clone, Debug)]
/// Only lifted local lambdas receive an environment parameter.
pub struct Func {
pub name: FuncId,
pub source: Var,
pub env: Option<Var>,
pub params: Vec<Var>,
pub body: Body,
pub captures: Vec<Var>,
}
#[derive(Clone, Debug)]
/// Function globals are installed before ordered strict value initializers run.
pub struct GlobalInit {
pub name: Var,
pub function: Option<FuncId>,
pub body: Body,
}
#[derive(Clone, Debug)]
pub struct Program {
pub funcs: Vec<Func>,
pub globals: Vec<GlobalInit>,
pub metadata: core::Program,
pub reps: crate::rep::Table,
}
#[derive(Clone, Debug)]
/// PatchClosure is a compiler-only operation used after all letrec allocations.
pub enum Rhs {
Atom(Atom),
CallKnown(FuncId, Option<Atom>, Vec<Atom>),
CallUnknown(Atom, Vec<Atom>),
AllocCon(ConId, Vec<Atom>),
AllocClosure(FuncId, Vec<Atom>),
EnvField(Var, u32),
Field(Atom, u32),
Prim(Op, Vec<Atom>, Span),
PatchClosure(Atom, u32, Atom),
}
impl std::fmt::Display for FuncId {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "f{}", self.0)
}
}
fn list<T: std::fmt::Display>(xs: &[T]) -> String {
xs.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::CallKnown(id, env, args) => write!(
f,
"call {id}[{}]({})",
env.as_ref().map(ToString::to_string).unwrap_or_default(),
list(args)
),
Self::CallUnknown(a, args) => {
write!(f, "apply {a}({})", list(args))
}
Self::AllocCon(c, args) => {
write!(f, "{}({})", c.name, list(args))
}
Self::AllocClosure(id, args) => {
write!(f, "closure {id}[{}]", list(args))
}
Self::EnvField(v, i) => write!(f, "env {v}[{i}]"),
Self::Field(a, i) => write!(f, "field {a}[{i}]"),
Self::Prim(p, args, _) => {
write!(f, "{}({})", p.text(), list(args))
}
Self::PatchClosure(a, i, v) => {
write!(f, "patch {a}[{i}] = {v}")
}
}
}
}
impl std::fmt::Display for Flat {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
enum Visit<'a> {
Body(&'a Flat),
Text(String),
}
let mut work = vec![Visit::Body(self)];
while let Some(next) = work.pop() {
let Visit::Body(node) = next else {
if let Visit::Text(text) = next {
f.write_str(&text)?;
}
continue;
};
match node {
Self::Let(v, r, b) => {
writeln!(f, "let {v} = {r};")?;
work.push(Visit::Body(b));
}
Self::Join(j, ps, b, r) => {
write!(f, "join {j}({}) = {{ ", list(ps))?;
work.extend([
Visit::Body(r),
Visit::Text(" };\n".into()),
Visit::Body(b),
]);
}
Self::Jump(j, args) => {
write!(f, "jump {j}({})", list(args))?
}
Self::Ret(a) => write!(f, "return {a}")?,
Self::TailCallKnown(id, env, args) => write!(
f,
"tail {id}[{}]({})",
env.as_ref()
.map(ToString::to_string)
.unwrap_or_default(),
list(args)
)?,
Self::TailCallUnknown(a, args) => {
write!(f, "tail-apply {a}({})", list(args))?
}
Self::Fail(s) => write!(f, "fail {s:?}")?,
Self::Case(a, alts) => {
writeln!(f, "case {a} {{")?;
work.push(Visit::Text("}".into()));
for (c, ps, b) in alts.iter().rev() {
let head = match c {
AltCon::Con(c) => c.name.clone(),
AltCon::Lit(l) => l.to_string(),
AltCon::Default => "_".into(),
};
work.extend([
Visit::Text(" }\n".into()),
Visit::Body(b),
Visit::Text(format!(
"{head}({}) -> {{ ",
list(ps)
)),
]);
}
}
}
}
Ok(())
}
}
/// Drain owned IR edges explicitly: even Rc destruction can otherwise recurse deeply.
impl Drop for Program {
fn drop(&mut self) {
let mut work = self
.funcs
.drain(..)
.map(|f| f.body)
.chain(self.globals.drain(..).map(|g| g.body))
.collect::<Vec<_>>();
while let Some(body) = work.pop() {
let Ok(node) = Rc::try_unwrap(body) else {
continue;
};
match node {
Flat::Let(_, _, rest) => work.push(rest),
Flat::Join(_, _, body, rest) => work.extend([body, rest]),
Flat::Case(_, alts) => {
work.extend(alts.into_iter().map(|(_, _, b)| b))
}
_ => {}
}
}
}
}
#[derive(Clone, Debug)]
/// Control transfers are explicit and joins remain local to each function.
pub enum Flat {
Let(Var, Rhs, Body),
Case(Atom, Vec<(AltCon, Vec<Var>, Body)>),
Join(Var, Vec<Var>, Body, Body),
Jump(Var, Vec<Atom>),
Ret(Atom),
TailCallKnown(FuncId, Option<Atom>, Vec<Atom>),
TailCallUnknown(Atom, Vec<Atom>),
Fail(Span),
}
}Known calls name a lifted function with the correct number of arguments. Unknown
calls use eval/apply, which supports exact, partial, and oversaturated calls.
PatchClosure initializes a recursive capture after allocating every closure in
the group. It is an internal operation, never a source mutation primitive.
Numeric Evidence and Storage
Chapter 23 preserves a small classification derived from checked Core types:
#![allow(unused)]
fn main() {
impl std::fmt::Display for Rep {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str(match self {
Self::Int => "Int",
Self::Double => "Double",
Self::Word => "Word",
})
}
}
use crate::{
anf::{Anf, Atom, Rhs, Var},
core,
names::Id,
};
use std::collections::BTreeMap;
pub type Table = BTreeMap<Id, Rep>;
/// Missing evidence is an internal error, never an invitation to infer a storage tag.
pub fn get(table: &Table, id: &Id) -> Result<Rep, String> {
table
.get(id)
.copied()
.ok_or_else(|| format!("missing representation evidence for {id}"))
}
pub fn atom(table: &Table, a: &Atom) -> Result<Rep, String> {
match a {
Atom::Var(v) | Atom::Global(v) => get(table, v),
Atom::Lit(l) => Ok(crate::erase::literal_rep(l)),
}
}
/// Numeric operands are checked against the primitive's declared signature.
pub fn primitive(
table: &Table,
op: crate::ast::Op,
args: &[Atom],
result: &Var,
metadata: &core::Program,
) -> Result<(), String> {
use crate::primitives::Prim;
let generic = matches!(
op,
crate::ast::Op::Runtime(Prim::Trace | Prim::Error | Prim::Exit)
);
let types = if generic {
vec![core::Type::Var(0)]
} else {
vec![]
};
let (mut ty, _) = crate::primitives::core_signature(
op,
&types,
&metadata.data_types,
)?;
for arg in args {
let core::Type::Arrow(a, b) = ty else {
return Err("primitive arity evidence".into());
};
if !matches!(a.as_ref(), core::Type::Var(_))
&& atom(table, arg)? != crate::erase::representation(&a)
{
return Err(format!(
"contradictory operand evidence for {}: {:?}",
op.text(),
arg
));
}
ty = *b;
}
let expected = if matches!(op, crate::ast::Op::Runtime(Prim::Trace)) {
atom(table, &args[1])?
} else if matches!(ty, core::Type::Var(_)) {
get(table, result)?
} else {
crate::erase::representation(&ty)
};
if get(table, result)? != expected {
return Err(format!("contradictory result evidence for {result}"));
}
Ok(())
}
/// Copy evidence to the beta continuation's fresh result. No type classification occurs here.
pub fn beta_results(program: &mut crate::anf::Program) {
let mut todo = program
.globals
.iter()
.map(|(_, b)| b.as_ref())
.collect::<Vec<_>>();
let mut joins = BTreeMap::new();
let mut pending = vec![];
while let Some(b) = todo.pop() {
match b {
Anf::Let(v, r, rest) => {
if !program.reps.contains_key(v) {
let Anf::Jump(j, _) = rest.as_ref() else {
panic!("beta result continuation")
};
pending.push((v.clone(), j.clone()));
}
if let Rhs::Lambda(l) = r {
todo.push(&l.body);
}
todo.push(rest);
}
Anf::LetRec(bs, r) => {
todo.push(r);
for (_, l) in bs {
todo.push(&l.body);
}
}
Anf::Join(j, ps, b, r) => {
if ps.len() == 1 {
joins.insert(j.clone(), program.reps[&ps[0]]);
}
todo.push(b);
todo.push(r);
}
Anf::Case(_, alts) => {
for (_, _, b) in alts {
todo.push(b);
}
}
_ => {}
}
}
for (v, j) in pending {
program.reps.insert(v, joins[&j]);
}
}
pub fn lint_anf(program: &crate::anf::Program) -> Result<(), String> {
let mut todo = vec![];
for (v, b) in &program.globals {
get(&program.reps, v)?;
todo.push(b.as_ref());
}
while let Some(b) = todo.pop() {
match b {
Anf::Let(v, r, rest) => {
get(&program.reps, v)?;
match r {
Rhs::Prim(p, args, _) => primitive(
&program.reps,
*p,
args,
v,
&program.metadata,
)?,
Rhs::Lambda(l) => todo.push(&l.body),
_ => {}
}
todo.push(rest);
}
Anf::LetRec(bs, r) => {
todo.push(r);
for (_, l) in bs {
todo.push(&l.body);
}
}
Anf::Join(_, _, b, r) => {
todo.push(b);
todo.push(r);
}
Anf::Case(_, alts) => {
for (_, _, b) in alts {
todo.push(b);
}
}
_ => {}
}
}
Ok(())
}
pub fn lint_flat(program: &crate::flat::Program) -> Result<(), String> {
use crate::flat::{Flat, Rhs};
let mut todo = program
.funcs
.iter()
.map(|f| f.body.as_ref())
.collect::<Vec<_>>();
for g in &program.globals {
get(&program.reps, &g.name)?;
todo.push(g.body.as_ref());
}
while let Some(b) = todo.pop() {
match b {
Flat::Let(v, r, rest) => {
get(&program.reps, v)?;
if let Rhs::Prim(p, args, _) = r {
primitive(
&program.reps,
*p,
args,
v,
&program.metadata,
)?;
}
todo.push(rest);
}
Flat::Join(_, _, b, r) => {
todo.push(b);
todo.push(r);
}
Flat::Case(_, alts) => {
for (_, _, b) in alts {
todo.push(b);
}
}
_ => {}
}
}
Ok(())
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Rep {
Int,
Double,
Word,
}
}This is type evidence, not a calling convention. Call results and parameters
remain words even when their evidence says Int or Double. LLVM’s local
locations distinguish words, native numbers, and reloadable roots:
#![allow(unused)]
fn main() {
use super::*;
use crate::{
core::Lit,
flat::{Atom, FuncId},
runtime_layout as layout,
};
use inkwell::{
types::BasicMetadataTypeEnum,
values::{BasicMetadataValueEnum, PointerValue},
};
impl<'ctx> Backend<'ctx, '_> {
pub(super) fn n(&self, n: u64) -> IntValue<'ctx> {
self.word.const_int(n, false)
}
pub(super) fn external(
&self,
name: &str,
args: &[BasicMetadataTypeEnum<'ctx>],
result: bool,
) -> FunctionValue<'ctx> {
self.module.get_function(name).unwrap_or_else(|| {
let ty = if result {
self.word.fn_type(args, false)
} else {
self.context.void_type().fn_type(args, false)
};
self.module.add_function(name, ty, None)
})
}
pub(super) fn call(
&self,
name: &str,
args: &[BasicMetadataValueEnum<'ctx>],
) -> Result<IntValue<'ctx>> {
let types = args
.iter()
.map(|a| match a {
BasicMetadataValueEnum::IntValue(v) => v.get_type().into(),
BasicMetadataValueEnum::PointerValue(v) => {
v.get_type().into()
}
_ => unreachable!("runtime ABI operands"),
})
.collect::<Vec<_>>();
let call = self.builder.build_call(
self.external(name, &types, true),
args,
"call",
)?;
// A tailcc function must regain control to restore its callee-pop frame.
// LLVM's tail-call pass may otherwise infer a tail transfer into the C ABI.
call.set_tail_call_kind(
inkwell::values::LLVMTailCallKind::LLVMTailCallKindNoTail,
);
Ok(call.try_as_basic_value().unwrap_basic().into_int_value())
}
pub(super) fn void_call(
&self,
name: &str,
args: &[BasicMetadataValueEnum<'ctx>],
) -> Result<()> {
let types = args
.iter()
.map(|a| match a {
BasicMetadataValueEnum::IntValue(v) => v.get_type().into(),
BasicMetadataValueEnum::PointerValue(v) => {
v.get_type().into()
}
_ => unreachable!("runtime ABI operands"),
})
.collect::<Vec<_>>();
let call = self.builder.build_call(
self.external(name, &types, false),
args,
"",
)?;
if self.copying {
call.set_tail_call_kind(
inkwell::values::LLVMTailCallKind::LLVMTailCallKindNoTail,
);
}
Ok(())
}
pub(super) fn pointer(
&self,
value: IntValue<'ctx>,
) -> Result<PointerValue<'ctx>> {
Ok(self.builder.build_int_to_ptr(
value,
self.context.ptr_type(AddressSpace::default()),
"ptr",
)?)
}
pub(super) fn slot(
&self,
pointer: PointerValue<'ctx>,
index: u64,
) -> Result<PointerValue<'ctx>> {
// SAFETY: GEP indexes i64 words using the checked ABI layout.
Ok(unsafe {
self.builder.build_gep(
self.word,
pointer,
&[self.n(index)],
"slot",
)?
})
}
pub(super) fn load(
&self,
value: IntValue<'ctx>,
index: u64,
) -> Result<IntValue<'ctx>> {
Ok(self
.builder
.build_load(
self.word,
self.slot(self.pointer(value)?, index)?,
"load",
)?
.into_int_value())
}
pub(super) fn store(
&self,
value: IntValue<'ctx>,
index: u64,
field: IntValue<'ctx>,
) -> Result<()> {
self.builder
.build_store(self.slot(self.pointer(value)?, index)?, field)?;
Ok(())
}
pub(super) fn allocation(
&self,
kind: u8,
tag: u32,
fields: &[IntValue<'ctx>],
) -> Result<IntValue<'ctx>> {
let protect = self.copying
&& !matches!(kind, layout::DOUBLE | layout::STRING)
&& fields.len() > if kind == layout::CLOSURE { 2 } else { 0 };
let mut roots = None;
if protect {
let entry = self
.builder
.get_insert_block()
.unwrap()
.get_parent()
.unwrap()
.get_first_basic_block()
.unwrap();
let alloc = self.context.create_builder();
alloc.position_before(&entry.get_first_instruction().unwrap());
let p = alloc.build_alloca(
self.word.array_type(fields.len().max(1) as u32),
"allocation.roots",
)?;
for (i, f) in fields.iter().enumerate() {
self.builder.build_store(self.slot(p, i as u64)?, *f)?;
}
// Metadata fields (code, arity) are excluded from the root range.
let skip = if kind == layout::CLOSURE { 2 } else { 0 };
self.void_call(
"rt_roots_push",
&[
self.slot(p, skip)?.into(),
self.n(fields.len() as u64 - skip).into(),
],
)?;
roots = Some(p);
}
let name = if matches!(kind, layout::DOUBLE | layout::STRING) {
"rt_alloc_atomic"
} else {
"rt_alloc"
};
let ptr = self.context.ptr_type(AddressSpace::default());
let f = self.module.get_function(name).unwrap_or_else(|| {
self.module.add_function(
name,
ptr.fn_type(&[self.word.into()], false),
None,
)
});
let size = (fields.len() + 1) as u64
* if name == "rt_alloc" { 1 } else { 8 };
let p = self
.builder
.build_call(f, &[self.n(size).into()], "alloc")?
.try_as_basic_value()
.unwrap_basic()
.into_pointer_value();
let value = self.builder.build_ptr_to_int(p, self.word, "word")?;
self.store(
value,
0,
self.n(layout::header(kind, tag, fields.len() as u32)),
)?;
for (i, field) in fields.iter().enumerate() {
let field = if let Some(p) = roots {
self.builder
.build_load(
self.word,
self.slot(p, i as u64)?,
"relocated.field",
)?
.into_int_value()
} else {
*field
};
self.store(value, i as u64 + 1, field)?;
}
if protect {
self.void_call("rt_roots_pop", &[])?;
}
Ok(value)
}
pub(super) fn closure(
&self,
f: FuncId,
captures: &[IntValue<'ctx>],
) -> Result<IntValue<'ctx>> {
let code = self.slow[f.0 as usize]
.as_global_value()
.as_pointer_value()
.const_to_int(self.word);
let mut fields = vec![
code,
self.n(self.program.funcs[f.0 as usize].params.len() as u64),
];
fields.extend_from_slice(captures);
self.allocation(layout::CLOSURE, 0, &fields)
}
fn string(&mut self, s: &str) -> IntValue<'ctx> {
if let Some(v) = self.strings.get(s) {
return *v;
}
let mut bytes = s.as_bytes().to_vec();
bytes.resize(bytes.len().div_ceil(8) * 8, 0);
let data = self.context.const_string(&bytes, false);
let object = self.context.const_struct(
&[
self.n(layout::header(
layout::STRING,
0,
1 + (bytes.len() / 8) as u32,
))
.into(),
self.n(s.len() as u64).into(),
data.into(),
],
false,
);
let g = self.module.add_global(
object.get_type(),
None,
&format!("fun.string{}", self.strings.len()),
);
g.set_linkage(Linkage::Private);
g.set_constant(true);
g.set_alignment(8);
g.set_initializer(&object);
let word = g.as_pointer_value().const_to_int(self.word);
self.strings.insert(s.into(), word);
word
}
/// Keep static string words in a retained data root table. Strings themselves are read-only.
pub(super) fn string_roots(&self) {
if self.strings.is_empty() {
return;
}
let words = self.strings.values().copied().collect::<Vec<_>>();
let array = self.word.const_array(&words);
let roots = self.module.add_global(
array.get_type(),
None,
"fun.string_roots",
);
roots.set_linkage(Linkage::Internal);
roots.set_initializer(&array);
roots.set_alignment(8);
let ptr = self.context.ptr_type(AddressSpace::default());
let used = ptr.const_array(&[roots.as_pointer_value()]);
let keep =
self.module.add_global(used.get_type(), None, "llvm.used");
keep.set_linkage(Linkage::Appending);
keep.set_section(Some("llvm.metadata"));
keep.set_initializer(&used);
}
pub(super) fn literal(&mut self, l: &Lit) -> Result<IntValue<'ctx>> {
Ok(match l {
Lit::Int(n) => self.n(layout::integer(*n)),
Lit::Char(c) => self.n(layout::integer(*c as i64)),
Lit::String(s) => self.string(s),
Lit::Double(bits) => {
self.allocation(layout::DOUBLE, 0, &[self.n(*bits)])?
}
})
}
pub(super) fn atom(
&mut self,
a: &Atom,
env: &Env<'ctx>,
) -> Result<Loc<'ctx>> {
Ok(match a {
Atom::Lit(Lit::Int(n)) => Loc::Int(self.n(*n as u64)),
Atom::Lit(Lit::Double(bits)) => Loc::Double(
self.context.f64_type().const_float(f64::from_bits(*bits)),
),
Atom::Lit(l) => Loc::Word(self.literal(l)?),
Atom::Var(v) => env[v],
Atom::Global(v) if self.copying => {
Loc::Root(self.globals[v].as_pointer_value())
}
Atom::Global(v) => Loc::Word(
self.builder
.build_load(
self.word,
self.globals[v].as_pointer_value(),
"global",
)?
.into_int_value(),
),
})
}
pub(super) fn loc_word(
&self,
value: Loc<'ctx>,
) -> Result<IntValue<'ctx>> {
match value {
Loc::Root(p) => Ok(self
.builder
.build_load(self.word, p, "root")?
.into_int_value()),
Loc::Word(v) => Ok(v),
Loc::Int(v) => self.retag(v),
Loc::Double(v) => self.box_double(v),
}
}
pub(super) fn loc_int(
&self,
value: Loc<'ctx>,
) -> Result<IntValue<'ctx>> {
match value {
Loc::Root(_) => self.untag(self.loc_word(value)?),
Loc::Word(v) => self.untag(v),
Loc::Int(v) => Ok(v),
Loc::Double(_) => {
unreachable!("numeric evidence checked by Flat lint")
}
}
}
pub(super) fn loc_double(
&self,
value: Loc<'ctx>,
) -> Result<inkwell::values::FloatValue<'ctx>> {
match value {
Loc::Root(_) => self.unbox_double(self.loc_word(value)?),
Loc::Word(v) => self.unbox_double(v),
Loc::Double(v) => Ok(v),
Loc::Int(_) => {
unreachable!("numeric evidence checked by Flat lint")
}
}
}
pub(super) fn atom_word(
&mut self,
a: &Atom,
env: &Env<'ctx>,
) -> Result<IntValue<'ctx>> {
let loc = self.atom(a, env)?;
self.loc_word(loc)
}
pub(super) fn atoms(
&mut self,
args: &[Atom],
env: &Env<'ctx>,
) -> Result<Vec<IntValue<'ctx>>> {
let args = args
.iter()
.map(|a| self.atom(a, env))
.collect::<Result<Vec<_>>>()?;
self.loc_words(&args)
}
pub(super) fn known(
&self,
f: FuncId,
env: Option<IntValue<'ctx>>,
args: &[IntValue<'ctx>],
tail: bool,
) -> Result<IntValue<'ctx>> {
let mut actual: Vec<BasicMetadataValueEnum> =
vec![env.unwrap_or(self.n(0)).into()];
actual
.extend(args.iter().map(|v| BasicMetadataValueEnum::from(*v)));
let call = self.builder.build_call(
self.fast[f.0 as usize],
&actual,
"known",
)?;
call.set_call_convention(TAIL_CC);
call.set_tail_call(tail);
if self
.builder
.get_insert_block()
.unwrap()
.get_parent()
.unwrap()
.get_call_conventions()
!= TAIL_CC
{
call.set_tail_call_kind(
inkwell::values::LLVMTailCallKind::LLVMTailCallKindNoTail,
);
}
Ok(call.try_as_basic_value().unwrap_basic().into_int_value())
}
pub(super) fn apply(
&self,
f: IntValue<'ctx>,
args: &[IntValue<'ctx>],
) -> Result<IntValue<'ctx>> {
if (1..=4).contains(&args.len()) {
let mut actual = vec![f.into()];
actual.extend(
args.iter().map(|v| BasicMetadataValueEnum::from(*v)),
);
return self.call(&format!("rt_apply{}", args.len()), &actual);
}
// Allocate in the entry, never in a loop reached by a join back-edge.
let entry = self
.builder
.get_insert_block()
.unwrap()
.get_parent()
.unwrap()
.get_first_basic_block()
.unwrap();
let alloc = self.context.create_builder();
if let Some(first) = entry.get_first_instruction() {
alloc.position_before(&first);
} else {
alloc.position_at_end(entry);
}
let array = alloc.build_alloca(
self.word.array_type(args.len().max(1) as u32),
"arguments",
)?;
for (i, a) in args.iter().enumerate() {
self.builder.build_store(self.slot(array, i as u64)?, *a)?;
}
self.call(
"rt_apply",
&[f.into(), self.n(args.len() as u64).into(), array.into()],
)
}
pub(super) fn box_double(
&self,
v: inkwell::values::FloatValue<'ctx>,
) -> Result<IntValue<'ctx>> {
let bits = self
.builder
.build_bit_cast(v, self.word, "bits")?
.into_int_value();
self.allocation(layout::DOUBLE, 0, &[bits])
}
pub(super) fn unbox_double(
&self,
v: IntValue<'ctx>,
) -> Result<inkwell::values::FloatValue<'ctx>> {
Ok(self
.builder
.build_bit_cast(
self.load(v, 1)?,
self.context.f64_type(),
"double",
)?
.into_float_value())
}
}
/// Storage is local to codegen. All ABI boundaries still carry tagged words.
#[derive(Clone, Copy)]
pub(super) enum Loc<'ctx> {
Root(PointerValue<'ctx>),
Word(IntValue<'ctx>),
Int(IntValue<'ctx>),
Double(inkwell::values::FloatValue<'ctx>),
}
}The copying backend reloads a Root after a possible collection. Arithmetic can
keep a native number in a register until a boundary requires tagging or boxing.
The runtime ABI specifies those boundaries.