feat: Adding ValueEmitter, LambdaEvaluatorSystem

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;
+        }
+    }
+}