oftlisp-anf 0.1.3

An OftLisp backend using A-normal form.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

use either::{Either, Left, Right};
use gc::Gc;
use oftlisp::Value;
use oftlisp::ast::{Expr as AstExpr};
use oftlisp::gensym::gensym_prefix;

use types::{Context, Expr, Prim};

impl Context {
    fn convert(expr: Gc<AstExpr<Self>>) -> Either<Gc<Prim>, Gc<Expr>> {
        match *expr {
            AstExpr::Call(ref f, ref a) => Right({
                Self::convert_prim(f.clone(), |f| {
                    let mut a = a.clone();
                    a.reverse();
                    Self::convert_prims(a, |mut a| {
                        a.reverse();
                        Gc::new(Expr::Call(f, a))
                    })
                })
            }),
            AstExpr::Def(_, ref e) => {
                // The def is not in a lexical context, and thus is ignored.
                let nil = Gc::new(Prim::Lit(Gc::new(Value::Nil(()))));
                match Self::convert(e.clone()) {
                    Left(_) => Left(nil),
                    Right(expr) => Right({
                        let nil = Gc::new(Expr::Prim(nil));
                        Gc::new(Expr::Let(None, expr, nil))
                    }),
                }
            },
            AstExpr::If(ref c, ref t, ref e) => {
                Right(Self::convert_prim(c.clone(), |c| {
                    let t = Self::convert_expr(t.clone());
                    let e = Self::convert_expr(e.clone());
                    Gc::new(Expr::If(c, t, e))
                }))
            },
            AstExpr::Lambda(n, ref a, ref b, ref t) => {
                let t = Self::convert_expr(t.clone());
                let body = Self::convert_block(b.clone(), t);
                Left(Gc::new(Prim::Fn(n, a.clone(), body)))
            },  
            AstExpr::Literal(ref v) => Left(Gc::new(Prim::Lit(v.clone()))),
            AstExpr::Progn(ref exprs) => if exprs.len() == 0 {
                Left(Gc::new(Prim::Lit(Gc::new(Value::Nil(())))))
            } else {
                let mut body = exprs.clone();
                let tail = Self::convert_expr(body.pop().unwrap());
                Right(Self::convert_block(body, tail))
            },
            AstExpr::Variable(s) => Left(Gc::new(Prim::Var(s))),
            AstExpr::Vector(ref v) => {
                let mut v = v.clone();
                v.reverse();
                Right(Self::convert_prims(v, |mut v| {
                    v.reverse();
                    Gc::new(Expr::Prim(Gc::new(Prim::Vec(v))))
                }))
            },
        }
    }

    fn convert_block(mut body: Vec<Gc<AstExpr<Self>>>, tail: Gc<Expr>) -> Gc<Expr> {
        // TODO: Make this loopish.
        match body.pop() {
            Some(expr) => {
                let tail = if let AstExpr::Def(n, ref e) = *expr.clone() {
                    Expr::Let(Some(n), Self::convert_expr(e.clone()), tail)
                } else {
                    Expr::Let(None, Self::convert_expr(expr), tail)
                };
                Self::convert_block(body, Gc::new(tail))
            },
            None => tail,
        }
    }

    pub(crate) fn convert_expr(expr: Gc<AstExpr<Context>>) -> Gc<Expr> {
        match Self::convert(expr) {
            Left(prim) => Gc::new(Expr::Prim(prim)),
            Right(expr) => expr,
        }
    }

    fn convert_prim<F: FnOnce(Gc<Prim>) -> Gc<Expr>>(expr: Gc<AstExpr<Context>>, f: F) -> Gc<Expr> {
        match Self::convert(expr) {
            Left(prim) => f(prim),
            Right(expr) => {
                let name = gensym_prefix("anf");
                let next = f(Gc::new(Prim::Var(name)));
                Gc::new(Expr::Let(Some(name), expr, next))
            },
        }
    }

    fn convert_prims<F: FnOnce(Vec<Gc<Prim>>) -> Gc<Expr>>(exprs: Vec<Gc<AstExpr<Context>>>, f: F) -> Gc<Expr> {
        // TODO: I'm pretty sure this is more inefficient than it needs to be.
        let mut prims = Vec::new();
        let mut conts = Vec::new();
        for expr in exprs {
            match Self::convert(expr) {
                Left(prim) => prims.push(prim),
                Right(expr) => {
                    let name = gensym_prefix("anf");
                    prims.push(Gc::new(Prim::Var(name)));
                    conts.push(move |next| Gc::new(Expr::Let(Some(name), expr, next)))
                },
            }
        }
        let mut expr = f(prims);
        for cont in conts {
            expr = cont(expr);
        }
        expr
    }
}