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

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Fri Mar 10 22:56:19 EST 2006

Please take a look at Mike Ernst's paper in the 2005 OOPSLA. You might 
find it interesting. -- Matthias

On Mar 10, 2006, at 9:48 PM, Paul Schlie wrote:

> 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
> parallel.
> 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
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme

Posted on the users mailing list.