Timothy J. Hickey, Brandeis University, Waltham, MA
tim@cs.brandeis.edu
AbstractWe describe our experience with SILK, a Scheme dialect written in Java. SILK grazes symbiotically on Java's reflective layer, enriching itself with Java's classes and their behavior. This is done with two primitive procedures, (constructor) and (method) that provides access to a specific Java constructor or method respectively. A recent extension allows, an entire class's behavior to be imported using (import). The extension also provides generic functions that take methods written in Java or Scheme.In return, SILK provides Java with an interactive development and debugging environment that can be used to develop graphical applications from the convenience of your web browser. In Java terms, SILK is a Java bean box with Scheme as a runtime scripting language. However, because SILK has introspective access into Java, it can also be used for compile time metaobject scripting. For example, it can generate a new class using an old one as a template. |
Despite these limitations, Java's reflective capabilities are used successfully by many Java facilities, such as serialization, remote method invocation (RMI), and Java Beans. However, programming in base Java, is different from programming in the reflective layer. While Java is a statically typed language, the reflective layer is more dynamic. This suggests that a dynamic language, such as Scheme, could be ideal for programming the reflective layer. Scheme could be used as a dynamic language at runtime, and as a dynamic metalanguage at compile time.
Here we describe SILK (Scheme in about 50 K), a compact Scheme dialect written in Java. Because Java is reflective, considerable power can be gained relatively easily. For example, only two functions, (constructor) and (method), need to be added to Scheme to provide complete access to the underlying Java.
Following Common Lisp, SILK provides generic functions. These generic functions accept several method types:
The foreign function interface between Scheme and Java is virtually transparent to the user. The function (import <class name>) makes the methods and final static fields of the Java class named class name, <class>, accessible to Scheme.
Compile time reflection is used to construct SILK in several stages. Scheme is used to define a Java class, Primitive, that defines static methods corresponding to Scheme primitives. Once compiled, reflection on the class can import the primitives into a Scheme runtime environment.
SILK is being used in Java applications and in an "introduction to computer science" course for no ncomputer science students.
After Peter made this implementation available on the web several people made useful (and sometimes almost identical extensions). This version was a tiny, straightforward Scheme interpreter.
Tim Hickey, who had his own Scheme in Java, adopted SILK, and added JLIB, a library that provides convenient access to the Java AWT.
The SILK 2.0 version compiled Scheme syntactic expressions into Code objects that could be more efficiently evaluated. This version was started by Peter Norvig and completed by Tim Hickey.
Most recently, generic functions have been added as an extension. While we describe SILK in general, they are the primary topic of this paper.
(constructor CLASSNAME ARGTYPE1 ...) (method METHODNAME CLASSNAME ARGTYPE1 ...)The (constructor) procedure is given a specification of a Java constructor, in terms of a class name and a list of argument type names, and returns a procedure implementing that constructor. The (method) is given a specification of a Java method, in terms of a method name, class name, and a list of argument type names, and returns a procedure implementing that method.
So, for example, we can use the java.math.BigInteger package to see if the number, 12345678987654321, is probably prime (with a probably of error of less than 1 part in 2 -10 when the result is #t):
> (define isProbablePrime (method "isProbablePrime" "java.math.BigInteger" "int")) isProbablePrime > (define BigInteger (constructor "java.math.BigInteger" "java.lang.String")) BigInteger > (isProbablePrime (BigInteger "12345678987654321") 10) #fIt is useful to have additional access to Java's reflection layer. Here we define the procedure (class) that returns a class object given its full name string:
> (define class (method "forName" "java.lang.Class" "java.lang.String")) class > (define HT (class "java.util.Hashtable")) HT > HT class java.util.Hashtable >Here we define a procedure, (get-static-value) that given a class and a string naming a static field, returns the value of the corresponding static field. We then ask for the value of the TYPE of the class Void. In Java, that would be simply Void.TYPE.
> (define get-field (method "getField" "java.lang.Class" "java.lang.String")) get-field > (define get-field-value (method "get" "java.lang.reflect.Field" "java.lang.Object")) get-field-value >(define (get-static-value class field-name) (get-field-value (get-field class field-name) '())) get-static-value > (get-static-value (class "java.lang.Void") "TYPE") void >
The larger window in the background is a SILK interaction window. Scheme expressions can be typed into the larger text area in the upper right. When the evaluate button is pressed, the printout appears in the lower text area. Using this, the entire application can be developed using only a web browser.
Here we have defined a simple body mass index calculator window in the foreground of the exhibit. Procedures (window), (textfield), (button), and (label) create the corresponding AWT components. Procedure (pad) lets one add behavior, in the form of a lambda expression to a button press event. Procedures (readExpr) and (writeExpr) are used to read and write Scheme expressions from and to text fields. Procedures (col) and (grid) provide columnar and grid layout, respectively.
The layout of the Scheme code matches the layout of the window. Basically, there is a column consisting of a 2x2 grid, a compute button and a result text area. The corresponding Java looks more cluttered and the structure is not as apparent. Scheme anonymous functions take the place of Java inner classes.
At Brandeis University, JLIB has been in used in an undergraduate/graduate level Computer graphics course (CS155, Spring 1998), and an "Introduction to computers" course (CS2a, Autumn 1997, Autumn 1998) for non computer science majors. Over 1,000 applets have been developed by the students.
(define (get x) (let* ((c (class-of x)) (choice (cond ((eq? c hashtable-class) hashtable-get-method) ((eq? c field-class) field-get-method) (else (lambda (x) (error "no method for " x)))))) (choice x)))Macros can help generate such code automatically and we used that approach for a while. Before showing our solution to these problems, we look at the approach taken by another Scheme in Java, Skij.
For example, here is how it would create a hashtable and access it, and invoke a static method:
(define ht (new 'java.lang.Hashtable 100)) (invoke 'put ht "hi" "bye") (invoke 'get ht "hi") (invoke-static 'java.lang.Class 'forName 'java.lang.Hashtable)
In our approach an (import) function is used to import the static and instance methods of a class. The goal was to make this similar to the import statement in Java. Here we import Hashtable:
> (import "java.util.Hashtable") (import-class class java.util.Hashtable) Hashtable.class generic clone generic equals generic getClass generic hashCode generic notify generic notifyAll generic toString generic wait generic elements generic get generic isEmpty generic keys generic put generic remove generic size generic clear generic contains generic containsKey generic containsValue generic entrySet generic keySet generic putAll generic values () >The result of an (import) is that:
> (define ht (Hashtable 20))
ht
> ht
{}
> (put ht 'clone 1)
()
> ht
{clone=1}
> (put ht 'zone 2)
()
> ht
{clone=1, zone=2}
> (get ht 'clone)
1
>
The procedure (import) creates generic functions. For example,
(get) is a generic function with one method:
> get
{JavaGeneric get[1]}
> (methods get)
({silk.JavaMethod class java.lang.Object java.util.Map.get(Object)})
>
The number in square brakets indicate the number of methods, one here.
Here's an example with static methods:
> (import "java.lang.Float") (import-class class java.lang.Float) Float.class generic Float.floatToIntBits generic Float.intBitsToFloat generic Float.isInfinite generic Float.isNaN generic Float.parseFloat generic Float.toString generic Float.valueOf generic byteValue generic doubleValue generic floatValue generic intValue generic longValue generic shortValue generic compareTo generic isInfinite generic isNaN () > (Float.parseFloat "17.42") 17.42 >When a class is imported, a Name.class variable is bound to the class:
> Hashtable.class class java.util.Hashtable >
To use it, type a number into the second textfield. The top textfield contains the current estimate of its square root. Each time the "iterate" button is pressed, an iteration of Newton's method is performed to better approximate the square root.
Here's the code. Since JLIB is not used here, except to borrow the EasyWin class, the programming style is more similar to programming AWT in Java than it might be programming in JLIB.
(import "java.lang.Double") ; Import some Java classes. (import "java.awt.Color") (import "java.awt.Button") (import "java.awt.TextField") (import "jlib.EasyWin") ; Import a JLIB class. (define (test1) ;; Construct a test window. (let ((win (EasyWin "test1.scm" this-interpreter)) ; Create an Easywin. (g (TextField "1" 20)) ; Create some components (x (TextField "16" 20)) (go (Button "Iterate"))) (define (action e) ; Define call back. (setText g (toString (f (Double.valueOf (getText g)) (Double.valueOf (getText x)) )))) (define (f g x) ; Define Newton's method. (/ (+ g (/ x g)) 2.0)) (resize win 200 200) ; Size the window. (add win g) ; Add the components. (add win x) (add win go) (addActionCallback win action) (setBackground win (Color 200 200 255)) ; Set background color (show win))) (test1) ; Try it out.
> (methods toString)
({silk.JavaMethod class java.lang.String java.lang.Object.toString()})
>
We call such a method, a "most general method".
The feasibility of this approach was studied using the 494 classes reachable from the class javax.swing.Jframe. Here are some statistics:
Count What 494 classes 458 public classes 52 Exception classes 176 static most general methods 2759 instance most general methods. 2935 total most general methods.There were 134 generic functions that contain only static methods. 93% of them have two or fewer methods:
Count Methods Cumulative % and examples 110 1 82.1% 15 2 93.3% 6 3 1 4 java.awt.image.Raster.createPackedRaster 1 5 javax.swing.KeyStroke.getKeyStroke 1 9 java.lang.String.valueOfThe 2,759 instance most general methods fall into 1525 generic functions. 91% of these have three or fewer methods:
Count Methods Cumulative % and examples 1058 1 69.4% 255 2 86.1% 75 3 91.0% 39 4 24 5 23 6 17 7 10 8 6 9 1 10 5 11 1 12 1 13 2 16 1 17 get 1 18 contains 3 20 clone insert print 1 22 println 1 24 remove 1 36 addSo, most generic functions have one or two methods so our discriminator approach favors such situations.
Methods are only added to a generic function when a class is imported. So, the above statistics reflect what you get if you imported all 494 classes. The number of actual methods is likely to be substantially lower than this. For example, when using only javax.swing.JFrame, (add) only has six methods, not 36.
Following Common Lisp, SILK's generic functions perform method selection using all their arguments at runtime.
Currently we use a discriminator with 7 states. The state of the discriminator is recomputed whenever a method is added to the generic function. The states are chosen based on the static statistical analysis above. In contrast, Common Lisp chooses discriminator states dynamically so performance is adapted to each run of an application. Here is a description of the states:
Java development environments, such as a Java Bean box, such as Sun's BDK (Bean Developer Kit) compile small glue classes automatically. This generated code usually follows a standard template and requires some introspection of an existing class. We can do the same thing in SILK. Essentially, Scheme becomes a macro language for Java.
For example, the normal Java runtime environment does not provide a way to trace individual methods. Here we sketch how to add such tracing capability. The basic idea is to generate a subclass of an existing class which allows its methods to be traced. If SILK has enough access to the Java application, an instance of this traceable class can be substituted into the application without changing any Java code. As part of this process, we would have a method, m, say Hashtable's put() method, and generate a traced method from it using (gen-method m):
> m
public synchronized java.lang.Object java.util.Hashtable.put(java.lang.Object,java.lang.Object)
> (gen-method m)
public synchronized java.lang.Object put(java.lang.Object a1, java.lang.Object a0)
{
if (trace) Trace.enter(this + ".put(" + a1 + ", " + a0 + ")");
java.lang.Object result = super.put(a1, a0);
if (trace) Trace.exit(result);
return result; }
}
#\newline
>
Here's some Scheme code that does this:
(define (gen-method m)
(gen-method-signature m) (emitn " {")
(gen-trace-method-body m) (emitn "}"))
(define (gen-method-signature m)
(emit " " (Modifier.toString (getModifiers m)) " " (method-return-type m)
" " (getName m) "(")
(emit-args (arg-types m)) (emitn ")"))
(define (gen-trace-method-body m)
(emit " if (trace) Trace.enter(this + \"." (getName m) "(\"")
(emit-trace-args (map arg-name (arg-types m))) (emitn " + \")\");")
(emit " " (method-return-type m) " result = super." (getName m) "(")
(emit-call-args (map arg-name (arg-types m))) (emitn ");")
(emitn " if (trace) Trace.exit(result);")
(emitn " return result; }"))
(define (emit-trace-args args)
(for-args (lambda (arg) (emit " + " arg)) " + \", \"" args))
(define (emit-args args)
(for-args (lambda (arg) (emit (arg-type arg) " " (arg-name arg))) ", " args))
(define (emit-call-args args) (for-args emit ", " args))
(define (for-args f more args) ; Map over Argument lists
(if (not (null? args))
(let ((arg (car args))
(args (cdr args)))
(f arg)
(if (not (null? args)) (emit more))
(for-args f more args))))
;;; For emitting code.
(define (emit . args) (for-each display args))
(define (emitn . args) (for-each display args) (write-char #\newline))
(define arg-type car) (define arg-name cadr)
(define (make-arg-name c) ; 1 -> a1
(string->symbol (string-append "a" (symbol->string (toString c)))))
(define (arg-types m) ; method -> ((type name) ...)
(let ((c 0))
(map* (lambda (a) (list (getName a) (make-arg-name (set! c (+ c 1)))))
(getParameterTypes m))))
(define (method-return-type m) (getName (getReturnType m)))
This code generation system is extremely basic.
(emit) and (emitn)
are used to generate lines of Java code by printing their arguments. And (for-args) is used
to map over argument lists.
SILK can automatically compile this code. Currently, due to a technical glitch, SILK can not assign a string into a string array, So we use a Java helper class:
package elf;
import sun.tools.javac.Main;
/**
This lets you compile Java classes in silk:
(Compile.compile "<the java file>")
**/
public class Compile {
public static boolean compile (String file) {
String[] args = new String[1];
args[0] = file;
Main m = new Main(System.out, "silkc");
return m.compile(args);
}}
To compile and load the new class we just do:
> (Compile.compile "elf/TracedHashtable.java") #t (import "elf.TracedHashtable") (import-class class elf.TracedHashtable) TracedHashtable.class generic clone generic elements generic isEmpty generic keys generic put generic remove generic size generic clear generic contains generic containsKey generic containsValue generic entrySet generic keySet generic putAll generic values () >While this example is simple, it should be clear that SILK can become a useful software development environment without a substantial amount of work.
We have tried to show that SILK makes effective use of Java's reflective capabilites. However, even though we were well aware of reflection from the beginning, SILK was originally developed using a relatively traditional approach; one that you might use to implement a Scheme in a non-reflective language, such as C or Scheme. First the essentials of a runtime environment were defined, then the essential Scheme primitives were written in terms of the capabilities of the runtime environment. After that, the Scheme listener is written to bootstrap itself into existence.
The result is a Scheme dialect that is relatively compact, though it has grown over the past 18 months. Even so, it still fits in a 76KB jar file. The following exhibit shows statistics from Scheme dialects we know of.
| Implementation | java files | lines | Scheme files | lines |
|---|---|---|---|---|
| Silk 1.0 | 12 | 1905 | 0 | 0 |
| Silk 2.0 | 20 | 2778 | 0 | 0 |
| Silk 2.0 + import | 28 | 3347 | 3 | 307 |
| Skij | 27 | 2523 | 44 | 2844 |
| Jaja | 66 | 5760 | ? | ? |
| Kawa | 273 | 16629 | 14 | 708 |
About a third of the code, 988 lines that relate to 191 Scheme primitives, can be generated by Scheme.
We speculate that by making a more determined effort to use reflection as a building material, SILK could be even smaller. Of course, that might come at the expense of favoring Java in favor of current Scheme standard.
Imagine a runtime environment with the following characteristics:
Since, by definition, generic functions do argument type checking, the type check code of the previous SILK kernel is unnecessary.
Now, we can use Java as a supermarket adding its methods to generic
functions to create the Scheme environment we want. For example, if
we are willing to accept Java's String class as the representation of
a Scheme string, we can simply load the corresponding methods into the
appropriately named generics and we are in business. Making this
implementation decision as Skij does, simply means that only the
(string-set!) procedure is no longer available.
Scheme must provide some classes, such as Pair, but their constructors and methods become become the obvious procedures, cons, car, and cdr.
Some primitives may require type conversion, but they can be constructed from functional composition with functions in the runtime base.
The size and performance characteristics of a Scheme dialect built this way, would certainly be different than SILK's. However, since in either case, most of the performance is lost jumping across the Scheme/Java boundary, the differences are likely to be small.
Performance can be regained using the compile time technique described above. Once a set of generic functions have been identifed, their contents can be crystalized into a Java class that constructs them when the Scheme application starts.
So, in summary, there is a reflective bootstrapping process where a Scheme runtime enviornment grazes over the Java runtime environmnet to construct the behavior it wants. Then, introspection of the Scheme environment is used to compile it into a brick of Java code that is the Scheme environment users actually see over the web.
Thus by proper use of reflection, softare gets smaller and faster.
[BW] A. Berlin and D. Weise, Compiling scientific code using partial evaluation. Technical Report CSL-TR 90-422, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, 1990.
[GK] Gregor Kiczales, Tiny CLOS, http://???
[KR] Gregor Kiczales and Luis Rodriguez, Efficient method dispatch in PCL, proceedings 1990 ACM Conference on LISP and Functional Programming, Nice, France, June 1990, 99-105.
[PB] Per Bothner, Kawa the Java-based Scheme System, http://www.cygnus.com/bothner/kawa.html
[PN] Peter Norvig, SILK: Scheme in Fifty K, http://www.norvig.com/SILK
[TH] Tim Hickey, JLIB: A Declarative GUI-building library for SILK, http://www.cs.brandeis.edu/~tim/Packages/jlib/jlib.html
[MT] Mike Travers, Skij, IBM alphaWorks archive, http://www.alphaworks.ibm.com/formula/Skij
[CQ] Christian Queinnec, JaJa: Scheme in Java, http://www-spi.lip6.fr/~queinnec/WWW/Jaja.html