webLISP

'97 Thomas Mahler

Why 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.

 

Main Features

 

Introduction

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!!

 

Content

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

 

Installation

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

Usage

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:

Examples

(+ 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!!) 

Language Documentation

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

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).

 

Integer Operators

Operator computes
(+ x y) x + y
(- x y) x - y
(* x y) x * y
(/ x y) / x y

 

Control and Logical Functions

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.

 

List Processing

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.

System Commands

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.

stats
Prints out JavaVM total memory and free memory.
In addition a JAVA Garbage Collection is startet.
verbose
Toggles verbose mode on/off. If verbose is on, every reduction step of the Virtual machine is displayed.
You find information about the evaluated Combinator, its arguments, the reduction result.
After each step the complete Tasks-list which is managed by a stochastic Scheduler is displayed
tasks
after any evaluation the maximum number of created tasks and the total sum of reduction steps is displayed.
exit
quit the webLISP Interpreter.
 

 

 


Related Works

Lambda-Calculus

Combinatory Logic

PolyContextural Logics

 


(c) '97 Thomas Mahler

mailto:tm@bov.de
http://www.techno.net/pkl