I imagine here a deterministic language capable of MP.
I think that <a href=http://people.csail.mit.edu/jaffer/r5rs_toc.html>Scheme</a> is deterministic.
There are a few occurances of <i><tt>unspecified</tt></i> in the spec but it seems clear that are already a deterministic function of their arguments and the implementation. 
<p>Scheme is extended by defining a class of identifier which cannot be stored into.
I will call the ‘constants’ here.
Better yet I adopt Reese’s Scheme 48 where there is no procedure <tt>set!</tt>.

A variation of lambda produces a function that closes over constant variables in the scope of its definition.
<hr>
This is becoming tedious and premature.
I presume a new class of function definition that sees only a class of variable in the context of its definition that denotes a manifestly immutable value.
I claim that it is easy to define these.
Non-Scheme like value identifiers are needed as in Scheme 48.
This is a compile time check.

There is a trusted primitive procedure whose behavior is <tt>(lambda (P Q) (cons (P) (Q)))</tt> where P and Q must be such functions.
The real primitive is free to run P and Q on different processors.
There is now no way to learn whether P finished before Q.
The new language is thus deterministic.
<p>This does not subsume all MP patterns and some problems may not find this language suitable for harnessing multiple CPUs and other forms of MP.
<hr>
Recursive definition of ‘constant’ in Scheme<ul>
<li>A numeral is a constant.
<li>If <i>op</i> is one of the standard binary operators and <i>a</i> and  <i>b</i> are constants then  <i>(op a b)</i> is a constant.
<li>If <i>op</i> is one of the standard unary operators and <i>a</i> is a constant then  <i>(op a)</i> is a constant.
<li><i>(stat a)</i> is a constant even if expression <i>a</i> is not.
<br>(equal? a (stat a))
<li>If <i>f</i> is a procedure whose definition captures only constant values, and <i>a<sub>0</sub></i> thru <i>a<sub>n</sub></i> are constants then <i>(f a<sub>0</sub> … a<sub>n</sub>)</i> is a constant.
<li>If <i>a</i> and  <i>b</i> are constants then <i>(do-together a b)</i> is a constant and yields a pair of the the value of a and the value of b.</ul>
Special rules:<ul>
<li>(stat f) fails for a non constant function.
<li>(set! z x) fails if z is constant.
<li>(set-car x y) and (set-cdr x y) fail if x is constant.
<li>All primitive procedures are constant but string-copy and make-vector.

OCaml and Scheme 48 and Algol68 would make this clearer.