October 28, 1998

TISL: An Experimental Interpreter and Compiler for ISLisp

Takayasu Ito
Dept of Computer and Mathematical Sciences
Graduate School of Information Scinces
Tohoku University, Sendai, Japan
(ito@ito.ecei.tohoku.ac.jp)

This is a short note on an implementation of ISLisp, the ISO Lisp Standards [1] established on May 1st, 1997. The first ISLisp processor is OpenLisp implemented by C. Jullien [2]. OpenLisp is an interpreter with a fairly good performance inherited from the nature of design philosophy of ISLisp whose kernel Lisp part is based on the Japanese Kernel Lisp proposal.

As one of the most enthusiastic advocators in designing ISLisp I have been interested in having our experience of implementing an ISLisp processor. Last October (in 1997) one of my undergraduate students (N. Izumi) expressed his interest in implementing ISLisp as his undergradute thesis work. He started to study ISLisp and how to write a Lisp system under my supervision. His system was weak at his undergraduate level, but he improved his system very much after entering into his graduate study in April, 1998. A first version of the system was completed by the end of July, 1998, and its system outline and performance results using the Gabriel Benchmarks were announced at the National Convention of Information Processing Society of Japan held at Nagoya University on October 7, 1998 [4].

The system is now called "TISL", which consists of ISLisp interpreter and compiler, where the compiler is an interpreter-based compiler that the function "compiler" will be invoked from the interpreter.

TISL is an acronym of Tohoku university ISLisp system. The current TISL system runs on PCs under Windows NT 4.0 (CPU: AMD K6 200MHz with 64Mbytes) and on workstations under the Solaris 2.5.1 OS (on UltraSparcII 168MHz with 128Mbytes and others).

Table 1 shows the results of running the Gabriel Benchmarks [3] on the PC cited above.

Table 2 shows the results of running several programs written using ISLisp generic functions which support object-oriented programming in ISLisp.

[N.B.] The object-oriented features of ISLisp are desinged as a very compact system on the basis of CLOS under an international collaboration at the ISO/SC22/WG16 LISP.

In Table 2 "compiler (type-based)" means an ISLisp compiler that supports optimizations in implementing generic functions using type-inference. The current type-based system works fairly well for the cases when an effective method for a generic function can be statically determined as in "gfib" and "tak". But at present, no good support is realized yet for the cases that an effective method cannot be statically determined as in "gderiv" and "qsort", and an improvement for such cases is left for future (actually, under study).

Note that in case of "gqsort" an object comparison is done using a generic function. According to our experiments OpenLisp did not work properly in this case; it does not invoke methods correctly for classes of multiple inheritance in this example of "quick-sort" written using generic functions.

[Remarks] OpenLisp has been the first interpreter of ISLisp. According to my knowledge the TISL compiler is the first running compiler for ISLisp.

From Table 1 and Table 2 we can observe the following:

  1. TISL interpreter is 1 - 2.8 times faster than OpenLisp.
  2. TISL compiler is 1 - 4 times faster than TISL interpreter.
  3. In cases of tiny programs whose compiler execution timings are less than 0.50 [sec] the compiler sometimes gives no performance improvement, compared to the interpreter, since the TISL compiler is a compiler based on the TISL interpreter. In other cases like Boyer, Browse, Travese-init/-run, Puzzle and Triangle the TISL compiler runs more than 2 times faster than the TISL interpreter.

Moreover, according to the Izumi's preliminary experimental results on a Sparc workstation the TISL interpreter runs about 10 times faster than the interpreters of KCL and Lucid Common Lisp for the Gabriel Benchmarks. Also, the TISL compiler runs as fast as the KCL compiler, but the Lucid Common Lisp compiler runs more 5 times faster than the TISL compiler.

Table 1: Results of Gabriel Benchmarks of TISL [sec]

program OpenLisp TISL interpreter TISL compiler
Tak 0.21 0.10 0.09
Stak 0.29 0.23 0.12
Ctak 0.39 0.22 0.15
Takl 1.53 1.11 0.28
Takr 0.26 0.16 0.16
Boyer ----- 2.25 0.62
Browse 3.46 3.17 1.52
Destructive 0.62 0.51 0.30
Traverse-init 4.03 3.22 1.50
Traverse-run 21.67 15.47 6.97
Derivate 0.52 0.41 0.26
Dderivate 0.56 0.43 0.26
Div2-iter 0.42 0.29 0.16
Div-rec 0.41 0.26 0.17
FFT 2.54 0.88 0.37
Puzzle 4.19 2.97 1.23
Triangle 51.69 42.22 12.97

Table 2: Results of Running Programs Written Using Generic Functions [sec]

program OpenLisp TISL interpreter TISL compiler TISL compiler
(type-based)
Gfib 1.04 0.64 0.41 0.13
Gtak 0.32 0.26 0.20 0.12
Gderiv 1.64 1.14 0.92 0.92
Gqsort ----- 0.80 0.60 0.55

REFERENCES

[1] ISO/IEC 13816:1997, Information technology - Programming languages, their environments and system software interfaces - Programming language ISLISP (1997)

[2] Christian Jullien: OpenLisp, http://www.ilog.fr:8001/Eligis/ (1998)

[3] Richard P. Gabriel: Performance and Evaluation of Lisp Systems, MIT Press (1985)

[4] N. Izumi and T. Ito: Interpreter and Compiler of the ISO Standard Lisp ISLISP, Proc. National Convention of Information Processing Society of Japan, Vol.1, pp.323 - 324 (1998)

[N.B.] Windows, AMD, and Solaris/ UltraSparc are the registered trademarks of Microsoft, AMD, and Sun Microsystems, respectively.