Difference between revisions of "Output/Input"
(Minor changes) |
m |
||
(93 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
+ | <div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote"> |
||
− | Let me guess...you've read every other guide, tutorial, lesson and introduction and none of them have helped - you still don't understand I/O in Haskell. |
||
+ | 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. |
||
+ | <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> |
||
− | Alright then - have a look at this: |
||
+ | </div> |
||
+ | One technique has been used for similar tasks: |
||
− | <haskell> |
||
− | data OI -- abstract, primitive |
||
+ | <div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote"> |
||
− | partOI :: OI -> (OI, OI) -- |
||
+ | 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 [...] |
||
− | getchar :: OI -> Char -- primitives |
||
− | putchar :: Char -> OI -> () -- |
||
+ | <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> |
||
− | seq :: a -> b -> b -- also primitive |
||
+ | </div> |
||
+ | It can also be used to provide access to external resources: |
||
− | instance Partible OI where ... |
||
+ | <div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote"> |
||
− | class Partible a where |
||
+ | 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. |
||
− | part :: a -> (a, a) |
||
− | parts :: a -> [a] |
||
− | . |
||
− | . |
||
− | . |
||
− | </haskell> |
||
− | |||
− | No up-front explanation; I'm guessing you've seen more than enough of those, so I'm trying something different. I will explain it later... |
||
+ | <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> |
||
− | Yes, of course there's more to Haskell I/O than <code>getchar</code> and <code>putchar</code>; I've downsized it for convenience. If you want, you can add the rest afterwards... |
||
+ | </div> |
||
+ | Perhaps it can be used for I/O... |
||
− | Yes, they're somewhat arcane, but they can be used to emulate all the classic approaches to I/O in Haskell, albeit in miniature: |
||
+ | <br> |
||
+ | __TOC__ |
||
− | <haskell> |
||
+ | <sup> <sup> |
||
− | -- for GHC 8.6.5 |
||
− | {-# LANGUAGE BangPatterns #-} |
||
− | module ClassicIO where |
||
− | import Prelude(Char, String) |
||
− | import Prelude(($), (.)) |
||
− | import Data.List(map, foldr, zipWith) |
||
− | import OutputInput |
||
− | import Partible |
||
− | + | ---- |
|
+ | === <u>Details, details</u> === |
||
+ | How does it work? |
||
− | {- main :: (String -> String) -} |
||
+ | <div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote"> |
||
− | runMain_text :: (String -> String) -> OI -> () |
||
+ | [...] 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. |
||
− | runMain_text main = \u -> let !(u1, u2) = part u in |
||
+ | </div> |
||
− | putchars (main (getchars u1)) u2 |
||
+ | ...<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. |
||
− | getchars :: OI -> String |
||
− | getchars = map getchar . parts |
||
+ | <haskell> |
||
− | putchars :: String -> OI -> () |
||
+ | main' :: Tree Exterior -> ... |
||
− | putchars s = foldr seq () . zipWith putchar s . parts |
||
+ | -- section 2 |
||
+ | data Tree a = Node { contents :: a, |
||
+ | left :: Tree a, |
||
+ | right :: Tree a } |
||
+ | data Exterior -- the abstract value type |
||
− | -- dialogues -- |
||
+ | getchar :: Exterior -> Char -- the special functions |
||
− | |||
+ | putchar :: Char -> Exterior -> () -- (add more as needed :-) |
||
− | {- main :: Dialogue -} |
||
− | |||
− | runMain_dial :: Dialogue -> OI -> () |
||
− | runMain_dial main = \u -> foldr seq () $ yet $ |
||
− | \l -> zipWith respond (main l) (parts u) |
||
− | |||
− | type Dialogue = [Response] -> [Request] |
||
− | |||
− | data Request = Getq | Putq Char |
||
− | data Response = Getp Char | Putp |
||
− | |||
− | yet :: (a -> a) -> a |
||
− | yet f = f (yet f) |
||
− | |||
− | respond :: Request -> OI -> Response |
||
− | respond Getq = \u -> case getchar u of c -> Getp c |
||
− | respond (Putq c) = \u -> seq (putchar c u) Putp |
||
− | |||
− | |||
− | -- continuations -- |
||
− | |||
− | {- main :: (() -> IOResult) -> IOResult -} |
||
− | |||
− | runMain_cont :: ((() -> IOResult) -> IOResult) -> OI -> () |
||
− | runMain_cont main = call (main done) |
||
− | |||
− | newtype IOResult = R (OI -> ()) |
||
− | |||
− | call :: IOResult -> OI -> () |
||
− | call (R a) = a |
||
− | |||
− | done :: () -> IOResult |
||
− | done () = R $ \ u -> part u `seq` () |
||
− | |||
− | getchar_cont :: (Char -> IOResult) -> IOResult |
||
− | getchar_cont k = R $ \u -> let !(u1, u2) = part u in |
||
− | let !c = getchar u1 in |
||
− | call (k c) u2 |
||
− | |||
− | putchar_cont :: Char -> (() -> IOResult) -> IOResult |
||
− | putchar_cont c k = R $ \u -> let !(u1, u2) = part u in |
||
− | seq (putchar c u) (call (k ()) u2) |
||
− | |||
− | |||
− | -- state-passing -- |
||
− | |||
− | {- main :: IOState -> ((), IOState) -} |
||
− | |||
− | runMain_stat :: (IOState -> ((), IOState)) -> OI -> () |
||
− | runMain_stat main = \u -> seq (main (ini_st u)) () |
||
− | |||
− | newtype IOState = S OI |
||
− | |||
− | ini_st :: OI -> IOState |
||
− | ini_st = S |
||
− | |||
− | getchar_stat :: IOState -> (Char, IOState) |
||
− | getchar_stat (S u) = let !(u1, u2) = part u in |
||
− | let !c = getchar u1 in |
||
− | (c, S u2) |
||
− | |||
− | putchar_stat :: Char -> IOState -> ((), IOState) |
||
− | putchar_stat c (S u) = let !(u1, u2) = part u in |
||
− | seq (putchar c u1) ((), S u2) |
||
− | |||
− | |||
− | -- and those weird, fickle things ;-) |
||
− | |||
− | {- main :: IO () -} |
||
− | |||
− | runMain_wfth :: IO () -> OI -> () |
||
− | runMain_wfth main = main |
||
− | |||
− | type IO a = OI -> a |
||
− | |||
− | getchar_wfth :: IO Char |
||
− | getchar_wfth = getchar |
||
− | |||
− | putchar_wfth :: Char -> IO () |
||
− | putchar_wfth = putchar |
||
− | |||
− | unit :: a -> IO a |
||
− | unit x = \u -> part u `seq` x |
||
− | |||
− | bind :: IO a -> (a -> IO b) -> IO b |
||
− | bind m k = \u -> case part u of |
||
− | (u1, u2) -> (\x -> x `seq` k x u2) (m u1) |
||
</haskell> |
</haskell> |
||
+ | Avoiding gratuitous repetition: |
||
− | Here are examples for each of those approaches: |
||
<haskell> |
<haskell> |
||
+ | type OI = Tree Exterior |
||
− | module Echoes where |
||
− | import Prelude(String, Char(..), Eq(..)) |
||
− | import Prelude(($)) |
||
− | import ClassicIO |
||
− | import OutputInput(runOI) |
||
− | |||
− | echo_text :: String -> String |
||
− | echo_text (c:cs) = if c == '\n' then [] else c : echo_text cs |
||
− | |||
− | echo_dial :: Dialogue |
||
− | echo_dial p = Getq : |
||
− | case p of |
||
− | Getp c : p' -> |
||
− | if c == '\n' then |
||
− | [] |
||
− | else |
||
− | Putq c : |
||
− | case p' of |
||
− | Putp : p'' -> echo_dial p'' |
||
+ | getChar' :: OI -> Char |
||
− | echo_cont :: (() -> IOResult) -> IOResult |
||
+ | getChar' = getchar . contents |
||
− | echo_cont k = getchar_cont $ \c -> |
||
− | if c == '\n' then |
||
− | k () |
||
− | else |
||
− | putchar_cont c (\_ -> echo_cont k) |
||
+ | putChar' :: Char -> OI -> () |
||
− | echo_wfth :: IO () |
||
+ | putChar' c = putchar c . contents |
||
− | echo_wfth = getchar_wfth `bind` \c -> |
||
− | if c == '\n' then |
||
− | unit () |
||
− | else |
||
− | putchar_wfth c `bind` \_ -> echo_wfth |
||
</haskell> |
</haskell> |
||
+ | <sup> </sup> |
||
+ | ==== An alternative abstraction ==== |
||
− | What was that - using <code>Prelude.seq</code> that way won't work in Haskell 2010? ''You are correct!'' |
||
+ | 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: |
||
− | This should work as expected[1][2]: |
||
<haskell> |
<haskell> |
||
+ | data OI |
||
− | -- for GHC 8.6.5 |
||
+ | getChar' :: OI -> Char |
||
− | {-# LANGUAGE MagicHash, UnboxedTuples #-} |
||
+ | putChar' :: Char -> OI -> () |
||
− | module Sequential(seq) where |
||
− | import GHC.Base(seq#, realWorld#) |
||
− | |||
− | infixr 0 `seq` |
||
− | seq :: a -> b -> b |
||
− | x `seq` y = case seq# x realWorld# of |
||
− | (# s, _ #) -> case seq# y s of |
||
− | (# _, t #) -> t |
||
</haskell> |
</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: |
||
− | It didn't work? Try this instead: |
||
<haskell> |
<haskell> |
||
− | + | main' :: OI -> ... |
|
− | {-# LANGUAGE CPP #-} |
||
− | #define during seq |
||
− | module Sequential(seq) where |
||
− | import qualified Prelude(during) |
||
− | import GHC.Base(lazy) |
||
− | |||
− | infixr 0 `seq` |
||
− | seq :: a -> b -> b |
||
− | seq x y = Prelude.during x (lazy y) |
||
</haskell> |
</haskell> |
||
+ | But most Haskell programs will need more: |
||
− | As for those extensions - they stay with each definition. |
||
− | |||
− | That still didn't work? Well, give this a try: |
||
<haskell> |
<haskell> |
||
− | + | part :: OI -> (OI, OI) |
|
+ | part t = (left t, right t) |
||
− | yet f = y where y = f y |
||
</haskell> |
</haskell> |
||
+ | ...than two <code>OI</code> values: |
||
− | Now that we're firmly on the topic of implementation details, did you notice how easy it was to define that allegedly ''warm, fuzzy''[3] <code>IO</code> type using this curious new <code>OI</code> type, and those primitives? |
||
− | |||
− | Sometimes that can be a hint that doing the opposite will be difficult or even impossible to do while staying within standard Haskell 2010. As it happens, this is one of those cases... |
||
− | |||
− | To define <code>OI</code>, <code>partOI</code>, <code>getchar</code> and <code>putchar</code> will require: |
||
− | |||
− | * modifying your preferred Haskell implementation - lots of work; |
||
− | |||
− | * using some other language for the definitions, with Haskell then calling the foreign code - extra work to deal with two different languages; |
||
− | |||
− | * using unsafe or implementation-specific primitives - work needed to avoid conflicts with Haskell semantics; |
||
− | |||
− | * using implementation-specific extensions - work needed to track relevant extensions, and possible conflicts with Haskell semantics. |
||
− | |||
− | For now, I'll just use the extensions - they're ugly, but at least they're contained, just like those alternate definitions of <code>seq</code>. But who knows - if this approach to I/O proves useful enough, it might make its way into a future Haskell standard...that's how <code>IO</code> happened[4]. |
||
− | |||
− | In the meantime, take a deep breath: |
||
<haskell> |
<haskell> |
||
+ | parts :: OI -> [OI] |
||
− | -- for GHC 8.6.5 |
||
+ | parts t = let (t1, t2) = part t in t1 : parts t2 |
||
− | {-# LANGUAGE BangPatterns, MagicHash, UnboxedTuples #-} |
||
− | module OutputInput(OI, runOI, seq, getchar, putchar) where |
||
− | import Prelude(Char, String) |
||
− | import Prelude(($), (++), putChar, getChar, error) |
||
− | import Partible |
||
− | import Sequential |
||
− | import GHC.Base(IO(..), State#, MutVar#, RealWorld) |
||
− | import GHC.Base(seq#, realWorld#, newMutVar#, atomicModifyMutVar#) |
||
− | |||
− | data OI = OI OI# |
||
− | |||
− | instance Partible OI where |
||
− | part = partOI |
||
− | |||
− | partOI :: OI -> (OI, OI) |
||
− | partOI (OI r) = case expire# "partOI" r realWorld# of |
||
− | s -> case newMutVar# () s of |
||
− | (# s', r1 #) -> |
||
− | case newMutVar# () s' of |
||
− | (# _, r2 #) -> (OI r1, OI r2) |
||
− | |||
− | runOI :: (OI -> a) -> IO a |
||
− | runOI g = IO $ \s -> case newMutVar# () s of |
||
− | (# s', r #) -> seq# (g (OI r)) s' |
||
− | |||
− | getchar :: OI -> Char |
||
− | getchar (OI r) = case expire# "getchar" r realWorld# of |
||
− | s -> case undo# getChar s of |
||
− | (# _, c #) -> c |
||
− | |||
− | putchar :: Char -> OI -> () |
||
− | putchar c (OI r) = case expire# "putchar" r realWorld# of |
||
− | s -> case undo# (putChar c) s of |
||
− | (# _, x #) -> x |
||
− | |||
− | |||
− | -- Local definitions |
||
− | -- |
||
− | type OI# = MutVar# RealWorld () |
||
− | |||
− | expire# :: String -> MutVar# s () -> State# s -> State# s |
||
− | expire# name r s = case atomicModifyMutVar# r flick s of |
||
− | (# s', _ #) -> s' |
||
− | where |
||
− | flick :: () -> (a, ()) |
||
− | flick x@() = (error nowUsed, x) |
||
− | |||
− | nowUsed = name ++ ": argument already used" |
||
− | |||
− | undo# :: IO a -> State# RealWorld -> (# State# RealWorld, a #) |
||
− | undo# (IO a) = a |
||
</haskell> |
</haskell> |
||
+ | So <code>OI</code> can be a tree-free abstract data type after all: |
||
− | Now you can start breathing again :-) |
||
<haskell> |
<haskell> |
||
+ | data OI |
||
− | module Partible where |
||
+ | partOI :: OI -> (OI, OI) |
||
+ | getChar :: OI -> Char |
||
+ | putChar :: Char -> OI -> () |
||
+ | </haskell> |
||
+ | <sup> </sup> |
||
+ | ---- |
||
− | class Partible a where |
||
+ | === <u>Other interfaces</u> === |
||
− | part :: a -> (a, a) |
||
− | parts :: a -> [a] |
||
+ | * [[Monad|monad]] |
||
− | -- Minimal complete definition: part or parts |
||
− | part u = case parts u of u1:u2:_ -> (u1, u2) |
||
− | parts u = case part u of (u1, u2) -> u1 : parts u2 |
||
− | </haskell> |
||
+ | :<haskell> |
||
− | If you remember, I dispensed with an up-front explanation to try something different. Now that you've |
||
+ | type M a = OI -> a |
||
− | seen just how different this all is, here's the explanation... |
||
+ | unit :: a -> M a |
||
− | That abstract <code>partOI</code> and its overloaded associates <code>part</code> and <code>parts</code>? They help an optimising Haskell implementation to determine when it's safe to use those optimisations. Consider this definition: |
||
+ | unit x = \ u -> let !_ = partOI u in x |
||
+ | bind :: M a -> (a -> M b) -> M b |
||
− | <haskell> |
||
+ | bind m k = \ u -> let !(u1, u2) = partOI u in |
||
− | testme n = n^2 + n^2 |
||
+ | let !x = m u1 in |
||
− | </haskell> |
||
+ | let !y = k x u2 in |
||
+ | y |
||
+ | getcharM :: M Char |
||
− | One simple optimisation would be to replace the duplicates of <code>n^2</code> with a single, shared local definition: |
||
+ | getcharM = getChar |
||
+ | putcharM :: Char -> M () |
||
− | <haskell> |
||
+ | putcharM = putChar |
||
− | testme n = let x = n^2 in x + x |
||
</haskell> |
</haskell> |
||
+ | * [[Comonad|comonad]]: |
||
− | This definition: |
||
− | <haskell> |
+ | :<haskell> |
+ | type C a = (OI, a) |
||
− | main' u = putchars "ha" u `seq` putchars "ha" u |
||
+ | extract :: C a -> a |
||
− | </haskell> |
||
+ | extract (u, x) = let !_ = partOI u in x |
||
+ | duplicate :: C a -> C (C a) |
||
− | would likewise be rewritten, with the result being: |
||
+ | duplicate (u, x) = let !(u1, u2) = partOI u in |
||
+ | (u2, (u1, x)) |
||
+ | extend :: (C a -> b) -> C a -> C b |
||
− | <haskell> |
||
− | + | extend h (u, x) = let !(u1, u2) = partOI u in |
|
+ | let !y = h (u1, x) in |
||
− | </haskell> |
||
+ | (u2, y) |
||
+ | getcharC :: C () -> Char |
||
− | but, as noted by Philip Wadler[5]: |
||
+ | getcharC (u, ()) = getChar u |
||
+ | putcharC :: C Char -> () |
||
− | <blockquote>''[...] the laugh is on us: the program prints only a single <code>"ha"</code>, at the time variable <br><code>x</code> is bound. In the presence of side effects, equational reasoning in its simplest form <br>becomes invalid.''</blockquote> |
||
+ | putcharC (u, c) = putChar c u |
||
+ | </haskell> |
||
− | ''Equational reasoning'' is the basis for that simple optimisation and many others in implementations like GHC - so far they've been serving us quite well. |
||
+ | * [[Arrow|arrow]]: |
||
− | What - just treat I/O-centric definitions as some special case by modifying GHC? Haskell implementations like GHC are complicated enough as is! |
||
+ | :<haskell> |
||
− | The problem is being caused by the code being treated as though it's pure, so let's modify the code instead. In this case, the easiest solution is to make all calls to I/O-centric definitions unique: |
||
+ | type A b c = (OI -> b) -> (OI -> c) |
||
+ | arr :: (b -> c) -> A b c |
||
− | <haskell> |
||
− | + | arr f = \ c' u -> let !x = c' u in f x |
|
− | putchars "ha" u1 `seq` putchars "ha" u2 |
||
− | </haskell> |
||
+ | both :: A b c -> A b' c' -> A (b, b') (c, c') |
||
− | But what about: |
||
+ | 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 |
||
− | <haskell> |
||
− | + | getcharA = \ c' u -> let !(u1, u2) = partOI u in |
|
+ | let !_ = c' u1 in |
||
+ | let !ch = getChar u2 in |
||
+ | ch |
||
+ | putcharA :: A Char () |
||
− | main' = oops (putchars "ha") (putchars "ha") |
||
+ | putcharA = \ c' u -> let !(u1, u2) = partOI u in |
||
+ | let !ch = c' u1 in |
||
+ | let !z = putChar ch u2 in |
||
+ | z |
||
</haskell> |
</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: |
||
− | Will the laugh be on us, again? |
||
+ | * dialogues: |
||
− | This is Haskell, not Clean[6] - there are no uniqueness types to help fend off such potentially-troublesome expressions. For now, the simplest way to make sure <code>OI</code> values are only used once is to have the implementation treat their reuse as being invalid e.g. by throwing an exception or raising an error to stop the offending program. |
||
+ | :<haskell> |
||
− | In the prototype implementation, the maintenance of this all-important ''single-use'' property is performed by <code>expire#</code>. |
||
+ | runD :: ([Response] -> [Request]) -> OI -> () |
||
+ | runD d u = foldr (\ (!_) -> id) () $ yet $ \ l -> zipWith respond (d l) (partsOI u) |
||
+ | yet :: (a -> a) -> a |
||
− | Now for the much-maligned[7] <code>seq</code>...you could be tempted into avoiding its use by using a new data type: |
||
+ | yet f = f (yet f) |
||
+ | respond :: Request -> OI -> Response |
||
− | <haskell> |
||
+ | respond Getq u = let !c = getChar u in Getp c |
||
− | newtype Result a = Is a |
||
+ | respond (Putq c) u = let !_ = putChar c u in Putp |
||
− | + | data Request = Getq | Putq Char |
|
+ | data Response = Getp Char | Putp |
||
− | putchar' :: Char -> OI -> Result () |
||
</haskell> |
</haskell> |
||
+ | * continuations: |
||
− | and case-expressions: |
||
− | <haskell> |
+ | :<haskell> |
+ | type Answer = OI -> () |
||
− | respond' :: Request -> OI -> Response |
||
− | respond' Getq = \u -> case getchar' u of Is c -> Getp c |
||
− | respond' (Putq c) = \u -> case putchar' c u of Is _ -> Putp |
||
− | </haskell> |
||
+ | runK :: Answer -> OI -> () |
||
− | But before you succumb: |
||
+ | runK a u = a u |
||
+ | doneK :: Answer |
||
− | <haskell> |
||
+ | doneK = \ u -> let !_ = partOI u in () |
||
− | unit_Result :: a -> Result a |
||
+ | |||
− | unit_Result = Is |
||
+ | 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 |
||
− | bind_Result :: Result a -> (a -> Result b) -> Result b |
||
+ | putcharK c a = \ u -> let !(u1, u2) = partOI u in |
||
− | bind_Result (Is x) k = k x |
||
+ | let !_ = putChar c u1 in |
||
+ | a u2 |
||
</haskell> |
</haskell> |
||
+ | ...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: |
||
− | Oh look - <code>Result</code> is one of '''those''' types... |
||
− | |||
− | The bang-pattern extension? So you can instead write: |
||
<haskell> |
<haskell> |
||
+ | newtype World = W OI |
||
− | respond'' :: Request -> OI -> Response |
||
− | respond'' Getq = \u -> let !c = getchar u in Getp c |
||
− | respond'' (Putq c) = \u -> let !z = putchar c u in Putp |
||
− | </haskell> |
||
+ | getcharL :: World -> (Char, World) |
||
− | As you can see, <code>z</code> isn't used anywhere - there is no need for it. This being Haskell, if it isn't needed, it isn't evaluated - that allows implementations like GHC to rewrite a definition like <code>respond''</code> as: |
||
+ | getcharL (W u) = let !(u1, u2) = partOI u in |
||
+ | let !c = getChar u1 in |
||
+ | (c, W u2) |
||
+ | putcharL :: Char -> World -> World |
||
− | <haskell> |
||
+ | putcharL c (W u) = let !(u1, u2) = partOI u in |
||
− | respond'' :: Request -> OI -> Response |
||
− | + | let !_ = putChar c u1 in |
|
− | + | W u2 |
|
</haskell> |
</haskell> |
||
+ | <sup> </sup> |
||
+ | ---- |
||
− | You could try all manner of ways to avoid using <code>seq</code> - you might even find one that you like; all well and good...but others might not. For me, the simplest way I've found to make this approach to I/O work is with <code>seq</code> - one that's actually sequential. |
||
+ | === <u>See also</u> === |
||
− | |||
− | But maybe - after all that - you still want <code>seq</code> banished from Haskell. Perhaps you still don't understand I/O in Haskell. It could be that you're dismayed by what you've read here. Alternately, you may have seen or tried this all before, and know it doesn't work - darn... |
||
− | |||
− | If that's you, the corresponding language proposal[8] has a list of other articles and research papers I've found which describe or refer to other approaches - perhaps one (or more) of them will be more acceptable. |
||
− | |||
− | As noted by Owen Stephens[9]: |
||
− | |||
− | <blockquote>''I/O is not a particularly active area of research, but new approaches are still being discovered, <br>iteratees being a case in point.''</blockquote> |
||
− | |||
− | Who knows - the Haskell language could return to having a pure, fully-defined approach to I/O...and it could be you that finds it :-D |
||
− | |||
− | |||
− | P.S: Why the name <code>OI</code>? Many years ago I was tinkering with arrows for performing I/O, labelling them <code>OI a b</code> out of expediency. More recently, I discovered a set of slides[10] describing another approach to I/O which used values of type <code>OI a</code> in a similar fashion to what I've been describing here. I've reused the name because of that similarity. |
||
− | |||
− | |||
− | References: |
||
− | |||
− | [1] [[Sequential ordering of evaluation]]; Haskell Wiki.<br> |
||
− | |||
− | [2] [https://gitlab.haskell.org/ghc/ghc/-/issues/5129 Ticket# 5129: "evaluate" optimized away]; GHC bug tracker.<br> |
||
− | |||
− | [3] [https://www.cs.nott.ac.uk/~pszgmh/appsem-slides/peytonjones.ppt Wearing the hair shirt: a retrospective on Haskell]; Simon Peyton Jones.<br> |
||
− | |||
− | [4] [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.<br> |
||
− | |||
− | [5] [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.3579&rep=rep1&type=pdf How to Declare an Imperative]; Philip Wadler.<br> |
||
− | |||
− | [6] [https://clean.cs.ru.nl/Clean The Clean homepage]; Radboud University, Nijmegen, The Netherlands.<br> |
||
− | |||
− | [7] [https://mail.haskell.org/pipermail/haskell/2002-May/009622.html Thread: State monads don't respect the monad laws in Haskell]; Haskell mail archive.<br> |
||
− | |||
− | [8] [[Partibles for composing monads]]; Haskell Wiki.<br> |
||
− | |||
− | [9] [https://www.owenstephens.co.uk/assets/static/research/masters_report.pdf Approaches to Functional I/O]; Owen Stephens.<br> |
||
− | |||
− | [10] <span style="color:#ba0000">Non-Imperative Functional Programming</span>; Nobuo Yamashita.<br> |
||
+ | * [[Plainly partible]] |
||
+ | * [[Disposing of dismissives]] |
||
+ | * [[IO then abstraction]] |
||
+ | [[Category:Theoretical foundations]] |
||
− | [[User:Atravers|Atravers]] 03:05, 20 August 2020 (UTC) |
Latest 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