© '98 Thomas Mahler
|
pLISP © '98 Thomas Mahler |
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
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.
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
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 |
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.
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
See files cc.lsp, basics.lsp, par.lsp for illustrating examples.
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 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).
| 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 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.
| 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 | |
| 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 |
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:
The Editor provides also basic file operations that can be found in the File-Menu:
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
(c) '98 Thomas Mahler
mailto:[email protected] http://www.techno.net/pkl