Home > Java, Lisp, Scheme > Scheme interpreter in two days

Scheme interpreter in two days

Then I started to learn Scheme, I often saw people writing that Scheme interpreter could be build in several days. Such writings always make me feel stupid, because I can’t even think where to start writing Scheme interpreter. Finally, I decided to try and make a Scheme interpreter in Java, and it was unexpectingly easy! In two days I was able to make a very limited implementation, which is a good base for further improvement.
I’ve started my implementation from REPL, a loop which reads a line, evaluates the expression and prints results. My first day was not very productive in terms of code, but I did lots of thinking. Most diffucult task was to design parser for Lisp notation, which was very buggy.
On second day I’ve re-written my parser, and implemented evaluator, which was quite easy. Here are my results.
ListTools class performes list parsing and printing. Main idea is that parentheses are not part of list which is parsed, they are part of parent expression.

public class ListTools {
public static void printList(List list, Appendable out) throws IOException {
out.append(‘(‘);
for (Iterator it = list.iterator(); it.hasNext();) {
out.append(it.next().toString());
out.append(‘ ‘);
}
out.append(‘)’);
}
public static String printList(List list) {
StringBuffer sb = new StringBuffer();
try {
printList(list, sb);
} catch (IOException e) {
throw new RuntimeException(e);
}
return sb.toString();
}
public static int parseList(List list, CharSequence cs, int start) throws ListSyntaxError {
boolean inWord = false;
int elementStart = start-1;
int elementEnd = start-1;
int i = 0;
for (i = elementStart + 1; i = cs.length() || cs.charAt(i) != ‘)’) throw new ListSyntaxError(“List incomplete”, -1);
} else if (c == ‘)’) {
if (inWord) {
list.add(cs.subSequence(elementStart, i ));
}
return i;
} else {
if (!inWord) {
elementStart = i;
}
inWord = true;
}
}
if (inWord) {
list.add(cs.subSequence(elementStart, i));
}
return ++i;
}
public static List parseList(CharSequence cs) throws ListSyntaxError {
List result = new ArrayList();
int i = parseList(result, cs, 0);
if (i < cs.length() && cs.charAt(i) != ‘)’) throw new ListSyntaxError(“Unexpected ‘)’ at:” + i, i);
return result;
}
public static boolean isWhitespace(char c) {
return c == ‘ ‘ || c == ‘\t’ || c == ‘\r’ || c == ‘\n’;
}
}

And this class uses dedicated exception:

public class ListSyntaxError extends Exception {
public final int position;
public ListSyntaxError(String message, int pos) {
super(message);
position = pos;
}
}

Now I’ll show an evaluator:

public class Evaluator {
public static List evalAll(CharSequence cs, Map environment) throws ListSyntaxError {
List results = new ArrayList();
List expressions;
expressions = ListTools.parseList(cs);
for (Iterator it = expressions.iterator(); it.hasNext();) {
Object elem = it.next();
try {
Object result = eval(elem, environment, true);
if (result != null) results.add(result);
} catch (EvalError e) {
System.out.println(e.getMessage());
}
}
return results;
}
public static Object eval(Object elem, Map environment, boolean topLevel) throws EvalError {
Object result;
if (elem instanceof CharSequence) {
result = eval((CharSequence)elem, environment, topLevel);
} else if (elem instanceof List) {
result = eval((List)elem, environment, topLevel);
} else {
throw new EvalError(“Unknown type”);
}
return result;
}
public static Object eval(CharSequence cs, Map environment, boolean topLevel) throws EvalError {
// try numeric conversion
try {
int val = Integer.parseInt(cs.toString());
return String.valueOf(val);
} catch (NumberFormatException e) {
// do nothing
}
// check if symbol
if (cs.charAt(0) == ‘\”) {
return cs.subSequence(1, cs.length());
}
// now try to lookup in environment
Object result = environment.get(cs);
if (result == null) {
throw new EvalError(“Unbound variable: ” + cs);
} else {
if (result instanceof CharSequence) {
return (CharSequence)result;
} else if (result instanceof List) {
return ListTools.printList((List)result);
} else if (result instanceof Procedure) {
return result;
} else {
throw new EvalError(“Unknown type”);
}
}
}
public static Object eval(List list, Map environment, boolean topLevel) throws EvalError {
if (list.size() == 0) {
// hack from CL, null list evals to itself
return “()”;
} else {
Object car = list.get(0);
if (car instanceof CharSequence) {
if (car.toString().equals(“define”)) {
if (!topLevel) throw new EvalError(“invalid context for definition”);
if (list.size() != 3) throw new EvalError(“Wrong number of arguments for define”);
Object value = eval(list.get(2), environment, false);
if (value == null) throw new EvalError(“Argument could not be evaluated”);
environment.put(list.get(1), value);
return null;
} else if (car.toString().equals(“lambda”)) {
if (list.size() != 3) throw new EvalError(“Wrong number of arguments for lambda”);
if (!(list.get(1) instanceof List)) throw new EvalError(“Arguments for lambda should be lists”);
if (!(list.get(2) instanceof List)) throw new EvalError(“Arguments for lambda should be lists”);
return new CustomProcedure(((List)list.get(1)), environment, ((List)list.get(2)));
}

}
Object result = eval(car, environment, false);
if (result instanceof Procedure) {
return ((Procedure)result).eval(list, environment);
} else {
throw new EvalError(“Object is not a procedure”);
}
}
}
}

