Opting for oracles

LML had a fully fledged implementation of oracles running of a multi-processor (a Sequent Symmetry) back in ca 1989. The description in the Fudgets thesis refers to this implementation. It was fairly pleasant to work with and quite practical.

Lennart Augustsson.

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, limits the effect on the semantics 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.

The use of oracles goes beyond programming languages:

• Jennifer Hackett and Graham Hutton use them as the basis for an alternate semantics (rather than the more common stateful effects) in Call-by-Need Is Clairvoyant Call-by-Value.

• A brief mention appears in Conor McBride's representation of general recursion for use with total functional languages in Turing-Completeness Totally Free.

• They have also been used in functional big-step semantics for supporting languages with I/O, in addition to nondeterminism.

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 for regular use. A small implementation by Iavor Diatchki is available in Hackage.

Extra parameters and arguments

While they recognise its preservation of referential transparency, in their paper Programming Reactive Systems in Haskell, Sigbjørn Finne and Simon Peyton Jones also raise one possible annoyance with Burton's approach - 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.