pLISP
'98 Thomas Mahler

Table of Content

Parallel Functional Programming

Main Features

Concepts

Disclaimer & Copyright

Content of the archive

Installation

Usage
- Commandline Version
- GUI Version

Examples

Language Documentation

Related Works


Parallel functional Programming

pLISP is an experimental Implementation of parallel functional Programming. It is based on massive parallel graph-reduction machine. This special architecture has been implemented for several platforms in Standard ML and Java. This pLISP edition is a C++ Implementation. This edition includes portable source code for a command line oriented application and a GUI version for the WIN32 platform. This edition is mainly concerned with presenting our approach of parallel functional programming utilizing a very convenient graphical user interface. Second aim of this edition was to provide an optimized implementation of the former proof of concept implementations.

Picture 1: The pLISP Application


Main Features


Concepts

pLISP is an experimental Implementation of reflective functional Programming. It is built as a hybrid architecture using a simple Lisp interpreter for driving the compiler and wrapping calls to the Graph-reduction VM. 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 lazy evaluation is obeyed 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 pLISP project is to build a LISP-like Programming language which is capable of implementing such architectures. A short paper in English that provides a general overview is here. A detailed description of the approach and documentation of the implementation is only available in German.

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 & Copyright

Copyright 1998 ICS Institut fuer Cybernetic und Systemtheorie, Bochum, Germany. All rights reserved.
Copyright 1997,98 Thomas Mahler

This is copyrighted software. By using the software, you agree to the following terms and conditions.

1. License for personal non-commercial use.
You may use the software only for your personal, noncommercial use.

2. No redistribution.
You may not distribute copies of the software to others.
You may not place the software on any web site, Internet server, electronic bulletin board, //
or other information retrieval systems.

3. No warranty.
THIS SOFTWARE IS PROVIDED "AS IS" AND WITHOUT WARRANTY OF ANY KIND.
TO THE MAXIMUM EXTENT PERMITTED BY LAW, THE AUTHOR DISCLAIMS ALL WARRANTIES,
EXPRESS OR IMPLIED, INCLUDING WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.

4. Disclaimer.
IN NO EVENT WILL THE AUTHOR BE LIABLE TO YOU FOR ANY DAMAGES,
INCLUDING ANY LOST PROFITS, LOST SAVINGS, OR OTHER INCIDENTAL OR CONSEQUENTIAL DAMAGES
ARISING OUT OF THE USE OR INABILITY TO USE THE SOFTWARE.

5. Notice of experimental software.
THIS SOFTWARE CONTAINS PROGRAMS OF AN EXPERIMENTAL NATURE,
INCLUDING PROGRAMS THAT HAVE NOT BEEN FULLY TESTED.
YOU AGREE TO ASSUME ALL RISKS INVOLVED IN THE USE OF EXPERIMENTAL AND UNTESTED SOFTWARE.

6. General.
For commercial use or if you intend to modify the code and to distribute modified code
please contact the author:
mailto:[email protected]
http://www.techno.net/pcl


Content of the Archive

Download the complete pLISP 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.

winlisp.exe The GUI Application for WIN32 systems
ActiveLisp.exe Commandline Application without parallel features
ActiveLisp-P.exe Commandline Application with full parallel features
MSVCP50.DLL MS C++ Runtime library
dump.fasl dump of current lisp environment. Will be loaded on initial startup
init.lsp init.lsp is loaded on startup but after dump restore.
cc.lsp Source code of the compiler. Very helpful for learning concepts of combinatory based implementations of functional languages and basic pLISP programming techniques.
system.lsp some definitions regarding system settings.
par.lsp demo file explaining basic concepts of the parallel architecture and corresponding programming techniques
basics.lsp file containing small library of test and benchmarking function for testing interpreter, compiler an VM execution. Also helpful in learning pLISP Programming style.
deutsch.eps german documentation of theoretical concepts,
use Postscript viewer
like GhostScript to read this document
english.eps english documentation
doc folder documentation
src folder source code

Installation

Expand the ZIP-File to a local folder on your system. Ensure you have the MSVCP50.DLL in this directory. Start the Application of your choice.


Usage

Commandline Version

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 catastrophy, 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):

P-LISP Version 1.5 Console Version
(c)'98 Thomas Mahler

Build: Jun 27 1998
Options: _MY_MEM, _NV_GC, _PTHREADS
Allocating 100000 Nodes...
loading Lisp file dump.fasl ...
(restoring world from "dump.fasl")
...finished loading
loading Lisp file init.lsp ...
input: (define fak (lambda (n) (if (= n 0) 1 (* n (fak (- n 1))))))

