Difference between revisions of "Concurrency with oracles"
(Transferred archived content in 'ConcurrencyWithOracles, from 2001/05/17, to here) |
(Original remarks transferred out) |
||
| Line 1: | Line 1: | ||
| − | <tt><i>Someone can add a reference here; I'm too lazy right now to do so.</i></tt> |
||
| − | |||
An ''oracle'' is a value that "knows", by magic predictive power, which of two computations will finish first or which input event will arrive first, or whether a computation will finish before an input event arrives. In practice the predictive power is unnecessary, but the oracle, by seeming to contain the prediction, will preserve the [[Referential transparency|referential transparency]] of a language while allowing expression of computations whose outcomes depend on execution time and arrival time. |
An ''oracle'' is a value that "knows", by magic predictive power, which of two computations will finish first or which input event will arrive first, or whether a computation will finish before an input event arrives. In practice the predictive power is unnecessary, but the oracle, by seeming to contain the prediction, will preserve the [[Referential transparency|referential transparency]] of a language while allowing expression of computations whose outcomes depend on execution time and arrival time. |
||
Solutions tend to involve infinite trees of oracles, so you can pull one out whenever you need one, and pass an infinite subtree to future computations. Of course once an oracle has been used, it can't be reused. [[Referential transparency]] demands that the outcome of applying the oracle is fixed. |
Solutions tend to involve infinite trees of oracles, so you can pull one out whenever you need one, and pass an infinite subtree to future computations. Of course once an oracle has been used, it can't be reused. [[Referential transparency]] demands that the outcome of applying the oracle is fixed. |
||
| − | |||
| − | <tt><i> |
||
| − | I think we could equivalently assume a given oracle not only stores the prediction about the computations and events it's going to be applied to, but also a couple of additional oracles. Thus the same kind of thing can function for the origial idea of an oracle and as the infinite binary tree of oracles that seems to come in handy. |
||
| − | </i></tt> |
||
[[Category:Concurrency]] |
[[Category:Concurrency]] |
||
Revision as of 04:45, 18 March 2021
An oracle is a value that "knows", by magic predictive power, which of two computations will finish first or which input event will arrive first, or whether a computation will finish before an input event arrives. In practice the predictive power is unnecessary, but the oracle, by seeming to contain the prediction, will preserve the referential transparency of a language while allowing expression of computations whose outcomes depend on execution time and arrival time.
Solutions tend to involve infinite trees of oracles, so you can pull one out whenever you need one, and pass an infinite subtree to future computations. Of course once an oracle has been used, it can't be reused. Referential transparency demands that the outcome of applying the oracle is fixed.