ProLisp
Generalities
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 !)
Features
Pro Lisp's features:
- datatypes: atom, string, integer, float, double, array
- arithmetic functions: plus, minus, times, divide, sin, cos, tan, arcsin, arccos, arctan, exp, log, sqrt
- logic functions: and, or, not
- comparisons: lt, lte, eql, gte, gt, eqp (equality of pointers)
- type tests: atomp, fixp, floatp, numberp
- lisp specific functions: car, cdr, cons, maplist, setq
- control structures: cond, if, while, for (c-style)
- modules with declared local variables, statement sequences.
- possibility of C-style input, lex-yacc controlled transformation module supplied in code
Possible Use
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
Go to the project page prolisp at sourceforge.
Installation
-
Unpack in an appropriate $(SRCDIR), e.g. $(SRCDIR)=$(HOME)
tar -xvzf prolisp-0.1.0.tar.gz - A subdirectory appears: $(SRCDIR)/prolisp
- Execute from $(SRCDIR): cd prolisp
- ./make all
- in $(SRCDIR)/prolisp/bin there is now the executable prolisp
- if needed, copy prolisp to another directory (or do a 'make install' in $(SRCDIR)/prolisp)
Starting ProLisp
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 (PI N) which computes a
list of all primes less than or equal to N. (Hint: it can be done with the functions
introduced above. Further examples for input you find in
test.lsp
Changelog
2006/03/24
Moved over to Qt 3.0 as GUI framework, so that everything compiles now on
my new machine (Linux/x86-64/SuSE 10.0).
Also removed the _asm statements from the eval loop and substituted
standard C++ code for them.
There remains much to be done, for example atoms in functional position
whose values are closures (or defined functions) are up to now
evaluated and their value used as function. This is in contrast to
Common Lisp style, where one has to use "funcall". So
I sometimes will have to change that.
Finally, the cerr cout redirection into the lower pane of the splitted window
is disabled at the moment, as I will have to rewrite the code for that.
2005/08/05
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.
P.S. Now (2005/08/06) I could remove the glitches in the output. Still
the code I used is - as far as I think - a bit questionable.
P.P.S. If the output window is running full of error messages, press Control-D
in the Lisp-Window. It should stop the avalanche of
error messages.
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...).
2005/05/03
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#))
==
2005/04/30
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),
Addendum
For a different approach to interpreting Lisp, namely defining a complete Lisp in a restricted subset of it, see my page about a new project I am currently working on. It is preliminary called meval.
