Scheme interpreter extension

I’ve spent one more day on extending my Scheme interpreter. I’ve added booleans, cond, list, length, -, = , so now it is quite capable. For example, now I can write a recursive function which will calculate sum of numbers starting from 1 up to provided number. Internally code was refactored quite a bit, except of ListTools, which remained exactly the same. I’ve also made a tracing facility, which was surprisingly easy to implement.
Very important discovery for me is that now I understand Scheme language much better. It’s a general rule: to use something effectively you should understand how it works. Implementation and description are the same.
Now I want to summarize my results so far. Scheme interpreter consists of two parts: REPL (which includes reader and result printer) and Evaluator. Reader invokes ListParser, which parses user’s input presented as sequence of characters into list structure, so elements of list could be character strings or other lists. Then result of parsing is passed to evaluator. Evaluator evaluates all items in top-level list, and returns list of result values, which are printed by result printer. If error occurs in ListParser or Evaluator, it is also printed.
Since Evaluator is provided with representation of user’s input, it can distinguish raw symbolic data and lists. Raw symbolic data are evaluated by checking if they are numeric, symbolic or boolean literals, and if not they are considered variable names and their values is looked up in environments. Lists are first checked to be special syntax forms (like define, cond, lambda), and if not, then first item is evaluated. If first item is a procedure, then arguments are evaluated and then procedure body is evaluated.
I think that simplicity of language itself and it’s implementation comes from two things: simple syntax and dynamic nature.
Now I use ArrayList to represent lists. I can implement cons, but it will not provide true sharing, it will make copies instead. But users will see no difference until set-car! and set-cdr! are implemented. Later I will implement cons sells, and will make List implementation based on them.
Making Scheme in Java is a simple task, because both languages have garbage collection. I’m afraid that implementation in Z80 assembler will be more diffucult.

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.

The Astyanax

Today is my lucky day. I’ve finally found that game!

Arcade games were popular in Russia, but most games were locally developed, and were electromechanical, not computer-based. At the beginning of 90-s there were very few places with computer-based arcade games (usually made in Japan or US). Then I’ve got to one such place once I was impressed. I’ve already had my 8 bit ZX Spectrum at home, with palette of 8 colours, and with lots of games. In arcades I was impressed mostly by colourful and reach graphics, because gameplay was the same as in games for my ZX Spectrum. I even had something to compare: “Golden Axe” already existed for ZX Spectrum, and there were an arcade version there. Except “Golden Axe”, there were two games which I liked. Name of one game I remembered: “Hammerin Harry”. And name of another game I forgot.

In modern time, then I investigated console emulation, I’ve discovered that arcade machines also could be emulated, and there is a software for it called MAME. I’ve checked it, and both “Golden Axe” and “Hammerin Harry” were working very well. I even discovered a very good sequel to “Golden Axe”, very beautiful and highly playable game. But I couldn’t remember last game, and, without it, I could not find peace.
But, thanks to effort of people at klov, I’ve finally found it. Recently I was browsing this site, now it has much more screenshots then before, and I quickly found my game. It is called “The Astyanax”. Now I can return to my childish memories. Thanks guys!

Dreamhold

“Dreamhold” was first ineractive fiction game I’ve played at “modern” times. I’ve decided to start with it because description told that this is an introductionary game, and, since I didn’t played interactive fiction for more then 10 years, I’ve choosen that game because I thought that I’m not more than beginner. To summarize by experience from playing: this game is good, I’m not a beginner, this game is not really for beginners.

The game itself is about a wizard who dreamed of conquerring countries and discover new worlds, but, as effect of very powerful spell, he lost his memories and now walks through house build inside his dreams. Surroundings pretend to be surrealistic. To be honest, the plot didn’t made much sence to me: it doesn’t develop, there are no NPC to interact with, player just receives some pieces of story through flashbacks. Gameplay consists of exploration and puzzle solving. Task is to restore player’s memory and, either fix the spell and go to new worlds, or to return back and fix all the wrongs player did.

I think I will not spoil the game if I’ll tell that task is achieved by collecting several colour masks. There is also a secondary task to collect special objects, but those objects are just add to score. Solving puzzles open new areas or give player some new object.

The game is positioned as “introductory”. This means that the game have two settings for difficulty, and tutorial voice which helps at the beginning. Well, for me tutorial voice was not much help, because beginning of the game is really easy. Two difficulty settings are also quite confusing. I’ve started on “easy” level, and spent too many time figuring out what to do with lots of stuff present in game. “Easy” level is really confusing, because most objects are simply accessible, and some hard puzzles don’t give anything to player. Then I’ve played on “hard” level, the game become more logical, because objects are now accessible only when you solve puzzles.

So, I whould not recommmend this game as introductionary, but, in general, it’s a good piece of IF, definetely worth playing.

Value capture in Lisp

In one of my previous posts I’ve told about how (define) works and how (lambda) works. Main difference is that (define) evaluates second argument, and (lambda) doesn’t evaluate anything, it just binds all variables to specific scope. Variables could even be defined after definition of (lambda)! See following example (in Scheme):

>(define f (lambda (x) (+ x y)))

>(f 5)

Error: variable y is not bound.

>(define y 5)

>(f 5)

10

In this example, x is bound to scope of function’s arguments, and y is bound to local scope. Each time the function is applied, it tries to use (evaluate) variable in initially defined scope.

The story continues in OCaml. Now I’m reading a book about this language, and I was surprised to know that it is implemented exactly in the way I was mistakenly thinking about Lisp earlier. So, function definition in OCaml doesn’t capture the scope, it captures the value! Look:

# let a = 10;;
val a : int = 10
# let add2a x = a + x ;;
val add2a : int -> int = <fun>
# add2a 5;;
- : int = 15
# let a = 20;;
val a : int = 20
# add2a 5;;
- : int = 15

So, we have fundamental difference between OCaml and Lisp. I don’t know which behaviour is better, and I don’t bother. I just know how it will behave in both languages. But, my next idea was: is it possible to achieve value capture in Lisp, and scope capture in OCaml ?

Value capture in Lisp is, of course, possible. It is done by using (lambda) inside (let). Look:

>(define x 5)

>(define f
    (let
        ((x1 x))
      (lambda (y) (+ x1 y)))
    )

>(f 5)

10

>(define x 10)

>(f 5)

10

Let allows us to create local scope, and each clause in let is like (define), so it evaluates variable. In this way we achieve value capture in scope accessible only from body of function.

Regarding OCaml: I’m sure that “scope capture” will not work. The reason is that OCaml, unlike Lisp, is a language with static type checking. Since any variable could be re-defined with different type after funciton definition, OCaml implements value capture to avoid type errors.