Governance by those who do the work.

Sunday, November 15, 2009

Implicitly Concurrent `map'

In my first Implicit Concurrency post I stated that
The Scheme Reports mandate an unspecified-but-serial evaluation order for arguments to procedure-calls, `let' bindings, `letrec' bindings, `do' bindings, and `map'.
The only RnRS mention of concurrency appears in the description of Procedure call:
Note: Although the order of evaluation is otherwise unspecified, the effect of any concurrent evaluation of the operator and operand expressions is constrained to be consistent with some sequential order of evaluation. The order of evaluation may be chosen differently for each procedure call.

Because `do', `let', and `letrec' bindings are defined in terms of (`lambda' and) procedure calls, this restriction applies to them as well.

But the Reports are silent as to the evaluation order for `map'; so it shouldn't have been included in my list.

If the Implicitly Concurrent future is already here, why is it a secret? Because misunderstanding of `map' evaluation order is widespread; in [R6RS] Will `map' order remain unspecified?, W. Clinger writes:

... expecting map to process its elements from left to right has been perhaps the most common order-of-evaluation bug in R5RS programs.

There is a deep connection between concurrent `map' and the other implicit concurrencies. If a metacircular-interpreter uses a concurrent `map' to evaluate arguments to procedure calls, then that interpreter's procedure calls will also be concurrent.

Implicit concurrency can thus be viewed as a basic property of a computing platform. A concurrently-repeatable metacircular-interpreter can be written without using explicit-concurrency primitives which is concurrent when run by a concurrent (implicitly concurrent) implementation and serial when run by a serial implementation.