Move code over

4 files changed, 372 insertions, 0 deletions

diff --git a/core/src/test/java/coffee/liz/lambda/eval/InterpreterTest.java b/core/src/test/java/coffee/liz/lambda/eval/InterpreterTest.java
new file mode 100644
index 0000000..4b63782
--- /dev/null
+++ b/core/src/test/java/coffee/liz/lambda/eval/InterpreterTest.java
@@ -0,0 +1,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());
+	}
+}
diff --git a/core/src/test/java/coffee/liz/lambda/eval/ThunkTest.java b/core/src/test/java/coffee/liz/lambda/eval/ThunkTest.java
new file mode 100644
index 0000000..2a1d5e3
--- /dev/null
+++ b/core/src/test/java/coffee/liz/lambda/eval/ThunkTest.java
@@ -0,0 +1,38 @@
+package coffee.liz.lambda.eval;
+
+import org.junit.jupiter.api.Assertions;
+import org.junit.jupiter.api.Test;
+import org.mockito.Mockito;
+
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.function.Supplier;
+
+public class ThunkTest {
+	@Test
+	public void testThunkNonNull() {
+		final AtomicInteger invok = new AtomicInteger(0);
+		final Supplier<Integer> i = () -> {
+			invok.incrementAndGet();
+			return invok.get();
+		};
+		final Thunk<Integer> thunk = new Thunk<>(i);
+		Assertions.assertEquals(1, thunk.get());
+		Assertions.assertEquals(1, thunk.get());
+		Assertions.assertEquals(1, thunk.get());
+		Assertions.assertEquals(1, invok.get());
+	}
+
+	@Test
+	public void testThunkNull() {
+		final AtomicInteger invok = new AtomicInteger(0);
+		final Supplier<Integer> i = () -> {
+			invok.incrementAndGet();
+			return null;
+		};
+		final Thunk<Integer> thunk = new Thunk<>(i);
+		Assertions.assertNull(thunk.get());
+		Assertions.assertNull(thunk.get());
+		Assertions.assertNull(thunk.get());
+		Assertions.assertEquals(1, invok.get());
+	}
+}
diff --git a/core/src/test/java/coffee/liz/lambda/format/FormatterTest.java b/core/src/test/java/coffee/liz/lambda/format/FormatterTest.java
new file mode 100644
index 0000000..111855f
--- /dev/null
+++ b/core/src/test/java/coffee/liz/lambda/format/FormatterTest.java
@@ -0,0 +1,53 @@
+package coffee.liz.lambda.format;
+
+import coffee.liz.lambda.LambdaDriver;
+import coffee.liz.lambda.ast.SourceCode;
+import coffee.liz.lambda.ast.SourceCode.Syntax;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+
+import java.util.stream.Stream;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+class FormatterTest {
+	@ParameterizedTest
+	@MethodSource("provideRoundTrip")
+	public void testRoundTrip(final String lambda, final String arrow) {
+		final String formattedLambda = format(SourceCode.ofArrow(arrow), Syntax.LAMBDA);
+		final String formattedArrow = format(SourceCode.ofLambda(lambda), Syntax.ARROW);
+		assertEquals(lambda, formattedLambda);
+		assertEquals(arrow, formattedArrow);
+	}
+
+	public static Stream<Arguments> provideRoundTrip() {
+		return Stream.of(Arguments.of("λx.λy.x", "x -> y -> x"), Arguments.of("(λx.x) y", "(x -> x)(y)"),
+				Arguments.of("f x y z", "f(x)(y)(z)"), Arguments.of("f x y z -- Comment!", "f(x)(y)(z) -- Comment!"),
+				Arguments.of("""
+						let id = λx.x;
+						let const = λx.λy.x; -- Inline comment!
+
+						-- Test comment
+						-- Another comment
+						id""", """
+						let id = x -> x;
+						let const = x -> y -> x; -- Inline comment!
+
+						-- Test comment
+						-- Another comment
+						id"""), Arguments.of("""
+						-- The identity function
+						let id = λx.x;
+
+						id""", """
+						-- The identity function
+						let id = x -> x;
+
+						id"""));
+	}
+
+	private static String format(final SourceCode code, final Syntax syntax) {
+		return Formatter.emit(LambdaDriver.parse(code), syntax);
+	}
+}
diff --git a/core/src/test/java/coffee/liz/lambda/parser/ParserTest.java b/core/src/test/java/coffee/liz/lambda/parser/ParserTest.java
new file mode 100644
index 0000000..0158003
--- /dev/null
+++ b/core/src/test/java/coffee/liz/lambda/parser/ParserTest.java
@@ -0,0 +1,178 @@
+package coffee.liz.lambda.parser;
+
+import coffee.liz.lambda.LambdaDriver;
+import coffee.liz.lambda.ast.Expression;
+import coffee.liz.lambda.ast.Expression.AbstractionExpression;
+import coffee.liz.lambda.ast.Expression.ApplicationExpression;
+import coffee.liz.lambda.ast.Expression.IdentifierExpression;
+import coffee.liz.lambda.ast.LambdaProgram;
+import coffee.liz.lambda.ast.Macro;
+import coffee.liz.lambda.ast.SourceCode;
+import coffee.liz.lambda.ast.SourceComment;
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertInstanceOf;
+
+class ParserTest {
+
+	@Test
+	public void testTrivial() {
+		final LambdaProgram lambda = LambdaDriver.parse(SourceCode.ofLambda("λx.x"));
+		final LambdaProgram arrow = LambdaDriver.parse(SourceCode.ofArrow("x -> x"));
+
+		assertStructurallyEqual(lambda, arrow);
+		assertEquals(0, lambda.macros().size());
+		assertInstanceOf(AbstractionExpression.class, lambda.expression());
+		assertEquals("x", ((AbstractionExpression) lambda.expression()).parameter());
+	}
+
+	@Test
+	public void testApplication() {
+		final LambdaProgram lambda = LambdaDriver.parse(SourceCode.ofLambda("(λx.x) y"));
+		final LambdaProgram arrow = LambdaDriver.parse(SourceCode.ofArrow("(x -> x)(y)"));
+
+		assertStructurallyEqual(lambda, arrow);
+
+		final ApplicationExpression app = (ApplicationExpression) lambda.expression();
+		assertInstanceOf(AbstractionExpression.class, app.applicable());
+		assertInstanceOf(IdentifierExpression.class, app.argument());
+	}
+
+	@Test
+	public void testChainedLambdas() {
+		final LambdaProgram lambda = LambdaDriver.parse(SourceCode.ofLambda("λx.λy.λz.x"));
+		final LambdaProgram arrow = LambdaDriver.parse(SourceCode.ofArrow("x -> y -> z -> x"));
+
+		assertStructurallyEqual(lambda, arrow);
+
+		final AbstractionExpression outer = (AbstractionExpression) lambda.expression();
+		assertEquals("x", outer.parameter());
+		final AbstractionExpression middle = (AbstractionExpression) outer.body();
+		assertEquals("y", middle.parameter());
+		final AbstractionExpression inner = (AbstractionExpression) middle.body();
+		assertEquals("z", inner.parameter());
+	}
+
+	@Test
+	public void testChainedApplication() {
+		final LambdaProgram lambda = LambdaDriver.parse(SourceCode.ofLambda("((f x) y) z"));
+		final LambdaProgram arrow = LambdaDriver.parse(SourceCode.ofArrow("f(x)(y)(z)"));
+
+		assertStructurallyEqual(lambda, arrow);
+
+		final ApplicationExpression app1 = (ApplicationExpression) lambda.expression();
+		assertEquals("z", ((IdentifierExpression) app1.argument()).name());
+		final ApplicationExpression app2 = (ApplicationExpression) app1.applicable();
+		assertEquals("y", ((IdentifierExpression) app2.argument()).name());
+		final ApplicationExpression app3 = (ApplicationExpression) app2.applicable();
+		assertEquals("f", ((IdentifierExpression) app3.applicable()).name());
+		assertEquals("x", ((IdentifierExpression) app3.argument()).name());
+	}
+
+	@Test
+	public void testMacros() {
+		final LambdaProgram lambda = LambdaDriver.parse(SourceCode.ofLambda("""
+				let id = λx.x;
+				id
+				"""));
+		final LambdaProgram arrow = LambdaDriver.parse(SourceCode.ofArrow("""
+				let id = x -> x;
+				id
+				"""));
+
+		assertStructurallyEqual(lambda, arrow);
+		assertEquals(1, lambda.macros().size());
+		assertEquals("id", lambda.macros().getFirst().name());
+		assertInstanceOf(IdentifierExpression.class, lambda.expression());
+	}
+
+	@Test
+	public void testLineComments() {
+		final LambdaProgram lambda = LambdaDriver.parse(SourceCode.ofLambda("""
+				-- The identity function
+				let id = λx.x; -- returns its argument
+				id -- use it
+				"""));
+		final LambdaProgram arrow = LambdaDriver.parse(SourceCode.ofArrow("""
+				-- The identity function
+				let id = x -> x; -- returns its argument
+				id -- use it
+				"""));
+
+		assertStructurallyEqual(lambda, arrow);
+		assertEquals(1, lambda.macros().size());
+		assertEquals("id", lambda.macros().getFirst().name());
+	}
+
+	@Test
+	public void testComplexProgram() {
+		final LambdaProgram lambda = LambdaDriver.parse(SourceCode.ofLambda("""
+				let zero = λf.λx.x;
+				let one  = λf.λx.f x;
+				let succ = λn.λf.λx.f (n f x);
+				let add  = λm.λn.λf.λx.m f (n f x);
+
+				succ (add one zero)
+				"""));
+
+		final LambdaProgram arrow = LambdaDriver.parse(SourceCode.ofArrow("""
+				let zero = f -> x -> x;
+				let one  = f -> x -> f(x);
+				let succ = n -> f -> x -> f(n(f)(x));
+				let add  = m -> n -> f -> x -> m(f)(n(f)(x));
+
+				succ(add(one)(zero))
+				"""));
+
+		assertStructurallyEqual(lambda, arrow);
+
+		assertEquals(4, lambda.macros().size());
+		assertEquals("zero", lambda.macros().get(0).name());
+		assertEquals("one", lambda.macros().get(1).name());
+		assertEquals("succ", lambda.macros().get(2).name());
+		assertEquals("add", lambda.macros().get(3).name());
+	}
+
+	@Test
+	public void testOmegaCombinator() {
+		final LambdaProgram lambda = LambdaDriver.parse(SourceCode.ofLambda("(λx.x x)(λx.x x)"));
+		final LambdaProgram arrow = LambdaDriver.parse(SourceCode.ofArrow("(x -> x(x))(x -> x(x))"));
+
+		assertStructurallyEqual(lambda, arrow);
+	}
+
+	private static void assertStructurallyEqual(final LambdaProgram expected, final LambdaProgram actual) {
+		assertEquals(expected.macros().size(), actual.macros().size(), "Macro count mismatch");
+		for (int i = 0; i < expected.macros().size(); i++) {
+			assertStructurallyEqual(expected.macros().get(i), actual.macros().get(i));
+		}
+		assertStructurallyEqual(expected.expression(), actual.expression());
+	}
+
+	private static void assertStructurallyEqual(final Macro expected, final Macro actual) {
+		assertEquals(expected.name(), actual.name(), "Macro name mismatch");
+		assertEquals(expected.comment().map(SourceComment::text), actual.comment().map(SourceComment::text),
+				"Macro comment mismatch");
+		assertStructurallyEqual(expected.expression(), actual.expression());
+	}
+
+	private static void assertStructurallyEqual(final Expression expected, final Expression actual) {
+		assertEquals(expected.getClass(), actual.getClass(), "Expression type mismatch");
+		assertEquals(expected.comment().map(SourceComment::text), actual.comment().map(SourceComment::text),
+				"Expression comment mismatch");
+
+		switch (expected) {
+			case IdentifierExpression e ->
+				assertEquals(e.name(), ((IdentifierExpression) actual).name(), "Identifier name mismatch");
+			case AbstractionExpression e -> {
+				assertEquals(e.parameter(), ((AbstractionExpression) actual).parameter(), "Parameter mismatch");
+				assertStructurallyEqual(e.body(), ((AbstractionExpression) actual).body());
+			}
+			case ApplicationExpression e -> {
+				assertStructurallyEqual(e.applicable(), ((ApplicationExpression) actual).applicable());
+				assertStructurallyEqual(e.argument(), ((ApplicationExpression) actual).argument());
+			}
+		}
+	}
+}