Touch the future

I recently implemented concurrency constructs for Streme, and I decided to go with future/touch.

(future exp) allows the programmer to say to the evaluator: I will need the value of exp some time in the future. This means the evaluator has more freedom in choosing when to evaluate exp. Some possibilities:

1. Evaluate exp directly: this gives the future construct the semantics of the identity function.
2. Evaluate exp when its value is needed: the future becomes a delay.
3. The evaluation can start between 1 and 2, and in the best-case scenario the value is available when needed.

Of course, 3 is by far the most interesting option because exp can be concurrently evaluated with the rest of the program, including the thread that constructed the future. There is one "small" detail of course that should be mentioned: choosing between 1, 2 and 3 potentially changes the semantics of a program. More on that later.

(future exp) creates a future value that can be resolved by its cousin procedure touch. touch always returns the value of exp, but it is possible it has to wait for it to become available, so it is a blocking operation.

Futures are first class values and can freely be passed around. So when is it necessary to use touch? At least before the value of exp is needed. And who has to perform the touch? Again some options:

1. The programmer manually introduces touch where necessary.
2. The evaluator, when needing a strict value, checks for futures and touches if necessary.
3. The evaluator does value-flow analysis and introduces the necessary touch operations.

And again option 3 is the most attractive. Option 1 requires the programmer to keep track of where futures flow, which can increase the complexity of writing non-trivial programs. Option 2 incurs a performance penalty: if every time the evaluation of, say, (+ a b) actually becomes (let ((a-value (if (future? a) (touch a) a) (b-value (if (future? b) (touch b) b)) (+ a-value b-value)) at runtime, it is easy to see why this is so.

Options 2 and 3 makes the use of futures more transparent for the programmer, since he or she doesn't have to deal with touch explicitly. But wait... let's extend this principle. What if the evaluator can perform an analysis to decide where to introduce futures? That way, not only touch but also future becomes transparent, resulting in automatic parallelization.

The analysis needed for safe introduction of futures is dependency analysis. As said before, introducing futures can change the semantics of a program. The only way to make sure this doesn't happen is to check for interdependence between expressions. In short, if two expressions have no dependencies, evaluating them in parallel cannot change the meaning of a program.

So, to conclude, future and touch available at the source level in Streme only to manually test out concurrency in Streme. Ideally, in the near "future", the programmer should not worry about future/touch at all, since the evaluator will take care of it. Hopefully.