Difference between revisions of "Output/Input"
Jump to navigation
Jump to search
m (Selected statements further qualified) |
m |
||
| (66 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| + | Regarding <code>IO a</code>, Haskell's monadic I/O type: |
||
| − | [[Category:Code]] |
||
| + | <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. |
||
| + | Some operations are primitive actions, |
||
| + | corresponding to conventional I/O operations. Special operations (methods in the class <code>Monad</code>, see Section 6.3.6) |
||
| + | sequentially compose actions, corresponding to sequencing operators (such as the semicolon) in imperative |
||
| + | languages. |
||
| + | :<small>[https://www.haskell.org/definition/haskell2010.pdf The Haskell 2010 Report], (page 107 of 329).</small> |
||
| − | Alright then, have a look at this: |
||
| + | </blockquote> |
||
| + | So for I/O, the monadic interface merely provides [[Monad tutorials timeline|an abstract way]] to sequence its actions. However there is another, more direct approach to sequencing: |
||
| − | <haskell> |
||
| − | data OI -- abstract, primitive |
||
| − | |||
| − | partOI :: OI -> (OI, OI) -- |
||
| − | getchar :: OI -> Char -- primitives |
||
| − | putchar :: Char -> OI -> () -- |
||
| − | |||
| − | seq :: a -> b -> b -- also primitive |
||
| − | |||
| − | instance Partible OI where ... |
||
| − | |||
| − | class Partible a where |
||
| − | 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... |
||
| − | |||
| − | 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... |
||
| − | |||
| − | Yes, they're somewhat arcane, but they can be used to emulate all the classic approaches to I/O in Haskell, albeit in miniature: |
||
<haskell> |
<haskell> |
||
| + | Control.Parallel.pseq :: a -> b -> b |
||
| − | module ClassicIO where |
||
| − | import qualified Prelude as T |
||
| − | import Prelude(Char, String) |
||
| − | import Prelude(($), (.)) |
||
| − | import Data.List(map, foldr, zipWith) |
||
| − | import OutputInput |
||
| − | import Partible |
||
| − | |||
| − | -- simple text -- |
||
| − | |||
| − | {- main :: (String -> String) -} |
||
| − | |||
| − | runMain_text :: (String -> String) -> OI -> () |
||
| − | runMain_text main = \u -> case part u of |
||
| − | (u1, u2) -> |
||
| − | putchars (main (getchars u1)) u2 |
||
| − | |||
| − | getchars :: OI -> String |
||
| − | getchars = foldr (\c cs -> seq c (c:cs)) [] . map getchar . parts |
||
| − | |||
| − | putchars :: String -> OI -> () |
||
| − | putchars s = foldr seq () . zipWith putchar s . parts |
||
| − | |||
| − | |||
| − | -- dialogues -- |
||
| − | |||
| − | {- 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 -> seq 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 -> case part u of |
||
| − | (u1, u2) -> |
||
| − | case getchar u1 of |
||
| − | c -> seq c (call (k c) u2) |
||
| − | |||
| − | putchar_cont :: Char -> (() -> IOResult) -> IOResult |
||
| − | putchar_cont c k = R $ \u -> case part u of |
||
| − | (u1, u2) -> |
||
| − | seq (putchar c u1) (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) = case part u of |
||
| − | (u1, u2) -> |
||
| − | case getchar u1 of |
||
| − | c -> seq c (c, S u2) |
||
| − | |||
| − | putchar_stat :: Char -> IOState -> ((), IOState) |
||
| − | putchar_stat c (S u) = case part u of |
||
| − | (u1, u2) -> |
||
| − | 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) |
||
| − | |||
| − | -- supporting definitions -- |
||
| − | -- |
||
| − | getchar :: OI -> Char |
||
| − | getchar = "getchar" `invokes` T.getChar |
||
| − | |||
| − | putchar :: Char -> OI -> () |
||
| − | putchar c = "putchar" `invokes` T.putChar c |
||
</haskell> |
</haskell> |
||
| + | (as opposed to the [[seq|<b>non</b>]]-sequential <code>Prelude.seq</code>.) That means a more direct way of preserving [[Referential transparency|referential transparency]] is also needed. For simple teletype I/O: |
||
| − | What was that - using <code>Prelude.seq</code> that way won't work in Haskell 2010? You are ''correct!''<br> |
||
| − | Now look closely at those imports... |
||
| − | |||
| − | Moving on, here are examples using each of those approaches: |
||
<haskell> |
<haskell> |
||
| + | data OI |
||
| − | module Echoes where |
||
| + | partOI :: OI -> (OI, OI) |
||
| − | import Prelude(String, Char(..), Eq(..)) |
||
| + | getChar :: OI -> Char |
||
| − | import Prelude(($)) |
||
| + | putChar :: Char -> OI -> () |
||
| − | 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'' |
||
| − | |||
| − | echo_cont :: (() -> IOResult) -> IOResult |
||
| − | echo_cont k = getchar_cont $ \c -> |
||
| − | if c == '\n' then |
||
| − | k () |
||
| − | else |
||
| − | putchar_cont c (\_ -> echo_cont k) |
||
| − | |||
| − | echo_stat :: IOState -> ((), IOState) |
||
| − | echo_stat s = case getchar_stat s of |
||
| − | (c, s') -> |
||
| − | if c == '\n' then |
||
| − | ((), s') |
||
| − | else |
||
| − | case putchar_stat c s' of |
||
| − | (_, s'') -> echo_stat s'' |
||
| − | |||
| − | echo_wfth :: IO () |
||
| − | echo_wfth = getchar_wfth `bind` \c -> |
||
| − | if c == '\n' then |
||
| − | unit () |
||
| − | else |
||
| − | putchar_wfth c `bind` \_ -> echo_wfth |
||
</haskell> |
</haskell> |
||
| + | where: |
||
| − | Now that we're on the topic of implementation details, did you notice how easy it was to define that allegedly ''warm, fuzzy''[[#refs|[4]]] <code>IO</code> type using this curious new <code>OI</code> type, and those primitives? |
||
| + | * <code>OI</code> isn't an ordinary Haskell type - ordinary Haskell types represent values without (externally-visible) side-effects, hence <code>OI</code> being abstract. |
||
| − | Sometimes that can be a hint that doing the opposite will be difficult or even impossible while staying within standard Haskell 2010. As it happens, this is one of those cases... |
||
| − | + | * The action <code>partOI</code> is needed because each <code>OI</code> value can only be used once. |
|
| + | * The action <code>getChar</code> obtains the the next character of input. |
||
| − | * modifying your preferred Haskell implementation - lots of work; |
||
| + | * The function <code>putChar</code> expects a character, and returns an action which will output the given character. |
||
| − | * using some other language for the definitions, with Haskell then calling the foreign code - extra work to deal with two different languages; |
||
| + | <br> |
||
| − | * using unsafe or implementation-specific primitives - work needed to avoid conflicts with Haskell semantics; |
||
| + | Now for a few other I/O interfaces - if <code>seq</code> was actually sequential: |
||
| − | * using implementation-specific extensions - work needed to track relevant extensions, and possible conflicts with Haskell semantics. |
||
| + | * [[Monad|monad]] |
||
| − | For now, I'll just use the extensions - they're ugly, but at least they'll be contained to their respecitve modules. 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[[#refs|[5]]]. |
||
| + | :<haskell> |
||
| − | In the meantime, take a very deep breath: |
||
| + | type M a = OI -> a |
||
| + | unit :: a -> M a |
||
| − | <haskell> |
||
| + | unit x = \ u -> let !_ = partOI u in x |
||
| − | -- for GHC 8.6.5 |
||
| − | {-# LANGUAGE MagicHash, UnboxedTuples #-} |
||
| − | module OutputInput(OI, Monomo, runOI, invokes, seq) where |
||
| − | import Prelude(Bool, Char, Double, Either, Float, Int, Integer, Maybe) |
||
| − | import Prelude(String, Eq(..)) |
||
| − | import Prelude(($), (++), error, all) |
||
| − | import Control.Concurrent(ThreadId, MVar, Chan, QSem, QSemN) |
||
| − | import Control.Concurrent.STM(STM, TVar, TMVar, TChan, TQueue, TBQueue) |
||
| − | import Control.Concurrent.STM(TArray) |
||
| − | import Control.Monad.ST(ST) |
||
| − | import Data.Array(Array) |
||
| − | import Data.Array.IO(IOArray) |
||
| − | import Data.Array.ST(STArray) |
||
| − | import Data.Char(isSpace) |
||
| − | import Data.IORef(IORef) |
||
| − | import Data.STRef(STRef) |
||
| − | import Data.Time(UTCTime, NominalDiffTime, Day, TimeOfDay) |
||
| − | import Data.Time(LocalTime, TimeZone, ZonedTime) |
||
| − | import Data.Time(DiffTime) |
||
| − | import Data.Time(UniversalTime) |
||
| − | import System.Directory(XdgDirectory, XdgDirectoryList, Permissions) |
||
| − | import System.IO(Handle, IOMode, BufferMode, SeekMode, HandlePosn) |
||
| − | import System.IO(TextEncoding, Newline, NewlineMode) |
||
| − | import Partible |
||
| − | import Sequential |
||
| − | import GHC.Base(IO(..), State#, MutVar#, RealWorld) |
||
| − | import GHC.Base(seq#, newMutVar#, atomicModifyMutVar#, noDuplicate#) |
||
| − | + | 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 |
||
| − | instance Partible OI where |
||
| − | + | getcharM = getChar |
|
| − | + | putcharM :: Char -> M () |
|
| + | putcharM = putChar |
||
| − | partOI (OI h) = case part# h of (# h1, h2 #) -> (OI h1, OI h2) |
||
| + | </haskell> |
||
| + | * [[Comonad|comonad]]: |
||
| − | runOI :: (OI -> a) -> IO a |
||
| − | runOI g = IO $ \s -> case dispense# s of |
||
| − | (# s', h #) -> seq# (g (OI h)) s' |
||
| + | :<haskell> |
||
| − | invokes :: Monomo a => String -> IO a -> OI -> a |
||
| − | + | type C a = (OI, a) |
|
| − | = (name `invokes#` act) h |
||
| + | extract :: C a -> a |
||
| − | class Monomo a |
||
| + | extract (u, x) = let !_ = partOI u in x |
||
| + | duplicate :: C a -> C (C a) |
||
| − | -- local definitions -- |
||
| + | 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) |
|
| − | case dispense# s' of |
||
| − | (# _, h2 #) -> (# h1, h2 #) |
||
| − | + | getcharC :: C () -> Char |
|
| + | getcharC (u, ()) = getChar u |
||
| − | dispense# s = case newMutVar# () s of |
||
| − | (# s', r #) -> (# s', expire# s' r #) |
||
| − | + | putcharC :: C Char -> () |
|
| + | putcharC (u, c) = putChar c u |
||
| − | expire# s r name = case atomicModifyMutVar# r use s of |
||
| − | (# s', () #) -> s' |
||
| − | where |
||
| − | use x = (error nowUsed, x) |
||
| − | nowUsed = name' ++ ": already expired" |
||
| − | name' = if all isSpace name then "(unknown)" |
||
| − | else name |
||
| − | |||
| − | invokes# :: Monomo a => String -> IO# a -> OI# -> a |
||
| − | (name `invokes#` act) h = case act (noDuplicate# (h name)) of (# _, t #) -> t |
||
| − | |||
| − | type IO# a = State# RealWorld -> (# State# RealWorld, a #) |
||
| − | |||
| − | -- supplemental instances -- |
||
| − | -- |
||
| − | instance (Monomo a, Monomo b) => Monomo (Array a b) |
||
| − | instance Monomo Bool |
||
| − | instance Monomo BufferMode |
||
| − | instance Monomo Char |
||
| − | instance Monomo a => Monomo (Chan a) |
||
| − | instance Monomo Day |
||
| − | instance Monomo DiffTime |
||
| − | instance Monomo Double |
||
| − | instance (Monomo a, Monomo b) => Monomo (Either a b) |
||
| − | instance Monomo Float |
||
| − | instance Monomo Handle |
||
| − | instance Monomo HandlePosn |
||
| − | instance Monomo Int |
||
| − | instance Monomo Integer |
||
| − | instance Monomo (IO a) |
||
| − | instance (Monomo a, Monomo b) => Monomo (IOArray a b) |
||
| − | instance Monomo IOMode |
||
| − | instance Monomo a => Monomo (IORef a) |
||
| − | instance Monomo a => Monomo [a] |
||
| − | instance Monomo LocalTime |
||
| − | instance Monomo a => Monomo (Maybe a) |
||
| − | instance Monomo a => Monomo (MVar a) |
||
| − | instance Monomo Newline |
||
| − | instance Monomo NewlineMode |
||
| − | instance Monomo NominalDiffTime |
||
| − | instance Monomo Permissions |
||
| − | instance Monomo QSem |
||
| − | instance Monomo QSemN |
||
| − | instance Monomo SeekMode |
||
| − | instance Monomo (ST s a) |
||
| − | instance (Monomo a, Monomo b) => Monomo (STArray s a b) |
||
| − | instance Monomo (STM a) |
||
| − | instance Monomo a => Monomo (STRef s a) |
||
| − | instance Monomo TextEncoding |
||
| − | instance Monomo ThreadId |
||
| − | instance Monomo TimeOfDay |
||
| − | instance Monomo TimeZone |
||
| − | instance (Monomo a, Monomo b) => Monomo (TArray a b) |
||
| − | instance Monomo a => Monomo (TBQueue a) |
||
| − | instance Monomo a => Monomo (TChan a) |
||
| − | instance Monomo a => Monomo (TMVar a) |
||
| − | instance Monomo a => Monomo (TQueue a) |
||
| − | instance (Monomo a, Monomo b, Monomo c, Monomo d, Monomo e, Monomo f) => Monomo (a, b, c, d, e, f) |
||
| − | instance (Monomo a, Monomo b, Monomo c, Monomo d, Monomo e) => Monomo (a, b, c, d, e) |
||
| − | instance (Monomo a, Monomo b, Monomo c, Monomo d) => Monomo (a, b, c, d) |
||
| − | instance (Monomo a, Monomo b, Monomo c) => Monomo (a, b, c) |
||
| − | instance (Monomo a, Monomo b) => Monomo (a, b) |
||
| − | instance Monomo a => Monomo (TVar a) |
||
| − | instance Monomo () |
||
| − | instance Monomo UniversalTime |
||
| − | instance Monomo UTCTime |
||
| − | instance Monomo XdgDirectory |
||
| − | instance Monomo XdgDirectoryList |
||
| − | instance Monomo ZonedTime |
||
</haskell> |
</haskell> |
||
| + | * [[Arrow|arrow]]: |
||
| − | Almost there; this replacement definition of <code>seq</code> should work as expected[[#refs|[1][2][3]]]: |
||
| − | <haskell> |
+ | :<haskell> |
| + | type A b c = (OI -> b) -> (OI -> c) |
||
| − | -- for GHC 8.6.5 |
||
| − | {-# LANGUAGE CPP #-} |
||
| − | #define during seq |
||
| − | module Sequential(seq) where |
||
| − | import qualified Prelude(during) |
||
| − | |||
| − | {-# NOINLINE seq #-} |
||
| − | infixr 0 `seq` |
||
| − | seq :: a -> b -> b |
||
| − | seq x y = Prelude.during x (case x of _ -> y) |
||
| − | </haskell> |
||
| − | |||
| − | Now you can start breathing again :-) |
||
| − | |||
| − | <haskell> |
||
| − | module Partible where |
||
| − | import Data.Array |
||
| − | import Data.List |
||
| − | |||
| − | class Partible a where |
||
| − | part :: a -> (a, a) |
||
| − | parts :: a -> [a] |
||
| + | arr :: (b -> c) -> A b c |
||
| − | -- Minimal complete definition: part or parts |
||
| − | + | arr f = \ c' u -> let !x = c' u in f x |
|
| − | parts u = case part u of (u1, u2) -> u1 : parts u2 |
||
| + | both :: A b c -> A b' c' -> A (b, b') (c, c') |
||
| − | instance (Ix a, Partible b) => Partible (Array a b) where |
||
| + | f' `both` g' = \ c' u -> let !(u1:u2:u3:_) = partsOI u in |
||
| − | part arr = case unzip (map part' (assocs arr)) of |
||
| − | ( |
+ | let !(x, x') = c' u1 in |
| + | let !y = f' (unit x) u2 in |
||
| + | let !y' = g' (unit x') u3 in |
||
| + | (y, y') |
||
where |
where |
||
| − | + | unit x u = let !_ = partOI u in x |
|
| − | part' (i, u) = case part u of |
||
| − | (u1, u2) -> ((i, u1), (i, u2)) |
||
| + | getcharA :: A () Char |
||
| − | instance (Partible a, Partible b) => Partible (Either a b) where |
||
| − | + | getcharA = \ c' u -> let !(u1, u2) = partOI u in |
|
| + | let !_ = c' u1 in |
||
| − | parts (Right v) = map Right (parts v) |
||
| + | let !ch = getChar u2 in |
||
| + | ch |
||
| + | putcharA :: A Char () |
||
| − | instance (Partible a, Partible b, Partible c, Partible d, Partible e) => Partible (a, b, c, d, e) where |
||
| + | putcharA = \ c' u -> let !(u1, u2) = partOI u in |
||
| − | parts (u, v, w, x, y) = zipWith5 (,,,,) (parts u) (parts v) (parts w) (parts x) (parts y) |
||
| + | let !ch = c' u1 in |
||
| − | |||
| + | let !z = putChar ch u2 in |
||
| − | instance (Partible a, Partible b, Partible c, Partible d) => Partible (a, b, c, d) where |
||
| − | + | z |
|
| − | |||
| − | instance (Partible a, Partible b, Partible c) => Partible (a, b, c) where |
||
| − | parts (u, v, w) = zipWith3 (,,) (parts u) (parts v) (parts w) |
||
| − | |||
| − | instance (Partible a, Partible b) => Partible (a, b) where |
||
| − | parts (u, v) = zipWith (,) (parts u) (parts v) |
||
</haskell> |
</haskell> |
||
| + | The <code>OI</code> interface can also be used to implement [https://web.archive.org/web/20210414160729/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: |
||
| − | You're having problems? Maybe one of these can help: |
||
| + | * dialogues[https://www.haskell.org/definition/haskell-report-1.2.ps.gz <span></span>][https://dl.acm.org/doi/pdf/10.1145/130697.130699 <span></span>]: |
||
| − | <haskell> |
||
| − | -- for Sequential.hs |
||
| − | import GHC.Base(lazy) |
||
| + | :<haskell> |
||
| − | infixr 0 `seq` |
||
| − | + | runD :: ([Response] -> [Request]) -> OI -> () |
|
| + | runD d u = foldr (\ (!_) -> id) () $ yet $ \ l -> zipWith respond (d l) (partsOI u) |
||
| − | seq x y = Prelude.during x (lazy y) |
||
| − | </haskell> |
||
| + | yet :: (a -> a) -> a |
||
| − | <haskell> |
||
| + | yet f = f (yet f) |
||
| − | -- for ClassicIO.hs |
||
| − | yet :: (a -> a) -> a |
||
| − | yet f = y where y = f y |
||
| − | </haskell> |
||
| + | respond :: Request -> OI -> Response |
||
| − | (You could also try another extensions-compatible version of GHC; beyond that, the options get more complicated...) |
||
| + | 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 |
||
| − | Now, remember how I dispensed with an up-front explanation to try something different? Having just seen how different this all is, here's the explanation... |
||
| + | data Response = Getp Char | Putp |
||
| − | |||
| − | That abstract <code>partOI</code> and its overloaded associates <code>part</code> and <code>parts</code>? Their origins reside in the ''pseudocode'' technique by F. Warren Burton[[#refs|[6]]] - for our purposes, they help an optimising Haskell implementation to determine when it's safe to use those optimisations. Consider this definition: |
||
| − | |||
| − | <haskell> |
||
| − | testme n = n^2 + n^2 |
||
</haskell> |
</haskell> |
||
| + | * [[Continuation|continuations]]: |
||
| − | One simple optimisation would be to replace the duplicates of <code>n^2</code> with a single, shared local definition: |
||
| − | <haskell> |
+ | :<haskell> |
| + | type Answer = OI -> () |
||
| − | testme n = let x = n^2 in x + x |
||
| − | </haskell> |
||
| + | runK :: Answer -> OI -> () |
||
| − | This definition: |
||
| + | runK a u = a u |
||
| + | doneK :: Answer |
||
| − | <haskell> |
||
| + | doneK = \ u -> let !_ = partOI u in () |
||
| − | main' u = putchars "ha" u `seq` putchars "ha" u |
||
| + | getcharK :: (Char -> Answer) -> Answer |
||
| − | </haskell> |
||
| + | 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 |
||
| − | would likewise be rewritten, with the result being: |
||
| + | putcharK c a = \ u -> let !(u1, u2) = partOI u in |
||
| − | |||
| + | let !_ = putChar c u1 in |
||
| − | <haskell> |
||
| − | + | a u2 |
|
</haskell> |
</haskell> |
||
| + | ...and even <i>that</i> <s><i>world</i></s> state-passing style used in GHC, and by [https://web.archive.org/web/20130607204300/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: |
||
| − | but, as noted by Philip Wadler[[#refs|[7]]]: |
||
| − | |||
| − | <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> |
||
| − | |||
| − | ''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. |
||
| − | |||
| − | What - just treat I/O-centric definitions as some special case by modifying GHC? Haskell implementations are complicated enough as is! |
||
| − | |||
| − | 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, one simple solution is to make all calls to I/O-centric definitions unique: |
||
<haskell> |
<haskell> |
||
| + | newtype World = W OI |
||
| − | main u = case part u of |
||
| − | (u1, u2) -> |
||
| − | putchars "ha" u1 `seq` putchars "ha" u2 |
||
| − | </haskell> |
||
| + | getcharL :: World -> (Char, World) |
||
| − | But what about: |
||
| + | 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 |
|
| + | let !_ = putChar c u1 in |
||
| − | |||
| + | W u2 |
||
| − | main' = oops (putchars "ha") (putchars "ha") |
||
</haskell> |
</haskell> |
||
| + | (Rewriting those examples to use <code>pseq</code> is left as an exercise.) |
||
| − | Will the laugh be on us, again? |
||
| − | |||
| − | This is Haskell, not Clean[[#refs|[8]]] - 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. |
||
| − | |||
| − | In the prototype implementation, this all-important ''single-use'' property is maintained by <code>expire#</code>. |
||
| − | |||
| − | As for that curious <code>Monomo</code> class and its instances, they leverage Haskell's type system to provide an extra measure of safety for the prototype - an actual implementation would instead use an annotation[[#refs|[9]]] to achieve the same result e.g: |
||
| − | |||
| − | <haskell> |
||
| − | newEmptyMVar :: monomo a . OI -> MVar a |
||
| − | </haskell> |
||
| − | |||
| − | Now for the much-maligned[[#refs|[10][11]]] <code>seq</code>...you could be tempted into avoiding it by using a new data type: |
||
| − | |||
| − | <haskell> |
||
| − | newtype Result a = Is a |
||
| − | |||
| − | getchar' :: OI -> Result Char |
||
| − | putchar' :: Char -> OI -> Result () |
||
| − | </haskell> |
||
| − | |||
| − | and case-expressions: |
||
| − | |||
| − | <haskell> |
||
| − | 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> |
||
| − | |||
| − | But before you succumb: |
||
| − | |||
| − | <haskell> |
||
| − | unit_Result :: a -> Result a |
||
| − | unit_Result = Is |
||
| − | |||
| − | bind_Result :: Result a -> (a -> Result b) -> Result b |
||
| − | bind_Result (Is x) k = k x |
||
| − | </haskell> |
||
| − | |||
| − | Oh look - <code>Result</code> is one of '''those''' types[[#refs|[12]]]... |
||
| − | |||
| − | The bang-pattern[[#refs|[13]]] extension? So you can instead write: |
||
| − | |||
| − | <haskell> |
||
| − | 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> |
||
| − | |||
| − | 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 normally isn't evaluated. For now, the bang-pattern extension modifies the evaluation of |
||
| − | <code>z</code> in order to prevent <code>respond''</code> being rewritten as: |
||
| − | |||
| − | <haskell> |
||
| − | respond'' :: Request -> OI -> Response |
||
| − | respond'' Getq = \u -> let !c = getchar u in Getp c |
||
| − | respond'' (Putq c) = \u -> Putp |
||
| − | </haskell> |
||
| − | |||
| − | Will bang-patterns ever be included in a future Haskell standard? If so, will you still be able to use them like this? If not, will you be left with the clean-up job? |
||
| − | |||
| − | Perhaps you'll find some other way for correctly sequencing the evaluation 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. |
||
| − | |||
| − | 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 all that well - darn... |
||
| − | |||
| − | If that's you, the corresponding language proposal[[#refs|[14]]] has a list of other articles and research papers I've found which describe or refer to alternative approaches - perhaps one (or more) of them will be more acceptable. |
||
| − | |||
| − | As noted by Owen Stephens[[#refs|[15]]]: |
||
| − | |||
| − | <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 without the notoriety...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[[#refs|[16]]] 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. |
||
| − | |||
| − | |||
| − | <span id="refs">References</span>: |
||
| − | |||
| − | [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://mail.haskell.org/pipermail/glasgow-haskell-users/2006-November/011480.html Thread: seq vs. pseq]; Haskell mail archive.<br> |
||
| − | |||
| − | [4] [https://www.cs.nott.ac.uk/~pszgmh/appsem-slides/peytonjones.ppt Wearing the hair shirt: a retrospective on Haskell]; Simon Peyton Jones.<br> |
||
| − | |||
| − | [5] [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> |
||
| − | |||
| − | [6] [https://academic.oup.com/comjnl/article-pdf/31/3/243/1157325/310243.pdf Nondeterminism with Referential Transparency in Functional Programming Languages]; F. Warren Burton.<br> |
||
| − | |||
| − | [7] [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> |
||
| − | |||
| − | [8] [https://clean.cs.ru.nl/Clean The Clean homepage]; Radboud University, Nijmegen, The Netherlands.<br> |
||
| − | |||
| − | [9] [[Monomorphism by annotation of type variables]]; Haskell Wiki.<br> |
||
| − | |||
| − | [10] [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> |
||
| − | |||
| − | [11] [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.1777&rep=rep1&type=pdf The Impact of ''seq'' on Free Theorems-Based Program Transformations]; Patricia Johann and Janis Voigtlander. |
||
| − | |||
| − | [12] [[Monad]]; Haskell Wiki.<br> |
||
| − | |||
| − | [13] [https://downloads.haskell.org/~ghc/7.8.4/docs/html/users_guide/bang-patterns.html 7.18. Bang patterns]; GHC user's guide.<br> |
||
| − | |||
| − | [14] [[Partibles for composing monads]]; Haskell Wiki.<br> |
||
| − | |||
| − | [15] [https://www.owenstephens.co.uk/assets/static/research/masters_report.pdf Approaches to Functional I/O]; Owen Stephens.<br> |
||
| + | See also: |
||
| − | [16] <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 22:02, 16 September 2024
Regarding IO a, Haskell's monadic I/O type:
Some operations are primitive actions, corresponding to conventional I/O operations. Special operations (methods in the class
Monad, see Section 6.3.6) sequentially compose actions, corresponding to sequencing operators (such as the semicolon) in imperative languages.
- The Haskell 2010 Report, (page 107 of 329).
So for I/O, the monadic interface merely provides an abstract way to sequence its actions. However there is another, more direct approach to sequencing:
Control.Parallel.pseq :: a -> b -> b
(as opposed to the non-sequential Prelude.seq.) That means a more direct way of preserving referential transparency is also needed. For simple teletype I/O:
data OI
partOI :: OI -> (OI, OI)
getChar :: OI -> Char
putChar :: Char -> OI -> ()
where:
OIisn't an ordinary Haskell type - ordinary Haskell types represent values without (externally-visible) side-effects, henceOIbeing abstract.
- The action
partOIis needed because eachOIvalue can only be used once.
- The action
getCharobtains the the next character of input.
- The function
putCharexpects a character, and returns an action which will output the given character.
Now for a few other I/O interfaces - if seq was actually sequential:
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:
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
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, and 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
(Rewriting those examples to use pseq is left as an exercise.)
See also: