2009/9/8 Aubrey Jaffer <[email protected]> > | Date: Sun, 06 Sep 2009 19:21:58 -0400 > | From: "Aaron W. Hsu" <[email protected]> > | > | ... > | On the other hand, we should also keep in mind that while > | parallelizing in Scheme is a very nice idea and can yield > | theoretical benefits, at the moment, automated parallelization is > | nowhere near ready for use. > > Automated parallelization is about converting a serial program (with > side effects, eg. FORTRAN) to a parallel one; because of the halting > problem, it is undecidable. > > On the other hand, a functional program, or the purely functional > parts of a program, can be parallelized very simply: argument > expressions can be evaluated concurrently or in any order. With no > side-effects, there is no way for the evaluation of one argument > expression to affect the evaluation of another. > > Implicitly-Parallel-Scheme exploits the small difference between "The > order in which the subexpressions of an application are evaluated is > unspecified" and concurrent evaluation. The program specification is > then no longer serial. This removes the "automated parallelization" > burden from a concurrent compiler. > > For more insight on concurrent evaluation of arguments in Scheme, I've found this explanation illustrative:
http://okmij.org/ftp/Computation/serialization.html Oleg explains *what* "serializable concurrency" means in R5RS/R6RS. He does not explain the reasons *why* this constraint remains in R5RS/R6RS, though. I think (and this is personal opinion, of course) that this requirement remains there because of the formal background that backs-up Scheme (lambda calculus/denotational semantics). > | Since it appears that industrial needs are the first on the list of > | things to address with Scheme, I'd say that more work on developing > | higher-level abstractions on concurrent programming processes, > | based on a thread model, should see a lot of attention, simply from > | the fact that automatic parallelization isn't going to be ready for > | a while. I am in favor of improving the ability of Schemes to do > | research in this area, of course, but I'd like to know how Scheme > | implementations right now take advantage of the sequential order > | mandate first. > > Any single-threaded (and non-preemptive) Scheme implementation is > already an Implicitly-Parallel-Scheme, which is the great majority of > implementations. Implicitly-Parallel-Scheme does not require an > implementation to use concurrent execution; but it enables > implementations to employ concurrent execution (perhaps only for > functional expressions) at their option. > Exact. The idea here is to enable, improve and specify, and not impose, concurrent execution of Scheme. After all the future is having lots of processors available, and even processors with vectorial/parallel capabilities ( http://www.nvidia.com/object/cuda_home.html, http://en.wikipedia.org/wiki/OpenCL). Enabling, specifying and improving (not imposing) how Scheme is expected to work in those environments is a real need. As an example: the "concurrent serializable" constraint applies to evaluation of lambda arguments, but I haven't seen such a constraint for evaluating "map" concurrently. The R6RS specification for map says "Proc should not mutate any of the lists. The map procedure applies proc element-wise to the elements of the lists and returns a list of the results, in order. Proc is always called in the same dynamic environment as map itself. The order in which proc is applied to the elementsof the lists is unspecified." The report should emphasize that "proc" should have no side effects (not just on the lists, but everywyhere). It should not impose a concurrent evaluation, just specify if concurrent evaluation of map is allowed or not. Finally, explicit parallel Scheme is, in my opinion, the *wrong* way to go (as explicit memory management is, for instance). Understanding explicit parallel programs (either in Scheme or any other language) is usually difficult. Debugging and maintaining them is usually the worst nightmare of a developer. (I can't imagine debugging a Scheme program with threads, semaphores, locks, and continuations all messed up). Cheers, Antonio
_______________________________________________ r6rs-discuss mailing list [email protected] http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
