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 w