Difference between revisions of "Opting for oracles"

From HaskellWiki
Jump to: navigation, search
(Extra section about monadic interface; other sections relocated elsewhere; etc.)
m (Monad-instance code improved)
Line 7: Line 7:
 
== Oracles in use ==
 
== Oracles in use ==
   
The early use of oracles in programming languages focused on coping with the <span class="plainlinks">[https://wiki.haskell.org/Category:Nondeterminism nondeterminism]<span> <!-- [[Category:Nondeterminism|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 computations to each progress at their own rate, depending on the current availability of suitable resources, which can either be:
+
The early use of oracles in programming languages focused on coping with the <span class="plainlinks">[https://wiki.haskell.org/Category:Nondeterminism nondeterminism]<span> <!-- [[Category:Nondeterminism|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
 
* ''inside'' the language e.g. definitions which the computations share, or
Line 42: Line 42:
   
 
<haskell>
 
<haskell>
  +
-- for GHC 8.4.3
  +
{-# LANGUAGE BangPatterns, FlexibleInstances, OverlappingInstances #-}
  +
 
instance Monad ((->) (Tree a)) where
 
instance Monad ((->) (Tree a)) where
return x = \!_ -> x
+
return x = \(!_) -> x
 
m >>= k = \t -> case m (left t) of !x -> k x (right t)
 
m >>= k = \t -> case m (left t) of !x -> k x (right t)
 
</haskell>
 
</haskell>

Revision as of 01:26, 12 July 2021

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 oracles can be repurposed to make use of other types of outside information, based on the classic example of nondeterministic choice: from that, Burton shows how to provide the current time, using the example of timestamps:

 -- 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 also be made available.

Extra parameters and arguments

While they acknowledge Burton's technique does maintain referential transparency, in their paper On the Expressiveness of Purely Functional I/O Systems Paul Hudak and Raman S. Sundaresh also raise one possible annoyance - the need to manually disperse subtrees 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.