| Date: Tue, 15 Sep 2009 20:05:20 -0400 | From: "Aaron W. Hsu" <[email protected]> | | On Sun, 13 Sep 2009 23:21:44 -0400, Aubrey Jaffer <[email protected]> wrote: | | > | Date: Sun, 13 Sep 2009 21:14:01 -0400 | > | From: "Aaron W. Hsu" <[email protected]> | > | | > | ... | > | However, it seems that you or someone else has also brought up | > | the point that the standards actually do permit such | > | optmizations provided the serializability of the parts. | > | > To parallelize a serial program is in general an undecidable | > problem. | | Are you saying that it is impossible to effectively or usefully | identify when it is safe to parallelize Scheme code because it is | impossible to determine whether parallelizing code will not | potentially result in an incompatible behavior,
Yes. Lets look at this from the compiler's perspective. When encountering an expression (list (u) (v)), a parallelizing RnRS compiler must commence an analysis of U and V and everything they call, possibly including other modules, to determine whether any side effects to shared state might depend on concurrent execution order. And there is no guarantee that such an analysis will terminate (Halting Problem). When a parallelizing IPS compiler encounters (list (u) (v)), it immediately knows that it can delegate the computation of (u) and (v) to distinct threads. This might seem like a major change to Scheme, except when you consider how similar thread-safety is to the (programmer) constraint to produce identical behavior regardless of execution order. | > | Are you saying that the standards now don't permit parallel | > | optimizations to take place? It appears to me that they do, | > | and that Scheme is, even now, welcome to lead the forefront in | > | parallelization. | > | > Without a change to the language, Scheme would be no more | > parallel than FORTRAN-77. | | Outside of the issue of undecidability of determining the | serializability of parallel execution (if that's what you are | asserting above) I can think of no theoretical limitation on | Scheme's semantics that prohibit parallel execution in this area. | Maybe I'm missing something? I'm not sure where you are getting | this requirement that Scheme be sequential by explicit requirement. "Outside of the issue of undecidability"? The Halting Problem is a fundamental constraint of code analysis! Ignoring the Halting Problem in creating a language specification is folly. _______________________________________________ r6rs-discuss mailing list [email protected] http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
