Opting for oracles

Oracles, defined

An oracle is a value that can be viewed as having the ability to predict what another value will be. The predicted value is usually the result of a computation involving information which cannot be represented as regular values by the language defining the computation. The oracle, by seeming to contain the prediction, preserves the referential transparency of the language being used.

This makes the use of oracles highly relevant to languages intended to preserve referential transparency, such as Haskell.

Oracles in use

The early use of oracles in programming languages focused on coping with the nondeterminism arising from the occurrence of events outside the language - one classic example being concurrency. For a language to support it, it must provide computations some means of allowing multiple sub-computations to each progress at their own rate, depending on the current availability of suitable resources, which can either be:

• inside the language e.g. definitions which the computations share, or

• outside of it e.g. hardware devices for storage, audiovisual or networking.

Clearly the language cannot predict e.g. when users of a computer system will be active, so concurrency is generally nondeterministic. For information on how oracles have helped to support various forms of concurrency, see Concurrency with oracles.

(Of course, the use of oracles goes beyond programming languages e.g. Jennifer Hackett and Graham Hutton use them to alleviate some of the tedium associated with the classic state-centric semantics used to examine the operational behaviour of lazy programs - see Call-by-Need Is Clairvoyant Call-by-Value.)

From oracles to pseudodata

In his paper Nondeterminism with Referential Transparency in Functional Programming Languages, F. Warren Burton illustrates how oracle streams can be repurposed to convey other types of outside information, based on the classic example of nondeterministic choice: - from that, Burton shows how this pseudodata can provide timestamps based on the current time:

 -- section 2
data Tree a = Node { contents :: a,
                     left     :: Tree a,
                     right    :: Tree a }

 -- section 7
data Timestamp  -- abstract, possibly builtin
stamp :: !Timestamp -> Timestamp
compare :: Timestamp -> Timestamp -> Integer -> Bool

He also hints as to how the current size of available storage can be made available.

Practical examples of pseudodata include:

• clocks - in his thesis Functional Real-Time Programming: The Language Ruth And Its Semantics, Dave Harrison uses pseudodata to provide processes in a program with the current time.

• supplies - In their functional pearl On generating unique names, Lennart Augustsson, Mikael Rittri and Dan Synek show how pseudodata can make Peter Hancock's name_supply viable:

Counter passing is the traditional method of generating unique names in a purely functional language, but it is awkward to use and imposes unnecessary data dependencies which can destroy opportunities for lazy or parallel evaluation. A method of Hancock does not have this drawback, but instead wastes large portions of the name space, so that the generated names cannot be trusted to fit inside a machine word. We implement Hancock's operations in the lazy language Haskell without wasting names, using hidden state changes à la Burton's decisions. Measurements show that this can be faster than counter passing even when no laziness or parallelism is gained.

...with more recent implementations appearing on pages 39-40 of 51 in State in Haskell by John Launchbury and Simon Peyton Jones, and in Simon Marlow's thesis Deforestation for Higher-Order Functional Programs on pages 142-143 of 182.

Extra parameters and arguments

While they acknowledge Burton's technique does maintain referential transparency, in their paper Programming Reactive Systems in Haskell, Sigbjørn Finne and Simon Peyton Jones also raise one possible annoyance - the need to manually disperse pseudodata as additional arguments or parameters within programs.

As it happened, the first hints of a solution was already present when Burton's paper was first published, and now forms part of the standard Prelude for Haskell. Using the bang-patterns extension:

 -- for GHC 8.4.3
{-# LANGUAGE BangPatterns, FlexibleInstances, OverlappingInstances #-}

instance Monad ((->) (Tree a)) where
    return x = \(!_) -> x
    m >>= k  = \t -> case m (left t) of !x -> k x (right t)

making use of the fact that the partially-applied function type forall a . (->) a is monadic.