webLISP
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.
| weblisp.class | The
toplevel Lisp-interpreter 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 |
| GraphInterface.class Graph.class |
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 |
| deutsch.dvi | german documentation |
| english.dvi | english documentation |
| index.htm | this text |
Expand the
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):
JAVA-LISP v0.1
(c)'97 Th. Mahler
input: (+ 2 3)
MaxTasks: 1 | Steps: 1
value: 5
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
value: 5040
// verbose
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: verbose
input: (+ 1 2)
spine: +
top: (+ 1)
+
red +: 3
[]
MaxTasks: 1 | Steps: 1
value: 3
input:
(+ 2 3)
(* (- 5 2) (/ 100 2))
(define var 57)
(+ var 100)
((lambda (n) (+ n 1)) 99)
(define add1 (lambda (n) (+ n 1)))
(add1 567)
(define fac (lambda (n) (if (= n 0) 1 (* n (fac (- n 1))))))
(fac 3)
// 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)))
//whats this?
(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:
| Combinator | Reduction Rule |
| (I x) | x |
| (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).
| Operator | computes |
| (+ x y) | x + y |
| (- x y) | x - y |
| (* x y) | x * y |
| (/ x y) | / x y |
| Operator | computes |
| (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
parallel languages.
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.
| function | computes |
| (cons 1 (quote (2 3))) | (1 2 3) |
| (car (quote (1 2 3))) | 1 |
| (cdr (quote (1 2 3))) | (2 3) |
| (quote x) | x |
| (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 Mahler
mailto:tm@bov.de http://www.techno.net/pkl