Fun: Lisp is fun, Lisp on the web is more fun, Lisp in your own Browser is just ...
Research: webLISP is based on a parallel operating GraphReduction Machine. It is a showcase for JAVA-programming techniques and a Toolbox for experimenting with Lambda-calculus, Combinatory Logics and Parallel Processing.
webLISP is an experimental Implementation of reflective functional Programming. It contains a very simple Lexer and Parser for a lambda-calculus language in lisp-syntax. The Lambda terms are compiled to variablefree Combinator Graphs. The virtual Graph-Reduction-Machine that reduces the Combinator-graph distinguishes between strict and non-strict operations. Strict operations have to be evaluated even if we obey lazy evaluation and can thus be evaluated in parallel to the main computation. The parallel computations are added to a global task pool, which is maintained by a stochastic scheduler.
In addition to this basic implemenation a special Combinator P is introduced which performs an asyncronous parallelism of two given applications. P (app1 rator1) (app2 rator2) --> (quote parEval(app1 rator1) parEval(app2 rator2))
If rator1 and app2 point to the same object X, you get the funny result, that the same object is used simultaneously as Operand (by app1) and as Operator (for rator2), because both applications are evaluated in parallel: P (app1 X) (X rator2)
This special situation is quite ambigious and "dangerous" for it disturbs the predictability of computational systems. Although it looks a bit awkward and arises many problems in traditional calculi, this Relationship can be formalized by PolyContextural Logics (PCL), which describes it as the "Proemial relationship"
This Relationship is useful in formalizing self-referential, contradictory, autopoietic etc. systems. It is also quite helpful in the formalisation of meta-level architectures and computational reflection.
The aim of the webLISP project is to build a LISP-like Programming language which is capable of implementing such architectures.
As you will recognise, the implementation is rather small and includes until now only the most necessary features. However you can feel free to experiment with this toolbox, improve it, discard it... or give some feedback for further developments.
Disclaimer: Experimental Implementation, no warranty of any kind!!
Download the complete webLISP Environment with this ZIP File.
This Archive contains all neccessary Java-classes, the Java-sources, a short documentation in english and german and this Hypertext Environment.
as an Java-Applet (like on the top of this page)
|lisp.class||The toplevel Lisp-interpreter
to start the Program call it with Jview
eg. under NT: jview.exe lisp.class
|compile.class||Compiler Lambda --> Combinatory Logic|
|Definition of the binary graph data structure|
|KombGraph.class||Kombinatory Logic in binary Graphs
an the virtual Graph reduction machine
|Lambda.class||Lambda terms, Parser, Variable abstraction|
|NoSpineKombinator.class||an exception class|
|reader.class||rudimentary lisp lexer|
|test.class||driver class with several experiments,
try this to experiment with the naked
machine without interpreter toplevel
|*.java||the corresponding sources|
ZIP-File to a local folder on your system.
To see the Applet-version, open the file frameset.htm with your Browser (Frames and JAVA-support required).
To work with the standalone Version call lisp.class with the jview programm. Eg. under NT: jview.exe lisp.class
At the input:-Prompt you can enter some lisplike statements. After typing <return> the machine computes and displays the result at the output:-Prompt. For analyzing purposes you can set a verbose-flag, so that the number of created Tasks and the number of needed evaluation steps are displayed for each evaluation. In lambda-calculus it is very easy to produce non-terminating computations. This one is probably the shortest: (Y Y). In a classical language this is a catastropy, in lambda-calculus it increases fun. If you produced a non-terminating computation, just reload the page and the Interpreter is alive again.
See demo session below (the following is taking from the standalone version):
(c)'97 Th. Mahler
input: (+ 2 3)
MaxTasks: 1 | Steps: 1
input: (define fak (lambda (n) (if (= n 0) 1 (* n (fak (- n 1))))))
MaxTasks: 1 | Steps: 1
value: ((define (DEF fak)) ((S ((S ((S (K if)) ((S ((S (K =)) I)) (K 0)))) (K 1)
)) ((S ((S (K *)) I)) ((S (K (DEF fak))) ((S ((S (K -)) I)) (K 1))))))
input: (fak 7)
MaxTasks: 57 | Steps: 1425
switches Verbose mode of the combinatory
// machine on and off.
// For each reduction-step the spine (Combinator to be
// reduced), the top (active node of the graph), the
// red-result and the resulting Tasks-vector are displayed
input: (+ 1 2)
top: (+ 1)
red +: 3
MaxTasks: 1 | Steps: 1
(+ 2 3)
(* (- 5 2) (/ 100 2))
(define var 57)
(+ var 100)
((lambda (n) (+ n 1)) 99)
(define add1 (lambda (n) (+ n 1)))
(define fac (lambda (n) (if (= n 0) 1 (* n (fac (- n 1))))))
// definition of recursion for use with Y-Combinator:
(define fact (lambda (f n) (if (= n 0) 1 (* n (f (- n 1))))))
(Y fact 3)
//The Ackermann-function (define a (lambda (n m) (if (= n 0) (+ m 1) (if (= m 0) (a (- n 1) 1) (a (- n 1) (a n (- m 1)))))))
//Count counts down from n to 0 (define count (lambda (n) (if (= n 0) 0 (count (- n 1)))))
//Y Combinator version of count (define countY (lambda (f n) (if (= n 0) 0 (f (- n 1)))))
//Computing with LISTS
input: (car (cdr (cons 1 (cons 2 3)))) value: 2
// length computes the length of a linear list (define length (lambda (l) (if (atomp l) 1 (+ 1 (length (cdr l))))))
//Building S-expressions and evaluate them: input: (eval (cons (quote +) (cons 40 60))) value: 100
//definition of a self-reproducing lambda-term:
(define d (lambda (x) (x x)))
(P d d d d) // (any ideas how you might call such entity are most welcome!!)
webLISP is an experimental System and thus rather small. It contains until now only Integer arithmetic and basic LISP-like symbolic computation and list processing.
Combinators are the
foundation of this implementation. All Lisp statements typed in
at the Interpreter prompt are internally compiled to Combinator
Graphs, which can be efficiently evaluated by the virtual
machine. Normally these Combinators are only called implicitly,
but you can invoke like usual other functions.
The basic Combinators are:
|(K x y)||x|
|(S f g x)||((f x)(g x))|
|(B f g x)||(f(g x))|
|(C x y z)||(x z y)|
|(Y f x)||(f (Y f) x)|
|(P (f x) (g y))||(P parEval(f x) parEval(g y))|
The P-Combinator is not a
classical Termtransformation. On the term level it does not
change anything. But it produces two asynchronous Tasks (f x) and
(g y) that are left on their own.
This Combinator is used to produce explicit parallelity. If both processes work with equal variables, the processes are linked like in (P (f x)(g x)).
With the P-Combinator it is possible to create interesting topologies like (P (f x) (x y)). In the first process x functions as the operand, in the second it is the Operator. And this categorical exchange is performed simultaneously!
Such computational topologies are found in Polycontextural Logics (where they are formalized as "Proemial Relations", meta-level architectures, computational reflection with causal connection and in simulations of self-referential, paradoxical and autopoietic systems.
For further explanation on this theme see this one (dvi file).
|(+ x y)||x + y|
|(- x y)||x - y|
|(* x y)||x * y|
|(/ x y)||/ x y|
|(not x)||1 if (x == 0) else 0|
|(and x y)||1 if (x == 1 and y ==1) else 0|
|(or x y)||0 if (x == 0 and y ==0) else 1|
|(if test thenPart elsePart)||thenPart if (test == 1) else elsePart|
|(= x y)||1 if (x == y) else 0 ; (only for integers)|
|(eq x y)||1 if (x == y) else 0 ; (for all objects)|
|(atomp x)||1 if x is a number or a symbol else 0|
The logical functions and
and or are parallelized like in ParLisp or other
Consider the following term:
(and (not 1) (Y Y))
In a classical language --
where both arguments have to be computed before the main function
can be evaluated -- this term would not terminate because of the
infinite loop (Y Y).
The reduction of and in webLISP is organized in a such way that two synchronized Subtasks are generated, that compute the arguments. At the same time the original and function is kept active. When the first argument (not 1) is evaluated to 0, the main function detects that one of its arguments equals 0. It can thus return 0 without computing both arguments. The evaluation of (Y Y) is then stopped, because it is not longer required.
The or-function is parallelized in an analogous way.
|(cons 1 (quote (2 3)))||(1 2 3)|
|(car (quote (1 2 3)))||1|
|(cdr (quote (1 2 3)))||(2 3)|
|(eval (quote (+ 1 2)))||3|
|(define var val)||(binds the value val to the symbol var in the global environment)|
There is only one global environment for defining values and functions at the top-level. For the actual computation no environment like in other LISP-Implementations is needed. This is a positive effect of the compilation to variable-free combinator-terms.
These System Commands give some additional insights in the internal operating of the virtual machine. These Commands are only available in the standalone Version of webLISP.
(c) '97 Thomas Mahlermailto:email@example.com http://www.techno.net/pkl