aboutsummaryrefslogtreecommitdiff
path: root/core/src/main/java/coffee/liz/lambda
diff options
context:
space:
mode:
authorElizabeth Hunt <me@liz.coffee>2026-02-08 12:33:16 -0800
committerElizabeth Hunt <me@liz.coffee>2026-02-08 13:04:51 -0800
commita673b749a5816392652785457dd1cf3603368628 (patch)
tree2f9fce694996264e7135c2533c1afc1cca026cb6 /core/src/main/java/coffee/liz/lambda
parenta483f04c16e6b56df24527f6a640e79c86928238 (diff)
downloadthe-abstraction-engine-java-a673b749a5816392652785457dd1cf3603368628.tar.gz
the-abstraction-engine-java-a673b749a5816392652785457dd1cf3603368628.zip
chore: Use actors
Diffstat (limited to 'core/src/main/java/coffee/liz/lambda')
-rw-r--r--core/src/main/java/coffee/liz/lambda/LambdaDriver.java104
-rw-r--r--core/src/main/java/coffee/liz/lambda/ast/Expression.java24
-rw-r--r--core/src/main/java/coffee/liz/lambda/ast/Macro.java2
-rw-r--r--core/src/main/java/coffee/liz/lambda/ast/SourceCode.java32
-rw-r--r--core/src/main/java/coffee/liz/lambda/ast/SourceComment.java12
-rw-r--r--core/src/main/java/coffee/liz/lambda/ast/SourceSpan.java14
-rw-r--r--core/src/main/java/coffee/liz/lambda/bind/ExternalBinding.java12
-rw-r--r--core/src/main/java/coffee/liz/lambda/bind/Tick.java14
-rw-r--r--core/src/main/java/coffee/liz/lambda/bind/ToChurch.java42
-rw-r--r--core/src/main/java/coffee/liz/lambda/eval/Environment.java154
-rw-r--r--core/src/main/java/coffee/liz/lambda/eval/EvaluationDepthExceededException.java10
-rw-r--r--core/src/main/java/coffee/liz/lambda/eval/NormalOrderEvaluator.java140
-rw-r--r--core/src/main/java/coffee/liz/lambda/eval/Thunk.java22
-rw-r--r--core/src/main/java/coffee/liz/lambda/eval/Value.java60
-rw-r--r--core/src/main/java/coffee/liz/lambda/format/Formatter.java356
15 files changed, 499 insertions, 499 deletions
diff --git a/core/src/main/java/coffee/liz/lambda/LambdaDriver.java b/core/src/main/java/coffee/liz/lambda/LambdaDriver.java
index 2ba8c70..59cee25 100644
--- a/core/src/main/java/coffee/liz/lambda/LambdaDriver.java
+++ b/core/src/main/java/coffee/liz/lambda/LambdaDriver.java
@@ -20,60 +20,60 @@ import java.util.List;
*/
public class LambdaDriver {
- /**
- * Parses source code into an AST.
- *
- * @param sourceCode
- * the source code (either Lambda or Arrow syntax)
- * @return the parsed program
- */
- public static LambdaProgram parse(final SourceCode sourceCode) {
- return switch (sourceCode) {
- case SourceCode.Lambda(String source) -> parseLambda(source);
- case SourceCode.Arrow(String source) -> parseArrow(source);
- };
- }
+ /**
+ * Parses source code into an AST.
+ *
+ * @param sourceCode
+ * the source code (either Lambda or Arrow syntax)
+ * @return the parsed program
+ */
+ public static LambdaProgram parse(final SourceCode sourceCode) {
+ return switch (sourceCode) {
+ case SourceCode.Lambda(String source) -> parseLambda(source);
+ case SourceCode.Arrow(String source) -> parseArrow(source);
+ };
+ }
- private static LambdaProgram parseLambda(final String source) {
- try (final StringReader reader = new StringReader(source)) {
- return new LambdaParser(reader).Program();
- } catch (final ParseException parseException) {
- throw new RuntimeException("Failed to parse program", parseException);
- }
- }
+ private static LambdaProgram parseLambda(final String source) {
+ try (final StringReader reader = new StringReader(source)) {
+ return new LambdaParser(reader).Program();
+ } catch (final ParseException parseException) {
+ throw new RuntimeException("Failed to parse program", parseException);
+ }
+ }
- private static LambdaProgram parseArrow(final String source) {
- try (final StringReader reader = new StringReader(source)) {
- return new ArrowParser(reader).Program();
- } catch (final ParseException parseException) {
- throw new RuntimeException("Failed to parse program", parseException);
- }
- }
+ private static LambdaProgram parseArrow(final String source) {
+ try (final StringReader reader = new StringReader(source)) {
+ return new ArrowParser(reader).Program();
+ } catch (final ParseException parseException) {
+ throw new RuntimeException("Failed to parse program", parseException);
+ }
+ }
- /**
- * Parses and evaluates lambda calculus programs.
- *
- * @param sourceCode
- * the source code
- * @return the evaluated result
- */
- public static Value interpret(final SourceCode sourceCode) {
- return interpret(sourceCode, List.of());
- }
+ /**
+ * Parses and evaluates lambda calculus programs.
+ *
+ * @param sourceCode
+ * the source code
+ * @return the evaluated result
+ */
+ public static Value interpret(final SourceCode sourceCode) {
+ return interpret(sourceCode, List.of());
+ }
- /**
- * Parses and evaluates lambda calculus programs with "FFI"'s.
- *
- * @param sourceCode
- * the source code
- * @param bindings
- * external Java functions available during evaluation
- * @return the evaluated result
- */
- public static Value interpret(final SourceCode sourceCode, final List<ExternalBinding> bindings) {
- final LambdaProgram program = parse(sourceCode);
- final Expression expression = program.expression();
- final List<Macro> macros = program.macros();
- return NormalOrderEvaluator.evaluate(expression, Environment.from(macros, bindings));
- }
+ /**
+ * Parses and evaluates lambda calculus programs with "FFI"'s.
+ *
+ * @param sourceCode
+ * the source code
+ * @param bindings
+ * external Java functions available during evaluation
+ * @return the evaluated result
+ */
+ public static Value interpret(final SourceCode sourceCode, final List<ExternalBinding> bindings) {
+ final LambdaProgram program = parse(sourceCode);
+ final Expression expression = program.expression();
+ final List<Macro> macros = program.macros();
+ return NormalOrderEvaluator.evaluate(expression, Environment.from(macros, bindings));
+ }
}
diff --git a/core/src/main/java/coffee/liz/lambda/ast/Expression.java b/core/src/main/java/coffee/liz/lambda/ast/Expression.java
index 6d75a08..c2bdd39 100644
--- a/core/src/main/java/coffee/liz/lambda/ast/Expression.java
+++ b/core/src/main/java/coffee/liz/lambda/ast/Expression.java
@@ -8,21 +8,21 @@ import java.util.Optional;
* Represents an expression in the untyped lambda calculus.
*/
public sealed interface Expression
- permits Expression.AbstractionExpression, Expression.IdentifierExpression, Expression.ApplicationExpression {
+ permits Expression.AbstractionExpression, Expression.IdentifierExpression, Expression.ApplicationExpression {
- Optional<SourceComment> comment();
+ Optional<SourceComment> comment();
- SourceSpan span();
+ SourceSpan span();
- record AbstractionExpression(@NonNull Optional<SourceComment> comment, @NonNull SourceSpan span,
- @NonNull String parameter, @NonNull Expression body) implements Expression {
- }
+ record AbstractionExpression(@NonNull Optional<SourceComment> comment, @NonNull SourceSpan span,
+ @NonNull String parameter, @NonNull Expression body) implements Expression {
+ }
- record ApplicationExpression(@NonNull Optional<SourceComment> comment, @NonNull SourceSpan span,
- @NonNull Expression applicable, @NonNull Expression argument) implements Expression {
- }
+ record ApplicationExpression(@NonNull Optional<SourceComment> comment, @NonNull SourceSpan span,
+ @NonNull Expression applicable, @NonNull Expression argument) implements Expression {
+ }
- record IdentifierExpression(@NonNull Optional<SourceComment> comment, @NonNull SourceSpan span,
- @NonNull String name) implements Expression {
- }
+ record IdentifierExpression(@NonNull Optional<SourceComment> comment, @NonNull SourceSpan span,
+ @NonNull String name) implements Expression {
+ }
}
diff --git a/core/src/main/java/coffee/liz/lambda/ast/Macro.java b/core/src/main/java/coffee/liz/lambda/ast/Macro.java
index 07ba911..4a485fc 100644
--- a/core/src/main/java/coffee/liz/lambda/ast/Macro.java
+++ b/core/src/main/java/coffee/liz/lambda/ast/Macro.java
@@ -8,5 +8,5 @@ import java.util.Optional;
* A named macro definition that maps an identifier to an expression.
*/
public record Macro(@NonNull Optional<SourceComment> comment, @NonNull SourceSpan span, @NonNull String name,
- @NonNull Expression expression) {
+ @NonNull Expression expression) {
}
diff --git a/core/src/main/java/coffee/liz/lambda/ast/SourceCode.java b/core/src/main/java/coffee/liz/lambda/ast/SourceCode.java
index 200c45e..c2112ad 100644
--- a/core/src/main/java/coffee/liz/lambda/ast/SourceCode.java
+++ b/core/src/main/java/coffee/liz/lambda/ast/SourceCode.java
@@ -4,24 +4,24 @@ package coffee.liz.lambda.ast;
* Represents source code in one of the supported lambda calculus syntaxes.
*/
public sealed interface SourceCode {
- static SourceCode ofLambda(final String source) {
- return new Lambda(source);
- }
+ static SourceCode ofLambda(final String source) {
+ return new Lambda(source);
+ }
- static SourceCode ofArrow(final String source) {
- return new Arrow(source);
- }
+ static SourceCode ofArrow(final String source) {
+ return new Arrow(source);
+ }
- record Lambda(String source) implements SourceCode {
- }
+ record Lambda(String source) implements SourceCode {
+ }
- record Arrow(String source) implements SourceCode {
- }
+ record Arrow(String source) implements SourceCode {
+ }
- /**
- * Supported syntax types for {@link SourceCode}.
- */
- enum Syntax {
- LAMBDA, ARROW
- }
+ /**
+ * Supported syntax types for {@link SourceCode}.
+ */
+ enum Syntax {
+ LAMBDA, ARROW
+ }
}
diff --git a/core/src/main/java/coffee/liz/lambda/ast/SourceComment.java b/core/src/main/java/coffee/liz/lambda/ast/SourceComment.java
index da6b5ab..8e50f5f 100644
--- a/core/src/main/java/coffee/liz/lambda/ast/SourceComment.java
+++ b/core/src/main/java/coffee/liz/lambda/ast/SourceComment.java
@@ -12,10 +12,10 @@ import lombok.NonNull;
*/
public record SourceComment(@NonNull String text, @NonNull SourceSpan span) {
- /**
- * Returns true if this comment is on the same line as the given span's end.
- */
- public boolean isInlineAfter(final SourceSpan previous) {
- return previous != null && previous.endLine() == this.span.startLine();
- }
+ /**
+ * Returns true if this comment is on the same line as the given span's end.
+ */
+ public boolean isInlineAfter(final SourceSpan previous) {
+ return previous != null && previous.endLine() == this.span.startLine();
+ }
}
diff --git a/core/src/main/java/coffee/liz/lambda/ast/SourceSpan.java b/core/src/main/java/coffee/liz/lambda/ast/SourceSpan.java
index 7df9bcd..80e06f9 100644
--- a/core/src/main/java/coffee/liz/lambda/ast/SourceSpan.java
+++ b/core/src/main/java/coffee/liz/lambda/ast/SourceSpan.java
@@ -13,12 +13,12 @@ package coffee.liz.lambda.ast;
* 1-based column number where the span ends
*/
public record SourceSpan(int startLine, int startColumn, int endLine, int endColumn) {
- public static final SourceSpan UNKNOWN = new SourceSpan(0, 0, 0, 0);
+ public static final SourceSpan UNKNOWN = new SourceSpan(0, 0, 0, 0);
- /**
- * Returns true if this span ends on the same line that the other span starts.
- */
- public boolean isOnSameLine(final SourceSpan other) {
- return this.endLine == other.startLine;
- }
+ /**
+ * Returns true if this span ends on the same line that the other span starts.
+ */
+ public boolean isOnSameLine(final SourceSpan other) {
+ return this.endLine == other.startLine;
+ }
}
diff --git a/core/src/main/java/coffee/liz/lambda/bind/ExternalBinding.java b/core/src/main/java/coffee/liz/lambda/bind/ExternalBinding.java
index 4895972..7a8ae40 100644
--- a/core/src/main/java/coffee/liz/lambda/bind/ExternalBinding.java
+++ b/core/src/main/java/coffee/liz/lambda/bind/ExternalBinding.java
@@ -14,10 +14,10 @@ import java.util.function.BiFunction;
*/
public interface ExternalBinding extends BiFunction<Environment, Value, Value> {
- /**
- * Returns the name used to reference this binding in environment.
- *
- * @return the binding name
- */
- String getName();
+ /**
+ * Returns the name used to reference this binding in environment.
+ *
+ * @return the binding name
+ */
+ String getName();
}
diff --git a/core/src/main/java/coffee/liz/lambda/bind/Tick.java b/core/src/main/java/coffee/liz/lambda/bind/Tick.java
index 0fa4de5..c4ad8ee 100644
--- a/core/src/main/java/coffee/liz/lambda/bind/Tick.java
+++ b/core/src/main/java/coffee/liz/lambda/bind/Tick.java
@@ -11,12 +11,12 @@ import java.util.concurrent.atomic.AtomicInteger;
*/
@Getter
public class Tick implements ExternalBinding {
- private final String name = "Tick";
- private final AtomicInteger counter = new AtomicInteger(0);
+ private final String name = "Tick";
+ private final AtomicInteger counter = new AtomicInteger(0);
- @Override
- public Value apply(final Environment environment, final Value value) {
- counter.incrementAndGet();
- return value;
- }
+ @Override
+ public Value apply(final Environment environment, final Value value) {
+ counter.incrementAndGet();
+ return value;
+ }
}
diff --git a/core/src/main/java/coffee/liz/lambda/bind/ToChurch.java b/core/src/main/java/coffee/liz/lambda/bind/ToChurch.java
index bfddd86..315622a 100644
--- a/core/src/main/java/coffee/liz/lambda/bind/ToChurch.java
+++ b/core/src/main/java/coffee/liz/lambda/bind/ToChurch.java
@@ -22,28 +22,28 @@ import lombok.Getter;
*/
@Getter
public class ToChurch implements ExternalBinding {
- private final String name = "ToChurch";
+ private final String name = "ToChurch";
- /**
- * Converts a free variable containing an integer string to a Church numeral.
- *
- * @param env
- * the current environment
- * @param val
- * a Free value whose name is an integer string
- * @return a Closure representing the Church numeral
- */
- @Override
- public Value apply(final Environment env, final Value val) {
- final Free free = (Free) val;
- final int n = Integer.parseInt(free.name());
+ /**
+ * Converts a free variable containing an integer string to a Church numeral.
+ *
+ * @param env
+ * the current environment
+ * @param val
+ * a Free value whose name is an integer string
+ * @return a Closure representing the Church numeral
+ */
+ @Override
+ public Value apply(final Environment env, final Value val) {
+ final Free free = (Free) val;
+ final int n = Integer.parseInt(free.name());
- Expression body = new IdentifierExpression(Optional.empty(), SourceSpan.UNKNOWN, "x");
- for (int i = 0; i < n; i++) {
- body = new ApplicationExpression(Optional.empty(), SourceSpan.UNKNOWN,
- new IdentifierExpression(Optional.empty(), SourceSpan.UNKNOWN, "f"), body);
- }
+ Expression body = new IdentifierExpression(Optional.empty(), SourceSpan.UNKNOWN, "x");
+ for (int i = 0; i < n; i++) {
+ body = new ApplicationExpression(Optional.empty(), SourceSpan.UNKNOWN,
+ new IdentifierExpression(Optional.empty(), SourceSpan.UNKNOWN, "f"), body);
+ }
- return new Closure(env, "f", new AbstractionExpression(Optional.empty(), SourceSpan.UNKNOWN, "x", body));
- }
+ return new Closure(env, "f", new AbstractionExpression(Optional.empty(), SourceSpan.UNKNOWN, "x", body));
+ }
}
diff --git a/core/src/main/java/coffee/liz/lambda/eval/Environment.java b/core/src/main/java/coffee/liz/lambda/eval/Environment.java
index 8854719..a4ec24a 100644
--- a/core/src/main/java/coffee/liz/lambda/eval/Environment.java
+++ b/core/src/main/java/coffee/liz/lambda/eval/Environment.java
@@ -18,92 +18,92 @@ import java.util.stream.Collectors;
*/
@RequiredArgsConstructor
public final class Environment {
- /** Named expansions */
- private final Map<String, Expression> macros;
+ /** Named expansions */
+ private final Map<String, Expression> macros;
- /** "FFI" */
- private final Map<String, ExternalBinding> externalBindings;
+ /** "FFI" */
+ private final Map<String, ExternalBinding> externalBindings;
- /** Variable name bound at this scope level. Null for root. */
- @Nullable
- private final String boundName;
+ /** Variable name bound at this scope level. Null for root. */
+ @Nullable
+ private final String boundName;
- /** Lazily-evaluated value for boundName, or null for root. */
- @Nullable
- private final Supplier<Value> boundValue;
+ /** Lazily-evaluated value for boundName, or null for root. */
+ @Nullable
+ private final Supplier<Value> boundValue;
- /** Enclosing scope, or null for root. Forms a linked list of bindings. */
- @Nullable
- private final Environment parent;
+ /** Enclosing scope, or null for root. Forms a linked list of bindings. */
+ @Nullable
+ private final Environment parent;
- /**
- * Creates an environment from macro and external binding lists.
- *
- * @param macros
- * program macro definitions
- * @param externalBindings
- * external Java bindings for FFI
- * @return the new environment
- */
- public static Environment from(final List<Macro> macros, final List<ExternalBinding> externalBindings) {
- return new Environment(macros.stream().collect(Collectors.toMap(Macro::name, Macro::expression)),
- externalBindings.stream().collect(Collectors.toMap(ExternalBinding::getName, Function.identity())),
- null, null, null);
- }
+ /**
+ * Creates an environment from macro and external binding lists.
+ *
+ * @param macros
+ * program macro definitions
+ * @param externalBindings
+ * external Java bindings for FFI
+ * @return the new environment
+ */
+ public static Environment from(final List<Macro> macros, final List<ExternalBinding> externalBindings) {
+ return new Environment(macros.stream().collect(Collectors.toMap(Macro::name, Macro::expression)),
+ externalBindings.stream().collect(Collectors.toMap(ExternalBinding::getName, Function.identity())),
+ null, null, null);
+ }
- /**
- * Creates a child scope.
- *
- * @param name
- * the variable name
- * @param value
- * the value supplier (thunk)
- * @return a new environment with the binding added
- */
- public Environment extend(final String name, final Supplier<Value> value) {
- return new Environment(macros, externalBindings, name, value, this);
- }
+ /**
+ * Creates a child scope.
+ *
+ * @param name
+ * the variable name
+ * @param value
+ * the value supplier (thunk)
+ * @return a new environment with the binding added
+ */
+ public Environment extend(final String name, final Supplier<Value> value) {
+ return new Environment(macros, externalBindings, name, value, this);
+ }
- /**
- * Looks up a name, checking bindings, then macros, then external bindings.
- *
- * @param name
- * the name to look up
- * @return the lookup result, or empty if not found
- */
- public Optional<LookupResult> lookup(final String name) {
- for (Environment env = this; env != null; env = env.parent) {
- if (!name.equals(env.boundName)) {
- continue;
- }
- return Optional.of(new LookupResult.Binding(env.boundValue));
- }
+ /**
+ * Looks up a name, checking bindings, then macros, then external bindings.
+ *
+ * @param name
+ * the name to look up
+ * @return the lookup result, or empty if not found
+ */
+ public Optional<LookupResult> lookup(final String name) {
+ for (Environment env = this; env != null; env = env.parent) {
+ if (!name.equals(env.boundName)) {
+ continue;
+ }
+ return Optional.of(new LookupResult.Binding(env.boundValue));
+ }
- final Expression macro = macros.get(name);
- if (macro != null) {
- return Optional.of(new LookupResult.Macro(macro));
- }
+ final Expression macro = macros.get(name);
+ if (macro != null) {
+ return Optional.of(new LookupResult.Macro(macro));
+ }
- final ExternalBinding external = externalBindings.get(name);
- if (external != null) {
- return Optional.of(new LookupResult.External(external));
- }
+ final ExternalBinding external = externalBindings.get(name);
+ if (external != null) {
+ return Optional.of(new LookupResult.External(external));
+ }
- return Optional.empty();
- }
+ return Optional.empty();
+ }
- /**
- * Result of looking up a name in the environment.
- */
- public sealed interface LookupResult {
- /** A local variable binding. */
- record Binding(Supplier<Value> value) implements LookupResult {
- }
- /** A macro definition. */
- record Macro(Expression expression) implements LookupResult {
- }
- /** An external Java binding. */
- record External(ExternalBinding binding) implements LookupResult {
- }
- }
+ /**
+ * Result of looking up a name in the environment.
+ */
+ public sealed interface LookupResult {
+ /** A local variable binding. */
+ record Binding(Supplier<Value> value) implements LookupResult {
+ }
+ /** A macro definition. */
+ record Macro(Expression expression) implements LookupResult {
+ }
+ /** An external Java binding. */
+ record External(ExternalBinding binding) implements LookupResult {
+ }
+ }
}
diff --git a/core/src/main/java/coffee/liz/lambda/eval/EvaluationDepthExceededException.java b/core/src/main/java/coffee/liz/lambda/eval/EvaluationDepthExceededException.java
index 7926004..8f2ad2e 100644
--- a/core/src/main/java/coffee/liz/lambda/eval/EvaluationDepthExceededException.java
+++ b/core/src/main/java/coffee/liz/lambda/eval/EvaluationDepthExceededException.java
@@ -7,10 +7,10 @@ import lombok.Getter;
*/
@Getter
public final class EvaluationDepthExceededException extends RuntimeException {
- private final int maxDepth;
+ private final int maxDepth;
- public EvaluationDepthExceededException(final int maxDepth) {
- super("Evaluation exceeded maximum depth of " + maxDepth);
- this.maxDepth = maxDepth;
- }
+ public EvaluationDepthExceededException(final int maxDepth) {
+ super("Evaluation exceeded maximum depth of " + maxDepth);
+ this.maxDepth = maxDepth;
+ }
}
diff --git a/core/src/main/java/coffee/liz/lambda/eval/NormalOrderEvaluator.java b/core/src/main/java/coffee/liz/lambda/eval/NormalOrderEvaluator.java
index 28eb69b..d9bcba3 100644
--- a/core/src/main/java/coffee/liz/lambda/eval/NormalOrderEvaluator.java
+++ b/core/src/main/java/coffee/liz/lambda/eval/NormalOrderEvaluator.java
@@ -18,84 +18,84 @@ import coffee.liz.lambda.eval.Value.Free;
*/
public final class NormalOrderEvaluator {
- public static final int DEFAULT_MAX_DEPTH = 140;
+ public static final int DEFAULT_MAX_DEPTH = 140;
- /**
- * Evaluates an expression in the given environment with default depth limit.
- *
- * @param term
- * the expression to evaluate
- * @param env
- * the environment containing bindings
- * @return the resulting value
- * @throws EvaluationDepthExceededException
- * if evaluation exceeds {@link #DEFAULT_MAX_DEPTH}
- */
- public static Value evaluate(final Expression term, final Environment env) {
- return evaluate(term, env, DEFAULT_MAX_DEPTH);
- }
+ /**
+ * Evaluates an expression in the given environment with default depth limit.
+ *
+ * @param term
+ * the expression to evaluate
+ * @param env
+ * the environment containing bindings
+ * @return the resulting value
+ * @throws EvaluationDepthExceededException
+ * if evaluation exceeds {@link #DEFAULT_MAX_DEPTH}
+ */
+ public static Value evaluate(final Expression term, final Environment env) {
+ return evaluate(term, env, DEFAULT_MAX_DEPTH);
+ }
- /**
- * Evaluates an expression in the given environment with specified depth limit.
- *
- * @param term
- * the expression to evaluate
- * @param env
- * the environment containing bindings
- * @param maxDepth
- * maximum evaluation depth
- * @return the resulting value
- * @throws EvaluationDepthExceededException
- * if evaluation exceeds maxDepth
- */
- public static Value evaluate(final Expression term, final Environment env, final int maxDepth) {
- return evaluate(term, env, maxDepth, 0);
- }
+ /**
+ * Evaluates an expression in the given environment with specified depth limit.
+ *
+ * @param term
+ * the expression to evaluate
+ * @param env
+ * the environment containing bindings
+ * @param maxDepth
+ * maximum evaluation depth
+ * @return the resulting value
+ * @throws EvaluationDepthExceededException
+ * if evaluation exceeds maxDepth
+ */
+ public static Value evaluate(final Expression term, final Environment env, final int maxDepth) {
+ return evaluate(term, env, maxDepth, 0);
+ }
- private static Value evaluate(final Expression term, final Environment env, final int maxDepth, final int depth) {
- if (depth > maxDepth) {
- throw new EvaluationDepthExceededException(maxDepth);
- }
+ private static Value evaluate(final Expression term, final Environment env, final int maxDepth, final int depth) {
+ if (depth > maxDepth) {
+ throw new EvaluationDepthExceededException(maxDepth);
+ }
- return switch (term) {
- case IdentifierExpression(var _, var _, final String name) ->
- env.lookup(name).map(result -> switch (result) {
- case LookupResult.Binding(final var value) -> value.get();
- case LookupResult.Macro(final var expr) -> evaluate(expr, env, maxDepth, depth + 1);
- case LookupResult.External(final var binding) -> new Free(binding.getName());
- }).orElseGet(() -> new Free(name));
+ return switch (term) {
+ case IdentifierExpression(var _, var _, final String name) ->
+ env.lookup(name).map(result -> switch (result) {
+ case LookupResult.Binding(final var value) -> value.get();
+ case LookupResult.Macro(final var expr) -> evaluate(expr, env, maxDepth, depth + 1);
+ case LookupResult.External(final var binding) -> new Free(binding.getName());
+ }).orElseGet(() -> new Free(name));
- case AbstractionExpression(var _, var _, final String parameter, final Expression body) ->
- new Closure(env, parameter, body);
+ case AbstractionExpression(var _, var _, final String parameter, final Expression body) ->
+ new Closure(env, parameter, body);
- case ApplicationExpression(var _, var _, final Expression func, final Expression arg) ->
- apply(evaluate(func, env, maxDepth, depth + 1), arg, env, maxDepth, depth + 1);
- };
- }
+ case ApplicationExpression(var _, var _, final Expression func, final Expression arg) ->
+ apply(evaluate(func, env, maxDepth, depth + 1), arg, env, maxDepth, depth + 1);
+ };
+ }
- private static Value apply(final Value funcVal, final Expression arg, final Environment argEnv, final int maxDepth,
- final int depth) {
- if (depth > maxDepth) {
- throw new EvaluationDepthExceededException(maxDepth);
- }
+ private static Value apply(final Value funcVal, final Expression arg, final Environment argEnv, final int maxDepth,
+ final int depth) {
+ if (depth > maxDepth) {
+ throw new EvaluationDepthExceededException(maxDepth);
+ }
- return switch (funcVal) {
- case Closure(final Environment closureEnv, final String parameter, final Expression body) -> {
- final Thunk<Value> thunk = new Thunk<>(() -> evaluate(arg, argEnv, maxDepth, depth + 1));
- final Environment newEnv = closureEnv.extend(parameter, thunk);
- yield evaluate(body, newEnv, maxDepth, depth + 1);
- }
+ return switch (funcVal) {
+ case Closure(final Environment closureEnv, final String parameter, final Expression body) -> {
+ final Thunk<Value> thunk = new Thunk<>(() -> evaluate(arg, argEnv, maxDepth, depth + 1));
+ final Environment newEnv = closureEnv.extend(parameter, thunk);
+ yield evaluate(body, newEnv, maxDepth, depth + 1);
+ }
- case Free(final String name) ->
- argEnv.lookup(name).filter(r -> r instanceof LookupResult.External).map(r -> {
- final ExternalBinding binding = ((LookupResult.External) r).binding();
- return binding.apply(argEnv, evaluate(arg, argEnv, maxDepth, depth + 1));
- }).orElseGet(() -> new Application(funcVal, evaluate(arg, argEnv, maxDepth, depth + 1)));
+ case Free(final String name) ->
+ argEnv.lookup(name).filter(r -> r instanceof LookupResult.External).map(r -> {
+ final ExternalBinding binding = ((LookupResult.External) r).binding();
+ return binding.apply(argEnv, evaluate(arg, argEnv, maxDepth, depth + 1));
+ }).orElseGet(() -> new Application(funcVal, evaluate(arg, argEnv, maxDepth, depth + 1)));
- case Application app -> {
- final Value argVal = evaluate(arg, argEnv, maxDepth, depth + 1);
- yield new Application(app, argVal);
- }
- };
- }
+ case Application app -> {
+ final Value argVal = evaluate(arg, argEnv, maxDepth, depth + 1);
+ yield new Application(app, argVal);
+ }
+ };
+ }
}
diff --git a/core/src/main/java/coffee/liz/lambda/eval/Thunk.java b/core/src/main/java/coffee/liz/lambda/eval/Thunk.java
index 07c89bf..fdbda93 100644
--- a/core/src/main/java/coffee/liz/lambda/eval/Thunk.java
+++ b/core/src/main/java/coffee/liz/lambda/eval/Thunk.java
@@ -12,16 +12,16 @@ import java.util.function.Supplier;
*/
@RequiredArgsConstructor
public final class Thunk<T> implements Supplier<T> {
- private final Supplier<T> thinker; // https://www.youtube.com/shorts/Dzksib8YxSY
- private T cached = null;
- private boolean evaluated = false;
+ private final Supplier<T> thinker; // https://www.youtube.com/shorts/Dzksib8YxSY
+ private T cached = null;
+ private boolean evaluated = false;
- @Override
- public T get() {
- if (!evaluated) {
- cached = thinker.get();
- evaluated = true;
- }
- return cached;
- }
+ @Override
+ public T get() {
+ if (!evaluated) {
+ cached = thinker.get();
+ evaluated = true;
+ }
+ return cached;
+ }
} \ No newline at end of file
diff --git a/core/src/main/java/coffee/liz/lambda/eval/Value.java b/core/src/main/java/coffee/liz/lambda/eval/Value.java
index 58b9ba4..dc459ff 100644
--- a/core/src/main/java/coffee/liz/lambda/eval/Value.java
+++ b/core/src/main/java/coffee/liz/lambda/eval/Value.java
@@ -7,36 +7,36 @@ import coffee.liz.lambda.ast.Expression;
*/
public sealed interface Value permits Value.Closure, Value.Application, Value.Free {
- /**
- * A closure capturing an environment, parameter, and body.
- *
- * @param env
- * the captured environment
- * @param parameter
- * the bound parameter name
- * @param body
- * the lambda body expression
- */
- record Closure(Environment env, String parameter, Expression body) implements Value {
- }
+ /**
+ * A closure capturing an environment, parameter, and body.
+ *
+ * @param env
+ * the captured environment
+ * @param parameter
+ * the bound parameter name
+ * @param body
+ * the lambda body expression
+ */
+ record Closure(Environment env, String parameter, Expression body) implements Value {
+ }
- /**
- * A symbolic application of a function to an argument.
- *
- * @param function
- * the function
- * @param argument
- * the argument
- */
- record Application(Value function, Value argument) implements Value {
- }
+ /**
+ * A symbolic application of a function to an argument.
+ *
+ * @param function
+ * the function
+ * @param argument
+ * the argument
+ */
+ record Application(Value function, Value argument) implements Value {
+ }
- /**
- * A free variable.
- *
- * @param name
- * the variable name
- */
- record Free(String name) implements Value {
- }
+ /**
+ * A free variable.
+ *
+ * @param name
+ * the variable name
+ */
+ record Free(String name) implements Value {
+ }
}
diff --git a/core/src/main/java/coffee/liz/lambda/format/Formatter.java b/core/src/main/java/coffee/liz/lambda/format/Formatter.java
index 1ac3e95..e4fbc0c 100644
--- a/core/src/main/java/coffee/liz/lambda/format/Formatter.java
+++ b/core/src/main/java/coffee/liz/lambda/format/Formatter.java
@@ -21,218 +21,218 @@ import java.util.Optional;
@RequiredArgsConstructor
public final class Formatter {
- private final Syntax syntax;
+ private final Syntax syntax;
- public String format(final LambdaProgram program) {
- final StringBuilder sb = new StringBuilder();
- SourceSpan previousEnd = null;
+ public String format(final LambdaProgram program) {
+ final StringBuilder sb = new StringBuilder();
+ SourceSpan previousEnd = null;
- for (int i = 0; i < program.macros().size(); i++) {
- final Macro macro = program.macros().get(i);
+ for (int i = 0; i < program.macros().size(); i++) {
+ final Macro macro = program.macros().get(i);
- if (macro.comment().isPresent()) {
- final SourceComment comment = macro.comment().get();
- final String leadingPart = getLeadingCommentPart(comment, previousEnd);
- if (!leadingPart.isEmpty()) {
- sb.append(leadingPart);
- if (!leadingPart.endsWith("\n")) {
- sb.append("\n");
- }
- }
- }
+ if (macro.comment().isPresent()) {
+ final SourceComment comment = macro.comment().get();
+ final String leadingPart = getLeadingCommentPart(comment, previousEnd);
+ if (!leadingPart.isEmpty()) {
+ sb.append(leadingPart);
+ if (!leadingPart.endsWith("\n")) {
+ sb.append("\n");
+ }
+ }
+ }
- sb.append("let ").append(macro.name()).append(" = ");
- sb.append(formatExpression(macro.expression(), false));
- sb.append(";");
+ sb.append("let ").append(macro.name()).append(" = ");
+ sb.append(formatExpression(macro.expression(), false));
+ sb.append(";");
- final Optional<String> inlineComment = getInlineCommentAfter(macro.span(), program, i);
- inlineComment.ifPresent(c -> sb.append(" ").append(c));
- sb.append("\n");
+ final Optional<String> inlineComment = getInlineCommentAfter(macro.span(), program, i);
+ inlineComment.ifPresent(c -> sb.append(" ").append(c));
+ sb.append("\n");
- previousEnd = macro.span();
- }
+ previousEnd = macro.span();
+ }
- boolean isTrailingComment = false;
- boolean inlinePartAlreadyOutput = false;
+ boolean isTrailingComment = false;
+ boolean inlinePartAlreadyOutput = false;
- if (program.expression().comment().isPresent()) {
- final SourceComment comment = program.expression().comment().get();
+ if (program.expression().comment().isPresent()) {
+ final SourceComment comment = program.expression().comment().get();
- isTrailingComment = comment.span().startLine() >= program.expression().span().startLine()
- && comment.span().startColumn() > program.expression().span().startColumn();
+ isTrailingComment = comment.span().startLine() >= program.expression().span().startLine()
+ && comment.span().startColumn() > program.expression().span().startColumn();
- if (!isTrailingComment) {
- inlinePartAlreadyOutput = previousEnd != null && comment.isInlineAfter(previousEnd);
+ if (!isTrailingComment) {
+ inlinePartAlreadyOutput = previousEnd != null && comment.isInlineAfter(previousEnd);
- final String leadingPart = getLeadingCommentPart(comment, previousEnd);
- if (!leadingPart.isEmpty()) {
- sb.append(leadingPart);
- if (!leadingPart.endsWith("\n")) {
- sb.append("\n");
- }
- } else if (!program.macros().isEmpty()) {
- sb.append("\n");
- }
- } else if (!program.macros().isEmpty()) {
- sb.append("\n");
- }
- } else if (!program.macros().isEmpty()) {
- sb.append("\n");
- }
+ final String leadingPart = getLeadingCommentPart(comment, previousEnd);
+ if (!leadingPart.isEmpty()) {
+ sb.append(leadingPart);
+ if (!leadingPart.endsWith("\n")) {
+ sb.append("\n");
+ }
+ } else if (!program.macros().isEmpty()) {
+ sb.append("\n");
+ }
+ } else if (!program.macros().isEmpty()) {
+ sb.append("\n");
+ }
+ } else if (!program.macros().isEmpty()) {
+ sb.append("\n");
+ }
- sb.append(formatExpression(program.expression(), false));
+ sb.append(formatExpression(program.expression(), false));
- if (program.expression().comment().isPresent() && !inlinePartAlreadyOutput && isTrailingComment) {
- sb.append(" ").append(program.expression().comment().get().text());
- }
+ if (program.expression().comment().isPresent() && !inlinePartAlreadyOutput && isTrailingComment) {
+ sb.append(" ").append(program.expression().comment().get().text());
+ }
- return sb.toString();
- }
+ return sb.toString();
+ }
- /**
- * Gets the inline portion of a comment (first line if on same line as previous
- * element).
- */
- private String getInlineCommentPart(final SourceComment comment, final SourceSpan previousEnd) {
- if (previousEnd == null || !comment.isInlineAfter(previousEnd)) {
- return "";
- }
- final String text = comment.text();
- final int newlineIndex = text.indexOf('\n');
- return newlineIndex == -1 ? text : text.substring(0, newlineIndex);
- }
+ /**
+ * Gets the inline portion of a comment (first line if on same line as previous
+ * element).
+ */
+ private String getInlineCommentPart(final SourceComment comment, final SourceSpan previousEnd) {
+ if (previousEnd == null || !comment.isInlineAfter(previousEnd)) {
+ return "";
+ }
+ final String text = comment.text();
+ final int newlineIndex = text.indexOf('\n');
+ return newlineIndex == -1 ? text : text.substring(0, newlineIndex);
+ }
- /**
- * Gets the leading portion of a comment (all lines except inline first line).
- */
- private String getLeadingCommentPart(final SourceComment comment, final SourceSpan previousEnd) {
- if (previousEnd == null || !comment.isInlineAfter(previousEnd)) {
- return comment.text();
- }
- final String text = comment.text();
- final int newlineIndex = text.indexOf('\n');
- return newlineIndex == -1 ? "" : text.substring(newlineIndex + 1);
- }
+ /**
+ * Gets the leading portion of a comment (all lines except inline first line).
+ */
+ private String getLeadingCommentPart(final SourceComment comment, final SourceSpan previousEnd) {
+ if (previousEnd == null || !comment.isInlineAfter(previousEnd)) {
+ return comment.text();
+ }
+ final String text = comment.text();
+ final int newlineIndex = text.indexOf('\n');
+ return newlineIndex == -1 ? "" : text.substring(newlineIndex + 1);
+ }
- /**
- * Gets the inline comment that appears after the given span, if any.
- */
- private Optional<String> getInlineCommentAfter(final SourceSpan span, final LambdaProgram program,
- final int macroIndex) {
- if (macroIndex + 1 < program.macros().size()) {
- final Macro nextMacro = program.macros().get(macroIndex + 1);
- if (nextMacro.comment().isPresent() && nextMacro.comment().get().isInlineAfter(span)) {
- final String inlinePart = getInlineCommentPart(nextMacro.comment().get(), span);
- if (!inlinePart.isEmpty()) {
- return Optional.of(inlinePart);
- }
- }
- }
- if (macroIndex == program.macros().size() - 1 && program.expression().comment().isPresent()
- && program.expression().comment().get().isInlineAfter(span)) {
- final String inlinePart = getInlineCommentPart(program.expression().comment().get(), span);
- if (!inlinePart.isEmpty()) {
- return Optional.of(inlinePart);
- }
- }
- return Optional.empty();
- }
+ /**
+ * Gets the inline comment that appears after the given span, if any.
+ */
+ private Optional<String> getInlineCommentAfter(final SourceSpan span, final LambdaProgram program,
+ final int macroIndex) {
+ if (macroIndex + 1 < program.macros().size()) {
+ final Macro nextMacro = program.macros().get(macroIndex + 1);
+ if (nextMacro.comment().isPresent() && nextMacro.comment().get().isInlineAfter(span)) {
+ final String inlinePart = getInlineCommentPart(nextMacro.comment().get(), span);
+ if (!inlinePart.isEmpty()) {
+ return Optional.of(inlinePart);
+ }
+ }
+ }
+ if (macroIndex == program.macros().size() - 1 && program.expression().comment().isPresent()
+ && program.expression().comment().get().isInlineAfter(span)) {
+ final String inlinePart = getInlineCommentPart(program.expression().comment().get(), span);
+ if (!inlinePart.isEmpty()) {
+ return Optional.of(inlinePart);
+ }
+ }
+ return Optional.empty();
+ }
- private String formatExpression(final Expression expr, final boolean needsParens) {
- return switch (expr) {
- case AbstractionExpression abs -> formatAbstraction(abs, needsParens);
- case ApplicationExpression app -> formatApplication(app, needsParens);
- case IdentifierExpression id -> id.name();
- };
- }
+ private String formatExpression(final Expression expr, final boolean needsParens) {
+ return switch (expr) {
+ case AbstractionExpression abs -> formatAbstraction(abs, needsParens);
+ case ApplicationExpression app -> formatApplication(app, needsParens);
+ case IdentifierExpression id -> id.name();
+ };
+ }
- private String formatAbstraction(final AbstractionExpression abs, final boolean needsParens) {
- final StringBuilder sb = new StringBuilder();
+ private String formatAbstraction(final AbstractionExpression abs, final boolean needsParens) {
+ final StringBuilder sb = new StringBuilder();
- if (needsParens) {
- sb.append("(");
- }
- switch (syntax) {
- case LAMBDA -> {
- sb.append("λ").append(abs.parameter()).append(".");
- sb.append(formatExpression(abs.body(), false));
- }
- case ARROW -> {
- sb.append(abs.parameter()).append(" -> ");
- sb.append(formatExpression(abs.body(), false));
- }
- }
- if (needsParens) {
- sb.append(")");
- }
+ if (needsParens) {
+ sb.append("(");
+ }
+ switch (syntax) {
+ case LAMBDA -> {
+ sb.append("λ").append(abs.parameter()).append(".");
+ sb.append(formatExpression(abs.body(), false));
+ }
+ case ARROW -> {
+ sb.append(abs.parameter()).append(" -> ");
+ sb.append(formatExpression(abs.body(), false));
+ }
+ }
+ if (needsParens) {
+ sb.append(")");
+ }
- return sb.toString();
- }
+ return sb.toString();
+ }
- private String formatApplication(final ApplicationExpression app, final boolean needsParens) {
- return switch (syntax) {
- case LAMBDA -> formatLambdaApplication(app, needsParens);
- case ARROW -> formatArrowApplication(app);
- };
- }
+ private String formatApplication(final ApplicationExpression app, final boolean needsParens) {
+ return switch (syntax) {
+ case LAMBDA -> formatLambdaApplication(app, needsParens);
+ case ARROW -> formatArrowApplication(app);
+ };
+ }
- private String formatLambdaApplication(final ApplicationExpression app, final boolean needsParens) {
- final StringBuilder sb = new StringBuilder();
+ private String formatLambdaApplication(final ApplicationExpression app, final boolean needsParens) {
+ final StringBuilder sb = new StringBuilder();
- if (needsParens) {
- sb.append("(");
- }
+ if (needsParens) {
+ sb.append("(");
+ }
- final boolean funcNeedsParens = app.applicable() instanceof AbstractionExpression;
- sb.append(formatExpression(app.applicable(), funcNeedsParens));
+ final boolean funcNeedsParens = app.applicable() instanceof AbstractionExpression;
+ sb.append(formatExpression(app.applicable(), funcNeedsParens));
- sb.append(" ");
+ sb.append(" ");
- final boolean argNeedsParens = app.argument() instanceof ApplicationExpression
- || app.argument() instanceof AbstractionExpression;
- sb.append(formatExpression(app.argument(), argNeedsParens));
+ final boolean argNeedsParens = app.argument() instanceof ApplicationExpression
+ || app.argument() instanceof AbstractionExpression;
+ sb.append(formatExpression(app.argument(), argNeedsParens));
- if (needsParens) {
- sb.append(")");
- }
+ if (needsParens) {
+ sb.append(")");
+ }
- return sb.toString();
- }
+ return sb.toString();
+ }
- private String formatArrowApplication(final ApplicationExpression app) {
- final StringBuilder sb = new StringBuilder();
+ private String formatArrowApplication(final ApplicationExpression app) {
+ final StringBuilder sb = new StringBuilder();
- Expression func = app.applicable();
- final List<Expression> args = new ArrayList<>();
- args.add(app.argument());
+ Expression func = app.applicable();
+ final List<Expression> args = new ArrayList<>();
+ args.add(app.argument());
- while (func instanceof ApplicationExpression appFunc) {
- args.addFirst(appFunc.argument());
- func = appFunc.applicable();
- }
+ while (func instanceof ApplicationExpression appFunc) {
+ args.addFirst(appFunc.argument());
+ func = appFunc.applicable();
+ }
- final boolean funcNeedsParens = func instanceof AbstractionExpression;
- if (funcNeedsParens) {
- sb.append("(");
- }
- sb.append(formatExpression(func, false));
- if (funcNeedsParens) {
- sb.append(")");
- }
+ final boolean funcNeedsParens = func instanceof AbstractionExpression;
+ if (funcNeedsParens) {
+ sb.append("(");
+ }
+ sb.append(formatExpression(func, false));
+ if (funcNeedsParens) {
+ sb.append(")");
+ }
- for (final Expression arg : args) {
- sb.append("(");
- sb.append(formatExpression(arg, false));
- sb.append(")");
- }
+ for (final Expression arg : args) {
+ sb.append("(");
+ sb.append(formatExpression(arg, false));
+ sb.append(")");
+ }
- return sb.toString();
- }
+ return sb.toString();
+ }
- /**
- * Formats a program in the specified syntax.
- */
- public static String emit(final LambdaProgram program, final Syntax syntax) {
- return new Formatter(syntax).format(program);
- }
+ /**
+ * Formats a program in the specified syntax.
+ */
+ public static String emit(final LambdaProgram program, final Syntax syntax) {
+ return new Formatter(syntax).format(program);
+ }
}