diff options
Diffstat (limited to 'core/src/main/java/coffee/liz/lambda')
5 files changed, 215 insertions, 11 deletions
diff --git a/core/src/main/java/coffee/liz/lambda/LambdaDriver.java b/core/src/main/java/coffee/liz/lambda/LambdaDriver.java index 59cee25..475e14a 100644 --- a/core/src/main/java/coffee/liz/lambda/LambdaDriver.java +++ b/core/src/main/java/coffee/liz/lambda/LambdaDriver.java @@ -71,9 +71,14 @@ public class LambdaDriver { * @return the evaluated result */ public static Value interpret(final SourceCode sourceCode, final List<ExternalBinding> bindings) { + return interpret(sourceCode, bindings, Environment.root()); + } + + public static Value interpret(final SourceCode sourceCode, final List<ExternalBinding> bindings, + final Environment baseEnvironment) { final LambdaProgram program = parse(sourceCode); final Expression expression = program.expression(); final List<Macro> macros = program.macros(); - return NormalOrderEvaluator.evaluate(expression, Environment.from(macros, bindings)); + return NormalOrderEvaluator.evaluate(expression, baseEnvironment.extend(Environment.from(macros, bindings))); } } 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 a4ec24a..5178385 100644 --- a/core/src/main/java/coffee/liz/lambda/eval/Environment.java +++ b/core/src/main/java/coffee/liz/lambda/eval/Environment.java @@ -4,9 +4,11 @@ import coffee.liz.lambda.ast.Expression; import coffee.liz.lambda.ast.Macro; import coffee.liz.lambda.bind.ExternalBinding; import jakarta.annotation.Nullable; +import lombok.Builder; import lombok.RequiredArgsConstructor; import java.util.List; +import java.util.ArrayList; import java.util.Map; import java.util.Optional; import java.util.function.Function; @@ -17,6 +19,7 @@ import java.util.stream.Collectors; * Runtime environment for variable bindings, macros, and external bindings. */ @RequiredArgsConstructor +@Builder(toBuilder = true) public final class Environment { /** Named expansions */ private final Map<String, Expression> macros; @@ -64,6 +67,10 @@ public final class Environment { return new Environment(macros, externalBindings, name, value, this); } + public Environment extend(final Environment other) { + return other.toBuilder().parent(this).build(); + } + /** * Looks up a name, checking bindings, then macros, then external bindings. * @@ -93,6 +100,20 @@ public final class Environment { } /** + * Returns local binding frames from nearest scope to farthest. + */ + public List<BindingFrame> bindingFrames() { + final List<BindingFrame> frames = new ArrayList<>(); + for (Environment env = this; env != null; env = env.parent) { + if (env.boundName == null || env.boundValue == null) { + continue; + } + frames.add(new BindingFrame(env.boundName, env.boundValue)); + } + return List.copyOf(frames); + } + + /** * Result of looking up a name in the environment. */ public sealed interface LookupResult { @@ -106,4 +127,11 @@ public final class Environment { record External(ExternalBinding binding) implements LookupResult { } } + + public record BindingFrame(String name, Supplier<Value> value) { + } + + public static Environment root() { + return new Environment(Map.of(), Map.of(), null, null, null); + } } 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 d9bcba3..4587f4b 100644 --- a/core/src/main/java/coffee/liz/lambda/eval/NormalOrderEvaluator.java +++ b/core/src/main/java/coffee/liz/lambda/eval/NormalOrderEvaluator.java @@ -11,10 +11,7 @@ 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. + * Evaluates lambda expressions using normal order reduction. */ public final class NormalOrderEvaluator { 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 e4fbc0c..ab6f4db 100644 --- a/core/src/main/java/coffee/liz/lambda/format/Formatter.java +++ b/core/src/main/java/coffee/liz/lambda/format/Formatter.java @@ -15,9 +15,7 @@ import java.util.ArrayList; import java.util.List; import java.util.Optional; -/** - * Formats lambda calculus ASTs. - */ +/** Formats lambda calculus ASTs. */ @RequiredArgsConstructor public final class Formatter { @@ -62,7 +60,7 @@ public final class Formatter { && comment.span().startColumn() > program.expression().span().startColumn(); if (!isTrailingComment) { - inlinePartAlreadyOutput = previousEnd != null && comment.isInlineAfter(previousEnd); + inlinePartAlreadyOutput = comment.isInlineAfter(previousEnd); final String leadingPart = getLeadingCommentPart(comment, previousEnd); if (!leadingPart.isEmpty()) { @@ -94,7 +92,7 @@ public final class Formatter { * element). */ private String getInlineCommentPart(final SourceComment comment, final SourceSpan previousEnd) { - if (previousEnd == null || !comment.isInlineAfter(previousEnd)) { + if (!comment.isInlineAfter(previousEnd)) { return ""; } final String text = comment.text(); @@ -106,7 +104,7 @@ public final class Formatter { * 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)) { + if (!comment.isInlineAfter(previousEnd)) { return comment.text(); } final String text = comment.text(); diff --git a/core/src/main/java/coffee/liz/lambda/format/ValueEmitter.java b/core/src/main/java/coffee/liz/lambda/format/ValueEmitter.java new file mode 100644 index 0000000..337beed --- /dev/null +++ b/core/src/main/java/coffee/liz/lambda/format/ValueEmitter.java @@ -0,0 +1,176 @@ +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.SourceCode; +import coffee.liz.lambda.ast.SourceSpan; +import coffee.liz.lambda.eval.Environment; +import coffee.liz.lambda.eval.Value; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.HashSet; +import java.util.LinkedHashMap; +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.Set; +import java.util.function.Supplier; + +/** Emits runtime values back into source code. */ +public final class ValueEmitter { + private ValueEmitter() { + } + + public static SourceCode emit(final Value value, final SourceCode.Syntax syntax) { + final ProgramFragment fragment = toProgramFragment(value, new NameGenerator()); + final LambdaProgram program = new LambdaProgram(SourceSpan.UNKNOWN, fragment.macros(), fragment.expression()); + final String rendered = Formatter.emit(program, syntax); + return switch (syntax) { + case LAMBDA -> SourceCode.ofLambda(rendered); + case ARROW -> SourceCode.ofArrow(rendered); + }; + } + + private static ProgramFragment toProgramFragment(final Value value, final NameGenerator nameGenerator) { + return switch (value) { + case Value.Free(String name) -> new ProgramFragment(List.of(), identifier(name)); + case Value.Application(Value function, Value argument) -> { + final ProgramFragment functionFragment = toProgramFragment(function, nameGenerator); + final ProgramFragment argumentFragment = toProgramFragment(argument, nameGenerator); + final List<Macro> macros = new ArrayList<>(functionFragment.macros()); + macros.addAll(argumentFragment.macros()); + yield new ProgramFragment(macros, + application(functionFragment.expression(), argumentFragment.expression())); + } + case Value.Closure(Environment env, String parameter, Expression body) -> + emitClosure(env, parameter, body, nameGenerator); + }; + } + + private static ProgramFragment emitClosure(final Environment env, final String parameter, final Expression body, + final NameGenerator nameGenerator) { + final LinkedHashMap<String, Supplier<Value>> captures = captures(env); + if (captures.isEmpty()) { + return new ProgramFragment(List.of(), abstraction(parameter, sanitizeExpression(body))); + } + + final Set<String> reservedNames = collectIdentifiers(body); + final Map<String, ProgramFragment> captureFragments = new LinkedHashMap<>(); + for (final Map.Entry<String, Supplier<Value>> capture : captures.entrySet()) { + final ProgramFragment fragment = toProgramFragment(capture.getValue().get(), nameGenerator); + captureFragments.put(capture.getKey(), fragment); + reservedNames.addAll(collectIdentifiers(fragment.expression())); + fragment.macros().forEach(macro -> reservedNames.add(macro.name())); + } + + final Map<String, String> renamedCaptures = new HashMap<>(); + for (final String captureName : captures.keySet()) { + final String generated = nameGenerator.freshCaptureName(reservedNames); + reservedNames.add(generated); + renamedCaptures.put(captureName, generated); + } + + final List<Macro> macros = new ArrayList<>(); + for (final String captureName : captures.keySet()) { + final ProgramFragment fragment = captureFragments.get(captureName); + macros.addAll(fragment.macros()); + macros.add(new Macro(Optional.empty(), SourceSpan.UNKNOWN, renamedCaptures.get(captureName), + renameFreeIdentifiers(fragment.expression(), renamedCaptures, Set.of()))); + } + + final Set<String> bound = new HashSet<>(); + bound.add(parameter); + final Expression rewrittenBody = renameFreeIdentifiers(sanitizeExpression(body), renamedCaptures, bound); + return new ProgramFragment(macros, abstraction(parameter, rewrittenBody)); + } + + private static LinkedHashMap<String, Supplier<Value>> captures(final Environment env) { + final LinkedHashMap<String, Supplier<Value>> captures = new LinkedHashMap<>(); + for (final Environment.BindingFrame frame : env.bindingFrames()) { + captures.putIfAbsent(frame.name(), frame.value()); + } + return captures; + } + + private static Expression renameFreeIdentifiers(final Expression expression, final Map<String, String> renameMap, + final Set<String> boundNames) { + return switch (expression) { + case IdentifierExpression(var _, var _, String name) -> { + if (boundNames.contains(name) || !renameMap.containsKey(name)) { + yield identifier(name); + } + yield identifier(renameMap.get(name)); + } + case ApplicationExpression(var _, var _, Expression applicable, Expression argument) -> + application(renameFreeIdentifiers(applicable, renameMap, boundNames), + renameFreeIdentifiers(argument, renameMap, boundNames)); + case AbstractionExpression(var _, var _, String parameter, Expression body) -> { + final Set<String> nestedBound = new HashSet<>(boundNames); + nestedBound.add(parameter); + yield abstraction(parameter, renameFreeIdentifiers(body, renameMap, nestedBound)); + } + }; + } + + private static Expression sanitizeExpression(final Expression expression) { + return switch (expression) { + case IdentifierExpression(var _, var _, String name) -> identifier(name); + case ApplicationExpression(var _, var _, Expression applicable, Expression argument) -> + application(sanitizeExpression(applicable), sanitizeExpression(argument)); + case AbstractionExpression(var _, var _, String parameter, Expression body) -> + abstraction(parameter, sanitizeExpression(body)); + }; + } + + private static Set<String> collectIdentifiers(final Expression expression) { + final Set<String> identifiers = new HashSet<>(); + collectIdentifiers(expression, identifiers); + return identifiers; + } + + private static void collectIdentifiers(final Expression expression, final Set<String> identifiers) { + switch (expression) { + case IdentifierExpression(var _, var _, String name) -> identifiers.add(name); + case ApplicationExpression(var _, var _, Expression applicable, Expression argument) -> { + collectIdentifiers(applicable, identifiers); + collectIdentifiers(argument, identifiers); + } + case AbstractionExpression(var _, var _, String parameter, Expression body) -> { + identifiers.add(parameter); + collectIdentifiers(body, identifiers); + } + } + } + + private static IdentifierExpression identifier(final String name) { + return new IdentifierExpression(Optional.empty(), SourceSpan.UNKNOWN, name); + } + + private static ApplicationExpression application(final Expression function, final Expression argument) { + return new ApplicationExpression(Optional.empty(), SourceSpan.UNKNOWN, function, argument); + } + + private static AbstractionExpression abstraction(final String parameter, final Expression body) { + return new AbstractionExpression(Optional.empty(), SourceSpan.UNKNOWN, parameter, body); + } + + private record ProgramFragment(List<Macro> macros, Expression expression) { + } + + private static final class NameGenerator { + private int nextCapture = 0; + + private String freshCaptureName(final Set<String> reservedNames) { + String candidate; + do { + candidate = "_cap" + nextCapture++; + } while (reservedNames.contains(candidate)); + return candidate; + } + } +} |