In June of 1997, I wanted to learn Java beter. I had a pretty good theoretical understanding of the language, but hadn't written much actual Java code. I decided to write a Lisp interpreter, and JSCHEME is the result. Here are the design decisions I dealt with.

1. What resources? I decided I didn't want to spend more than 20 hours on this exercise of learning Java, learning the IDE I was using, and producing a Lisp interpreter. I met the goal in the allocated time: I had a Lisp with 638 lines of code, 4 data types (pair, symbol, number, and procedure). I put the project aside (and went on to write lots more Java at work), but then I found Aubrey Jaffrey's r4rstest.scm test suite, which tests Scheme compliance. My system failed most of the tests, of course, so every now and then I would get some spare time and make some additions. Eventually I passed all the tests, released it to the Internet, and made a few updates once I found that people were finding it useful and downloading it. Because the system came out to about 50KB I decided to call it SILK, or Scheme In L KB (L is 50 in Roman), with the intention that if it ever bloats up to 100KB, I'd change the name to SICK. In version 1.4 the jar files (source and .class) are comfortably below 30KB, but the uncompressed source code has climbed to 69KB (still closer to L than C).

   Addendum: In 2001 (and again in 2002) we got letters from the friendly folks at Thredtec.com, who have a trademark on ``Silk'' for a Java simulation tool, so we changed the name to ``Jscheme,'' which was the name of Tim Hickey's implementation before he joined the SILK project.

2. What Lisp? I settled on R⁴RS Scheme, because it has the test suite, is widely used, and has a publicly accessible manual.  Some day I should upgrade to R⁵RS Scheme, which is the most recent verison, and is compatible with the IEEE Scheme standard.

