- rt01_.val: For values in the only datatype in 01_, a list of bits. I included the trampoline() method, which must be called before evaluation, to avoid stack overflows, and to allow discarded values to be garbage collected.
- rt01_.constant: For literal constants. I decided on representing the constant as a string of 0 and 1, since strings are the only way to represent arbitrary length constants in the Java class file format without needing initialization code to construct it. Additionally, the same string in the constant pool could be reused as the name of the field holding that constant. Compiling to Java means the field names have to be valid Java identifiers, but they don't have to be when compiling directly to Java class files.
- rt01_.concat: For the only operation in 01_, list concatenation.
- rt01_.input: For reading input as a list of bits.
- rt01_.function: To be extended by classes representing 01_ functions. They should receive their arguments in the constructor, and build their results in eval(), and have a main() for being invoked from the command line.
Then, to test it out, I started with using it to write an interpreter. At first, it was getting OutOfMemoryErrors. I had written Function.eval() as
public rt01_.function eval(final rt01_.val[] args) {
return new rt01_.function() {
protected rt01_.val eval() {
for (Def def : defs) {
rt01_.val val = def.eval(args);
if (val != null)
return val;
}
throw new RuntimeException(...);
}
};
}
The capture of args in the anonymous class prevented the arguments from being garbage collected. Once I fixed that, the interpreter ran much faster than my previous interpreter in Java, faster than my interpreter in C, and even slightly faster than my interpreter in Haskell. Once I implemented the interpreter, it was a simple matter to extend it to compile to Java. The compiled code was maybe 5-10% faster than the interpreter.
I want to compile directly to class files rather than to Java, which will take a lot more work. This interpreter and compiler to Java was pretty much a weekend hack. I imagine the generated code would be pretty much the same as compiling to Java. The main difference is that the function names wouldn't have to be as heavily mangled, since they would no longer have to be valid Java identifiers, and would not have to avoid Java reserved words. Also, the SourceFile and LineNumberTable attributes could point to the 01_ source.
Here is the runtime:
package rt01_;
public abstract class val {
protected val trampoline() {
return null;
}
public boolean nil() {
return false;
}
public abstract boolean head();
public abstract val tail();
public static final val NIL = new val() {
public boolean nil() {
return true;
}
public boolean head() {
throw new NullPointerException();
}
public val tail() {
throw new NullPointerException();
}
};
public static val trampoline(val val) {
for (val v = val.trampoline(); v != null; v = val.trampoline())
val = v;
return val;
}
}
package rt01_;
public class constant extends val {
private String bits;
private int index;
private val tail = null;
public constant(String bits) {
this(bits, 0);
}
private constant(String bits, int index) {
this.bits = bits;
this.index = index;
}
protected val trampoline() {
if (index >= bits.length())
return NIL;
return null;
}
public boolean head() {
return '1' == bits.charAt(index);
}
public val tail() {
if (tail == null) {
if (index + 1 < bits.length())
tail = new constant(bits, index + 1);
else
tail = NIL;
}
return tail;
}
}
package rt01_;
public class concat extends val {
private val first;
private val second;
private val tail = null;
public concat(val first, val second) {
this.first = first;
this.second = second;
}
protected val trampoline() {
first = trampoline(first);
if (first.nil())
return second;
else
return null;
}
public boolean head() {
return first.head();
}
public val tail() {
if (tail == null)
tail = new concat(first.tail(), second);
return tail;
}
}
package rt01_;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.IOException;
public class input extends val {
private InputStream in;
private int byt;
private int bit;
private val tail = null;
public input(String file) throws IOException {
this(new FileInputStream(file));
}
public input(InputStream in) {
this(in, -1, 0);
}
private input(InputStream in, int byt, int bit) {
this.in = in;
this.byt = byt;
this.bit = bit;
}
protected val trampoline() {
if (bit == 0) {
try {
byt = in.read();
} catch (IOException e) {
throw new RuntimeException(e);
}
if (byt < 0)
return NIL;
bit = 128;
}
return null;
}
public boolean head() {
return (byt & bit) != 0;
}
public val tail() {
if (tail == null)
tail = new input(in, byt, bit >> 1);
return tail;
}
}
package rt01_;
import java.io.OutputStream;
import java.io.PrintStream;
public abstract class function extends val {
private val val = null;
protected val trampoline() {
if (val == null)
val = eval();
return val;
}
protected abstract val eval();
public boolean nil() {
throw new RuntimeException();
}
public boolean head() {
throw new RuntimeException();
}
public val tail() {
throw new RuntimeException();
}
public static void main(String[] args, int arity, String name) throws Exception {
Class<?>[] types = new Class<?>[arity];
for (int i = 0; i < arity; i++)
types[i] = val.class;
int index = 0;
boolean bits = false;
if (args.length > 0 && "-bits".equals(args[0])) {
index = 1;
bits = true;
}
val val = (function) Class.forName(name).getDeclaredConstructor(types).newInstance((Object[]) args(args, arity, index));
if (bits)
writeBits(val, System.out);
else
write(val, System.out);
System.out.flush();
}
public static val[] args(String[] args, int arity, int index) throws Exception {
val[] vals = new val[arity];
val stdin = null;
for (int i = 0; i < arity; i++) {
if (index + i < args.length) {
if (!"-".equals(args[index + i])) {
vals[i] = new input(args[index + i]);
} else {
if (stdin == null)
stdin = new input(System.in);
vals[i] = stdin;
}
} else if (stdin == null) {
stdin = new input(System.in);
vals[i] = stdin;
} else {
vals[i] = NIL;
}
}
return vals;
}
public static void writeBits(val val, PrintStream out) throws Exception {
for (;;) {
val = trampoline(val);
if (val.nil())
break;
out.print(val.head() ? "1" : "0");
val = val.tail();
}
}
public static void write(val val, OutputStream out) throws Exception {
int byt = 0;
int bit = 128;
for (;;) {
val = trampoline(val);
if (val.nil())
break;
byt |= val.head() ? bit : 0;
bit >>= 1;
if (bit == 0) {
out.write(byt);
byt = 0;
bit = 128;
}
val = val.tail();
}
}
}
Here is the interpreter and compiler to Java:
public class BoundExpr extends Expr {
private int index;
public BoundExpr(Token token, int index) {
super(token);
this.index = index;
}
public rt01_.val eval(rt01_.val[] bindings) {
return bindings[index];
}
public int getIndex() {
return index;
}
}
import java.io.FileWriter;
import java.io.PrintWriter;
public class Compiler {
public static void main(String[] args) throws Exception {
Parser parser = new Parser();
for (String arg : args)
parser.add(arg);
for (Function function : parser.getFunctions().values()) {
PrintWriter out = new PrintWriter(new FileWriter(function.getMangledName() + ".java"));
function.compile(out);
out.flush();
out.close();
}
}
}
public class ConcatExpr extends Expr {
private Expr first;
private Expr second;
public ConcatExpr(Expr first, Expr second) {
super(first.getToken());
this.first = first;
this.second = second;
}
public rt01_.val eval(rt01_.val[] bindings) {
return new rt01_.concat(first.eval(bindings), second.eval(bindings));
}
public Expr getFirst() {
return first;
}
public Expr getSecond() {
return second;
}
}
import java.util.List;
public class ConstantExpr extends Expr {
private String bits;
private rt01_.constant val;
public ConstantExpr(Token token, boolean[] bits) {
super(token);
StringBuilder sb = new StringBuilder();
for (boolean bit : bits)
sb.append(bit ? "1" : "0");
this.bits = sb.toString();
val = new rt01_.constant(this.bits);
}
public rt01_.val eval(rt01_.val[] bindings) {
return val;
}
public String getBits() {
return bits;
}
}
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Map;
public class Def {
private Token name;
private Pattern[] patterns;
private Token[] body;
private int bindingCount;
private Expr expr;
public Def(Token name, Pattern[] patterns, Token[] body) {
this.name = name;
this.patterns = patterns;
this.body = body;
bindingCount = 0;
for (Pattern pattern : patterns)
if (pattern.isBinding())
bindingCount++;
}
public int getArity() {
return patterns.length;
}
public Token getName() {
return name;
}
private class ParseState {
int index;
Expr expr;
}
public void parse(Map<String,Function> functions) {
if (body.length == 0) {
expr = new ConstantExpr(name, new boolean[0]);
} else {
ParseState state = new ParseState();
state.index = 0;
state.expr = null;
parse(functions, state);
expr = state.expr;
}
body = null;
}
private void parse(Map<String,Function> functions, ParseState state) {
state.expr = null;
parse1(functions, state);
if (state.index < body.length) {
Expr first = state.expr;
parse(functions, state);
state.expr = new ConcatExpr(first, state.expr);
}
}
private void parse1(Map<String,Function> functions, ParseState state) {
Token token = body[state.index];
switch (token.getType()) {
case EQUALS: case DOT:
assert false;
throw new RuntimeException();
case ZERO: case ONE: case NIL:
parseConstant(token, state);
return;
case SYMBOL:
state.index++;
state.expr = binding(token);
if (state.expr != null)
return;
if (!functions.containsKey(token.getSymbol()))
throw new RuntimeException(token.getLocation() + ": unknown function: " + token.getSymbol());
Function function = functions.get(token.getSymbol());
Expr[] args = new Expr[function.getArity()];
for (int i = 0; i < args.length; i++) {
parse1(functions, state);
args[i] = state.expr;
}
state.expr = new FuncallExpr(token, function, args);
}
}
private void parseConstant(Token token, ParseState state) {
ArrayList<Boolean> bits = new ArrayList<Boolean>();
loop: while (state.index < body.length) {
switch (body[state.index].getType()) {
case ZERO:
state.index++;
bits.add(false);
break;
case ONE:
state.index++;
bits.add(true);
break;
case NIL:
state.index++;
default:
break loop;
}
}
state.expr = new ConstantExpr(token, DefReader.toBitArray(bits));
}
private BoundExpr binding(Token token) {
int bindingIndex = 0;
for (Pattern pattern : patterns) {
if (!pattern.isBinding())
continue;
if (pattern.getToken().getSymbol().equals(token.getSymbol()))
return new BoundExpr(token, bindingIndex);
bindingIndex++;
}
return null;
}
public Expr getExpr() {
return expr;
}
public rt01_.val eval(rt01_.val[] args) {
assert args.length == patterns.length;
rt01_.val[] bindings = new rt01_.val[bindingCount];
int bindingIndex = 0;
for (int i = 0; i < args.length; i++) {
rt01_.val val = patterns[i].match(args[i]);
if (val == null)
return null;
if (patterns[i].isBinding())
bindings[bindingIndex++] = val;
}
return expr.eval(bindings);
}
public void compile(int n, PrintWriter out) throws Exception {
out.print(" private rt01_.val m");
out.print(n);
out.println("() {");
if (patterns.length > 0)
out.println(" rt01_.val val;");
int bindingIndex = 0;
for (int i = 0; i < patterns.length; i++) {
Pattern pattern = patterns[i];
boolean[] bits = pattern.getBits();
if (bits.length > 0) {
out.print(" a");
out.print(i);
out.print(" = trampoline(a");
out.print(i);
out.println(");");
}
out.print(" val = a");
out.print(i);
out.println(";");
boolean start = true;
for (boolean bit : bits) {
if (start)
start = false;
else
out.println(" val = trampoline(val);");
out.print(" if (val.nil() || ");
if (bit) out.print("!");
out.println("val.head()) return null;");
out.println(" val = val.tail();");
}
if (pattern.isLiteral()) {
out.println(" val = trampoline(val);");
out.println(" if (!val.nil()) return null;");
} else if (pattern.isBinding()) {
out.print(" rt01_.val b");
out.print(bindingIndex);
out.println(" = val;");
bindingIndex++;
}
}
out.print(" return ");
compileExpr(expr, out);
out.println(";");
out.println(" }");
}
private void compileExpr(Expr e, PrintWriter out) throws Exception {
if (e instanceof BoundExpr) {
out.print("b");
out.print(((BoundExpr) e).getIndex());
} else if (e instanceof ConstantExpr) {
out.print("_");
out.print(((ConstantExpr) e).getBits());
} else if (e instanceof ConcatExpr) {
out.print("new rt01_.concat(");
compileExpr(((ConcatExpr) e).getFirst(), out);
out.print(",");
compileExpr(((ConcatExpr) e).getSecond(), out);
out.print(")");
} else if (e instanceof FuncallExpr) {
out.print("new ");
out.print(((FuncallExpr) e).getFunction().getMangledName());
out.print("(");
boolean start = true;
for (Expr arg : ((FuncallExpr) e).getArgs()) {
if (start)
start = false;
else
out.print(",");
compileExpr(arg, out);
}
out.print(")");
}
}
}
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class DefReader implements Iterator<Def> {
private Iterator<Token> tokenizer;
private Def def = null;
public DefReader(Iterator<Token> tokenizer) {
this.tokenizer = tokenizer;
}
public boolean hasNext() {
if (def == null)
def = readNext();
return def != null;
}
public Def next() {
if (def == null)
return readNext();
Def result = def;
def = null;
return result;
}
public void remove() {
}
private Def readNext() {
if (!tokenizer.hasNext())
return null;
Token name = tokenizer.next();
if (name.getType() != Token.Type.SYMBOL)
throw new RuntimeException(name.getLocation() + ": symbol expected");
ArrayList<Pattern> patterns = readPatterns(name);
ArrayList<Token> body = new ArrayList<Token>();
for (;;) {
if (!tokenizer.hasNext())
throw new RuntimeException(name.getLocation() + ": incomplete definition");
Token token = tokenizer.next();
if (token.getType() == Token.Type.DOT)
break;
body.add(token);
}
return new Def(name, patterns.toArray(new Pattern[patterns.size()]), body.toArray(new Token[body.size()]));
}
private ArrayList<Pattern> readPatterns(Token name) {
ArrayList<Pattern> patterns = new ArrayList<Pattern>();
ArrayList<Boolean> bits = new ArrayList<Boolean>();
Token startToken = null;
for (;;) {
if (!tokenizer.hasNext())
throw new RuntimeException(name.getLocation() + ": incomplete definition");
Token token = tokenizer.next();
if (startToken == null)
startToken = token;
switch (token.getType()) {
case EQUALS:
if (bits.size() > 0)
patterns.add(new Pattern(startToken, toBitArray(bits), null));
return patterns;
case ZERO:
bits.add(false);
break;
case ONE:
bits.add(true);
break;
case DOT:
case NIL:
case SYMBOL:
patterns.add(new Pattern(startToken, toBitArray(bits), token));
bits.clear();
startToken = null;
break;
}
}
}
public static boolean[] toBitArray(List<Boolean> list) {
boolean[] bits = new boolean[list.size()];
for (int i = 0; i < list.size(); i++)
bits[i] = list.get(i);
return bits;
}
}
public abstract class Expr {
private Token token;
protected Expr(Token token) {
this.token = token;
}
public abstract rt01_.val eval(rt01_.val[] bindings);
public Token getToken() {
return token;
}
}
public class FuncallExpr extends Expr {
private Function function;
private Expr[] args;
public FuncallExpr(Token token, Function function, Expr[] args) {
super(token);
this.function = function;
this.args = args;
}
public rt01_.val eval(rt01_.val[] bindings) {
rt01_.val[] argVals = new rt01_.val[args.length];
for (int i = 0; i < argVals.length; i++)
argVals[i] = args[i].eval(bindings);
return function.eval(argVals);
}
public Function getFunction() {
return function;
}
public Expr[] getArgs() {
return args;
}
}
import java.io.File;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Map;
public class Function {
private Def[] defs;
public Function(Def[] defs) {
this.defs = defs;
}
public int getArity() {
return defs[0].getArity();
}
public void parse(Map<String,Function> functions) {
for (Def def : defs)
def.parse(functions);
}
private class Result extends rt01_.function {
private rt01_.val[] args;
Result(rt01_.val[] args) {
this.args = args;
}
protected rt01_.val eval() {
for (Def def : defs) {
rt01_.val val = def.eval(args);
if (val != null) {
args = null; // let arguments get garbage collected
return val;
}
}
Token name = defs[defs.length-1].getName();
throw new RuntimeException(name.getLocation() + ": no matching pattern in definition of " + name.getSymbol());
}
}
public rt01_.function eval(rt01_.val[] args) {
return new Result(args);
}
private static final HashSet<String> reserved = new HashSet<String>();
static {
reserved.add("abstract");
reserved.add("assert");
reserved.add("boolean");
reserved.add("break");
reserved.add("byte");
reserved.add("case");
reserved.add("catch");
reserved.add("char");
reserved.add("class");
reserved.add("const");
reserved.add("continue");
reserved.add("default");
reserved.add("do");
reserved.add("double");
reserved.add("else");
reserved.add("enum");
reserved.add("extends");
reserved.add("false");
reserved.add("final");
reserved.add("finally");
reserved.add("float");
reserved.add("for");
reserved.add("goto");
reserved.add("if");
reserved.add("implements");
reserved.add("import");
reserved.add("instanceof");
reserved.add("int");
reserved.add("interface");
reserved.add("long");
reserved.add("native");
reserved.add("new");
reserved.add("null");
reserved.add("package");
reserved.add("private");
reserved.add("protected");
reserved.add("public");
reserved.add("return");
reserved.add("short");
reserved.add("static");
reserved.add("switch");
reserved.add("synchronized");
reserved.add("strictfp");
reserved.add("super");
reserved.add("this");
reserved.add("throw");
reserved.add("throws");
reserved.add("transient");
reserved.add("true");
reserved.add("try");
reserved.add("void");
reserved.add("volatile");
reserved.add("while");
}
public static String mangle(String name) {
StringBuilder sb = new StringBuilder();
if (reserved.contains(name))
sb.append("__");
for (int i = 0; i < name.length(); i++)
switch (name.charAt(i)) {
case '0': case '1': case '2': case '3': case '4': case '5':
case '6': case '7': case '8': case '9':
if (i == 0)
sb.append("__");
case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
case 'g': case 'h': case 'i': case 'j': case 'k': case 'l':
case 'm': case 'n': case 'o': case 'p': case 'q': case 'r':
case 's': case 't': case 'u': case 'v': case 'w': case 'x':
case 'y': case 'z':
case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
case 'G': case 'H': case 'I': case 'J': case 'K': case 'L':
case 'M': case 'N': case 'O': case 'P': case 'Q': case 'R':
case 'S': case 'T': case 'U': case 'V': case 'W': case 'X':
case 'Y': case 'Z':
sb.append(name.charAt(i));
break;
default:
sb.append('_').append(Integer.toHexString(name.charAt(i))).append('_');
}
return sb.toString();
}
public String getMangledName() {
return mangle(defs[0].getName().getSymbol());
}
public void compile(PrintWriter out) throws Exception {
int arity = getArity();
String name = getMangledName();
out.print("public class ");
out.print(name);
out.println(" extends rt01_.function {");
for (int i = 0; i < arity; i++) {
out.print(" private rt01_.val a");
out.print(i);
out.println(";");
}
out.print(" public ");
out.print(name);
out.print("(");
for (int i = 0; i < arity; i++) {
if (i > 0)
out.print(",");
out.print("rt01_.val p");
out.print(i);
}
out.println(") {");
for (int i = 0; i < arity; i++) {
out.print(" a");
out.print(i);
out.print("=p");
out.print(i);
out.println(";");
}
out.println(" }");
out.println(" protected rt01_.val eval() {");
out.println(" rt01_.val val;");
out.print(" if (");
for (int i = 0; i < defs.length; i++) {
out.print("(val = m");
out.print(i);
out.print("()) == null && ");
}
out.print("true) throw new RuntimeException(\"");
out.print(getLocation(defs[defs.length-1].getName()));
out.println(": pattern match failed\");");
for (int i = 0; i < arity; i++) {
out.print(" a");
out.print(i);
out.println(" = null;");
}
out.println(" return val;");
out.println(" }");
HashSet<String> constants = new HashSet<String>();
for (Def def : defs)
collectConstants(constants, def.getExpr());
for (String constant : constants) {
out.print(" private static final rt01_.val _");
out.print(constant);
if (constant.length() == 0) {
out.println(" = NIL;");
} else {
out.print(" = new rt01_.constant(\"");
out.print(constant);
out.println("\");");
}
}
for (int i = 0; i < defs.length; i++)
defs[i].compile(i, out);
out.println(" public static void main(String[] args) throws Exception {");
out.print(" main(args,");
out.print(arity);
out.print(",\"");
out.print(name);
out.println("\");");
out.println(" }");
out.println("}");
}
private void collectConstants(HashSet<String> constants, Expr expr) {
if (expr instanceof ConstantExpr) {
constants.add(((ConstantExpr) expr).getBits());
} else if (expr instanceof ConcatExpr) {
collectConstants(constants, ((ConcatExpr) expr).getFirst());
collectConstants(constants, ((ConcatExpr) expr).getSecond());
} else if (expr instanceof FuncallExpr) {
for (Expr arg : ((FuncallExpr) expr).getArgs())
collectConstants(constants, arg);
}
}
public static String getLocation(Token token) {
return new File(token.getFileName()).getName() + ":" + token.getLineNumber() + ":" + token.getColumn();
}
}
import java.io.File;
import java.util.Map;
public class Interpreter {
public static void main(String[] args) throws Exception {
Parser parser = new Parser();
int i;
String fname = null;
for (i = 0; i < args.length && !args[i].equals("-"); i++) {
parser.add(args[i]);
fname = getFunction(args[i]);
}
if (i + 1 < args.length) {
fname = args[i+1];
i = i + 2;
}
boolean writeBits = false;
if (i < args.length && "-bits".equals(args[i])) {
i++;
writeBits = true;
}
Function f = parser.getFunctions().get(fname);
if (writeBits)
rt01_.function.writeBits(f.eval(rt01_.function.args(args, f.getArity(), i)), System.out);
else
rt01_.function.write(f.eval(rt01_.function.args(args, f.getArity(), i)), System.out);
System.out.flush();
}
private static String getFunction(String fileName) {
String fn = new File(fileName).getName();
if (fn.indexOf('.') > 0)
return fn.substring(0, fn.indexOf('.'));
else
return fn;
}
}
import java.io.Reader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class Parser {
private HashMap<String,Integer> arities = new HashMap<String,Integer>();
private HashMap<String,List<Def>> functions = new HashMap<String,List<Def>>();
public void add(String fileName) throws Exception {
add(new Tokenizer(fileName));
}
public void add(Reader in, String fileName, int lineNumber, int column) {
add(new Tokenizer(in, fileName, lineNumber, column));
}
public void add(Iterator<Token> tokenizer) {
addDefs(new DefReader(tokenizer));
}
public void addDefs(Iterator<Def> defs) {
while (defs.hasNext()) {
Def def = defs.next();
Token name = def.getName();
if (arities.containsKey(name.getSymbol())) {
if (def.getArity() != arities.get(name.getSymbol()))
throw new RuntimeException(name.getLocation() + ": arity mismatch in definition of " + name.getSymbol());
} else {
arities.put(name.getSymbol(), def.getArity());
functions.put(name.getSymbol(), new ArrayList<Def>());
}
functions.get(name.getSymbol()).add(def);
}
}
public Map<String,Function> getFunctions() {
HashMap<String,Function> fns = new HashMap<String,Function>();
for (Map.Entry<String,List<Def>> entry : functions.entrySet()) {
List<Def> defs = entry.getValue();
fns.put(entry.getKey(), new Function(defs.toArray(new Def[defs.size()])));
}
for (Function function : fns.values())
function.parse(fns);
return fns;
}
}
public class Pattern {
private Token startToken;
private boolean[] bits;
private Token token;
private String fileName;
private int lineNumber;
public Pattern(Token startToken, boolean[] bits, Token token) {
this.startToken = startToken;
this.bits = bits;
this.token = token;
}
public Token getStartToken() {
return startToken;
}
public boolean[] getBits() {
return bits;
}
public Token getToken() {
return token;
}
public boolean isLiteral() {
return token == null || token.getType() == Token.Type.NIL;
}
public boolean isWild() {
return token != null && token.getType() == Token.Type.DOT;
}
public boolean isBinding() {
return token != null && token.getType() == Token.Type.SYMBOL;
}
public rt01_.val match(rt01_.val val) {
for (int i = 0; i < bits.length; i++) {
val = rt01_.val.trampoline(val);
if (val.nil() || val.head() != bits[i])
return null;
val = val.tail();
}
if (isLiteral()) {
val = rt01_.val.trampoline(val);
if (!val.nil())
return null;
}
return val;
}
}
public class Token {
public enum Type {
ZERO, ONE, NIL, DOT, EQUALS, SYMBOL
}
private Type type;
private String symbol;
private String fileName;
private int lineNumber;
private int column;
public Token(Type type, String symbol, String fileName, int lineNumber, int column) {
this.type = type;
this.symbol = symbol;
this.fileName = fileName;
this.lineNumber = lineNumber;
this.column = column;
}
public Type getType() {
return type;
}
public String getSymbol() {
return symbol;
}
public String getFileName() {
return fileName;
}
public int getLineNumber() {
return lineNumber;
}
public int getColumn() {
return column;
}
public String getLocation() {
return fileName + ":" + lineNumber + ":" + column;
}
}
import java.io.FileReader;
import java.io.Reader;
import java.util.Iterator;
public class Tokenizer implements Iterator<Token> {
private Reader in;
private String fileName;
private int lineNumber;
private int column = 0;
private int pushback = -1;
private Token next;
public Tokenizer(String fileName) throws Exception {
this(new FileReader(fileName), fileName, 1, 0);
}
public Tokenizer(Reader in, String fileName, int lineNumber, int column) {
this.in = in;
this.fileName = fileName;
this.lineNumber = lineNumber;
}
public boolean hasNext() {
if (next == null)
readNext();
return next != null;
}
public Token next() {
if (next == null)
readNext();
Token result = next;
next = null;
return result;
}
public void remove() {
}
private void pushback(int lastChar) {
assert pushback < 0;
pushback = lastChar;
column--;
if (lastChar == '\n')
lineNumber--;
}
private int nextChar() {
int nextChar = -1;
if (pushback >= 0) {
nextChar = pushback;
pushback = -1;
} else {
try {
nextChar = in.read();
} catch (Exception e) {
throw new RuntimeException(e);
}
}
if (nextChar >= 0) {
column++;
if (nextChar == '\n') {
lineNumber++;
column = 0;
}
}
return nextChar;
}
private void readNext() {
for (;;) {
int nextChar = nextChar();
if (nextChar < 0)
return;
int saveLineNumber = lineNumber;
int saveColumn = column;
switch (nextChar) {
case '0':
next = new Token(Token.Type.ZERO, null, fileName, lineNumber, column);
return;
case '1':
next = new Token(Token.Type.ONE, null, fileName, lineNumber, column);
return;
case '_':
next = new Token(Token.Type.NIL, null, fileName, lineNumber, column);
return;
case '.':
next = new Token(Token.Type.DOT, null, fileName, lineNumber, column);
return;
case '=':
nextChar = nextChar();
if (nextChar != '=') {
pushback(nextChar);
next = new Token(Token.Type.EQUALS, null, fileName, saveLineNumber, saveColumn);
return;
}
while (nextChar >= 0 && nextChar != '\n')
nextChar = nextChar();
continue;
case ' ': case '\t': case '\r': case '\n':
continue;
default:
StringBuilder sb = new StringBuilder();
sb.append((char) nextChar);
for (;;) {
nextChar = nextChar();
if (nextChar < 0) {
next = new Token(Token.Type.SYMBOL, sb.toString(), fileName, saveLineNumber, saveColumn);
return;
}
switch (nextChar) {
case '0': case '1': case '_': case '.': case '=':
case ' ': case '\t': case '\r': case '\n':
pushback(nextChar);
next = new Token(Token.Type.SYMBOL, sb.toString(), fileName, saveLineNumber, saveColumn);
return;
default:
sb.append((char) nextChar);
}
}
}
}
}
}
Here is 99 bottles of beer compiled to Java:
public class __2 extends rt01_.function {
private rt01_.val a0;
public __2(rt01_.val p0) {
a0=p0;
}
protected rt01_.val eval() {
rt01_.val val;
if ((val = m0()) == null && true) throw new RuntimeException("99.01_:5:1: pattern match failed");
a0 = null;
return val;
}
private static final rt01_.val _010 = new rt01_.constant("010");
private rt01_.val m0() {
rt01_.val val;
a0 = trampoline(a0);
val = a0;
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || !val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || !val.head()) return null;
val = val.tail();
rt01_.val b0 = val;
return new rt01_.concat(_010,b0);
}
public static void main(String[] args) throws Exception {
main(args,1,"__2");
}
}
public class __33r extends rt01_.function {
public __33r() {
}
protected rt01_.val eval() {
rt01_.val val;
if ((val = m0()) == null && true) throw new RuntimeException("99.01_:8:1: pattern match failed");
return val;
}
private static final rt01_.val _001000000110111101101110001000000111010001101000011001010010000001110111011000010110110001101100 = new rt01_.constant("001000000110111101101110001000000111010001101000011001010010000001110111011000010110110001101100");
private rt01_.val m0() {
return _001000000110111101101110001000000111010001101000011001010010000001110111011000010110110001101100;
}
public static void main(String[] args) throws Exception {
main(args,0,"__33r");
}
}
public class __4 extends rt01_.function {
private rt01_.val a0;
public __4(rt01_.val p0) {
a0=p0;
}
protected rt01_.val eval() {
rt01_.val val;
if ((val = m0()) == null && (val = m1()) == null && (val = m2()) == null && (val = m3()) == null && true) throw new RuntimeException("99.01_:14:1: pattern match failed");
a0 = null;
return val;
}
private static final rt01_.val _ = NIL;
private static final rt01_.val _1 = new rt01_.constant("1");
private static final rt01_.val _1001 = new rt01_.constant("1001");
private static final rt01_.val _0 = new rt01_.constant("0");
private rt01_.val m0() {
rt01_.val val;
a0 = trampoline(a0);
val = a0;
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (!val.nil()) return null;
return _1001;
}
private rt01_.val m1() {
rt01_.val val;
val = a0;
val = trampoline(val);
if (!val.nil()) return null;
return _;
}
private rt01_.val m2() {
rt01_.val val;
a0 = trampoline(a0);
val = a0;
if (val.nil() || val.head()) return null;
val = val.tail();
rt01_.val b0 = val;
return new rt01_.concat(_1,new __4(b0));
}
private rt01_.val m3() {
rt01_.val val;
a0 = trampoline(a0);
val = a0;
if (val.nil() || !val.head()) return null;
val = val.tail();
rt01_.val b0 = val;
return new rt01_.concat(_0,b0);
}
public static void main(String[] args) throws Exception {
main(args,1,"__4");
}
}
public class __5 extends rt01_.function {
private rt01_.val a0;
private rt01_.val a1;
public __5(rt01_.val p0,rt01_.val p1) {
a0=p0;
a1=p1;
}
protected rt01_.val eval() {
rt01_.val val;
if ((val = m0()) == null && (val = m1()) == null && (val = m2()) == null && (val = m3()) == null && true) throw new RuntimeException("99.01_:20:1: pattern match failed");
a0 = null;
a1 = null;
return val;
}
private static final rt01_.val _00110001 = new rt01_.constant("00110001");
private static final rt01_.val _01101110011011110010000001101101011011110111001001100101 = new rt01_.constant("01101110011011110010000001101101011011110111001001100101");
private static final rt01_.val _0011 = new rt01_.constant("0011");
private static final rt01_.val _01110011 = new rt01_.constant("01110011");
private rt01_.val m0() {
rt01_.val val;
a0 = trampoline(a0);
val = a0;
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
a1 = trampoline(a1);
val = a1;
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (!val.nil()) return null;
return new rt01_.concat(_01101110011011110010000001101101011011110111001001100101,new rt01_.concat(new __7(),_01110011));
}
private rt01_.val m1() {
rt01_.val val;
a0 = trampoline(a0);
val = a0;
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
a1 = trampoline(a1);
val = a1;
if (val.nil() || !val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (!val.nil()) return null;
return new rt01_.concat(_00110001,new __7());
}
private rt01_.val m2() {
rt01_.val val;
a0 = trampoline(a0);
val = a0;
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = a1;
rt01_.val b0 = val;
return new rt01_.concat(_0011,new rt01_.concat(new __6(b0),new rt01_.concat(new __7(),_01110011)));
}
private rt01_.val m3() {
rt01_.val val;
val = a0;
rt01_.val b0 = val;
val = a1;
rt01_.val b1 = val;
return new rt01_.concat(_0011,new rt01_.concat(new __6(b0),new rt01_.concat(_0011,new rt01_.concat(new __6(b1),new rt01_.concat(new __7(),_01110011)))));
}
public static void main(String[] args) throws Exception {
main(args,2,"__5");
}
}
public class __6 extends rt01_.function {
private rt01_.val a0;
public __6(rt01_.val p0) {
a0=p0;
}
protected rt01_.val eval() {
rt01_.val val;
if ((val = m0()) == null && (val = m1()) == null && (val = m2()) == null && true) throw new RuntimeException("99.01_:25:1: pattern match failed");
a0 = null;
return val;
}
private static final rt01_.val _ = NIL;
private static final rt01_.val _1 = new rt01_.constant("1");
private static final rt01_.val _0 = new rt01_.constant("0");
private rt01_.val m0() {
rt01_.val val;
val = a0;
val = trampoline(val);
if (!val.nil()) return null;
return _;
}
private rt01_.val m1() {
rt01_.val val;
a0 = trampoline(a0);
val = a0;
if (val.nil() || val.head()) return null;
val = val.tail();
rt01_.val b0 = val;
return new rt01_.concat(new __6(b0),_0);
}
private rt01_.val m2() {
rt01_.val val;
a0 = trampoline(a0);
val = a0;
if (val.nil() || !val.head()) return null;
val = val.tail();
rt01_.val b0 = val;
return new rt01_.concat(new __6(b0),_1);
}
public static void main(String[] args) throws Exception {
main(args,1,"__6");
}
}
public class __7 extends rt01_.function {
public __7() {
}
protected rt01_.val eval() {
rt01_.val val;
if ((val = m0()) == null && true) throw new RuntimeException("99.01_:28:1: pattern match failed");
return val;
}
private static final rt01_.val _00100000011000100110111101110100011101000110110001100101 = new rt01_.constant("00100000011000100110111101110100011101000110110001100101");
private rt01_.val m0() {
return _00100000011000100110111101110100011101000110110001100101;
}
public static void main(String[] args) throws Exception {
main(args,0,"__7");
}
}
public class __8 extends rt01_.function {
private rt01_.val a0;
private rt01_.val a1;
public __8(rt01_.val p0,rt01_.val p1) {
a0=p0;
a1=p1;
}
protected rt01_.val eval() {
rt01_.val val;
if ((val = m0()) == null && (val = m1()) == null && true) throw new RuntimeException("99.01_:32:1: pattern match failed");
a0 = null;
a1 = null;
return val;
}
private rt01_.val m0() {
rt01_.val val;
val = a0;
rt01_.val b0 = val;
a1 = trampoline(a1);
val = a1;
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (!val.nil()) return null;
return new __4(b0);
}
private rt01_.val m1() {
rt01_.val val;
val = a0;
rt01_.val b0 = val;
val = a1;
return b0;
}
public static void main(String[] args) throws Exception {
main(args,2,"__8");
}
}
public class __9 extends rt01_.function {
private rt01_.val a0;
private rt01_.val a1;
public __9(rt01_.val p0,rt01_.val p1) {
a0=p0;
a1=p1;
}
protected rt01_.val eval() {
rt01_.val val;
if ((val = m0()) == null && (val = m1()) == null && true) throw new RuntimeException("99.01_:36:1: pattern match failed");
a0 = null;
a1 = null;
return val;
}
private static final rt01_.val _1001 = new rt01_.constant("1001");
private static final rt01_.val _0010110000100000 = new rt01_.constant("0010110000100000");
private static final rt01_.val _001011100000101001010100011000010110101101100101001000000110111101101110011001010010000001100100011011110111011101101110001000000110000101101110011001000010000001110000011000010111001101110011001000000110100101110100001000000110000101110010011011110111010101101110011001000010110000100000 = new rt01_.constant("001011100000101001010100011000010110101101100101001000000110111101101110011001010010000001100100011011110111011101101110001000000110000101101110011001000010000001110000011000010111001101110011001000000110100101110100001000000110000101110010011011110111010101101110011001000010110000100000");
private static final rt01_.val _0010111000001010 = new rt01_.constant("0010111000001010");
private static final rt01_.val _0000 = new rt01_.constant("0000");
private static final rt01_.val _00101110000010100100011101101111001000000111010001101111001000000111010001101000011001010010000001110011011101000110111101110010011001010010000001100001011011100110010000100000011000100111010101111001001000000111001101101111011011010110010100100000011011010110111101110010011001010010110000100000 = new rt01_.constant("00101110000010100100011101101111001000000111010001101111001000000111010001101000011001010010000001110011011101000110111101110010011001010010000001100001011011100110010000100000011000100111010101111001001000000111001101101111011011010110010100100000011011010110111101110010011001010010110000100000");
private static final rt01_.val _001011100000101000001010 = new rt01_.constant("001011100000101000001010");
private rt01_.val m0() {
rt01_.val val;
a0 = trampoline(a0);
val = a0;
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
a1 = trampoline(a1);
val = a1;
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (val.nil() || val.head()) return null;
val = val.tail();
val = trampoline(val);
if (!val.nil()) return null;
return new rt01_.concat(new __2(new __5(_0000,_0000)),new rt01_.concat(new b(),new rt01_.concat(new __33r(),new rt01_.concat(_0010110000100000,new rt01_.concat(new __5(_0000,_0000),new rt01_.concat(new b(),new rt01_.concat(_00101110000010100100011101101111001000000111010001101111001000000111010001101000011001010010000001110011011101000110111101110010011001010010000001100001011011100110010000100000011000100111010101111001001000000111001101101111011011010110010100100000011011010110111101110010011001010010110000100000,new rt01_.concat(new __5(_1001,_1001),new rt01_.concat(new b(),new rt01_.concat(new __33r(),_0010111000001010))))))))));
}
private rt01_.val m1() {
rt01_.val val;
val = a0;
rt01_.val b0 = val;
val = a1;
rt01_.val b1 = val;
return new rt01_.concat(new __5(b0,b1),new rt01_.concat(new b(),new rt01_.concat(new __33r(),new rt01_.concat(_0010110000100000,new rt01_.concat(new __5(b0,b1),new rt01_.concat(new b(),new rt01_.concat(_001011100000101001010100011000010110101101100101001000000110111101101110011001010010000001100100011011110111011101101110001000000110000101101110011001000010000001110000011000010111001101110011001000000110100101110100001000000110000101110010011011110111010101101110011001000010110000100000,new rt01_.concat(new __5(new __8(b0,b1),new __4(b1)),new rt01_.concat(new b(),new rt01_.concat(new __33r(),new rt01_.concat(_001011100000101000001010,new __9(new __8(b0,b1),new __4(b1)))))))))))));
}
public static void main(String[] args) throws Exception {
main(args,2,"__9");
}
}
public class __99 extends rt01_.function {
public __99() {
}
protected rt01_.val eval() {
rt01_.val val;
if ((val = m0()) == null && true) throw new RuntimeException("99.01_:38:1: pattern match failed");
return val;
}
private static final rt01_.val _1001 = new rt01_.constant("1001");
private rt01_.val m0() {
return new __9(_1001,_1001);
}
public static void main(String[] args) throws Exception {
main(args,0,"__99");
}
}
public class b extends rt01_.function {
public b() {
}
protected rt01_.val eval() {
rt01_.val val;
if ((val = m0()) == null && true) throw new RuntimeException("99.01_:2:1: pattern match failed");
return val;
}
private static final rt01_.val _0010000001101111011001100010000001100010011001010110010101110010 = new rt01_.constant("0010000001101111011001100010000001100010011001010110010101110010");
private rt01_.val m0() {
return _0010000001101111011001100010000001100010011001010110010101110010;
}
public static void main(String[] args) throws Exception {
main(args,0,"b");
}
}
