I imagine here a deterministic language capable of MP.
I think that Scheme is deterministic.
There are a few occurances of unspecified in the spec but it seems clear that are already a deterministic function of their arguments and the implementation.
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 set!.
A variation of lambda produces a function that closes over constant variables in the scope of its definition.
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 (lambda (P Q) (cons (P) (Q))) 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.
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.
Recursive definition of ‘constant’ in Scheme
- A numeral is a constant.
- If op is one of the standard binary operators and a and b are constants then (op a b) is a constant.
- If op is one of the standard unary operators and a is a constant then (op a) is a constant.
- (stat a) is a constant even if expression a is not.
(equal? a (stat a))
- If f is a procedure whose definition captures only constant values, and a0 thru an are constants then (f a0 … an) is a constant.
- If a and b are constants then (do-together a b) is a constant and yields a pair of the the value of a and the value of b.
- (stat f) fails for a non constant function.
- (set! z x) fails if z is constant.
- (set-car x y) and (set-cdr x y) fail if x is constant.
- All primitive procedures are constant but string-copy and make-vector.
OCaml and Scheme 48 and Algol68 would make this clearer.