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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358

use super::*;
use ast::Pattern;

#[test]
fn app() {
    let mut evaluator = CallByName::new(vec![
        Decl {
            name: "f".into(),
            args: vec![
                Pattern::Binding("x".into(), ()),
                Pattern::Binding("y".into(), ()),
            ],
            body: Expr::Op(
                Op::Add,
                Box::new(Expr::Variable("x".into(), ())),
                Box::new(Expr::Variable("y".into(), ())),
                (),
            ),
            aux: (),
        },
        Decl {
            name: "".into(),
            args: vec![],
            body: Expr::Op(
                Op::App,
                Box::new(Expr::Op(
                    Op::App,
                    Box::new(Expr::Variable("f".into(), ())),
                    Box::new(Expr::Op(
                        Op::Add,
                        Box::new(Expr::Literal(Literal::Int(1), ())),
                        Box::new(Expr::Literal(Literal::Int(2), ())),
                        (),
                    )),
                    (),
                )),
                Box::new(Expr::Op(
                    Op::Add,
                    Box::new(Expr::Literal(Literal::Int(3), ())),
                    Box::new(Expr::Literal(Literal::Int(4), ())),
                    (),
                )),
                (),
            ),
            aux: (),
        },
    ]);

    evaluator.step().unwrap();
    assert_eq!(
        format!("{}", evaluator),
        "App(App(f, Add(1, 2)), Add(3, 4))"
    );
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(format!("{}", evaluator), "Add(Add(1, 2), Add(3, 4))");
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(format!("{}", evaluator), "Add(3, Add(3, 4))");
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(format!("{}", evaluator), "Add(3, 7)");
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(format!("{}", evaluator), "10");
    assert!(evaluator.normal_form());
}

#[test]
fn id_int() {
    let mut evaluator = CallByName::new(vec![
        Decl {
            name: "f".into(),
            args: vec![Pattern::Literal(Literal::Int(0), ())],
            body: Expr::Literal(Literal::Int(0), ()),
            aux: (),
        },
        Decl {
            name: "f".into(),
            args: vec![Pattern::Binding("x".into(), ())],
            body: Expr::Op(
                Op::Add,
                Box::new(Expr::Literal(Literal::Int(1), ())),
                Box::new(Expr::Op(
                    Op::App,
                    Box::new(Expr::Variable("f".into(), ())),
                    Box::new(Expr::Op(
                        Op::Sub,
                        Box::new(Expr::Variable("x".into(), ())),
                        Box::new(Expr::Literal(Literal::Int(1), ())),
                        (),
                    )),
                    (),
                )),
                (),
            ),
            aux: (),
        },
        Decl {
            name: "".into(),
            args: vec![],
            body: Expr::Op(
                Op::App,
                Box::new(Expr::Variable("f".into(), ())),
                Box::new(Expr::Literal(Literal::Int(1), ())),
                (),
            ),
            aux: (),
        },
    ]);

    evaluator.step().unwrap();
    assert_eq!(format!("{}", evaluator), "App(f, 1)");
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(format!("{}", evaluator), "Add(1, App(f, Sub(1, 1)))");
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(format!("{}", evaluator), "Add(1, App(f, 0))");
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(format!("{}", evaluator), "Add(1, 0)");
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(format!("{}", evaluator), "1");
    assert!(evaluator.normal_form());
}

