Difference between revisions of "Opting for oracles"

From HaskellWiki
Jump to: navigation, search
m (Word replaced with synonym (too repetitive))
(Extra section about monadic interface; other sections relocated elsewhere; etc.)
 
Line 1: Line 1:
 
== Oracles, defined ==
 
== 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 in the computation. The oracle, by seeming to contain the prediction, preserves the [[Referential transparency|referential transparency]] of the language being used to define the computation.
+
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|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.
 
This makes the use of oracles highly relevant to languages intended to preserve referential transparency, such as Haskell.
Line 7: Line 7:
 
== Oracles in use ==
 
== Oracles in use ==
   
The early use of oracles in programming languages focussed 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 some means for 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 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 19: Line 19:
 
== From oracles to ''pseudodata'' ==
 
== From oracles to ''pseudodata'' ==
   
In his paper [https://academic.oup.com/comjnl/article-pdf/31/3/243/1157325/310243.pdf Nondeterminism with Referential Transparency in Functional Programming Languages], F. Warren Burton illustrates how oracles can be repurposed to make use of other outside information - starting with <tt>decisions</tt> for supporting nondeterministic choice:
+
In his paper [https://academic.oup.com/comjnl/article-pdf/31/3/243/1157325/310243.pdf 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 [[Burton-style nondeterminism|nondeterministic choice]]: from that, Burton shows how to provide the current time, using the example of <tt>timestamps</tt>:
   
 
<haskell>
 
<haskell>
Line 27: Line 27:
 
right :: Tree a }
 
right :: Tree a }
   
-- section 3
 
data Decision -- abstract, builtin
 
choice :: Decision -> a -> a -> a
 
</haskell>
 
 
(the details of which can be found in [[Burton-style nondeterminism]].)
 
 
Burton then shows how the concept of oracles can be expanded to access the current time, using the example of <tt>timestamps</tt>:
 
 
<haskell>
 
 
-- section 7
 
-- section 7
 
data Timestamp -- abstract, possibly builtin
 
data Timestamp -- abstract, possibly builtin
Line 43: Line 33:
 
</haskell>
 
</haskell>
   
all while preserving referential transparency. He also hints as to how the current size of available storage can also be made available - see his paper for more details.
+
He also hints as to how the current size of available storage can also be made available.
   
== A simpler interface ==
 
  +
== Extra parameters and arguments ==
   
Since its advent (sometimes as a result of being inspired by it, or similar entities), an alternate interface has appeared for working with Burton's ''pseudodata'':
 
  +
While they acknowledge Burton's technique does maintain referential transparency, in their paper [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.695&rep=rep1&type=pdf 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.
 
