Difference between revisions of "Output/Input"

From HaskellWiki
Jump to navigation Jump to search
(Article rewritten)
m
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
[[Category:Theoretical foundations]]
 
 
 
<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
 
<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
  +
A purely functional program implements a <i>function</i>; it has no side effect. [...] if the side effect can’t be in the functional program, it will have to be outside it.
There is a world of difference between the value <code>echoML</code> which has no side effects when evaluated, and the computation <code>echoML ()</code>, which does.
 
   
<tt>[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.3579&rep=rep1&type=pdf How to Declare an Imperative], Philip Wadler (page 25 of 33).</tt>
+
<small>[https://web.archive.org/web/20210415200634/https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.13.9123&rep=rep1&type=pdf Tackling the Awkward Squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell], Simon Peyton Jones (pages 3-4 of 60). </small>
 
</div>
 
</div>
   
  +
One technique has been used for similar tasks:
Of course, that assumes everything in the program's <i>“world”</i> required by <code>echoML</code> actually <b>works as intended</b>: reality isn't always so obliging! To then define Haskell's I/O type as:
 
   
<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
+
<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
  +
This is discussed by Burton[https://academic.oup.com/comjnl/article-pdf/31/3/243/1157325/310243.pdf <span></span>], and is built on by Harrison[https://core.ac.uk/download/9835633.pdf <span></span>]. The effect of this proposal is to place the non-determinism <i>entirely</i> outside the software [...]
<haskell>
 
type IO a = World -> (a, World)
 
</haskell>
 
 
[where an] <code>IO</code> computation is a function that (logically) takes the state of the world, and returns a modified world as well as the return value.
 
   
  +
<small>[https://academic.oup.com/comjnl/article-pdf/32/2/162/1445725/320162.pdf Functional Programming and Operating Systems], Simon B. Jones and A. F. Sinclair (page 10 of 13).</small>
<tt>[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.168.4008&rep=rep1&type=pdf A History of Haskell: Being Lazy With Class], Paul Hudak, John Hughes, Simon Peyton Jones and Philip Wadler.</tt>
 
 
</div>
 
</div>
   
  +
It can also be used to provide access to external resources:
...seems rather optimistic.
 
<sup> </sup>
 
 
----
 
=== <u>The determining of <code>IO</code></u> ===
 
 
Since reality isn't always so deterministic in behaviour, perhaps the study of <i>nondeterminism</i> can provide a more plausible implementation:
 
   
 
<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
 
<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
 
The approach generalizes so that a program can make use of other run-time information such as the current time or current amount of available storage.
We propose to solve this problem [existing constructs for nondeterminism not being compatible with the mathematical foundations of functional programming] by placing the nondeterminism in pseudo-data. A program is passed an infinite tree of two-valued <code>decisions</code>, along with its input. These <code>decisions</code> may be fixed at runtime, thereby permitting nondeterminism. Once fixed, a <code>decision</code> remains unchanged so equivalent expression must always have the same value.
 
   
<tt>[https://academic.oup.com/comjnl/article-pdf/31/3/243/1157325/310243.pdf Nondeterminism with Referential Transparency in Functional Programming Languages], F. Warren Burton (front page).</tt>
+
<small>[https://academic.oup.com/comjnl/article-pdf/31/3/243/1157325/310243.pdf Nondeterminism with Referential Transparency in Functional Programming Languages], F. Warren Burton (front page).</small>
 
</div>
 
</div>
   
  +
Perhaps it can be used for I/O...
There's more:
 
  +
<br>
  +
  +
__TOC__
  +
<sup> <sup>
  +
 
----
  +
=== <u>Details, details</u> ===
  +
  +
How does it work?
   
 
<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
 
<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
  +
[...] supply each program with an extra argument consisting of an infinite (lazy) binary tree of values. (We choose a tree [...] since any number of subtrees may be extracted from an infinite tree). In practice, these values will be determined at run time (when used as arguments to a special function [...]), but once fixed will never change.
The approach generalizes so that a program can make use of other run-time information such as the current time or current amount of available storage.
 
 
</div>
 
</div>
   
  +
...<i>“a special function”</i>: only one? More will definitely be needed! To keep matters [https://www.interaction-design.org/literature/article/kiss-keep-it-simple-stupid-a-design-principle simple], each value shall only be used <b>once</b> (if at all) as an argument to any such function.
Using this <i>pseudo-data</i> approach:
 
   
 
<haskell>
 
<haskell>
 
main' :: Tree Exterior -> ...
-- abstract; single-use I/O-access mediator
 
data Exterior
 
getchar :: Exterior -> Char
 
putchar :: Char -> Exterior -> ()
 
   
-- from section 2 of Burton's paper
+
-- section 2
 
data Tree a = Node { contents :: a,
 
data Tree a = Node { contents :: a,
 
left :: Tree a,
 
left :: Tree a,
 
right :: Tree a }
 
right :: Tree a }
   
  +
data Exterior -- the abstract value type
-- utility definitions
 
  +
getchar :: Exterior -> Char -- the special functions
type OI = Tree Exterior
 
 
putchar :: Char -> Exterior -> () -- (add more as needed :-)
 
</haskell>
   
  +
Avoiding gratuitous repetition:
main' :: OI -> ()
 
  +
main' = ...
 
 
<haskell>
 
type OI = Tree Exterior
   
 
getChar' :: OI -> Char
 
getChar' :: OI -> Char
Line 63: Line 61:
 
putChar' :: Char -> OI -> ()
 
putChar' :: Char -> OI -> ()
 
putChar' c = putchar c . contents
 
putChar' c = putchar c . contents
  +
</haskell>
 
<sup> </sup>
   
  +
==== An alternative abstraction ====
part :: OI -> (OI, OI)
 
parts :: OI -> [OI]
 
   
  +
About those trees: are they really necessary? If <code>OI</code> was an abstract data type, the use of trees could at least be confined to the implementation:
part t = (left t, right t)
 
  +
parts t = let !(t1, t2) = part t in
 
  +
<haskell>
t1 : parts t2
 
  +
data OI
  +
getChar' :: OI -> Char
  +
putChar' :: Char -> OI -> ()
  +
</haskell>
  +
  +
...provided that single-use property applies directly to <code>OI</code> values (thereby deeming <i>“special”</i> any function which uses an <code>OI</code> argument). That includes the initial <code>OI</code> value supplied to each program:
  +
  +
<haskell>
 
main' :: OI -> ...
  +
</haskell>
  +
  +
But most Haskell programs will need more:
  +
  +
<haskell>
 
part :: OI -> (OI, OI)
 
part t = (left t, right t)
  +
</haskell>
  +
  +
...than two <code>OI</code> values:
  +
  +
<haskell>
 
parts :: OI -> [OI]
 
parts t = let (t1, t2) = part t in t1 : parts t2
 
</haskell>
 
</haskell>
   
  +
So <code>OI</code> can be a tree-free abstract data type after all:
To avoid the visible use of trees, the single-use property can instead be applied directly to <code>OI</code> values. This permits an abstract definition of the <code>OI</code> type:
 
   
 
<haskell>
 
<haskell>
Line 80: Line 102:
 
putChar :: Char -> OI -> ()
 
putChar :: Char -> OI -> ()
 
</haskell>
 
</haskell>
 
The choice to use (theoretically) infinite structured values (binary trees or otherwise) is then an implementation matter.
 
 
<sup> </sup>
 
<sup> </sup>
   
Line 87: Line 107:
 
=== <u>Other interfaces</u> ===
 
=== <u>Other interfaces</u> ===
   
In addition to the [[Monad|current]] one:
+
* [[Monad|monad]]
   
<haskell>
+
:<haskell>
 
type M a = OI -> a
 
type M a = OI -> a
   
Line 107: Line 127:
 
putcharM = putChar
 
putcharM = putChar
 
</haskell>
 
</haskell>
 
the <code>OI</code> interface can be used to implement other models of I/O:
 
   
 
* [[Comonad|comonad]]:
 
* [[Comonad|comonad]]:
Line 165: Line 183:
 
</haskell>
 
</haskell>
   
including [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.3579&rep=rep1&type=pdf those used in earlier versions] of Haskell:
+
The <code>OI</code> interface can also be used to implement [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.3579&rep=rep1&type=pdf I/O models used in earlier versions] of Haskell:
   
 
* dialogues:
 
* dialogues:
Line 189: Line 207:
 
type Answer = OI -> ()
 
type Answer = OI -> ()
   
runK :: Answer -> IO -> ()
+
runK :: Answer -> OI -> ()
 
runK a u = a u
 
runK a u = a u
   
Line 207: Line 225:
 
</haskell>
 
</haskell>
   
and even <i>that</i> <s><i>world</i></s> state-passing style, which is also used by [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.935&rep=rep1&type=pdf Clean], [https://staff.science.uva.nl/c.u.grelck/publications/HerhSchoGrelDAMP09.pdf Single-Assignment C] and as part of the I/O model used for the verification of interactive programs in [https://cakeml.org/vstte18.pdf CakeML], remembering that <code>OI</code> values can only be used once:
+
...and even <i>that</i> <s><i>world</i></s> state-passing style used in GHC, which is also used by [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.935&rep=rep1&type=pdf Clean], [https://staff.science.uva.nl/c.u.grelck/publications/HerhSchoGrelDAMP09.pdf Single-Assignment C] and as part of the I/O model used for the verification of interactive programs in [https://cakeml.org/vstte18.pdf CakeML], remembering that <code>OI</code> values can only be used once:
   
 
<haskell>
 
<haskell>
Line 219: Line 237:
 
putcharL :: Char -> World -> World
 
putcharL :: Char -> World -> World
 
putcharL c (W u) = let !(u1, u2) = partOI u in
 
putcharL c (W u) = let !(u1, u2) = partOI u in
let !_ = putChar u1 in
+
let !_ = putChar c u1 in
 
W u2
 
W u2
 
</haskell>
 
</haskell>
Line 230: Line 248:
 
* [[Disposing of dismissives]]
 
* [[Disposing of dismissives]]
 
* [[IO then abstraction]]
 
* [[IO then abstraction]]
  +
 
[[Category:Theoretical foundations]]

Revision as of 12:36, 1 January 2024

A purely functional program implements a function; it has no side effect. [...] if the side effect can’t be in the functional program, it will have to be outside it.

Tackling the Awkward Squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell, Simon Peyton Jones (pages 3-4 of 60).

One technique has been used for similar tasks:

This is discussed by Burton, and is built on by Harrison. The effect of this proposal is to place the non-determinism entirely outside the software [...]

Functional Programming and Operating Systems, Simon B. Jones and A. F. Sinclair (page 10 of 13).

It can also be used to provide access to external resources:

The approach generalizes so that a program can make use of other run-time information such as the current time or current amount of available storage.

Nondeterminism with Referential Transparency in Functional Programming Languages, F. Warren Burton (front page).

Perhaps it can be used for I/O...


Details, details

How does it work?

[...] supply each program with an extra argument consisting of an infinite (lazy) binary tree of values. (We choose a tree [...] since any number of subtrees may be extracted from an infinite tree). In practice, these values will be determined at run time (when used as arguments to a special function [...]), but once fixed will never change.

...“a special function”: only one? More will definitely be needed! To keep matters simple, each value shall only be used once (if at all) as an argument to any such function.

main' :: Tree Exterior -> ...

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

data Exterior                      -- the abstract value type
getchar :: Exterior -> Char        -- the special functions
putchar :: Char -> Exterior -> ()  -- (add more as needed :-)

Avoiding gratuitous repetition:

type OI  =  Tree Exterior

getChar' :: OI -> Char
getChar' =  getchar . contents

putChar' :: Char -> OI -> ()
putChar' c = putchar c . contents

An alternative abstraction

About those trees: are they really necessary? If OI was an abstract data type, the use of trees could at least be confined to the implementation:

data OI
getChar' :: OI -> Char
putChar' :: Char -> OI -> ()

...provided that single-use property applies directly to OI values (thereby deeming “special” any function which uses an OI argument). That includes the initial OI value supplied to each program:

main' :: OI -> ...

But most Haskell programs will need more:

part    :: OI -> (OI, OI)
part t  =  (left t, right t)

...than two OI values:

parts   :: OI -> [OI]
parts t =  let (t1, t2) = part t in t1 : parts t2

So OI can be a tree-free abstract data type after all:

data OI
partOI  :: OI -> (OI, OI)
getChar :: OI -> Char
putChar :: Char -> OI -> ()


Other interfaces

type M a   =  OI -> a

unit       :: a -> M a
unit x     =  \ u -> let !_ = partOI u in x 

bind       :: M a -> (a -> M b) -> M b
bind m k   =  \ u -> let !(u1, u2) = partOI u in
                     let !x = m u1 in
                     let !y = k x u2 in
                     y

getcharM   :: M Char
getcharM   =  getChar

putcharM   :: Char -> M () 
putcharM   =  putChar
type C a         =  (OI, a)

extract          :: C a -> a
extract (u, x)   =  let !_ = partOI u in x

duplicate        :: C a -> C (C a)
duplicate (u, x) =  let !(u1, u2) = partOI u in
                    (u2, (u1, x))

extend           :: (C a -> b) -> C a -> C b
extend h (u, x)  =  let !(u1, u2) = partOI u in
                    let !y        = h (u1, x) in
                    (u2, y)

getcharC         :: C () -> Char
getcharC (u, ()) =  getChar u

putcharC         :: C Char -> ()
putcharC (u, c)  =  putChar c u
type A b c   =  (OI -> b) -> (OI -> c)

arr          :: (b -> c) -> A b c
arr f        =  \ c' u -> let !x = c' u in f x

both         :: A b c -> A b' c' -> A (b, b') (c, c')
f' `both` g' =  \ c' u -> let !(u1:u2:u3:_) = partsOI u in
                          let !(x, x')      = c' u1 in
                          let !y            = f' (unit x) u2 in
                          let !y'           = g' (unit x') u3 in
                          (y, y')
                where
                  unit x u = let !_ = partOI u in x

getcharA     :: A () Char
getcharA     =  \ c' u -> let !(u1, u2) = partOI u in
                          let !_        = c' u1 in
                          let !ch       = getChar u2 in
                          ch     

putcharA     :: A Char ()
putcharA     =  \ c' u -> let !(u1, u2) = partOI u in
                          let !ch       = c' u1 in
                          let !z        = putChar ch u2 in
                          z

The OI interface can also be used to implement I/O models used in earlier versions of Haskell:

  • dialogues:
runD :: ([Response] -> [Request]) -> OI -> ()
runD d u = foldr (\ (!_) -> id) () $ yet $ \ l -> zipWith respond (d l) (partsOI u)

yet :: (a -> a) -> a
yet f = f (yet f)

respond :: Request -> OI -> Response
respond Getq     u = let !c = getChar u in Getp c
respond (Putq c) u = let !_ = putChar c u in Putp

data Request  = Getq | Putq Char
data Response = Getp Char | Putp
  • continuations:
type Answer = OI -> ()

runK :: Answer -> OI -> ()
runK a u = a u

doneK :: Answer
doneK = \ u -> let !_ = partOI u in ()

getcharK :: (Char -> Answer) -> Answer
getcharK k   = \ u -> let !(u1, u2) = partOI u in
                      let !c        = getChar u1 in
                      let !a        = k c in
                      a u2

putcharK :: Char -> Answer -> Answer
putcharK c a = \ u -> let !(u1, u2) = partOI u in
                      let !_        = putChar c u1 in
                      a u2

...and even that world state-passing style used in GHC, which is also used by Clean, Single-Assignment C and as part of the I/O model used for the verification of interactive programs in CakeML, remembering that OI values can only be used once:

newtype World = W OI

getcharL :: World -> (Char, World)
getcharL (W u) = let !(u1, u2) = partOI u in
                 let !c = getChar u1 in
                 (c, W u2)

putcharL :: Char -> World -> World
putcharL c (W u) = let !(u1, u2) = partOI u in
                   let !_ = putChar c u1 in
                   W u2


See also