#[test]
fn infinite() {
    let mut evaluator = CallByName::new(vec![
        Decl {
            name: "ones".into(),
            args: vec![],
            body: Expr::Op(
                Op::Cons,
                Box::new(Expr::Literal(Literal::Int(1), ())),
                Box::new(Expr::Variable("ones".into(), ())),
                (),
            ),
            aux: (),
        },
        Decl {
            name: "take".into(),
            args: vec![
                Pattern::Literal(Literal::Int(0), ()),
                Pattern::Binding("l".into(), ()),
            ],
            body: Expr::Literal(Literal::Nil, ()),
            aux: (),
        },
        Decl {
            name: "take".into(),
            args: vec![
                Pattern::Binding("n".into(), ()),
                Pattern::Cons(
                    Box::new(Pattern::Binding("h".into(), ())),
                    Box::new(Pattern::Binding("t".into(), ())),
                    (),
                ),
            ],
            body: Expr::Op(
                Op::Cons,
                Box::new(Expr::Variable("h".into(), ())),
                Box::new(Expr::Op(
                    Op::App,
                    Box::new(Expr::Op(
                        Op::App,
                        Box::new(Expr::Variable("take".into(), ())),
                        Box::new(Expr::Op(
                            Op::Sub,
                            Box::new(Expr::Variable("n".into(), ())),
                            Box::new(Expr::Literal(Literal::Int(1), ())),
                            (),
                        )),
                        (),
                    )),
                    Box::new(Expr::Variable("t".into(), ())),
                    (),
                )),
                (),
            ),
            aux: (),
        },
        Decl {
            name: "".into(),
            args: vec![],
            body: Expr::Op(
                Op::App,
                Box::new(Expr::Op(
                    Op::App,
                    Box::new(Expr::Variable("take".into(), ())),
                    Box::new(Expr::Literal(Literal::Int(1), ())),
                    (),
                )),
                Box::new(Expr::Variable("ones".into(), ())),
                (),
            ),
            aux: (),
        },
    ]);

    evaluator.step().unwrap();
    assert_eq!(format!("{}", evaluator), "App(App(take, 1), ones)");
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(format!("{}", evaluator), "App(App(take, 1), Cons(1, ones))");
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(
        format!("{}", evaluator),
        "Cons(1, App(App(take, Sub(1, 1)), ones))"
    );
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(format!("{}", evaluator), "Cons(1, App(App(take, 0), ones))");
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(format!("{}", evaluator), "Cons(1, [])");
    assert!(evaluator.normal_form());
}

#[test]
fn strictness() {
    let mut evaluator = CallByName::new(vec![
        Decl {
            name: "f".into(),
            args: vec![
                Pattern::Literal(Literal::Nil, ()),
                Pattern::Binding("y".into(), ()),
            ],
            body: Expr::Variable("y".into(), ()),
            aux: (),
        },
        Decl {
            name: "f".into(),
            args: vec![
                Pattern::Cons(
                    Box::new(Pattern::Binding("h".into(), ())),
                    Box::new(Pattern::Binding("t".into(), ())),
                    (),
                ),
                Pattern::Binding("y".into(), ()),
            ],
            body: Expr::Op(
                Op::Add,
                Box::new(Expr::Variable("h".into(), ())),
                Box::new(Expr::Op(
                    Op::App,
                    Box::new(Expr::Op(
                        Op::App,
                        Box::new(Expr::Variable("f".into(), ())),
                        Box::new(Expr::Variable("t".into(), ())),
                        (),
                    )),
                    Box::new(Expr::Variable("y".into(), ())),
                    (),
                )),
                (),
            ),
            aux: (),
        },
        Decl {
            name: "g".into(),
            args: vec![Pattern::Binding("x".into(), ())],
            body: Expr::Op(
                Op::Cons,
                Box::new(Expr::Variable("x".into(), ())),
                Box::new(Expr::Literal(Literal::Nil, ())),
                (),
            ),
            aux: (),
        },
        Decl {
            name: "".into(),
            args: vec![],
            body: Expr::Op(
                Op::App,
                Box::new(Expr::Op(
                    Op::App,
                    Box::new(Expr::Variable("f".into(), ())),
                    Box::new(Expr::Op(
                        Op::App,
                        Box::new(Expr::Variable("g".into(), ())),
                        Box::new(Expr::Op(
                            Op::Add,
                            Box::new(Expr::Literal(Literal::Int(1), ())),
                            Box::new(Expr::Literal(Literal::Int(2), ())),
                            (),
                        )),
                        (),
                    )),
                    (),
                )),
                Box::new(Expr::Op(
                    Op::Add,
                    Box::new(Expr::Literal(Literal::Int(3), ())),
                    Box::new(Expr::Literal(Literal::Int(4), ())),
                    (),
                )),
                (),
            ),
            aux: (),
        },
    ]);

    evaluator.step().unwrap();
    assert_eq!(
        format!("{}", evaluator),
        "App(App(f, App(g, Add(1, 2))), Add(3, 4))"
    );
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(
        format!("{}", evaluator),
        "App(App(f, Cons(Add(1, 2), [])), Add(3, 4))"
    );
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(
        format!("{}", evaluator),
        "Add(Add(1, 2), App(App(f, []), Add(3, 4)))"
    );
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(
        format!("{}", evaluator),
        "Add(3, App(App(f, []), Add(3, 4)))"
    );
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(format!("{}", evaluator), "Add(3, Add(3, 4))");
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(format!("{}", evaluator), "Add(3, 7)");
    assert!(!evaluator.normal_form());

    evaluator.step().unwrap();
    assert_eq!(format!("{}", evaluator), "10");
    assert!(evaluator.normal_form());
}