Evaluator also has a special exception:

public class EvalError extends Exception {
public EvalError(String message) {
super(message);
}
}

As you can see, Scheme procedures are implemented as instances of class Procedure:

public abstract class Procedure {
public Object eval(List arguments, Map environment) throws EvalError {
return null;
}
}

A good example of procedure is a “+”:

public class AddProcedure extends Procedure {
public Object eval(List arguments, Map environment) throws EvalError {
if (arguments.size() < 3) throw new EvalError(“Wrong number of arguments for +”);
int result = 0;
for (int j = 1; j < arguments.size(); j++) {
Object o = arguments.get(j);
try {
String val = Evaluator.eval(o, environment, false).toString();
if (val == null) throw new EvalError(“Argument could not be evaluated”);
result += Integer.parseInt(val);
} catch (Exception e) {
throw new EvalError(“Wrong argument for +”);
}
}
return String.valueOf(result);
}
}

Evaluation of “lambda” leads to creation of new instance of CustomProcedure:

public class CustomProcedure extends Procedure {
private final Map environment;
private final List expression;
private final List argNames;
public CustomProcedure(List argNames, Map environment, List expression) {
this.argNames = argNames;
this.environment = environment;
this.expression = expression;
}
public Object eval(List funcApplicationExpr, Map environment) throws EvalError {
Map copyEnv = new HashMap(this.environment);
Map arguments = putArguments(funcApplicationExpr);
copyEnv.putAll(arguments); // they override
return Evaluator.eval(expression, copyEnv, false);
}
private Map putArguments(List funcApplicationExpr) throws EvalError {
Map arguments = new HashMap();
int i;
for (i = 0; i = (funcApplicationExpr.size() – 1)) throw new EvalError(“Number of arguments is too small!”);
CharSequence argName = (CharSequence)argNames.get(i);
Object argValue = funcApplicationExpr.get(i + 1);
arguments.put(argName, argValue);
}
if (i ‘);
while (true) {
int size = in.available();
if (size > 0) {
byte[] data = new byte[size];
in.read(data);
sb.append(UTF_8_CHARSET.decode(ByteBuffer.wrap(data)));
List results = null;
try {
results = Evaluator.evalAll(sb, environment);
} catch (ListSyntaxError e) {
if (e.position == -1) {
continue;
} else {
System.out.println(e.getMessage());
sb.setLength(0);
out.print(‘>’);
continue;
}
}
print(results);
if (isEnd(results)) break;
sb.setLength(0);
out.print(‘>’);

} else {
Thread.sleep(100);
}
}
} catch (Exception e) {
e.printStackTrace();
}
}
public void print(List data) {
for (Iterator it = data.iterator(); it.hasNext();) {
out.println(it.next().toString());
}
}
public boolean isEnd(List data) {
for (Iterator it = data.iterator();it.hasNext();) {
if (it.next() instanceof ExitProcedure) {
return true;
}
}
return false;
}
public static Map getDefaultEnvironment() {
Map env = new HashMap();
env.put(“+”, new AddProcedure());
env.put(“exit”, new ExitProcedure());
return env;
}
}

This REPL could be started from main(), or from any Thread, which, for example, listens some socket.

This implementation is, of course, very limited and not optimal, but look what it is able to do!

>(+ 1 2)
3
>(+ 10 11 12)
33
>(define a 1)
>(+ a 2)
3
>(define b 2)
>(+ a b)
3
>(define b a)
>(+ a b)
2
>(define a 0)
>(+ a b)
1
>(define add (lambda (x) (+ x 5)))
>(add 1)
6
>(define add-gen (lambda () (lambda (y) (+ y 1))))
>((add-gen) 1)
2
>

My next steps whould be to implement =, eq?, quote, let, cond, booleans, cons, car and cdr. I also see how integers could be optimized.

By posting this I don’t claim that my code is perfect. To be honest, I just don’t have any place to put my code, so I’m putting it here. I’m not going to compete with other implementations of Scheme in Java, such as SISC or Kawa, I’m just learning and playing. My final goal will be to do my implementation in OCaml, and in Assembler for ZX Spectrum.

Advertisements
Categories: Java, Lisp, Scheme
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: