Timothy J. Hickey, Brandeis University, Waltham, MA

Peter Norvig, Junglee Corporation, Sunnyvale, CA

Kenneth R. Anderson, BBN Technologies, Cambridge, MA

Lisp at BBN:

• 1963 L. Peter Deutch, then a high school student, wrote a LISP for the PDP 1, like Lisp 1.5.

• 1970's BBN LISP becames INTERLISP

• 1980's Lisp Machines Lispm, Dorado, Jerico

• 1990 Fielded two LISP applications during Desert Shield.

• SILK - Scheme in 50K

• JLIB - Library for Applet development

• Web programming

• Scripting

• Debugging

• Implementation

• Other implementations

• Meta scripting

• Using the web - easy, just click.

• Writing web pages - a little harder, HTML.

• Applet writing - requires real programming.

• Server - requires understanding protocols and programming: HTTP, MIME, HTML, CGI, ...

• Easy access - just visit the web page

• Simple applet creation
  • Declarative interface to most commonly used parts of Java libraries
  • Students write applets after one 50 minute lecture.
  • In Java this takes 10 hours.
  • Graphical constructs are introduced along with everything else, not as an advanced topic.

• Simple debugging - better than stack trace.

• Simple incorporation in web pages - theaded object interpreter.

• Fast download
  • Tiny runtime and interpreter.
  • 8 second download.

Example: use the isProbablyPrime() method of the BigInteger class to determine if a number is prime:

Declarative minilanguages are easy in Lisp:

• uniform syntax - no distinction between method, function, or constructor.
• multiple arguments - easy grouping.
• macros
• constructing a computation is indistinguishable from constructing a value.

JLIB interface to AWT:

Code follows shape of window.

As easy as Tcl/TK.

Limited, but idea for quick prototypes.

More control can be gained by using the Lisp-Java interface

or extending the Scheme API.

LISP Applets are similar to Java Applets:

The jlib.Applet class uses the "program" parameter to find what LISP program to load.

• Typical java debugging:

  public void main(String[] arg) {
    // ... simple testing ...
  }
  Proper testing can take a lot of code.
  Interactive testing takes even more.
  Testing tools, such as JUnit, make testing easier.
  But still may not be interactive enough.
   LISP provides an interactive test harness for Java.
  

Lift Java interval arithmetic solver into LISP: Interval Arithmetic

After defining these procedures, we can interactively call these imported procedures and examine the results.

A few lines of LISP can provide a GUI for interacting or testing Java code. scripting

Here is a GUI for the interval arithmetic solver:

+ Scheme is a powerful but tiny language.

+ 50 page manual

+ Scheme interpreters are easy to build and relatively efficient.

+ High performance compilation well understood.

Original version of SILK done by Peter Norvig

Initially, 650 lines written in about 20 hours.

Within a few months i could handle Aubrey Jaffrey's online r4rstest.scm test suite.

Here is the initial class structure:

SchemePrimitives        - Scheme code in a big string.
SchemeUtils             - Scheme like static methods, cons, car, cdr, ...
    Scheme              - Interpreter.
    Environment
    Pair
    InputPort
    Procedure
        Primitive
        JavaMethod
        Continuation
        Closure
            Macro

• Read InputPort.reader()
• Write SchemeUtils.stringify() does most of the output work.

  So just use java.io.PrintWriter

• Eval Scheme.eval() interprets s-expressions. Tail recursive.
• ApplyScheme.apply() delegates to Procedure.apply()
• Memory management Java handles this.
• Run-time stack

  Uses Java's run-time stack.

  No call/cc - just throw like continuations.

two approaches:

Inner classes:

  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); }};

Big switch

  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);
  }
}

Scheme has a dozen or so data types

SILK uses the simplest simplest possible existing Java types:

Designed to be tiny.

Written in a compact Scheme style.

Existing Java classes used wherever possible.

Java null is the empty list.

Silk 2.0 provided a higher performance evaluator by splitting eval() into two steps:

  /** Evaluate an object, x, in an environment.  First compile the
  * meaning of the object, and then call eval method on the meaning. **/
  public static Object eval(Object x, Environment env) { 
    return Code.eval(Code.toCode(x,env), Frame.EMPTY);
  }

