data Flattened = HEAD | TAIL
flattened :: Value -> [Flattened]
flattened Nil = []
flattened (Cons head tail) = HEAD : flattened head ++ TAIL : flattened tail
I originally wrote the interpreter as multiple classes, but contained all of them as nested classes in a single class for this post. Some of the code would have been more straightforward had it been written recursively, but then larger data would cause stack overflows.
import java.io.EOFException;
import java.io.FileReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.OutputStream;
import java.io.Reader;
import java.util.EnumMap;
import java.util.Iterator;
import java.util.LinkedList;
public class phi {
public static class EnumTrie<K extends Enum<K>,V> {
private EnumMap<K,EnumTrie<K,V>> map;
private V value = null;
public EnumTrie(Class<K> keyType) {
map = new EnumMap<K,EnumTrie<K,V>>(keyType);
}
private EnumTrie(EnumTrie<K,V> trie) {
map = new EnumMap<K,EnumTrie<K,V>>(trie.map);
map.clear();
}
public V getValue() {
return value;
}
public EnumTrie<K,V> getSubtrie(K k) {
return map.get(k);
}
public EnumTrie<K,V> findPrefix(Iterator<K> iterator) {
EnumTrie<K,V> trie = this;
while (trie != null && iterator.hasNext())
trie = trie.map.get(iterator.next());
return trie;
}
public V get(Iterable<K> key) {
EnumTrie<K,V> trie = findPrefix(key.iterator());
return trie != null ? trie.value : null;
}
private EnumTrie<K,V> addPrefix(Iterator<K> iterator) {
EnumTrie<K,V> trie = this;
while (iterator.hasNext()) {
K k = iterator.next();
EnumTrie<K,V> subtrie = trie.map.get(k);
if (subtrie == null) {
subtrie = new EnumTrie<K,V>(trie);
trie.map.put(k, subtrie);
}
trie = subtrie;
}
return trie;
}
public V put(Iterable<K> key, V value) {
EnumTrie<K,V> trie;
if (value != null) {
trie = addPrefix(key.iterator());
} else {
trie = findPrefix(key.iterator());
if (trie == null)
return null;
}
trie.value = value;
return value;
}
}
public static abstract class Value implements Iterable<Value.Flattened> {
public enum Flattened { HEAD, TAIL }
public static final Value NIL = new NilValue();
public boolean isNil() {
return false;
}
public abstract Value getHead();
public abstract Value getTail();
public static Value read(Reader reader) throws IOException {
LinkedList<Value> stack = new LinkedList<Value>();
LinkedList<Boolean> open = new LinkedList<Boolean>();
for (;;) {
int c = reader.read();
if (c < 0) {
throw new EOFException();
} else if (c == '(') {
open.push(true);
} else if (c == ')') {
if (open.size() == 0)
throw new EOFException();
if (open.pop()) {
if (open.size() == 0)
return NIL;
open.push(false);
stack.push(NIL);
} else {
Value value = new Pair(stack.pop(), NIL);
while (!open.pop())
value = new Pair(stack.pop(), value);
if (open.size() == 0)
return value;
stack.push(value);
open.push(false);
}
}
}
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('(');
toString(sb);
sb.append(')');
return sb.toString();
}
private void toString(StringBuilder sb) {
if (!isNil()) {
sb.append('(');
getHead().toString(sb);
sb.append(')');
getTail().toString(sb);
}
}
public Iterator<Flattened> iterator() {
final LinkedList<Value> stack = new LinkedList<Value>();
return new Iterator<Flattened>() {
private Value value = Value.this;
public boolean hasNext() {
return !value.isNil() || stack.size() > 0;
}
public Flattened next() {
if (value.isNil()) {
value = stack.pop().getTail();
return Flattened.TAIL;
} else {
stack.push(value);
value = value.getHead();
return Flattened.HEAD;
}
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
private static class NilValue extends Value {
public boolean isNil() {
return true;
}
public Value getHead() {
return NilValue.this;
}
public Value getTail() {
return NilValue.this;
}
}
public static class Pair extends Value {
private Value head;
private Value tail;
public Pair(Value head, Value tail) {
this.head = head;
this.tail = tail;
}
public Value getHead() {
return head;
}
public Value getTail() {
return tail;
}
}
public static void write(Value value, OutputStream out) throws IOException {
int bit = 128;
int b = 0;
while (!value.isNil()) {
Value head = value.getHead();
if (head.isNil()) {
value = value.getTail();
} else {
b |= bit;
value = head;
}
if (bit == 1) {
out.write(b);
bit = 128;
b = 0;
} else {
bit >>= 1;
}
}
}
public static class InputValue extends Value {
private InputStream in;
private int bit;
private int b;
private Value head = null;
private Value tail = null;
public InputValue(InputStream in) {
this(in, 128, 0);
}
private InputValue(InputStream in, int bit, int b) {
this.in = in;
this.bit = bit;
this.b = b;
}
private void init() {
if (head == null) {
head = Value.NIL;
tail = Value.NIL;
if (bit == 0) {
try {
b = in.read();
} catch (IOException e) {
b = -1;
}
if (b < 0)
return;
bit = 128;
}
if ((b & bit) != 0)
head = new InputValue(in, bit>>1, b);
else
tail = new InputValue(in, bit>>1, b);
}
}
public Value getHead() {
init();
return head;
}
public Value getTail() {
init();
return tail;
}
}
}
public static class Scope {
private Scope outer;
private EnumTrie<Value.Flattened,Interp.Op> bindings;
private Value arg;
public Scope(Scope outer, EnumTrie<Value.Flattened,Interp.Op> bindings, Value arg) {
this.outer = outer;
this.bindings = bindings;
this.arg = arg;
}
public Value getArg() {
Scope scope = this;
while (scope.arg == null)
scope = scope.outer;
return scope.arg;
}
public Interp.Op getBinding(Value name) {
Scope scope = this;
while (scope != null) {
if (scope.bindings != null) {
Interp.Op op = scope.bindings.get(name);
if (op != null)
return op;
}
scope = scope.outer;
}
return null;
}
}
public static class Interp {
private Scope rootScope;
public Interp(Value input) {
rootScope = new Scope(null, rootBindings(), input);
}
public Value eval(Value expr) {
return eval(expr, rootScope);
}
protected Value eval(final Value expr, final Scope scope) {
if (expr.isNil())
return scope.getArg();
return new LazyValue() {
protected Value getValue() {
return scope.getBinding(expr.getHead()).op(expr.getTail(), scope);
}
};
}
public interface Op {
public Value op(Value expr, Scope scope);
}
private EnumTrie<Value.Flattened,Interp.Op> rootBindings() {
Value E3 = Value.NIL;
Value EE33 = new Value.Pair(E3,E3);
Value EE3E33 = new Value.Pair(E3,EE33);
Value EE3E3E33 = new Value.Pair(E3,EE3E33);
Value EEE333 = new Value.Pair(EE33,E3);
Value EEE33E33 = new Value.Pair(EE33,EE33);
Value EEEE3333 = new Value.Pair(EEE333,E3);
Value EE3EE333 = new Value.Pair(E3,EEE333);
EnumTrie<Value.Flattened,Interp.Op> rootBindings = new EnumTrie<Value.Flattened,Interp.Op>(Value.Flattened.class);
rootBindings.put(E3, new QuoteOp());
rootBindings.put(EE33, new LetOp());
rootBindings.put(EE3E33, new CdrOp());
rootBindings.put(EE3E3E33, new IfOp());
rootBindings.put(EEE333, new CarOp());
rootBindings.put(EEE33E33, new ConsOp());
rootBindings.put(EEEE3333, new EvalOp());
rootBindings.put(EE3EE333, new ConcatOp());
return rootBindings;
}
private class QuoteOp implements Op {
public Value op(Value arg, Scope scope) {
return arg;
}
}
private class LetOp implements Op {
public Value op(Value arg, Scope scope) {
EnumTrie<Value.Flattened,Interp.Op> bindings = new EnumTrie<Value.Flattened,Interp.Op>(Value.Flattened.class);
Scope letScope = new Scope(scope, bindings, null);
Value bindingList = arg.getHead();
while (!bindingList.isNil()) {
Value binding = bindingList.getHead();
bindingList = bindingList.getTail();
bindings.put(binding.getHead(), new DefinedOp(binding.getTail(), letScope));
}
return eval(arg.getTail(), letScope);
}
}
private class DefinedOp implements Op {
private Value body;
private Scope letScope;
public DefinedOp(Value body, Scope letScope) {
this.body = body;
this.letScope = letScope;
}
public Value op(final Value arg, final Scope scope) {
return eval(body, new Scope(letScope, null, eval(arg, scope)));
}
}
private class CdrOp implements Op {
public Value op(Value arg, Scope scope) {
return eval(arg, scope).getTail();
}
}
private class IfOp implements Op {
public Value op(Value arg, Scope scope) {
if (arg.isNil())
return Value.NIL;
Value body = arg.getTail();
if (body.isNil())
return Value.NIL;
if (eval(arg.getHead(), scope).isNil())
return eval(body.getTail(), scope);
else
return eval(body.getHead(), scope);
}
}
private class CarOp implements Op {
public Value op(Value arg, Scope scope) {
return eval(arg, scope).getHead();
}
}
private class ConsOp implements Op {
public Value op(Value arg, Scope scope) {
if (arg.isNil())
return Value.NIL;
return new Value.Pair(eval(arg.getHead(), scope), eval(arg.getTail(), scope));
}
}
private class EvalOp implements Op {
public Value op(Value arg, Scope scope) {
return eval(eval(arg, scope), scope);
}
}
private class ConcatOp implements Op {
public Value op(Value arg, Scope scope) {
if (arg.isNil())
return Value.NIL;
Value value = eval(arg.getHead(), scope);
Value rest = eval(arg.getTail(), scope);
LinkedList<Boolean> stack = new LinkedList<Boolean>();
LinkedList<Value> tails = new LinkedList<Value>();
for (;;) {
if (value.isNil())
break;
Value head = value.getHead();
Value tail = value.getTail();
if (head.isNil()) {
if (tail.isNil())
break;
stack.push(false);
value = tail;
} else {
stack.push(true);
tails.push(tail);
value = head;
}
}
while (!stack.isEmpty()) {
if (stack.pop())
rest = new Value.Pair(rest, tails.pop());
else
rest = new Value.Pair(Value.NIL, rest);
}
return rest;
}
}
private abstract class LazyValue extends Value {
private Value value = null;
protected abstract Value getValue();
public boolean isNil() {
if (value == null)
value = getValue();
return value.isNil();
}
public Value getHead() {
if (value == null)
value = getValue();
return value.getHead();
}
public Value getTail() {
if (value == null)
value = getValue();
return value.getTail();
}
}
}
public static void main(String[] args) throws Exception {
Value expr;
Value input;
if (args.length == 0) {
expr = Value.read(new InputStreamReader(System.in));
input = Value.NIL;
} else {
expr = Value.read(new FileReader(args[0]));
input = new Value.InputValue(System.in);
}
Value.write(new Interp(input).eval(expr), System.out);
System.out.flush();
}
}
No comments:
Post a Comment