evaltrees 0.1.0

A simple term-rewriting interpreter that displays intermediate expressions.
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

use ast::{Decl, Expr, Literal, Op, Pattern, Type};
use typeck::typeck;

#[test]
fn map_map() {
    let decls = vec![
        Decl {
            name: "map".into(),
            args: vec![
                Pattern::Binding("f".into(), ()),
                Pattern::Literal(Literal::Nil, ()),
            ],
            body: Expr::Literal(Literal::Nil, ()),
            aux: (),
        },
        Decl {
            name: "map".into(),
            args: vec![
                Pattern::Binding("f".into(), ()),
                Pattern::Cons(
                    Box::new(Pattern::Binding("h".into(), ())),
                    Box::new(Pattern::Binding("t".into(), ())),
                    (),
                ),
            ],
            body: Expr::Op(
                Op::Cons,
                Box::new(Expr::Op(
                    Op::App,
                    Box::new(Expr::Variable("f".into(), ())),
                    Box::new(Expr::Variable("h".into(), ())),
                    (),
                )),
                Box::new(Expr::Op(
                    Op::App,
                    Box::new(Expr::Op(
                        Op::App,
                        Box::new(Expr::Variable("map".into(), ())),
                        Box::new(Expr::Variable("f".into(), ())),
                        (),
                    )),
                    Box::new(Expr::Variable("t".into(), ())),
                    (),
                )),
                (),
            ),
            aux: (),
        },
        Decl {
            name: "mapmap".into(),
            args: vec![],
            body: Expr::Op(
                Op::App,
                Box::new(Expr::Variable("map".into(), ())),
                Box::new(Expr::Variable("map".into(), ())),
                (),
            ),
            aux: (),
        },
    ];

    // 'a 'b. ('a -> 'b) -> 'a list -> 'b list
    let map_ty = Type::Forall(Box::new(Type::Forall(Box::new(Type::Func(
        Box::new(Type::Func(Box::new(Type::Var(1)), Box::new(Type::Var(0)))),
        Box::new(Type::Func(
            Box::new(Type::List(Box::new(Type::Var(1)))),
            Box::new(Type::List(Box::new(Type::Var(0)))),
        )),
    )))));

    let decls = typeck(decls, Vec::new()).unwrap();
    assert_eq!(
        decls.into_iter().map(|decl| decl.aux).collect::<Vec<_>>(),
        vec![
            map_ty.clone(),
            map_ty,
            // 'a 'b. ('a -> 'b) list -> ('a list -> 'b list) list
            Type::Forall(Box::new(Type::Forall(Box::new(Type::Func(
                Box::new(Type::List(Box::new(Type::Func(
                    Box::new(Type::Var(1)),
                    Box::new(Type::Var(0)),
                )))),
                Box::new(Type::List(Box::new(Type::Func(
                    Box::new(Type::List(Box::new(Type::Var(1)))),
                    Box::new(Type::List(Box::new(Type::Var(0)))),
                )))),
            ))))),
        ]
    );
}

#[test]
fn poly_id() {
    let decls = vec![
        Decl {
            name: "id".into(),
            args: vec![Pattern::Binding("x".into(), ())],
            body: Expr::Variable("x".into(), ()),
            aux: (),
        },
        Decl {
            name: "foo".into(),
            args: vec![],
            body: Expr::Op(
                Op::Cons,
                Box::new(Expr::Op(
                    Op::App,
                    Box::new(Expr::Variable("id".into(), ())),
                    Box::new(Expr::Literal(Literal::Int(1), ())),
                    (),
                )),
                Box::new(Expr::Op(
                    Op::App,
                    Box::new(Expr::Variable("id".into(), ())),
                    Box::new(Expr::Op(
                        Op::Cons,
                        Box::new(Expr::Literal(Literal::Int(2), ())),
                        Box::new(Expr::Literal(Literal::Nil, ())),
                        (),
                    )),
                    (),
                )),
                (),
            ),
            aux: (),
        },
    ];

    let decls = typeck(decls, Vec::new()).unwrap();
    assert_eq!(
        decls.into_iter().map(|decl| decl.aux).collect::<Vec<_>>(),
        vec![
            Type::Forall(Box::new(Type::Func(
                Box::new(Type::Var(0)),
                Box::new(Type::Var(0)),
            ))),
            Type::List(Box::new(Type::Int)),
        ]
    );
}