On Mon 27 Sep, Bjorn Lisper wrote:
> We are not assuming a sequential machine. The equational semantics of "or"
> above does for instance allow that we speculatively fork off a thread
> evaluating the second argument before we know the value of the first
> argument, if we just delay the return of the answer until the first argument
> is fully evaluated. On the other hand, one must keep some operational
> semantics in mind when specifying a more abstract semantics, so one does not
> end up with a language which is very expensive or impossible to implement on
> the machines at hand.
True, concurrent implementations are possible, but they are still
constrained to behave like sequential implementations, aren't they?.
> Do you think about such semantics as the "parallel or", which has its
> strictness properties defined by:
>
> false or bot = bot or false = bot
> true or bot = bot or true = true
>
> ?
Yes I do think about such things, and yes the above is how I would
expect a boolean or to behave. It seems quite natural if you interpret
_|_ as 'not terminated yet' (which is testable at run time),
rather than 'won't terminate ever' (which isn't).
> Yes, it makes a lot of sense. The parallel or above is a classical example
> of a function for which there exists no semantically correct sequential
> evaluation order of its arguments (i.e., an evaluation order where an
> argument is evaluated in full before the evaluation of the next argument
> starts). Therefore, it has usually been discarded as infeasible to implement
> since the in the worst-case scenario its evaluation may require that you
> spawn off an exponential number of concurrent threads (imagine a function
> calling the parallel or recursively on both sides).
This is the biggest problem I think.
Implementation would be very difficult. It requires a compiler smart
enough to only start separate threads if it's going to make some
difference to the termination properties, and a very efficient
implementation capable of supporting an arbitary number of threads.
I don't see the potential problem with infinite nos. of threads as
a reason not to do this though. Haskell as it stands provides plenty of
opportunity to screw up with infinite things :-)
Just thinking about the implications of this sort of approach makes
my head spin. Should we (but not me) ..
Leave things as they are?
Forget about _|_ in program transformation?
Try to implement something like this?
Regards
--
Adrian Hey