2 calls to eval
value: (lambda (n) (if (= n 0) 1 (* n (fak (- n 1)))))
input: (cf 'fak)

2972 calls to eval
value: (ccsubr_ (S (C (B . if) (C . =) . 0) . 1) (S . *) (B . fak) (C . -) . 1)
input: (fak 10)

steps: 189 :: threads: 1
3 calls to eval
value: 3628800

GUI Version


Examples

See files cc.lsp, basics.lsp, par.lsp for illustrating examples.

Language Documentation

pLISP 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)
(B' w x y z) (w x (y z))
(B* w x y z) (w (x (y z)))
(C' w x y z) (w (x z) y)
(S' w x y z) (w (x z) (y z))
(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. The creation of asynchronous tasks is indicated by the index parEval.
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 (Postscript 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 pLISP 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.

 

Microcode Arity Description
Interpreter Version    
* 2  
+ 2  
+1 1  
- 2  
-1 1  
/ 2  
< 2  
= 2  
> 2  
alloc 1  
append 2  
appendwoc 2  
atomp 1  
car 1  
cdr 1  
cons 2  
copy 1  
dump 0  
equal 2  
explode 1  
gc 0  
implode 1  
last 1  
length 1  
microcodes 0  
mktree 1  
nfirst 2  
nogc 0  
not 1  
np 1  
nth 2  
nthcdr 2  
null 1  
numberp 1  
pp 1  
print 1  
printdepth 1  
printlength 1  
r 1  
reverse 1  
rplacd 2  
rplacw 2  
set 2  
top 2  
trace 0  
verbose 0  
     
Graph-reduction VM
microcodes:
   
     
* 2  
+ 2  
+1 1  
-1 1  
< 2  
= 2  
P 2  
and 2  
not 1  
or 2  
 

GUI Application

The GUI Application uses the same functional kernel but provides much more "sugar" for developing pLISP Applications. The basic concepts are described in this section. This Implementaion incorporates a lot of useful tips and code from the CodeGuru (MFC Developer SourceBook) Site, which is really an indispensably aid for any Windows C++ Developer.

Editor
PLisp uses the Multiple Document Interface (MDI) to allow editing of one or more lisp source files. The Editor works like any standard windows editor. In addition it provides basic support for lisp syntax: a simple mechanism detects unmatched closing brackets. If you place the cursor behind a ")" it will mark everything till the matching "(". If no matching "(" is found a message is displayed in the statusbar.

Basic operations like cut and paste are available from the Edit-Menu and from the context menu (right-click in the editor, see picture 2).

Picture 2: The pLISP Editor and its context menu

The context menu provides some lisp-specific functions:

Eval Region
Evaluate the selected region as a lisp expression.
Inspect
Inspect symbols
Compile Function
If the marked expression is an uncompiled function it can be compiled to a Combinator Logic subroutine.
UnCompile function
If the marked expression is a compiled function it can be uncompiled to the original lambda-term
(trace)
Toggle Trace Mode on and off. Trace will provide a full trace of the call to apply of the outer lisp interpreter. The Combinator VM is not traced in this mode.
(verbose)
Toggle Verbose Mode on and off. Verbose provides full trace of eval, apply and the inner Combinator VM. Useful only for diagnostic purposes, as it decreases performance radically.
(my-hook)
Calls the zero argument function my-hook. My-hook may be redefined according to your needs to perform any lisp task. Have a look in "system.lsp" for definition of my-hook.

The Editor provides also basic file operations that can be found in the File-Menu:

New, Open, Close, Save, Save As
Standard File operations for Lisp files.
Load Lisp File...
Execute all code in a selected file. Works on Lisp source file (*.lsp) as well as for FastLoad Files (*.fasl).
Preserve Lisp World...
Preserve the global environment to the file dump.fasl. This file is loaded on startup of the winLisp Environment. Thus this function can be used to preserve the state of your current lisp session.
Print, Printer-Setup
Print active lisp file, Setup the Printer
Exit
Quit winLisp.

The most important operations can be found on the Standard Toolbar (see Picture 3) as well.

Picture 3: The Standard Toolbar.

 

Lisp Prompt
The Lisp Prompt Toolbar (see Picture 4) can be used to type in short expression, which you want to evaluate interactively. You can type in code into the combo box or select one of the last expressions typed in. To evaluate the expression press <RETURN> or click on the Eval! Button (blue double arrow icon right to the combo box).
Evaluation is fully threaded and can thus be controlled by the Stop button (cross icon right to Eval! Button).

Picture 4: The Lisp Prompt Toolbar

Output Window
All Output of the Interpreter is directed to the Output Window (see Picture 5).
By default output is flushed to this window only in the end of an evaluation. For some cases (e.g. traces) you will prefer threaded Output, which pumps output from the output-queue in parallel to the actual computation. You can switch this on with the command "Threaded Logging" from the Lisp Menu.

Picture 5: Output Window


Related Works

Lambda-Calculus

Combinatory Logic

PolyContextural Logics


(c) '98 Thomas Mahler

mailto:[email protected]
http://www.techno.net/pkl