| Date: Thu, 10 Sep 2009 17:45:43 +0300
| From: Vitaly Magerya <[email protected]>
|
| Aubrey Jaffer wrote:
| > An example of an exception
| > is the use of a pseudo-random-number-generator having shared state:
| >
| > (require 'random)
| > (+ (random 99) (random 99))
| >
| > The concurrency-safe version could be written:
| >
| > (require 'random)
| > (let* ((rnd1 (random 99))
| > (rnd2 (random 99)))
| > (+ rnd1 rnd2))
|
| I have a rather long list of questions, some of which are more like
| statements; but please bear with me, as I want to understand the
| implications of such design better.
|
| For one thing, `let*'-wrapping in addition to preventing
| concurrency also restricts the order of evaluation; but you only
| want sequential, and don't care which exactly.
I think such situations are infrequent.
One of the important attributes of a seedable pseudo-random number
generator is that it allows a computation to be repeated by starting
with the same seed. A program containing:
(expt (random 42) (random 42))
will not be portable between R5RS or R6RS implementations because the
order of evaluation is unspecified. So that expression could be
considered a bug in current Schemes. Some Implicitly-Parallel-Schemes
will be able to catch this error at runtime (because the SLIB RANDOM
procedure checks for reentry).
| Note that many optimizing compilers shuffle the order of evaluation
| to achieve better register usage.
Yes! Scheme programmers are already responsible for not depending on
evaluation order of argumentss, LET, LETREC, etc. Most of these
errors are only exposed when a program is run on different
implementations, and can be very difficult to locate. A concurrent
implementation of Implicitly-Parallel-Scheme could help finding such
bugs.
| So shouldn't we specify additional sequential-call form (`scall')
| to explicitly mark call sites where you want to forbid concurrency?
Wrapping a let* around a call allows one to make sequential just those
arguments evaluations which need to be sequenced. SCALL will usually
make more evaluations serial than need to be.
| I wonder what would be the ratio of explicitly sequential call
| sites to implicitly concurrent one in a typical program. Or may it
| be better to explicitly mark concurrent call sites (e.g. with
| `pcall'), not the sequential ones?
Eyeballing a Scheme-to-Java translator (written in Scheme), it looks
like most calls are to procedures taking a single argument and all
that I see have an identifier in the function position. Those calls
don't have an sequential issues.
Next most frequent are two-argument calls and those that I see have
one or more atomic argument expressions. Also not a problem.
Only 9 of the 62 LETs and named LETs have more than one binding.
Those mulitple bindings are without side-effects.
No procedures passed to MAP have side-effects.
Lets look at this in a different way. The side-effecting forms in
this program are writing Java code, updating line-count, and
accumulating comment text. Because the Java code must be emitted in
the correct order, these updates are in COND clauses and procedure
bodies, which are sequential.
| Another thing, let's say I have an expression like this:
|
| (f (x) (y))
|
| Am I required to know if both `x' and `y' share the same mutable
| state, so I can't call them in parallel?
If the effect of calling `x' before `y' differs from the effect of
calling `y' before `x', then you are already screwed. So the
situation with Implicitly-Parallel-Scheme is not much different from
RnRS.
| What if I don't know (e.g. I'm calling some user-passed functions,
| or the documentation did not specify such details), do I change
| each call to `scall'?
No. (let ((xv (x))) (f xv (y)))
| What if at some point in the development both `x' and `y' where
| pure, but then I added `random' to both; do I now have to go
| through all the code that uses them and sequentialize the calls?
| Do I also have to find all the functions that call `x' or `y' and
| sequentialize calls to those functions as well?
Calling RANDOM with one argument is a convenience function. Better
practice is to call it with an explicit state argument. If those
state arguments are not shared, you are golden. If they are shared
(or absent), then your program is not portably repeatable in RnRS or
Implicitly-Parallel-Scheme. And a concurrent implementation of
Implicitly-Parallel-Scheme may catch the reentry. In any case,
introducing a binding fixes the execution order.
| Isn't this a rather major penalty for using side-effecting code?
Programming in Implicitly-Parallel-Scheme requires mindfulness of
closure reentry only when that procedure mutates common state. This
is very similar to the mindfulness current Scheme programmers should
have regarding execution order and mutating common state.
| I just wonder how much of a problem this may be in practice.
| Finally, how do I use code which I cannot sequentialize? E.g. if
| we specify `map' to be concurrent, how do I (map random '(1 2 3))?
| Or shall we have a separate `sequential-map' in the standard
| library?
SEQUENTIAL-MAP could be used when counting is done in a call to MAP:
(define cnt 0)
(display
(sequential-map
(lambda (x)
(if (negative? x) (set! cnt (+ 1 cnt)))
(* x x))
'(-1 2 -3 4 -5 6)))
(newline)
(display cnt) (newline)
Alternatively, a mutex could be used to regulate access to CNT.
_______________________________________________
r6rs-discuss mailing list
[email protected]
http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