* In Simon Peyton Jones's book [[Books|The implementation of functional programming languages]] (section 9.6 on page 188 of 458), Peter Hancock provides a simple interface for generating new type varibles (of type <tt>tvname</tt>) for a type checker, using the type <tt>name_supply</tt>:
 
   
<tt>
 
  +
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 <code>Prelude</code> for Haskell. Using the [https://downloads.haskell.org/~ghc/7.8.4/docs/html/users_guide/bang-patterns.html bang-patterns] extension:
::|| page 188 of 458
 
::next_name :: name_supply -> tvname
 
::deplete :: name_supply -> name_supply
 
::split :: name_supply -> (name_supply, name_supply)
 
</tt>
 
   
* In his paper [https://www.iro.umontreal.ca/~lecuyer/myftp/papers/cacm88.pdf Efficient and Portable Combined Random Number Generators], Pierre L'Ecuyer suggests the ''disjoint'' splitting of random numbers into independent subsequences as needed. Burton and Rex L. Page follow this up in [https://www.cs.ou.edu/~rlpage/burtonpagerngjfp.pdf Distributed Random Number Generation] - from page 9 of 10:
 
 
<haskell>
 
  +
instance Monad ((->) (Tree a)) where
:<haskell>
 
  +
return x = \!_ -> x
data Random = Seed Int
 
  +
m >>= k = \t -> case m (left t) of !x -> k x (right t)
 
seed :: Int -> Random
 
split :: Random -> (Random, Random)
 
generate :: Random -> [Float]
 
 
</haskell>
 
</haskell>
   
:(An assessment of the applicability of Burton's technique for simplifying the the provision of random numbers is also given).
 
  +
making use of the fact that the partially-applied function type <code>forall a . (->) a</code> is monadic.
 
* Lennart Augustsson, Mikael Rittri and Dan Synek use Burton's technique to reimplement Hancock's <tt>name_supply</tt> in their functional pearl [[Research papers/Functional pearls|On generating unique names]], making it practical for regular use. An implementation can be found in Simon Peyton Jones and Jon Launchbury's [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.3656&rep=rep1&type=pdf State in Haskell] - using using more-contemporary syntax:
 
 
:<haskell>
 
-- page 39
 
newUniqueSupply :: IO UniqueSupply
 
splitUniqueSupply :: UniqueSupply -> (UniqueSupply, UniqueSupply)
 
getUnique :: UniqueSupply -> Unique
 
 
data UniqueSupply = US Unique UniqueSupply UniqueSupply
 
 
-- page 40
 
type Unique = Int
 
 
newUniqueSupply = do uvar <- newIORef 0
 
let incr :: Int -> (Int, Unique)
 
incr u = (u+1, u)
 
 
next :: IO Unique
 
next = unsafeInterleaveIO $
 
atomicModifyIORef uvar incr
 
 
supply :: IO UniqueSupply
 
supply = unsafeInterleaveIO $
 
liftM3 US next supply supply
 
 
supply
 
 
splitUniqueSupply (US _ s1 s2) = (s1, s2)
 
getUnique (US u _ _) = u
 
</haskell>
 
 
:The crucial point here is that <code>US</code> - the single data constructor for <code>UniqueSupply</code> - can now be kept private. The use of trees has been reduced to an implementation detail, oblivious to the users of <code>UniqueSupply</code> (and <code>Unique</code>) values.
 
 
== A simpler implementation ==
 
 
Augustsson, Rittri and Synek provide other possible implementations of Hancock's supply in their paper - of particular interest is the ''monousal'' one: to preserve referential transparency, each <code>UniqueSupply</code> should only be used ''once'' (if at all). This makes their concept implementation quite compact, if a little peculiar - reusing parts of Launchbury and Peyton-Jones's example:
 
 
<tt>
 
:abstype uniquesupply
 
:with
 
::new_uniquesupply :: uniquesupply
 
::split_uniquesupply :: uniquesupply -> (uniquesupply, uniquesupply)
 
::get_unique :: uniquesupply -> unique
 
 
:uniquesupply ::= US
 
 
:new_uniquesupply = US
 
:split_uniquesupply US = (US, US)
 
:get_unique s = gensym(s)
 
 
:unique == int
 
 
:|| Not a regular definition!
 
:gensym :: * -> unique
 
</tt>
 
 
It should be obvious that an actual implementation in ''regular'' Haskell isn't possible - non-standard, possibly implementation-specific extensions are required. To provide an implementation here would be more distracting than useful.
 
 
== A matter of nomenclature ==
 
 
As mentioned earlier, L'Ecuyer suggests the splitting of random numbers be ''disjoint''. However, as this can complicate matters, many RNGs (including Burton and Page's) opt for simpler forms of splitting where the duplication of random numbers is statistically unlikely. It only requires a little imagination to realise the consequences of using a similarly-relaxed approach for supplying fresh identifiers!
 
 
To avoid having to repeatedly specify it, an alternate terminology is needed - one which clearly indicates that for some types of pseudodata, the ''disjointedness'' of its splitting is '''mandatory''', instead of just being very convenient.
 
   
 
[[Category:Code]]
 
[[Category:Code]]

Latest revision as of 11:57, 27 March 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 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:

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.