[plt-scheme] immutability and parallelism (was ... immutable pairs)

From: Paul Schlie (schlie at comcast.net)
Date: Fri Mar 10 21:48:27 EST 2006

After some thought, it seems that eliminating default mutable pairs and
respective modifying operators may not the correct solution to a broader
goal of enabling scheme to be more efficiently physically evaluated in

More specifically, if the true goal is to be able to clearly determine if
a given data structure (representing either code or data) may be accessed
in parallel by multiple logically distinct threads of execution evaluating
an otherwise single logical program thread of code, without otherwise
necessarily requiring a full data/control flow analysis of that program;
then I can't help but wonder if the more broadly correct approach, without
needing to eliminate what may be considered by many a powerful construct
historically inherent within the scheme language, would be to augment the
language by which function operands may be declared as being warranted as
not being mutated by the function (to which I'd personally also require
a logical left->right argument evaluation order, as although this would
seem to complicate parallel evaluation, it truly enables the reliable
deterministic parallelization of code which may otherwise be ambiguous
to benefit of none, other than potentially arguably lazy compiler writers).

Thereby, only a function's definition need be inspected to determine the
immutability of it's operands within the context of the function, where
the operands themselves need not be immutable themselves.

Where then one could use : or whatever to identify a const operand:

(define (foo :x :y z) ; declaring x y as being immutable within foo
  (set-car z (+ x y)  ; ok! as it's mutable.
  (set-car x (+ x y)) ; no! as it's immutable.

(foo (foo a b c) (foo a b d) c) ; thereby known that (foo a b c) and
                                ; (foo a b d) may be evaluated safely
                                ; in parallel, and c may not be evaluated
                                ; until (foo a b c) is completed.

(where performance of a non-strongly typed language is a different issue)

| Where as an aside, it would seem that simple macros could be defined
| by defining that quoted function operands are simply not evaluated:
|  (define (bar 'x y)
|   (display x)
|   (display y))
|  (define b 1)
|  (bar a b) => a1

Posted on the users mailing list.