3. Compiler or Interpreter? I just wanted something that works, so I did a simple interpreter.
4. What kind of performance? This was not a major concern.  I wanted an interpreter that would work, but it didn't have to be fast. It turns out I got about what I expected: it takes about half a second to load the 500 line primitives.scm file, and another half a second to loop 1000 times using this code:

   (define (loop n) (if (> n 0) (loop (- n 1))))
   (loop 1000)
   

   I conjecture that most of the time goes into a linear lookup of functions in the global environment. This conjecture is confirmed by seeing that the following variation runs about nine times faster:

   (define loop2 (let ((> >) (- -)) 
                   (lambda (n) (if (> n 0) (loop2 (- n 1))))))
   (loop2 1000)
   

   I can get another 15% faster by doing:

   (eval `(define (loop3 n) (if (,< n 0) 0 (loop3 (,- n 1)))))
   (loop3 1000) 
   

   With this I can loop 14,000 times in a second, which seems fast enough. Perhaps I should have the notion of immutable variables, and have lambda do some pre-treatment analysis, so the user can write the loop version and get the effect of the loop3 version.

5. How to Organize into classes?  At first, I was confused about the syntax for static methods in Java. I'd seen both Math.sqrt(x) and java.lang.Math.sqrt(x), but I thought you could do sqrt(x) if you import java.lang.Math. I quickly discovered that is not correct: you can only write sqrt(x) in code that is in the Math class, or a class that extends Math. So now I had a problem: over 100 error messages, and a question of how to re-organize.  My first thought was that I could live with one use of Math.sqrt(x), but I really wanted to write list(x, y), not SomeOtherClass.list(x, y), and the only way I could think of to achieve that was to put everything (well, almost everything) into one big class.  That's when I thought of the name SIOC, or Scheme in One Class, which is a play on George Carrette's SIOD, or Scheme in One Defun.

   However, I knew I really wanted to have a separate class for the interpreter (so I could swap several interpreters in; perhaps a simple interpreter, a tail-recursive interpreter, and an interpreter that supports full call/cc, as I did in PAIP). I also wanted to have a class for the primitive procedures, so I could have an R⁴RS, and an R⁵RS version some day. (I should probably clean things up so that the extensions are in a separate class from the R⁴RS primitives.) But if I put the list method in the primitive procedure class (where it will be used fairly often), then I would have to write Primitive.list(x, y) in the other classes (which also want to use list fairly often). I guess most Java programmers would just have accepted this, but I came up with the idea of putting the utility methods in their own class, SchemeUtils, and then having the five other top-level classes extend SchemeUtils.  That way, I can use the unqualified name, and I get the modularity I want. So the class structure I ended up with is:

SchemePrimitives SchemeUtils Scheme Environment Pair InputPort Procedure Primitive JavaMethod Continuation Closure Macro

6. Basic Implementation Parts Once these design issues are out of the way, the rest is pretty easy. In order to build a Scheme interpreter, you basically need six things:
   • Read and write. The reader goes in the InputPort class.  I tried java.io.StreamTokenizer, but it didn't help much, so I ended up writing my own tokenizer. For output, I put most of the functionality into a method, SchemeUtils.stringify, to convert an object to a printable string. Once we have the string, printing is trivial, so I can use the existing Java PrintWriter class, I don't need a class for OutputPort.
   • Eval and apply. The eval method goes in the Scheme class.  There's also an apply method there, but all it does is make sure you're applying a procedure and then dispatches to the apply method in each subclass of Procedure.  But note that we have to repeat the code for applying a Closure (a user-defined Scheme procedure) within the code for eval.  This is necessary only to make sure that eval is properly tail recursive. If Java were tail recursive, we wouldn't need to do this.
   • Memory management.  Java handles this automatically.
   • Run-time stack. I use the Java run-time stack. This means I don't have full continuations, just throw-like ones, and I don't have good debugging capabilities. But it does make things easier than implementing my own stack. I do take care to make the interpreter properly tail recursive: calls in the tail position do not grow the stack.
   • Primitive functions The class Primitive provides for the application of primitive procedures like list, pair?, and write. One possible implementation strategy is to have each primitive be an anonymous inner class:

   new Primitive("list", env, 0, n) {
     public Object apply(Object args) { return args; }};
   
   new Primitive("null?", env, 1) {
     public Object apply(Object args) { return truth(first(args) == null); }};
   

   The other possibility is to have a big switch statement.  I decided that loading 150 inner classes might be slow, so I went with the big switch. This means a lot of busy work, and breaking up the definition of each primitive into three places: first I need to define a long list of final static ints for the switch labels, then I need to initialize all the procedures, and finally I need to write the big switch that defines the semantics of each primitive.  This is ugly (in Lisp it would be pretty) but I decided to put up with it. It ends up like this:

   final static int ... LIST = 16, ... NULLQ = 23, ... // Define constants
   ...
   public static Environment installPrimitives(Environment env)  {
   
     int n = Integer.MAX_VALUE;
   
     env
       .defPrim("list",  LIST,  0, n) // list has 0 to n arguments
       ...
       .defPrim("null?", NULLQ, 1)    // null? has exactly one argument
       ...;
   }
   
   public Object apply(Scheme interpreter, Object args) {
     ...
     Object x = first(args);
     switch(idNumber) {
       ...
     case LIST: return args;
       ...
     case NULLQ: return truth(x == null);
     }
   }
   

   • Primitive data types. Scheme has a dozen or so data types (depending on how fine distinctions you make) that are visible to the programmer. There are two main ways to implement them.
   • I could have a SchemeObject class, and make everything a subclass of that.  The advantage is I could then call obj.display() and  obj.car(), in typical Scheme fashion.  Every class would have a display method, and the SchemeObject class would have a car method that gives an error; this method would be overridden in the Pair class. The disadvantages would be:
     • I would take a small memory hit by having extra objects around.
     • Many methods would need two implementations: one on SchemeObject, and one on the proper type.
     • I would have to re-implement some dispatching code to duplicate the behavior of Scheme types like Double and char[].
     • It would be harder to integrate JSCHEME with other Java code, if JSCHEME uses its own types for everything.
   • I could use the simplest possible existing Java types wherever possible.  So, for example, a Scheme vector is implemented as a Object[], not a Vector, because Scheme vectors don't need to add and delete elements.  Using existing Java types means that we can't call obj.display(), because there is no display method on these existing Scheme classes, and of course you can't add a method to an existing class in Java.  So instead, we will have lots of static methods in the SchemeUtils class. This is the choice I made, as you can see in the chart below. The Java types in Bold are ones I had to define; the ones in non-bold are already defined in Java.

For numbers, I have only one type: Double. This is allowable by the specification but raises a problem with respect to exact/inexact numbers. I didn't implement inexact contagion properly. Technically, (max 4 3.9) should be an inexact 4. But I have no way to distinguish #e4 from #i4. I implement (exact? x) as true iff (= x (round x)) and if adding or subtracting 1 from x changes x. Rather than do the add/subtract each time, I test against the maximum allowable number. I guess I could have looked up the format for IEEE double floating point to see that there are 53 bits in the mantissa, but instead I wrote a program to figure out that I can represent exact integers up to 0x1fffffffffffff (just under 10¹⁶). I still have the problem that (* 2 0.5) comes out to an exact number, when it should be inexact. Here's the program:

(define (f lo hi) 
  (let ((mid (+ (/ hi 2) (/ lo 2)) (round (sqrt (* lo hi)))))
    (if (or (= lo mid) (= mid hi))
	lo
	(if (ok? mid) (f mid hi) (f lo mid)))))

(define (ok? n)
  (and (< (- n 1) n (+ n 1)) 
       (= (- (+ n 1) 1) n (+ (- n 1) 1))))

(number->string (f 1 (expt 2 63)) 16)