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
|
package coffee.liz.lambda.eval;
import coffee.liz.lambda.LambdaDriver;
import coffee.liz.lambda.ast.Expression.IdentifierExpression;
import coffee.liz.lambda.ast.LambdaProgram;
import coffee.liz.lambda.ast.SourceCode;
import coffee.liz.lambda.bind.Tick;
import coffee.liz.lambda.bind.ToChurch;
import org.junit.jupiter.api.Test;
import java.util.List;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertInstanceOf;
import static org.junit.jupiter.api.Assertions.assertThrows;
class InterpreterTest {
@Test
public void identity() {
final Value result = LambdaDriver.interpret(SourceCode.ofArrow("x -> x"));
final Value.Closure closure = assertInstanceOf(Value.Closure.class, result);
assertEquals("x", closure.parameter());
assertInstanceOf(IdentifierExpression.class, closure.body());
}
@Test
public void identityApplication() {
final Value result = LambdaDriver.interpret(SourceCode.ofArrow("(x -> x)(y)"));
assertEquals(new Value.Free("y"), result);
}
@Test
public void nestedApplication() {
final Value result = LambdaDriver.interpret(SourceCode.ofArrow("(f -> g -> x -> f(g)(x))(x -> x)(y -> y)(x)"));
assertEquals(new Value.Free("x"), result);
}
@Test
public void cons() {
final Value result = LambdaDriver.interpret(SourceCode.ofArrow("""
let pair = a -> b -> f -> f(a)(b);
let second = x -> y -> y;
pair(x)(y)(second)
"""));
assertEquals(new Value.Free("y"), result);
}
@Test
public void fibonacci() {
final String source = """
let true = t -> f -> t;
let false = t -> f -> f;
let pair = x -> y -> f -> f(x)(y);
let fst = p -> p(x -> y -> x);
let snd = p -> p(x -> y -> y);
let 0 = f -> x -> x;
let 1 = f -> x -> f(x);
let succ = n -> f -> x -> f(n(f)(x));
let plus = m -> n -> f -> x -> m(f)(n(f)(x));
let next = p -> pair(snd(p))(succ(snd(p)));
let pred = n -> fst(n(next)(pair(0)(0)));
let iszero = n -> n(x -> false)(true);
let isone = n -> iszero(pred(n));
let y = f -> (x -> f(x(x)))(x -> f(x(x)));
let fib = y(fib -> n ->
iszero(n) (0)
(isone(n) (1)
(plus
(fib(pred(n)))
(fib(pred(pred(n)))))));
fib(ToChurch(13))(Tick)(dummy)
""";
final Tick ticker = new Tick();
final Value result = LambdaDriver.interpret(SourceCode.ofArrow(source), List.of(ticker, new ToChurch()));
assertEquals(new Value.Free("dummy"), result);
assertEquals(233, ticker.getCounter().get());
}
@Test
public void omegaCombinatorThrowsDepthExceeded() {
final LambdaProgram program = LambdaDriver.parse(SourceCode.ofArrow("(x -> x(x))(x -> x(x))"));
final Environment env = Environment.from(program.macros(), List.of());
final EvaluationDepthExceededException exception = assertThrows(EvaluationDepthExceededException.class,
() -> NormalOrderEvaluator.evaluate(program.expression(), env, 100));
assertEquals(100, exception.getMaxDepth());
}
}
|
