Jürgen Böhms Heimatseiten - Lisp
ProLisp is a little Lisp-interpreter, written in C++, using object oriented design as much as possible without harming efficiency of the code.
You could also call it ProtoLisp, because it has - upto now - very few builtin functions. But it is a full lexically scoped Lisp implementation, realized with FUNARG and an environment ALIST which permits forming closures and thereby using functional values and functional returns correctly.
The garbage collection is classical, by the link-bending Deutsch method, no generational garbage collection or other more modern concepts by now.
But nevertheless it doesn't seem to be a slow system taking into account that it is interpretive only. Some small tests I run recently showed that it lies between CLISP and Lispworks for some elementary benchmarks not involving numbers.
Indeed numbers are a weakness of the system, because it doesn't have pointers aliasing as FIXNUMs. (But I work on that !)
Pro Lisp's features:
Concerning possible use, ProLisp could be a playground for toying around with lisp functions and lisp concepts or making additions either by adding to the C++ codebase or implementing these in Lisp itself.
Maybe there is also a use as an embeddded language in a larger application, as the executable is quite small (around 150k when stripped off debugging information but with Qt window-system code in it).
Download the source package
Please go to the prolisp page at sourceforge.net and download the most recent release.
If you are in any way interested in using, modifying or just playing around with this software, you are invited to mail me (email@example.com), if you have any questions, comments or suggestions - additonally you will find a number of pointers to lisp resources in my Linkpages.
Up to yesterday (22 April 2005) the program was a batch mode system, that meant you had to specify a file with lisp expressions you wanted to process, they were sequentially read in and evaluated and after every evaluation the result was shown.
Of course this was very unsatisfactorily and maybe for this reason nobody gave my system a look. So I changed this last night by adding a QMultiLineEdit class from the Qt toolkit as the main window of the system.
Now if you want to evaluate an expression, find some blank space in this window and enter >> at the beginning of a blank line, then press Return. In the following lines enter the expression that you wish to evaluate. You can intersperse it with blanks, tabs and returns as you like. If you are finished enter == at the beginning of a blank line and press Return. The result of the evaluation appears below the ==.
For the beginning try (you can copy and paste):
>> (DE (FIB N) (COND ((LTE N 1) 1) (T (PLUS (FIB (MINUS N 1)) (FIB (MINUS N 2)))))) == >> (FIB 17) == >> (MAPLIST (QUOTE (LAMBDA (X) (FIB X))) (QUOTE (10 12 15 17 19 22))) == >> (DE (FAK N) (COND ((LTE N 1) 1) (T (TIMES (FAK (MINUS N 1)) N)))) == >> (CONS (FAK 8) (FIB 8)) ==
and proceed as you like. For example write a function
Moved over to Qt 3.0 as GUI framework, so that everything compiles now on
my new machine (Linux/x86-64/SuSE 10.0).
Added a horizontal splitter to the interface, the upper pane used for
Lisp interaction as before. The lower pane receives the output of
stdout and stderr (cout and cerr) which now mostly works. Alas, there are
still some glitches in this redirection to a window pane which come from
(my not yet full understanding of) the internals of streambuf, strstreambuf
and the like. The implementation is done very quick and dirty.
Speaking of shortcomings of the system: Please do *never* enter a function call in the (anyway illegal) forms (F . X), (F X . Y ), (F X Y . Z) and so on. It will immediately crash the program, as I didn't consider this case in the evaluator. (Will be fixed when I overcome my laziness or someone requests it, whatever comes first...).
Started changing the arithmetic to infinite precision integers, arbitrary long floats, and integer fractions as new datatypes. So far PLUS, MINUS, TIMES, DIV and MOD work with long integers, floats and fractions still have to be done. Used the libgmp and its C++ wrapper libgmpxx which are really great pieces of software. For testing purposes I also wrote a little C++ routine to compute by series expansion arctan(1)=Pi/4 to 220 places. It took unnoticeable time to complete. So, when I finally manage to implement all the case switches in the arithmetic and have long floats, I will be able to write this little series computation also in ProLisp. Maybe in a week...
The plans for small fixnums as an extra datatype with immediate representation I have given up, it introduces too many subcases in the arithmetic routines.
Instead I allocated a fixed array for all small integers between -N and N-1 (N a certain small number, e. g. 1024 or 8192, depends on much space you want to sacrifice for speedup). The ith array element (counted from 0) contains an integer node representing i-N. Now when a new integer is allocated there is always first a range check, and when the integer is small enough no space from the freelist of integer nodes is taken, but a pointer to the corresponding element of the array is returned.
This led to drastical speedups in the fixed size integer version of ProLisp which it was till yesterday, now with arbitrary long integers the speedup is not so dramatic anymore. But the system can compete quite well with other purely interpretive systems having also only long integer arithmetic. A little fibonacci program computed (fib 30) in 17.5 s in ProLisp and in 18.0s in Maple 8.0. CLISP needs only 9s for (fib 30) in interpretive mode but I suppose this is, because it has little fixnums as an extra datatype (all numbers in the computation of (fib 30) are well in the signed 32bit range).
It didn't took me a week to compute Arctan(1) on ProLisp. In fact it was much easier to integrate the long floats into the arithmetic than I first thought, because of the ample set of conversions in the GMP library. So only some bugs in my code for I/O of long floats lead to problems, but I could solve them finally. The program to compute Arctan(1) to 200 places is the following
>> (DE (ARCTAN Y) (TIMES Y (DIV 1 (PLUS 1 (TIMES Y Y))) (ARCTAN1 Y 0 1 1 1e-220#))) == >> (DE (ARCTAN1 Y S J TT EPS) (COND ((LTE TT EPS) S) (T (ARCTAN1 Y (PLUS S TT) (PLUS J 2) (TIMES TT (PLUS J 1) Y Y (DIV 1 (PLUS 1 (TIMES Y Y)) (PLUS J 2))) EPS)))) == >> (ARCTAN 1.0#) == >> (TIMES 4 (ARCTAN 1.0#)) ==
During the last three days I feverishly worked to change the system from Lisp 1.6 style to Lisp 1.5 style. Maybe it became a bit slower by this (but is still quite fast for an interpreter) but of course a statically scoped Lisp with full FUNARG feature is aesthetically much more rewarding.
Before that I also embellished the user interface by enhancing the input window with a matching parenthesis indicator, which is indispensible for Lisp. I also extended the reader to accept ' for QUOTE and #' for FUNCTION.
My next plans: Implement FIXNUMS as aliased pointers. Maybe include infinite precision integers from the GMP library. Medium term goal for arithmetic: Being able to compute Pi to several thousand places.
Further plans: Make a ProLisp compiler (in ProLisp) which generates code for an abstract machine especially suited for executing symbolic code. Implement this machine on an FPGA (I already bought a Spartan 3 Starter Kit board from Xilinx),