Tail recursion is accomplished by letting eval return a Code object:

  static Object eval(Object expr, Frame f) {
    if (expr instanceof Code) {
      expr = ((Code)expr).eval(f); 
      while (expr instanceof Code) 
        expr = ((Code)expr).eval(Frame.EMPTY);         
    }
    return expr;
  }

Thus the inner loop of the interpreter is replaced by method dispatch.

Currently, a relatively small number of Code inner classes are defined.

Further performance can be gained by generating more refined classes to handle common special cases more efficiently.

Skij is a Scheme advertised as a scripting extension for Java.

Similar in capabilities to Silk 1.5

Extensive Java support including generic operations:

(peek) and (poke)            - reading/writing slots
(invoke) and (invoke-static) - invoking methods
(new)                        - object construction

Scheme handles Java exceptions.

Based on Christian Queinnec's wonderful book "Lisp in Small Pieces"

Compiler written in Scheme 1/3 the size of a Java version.

Comparable to Silk

Written in a object oriented style.

Like SILK, uses the shared superclass trick.

Each Scheme type is one or more Java classes.

nil is prepresented as an instance of Emptylist.

Ambitious Scheme implementation.

Java classes useable for implementing other languages.

Scheme to Java byte code compiler.

Each function becomes a Java class compiled and loaded at runtime.

Generic Functions

Compiler

Meta scripting

• Initially based on Tiny CLOS, partly in Java.

• Generic acccess to Java objects as in Skij

• Scheme methods specialized on Java objects.

• Dynamic Java (redefinable Java methods)

Silk 1.4:

• File based compiler

• Basically partial evaluation of the interpreter.

Silk 2.0

• Compiles to threaded objects.

• Similar to Marc Feeley's closure compiler.

• Can be further optiized.

• File based interface compiler used by Jlib.

Scheme to Java compiler based on?

• Jaja LiSP

• Kawa

• Hobbit

A simpiler variant of a compiler:

write Scheme procedures that generate new Java classes from old ones.

Use reflection of existing class to construct a new one with additional capabilites.

Example: Class Primitive implements 150 SILK primitives. Representing this knowledge in Scheme would let the class and its necessary glue code generated automatically.

;;; Access your Java application:
(define app (.. your java application ...))

;;; Extract a component of the applcation, here a table.
(define table (get-field app "table"))

;;; Define a metawrapper class.
(define wrapper-class (metawrap (class table)))

;;; Create new wrapped table.
(define new-table (new wrapper-class table))

;;; Trace the methods you want:
(trace new-table "get")
(trace new-table "put")

;;; Reinstall the table 
(set-field app "table" new-table)

• (metawrap (class table)) - constructs a subclass of class that
  • delegates to an instance of class
  • has method invocation controlled by a metaobject.

• (new wrapper-class table) - constructs object delegating to table

• (trace new-table "get") - informs metaobject to trace method get().

  Java can do this because it has reflection.

  Scheme can do this interactively.

  We understand metaobjects.

• Thread support.
• Serialization.
• Networking.

• Don't under estimate the power of a tiny LISP

• Hybrid LISP systems work
  • embedded in applications - EMACS, GIMP
  • Client/server - CORBA, CL-HTTP
  • web - SILK, Kawa, Jaja Skij
  • Meta is better

The class structure for SILK 2.0 is shown below:

Object
  Frame
  SchemeUtils            - Scheme like static methods.
    Code                 - What things compile into.
    Environment
      GlobalEnvironment
      LambdaEnvironment
    InputPort
    Pair
    Procedure             - Something you can apply().
      Closure
      Continuation      
      JavaArgs            - Deals with Java arguments.
        JavaConstructor   - Java constructor, see (constructor).
        JavaMethod        - Java method, See (method).
      Primitive           - Primitive Procedure defined as big switch.
    Scheme                - Scheme main loop.
    Syntax
  SchemePrimitives        - String containing scheme code.
  Symbol
  Throwable
    Exception
      RuntimeException
        SchemeException