pLISP
© '98 Thomas Mahler

Basic Concepts of Parallelity in pLisp

This File presents some demos for the parallel features of the underlying VM of pLISP

1. strict operations

There are implicit mechanisms that spawn new subtasks if the VM detects possible parallelity.
All the standard Combinators S, K, I, Y, B, B', B*, C, and C'are nonstrict operations that don't evaluate their arguments.
Thus there is no chance for any parallelity in evaluating them. But arithmetic operations like (+ x y) need their arguments in normal form.
Thus x and y have to be complete evaluated before the final addition may be performed. Obviously it is possible to reduce x and y in parallel.

Experiments with the fib function will show this behaviour:


// define recursive fibonacci function:
input: (define fib (lambda (n) (if (= n 0) 1 (if (= n 1) 1 (+ (fib (-1 n)) (fib (- n 2)))))))
value: (lambda (n) (if (= n 0) 1 (if (= n 1) 1 (+ (fib (-1 n)) (fib (- n 2))))))
// compile it to a combinator logic subroutine (marked by ccsubr)
input: (cf 'fib)
value: (ccsubr_ (S (C (B . if) (C . =) . 0) . 1) (S (C (B . if) (C . =) . 1) . 1) (S ((B* . +) . fib) . -1) (B . fib) (C . -) . 2)
// compute fib 10:
input: (fib 10)
steps: 3969 :: threads: 6
value: 89
// Read: Combinator VM needed 3969 reductions and spawned 6 parallel threads

// now we enable the stochastic scheduler for full parallel reduction:
input: (stochastic)
value: 1
// now we run fib again
input: (fib 10)
steps: 3969 :: threads: 55
value: 89

This means that (fib 10) evaluates to 98, takes 3969 VM steps and runs up to 50 parallel tasks.

2. semi-strict Operations

Other operation like (AND x y) and (OR x y) are semi-strict. Generally x and y have to be in normal form before the boolean operation may be performed.
But if x and y are reduced in parallel it is possible that y has been successfully reduced to TRUE while reduction of x is caught in a non-terminating computation. If we would insist on strictness the term (OR x y) would also be non-terminating.
On the other hand we know that (OR TRUE z) == TRUE for any z.
Thus is it straightforward to reduce (OR x y) to TRUE if any of the subexpressions is reduced to TRUE even if the other subexpression is still being reduced (or even a non-terminating computation).
This implementation of implicit AND- and OR-Parallelity is quite similar to PARLISP.
Have a look at the functions andtest and ortest below and study their reduction behaviour.
Both functions terminate although they contain non-terminating subexpressions ( (D D) in our case).
TRUE is represented by 1 and False by 0 in our system.


// countdown counts from n down to zero
// this is used to waste some VM time
 (define countdown (lambda (n)
   (if (= n 0)
     0
     (countdown (-1 n))))) 
 (cf 'countdown)


// D is a selfreproducing lambda expression
// (D D) reduces to (D D) and so forth...
// we use it to produce a non-terminating computation
 (define D (lambda (x) (x x)))
 (cf 'D)

// andtest shows the parallelity of the underlying VM
// although the left side (D D) does not terminate
// the root expression (and ...)  evaluates to FALSE (0)
// because the right side evaluates to FALSE
 (define andtest (lambda (foo )
   (and (D D) (-1 1)))) 

 (cf 'andtest)

 (andtest 'bar)

 (define ortest (lambda (foo )
   (or (D D) (+ 0 1))))
 (cf 'ortest)

 (ortest 'bar)

3. Explicit Parallelity with the P-Combinator

The VM contains a special P Combinator for Parallel reductions.
P x y reduces to QUOTE x y while x and y are running as independend Tasks

 (define ptest (lambda (foo)
   (P (+ 1 1) (+ 3 4)))) 
 (cf 'ptest)
 (ptest 'bar)