18장: A-정규형과 조인 포인트
새 파일
src/erase.rssrc/anf.rssrc/anf_simplify.rssrc/anf_machine.rssrc/anf_lint.rs변경된 파일
src/lib.rssrc/main.rs
동기
f (g x) (h y)를 생각해 봅시다. 이것을 실행하려면 함수와 인자들을 올바른 순서로 평가하고, h y를 계산하는 동안 g x의 결과를 보관해 두었다가, 마지막으로 호출을 수행해야 합니다. 지금까지는 우리 인터프리터가 이런 장부 정리를 대신 해 주었습니다. 코드 생성기는 그 단계들을 직접 볼 수 있어야 합니다.
흔히 ANF로 줄여 부르는 A-정규형은 이러한 중간 결과들을 이름 붙은 바인딩으로 적어 둡니다. 그러면 함수 호출과 다른 연산들은 중첩된 계산 대신 단순한 피연산자를 받게 됩니다. 쓸모 있는 지역 변수 몇 개를 도입하는 것에 불과한 일치고는 이름이 꽤 거창하게 들립니다.
이는 5장의 CEK 기계를 다시 불러오기에도 좋은 지점입니다. 이제 Fun의 데이터, 사전, IO, 조인 포인트를 모두 갖춘 ANF를 명시적인 컨티뉴에이션 스택으로 실행하겠습니다. 프로그램을 네이티브 코드에 맞게 준비하면서 그 결과를 Core와 비교할 수 있습니다.
현재의 언어
결과가 다른 계산에 쓰이는 case 식을 따라가 봅시다.
main = print (3 + (case Just 4 of { Just x -> x; Nothing -> 0 }))
어느 대안이 값을 반환하든, 프로그램은 3을 더하고 한 번 출력해야 합니다. ANF는 그 공통 컨티뉴에이션을 각 대안에 복사하는 대신 조인으로 명시합니다. 새로 추가된 --engine=anf는 반복적 기계를 선택하며 기본값입니다. --engine=core는 참조 인터프리터를 유지합니다.
--no-simplify는 선택적 재작성이 적용되기 전에 생성된 ANF를 보여 줍니다. 두 형태 모두 stdout, stderr의 첫 줄, 프로세스 상태를 보존해야 합니다. 특히 엄격한 평가에서는 쓰이지 않는 바인딩의 초기화식도 여전히 실행됩니다. 실패하는 나눗셈은 그 결과가 쓰이지 않는다는 이유만으로 사라질 수 없습니다.
이론
f (g x) (h y)에서 중요한 작업은 호출에 있습니다. 이름 자체는 값을 가리킬 뿐입니다. ANF는 이 구분을 구문의 일부로 만듭니다. 아톰은 리터럴이거나 사용 가능한 값에 대한 참조입니다. 우변은 아톰에 대해 연산 하나를 수행하고, Let은 그 결과에 이름을 붙입니다. 중첩된 평가가 명시적인 순서로 바뀐 것입니다(Flanagan et al. 1993).
변환은 결과를 어떻게 처리할지 기술하는 문맥을 받습니다. 함수의 끝에서는 아톰을 반환합니다. 식 내부에서는 아톰을 바인딩하고 계속 진행합니다. case 대안의 끝에서는 공유된 컨티뉴에이션으로 점프할 수 있습니다. 이 표현은 Maurer와 동료들이 논의한 조인 포인트의 동기를 따라 (Maurer et al. 2017), 조인을 지역적인 2급 클래스(second-class) 구성 요소로 유지합니다. 모든 함수를 컨티뉴에이션을 명시적으로 받는 함수로 바꾸지는 않습니다.
타입 소거가 정당화되는 근거는 System F의 타입 추상화와 타입 적용이 하는 역할에 있습니다. 이들은 계산을 선택하고 기술하지만 그 자체로 런타임 작업을 수행하지는 않습니다(Pierce 2002). 사전 인자는 다릅니다. 딕셔너리 인자는 실제 메서드 구현을 담고 있으므로 일반 값으로 남아 있어야 합니다. IO는 소거 이전에 이미 unit 함수 표현을 갖추고 있습니다.
꼬리 위치는 남은 작업의 속성입니다. 함수 호출이 현재 함수의 결과를 직접 제공한다면, 기계는 그 활성화를 위한 반환 프레임이 필요하지 않습니다. 꼬리 호출이 아닌 호출은 보류 중인 계산을 기억해야 합니다. 따라서 호스트 스택 사용량이 일정하다고 해서 모든 재귀 프로그램이 일정한 메모리를 사용한다는 뜻은 아닙니다. 그래도 대기 중인 비꼬리 작업 때문에 명시적인 컨티뉴에이션 스택이 커질 수는 있습니다. 이것이 CEK 컨티뉴에이션을 눈에 보이게 만드는 것의 실질적인 이점입니다 (Felleisen and Friedman 1986).
구현
erase::erase는 실행 가능한 타입 정보를 제거하면서 전역 초기화 순서를 보존합니다. 후위 순회 작업 목록은 TyLam과 TyApp을 버리고, 사전 항은 유지하며, 이전 패스에서 빠져나온 중첩된 Match가 있으면 거부합니다. 읽기 전용 생성자 메타데이터와 위치 메타데이터는 프리미티브, 프린터, 진단에서 계속 사용할 수 있습니다.
#![allow(unused)]
fn main() {
use crate::{ast::Op, core, data::ConId, names::Id, source::Span};
#[derive(Clone, Debug)]
/// Untyped Core retains strict evaluation order and lexical join points.
pub enum Expr {
Var(Id),
Global(Id),
Lit(core::Lit),
Lam(Id, Box<Expr>),
App(Box<Expr>, Box<Expr>),
Let(bool, Vec<(Id, Expr)>, Box<Expr>),
Con(ConId, Vec<Expr>),
Prim(Op, Vec<Expr>, Span),
Case(Box<Expr>, Id, Vec<(core::AltCon, Vec<Id>, Expr)>),
Join(Id, Vec<Id>, Box<Expr>, Box<Expr>),
Jump(Id, Vec<Expr>),
Fail(Span),
}
#[derive(Clone, Debug)]
/// Ordered globals and runtime constructor/location metadata.
pub struct Program {
pub globals: Vec<(Id, Expr)>,
pub metadata: core::Program,
}
/// Postorder erasure uses an explicit worklist, including long constructor spines.
fn expr(root: &core::Expr) -> Expr {
use core::Expr as C;
let mut todo = vec![(root, false)];
let mut results: Vec<Expr> = vec![];
while let Some((e, done)) = todo.pop() {
let children: Vec<&core::Expr> = match e {
C::Lam(_, e) | C::TyLam(_, e) | C::TyApp(e, _) => vec![e],
C::App(f, a) => vec![f, a],
C::Let(g, b) => g
.binds
.iter()
.map(|b| b.rhs.as_ref())
.chain(std::iter::once(b.as_ref()))
.collect(),
C::Con(_, _, es) | C::Prim(_, _, es, _) | C::Jump(_, es, _) => {
es.iter().collect()
}
C::Case(e, _, _, alts) => std::iter::once(e.as_ref())
.chain(alts.iter().map(|a| &a.rhs))
.collect(),
C::Join(_, _, b, r) => vec![b, r],
C::Match(_) => panic!("match compilation precedes erasure"),
_ => vec![],
};
if !done {
todo.push((e, true));
todo.extend(children.into_iter().rev().map(|c| (c, false)));
continue;
}
let start = results.len() - children.len();
let mut parts = results.split_off(start).into_iter();
let result = match e {
C::Var(i) => Expr::Var(i.name.clone()),
C::Global(i) => Expr::Global(i.name.clone()),
C::Lit(l) => Expr::Lit(l.clone()),
C::TyLam(..) | C::TyApp(..) => parts.next().unwrap(),
C::Lam(i, _) => {
Expr::Lam(i.name.clone(), Box::new(parts.next().unwrap()))
}
C::App(..) => Expr::App(
Box::new(parts.next().unwrap()),
Box::new(parts.next().unwrap()),
),
C::Let(g, _) => {
let bs = g
.binds
.iter()
.map(|b| (b.name.name.clone(), parts.next().unwrap()))
.collect();
Expr::Let(g.recursive, bs, Box::new(parts.next().unwrap()))
}
C::Con(c, _, _) => Expr::Con(c.clone(), parts.collect()),
C::Prim(p, _, _, s) => Expr::Prim(*p, parts.collect(), *s),
C::Case(_, i, _, alts) => {
let e = parts.next().unwrap();
let alts = alts
.iter()
.map(|a| {
(
a.con.clone(),
a.binders
.iter()
.map(|i| i.name.clone())
.collect(),
parts.next().unwrap(),
)
})
.collect();
Expr::Case(Box::new(e), i.name.clone(), alts)
}
C::Join(j, ps, _, _) => Expr::Join(
j.clone(),
ps.iter().map(|i| i.name.clone()).collect(),
Box::new(parts.next().unwrap()),
Box::new(parts.next().unwrap()),
),
C::Jump(j, _, _) => Expr::Jump(j.clone(), parts.collect()),
C::PatternFail(s, _) => Expr::Fail(*s),
C::Match(_) => {
unreachable!("match compilation precedes erasure")
}
};
results.push(result);
}
results.pop().unwrap()
}
/// Compact syntax uses an explicit print stack and bounded indentation. Debug's
/// indentation grows with depth and makes even a linear tree quadratic in bytes.
impl std::fmt::Display for Expr {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
enum Work<'a> {
Expr(&'a Expr),
Text(String),
}
let mut todo = vec![Work::Expr(self)];
while let Some(work) = todo.pop() {
match work {
Work::Text(s) => write!(f, "{s}")?,
Work::Expr(e) => {
let mut parts = vec![];
match e {
Expr::Var(v) => write!(f, "{v}")?,
Expr::Global(v) => write!(f, "@{v}")?,
Expr::Lit(l) => write!(f, "{l}")?,
Expr::Lam(v, b) => {
write!(f, "(lambda {v}. ")?;
parts.push(Work::Expr(b));
parts.push(Work::Text(")".into()));
}
Expr::App(a, b) => {
write!(f, "(")?;
parts.extend([
Work::Expr(a),
Work::Text(" ".into()),
Work::Expr(b),
Work::Text(")".into()),
]);
}
Expr::Con(c, es) => {
write!(f, "({}", c.name)?;
for e in es {
parts.push(Work::Text(" ".into()));
parts.push(Work::Expr(e));
}
parts.push(Work::Text(")".into()));
}
Expr::Prim(p, es, _) => {
write!(f, "({}", p.text())?;
for e in es {
parts.push(Work::Text(" ".into()));
parts.push(Work::Expr(e));
}
parts.push(Work::Text(")".into()));
}
Expr::Jump(j, es) => {
write!(f, "(jump {j}")?;
for e in es {
parts.push(Work::Text(" ".into()));
parts.push(Work::Expr(e));
}
parts.push(Work::Text(")".into()));
}
Expr::Let(rec, bs, b) => {
write!(
f,
"(let{} ",
if *rec { "rec" } else { "" }
)?;
for (v, e) in bs {
parts.push(Work::Text(format!("{v} = ")));
parts.push(Work::Expr(e));
parts.push(Work::Text(";\n".into()));
}
parts.extend([
Work::Text("in ".into()),
Work::Expr(b),
Work::Text(")".into()),
]);
}
Expr::Case(e, v, alts) => {
write!(f, "(case ")?;
parts.extend([
Work::Expr(e),
Work::Text(format!(" as {v} {{\n")),
]);
for (c, ps, e) in alts {
let c = match c {
core::AltCon::Con(c) => c.name.clone(),
core::AltCon::Lit(l) => l.to_string(),
core::AltCon::Default => "_".into(),
};
parts.push(Work::Text(c));
for p in ps {
parts.push(Work::Text(format!(" {p}")));
}
parts.extend([
Work::Text(" -> ".into()),
Work::Expr(e),
Work::Text(";\n".into()),
]);
}
parts.push(Work::Text("})".into()));
}
Expr::Join(j, ps, b, r) => {
write!(f, "(join {j}")?;
for p in ps {
write!(f, " {p}")?;
}
write!(f, " = ")?;
parts.extend([
Work::Expr(b),
Work::Text("\nin ".into()),
Work::Expr(r),
Work::Text(")".into()),
]);
}
Expr::Fail(s) => write!(f, "fail {s:?}")?,
}
todo.extend(parts.into_iter().rev());
}
}
}
Ok(())
}
}
/// Destroy an owned erased tree without recursively following Box edges.
pub fn discard(root: Expr) {
let mut todo = vec![root];
while let Some(e) = todo.pop() {
match e {
Expr::Lam(_, b) => todo.push(*b),
Expr::App(a, b) | Expr::Join(_, _, a, b) => {
todo.push(*a);
todo.push(*b);
}
Expr::Let(_, bs, b) => {
todo.push(*b);
todo.extend(bs.into_iter().map(|(_, e)| e));
}
Expr::Con(_, es) | Expr::Prim(_, es, _) | Expr::Jump(_, es) => {
todo.extend(es)
}
Expr::Case(e, _, alts) => {
todo.push(*e);
todo.extend(alts.into_iter().map(|(_, _, e)| e));
}
_ => {}
}
}
}
/// Erase executable types only; read-only metadata supports diagnostics and printers.
pub fn erase(mut program: core::Program) -> Program {
let globals = program
.groups
.iter()
.flat_map(|g| &g.binds)
.map(|b| (b.name.name.clone(), expr(&b.rhs)))
.collect();
// Consuming Core must not recursively destroy its nested expressions.
let mut todo = program
.groups
.drain(..)
.flat_map(|g| g.binds.into_iter().map(|b| *b.rhs))
.collect::<Vec<_>>();
while let Some(e) = todo.pop() {
use core::Expr as C;
match e {
C::Lam(_, b) | C::TyLam(_, b) | C::TyApp(b, _) => todo.push(*b),
C::App(a, b) | C::Join(_, _, a, b) => {
todo.push(*a);
todo.push(*b);
}
C::Let(g, b) => {
todo.push(*b);
todo.extend(g.binds.into_iter().map(|b| *b.rhs));
}
C::Con(_, _, es) | C::Prim(_, _, es, _) | C::Jump(_, es, _) => {
todo.extend(es)
}
C::Case(e, _, _, alts) => {
todo.push(*e);
todo.extend(alts.into_iter().map(|a| a.rhs));
}
C::Match(_) => {
unreachable!("match compilation precedes erasure")
}
_ => {}
}
}
Program {
globals,
metadata: program,
}
}
}ANF 문법
다음은 제어 언어를 기호 형태로 나타낸 것입니다. 아톰에는 를, 우변에는 를, 완전한 ANF 본문에는 를 사용합니다. 각 행은 아래의 Rust 변형 하나에 대응합니다.
윗줄(overbar)은 시퀀스를 뜻합니다. 이름 는 조인 포인트를 식별하고, 는 대안(alternative)의 생성자 태그, 리터럴, 또는 기본(default) 표시입니다. 생성자 대안은 자신의 필드를 에 바인딩합니다. 리터럴 대안과 기본 대안에는 필드 바인더가 없습니다.
더 작은 구성 요소들이 이름의 “정규형” 부분을 설명해 줍니다. 피연산자는 언제나 아톰이며, 아직 일어나지 않은 또 다른 호출인 경우는 결코 없습니다.
여기서 는 생성자를, 는 프리미티브를 가리킵니다. 문법에서는 프리미티브의 소스 스팬을 생략했습니다. Core의 람다와 달리 이 람다들은 여러 매개변수를 받을 수 있으며, 타입 추상화나 타입 적용은 더 이상 남아 있지 않습니다.
이제 일반 호출과 꼬리 호출의 차이가 구문에 드러납니다. 는 호출 뒤에 할 작업을 남겨 둡니다. 에는 그런 본문이 없습니다. 점프 역시 뒤따르는 본문이 없지만, 현재 함수 안에 머무르면서 지역 조인 포인트로 제어를 넘깁니다.
ANF 제어 언어는 일반 바인딩, 재귀 클로저, 분기, 조인, 종결 제어 이전(terminal transfer)을 서로 구분합니다. Fail은 패턴 실패의 소스 스팬을 보존합니다:
#![allow(unused)]
fn main() {
use crate::{
ast::Op,
core::{self, AltCon, Lit},
data::ConId,
erase,
names::Id,
session::Session,
source::Span,
};
use std::{collections::BTreeMap, rc::Rc};
/// An erased binder keeps its unique identity and diagnostic spelling.
pub type Var = Id;
/// Syntax is immutable and shared between closures and machine states.
pub type Body = Rc<Anf>;
#[derive(Clone, Debug, PartialEq, Eq)]
/// Atoms cannot perform work or fail when read from a well-scoped environment.
pub enum Atom {
Var(Var),
Global(Id),
Lit(Lit),
}
#[derive(Clone, Debug)]
/// Lambda parameters are merged only across syntactically adjacent lambdas.
pub struct Lambda {
pub params: Vec<Var>,
pub body: Body,
}
#[derive(Clone, Debug)]
/// One strict computation whose operands have already been evaluated.
pub enum Rhs {
Atom(Atom),
Call(Atom, Vec<Atom>),
Con(ConId, Vec<Atom>),
Prim(Op, Vec<Atom>, Span),
Lambda(Lambda),
Field(Atom, u32),
}
#[derive(Clone, Debug)]
/// Global initialization order is preserved from typed Core.
pub struct Program {
pub globals: Vec<(Id, Body)>,
pub metadata: core::Program,
}
#[derive(Clone)]
enum Context {
Return,
Jump(Id),
Bind(Var, Body),
}
struct Convert<'a> {
sess: &'a mut Session,
arities: BTreeMap<Id, usize>,
}
fn arity(mut e: &erase::Expr) -> usize {
let mut n = 0;
while let erase::Expr::Lam(_, b) = e {
n += 1;
e = b;
}
n
}
fn collect(e: &erase::Expr, out: &mut BTreeMap<Id, usize>) {
use erase::Expr as E;
let mut todo = vec![e];
while let Some(e) = todo.pop() {
match e {
E::Let(_, bs, b) => {
for (v, e) in bs {
let n = arity(e);
if n > 0 {
out.insert(v.clone(), n);
}
todo.push(e);
}
todo.push(b);
}
E::Lam(_, b) => todo.push(b),
E::App(a, b) | E::Join(_, _, a, b) => {
todo.push(a);
todo.push(b);
}
E::Con(_, es) | E::Prim(_, es, _) | E::Jump(_, es) => {
todo.extend(es)
}
E::Case(e, _, alts) => {
todo.push(e);
todo.extend(alts.iter().map(|(_, _, e)| e));
}
_ => {}
}
}
}
impl Convert<'_> {
fn fresh(&mut self) -> Var {
self.sess.fresh_id("$a")
}
fn finish(&mut self, a: Atom, k: Context) -> Body {
Rc::new(match k {
Context::Return => Anf::Ret(a),
Context::Jump(j) => Anf::Jump(j, vec![a]),
Context::Bind(v, b) => Anf::Let(v, Rhs::Atom(a), b),
})
}
fn rhs(&mut self, r: Rhs, k: Context) -> Body {
if let Context::Bind(v, b) = k {
return Rc::new(Anf::Let(v, r, b));
}
if let (Rhs::Call(f, args), Context::Return) = (&r, &k) {
return Rc::new(Anf::TailCall(f.clone(), args.clone()));
}
let v = self.fresh();
let rest = self.finish(Atom::Var(v.clone()), k);
Rc::new(Anf::Let(v, r, rest))
}
/// Tasks hold pending compiler work. Neither expression depth nor the
/// number of operands adds a Rust call frame.
fn expr(&mut self, e: erase::Expr, k: Context) -> Body {
use erase::Expr as E;
enum Work {
Expr(erase::Expr, Context),
Bindings(Vec<(Var, erase::Expr)>),
Lambda(Vec<Var>, Context),
Rec(Vec<(Var, Vec<Var>)>),
Case(
erase::Expr,
Var,
Vec<(AltCon, Vec<Var>)>,
Option<(Id, Var, Body)>,
),
Join(Id, Vec<Var>, Option<(Id, Var, Body)>),
Call(erase::Expr, Var, Vec<erase::Expr>, Var),
}
fn peel(mut e: erase::Expr) -> (Vec<Var>, erase::Expr) {
let mut ps = vec![];
while let E::Lam(v, b) = e {
ps.push(v);
e = *b;
}
(ps, e)
}
fn branch(
k: Context,
sess: &mut Session,
) -> (Context, Option<(Id, Var, Body)>) {
match k {
Context::Bind(v, b) => {
let j = sess.fresh_id("$cont");
(Context::Jump(j.clone()), Some((j, v, b)))
}
k => (k, None),
}
}
fn wrap(body: Body, cont: Option<(Id, Var, Body)>) -> Body {
match cont {
Some((j, v, b)) => Rc::new(Anf::Join(j, vec![v], b, body)),
None => body,
}
}
let mut todo = vec![Work::Expr(e, k)];
let mut results: Vec<Body> = vec![];
while let Some(work) = todo.pop() {
match work {
Work::Bindings(mut bs) => {
if let Some((v, e)) = bs.pop() {
let b = results.pop().unwrap();
todo.push(Work::Bindings(bs));
todo.push(Work::Expr(e, Context::Bind(v, b)));
}
}
Work::Lambda(params, k) => {
let body = results.pop().unwrap();
results.push(
self.rhs(Rhs::Lambda(Lambda { params, body }), k),
);
}
Work::Rec(bs) => {
let bodies =
results.split_off(results.len() - bs.len());
let rest = results.pop().unwrap();
let bs = bs
.into_iter()
.zip(bodies)
.map(|((v, params), body)| {
(v, Lambda { params, body })
})
.collect();
results.push(Rc::new(Anf::LetRec(bs, rest)));
}
Work::Case(e, v, heads, cont) => {
let bodies =
results.split_off(results.len() - heads.len());
let alts = heads
.into_iter()
.zip(bodies)
.map(|((c, ps), b)| (c, ps, b))
.collect();
let b = wrap(
Rc::new(Anf::Case(Atom::Var(v.clone()), alts)),
cont,
);
todo.push(Work::Expr(e, Context::Bind(v, b)));
}
Work::Join(j, ps, cont) => {
let rest = results.pop().unwrap();
let body = results.pop().unwrap();
results.push(wrap(
Rc::new(Anf::Join(j, ps, body, rest)),
cont,
));
}
Work::Call(head, f, args, result) => {
let rest = results.pop().unwrap();
let vars: Vec<_> =
args.iter().map(|_| self.fresh()).collect();
let atoms =
vars.iter().cloned().map(Atom::Var).collect();
let b = self.rhs(
Rhs::Call(Atom::Var(f.clone()), atoms),
Context::Bind(result, rest),
);
let bs = std::iter::once((f, head))
.chain(vars.into_iter().zip(args))
.collect();
results.push(b);
todo.push(Work::Bindings(bs));
}
Work::Expr(e, k) => {
match e {
E::Var(v) => {
results.push(self.finish(Atom::Var(v), k))
}
E::Global(v) => {
results.push(self.finish(Atom::Global(v), k))
}
E::Lit(l) => {
results.push(self.finish(Atom::Lit(l), k))
}
node @ E::Lam(..) => {
let (ps, body) = peel(node);
todo.push(Work::Lambda(ps, k));
todo.push(Work::Expr(body, Context::Return));
}
node @ E::App(..) => {
let mut head = node;
let mut args = vec![];
while let E::App(f, a) = head {
args.push(*a);
head = *f;
}
args.reverse();
let known = match &head {
E::Var(v) | E::Global(v) => {
self.arities.get(v).copied()
}
E::Lam(..) => Some(arity(&head)),
_ => None,
};
// Unknown calls execute before evaluating their next argument.
let n = known.unwrap_or(1).min(args.len());
let extra = args.split_off(n);
let f = self.fresh();
if extra.is_empty() {
let vars: Vec<_> = args
.iter()
.map(|_| self.fresh())
.collect();
let atoms = vars
.iter()
.cloned()
.map(Atom::Var)
.collect();
results.push(self.rhs(
Rhs::Call(Atom::Var(f.clone()), atoms),
k,
));
todo.push(Work::Bindings(
std::iter::once((f, head))
.chain(vars.into_iter().zip(args))
.collect(),
));
} else {
let result = self.fresh();
let application = extra.into_iter().fold(
E::Var(result.clone()),
|f, a| E::App(Box::new(f), Box::new(a)),
);
todo.push(Work::Call(
head, f, args, result,
));
todo.push(Work::Expr(application, k));
}
}
E::Let(rec, bs, b) => {
if rec {
let (heads, bodies): (Vec<_>, Vec<_>) = bs
.into_iter()
.map(|(v, e)| {
let (ps, e) = peel(e);
((v, ps), e)
})
.unzip();
todo.push(Work::Rec(heads));
todo.extend(bodies.into_iter().rev().map(
|e| Work::Expr(e, Context::Return),
));
} else {
todo.push(Work::Bindings(bs));
}
todo.push(Work::Expr(*b, k));
}
node @ (E::Con(..) | E::Prim(..) | E::Jump(..)) => {
let args = match &node {
E::Con(_, es)
| E::Prim(_, es, _)
| E::Jump(_, es) => es,
_ => unreachable!(),
};
let vars: Vec<_> =
args.iter().map(|_| self.fresh()).collect();
let atoms = vars
.iter()
.cloned()
.map(Atom::Var)
.collect();
let (args, body) = match node {
E::Con(c, es) => {
(es, self.rhs(Rhs::Con(c, atoms), k))
}
E::Prim(p, es, s) => (
es,
self.rhs(Rhs::Prim(p, atoms, s), k),
),
E::Jump(j, es) => {
(es, Rc::new(Anf::Jump(j, atoms)))
}
_ => unreachable!(),
};
results.push(body);
todo.push(Work::Bindings(
vars.into_iter().zip(args).collect(),
));
}
E::Case(e, v, alts) => {
let (k, cont) = branch(k, self.sess);
let (heads, bodies): (Vec<_>, Vec<_>) = alts
.into_iter()
.map(|(c, ps, b)| ((c, ps), b))
.unzip();
todo.push(Work::Case(*e, v, heads, cont));
todo.extend(
bodies
.into_iter()
.rev()
.map(|e| Work::Expr(e, k.clone())),
);
}
E::Join(j, ps, b, r) => {
let (k, cont) = branch(k, self.sess);
todo.push(Work::Join(j, ps, cont));
todo.push(Work::Expr(*r, k.clone()));
todo.push(Work::Expr(*b, k));
}
E::Fail(s) => results.push(Rc::new(Anf::Fail(s))),
}
}
}
}
assert_eq!(results.len(), 1);
results.pop().unwrap()
}
}
/// Normalize left-to-right, sharing every non-tail continuation exactly once.
pub fn convert(sess: &mut Session, program: erase::Program) -> Program {
let mut arities = BTreeMap::new();
for (v, e) in &program.globals {
if arity(e) > 0 {
arities.insert(v.clone(), arity(e));
}
collect(e, &mut arities);
}
let mut c = Convert { sess, arities };
let globals = program
.globals
.into_iter()
.map(|(v, e)| (v, c.expr(e, Context::Return)))
.collect();
Program {
globals,
metadata: program.metadata,
}
}
impl std::fmt::Display for Atom {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Var(v) => write!(f, "{v}"),
Self::Global(v) => write!(f, "@{v}"),
Self::Lit(l) => write!(f, "{l}"),
}
}
}
fn list<T: std::fmt::Display>(items: &[T]) -> String {
items
.iter()
.map(ToString::to_string)
.collect::<Vec<_>>()
.join(", ")
}
impl std::fmt::Display for Rhs {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Atom(a) => write!(f, "{a}"),
Self::Call(a, args) => write!(f, "call {a}({})", list(args)),
Self::Con(c, args) => write!(f, "{}({})", c.name, list(args)),
Self::Prim(p, args, _) => {
write!(f, "{}({})", p.text(), list(args))
}
Self::Lambda(l) => {
write!(f, "lambda ({}) {{ {} }}", list(&l.params), l.body)
}
Self::Field(a, i) => write!(f, "field {a}[{i}]"),
}
}
}
impl std::fmt::Display for Anf {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
enum Work<'a> {
Body(&'a Anf),
Rhs(&'a Rhs),
Text(String),
}
let mut todo = vec![Work::Body(self)];
while let Some(work) = todo.pop() {
let mut parts = vec![];
match work {
Work::Text(s) => write!(f, "{s}")?,
Work::Rhs(Rhs::Lambda(l)) => {
write!(f, "lambda ({}) {{ ", list(&l.params))?;
parts.extend([
Work::Body(&l.body),
Work::Text(" }".into()),
]);
}
Work::Rhs(r) => write!(f, "{r}")?,
Work::Body(b) => match b {
Self::Let(v, r, b) => {
write!(f, "let {v} = ")?;
parts.extend([
Work::Rhs(r),
Work::Text(";\n".into()),
Work::Body(b),
]);
}
Self::LetRec(bs, b) => {
for (v, l) in bs {
parts.extend([
Work::Text(format!(
"rec {v}({}) = {{ ",
list(&l.params)
)),
Work::Body(&l.body),
Work::Text(" }\n".into()),
]);
}
parts.push(Work::Body(b));
}
Self::Join(j, ps, b, r) => {
write!(f, "join {j}({}) = {{ ", list(ps))?;
parts.extend([
Work::Body(b),
Work::Text(" };\n".into()),
Work::Body(r),
]);
}
Self::Jump(j, args) => {
write!(f, "jump {j}({})", list(args))?
}
Self::Case(a, alts) => {
writeln!(f, "case {a} {{")?;
for (c, ps, b) in alts {
let head = match c {
AltCon::Con(c) => c.name.clone(),
AltCon::Lit(l) => l.to_string(),
AltCon::Default => "_".into(),
};
parts.extend([
Work::Text(format!(
"{head}({}) -> {{ ",
list(ps)
)),
Work::Body(b),
Work::Text(" }\n".into()),
]);
}
parts.push(Work::Text("}".into()));
}
Self::Ret(a) => write!(f, "return {a}")?,
Self::TailCall(fun, args) => {
write!(f, "tail {fun}({})", list(args))?
}
Self::Fail(s) => write!(f, "fail {s:?}")?,
},
}
todo.extend(parts.into_iter().rev());
}
Ok(())
}
}
/// Drain child edges explicitly when the last owner releases a deep ANF tree.
impl Drop for Anf {
fn drop(&mut self) {
fn edges(node: &mut Anf, todo: &mut Vec<Body>) {
fn take(b: &mut Body) -> Body {
std::mem::replace(
b,
Rc::new(Anf::Ret(Atom::Lit(Lit::Int(0)))),
)
}
match node {
Anf::Let(_, r, b) => {
todo.push(take(b));
if let Rhs::Lambda(l) = r {
todo.push(take(&mut l.body));
}
}
Anf::LetRec(bs, b) => {
todo.push(take(b));
todo.extend(bs.drain(..).map(|(_, l)| l.body));
}
Anf::Join(_, _, b, r) => {
todo.push(take(b));
todo.push(take(r));
}
Anf::Case(_, alts) => {
todo.extend(alts.drain(..).map(|(_, _, b)| b))
}
_ => {}
}
}
let mut todo = vec![];
edges(self, &mut todo);
while let Some(b) = todo.pop() {
if let Ok(mut node) = Rc::try_unwrap(b) {
edges(&mut node, &mut todo);
// Empty this node before Drop runs again on the local variable.
// Its remaining children are only leaf placeholders.
}
}
}
}
#[derive(Clone, Debug)]
/// Jumps transfer within a function; tail calls replace its activation.
pub enum Anf {
Let(Var, Rhs, Body),
LetRec(Vec<(Var, Lambda)>, Body),
Join(Id, Vec<Var>, Body, Body),
Jump(Id, Vec<Atom>),
Case(Atom, Vec<(AltCon, Vec<Var>, Body)>),
Ret(Atom),
TailCall(Atom, Vec<Atom>),
Fail(Span),
}
}변환기의 컨텍스트에는 세 가지 경우만 있습니다. finish는 결과가 아톰이 된 뒤에 컨텍스트를 해석합니다. 대기 중인 변환은 작업 벡터에 들어 있으므로, 긴 식이 길게 이어지는 Rust 호출 사슬이 되지 않습니다:
#![allow(unused)]
fn main() {
use crate::{
ast::Op,
core::{self, AltCon, Lit},
data::ConId,
erase,
names::Id,
session::Session,
source::Span,
};
use std::{collections::BTreeMap, rc::Rc};
/// An erased binder keeps its unique identity and diagnostic spelling.
pub type Var = Id;
/// Syntax is immutable and shared between closures and machine states.
pub type Body = Rc<Anf>;
#[derive(Clone, Debug, PartialEq, Eq)]
/// Atoms cannot perform work or fail when read from a well-scoped environment.
pub enum Atom {
Var(Var),
Global(Id),
Lit(Lit),
}
#[derive(Clone, Debug)]
/// Lambda parameters are merged only across syntactically adjacent lambdas.
pub struct Lambda {
pub params: Vec<Var>,
pub body: Body,
}
#[derive(Clone, Debug)]
/// One strict computation whose operands have already been evaluated.
pub enum Rhs {
Atom(Atom),
Call(Atom, Vec<Atom>),
Con(ConId, Vec<Atom>),
Prim(Op, Vec<Atom>, Span),
Lambda(Lambda),
Field(Atom, u32),
}
#[derive(Clone, Debug)]
/// Jumps transfer within a function; tail calls replace its activation.
pub enum Anf {
Let(Var, Rhs, Body),
LetRec(Vec<(Var, Lambda)>, Body),
Join(Id, Vec<Var>, Body, Body),
Jump(Id, Vec<Atom>),
Case(Atom, Vec<(AltCon, Vec<Var>, Body)>),
Ret(Atom),
TailCall(Atom, Vec<Atom>),
Fail(Span),
}
#[derive(Clone, Debug)]
/// Global initialization order is preserved from typed Core.
pub struct Program {
pub globals: Vec<(Id, Body)>,
pub metadata: core::Program,
}
struct Convert<'a> {
sess: &'a mut Session,
arities: BTreeMap<Id, usize>,
}
fn arity(mut e: &erase::Expr) -> usize {
let mut n = 0;
while let erase::Expr::Lam(_, b) = e {
n += 1;
e = b;
}
n
}
fn collect(e: &erase::Expr, out: &mut BTreeMap<Id, usize>) {
use erase::Expr as E;
let mut todo = vec![e];
while let Some(e) = todo.pop() {
match e {
E::Let(_, bs, b) => {
for (v, e) in bs {
let n = arity(e);
if n > 0 {
out.insert(v.clone(), n);
}
todo.push(e);
}
todo.push(b);
}
E::Lam(_, b) => todo.push(b),
E::App(a, b) | E::Join(_, _, a, b) => {
todo.push(a);
todo.push(b);
}
E::Con(_, es) | E::Prim(_, es, _) | E::Jump(_, es) => {
todo.extend(es)
}
E::Case(e, _, alts) => {
todo.push(e);
todo.extend(alts.iter().map(|(_, _, e)| e));
}
_ => {}
}
}
}
impl Convert<'_> {
fn fresh(&mut self) -> Var {
self.sess.fresh_id("$a")
}
fn finish(&mut self, a: Atom, k: Context) -> Body {
Rc::new(match k {
Context::Return => Anf::Ret(a),
Context::Jump(j) => Anf::Jump(j, vec![a]),
Context::Bind(v, b) => Anf::Let(v, Rhs::Atom(a), b),
})
}
fn rhs(&mut self, r: Rhs, k: Context) -> Body {
if let Context::Bind(v, b) = k {
return Rc::new(Anf::Let(v, r, b));
}
if let (Rhs::Call(f, args), Context::Return) = (&r, &k) {
return Rc::new(Anf::TailCall(f.clone(), args.clone()));
}
let v = self.fresh();
let rest = self.finish(Atom::Var(v.clone()), k);
Rc::new(Anf::Let(v, r, rest))
}
/// Tasks hold pending compiler work. Neither expression depth nor the
/// number of operands adds a Rust call frame.
fn expr(&mut self, e: erase::Expr, k: Context) -> Body {
use erase::Expr as E;
enum Work {
Expr(erase::Expr, Context),
Bindings(Vec<(Var, erase::Expr)>),
Lambda(Vec<Var>, Context),
Rec(Vec<(Var, Vec<Var>)>),
Case(
erase::Expr,
Var,
Vec<(AltCon, Vec<Var>)>,
Option<(Id, Var, Body)>,
),
Join(Id, Vec<Var>, Option<(Id, Var, Body)>),
Call(erase::Expr, Var, Vec<erase::Expr>, Var),
}
fn peel(mut e: erase::Expr) -> (Vec<Var>, erase::Expr) {
let mut ps = vec![];
while let E::Lam(v, b) = e {
ps.push(v);
e = *b;
}
(ps, e)
}
fn branch(
k: Context,
sess: &mut Session,
) -> (Context, Option<(Id, Var, Body)>) {
match k {
Context::Bind(v, b) => {
let j = sess.fresh_id("$cont");
(Context::Jump(j.clone()), Some((j, v, b)))
}
k => (k, None),
}
}
fn wrap(body: Body, cont: Option<(Id, Var, Body)>) -> Body {
match cont {
Some((j, v, b)) => Rc::new(Anf::Join(j, vec![v], b, body)),
None => body,
}
}
let mut todo = vec![Work::Expr(e, k)];
let mut results: Vec<Body> = vec![];
while let Some(work) = todo.pop() {
match work {
Work::Bindings(mut bs) => {
if let Some((v, e)) = bs.pop() {
let b = results.pop().unwrap();
todo.push(Work::Bindings(bs));
todo.push(Work::Expr(e, Context::Bind(v, b)));
}
}
Work::Lambda(params, k) => {
let body = results.pop().unwrap();
results.push(
self.rhs(Rhs::Lambda(Lambda { params, body }), k),
);
}
Work::Rec(bs) => {
let bodies =
results.split_off(results.len() - bs.len());
let rest = results.pop().unwrap();
let bs = bs
.into_iter()
.zip(bodies)
.map(|((v, params), body)| {
(v, Lambda { params, body })
})
.collect();
results.push(Rc::new(Anf::LetRec(bs, rest)));
}
Work::Case(e, v, heads, cont) => {
let bodies =
results.split_off(results.len() - heads.len());
let alts = heads
.into_iter()
.zip(bodies)
.map(|((c, ps), b)| (c, ps, b))
.collect();
let b = wrap(
Rc::new(Anf::Case(Atom::Var(v.clone()), alts)),
cont,
);
todo.push(Work::Expr(e, Context::Bind(v, b)));
}
Work::Join(j, ps, cont) => {
let rest = results.pop().unwrap();
let body = results.pop().unwrap();
results.push(wrap(
Rc::new(Anf::Join(j, ps, body, rest)),
cont,
));
}
Work::Call(head, f, args, result) => {
let rest = results.pop().unwrap();
let vars: Vec<_> =
args.iter().map(|_| self.fresh()).collect();
let atoms =
vars.iter().cloned().map(Atom::Var).collect();
let b = self.rhs(
Rhs::Call(Atom::Var(f.clone()), atoms),
Context::Bind(result, rest),
);
let bs = std::iter::once((f, head))
.chain(vars.into_iter().zip(args))
.collect();
results.push(b);
todo.push(Work::Bindings(bs));
}
Work::Expr(e, k) => {
match e {
E::Var(v) => {
results.push(self.finish(Atom::Var(v), k))
}
E::Global(v) => {
results.push(self.finish(Atom::Global(v), k))
}
E::Lit(l) => {
results.push(self.finish(Atom::Lit(l), k))
}
node @ E::Lam(..) => {
let (ps, body) = peel(node);
todo.push(Work::Lambda(ps, k));
todo.push(Work::Expr(body, Context::Return));
}
node @ E::App(..) => {
let mut head = node;
let mut args = vec![];
while let E::App(f, a) = head {
args.push(*a);
head = *f;
}
args.reverse();
let known = match &head {
E::Var(v) | E::Global(v) => {
self.arities.get(v).copied()
}
E::Lam(..) => Some(arity(&head)),
_ => None,
};
// Unknown calls execute before evaluating their next argument.
let n = known.unwrap_or(1).min(args.len());
let extra = args.split_off(n);
let f = self.fresh();
if extra.is_empty() {
let vars: Vec<_> = args
.iter()
.map(|_| self.fresh())
.collect();
let atoms = vars
.iter()
.cloned()
.map(Atom::Var)
.collect();
results.push(self.rhs(
Rhs::Call(Atom::Var(f.clone()), atoms),
k,
));
todo.push(Work::Bindings(
std::iter::once((f, head))
.chain(vars.into_iter().zip(args))
.collect(),
));
} else {
let result = self.fresh();
let application = extra.into_iter().fold(
E::Var(result.clone()),
|f, a| E::App(Box::new(f), Box::new(a)),
);
todo.push(Work::Call(
head, f, args, result,
));
todo.push(Work::Expr(application, k));
}
}
E::Let(rec, bs, b) => {
if rec {
let (heads, bodies): (Vec<_>, Vec<_>) = bs
.into_iter()
.map(|(v, e)| {
let (ps, e) = peel(e);
((v, ps), e)
})
.unzip();
todo.push(Work::Rec(heads));
todo.extend(bodies.into_iter().rev().map(
|e| Work::Expr(e, Context::Return),
));
} else {
todo.push(Work::Bindings(bs));
}
todo.push(Work::Expr(*b, k));
}
node @ (E::Con(..) | E::Prim(..) | E::Jump(..)) => {
let args = match &node {
E::Con(_, es)
| E::Prim(_, es, _)
| E::Jump(_, es) => es,
_ => unreachable!(),
};
let vars: Vec<_> =
args.iter().map(|_| self.fresh()).collect();
let atoms = vars
.iter()
.cloned()
.map(Atom::Var)
.collect();
let (args, body) = match node {
E::Con(c, es) => {
(es, self.rhs(Rhs::Con(c, atoms), k))
}
E::Prim(p, es, s) => (
es,
self.rhs(Rhs::Prim(p, atoms, s), k),
),
E::Jump(j, es) => {
(es, Rc::new(Anf::Jump(j, atoms)))
}
_ => unreachable!(),
};
results.push(body);
todo.push(Work::Bindings(
vars.into_iter().zip(args).collect(),
));
}
E::Case(e, v, alts) => {
let (k, cont) = branch(k, self.sess);
let (heads, bodies): (Vec<_>, Vec<_>) = alts
.into_iter()
.map(|(c, ps, b)| ((c, ps), b))
.unzip();
todo.push(Work::Case(*e, v, heads, cont));
todo.extend(
bodies
.into_iter()
.rev()
.map(|e| Work::Expr(e, k.clone())),
);
}
E::Join(j, ps, b, r) => {
let (k, cont) = branch(k, self.sess);
todo.push(Work::Join(j, ps, cont));
todo.push(Work::Expr(*r, k.clone()));
todo.push(Work::Expr(*b, k));
}
E::Fail(s) => results.push(Rc::new(Anf::Fail(s))),
}
}
}
}
assert_eq!(results.len(), 1);
results.pop().unwrap()
}
}
/// Normalize left-to-right, sharing every non-tail continuation exactly once.
pub fn convert(sess: &mut Session, program: erase::Program) -> Program {
let mut arities = BTreeMap::new();
for (v, e) in &program.globals {
if arity(e) > 0 {
arities.insert(v.clone(), arity(e));
}
collect(e, &mut arities);
}
let mut c = Convert { sess, arities };
let globals = program
.globals
.into_iter()
.map(|(v, e)| (v, c.expr(e, Context::Return)))
.collect();
Program {
globals,
metadata: program.metadata,
}
}
impl std::fmt::Display for Atom {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Var(v) => write!(f, "{v}"),
Self::Global(v) => write!(f, "@{v}"),
Self::Lit(l) => write!(f, "{l}"),
}
}
}
fn list<T: std::fmt::Display>(items: &[T]) -> String {
items
.iter()
.map(ToString::to_string)
.collect::<Vec<_>>()
.join(", ")
}
impl std::fmt::Display for Rhs {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Atom(a) => write!(f, "{a}"),
Self::Call(a, args) => write!(f, "call {a}({})", list(args)),
Self::Con(c, args) => write!(f, "{}({})", c.name, list(args)),
Self::Prim(p, args, _) => {
write!(f, "{}({})", p.text(), list(args))
}
Self::Lambda(l) => {
write!(f, "lambda ({}) {{ {} }}", list(&l.params), l.body)
}
Self::Field(a, i) => write!(f, "field {a}[{i}]"),
}
}
}
impl std::fmt::Display for Anf {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
enum Work<'a> {
Body(&'a Anf),
Rhs(&'a Rhs),
Text(String),
}
let mut todo = vec![Work::Body(self)];
while let Some(work) = todo.pop() {
let mut parts = vec![];
match work {
Work::Text(s) => write!(f, "{s}")?,
Work::Rhs(Rhs::Lambda(l)) => {
write!(f, "lambda ({}) {{ ", list(&l.params))?;
parts.extend([
Work::Body(&l.body),
Work::Text(" }".into()),
]);
}
Work::Rhs(r) => write!(f, "{r}")?,
Work::Body(b) => match b {
Self::Let(v, r, b) => {
write!(f, "let {v} = ")?;
parts.extend([
Work::Rhs(r),
Work::Text(";\n".into()),
Work::Body(b),
]);
}
Self::LetRec(bs, b) => {
for (v, l) in bs {
parts.extend([
Work::Text(format!(
"rec {v}({}) = {{ ",
list(&l.params)
)),
Work::Body(&l.body),
Work::Text(" }\n".into()),
]);
}
parts.push(Work::Body(b));
}
Self::Join(j, ps, b, r) => {
write!(f, "join {j}({}) = {{ ", list(ps))?;
parts.extend([
Work::Body(b),
Work::Text(" };\n".into()),
Work::Body(r),
]);
}
Self::Jump(j, args) => {
write!(f, "jump {j}({})", list(args))?
}
Self::Case(a, alts) => {
writeln!(f, "case {a} {{")?;
for (c, ps, b) in alts {
let head = match c {
AltCon::Con(c) => c.name.clone(),
AltCon::Lit(l) => l.to_string(),
AltCon::Default => "_".into(),
};
parts.extend([
Work::Text(format!(
"{head}({}) -> {{ ",
list(ps)
)),
Work::Body(b),
Work::Text(" }\n".into()),
]);
}
parts.push(Work::Text("}".into()));
}
Self::Ret(a) => write!(f, "return {a}")?,
Self::TailCall(fun, args) => {
write!(f, "tail {fun}({})", list(args))?
}
Self::Fail(s) => write!(f, "fail {s:?}")?,
},
}
todo.extend(parts.into_iter().rev());
}
Ok(())
}
}
/// Drain child edges explicitly when the last owner releases a deep ANF tree.
impl Drop for Anf {
fn drop(&mut self) {
fn edges(node: &mut Anf, todo: &mut Vec<Body>) {
fn take(b: &mut Body) -> Body {
std::mem::replace(
b,
Rc::new(Anf::Ret(Atom::Lit(Lit::Int(0)))),
)
}
match node {
Anf::Let(_, r, b) => {
todo.push(take(b));
if let Rhs::Lambda(l) = r {
todo.push(take(&mut l.body));
}
}
Anf::LetRec(bs, b) => {
todo.push(take(b));
todo.extend(bs.drain(..).map(|(_, l)| l.body));
}
Anf::Join(_, _, b, r) => {
todo.push(take(b));
todo.push(take(r));
}
Anf::Case(_, alts) => {
todo.extend(alts.drain(..).map(|(_, _, b)| b))
}
_ => {}
}
}
let mut todo = vec![];
edges(self, &mut todo);
while let Some(b) = todo.pop() {
if let Ok(mut node) = Rc::try_unwrap(b) {
edges(&mut node, &mut todo);
// Empty this node before Drop runs again on the local variable.
// Its remaining children are only leaf placeholders.
}
}
}
}
#[derive(Clone)]
enum Context {
Return,
Jump(Id),
Bind(Var, Body),
}
fn finish(&mut self, a: Atom, k: Context) -> Body {
Rc::new(match k {
Context::Return => Anf::Ret(a),
Context::Jump(j) => Anf::Jump(j, vec![a]),
Context::Bind(v, b) => Anf::Let(v, Rhs::Atom(a), b),
})
}
}꼬리 위치가 아닌 case에서는 변환 과정이 나머지 컨텍스트에 새 조인 매개변수를 부여하고, 각 대안을 점프 컨텍스트로 변환합니다. 기존 Core 조인은 그대로 유지됩니다. 인접한 람다들은 하나의 다중 매개변수 람다로 합쳐집니다. 이것은 구문적 항수이며, 함수 타입에서 추론한 항수가 아닙니다.
적용 변환은 커리된 호출의 순서를 지켜야 합니다. f a b에서 호출 f a는 b가 평가되기 전에 실패할 수 있습니다. 두 인자를 하나의 즉시 평가 묶음으로 합치면 어떤 오류가 먼저 나타나는지가 바뀝니다. 변환기는 알려진 구문적 항수까지만 인자를 묶습니다. 알려지지 않은 호출은 인자를 한 번에 하나씩 소비하고, 과적용은 알려진 접두부 뒤의 경계를 보존합니다. known-prefix-error 회귀 테스트가 이 순서를 명시적으로 검사합니다.
anf_simplify는 아톰을 전파하고, 생성자가 알려진 분기를 선택하며, 사용되지 않는 전역적(total) 우변을 제거하고, 즉시 적용되는 포화(saturated) 람다를 축약합니다. 호출, 효과, 그리고 실패할 수 있는 프리미티브는 유지됩니다. 베타 규칙은 함수가 탈출하는지도 검사합니다. 물려받은 id id 예제처럼 함수를 자기 자신에게 넘기면, 그 바인딩을 그냥 삭제할 수 없습니다. 구조적 ANF 린트는 실행 전에 이름, 스코프, 조인 항수, 새 바인더를 독립적으로 검사합니다.
이 머신은 코드, 적용, 반환 상태를 도는 루프입니다. 기계의 프레임은 비꼬리 바인딩 컨티뉴에이션이나 과포화 호출 뒤에 남은 인자를 기억합니다:
#![allow(unused)]
fn main() {
use crate::{
anf::{self, Anf, Atom, Body, Lambda, Rhs, Var},
ast::Op,
core::{AltCon, Lit},
data::ConId,
eval::Failure,
};
use std::{collections::BTreeMap, rc::Rc};
type Env = crate::env::Env<u32, Value>;
type Joins = BTreeMap<u32, Rc<Join>>;
#[derive(Clone, Debug)]
/// Strict data, lexical closures, and partial applications.
pub enum Value {
Lit(Lit),
Con(ConId, Rc<Vec<Value>>, Option<Vec<String>>),
Closure(Rc<Closure>),
Pap(Rc<Value>, Vec<Value>),
}
impl Drop for Value {
fn drop(&mut self) {
fn children(value: &mut Value, todo: &mut Vec<Value>) {
match value {
Value::Con(_, fields, _) => {
if !fields.is_empty()
&& let Ok(values) = Rc::try_unwrap(
std::mem::replace(fields, Rc::new(vec![])),
)
{
todo.extend(values);
}
}
Value::Pap(base, args) => {
todo.append(args);
if let Some(value) = Rc::get_mut(base) {
todo.push(std::mem::replace(
value,
Value::Lit(Lit::Int(0)),
));
}
}
Value::Closure(c) => {
if let Some(c) = Rc::get_mut(c)
&& let Some(env) = Rc::get_mut(&mut c.env)
{
env.drain_unique(todo);
}
}
_ => {}
}
}
let mut todo = vec![];
children(self, &mut todo);
while let Some(mut value) = todo.pop() {
children(&mut value, &mut todo);
}
}
}
#[derive(Clone, Debug)]
/// Recursive groups are shared by index, avoiding reference-count cycles.
pub struct Closure {
lambda: Lambda,
env: Rc<Env>,
recursive: Option<usize>,
}
#[derive(Clone)]
struct Join {
params: Vec<Var>,
body: Body,
env: Env,
joins: Joins,
}
enum Frame {
Bind(Var, Body, Env, Joins),
Apply(Vec<Value>),
}
#[derive(Clone, Copy, Debug, Default)]
/// Continuation depth counts pending non-tail calls, not recursive tail transfers.
pub struct Stats {
pub steps: usize,
pub max_continuations: usize,
}
struct Machine<'a> {
groups: Vec<Env>,
program: &'a anf::Program,
globals: Env,
env: Env,
joins: Joins,
stack: Vec<Frame>,
fuel: usize,
stats: Stats,
}
fn key(v: &Var) -> u32 {
v.name.unique
}
fn closure(
lambda: Lambda,
env: Rc<Env>,
recursive: Option<usize>,
) -> Value {
Value::Closure(Rc::new(Closure {
lambda,
env,
recursive,
}))
}
fn function(body: &Body) -> Option<Lambda> {
if let Anf::Let(v, Rhs::Lambda(l), b) = body.as_ref()
&& matches!(b.as_ref(),Anf::Ret(Atom::Var(w)) if v==w)
{
Some(l.clone())
} else {
None
}
}
impl Machine<'_> {
fn atom(&self, a: &Atom) -> Result<Value, Failure> {
match a {
Atom::Lit(l) => Ok(Value::Lit(l.clone())),
Atom::Var(v) => {
self.env.get(&key(v)).cloned().ok_or_else(|| {
format!("internal error: unbound ANF variable {v}")
.into()
})
}
Atom::Global(v) => {
self.globals.get(&key(v)).cloned().ok_or_else(|| {
format!("internal error: uninitialized ANF global {v}")
.into()
})
}
}
}
fn atoms(&self, args: &[Atom]) -> Result<Vec<Value>, Failure> {
args.iter().map(|a| self.atom(a)).collect()
}
fn rhs(&self, r: &Rhs) -> Result<Value, Failure> {
match r {
Rhs::Atom(a) => self.atom(a),
Rhs::Con(c, args) => Ok(Value::Con(
c.clone(),
Rc::new(self.atoms(args)?),
self.program.metadata.constructors[c.index as usize]
.labels
.clone(),
)),
Rhs::Lambda(l) => {
Ok(closure(l.clone(), Rc::new(self.env.clone()), None))
}
Rhs::Field(a, i) => match &self.atom(a)? {
Value::Con(_, fields, _) => {
fields.get(*i as usize).cloned().ok_or_else(|| {
"internal error: invalid field index".into()
})
}
_ => Err("internal error: field on non-constructor".into()),
},
Rhs::Prim(op, args, _) => {
let p = match op {
Op::Runtime(p) => *p,
Op::Add => crate::primitives::Prim::IntAdd,
Op::Sub => crate::primitives::Prim::IntSub,
Op::Mul => crate::primitives::Prim::IntMul,
Op::Div => crate::primitives::Prim::IntDiv,
Op::Mod => crate::primitives::Prim::IntMod,
Op::Eq => crate::primitives::Prim::IntEq,
Op::Lt => crate::primitives::Prim::IntLt,
Op::Le => crate::primitives::Prim::IntLe,
Op::Append => crate::primitives::Prim::StrAppend,
};
let values = self.atoms(args)?;
let args = values
.iter()
.map(to_core)
.collect::<Result<Vec<_>, _>>()?;
crate::primitives::evaluate(
p,
&args,
&self.program.metadata,
)
.map(from_core)
}
Rhs::Call(..) => unreachable!("calls are machine transitions"),
}
}
fn run(&mut self, mut state: State) -> Result<Value, Failure> {
loop {
if self.fuel == 0 {
return Err("step limit exceeded".into());
}
self.fuel -= 1;
self.stats.steps += 1;
self.stats.max_continuations =
self.stats.max_continuations.max(self.stack.len());
state = match state {
State::Code(body) => match body.as_ref() {
Anf::Ret(a) => State::Return(self.atom(a)?),
Anf::TailCall(f, args) => {
State::Apply(self.atom(f)?, self.atoms(args)?)
}
Anf::Let(v, Rhs::Call(f, args), rest) => {
let f = self.atom(f)?;
let args = self.atoms(args)?;
self.stack.push(Frame::Bind(
v.clone(),
rest.clone(),
std::mem::take(&mut self.env),
std::mem::take(&mut self.joins),
));
State::Apply(f, args)
}
Anf::Let(v, r, rest) => {
let value = self.rhs(r)?;
self.env.insert(key(v), value);
State::Code(rest.clone())
}
Anf::LetRec(bindings, rest) => {
let index = self.groups.len();
let env = Rc::new(self.env.clone());
for (v, l) in bindings {
self.env.insert(
key(v),
closure(
l.clone(),
env.clone(),
Some(index),
),
);
}
self.groups.push(self.env.clone());
State::Code(rest.clone())
}
Anf::Join(j, params, body, rest) => {
let join = Join {
params: params.clone(),
body: body.clone(),
env: self.env.clone(),
joins: self.joins.clone(),
};
self.joins.insert(key(j), Rc::new(join));
State::Code(rest.clone())
}
Anf::Jump(j, args) => {
let values = self.atoms(args)?;
let join =
self.joins.get(&key(j)).cloned().ok_or(
"internal error: unbound ANF join",
)?;
if values.len() != join.params.len() {
return Err(
"internal error: ANF jump arity".into()
);
}
self.env = join.env.clone();
self.joins = join.joins.clone();
self.env.extend(
join.params.iter().map(key).zip(values),
);
State::Code(join.body.clone())
}
Anf::Case(a, alts) => {
let value = self.atom(a)?;
let mut chosen = None;
for (c, ps, b) in alts {
let fields = match (c, &value) {
(AltCon::Default, _) => Some(vec![]),
(
AltCon::Con(c),
Value::Con(d, fields, _),
) if c == d => Some((**fields).clone()),
(AltCon::Lit(a), Value::Lit(b))
if a == b =>
{
Some(vec![])
}
_ => None,
};
if let Some(fields) = fields {
self.env
.extend(ps.iter().map(key).zip(fields));
chosen = Some(b.clone());
break;
}
}
State::Code(chosen.ok_or(
"internal error: ANF case has no alternative",
)?)
}
Anf::Fail(span) => {
let site = self
.program
.metadata
.locations
.iter()
.find(|(s, _)| s == span)
.map(|(_, s)| s.as_str())
.unwrap_or("<unknown>:1:1");
return Err(format!(
"pattern match failure at {site}"
)
.into());
}
},
State::Apply(f, args) => match &f {
Value::Pap(base, earlier) => {
let mut earlier = earlier.clone();
earlier.extend(args);
State::Apply((**base).clone(), earlier)
}
Value::Closure(c) => {
let arity = c.lambda.params.len();
if args.len() < arity {
State::Return(Value::Pap(
Rc::new(Value::Closure(c.clone())),
args,
))
} else {
let mut args = args;
let extra = args.split_off(arity);
if !extra.is_empty() {
self.stack.push(Frame::Apply(extra));
}
self.env = (*c.env).clone();
self.joins.clear();
if let Some(index) = c.recursive {
self.env = self.groups[index].clone();
}
self.env.extend(
c.lambda.params.iter().map(key).zip(args),
);
State::Code(c.lambda.body.clone())
}
}
_ => {
return Err(
"internal error: application of non-function"
.into(),
);
}
},
State::Return(value) => match self.stack.pop() {
None => return Ok(value),
Some(Frame::Apply(args)) => State::Apply(value, args),
Some(Frame::Bind(v, b, mut env, joins)) => {
env.insert(key(&v), value);
self.env = env;
self.joins = joins;
State::Code(b)
}
},
};
}
}
}
/// Independent control flow, with shared monomorphic primitive definitions.
pub fn run(
program: &anf::Program,
fuel: usize,
io: bool,
) -> Result<(Value, Stats), Failure> {
let mut m = Machine {
groups: vec![],
program,
globals: Env::new(),
env: Env::new(),
joins: Joins::new(),
stack: vec![],
fuel,
stats: Stats::default(),
};
for (v, b) in &program.globals {
if let Some(l) = function(b) {
m.globals
.insert(key(v), closure(l, Rc::new(Env::new()), None));
}
}
for (v, b) in &program.globals {
if function(b).is_none() {
m.env.clear();
m.joins.clear();
let value = m.run(State::Code(b.clone()))?;
m.globals.insert(key(v), value);
}
}
let main = m
.globals
.get(&program.metadata.main.unique())
.cloned()
.ok_or("internal error: missing main")?;
let value = if io {
let unit = program
.metadata
.constructors
.iter()
.find(|c| c.id.name == "()")
.ok_or("internal error: missing unit")?;
m.run(State::Apply(
main,
vec![Value::Con(unit.id.clone(), Rc::new(vec![]), None)],
))?
} else {
main
};
Ok((value, m.stats))
}
fn to_core(v: &Value) -> Result<crate::eval::Value, Failure> {
Ok(match v {
Value::Lit(l) => crate::eval::Value::Lit(l.clone()),
Value::Con(c, fields, labels) => crate::eval::Value::Con(
c.clone(),
Rc::new(fields.iter().map(to_core).collect::<Result<_, _>>()?),
labels.clone(),
),
_ => {
return Err(
"internal error: function passed to a data primitive"
.into(),
);
}
})
}
fn from_core(v: crate::eval::Value) -> Value {
match &v {
crate::eval::Value::Lit(l) => Value::Lit(l.clone()),
crate::eval::Value::Con(c, fields, labels) => Value::Con(
c.clone(),
Rc::new(fields.iter().cloned().map(from_core).collect()),
labels.clone(),
),
_ => unreachable!("primitive cannot return a closure"),
}
}
impl std::fmt::Display for Value {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
self.print(f, 0)
}
}
impl Value {
fn print(
&self,
f: &mut std::fmt::Formatter<'_>,
precedence: u8,
) -> std::fmt::Result {
match self {
Self::Lit(Lit::Double(n))
if f64::from_bits(*n).is_sign_negative()
&& precedence > 6 =>
{
write!(
f,
"({})",
crate::primitives::show_double(f64::from_bits(*n))
)
}
Self::Lit(Lit::Int(n)) if *n < 0 && precedence > 6 => {
write!(f, "({n})")
}
Self::Lit(l) => write!(f, "{l}"),
Self::Closure(_) | Self::Pap(..) => write!(f, "<function>"),
Self::Con(id, fields, Some(labels)) => {
if precedence > 10 {
write!(f, "(")?;
}
write!(f, "{} {{", id.name)?;
for (i, (name, value)) in
labels.iter().zip(fields.iter()).enumerate()
{
if i > 0 {
write!(f, ", ")?;
}
write!(f, "{name} = ")?;
value.print(f, 0)?;
}
write!(f, "}}")?;
if precedence > 10 {
write!(f, ")")?;
}
Ok(())
}
Self::Con(id, fields, None) => match id.name.as_str() {
"[]" => write!(f, "[]"),
":" => {
write!(f, "[")?;
let mut value = self;
let mut first = true;
while let Self::Con(c, fs, _) = value {
if c.name == "[]" {
break;
}
if !first {
write!(f, ",")?;
}
first = false;
fs[0].print(f, 0)?;
value = &fs[1];
}
write!(f, "]")
}
"()" | "(,)" | "(,,)" => {
write!(f, "(")?;
for (i, v) in fields.iter().enumerate() {
if i > 0 {
write!(f, ",")?;
}
v.print(f, 0)?;
}
write!(f, ")")
}
_ => {
let parens = precedence > 10 && !fields.is_empty();
if parens {
write!(f, "(")?;
}
write!(f, "{}", id.name)?;
for v in fields.iter() {
write!(f, " ")?;
v.print(f, 11)?;
}
if parens {
write!(f, ")")?;
}
Ok(())
}
},
}
}
}
enum State {
Code(Body),
Apply(Value, Vec<Value>),
Return(Value),
}
use crate::{
anf::{self, Anf, Atom, Body, Lambda, Rhs, Var},
ast::Op,
core::{AltCon, Lit},
data::ConId,
eval::Failure,
};
use std::{collections::BTreeMap, rc::Rc};
type Env = crate::env::Env<u32, Value>;
type Joins = BTreeMap<u32, Rc<Join>>;
#[derive(Clone, Debug)]
/// Strict data, lexical closures, and partial applications.
pub enum Value {
Lit(Lit),
Con(ConId, Rc<Vec<Value>>, Option<Vec<String>>),
Closure(Rc<Closure>),
Pap(Rc<Value>, Vec<Value>),
}
impl Drop for Value {
fn drop(&mut self) {
fn children(value: &mut Value, todo: &mut Vec<Value>) {
match value {
Value::Con(_, fields, _) => {
if !fields.is_empty()
&& let Ok(values) = Rc::try_unwrap(
std::mem::replace(fields, Rc::new(vec![])),
)
{
todo.extend(values);
}
}
Value::Pap(base, args) => {
todo.append(args);
if let Some(value) = Rc::get_mut(base) {
todo.push(std::mem::replace(
value,
Value::Lit(Lit::Int(0)),
));
}
}
Value::Closure(c) => {
if let Some(c) = Rc::get_mut(c)
&& let Some(env) = Rc::get_mut(&mut c.env)
{
env.drain_unique(todo);
}
}
_ => {}
}
}
let mut todo = vec![];
children(self, &mut todo);
while let Some(mut value) = todo.pop() {
children(&mut value, &mut todo);
}
}
}
#[derive(Clone, Debug)]
/// Recursive groups are shared by index, avoiding reference-count cycles.
pub struct Closure {
lambda: Lambda,
env: Rc<Env>,
recursive: Option<usize>,
}
#[derive(Clone)]
struct Join {
params: Vec<Var>,
body: Body,
env: Env,
joins: Joins,
}
enum State {
Code(Body),
Apply(Value, Vec<Value>),
Return(Value),
}
#[derive(Clone, Copy, Debug, Default)]
/// Continuation depth counts pending non-tail calls, not recursive tail transfers.
pub struct Stats {
pub steps: usize,
pub max_continuations: usize,
}
struct Machine<'a> {
groups: Vec<Env>,
program: &'a anf::Program,
globals: Env,
env: Env,
joins: Joins,
stack: Vec<Frame>,
fuel: usize,
stats: Stats,
}
fn key(v: &Var) -> u32 {
v.name.unique
}
fn closure(
lambda: Lambda,
env: Rc<Env>,
recursive: Option<usize>,
) -> Value {
Value::Closure(Rc::new(Closure {
lambda,
env,
recursive,
}))
}
fn function(body: &Body) -> Option<Lambda> {
if let Anf::Let(v, Rhs::Lambda(l), b) = body.as_ref()
&& matches!(b.as_ref(),Anf::Ret(Atom::Var(w)) if v==w)
{
Some(l.clone())
} else {
None
}
}
impl Machine<'_> {
fn atom(&self, a: &Atom) -> Result<Value, Failure> {
match a {
Atom::Lit(l) => Ok(Value::Lit(l.clone())),
Atom::Var(v) => {
self.env.get(&key(v)).cloned().ok_or_else(|| {
format!("internal error: unbound ANF variable {v}")
.into()
})
}
Atom::Global(v) => {
self.globals.get(&key(v)).cloned().ok_or_else(|| {
format!("internal error: uninitialized ANF global {v}")
.into()
})
}
}
}
fn atoms(&self, args: &[Atom]) -> Result<Vec<Value>, Failure> {
args.iter().map(|a| self.atom(a)).collect()
}
fn rhs(&self, r: &Rhs) -> Result<Value, Failure> {
match r {
Rhs::Atom(a) => self.atom(a),
Rhs::Con(c, args) => Ok(Value::Con(
c.clone(),
Rc::new(self.atoms(args)?),
self.program.metadata.constructors[c.index as usize]
.labels
.clone(),
)),
Rhs::Lambda(l) => {
Ok(closure(l.clone(), Rc::new(self.env.clone()), None))
}
Rhs::Field(a, i) => match &self.atom(a)? {
Value::Con(_, fields, _) => {
fields.get(*i as usize).cloned().ok_or_else(|| {
"internal error: invalid field index".into()
})
}
_ => Err("internal error: field on non-constructor".into()),
},
Rhs::Prim(op, args, _) => {
let p = match op {
Op::Runtime(p) => *p,
Op::Add => crate::primitives::Prim::IntAdd,
Op::Sub => crate::primitives::Prim::IntSub,
Op::Mul => crate::primitives::Prim::IntMul,
Op::Div => crate::primitives::Prim::IntDiv,
Op::Mod => crate::primitives::Prim::IntMod,
Op::Eq => crate::primitives::Prim::IntEq,
Op::Lt => crate::primitives::Prim::IntLt,
Op::Le => crate::primitives::Prim::IntLe,
Op::Append => crate::primitives::Prim::StrAppend,
};
let values = self.atoms(args)?;
let args = values
.iter()
.map(to_core)
.collect::<Result<Vec<_>, _>>()?;
crate::primitives::evaluate(
p,
&args,
&self.program.metadata,
)
.map(from_core)
}
Rhs::Call(..) => unreachable!("calls are machine transitions"),
}
}
fn run(&mut self, mut state: State) -> Result<Value, Failure> {
loop {
if self.fuel == 0 {
return Err("step limit exceeded".into());
}
self.fuel -= 1;
self.stats.steps += 1;
self.stats.max_continuations =
self.stats.max_continuations.max(self.stack.len());
state = match state {
State::Code(body) => match body.as_ref() {
Anf::Ret(a) => State::Return(self.atom(a)?),
Anf::TailCall(f, args) => {
State::Apply(self.atom(f)?, self.atoms(args)?)
}
Anf::Let(v, Rhs::Call(f, args), rest) => {
let f = self.atom(f)?;
let args = self.atoms(args)?;
self.stack.push(Frame::Bind(
v.clone(),
rest.clone(),
std::mem::take(&mut self.env),
std::mem::take(&mut self.joins),
));
State::Apply(f, args)
}
Anf::Let(v, r, rest) => {
let value = self.rhs(r)?;
self.env.insert(key(v), value);
State::Code(rest.clone())
}
Anf::LetRec(bindings, rest) => {
let index = self.groups.len();
let env = Rc::new(self.env.clone());
for (v, l) in bindings {
self.env.insert(
key(v),
closure(
l.clone(),
env.clone(),
Some(index),
),
);
}
self.groups.push(self.env.clone());
State::Code(rest.clone())
}
Anf::Join(j, params, body, rest) => {
let join = Join {
params: params.clone(),
body: body.clone(),
env: self.env.clone(),
joins: self.joins.clone(),
};
self.joins.insert(key(j), Rc::new(join));
State::Code(rest.clone())
}
Anf::Jump(j, args) => {
let values = self.atoms(args)?;
let join =
self.joins.get(&key(j)).cloned().ok_or(
"internal error: unbound ANF join",
)?;
if values.len() != join.params.len() {
return Err(
"internal error: ANF jump arity".into()
);
}
self.env = join.env.clone();
self.joins = join.joins.clone();
self.env.extend(
join.params.iter().map(key).zip(values),
);
State::Code(join.body.clone())
}
Anf::Case(a, alts) => {
let value = self.atom(a)?;
let mut chosen = None;
for (c, ps, b) in alts {
let fields = match (c, &value) {
(AltCon::Default, _) => Some(vec![]),
(
AltCon::Con(c),
Value::Con(d, fields, _),
) if c == d => Some((**fields).clone()),
(AltCon::Lit(a), Value::Lit(b))
if a == b =>
{
Some(vec![])
}
_ => None,
};
if let Some(fields) = fields {
self.env
.extend(ps.iter().map(key).zip(fields));
chosen = Some(b.clone());
break;
}
}
State::Code(chosen.ok_or(
"internal error: ANF case has no alternative",
)?)
}
Anf::Fail(span) => {
let site = self
.program
.metadata
.locations
.iter()
.find(|(s, _)| s == span)
.map(|(_, s)| s.as_str())
.unwrap_or("<unknown>:1:1");
return Err(format!(
"pattern match failure at {site}"
)
.into());
}
},
State::Apply(f, args) => match &f {
Value::Pap(base, earlier) => {
let mut earlier = earlier.clone();
earlier.extend(args);
State::Apply((**base).clone(), earlier)
}
Value::Closure(c) => {
let arity = c.lambda.params.len();
if args.len() < arity {
State::Return(Value::Pap(
Rc::new(Value::Closure(c.clone())),
args,
))
} else {
let mut args = args;
let extra = args.split_off(arity);
if !extra.is_empty() {
self.stack.push(Frame::Apply(extra));
}
self.env = (*c.env).clone();
self.joins.clear();
if let Some(index) = c.recursive {
self.env = self.groups[index].clone();
}
self.env.extend(
c.lambda.params.iter().map(key).zip(args),
);
State::Code(c.lambda.body.clone())
}
}
_ => {
return Err(
"internal error: application of non-function"
.into(),
);
}
},
State::Return(value) => match self.stack.pop() {
None => return Ok(value),
Some(Frame::Apply(args)) => State::Apply(value, args),
Some(Frame::Bind(v, b, mut env, joins)) => {
env.insert(key(&v), value);
self.env = env;
self.joins = joins;
State::Code(b)
}
},
};
}
}
}
/// Independent control flow, with shared monomorphic primitive definitions.
pub fn run(
program: &anf::Program,
fuel: usize,
io: bool,
) -> Result<(Value, Stats), Failure> {
let mut m = Machine {
groups: vec![],
program,
globals: Env::new(),
env: Env::new(),
joins: Joins::new(),
stack: vec![],
fuel,
stats: Stats::default(),
};
for (v, b) in &program.globals {
if let Some(l) = function(b) {
m.globals
.insert(key(v), closure(l, Rc::new(Env::new()), None));
}
}
for (v, b) in &program.globals {
if function(b).is_none() {
m.env.clear();
m.joins.clear();
let value = m.run(State::Code(b.clone()))?;
m.globals.insert(key(v), value);
}
}
let main = m
.globals
.get(&program.metadata.main.unique())
.cloned()
.ok_or("internal error: missing main")?;
let value = if io {
let unit = program
.metadata
.constructors
.iter()
.find(|c| c.id.name == "()")
.ok_or("internal error: missing unit")?;
m.run(State::Apply(
main,
vec![Value::Con(unit.id.clone(), Rc::new(vec![]), None)],
))?
} else {
main
};
Ok((value, m.stats))
}
fn to_core(v: &Value) -> Result<crate::eval::Value, Failure> {
Ok(match v {
Value::Lit(l) => crate::eval::Value::Lit(l.clone()),
Value::Con(c, fields, labels) => crate::eval::Value::Con(
c.clone(),
Rc::new(fields.iter().map(to_core).collect::<Result<_, _>>()?),
labels.clone(),
),
_ => {
return Err(
"internal error: function passed to a data primitive"
.into(),
);
}
})
}
fn from_core(v: crate::eval::Value) -> Value {
match &v {
crate::eval::Value::Lit(l) => Value::Lit(l.clone()),
crate::eval::Value::Con(c, fields, labels) => Value::Con(
c.clone(),
Rc::new(fields.iter().cloned().map(from_core).collect()),
labels.clone(),
),
_ => unreachable!("primitive cannot return a closure"),
}
}
impl std::fmt::Display for Value {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
self.print(f, 0)
}
}
impl Value {
fn print(
&self,
f: &mut std::fmt::Formatter<'_>,
precedence: u8,
) -> std::fmt::Result {
match self {
Self::Lit(Lit::Double(n))
if f64::from_bits(*n).is_sign_negative()
&& precedence > 6 =>
{
write!(
f,
"({})",
crate::primitives::show_double(f64::from_bits(*n))
)
}
Self::Lit(Lit::Int(n)) if *n < 0 && precedence > 6 => {
write!(f, "({n})")
}
Self::Lit(l) => write!(f, "{l}"),
Self::Closure(_) | Self::Pap(..) => write!(f, "<function>"),
Self::Con(id, fields, Some(labels)) => {
if precedence > 10 {
write!(f, "(")?;
}
write!(f, "{} {{", id.name)?;
for (i, (name, value)) in
labels.iter().zip(fields.iter()).enumerate()
{
if i > 0 {
write!(f, ", ")?;
}
write!(f, "{name} = ")?;
value.print(f, 0)?;
}
write!(f, "}}")?;
if precedence > 10 {
write!(f, ")")?;
}
Ok(())
}
Self::Con(id, fields, None) => match id.name.as_str() {
"[]" => write!(f, "[]"),
":" => {
write!(f, "[")?;
let mut value = self;
let mut first = true;
while let Self::Con(c, fs, _) = value {
if c.name == "[]" {
break;
}
if !first {
write!(f, ",")?;
}
first = false;
fs[0].print(f, 0)?;
value = &fs[1];
}
write!(f, "]")
}
"()" | "(,)" | "(,,)" => {
write!(f, "(")?;
for (i, v) in fields.iter().enumerate() {
if i > 0 {
write!(f, ",")?;
}
v.print(f, 0)?;
}
write!(f, ")")
}
_ => {
let parens = precedence > 10 && !fields.is_empty();
if parens {
write!(f, "(")?;
}
write!(f, "{}", id.name)?;
for v in fields.iter() {
write!(f, " ")?;
v.print(f, 11)?;
}
if parens {
write!(f, ")")?;
}
Ok(())
}
},
}
}
}
enum Frame {
Bind(Var, Body, Env, Joins),
Apply(Vec<Value>),
}
}클로저는 람다 하나와 공유되는 렉시컬 환경을 담습니다. 재귀 그룹은 머신이 소유한 테이블에 한 번만 만들어집니다. 그 클로저들은 그룹의 인덱스를 보유하므로, 참조 카운트 순환이 생기지 않고 호출할 때마다 클로저를 다시 만들 필요도 없습니다. 인자를 너무 적게 적용하면 부분 적용이 반환됩니다. 남는 인자는 반환된 함수에 적용됩니다. 꼬리 호출은 현재 상태를 대체하고, 점프는 렉시컬하게 캡처된 조인 환경으로 진입합니다. 두 전이 모두 Rust 인터프리터를 재귀적으로 호출하지 않습니다. 원시 값은 데이터만 다루는 어댑터를 거쳐 기존 원시 연산 구현으로 넘어갑니다. 제어 흐름은 Core 평가기를 호출하지 않습니다.
실행해 보기
$ cd crates/ch18_anf
$ cargo run -q -- run tests/programs/anf/case-continuation.fun --lint
7
$ cargo run -q -- dump --pass=types tests/programs/anf/case-continuation.fun
main : IO ()
타입이 지워진 Core를 보려면 --pass=erase를, 이름 붙은 연산을 보려면 --pass=anf를 사용하십시오. 변환과 재작성을 구분하려면 후자를 --no-simplify와 함께 다시 실행하십시오. 기준 결과와 비교하려면 --engine=core로 실행을 반복하십시오. 덤프에는 Prelude가 포함됩니다. tests/anf.rs의 작은 스냅숏들은 꼬리 위치가 아닌 case나 가드 실패 조인 같은 개별 변환을 따로 떼어 보여 줍니다.
손으로 작성한 예제와 함께, testkit/src/gen.rs는 산술, 지역 바인딩, 분기, 재귀, 리스트를 포함하는 작고 타입이 올바른 프로그램을 생성합니다. 두 엔진은 모두 독립적인 래핑 정수 계산 결과와 일치해야 합니다. 우리는 실패한 경우의 소스와 시드를 저장하여, 예상치 못한 답이 디버깅할 수 있는 프로그램이 되도록 합니다.
백만 번 호출하는 합계 계산은 머신의 제어 흐름을 시험하기에 유용합니다. 우리는 단지 끝나는지만 확인하는 대신, 대기 중인 컨티뉴에이션의 수를 측정합니다. 꼬리 호출은 현재 계산을 대체해야 합니다. 비꼬리 호출은 힙에 할당된 컨티뉴에이션 스택에 대기 중인 작업을 추가할 수 있습니다. 어느 쪽도 Rust 호출 프레임을 추가로 필요로 하지 않습니다. Core는 자체적인 명시적 기계를 사용하므로, 이를 ANF와 비교하면 변환이 답을 바꾸지 않았는지도 확인할 수 있습니다.
연습 문제
- 준비 운동. 단순화하지 않은 ANF 덤프에서 예제의 case 뒤에 오는 컨티뉴에이션을 찾으십시오.
- 중급. 두 인자가 서로 다른 메시지로 실패하도록 만들고, 알려진 호출과 알려지지 않은 호출에서 각각 어느 쪽이 먼저 실행되어야 하는지 확인하십시오.
- 중급. 정수 나눗셈에는 IO 효과가 없는데도 사용되지 않는 나눗셈을 제거하는 것이 왜 잘못일 수 있는지 설명하십시오.
- 고급. 꼬리 재귀 합계와 꼬리 재귀가 아닌 합계에 대해 머신에 계측 코드를 넣고 최대 컨티뉴에이션 깊이를 비교하십시오.
- 고급. 결정적 생성기에 타입이 올바른 새 구문 하나와 그에 대한 독립적인 기대 결과 계산을 추가하여 확장하십시오.
더 읽을거리
- 직접 표현과 컨티뉴에이션 기반 컴파일 (Flanagan et al. 1993).
- 조인 포인트와 공유 컨티뉴에이션 (Maurer et al. 2017).
- CEK 기계의 제어, 환경, 컨티뉴에이션 (Felleisen and Friedman 1986).
- 컨티뉴에이션 기반 컴파일러 구성 (Appel 1992).
- 다형성과 타입 소거 (Pierce 2002).