부록 C: 중간 표현
최종 컴파일러에는 실행 가능한 중간 언어가 세 가지 있습니다. 각 언어는 다음 패스가 짊어질 특정한 의무 하나를 덜어 줍니다. 이 정의들은 24장에서 가져온 것이므로 참조 문서와 구현이 함께 유지됩니다.
| 표현 | 명시적으로 드러내는 것 | 여전히 암묵적으로 남겨 두는 것 |
|---|---|---|
| System F Core | 타입, 사전, 생성자, 제어 흐름 | 평가 임시값과 클로저 환경 |
| ANF | 평가 순서, 중간 결과, 조인, 꼬리 호출 | 캡처된 변수와 적용 디스패치 |
| Flat | 끌어올려진 코드, 클로저 필드, 알려진 호출과 알려지지 않은 호출 | 물리적 저장소와 기계 명령어 |
타입이 있는 Core
값 식별자는 자신의 타입을 지닙니다. 타입 적용은 타입 추상화를 인스턴스화합니다. 사전 인자는 평범한 값 인자이므로 TyLam과 TyApp을 지워도 클래스 증거는 지워지지 않습니다.
#![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는 정교화된 Core에 속합니다. 매치 컴파일은 이를 제거하고 평탄한 Case 대안과 어휘적 Join/Jump를 남깁니다. 생성자와 프리미티브는 포화되어 있습니다. 점프는 완전히 적용되며 자신의 조인 스코프 안에서 꼬리 위치에만 나타납니다. 린트 패스는 소스 타입 검사기와 독립적으로 이러한 속성을 검사합니다.
#![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>,
}
}재귀 그룹은 함수를 담습니다. 비재귀 그룹의 우변은 의존성 순서대로 평가됩니다. Case 바인더는 이미 평가된 검사 대상에 이름을 붙입니다. 패턴 실패와 실패하는 프리미티브는 소스 위치를 보존합니다.
A-정규형
아톰은 스코프가 올바른 환경에서 읽을 때 효과를 수행하거나 실패할 수 없습니다. Let은 하나의 엄격한 계산에 이름을 붙입니다. 본문 타입은 Rc<Anf>이므로, 머신과 변환 작업 목록이 불변 구문을 공유할 수 있습니다.
#![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은 현재 컨티뉴에이션으로 돌아갑니다. TailCall은 현재 활성화를 대체합니다. Jump는 그 활성화 안에 머뭅니다. 꼬리 위치가 아닌 소스 case는 자신의 대안들을 나머지 계산을 나타내는 하나의 join으로 보냅니다. 반복적 ANF 머신은 이 구분을 이용해 재귀적인 Rust 호출 없이 깊은 꼬리 재귀를 실행합니다.
Flat IR
모든 람다는 끌어올려진 함수가 되었습니다. 람다가 값을 캡처하면 그 환경이 명시적으로 드러납니다. 함수 인덱스는 프로그램의 함수 테이블을 가리킵니다.
#![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),
}
}알려진 호출은 올바른 개수의 인자로 끌어올려진 함수를 지정합니다. 알려지지 않은 호출은 eval/apply를 사용하며, 이 방식은 인자 수가 정확한 호출, 부분 호출, 과포화 호출을 지원합니다. PatchClosure는 그룹의 모든 클로저를 할당한 뒤 재귀적 캡처를 초기화합니다. 이는 내부 연산이며, 소스 언어의 변경 원시 연산이 결코 아닙니다.
수치 증거와 저장소
23장은 검사된 Core 타입에서 유도한 작은 분류를 보존합니다:
#![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,
}
}이는 타입 증거이지 호출 규약이 아닙니다. 호출 결과와 매개변수는 그 증거가 Int나 Double을 가리키더라도 워드로 남습니다. LLVM의 지역 위치는 워드, 네이티브 숫자, 다시 읽어 들일 수 있는 루트를 구분합니다:
#![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>),
}
}복사 백엔드는 수집이 일어날 수 있는 지점 뒤에 Root를 다시 읽어 들입니다. 산술 연산은 어떤 경계에서 태깅이나 박싱이 필요해질 때까지 네이티브 숫자를 레지스터에 둘 수 있습니다. 런타임 ABI가 그 경계들을 명시합니다.