pLISP © '98 Thomas Mahler

Parallel Functional Programming

pLISP is an experimental Implementation of parallel functional Programming. It is based on massive parallel graph-reduction machine.

During my research on this subject I implemented it in different languages for a variety of platforms. The most portable are the Java and Standard ML implementations. I developed C++ GUI versions for the WIN32 platform and Linux (KDE 1.1)

Main Features

• Lisp-like Syntax, convenient Graphical User Interface
• Hybrid architecture providing simple lisp interpreter, Incremental Compiler and Graph-reduction VM
• Implements lazy evaluation (Normal order reduction)
• The efficient Graph reduction Machine detects strict Operations
  and performs parallel evaluation of the subgraphs
• Full AND/OR-Parallelism like in ParLisp
• Special P-Combinator for defining explicit parallel processes
• Save Printing of circular Expressions
• portable Commandline Versions
• GUI Frontends for Linux (X11, KDE1.1) and Win32
• Clean Interface definition supports all major component architectures (DCOM, JavaBeans, Java RMI, Corba)

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 is available only in German.

Implementations

• C++ (GUI Version for Win32 Platform)
• JAVA should run on any JDK 1.1 compatible VM
• Standard ML (needs functors and won't thus run on subset implementations like Moscow ML)

Related Works

Lambda-Calculus

Combinatory Logic

PolyContextural Logics

(c) '98 Thomas Mahler