View source for Concurrency with oracles

== The problem ==
While there has been research into ''deterministic'' concurrency (e.g. Eleni Spiliopoulou's work with the Bristol Haskell system as described in his thesis [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.60.4364&rep=rep1&type=pdf Concurrent and Distributed Functional Systems]), models of concurrency are generally ''nondeterministic''. For programming languages like Haskell which have the goal of being [[Referential transparency|referentially transparent]], the nondeterminism associated with concurrency presents a challenge - the usual techniques for supporting it used by most other (imperative) languages cannot not be simply transferred verbatim. But neither can nondeterminism be just ignored:

<blockquote>
Nondeterminism is useful in real-time applications where the behaviour of a program should depend on the order in which external events occur. For example, it might be desirable to merge the elements of two lists in the order in which the elements become available. This type of nondeterminism appears to be necessary if functional programs are to be used for real-time computing.

:<small>[https://academic.oup.com/comjnl/article-pdf/31/3/243/1157325/310243.pdf Nondeterminism with Referential Transparency in Functional Programming Languages], F. Warren Burton.</small>
</blockquote>

Other example include:
* which out of two computations will finish first;
* which input event will arrive first;
* whether a computation will finish before an input event arrives.

For concurrent programs, nondeterminism is inescapable - events like storage, network or other external failures can occur without warning. The languages used for writing such programs must have some way to allow these programs to cope with such degradation gracefully while continuing to carry out the majority of their designated tasks, albeit at reduced capacity.  

== The option of oracles ==
Rather than use [[Pseudo-data|pseudo-data]] directly, or a combination of
deterministic [[oracle|oracles]] with
[[Turing's_various_machines#The_choice_machine|nondeterministic Turing machines]],
the nondeterminism can be attributed to the oracles themselves (with any
relevant prior research on oracles adapted accordingly). Then an oracle
can be consulted wherever the program requires a nondeterministic result.

== Examples of use ==
Stephan Herhut, Sven-Bodo Scholz and Clemens Grelck incorporate an oracle source in the uniquely-typed world state used in [https://www.sac-home.org Single-Assignment C] to help improve the performance of certain operations with side-effects within data-parallel segments of programs. Simon B. Jones and K. V. S. Prasad uses oracles directly for operating and broadcasting systems respectively; Peter Dybjer, Herbert Sander and Mieke Massink use the concept for reasoning about various models of concurrency and their possible applications.

== References ==
* [https://www.researchgate.net/profile/Clemens-Grelck/publication/220997216_Controlling_chaos_on_safe_side-effects_in_data-parallel_operations/links/543bb4670cf2d6698be31618/Controlling-chaos-on-safe-side-effects-in-data-parallel-operations.pdf Controlling Chaos: On Safe Side-Effects in Data-Parallel Operations], Stephan Herhut, Sven-Bodo Scholz and Clemens Grelck.

* [http://www.cse.chalmers.se/~peterd/papers/FACS1989.pdf A Functional Programming Approach to the Specification and Verification of Concurrent Systems], Peter Dybjer and Herbert Sander.

* [https://www.ru.nl/publish/pages/682191/massinkm.pdf Functional Techniques in Concurrency], Mieke Massink.

* [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.6225&rep=rep1&type=pdf A Calculus of Broadcasting Systems], K. V. S. Prasad.

* [https://www.cs.ox.ac.uk/files/3313/PRG42.pdf A range of operating systems written in a purely functional style], Simon B. Jones.


[[Category:Concurrency]]
[[Category:Nondeterminism]]