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
|
use std::fs::read_to_string;
mod ast;
use ast::*;
mod parser;
use parser::*;
pub fn run(arg: &str) -> String {
let content = read_to_string(arg).unwrap();
let value = parse(&content.to_string());
let result = interpret(&value);
result.to_string()
}
fn interpret(arg: &Value) -> Value {
match arg {
Value::App(l, r) => apply(&interpret(l), r),
other => other.clone(),
}
}
fn apply(l: &Value, r: &Value) -> Value {
if let Value::Lam(v, body) = l {
subst(v, body, r)
} else {
Value::App(Box::new(l.clone()), Box::new(r.clone()))
}
}
fn subst(var: &str, body: &Value, e: &Value) -> Value {
match body {
Value::Sym(x) if x == var => e.clone(),
Value::Lam(x, b) => Value::Lam(x.to_string(), Box::new(subst(var, b, e))),
Value::App(l, r) => Value::App(Box::new(subst(var, l, e)), Box::new(subst(var, r, e))),
other => other.clone(),
}
}
#[cfg(test)]
mod lambda_test {
use crate::{interpret, parse, Value};
#[test]
fn evaluating_a_non_reducible_value_yields_itself() {
let value = parse("(foo 12)");
assert_eq!(value, interpret(&value));
}
#[test]
fn evaluating_application_on_an_abstraction_reduces_it() {
let value = parse("((lam x x) 12)");
assert_eq!(Value::Num(12), interpret(&value));
}
#[test]
fn substitution_occurs_within_abstraction_body() {
let value = parse("(((lam x (lam y x)) 13) 12)");
assert_eq!(Value::Num(13), interpret(&value));
}
#[test]
fn substitution_occurs_within_application_body() {
let value = parse("(((lam x (lam y (y x))) 13) 12)");
assert_eq!(
Value::App(Box::new(Value::Num(12)), Box::new(Value::Num(13))),
interpret(&value)
);
}
}
|
