diff options
Diffstat (limited to 'core/src/main/java/coffee/liz/lambda')
18 files changed, 1400 insertions, 0 deletions
diff --git a/core/src/main/java/coffee/liz/lambda/LambdaDriver.java b/core/src/main/java/coffee/liz/lambda/LambdaDriver.java new file mode 100644 index 0000000..2ba8c70 --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/LambdaDriver.java @@ -0,0 +1,79 @@ +package coffee.liz.lambda; + +import coffee.liz.lambda.parser.ArrowParser; +import coffee.liz.lambda.parser.LambdaParser; +import coffee.liz.lambda.parser.ParseException; +import coffee.liz.lambda.ast.Expression; +import coffee.liz.lambda.ast.LambdaProgram; +import coffee.liz.lambda.ast.Macro; +import coffee.liz.lambda.ast.SourceCode; +import coffee.liz.lambda.bind.ExternalBinding; +import coffee.liz.lambda.eval.Environment; +import coffee.liz.lambda.eval.NormalOrderEvaluator; +import coffee.liz.lambda.eval.Value; + +import java.io.StringReader; +import java.util.List; + +/** + * Entry point for parsing and interpreting lambda calculus programs. + */ +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); + }; + } + + 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); + } + } + + /** + * 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)); + } +} diff --git a/core/src/main/java/coffee/liz/lambda/ast/Expression.java b/core/src/main/java/coffee/liz/lambda/ast/Expression.java new file mode 100644 index 0000000..6d75a08 --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/ast/Expression.java @@ -0,0 +1,28 @@ +package coffee.liz.lambda.ast; + +import lombok.NonNull; + +import java.util.Optional; + +/** + * Represents an expression in the untyped lambda calculus. + */ +public sealed interface Expression + permits Expression.AbstractionExpression, Expression.IdentifierExpression, Expression.ApplicationExpression { + + Optional<SourceComment> comment(); + + SourceSpan span(); + + 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 IdentifierExpression(@NonNull Optional<SourceComment> comment, @NonNull SourceSpan span, + @NonNull String name) implements Expression { + } +} diff --git a/core/src/main/java/coffee/liz/lambda/ast/LambdaProgram.java b/core/src/main/java/coffee/liz/lambda/ast/LambdaProgram.java new file mode 100644 index 0000000..efd4c03 --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/ast/LambdaProgram.java @@ -0,0 +1,19 @@ +package coffee.liz.lambda.ast; + +import lombok.NonNull; + +import java.util.List; + +/** + * A complete lambda calculus program consisting of macro definitions and a main + * expression. + * + * @param span + * source span covering the entire program + * @param macros + * named macro definitions that can be referenced in the expression + * @param expression + * the main expression to evaluate + */ +public record LambdaProgram(@NonNull SourceSpan span, @NonNull List<Macro> macros, @NonNull Expression 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 new file mode 100644 index 0000000..07ba911 --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/ast/Macro.java @@ -0,0 +1,12 @@ +package coffee.liz.lambda.ast; + +import lombok.NonNull; + +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) { +} diff --git a/core/src/main/java/coffee/liz/lambda/ast/SourceCode.java b/core/src/main/java/coffee/liz/lambda/ast/SourceCode.java new file mode 100644 index 0000000..200c45e --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/ast/SourceCode.java @@ -0,0 +1,27 @@ +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 ofArrow(final String source) { + return new Arrow(source); + } + + record Lambda(String source) implements SourceCode { + } + + record Arrow(String source) implements SourceCode { + } + + /** + * 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 new file mode 100644 index 0000000..da6b5ab --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/ast/SourceComment.java @@ -0,0 +1,21 @@ +package coffee.liz.lambda.ast; + +import lombok.NonNull; + +/** + * A comment with its source location; inline vs leading direction. + * + * @param text + * the comment text content + * @param span + * the source location of the comment + */ +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(); + } +} diff --git a/core/src/main/java/coffee/liz/lambda/ast/SourceSpan.java b/core/src/main/java/coffee/liz/lambda/ast/SourceSpan.java new file mode 100644 index 0000000..7df9bcd --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/ast/SourceSpan.java @@ -0,0 +1,24 @@ +package coffee.liz.lambda.ast; + +/** + * Span of source code with start and end positions. + * + * @param startLine + * 1-based line number where the span starts + * @param startColumn + * 1-based column number where the span starts + * @param endLine + * 1-based line number where the span ends + * @param endColumn + * 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); + + /** + * 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 new file mode 100644 index 0000000..4895972 --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/bind/ExternalBinding.java @@ -0,0 +1,23 @@ +package coffee.liz.lambda.bind; + +import coffee.liz.lambda.eval.Environment; +import coffee.liz.lambda.eval.Value; + +import java.util.function.BiFunction; + +/** + * Interface for external Java functions callable from lambda expressions. + * + * <p> + * Implementations receive the current environment and an argument value, and + * return a result value. + */ +public interface ExternalBinding extends BiFunction<Environment, Value, Value> { + + /** + * 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 new file mode 100644 index 0000000..0fa4de5 --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/bind/Tick.java @@ -0,0 +1,22 @@ +package coffee.liz.lambda.bind; + +import coffee.liz.lambda.eval.Environment; +import coffee.liz.lambda.eval.Value; +import lombok.Getter; + +import java.util.concurrent.atomic.AtomicInteger; + +/** + * Identity function that has a side effect which internally counts invocations. + */ +@Getter +public class Tick implements ExternalBinding { + 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; + } +} diff --git a/core/src/main/java/coffee/liz/lambda/bind/ToChurch.java b/core/src/main/java/coffee/liz/lambda/bind/ToChurch.java new file mode 100644 index 0000000..bfddd86 --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/bind/ToChurch.java @@ -0,0 +1,49 @@ +package coffee.liz.lambda.bind; + +import coffee.liz.lambda.ast.Expression; +import coffee.liz.lambda.ast.Expression.IdentifierExpression; +import coffee.liz.lambda.ast.Expression.AbstractionExpression; +import coffee.liz.lambda.ast.Expression.ApplicationExpression; +import coffee.liz.lambda.ast.SourceSpan; +import coffee.liz.lambda.eval.Environment; + +import java.util.Optional; +import coffee.liz.lambda.eval.Value; +import coffee.liz.lambda.eval.Value.Free; +import coffee.liz.lambda.eval.Value.Closure; +import lombok.Getter; + +/** + * Converts an integer to its Church numeral representation. + * + * <p> + * Church numerals encode n as {@code λf.λx.f(f(...f(x)...))} with n + * applications of f. + */ +@Getter +public class ToChurch implements ExternalBinding { + 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()); + + 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)); + } +} diff --git a/core/src/main/java/coffee/liz/lambda/eval/Environment.java b/core/src/main/java/coffee/liz/lambda/eval/Environment.java new file mode 100644 index 0000000..8854719 --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/eval/Environment.java @@ -0,0 +1,109 @@ +package coffee.liz.lambda.eval; + +import coffee.liz.lambda.ast.Expression; +import coffee.liz.lambda.ast.Macro; +import coffee.liz.lambda.bind.ExternalBinding; +import jakarta.annotation.Nullable; +import lombok.RequiredArgsConstructor; + +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.function.Function; +import java.util.function.Supplier; +import java.util.stream.Collectors; + +/** + * Runtime environment for variable bindings, macros, and external bindings. + */ +@RequiredArgsConstructor +public final class Environment { + /** Named expansions */ + private final Map<String, Expression> macros; + + /** "FFI" */ + private final Map<String, ExternalBinding> externalBindings; + + /** 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; + + /** 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 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)); + } + + 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)); + } + + 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 { + } + } +} diff --git a/core/src/main/java/coffee/liz/lambda/eval/EvaluationDepthExceededException.java b/core/src/main/java/coffee/liz/lambda/eval/EvaluationDepthExceededException.java new file mode 100644 index 0000000..7926004 --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/eval/EvaluationDepthExceededException.java @@ -0,0 +1,16 @@ +package coffee.liz.lambda.eval; + +import lombok.Getter; + +/** + * Thrown before we get a {@link StackOverflowError}, hopefully. + */ +@Getter +public final class EvaluationDepthExceededException extends RuntimeException { + private final int 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 new file mode 100644 index 0000000..28eb69b --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/eval/NormalOrderEvaluator.java @@ -0,0 +1,101 @@ +package coffee.liz.lambda.eval; + +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.bind.ExternalBinding; +import coffee.liz.lambda.eval.Environment.LookupResult; +import coffee.liz.lambda.eval.Value.Application; +import coffee.liz.lambda.eval.Value.Closure; +import coffee.liz.lambda.eval.Value.Free; + +/** + * Evaluates lambda expressions using normal order (lazy) reduction. + * + * <p> + * Arguments are wrapped in {@link Thunk} and only evaluated when needed. + */ +public final class NormalOrderEvaluator { + + 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 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); + } + + 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 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); + } + + 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 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 new file mode 100644 index 0000000..07c89bf --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/eval/Thunk.java @@ -0,0 +1,27 @@ +package coffee.liz.lambda.eval; + +import lombok.RequiredArgsConstructor; + +import java.util.function.Supplier; + +/** + * A memoizing thunk for lazy evaluation. + * + * @param <T> + * Thunk type + */ +@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; + + @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 new file mode 100644 index 0000000..58b9ba4 --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/eval/Value.java @@ -0,0 +1,42 @@ +package coffee.liz.lambda.eval; + +import coffee.liz.lambda.ast.Expression; + +/** + * Represents a runtime value produced by evaluation. + */ +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 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 { + } +} diff --git a/core/src/main/java/coffee/liz/lambda/format/Formatter.java b/core/src/main/java/coffee/liz/lambda/format/Formatter.java new file mode 100644 index 0000000..1ac3e95 --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/format/Formatter.java @@ -0,0 +1,238 @@ +package coffee.liz.lambda.format; + +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.SourceComment; +import coffee.liz.lambda.ast.SourceSpan; +import lombok.RequiredArgsConstructor; +import coffee.liz.lambda.ast.SourceCode.Syntax; + +import java.util.ArrayList; +import java.util.List; +import java.util.Optional; + +/** + * Formats lambda calculus ASTs. + */ +@RequiredArgsConstructor +public final class Formatter { + + private final Syntax syntax; + + 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); + + 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(";"); + + final Optional<String> inlineComment = getInlineCommentAfter(macro.span(), program, i); + inlineComment.ifPresent(c -> sb.append(" ").append(c)); + sb.append("\n"); + + previousEnd = macro.span(); + } + + boolean isTrailingComment = false; + boolean inlinePartAlreadyOutput = false; + + 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(); + + 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"); + } + + sb.append(formatExpression(program.expression(), false)); + + if (program.expression().comment().isPresent() && !inlinePartAlreadyOutput && isTrailingComment) { + sb.append(" ").append(program.expression().comment().get().text()); + } + + 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 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(); + } + + 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(); + + 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(); + } + + 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(); + + if (needsParens) { + sb.append("("); + } + + final boolean funcNeedsParens = app.applicable() instanceof AbstractionExpression; + sb.append(formatExpression(app.applicable(), funcNeedsParens)); + + sb.append(" "); + + final boolean argNeedsParens = app.argument() instanceof ApplicationExpression + || app.argument() instanceof AbstractionExpression; + sb.append(formatExpression(app.argument(), argNeedsParens)); + + if (needsParens) { + sb.append(")"); + } + + return sb.toString(); + } + + 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()); + + 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(")"); + } + + for (final Expression arg : args) { + sb.append("("); + sb.append(formatExpression(arg, false)); + sb.append(")"); + } + + 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); + } +} diff --git a/core/src/main/java/coffee/liz/lambda/parser/ArrowParser.jjt b/core/src/main/java/coffee/liz/lambda/parser/ArrowParser.jjt new file mode 100644 index 0000000..9ad9099 --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/parser/ArrowParser.jjt @@ -0,0 +1,276 @@ +options { + STATIC = false; + LOOKAHEAD = 2; + UNICODE_INPUT = true; + NODE_PREFIX = "AST"; +} + +PARSER_BEGIN(ArrowParser) +package coffee.liz.lambda.parser; + +import java.util.ArrayList; +import java.util.List; +import java.util.Optional; +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.Expression; +import coffee.liz.lambda.ast.SourceSpan; +import coffee.liz.lambda.ast.SourceComment; + +public class ArrowParser { + public static void main(final String[] args) throws Exception { + final ArrowParser parser = new ArrowParser(System.in); + final LambdaProgram program = parser.Program(); + System.out.println(program); + } + + private static SourceSpan spanFrom(final Token start, final Token end) { + return new SourceSpan(start.beginLine, start.beginColumn, end.endLine, end.endColumn); + } + + private static SourceSpan spanFrom(final Token start, final Expression end) { + return new SourceSpan(start.beginLine, start.beginColumn, end.span().endLine(), end.span().endColumn()); + } + + private static SourceSpan spanFromInts(final int startLine, final int startColumn, final Token end) { + return new SourceSpan(startLine, startColumn, end.endLine, end.endColumn); + } + + private static SourceSpan spanFromInts(final int startLine, final int startColumn, final Expression end) { + return new SourceSpan(startLine, startColumn, end.span().endLine(), end.span().endColumn()); + } + + private static Expression withComment(final Expression expr, final Optional<SourceComment> comment) { + if (comment.isEmpty()) { + return expr; + } + if (expr instanceof AbstractionExpression) { + final AbstractionExpression a = (AbstractionExpression) expr; + return new AbstractionExpression(comment, a.span(), a.parameter(), a.body()); + } + if (expr instanceof ApplicationExpression) { + final ApplicationExpression a = (ApplicationExpression) expr; + return new ApplicationExpression(comment, a.span(), a.applicable(), a.argument()); + } + if (expr instanceof IdentifierExpression) { + final IdentifierExpression a = (IdentifierExpression) expr; + return new IdentifierExpression(comment, a.span(), a.name()); + } + return expr; + } + + private static Expression withSpan(final Expression expr, final SourceSpan span) { + if (expr instanceof AbstractionExpression) { + final AbstractionExpression a = (AbstractionExpression) expr; + return new AbstractionExpression(a.comment(), span, a.parameter(), a.body()); + } + if (expr instanceof ApplicationExpression) { + final ApplicationExpression a = (ApplicationExpression) expr; + return new ApplicationExpression(a.comment(), span, a.applicable(), a.argument()); + } + if (expr instanceof IdentifierExpression) { + final IdentifierExpression a = (IdentifierExpression) expr; + return new IdentifierExpression(a.comment(), span, a.name()); + } + return expr; + } + + private static Expression withCommentAndSpan(final Expression expr, final Optional<SourceComment> comment, final SourceSpan span) { + if (expr instanceof AbstractionExpression) { + final AbstractionExpression a = (AbstractionExpression) expr; + return new AbstractionExpression(comment, span, a.parameter(), a.body()); + } + if (expr instanceof ApplicationExpression) { + final ApplicationExpression a = (ApplicationExpression) expr; + return new ApplicationExpression(comment, span, a.applicable(), a.argument()); + } + if (expr instanceof IdentifierExpression) { + final IdentifierExpression a = (IdentifierExpression) expr; + return new IdentifierExpression(comment, span, a.name()); + } + return expr; + } + + private static Optional<SourceComment> extractComment(final Token t) { + if (t == null || t.specialToken == null) { + return Optional.empty(); + } + Token st = t.specialToken; + while (st.specialToken != null) { + st = st.specialToken; + } + final Token firstComment = st; + final StringBuilder sb = new StringBuilder(); + Token lastComment = st; + int lastEndLine = 0; + while (st != null) { + if (sb.length() > 0) { + final int blankLines = st.beginLine - lastEndLine - 1; + for (int i = 0; i < blankLines; i++) { + sb.append("\n"); + } + sb.append("\n"); + } + String image = st.image; + while (image.endsWith("\n") || image.endsWith("\r")) { + image = image.substring(0, image.length() - 1); + } + sb.append(image); + lastEndLine = st.endLine; + lastComment = st; + st = st.next; + } + final SourceSpan span = new SourceSpan( + firstComment.beginLine, firstComment.beginColumn, + lastComment.endLine, lastComment.endColumn + ); + return Optional.of(new SourceComment(sb.toString(), span)); + } +} +PARSER_END(ArrowParser) + +SKIP : { + " " | "\t" | "\r" | "\n" +} + +SPECIAL_TOKEN : { + < COMMENT: "--" (~["\n","\r"])* ("\n"|"\r"|"\r\n")? > +} + +TOKEN : { + < LET: "let" > + | < ARROW: "->" > + | < EQ: "=" > + | < SEMI: ";" > + | < LPAREN: "(" > + | < RPAREN: ")" > + | < IDENT: (["a"-"z","A"-"Z","0"-"9","_"])+ > +} + +LambdaProgram Program() : +{ + final List<Macro> macros = new ArrayList<Macro>(); + Macro m; + Expression body; + Token eofToken; + Optional<SourceComment> eofComment; +} +{ + ( + m = Macro() + { macros.add(m); } + )* + body = Expression() + eofToken = <EOF> + { eofComment = extractComment(eofToken); } + { + final SourceSpan span; + if (!macros.isEmpty()) { + span = spanFromInts(macros.get(0).span().startLine(), macros.get(0).span().startColumn(), eofToken); + } else { + span = new SourceSpan(body.span().startLine(), body.span().startColumn(), eofToken.endLine, eofToken.endColumn); + } + if (eofComment.isPresent() && body.comment().isEmpty()) { + body = withComment(body, eofComment); + } + return new LambdaProgram(span, macros, body); + } +} + +Macro Macro() : +{ + Token letToken; + Token name; + Token semiToken; + Expression value; + Optional<SourceComment> comment; +} +{ + letToken = <LET> + { comment = extractComment(letToken); } + name = <IDENT> + <EQ> + value = Expression() + semiToken = <SEMI> + { + return new Macro(comment, spanFrom(letToken, semiToken), name.image, value); + } +} + +Expression Expression() : +{ + Token paramToken; + Expression e; + Expression body; + Optional<SourceComment> comment; +} +{ + ( + LOOKAHEAD(<IDENT> <ARROW>) + paramToken = <IDENT> + { comment = extractComment(paramToken); } + <ARROW> + body = Expression() + { + e = new AbstractionExpression(comment, spanFrom(paramToken, body), paramToken.image, body); + } + | + e = Application() + ) + { + return e; + } +} + +Expression Application() : +{ + Expression e; + Expression arg; + Token rparen; +} +{ + e = Atom() + ( + <LPAREN> + arg = Expression() + rparen = <RPAREN> + { + e = new ApplicationExpression(Optional.empty(), spanFromInts(e.span().startLine(), e.span().startColumn(), rparen), e, arg); + } + )* + { + return e; + } +} + +Expression Atom() : +{ + Token id; + Token lparen; + Token rparen; + Expression e; + Optional<SourceComment> comment; +} +{ + id = <IDENT> + { comment = extractComment(id); } + { + return new IdentifierExpression(comment, spanFrom(id, id), id.image); + } +| + lparen = <LPAREN> + { comment = extractComment(lparen); } + e = Expression() + rparen = <RPAREN> + { + final SourceSpan parenSpan = spanFrom(lparen, rparen); + if (comment.isPresent() && e.comment().isEmpty()) { + return withCommentAndSpan(e, comment, parenSpan); + } + return withSpan(e, parenSpan); + } +} + diff --git a/core/src/main/java/coffee/liz/lambda/parser/LambdaParser.jjt b/core/src/main/java/coffee/liz/lambda/parser/LambdaParser.jjt new file mode 100644 index 0000000..2482960 --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/parser/LambdaParser.jjt @@ -0,0 +1,287 @@ +options { + STATIC = false; + LOOKAHEAD = 2; + UNICODE_INPUT = true; + NODE_PREFIX = "AST"; +} + +PARSER_BEGIN(LambdaParser) +package coffee.liz.lambda.parser; + +import java.util.ArrayList; +import java.util.List; +import java.util.Optional; +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.Expression; +import coffee.liz.lambda.ast.SourceSpan; +import coffee.liz.lambda.ast.SourceComment; + +public class LambdaParser { + public static void main(final String[] args) throws Exception { + final LambdaParser parser = new LambdaParser(System.in); + final LambdaProgram program = parser.Program(); + System.out.println(program); + } + + private static SourceSpan spanFrom(final Token start, final Token end) { + return new SourceSpan(start.beginLine, start.beginColumn, end.endLine, end.endColumn); + } + + private static SourceSpan spanFrom(final Token start, final Expression end) { + return new SourceSpan(start.beginLine, start.beginColumn, end.span().endLine(), end.span().endColumn()); + } + + private static SourceSpan spanFromInts(final int startLine, final int startColumn, final Token end) { + return new SourceSpan(startLine, startColumn, end.endLine, end.endColumn); + } + + private static SourceSpan spanFromInts(final int startLine, final int startColumn, final Expression end) { + return new SourceSpan(startLine, startColumn, end.span().endLine(), end.span().endColumn()); + } + + private static Expression withComment(final Expression expr, final Optional<SourceComment> comment) { + if (comment.isEmpty()) { + return expr; + } + if (expr instanceof AbstractionExpression) { + final AbstractionExpression a = (AbstractionExpression) expr; + return new AbstractionExpression(comment, a.span(), a.parameter(), a.body()); + } + if (expr instanceof ApplicationExpression) { + final ApplicationExpression a = (ApplicationExpression) expr; + return new ApplicationExpression(comment, a.span(), a.applicable(), a.argument()); + } + if (expr instanceof IdentifierExpression) { + final IdentifierExpression a = (IdentifierExpression) expr; + return new IdentifierExpression(comment, a.span(), a.name()); + } + return expr; + } + + private static Expression withSpan(final Expression expr, final SourceSpan span) { + if (expr instanceof AbstractionExpression) { + final AbstractionExpression a = (AbstractionExpression) expr; + return new AbstractionExpression(a.comment(), span, a.parameter(), a.body()); + } + if (expr instanceof ApplicationExpression) { + final ApplicationExpression a = (ApplicationExpression) expr; + return new ApplicationExpression(a.comment(), span, a.applicable(), a.argument()); + } + if (expr instanceof IdentifierExpression) { + final IdentifierExpression a = (IdentifierExpression) expr; + return new IdentifierExpression(a.comment(), span, a.name()); + } + return expr; + } + + private static Expression withCommentAndSpan(final Expression expr, final Optional<SourceComment> comment, final SourceSpan span) { + if (expr instanceof AbstractionExpression) { + final AbstractionExpression a = (AbstractionExpression) expr; + return new AbstractionExpression(comment, span, a.parameter(), a.body()); + } + if (expr instanceof ApplicationExpression) { + final ApplicationExpression a = (ApplicationExpression) expr; + return new ApplicationExpression(comment, span, a.applicable(), a.argument()); + } + if (expr instanceof IdentifierExpression) { + final IdentifierExpression a = (IdentifierExpression) expr; + return new IdentifierExpression(comment, span, a.name()); + } + return expr; + } + + private static Optional<SourceComment> extractComment(final Token t) { + if (t == null || t.specialToken == null) { + return Optional.empty(); + } + Token st = t.specialToken; + while (st.specialToken != null) { + st = st.specialToken; + } + final Token firstComment = st; + final StringBuilder sb = new StringBuilder(); + Token lastComment = st; + int lastEndLine = 0; + while (st != null) { + if (sb.length() > 0) { + final int blankLines = st.beginLine - lastEndLine - 1; + for (int i = 0; i < blankLines; i++) { + sb.append("\n"); + } + sb.append("\n"); + } + String image = st.image; + while (image.endsWith("\n") || image.endsWith("\r")) { + image = image.substring(0, image.length() - 1); + } + sb.append(image); + lastEndLine = st.endLine; + lastComment = st; + st = st.next; + } + final SourceSpan span = new SourceSpan( + firstComment.beginLine, firstComment.beginColumn, + lastComment.endLine, lastComment.endColumn + ); + return Optional.of(new SourceComment(sb.toString(), span)); + } +} +PARSER_END(LambdaParser) + +SKIP : { + " " | "\t" | "\r" | "\n" +} + +SPECIAL_TOKEN : { + < COMMENT: "--" (~["\n","\r"])* ("\n"|"\r"|"\r\n")? > +} + +TOKEN : { + < LET: "let" > + | < LAMBDA: "λ" | "\\" > + | < DOT: "." > + | < EQ: "=" > + | < SEMI: ";" > + | < LPAREN: "(" > + | < RPAREN: ")" > + | < IDENT: (["a"-"z","A"-"Z","0"-"9","_"])+ > +} + +LambdaProgram Program() : +{ + final List<Macro> macros = new ArrayList<Macro>(); + Macro m; + Expression body; + Token eofToken; + Optional<SourceComment> eofComment; +} +{ + ( + m = Macro() + { macros.add(m); } + )* + body = Expression() + eofToken = <EOF> + { eofComment = extractComment(eofToken); } + { + final SourceSpan span; + if (!macros.isEmpty()) { + span = spanFromInts(macros.get(0).span().startLine(), macros.get(0).span().startColumn(), eofToken); + } else { + span = new SourceSpan(body.span().startLine(), body.span().startColumn(), eofToken.endLine, eofToken.endColumn); + } + if (eofComment.isPresent() && body.comment().isEmpty()) { + body = withComment(body, eofComment); + } + return new LambdaProgram(span, macros, body); + } +} + +Macro Macro() : +{ + Token letToken; + Token name; + Token semiToken; + Expression value; + Optional<SourceComment> comment; +} +{ + letToken = <LET> + { comment = extractComment(letToken); } + name = <IDENT> + <EQ> + value = Expression() + semiToken = <SEMI> + { + return new Macro(comment, spanFrom(letToken, semiToken), name.image, value); + } +} + +Expression Expression() : +{ + Expression e; +} +{ + ( + e = Lambda() + | + e = Application() + ) + { + return e; + } +} + +Expression Lambda() : +{ + Token lambdaToken; + Token param; + Expression body; + Optional<SourceComment> comment; +} +{ + lambdaToken = <LAMBDA> + { comment = extractComment(lambdaToken); } + param = <IDENT> + <DOT> + body = Expression() + { + return new AbstractionExpression(comment, spanFrom(lambdaToken, body), param.image, body); + } +} + +Expression Application() : +{ + Expression e; + Expression arg; +} +{ + e = Atom() + ( + arg = Atom() + { + e = new ApplicationExpression(Optional.empty(), spanFromInts(e.span().startLine(), e.span().startColumn(), arg), e, arg); + } + )* + { + return e; + } +} + +Expression Atom() : +{ + Token id; + Token lparen; + Token rparen; + Expression e; + Optional<SourceComment> comment; +} +{ + id = <IDENT> + { comment = extractComment(id); } + { + return new IdentifierExpression(comment, spanFrom(id, id), id.image); + } +| + lparen = <LPAREN> + { comment = extractComment(lparen); } + e = Expression() + rparen = <RPAREN> + { + final SourceSpan parenSpan = spanFrom(lparen, rparen); + if (comment.isPresent() && e.comment().isEmpty()) { + return withCommentAndSpan(e, comment, parenSpan); + } + return withSpan(e, parenSpan); + } +| + e = Lambda() + { + return e; + } +} + |