What other ways can state be handled in a pure functional language besides with Monads?

Question

So I started to wrap my head around Monads (used in Haskell). I'm curious what other ways IO or state can be handled in a pure functional language (both in theory or reality). For example, there is a logical language called "mercury" that uses "effect-typing". In a program such as haskell, how would effect-typing work? How does other systems work?

Kappel

As said by isturdy, Clean uses uniqueness types like Mercury does, though these do IMO fit to Mercury's paradigm way better than to purely functional languages, where Monads are just the way to go. – Aether

I guess that would fit better to programmers.stackexchange.com – Hot

To correct the question, Mercury does not use effect-typing it uses uniqueness typing (like Clean). Effect typing is different (see DDC) – Marienthal

#13537261 – Borreri

Answer 1

There are several different questions involved here.

First, IO and State are very different things. State is easy to do yourself: Just pass an extra argument to every function, and return an extra result, and you have a "stateful function"; for example, turn a -> b into a -> s -> (b,s).

There's no magic involved here: Control.Monad.State provides a wrapper that makes working with "state actions" of the form s -> (a,s) convenient, as well as a bunch of helper functions, but that's it.

I/O, by its nature, has to have some magic in its implementation. But there are a lot of ways of expressing I/O in Haskell that don't involve the word "monad". If we had an IO-free subset of Haskell as-is, and we wanted to invent IO from scratch, without knowing anything about monads, there are many things we might do.

For example, if all we want to do is print to stdout, we might say:

type PrintOnlyIO = String

main :: PrintOnlyIO
main = "Hello world!"

And then have an RTS (runtime system) which evaluates the string and prints it. This lets us write any Haskell program whose I/O consists entirely of printing to stdout.

This isn't very useful, however, because we want interactivity! So let's invent a new type of IO which allows for it. The simplest thing that comes to mind is

type InteractIO = String -> String

main :: InteractIO
main = map toUpper

This approach to IO lets us write any code which reads from stdin and writes to stdout (the Prelude comes with a function interact :: InteractIO -> IO () which does this, by the way).

This is much better, since it lets us write interactive programs. But it's still very limited compared to all the IO we want to do, and also quite error-prone (if we accidentally try to read too far into stdin, the program will just block until the user types more in).

We want to be able to do more than read stdin and write stdout. Here's how early versions of Haskell did I/O, approximately:

data Request = PutStrLn String | GetLine | Exit | ...
data Response = Success | Str String | ...
type DialogueIO = [Response] -> [Request]

main :: DialogueIO
main resps1 =
    PutStrLn "what's your name?"
  : GetLine
  : case resps1 of
        Success : Str name : resps2 ->
            PutStrLn ("hi " ++ name ++ "!")
          : Exit

When we write main, we get a lazy list argument and return a lazy list as a result. The lazy list we return has values like PutStrLn s and GetLine; after we yield a (request) value, we can examine the next element of the (response) list, and the RTS will arrange for it to be the response to our request.

There are ways to make working with this mechanism nicer, but as you can imagine, the approach gets pretty awkward pretty quickly. Also, it's error-prone in the same way as the previous one.

Here's another approach which is much less error-prone, and conceptually very close to how Haskell IO actually behaves:

data ContIO = Exit | PutStrLn String ContIO | GetLine (String -> ContIO) | ...

main :: ContIO
main =
    PutStrLn "what's your name?" $
    GetLine $ \name ->
    PutStrLn ("hi " ++ name ++ "!") $
    Exit

The key is that instead of taking a "lazy list" of responses as one big argument at he beginning of main, we make individual requests that accept one argument at a time.

Our program is now just a regular data type -- a lot like a linked list, except you can't just traverse it normally: When the RTS interprets main, sometimes it encounters a value like GetLine which holds a function; then it has to get a string from stdin using RTS magic, and pass that string to the function, before it can continue. Exercise: Write interpret :: ContIO -> IO ().

Note that none of these implementations involve "world-passing". "world-passing" isn't really how I/O works in Haskell. The actual implementation of the IO type in GHC involves an internal type called RealWorld, but that's only an implementation detail.

Actual Haskell IO adds a type parameter so we can write actions that "produce" arbitrary values -- so it looks more like data IO a = Done a | PutStr String (IO a) | GetLine (String -> IO a) | .... That gives us more flexibility, because we can create "IO actions" that produce arbitrary values.

(As Russell O'Connor points out, this type is just a free monad. We can write a Monad instance for it easily.)

---

Where do monads come into it, then? It turns out that we don't need Monad for I/O, and we don't need Monad for state, so why do we need it at all? The answer is that we don't. There's nothing magical about the type class Monad.

However, when we work with IO and State (and lists and functions and Maybe and parsers and continuation-passing style and ...) for long enough, we eventually figure out that they behave pretty similarly in some ways. We might write a function that prints every string in a list, and a function that runs every stateful computation in a list and threads the state through, and they'll look very similar to each other.

Since we don't like writing a lot of similar-looking code, we want a way to abstract it; Monad turns out to be a great abstraction, because it lets us abstract many types that seem very different, but still provide a lot of useful functionality (including everything in Control.Monad).

Given bindIO :: IO a -> (a -> IO b) -> IO b and returnIO :: a -> IO a, we could write any IO program in Haskell without ever thinking about monads. But we'd probably end up replicating a lot of the functions in Control.Monad, like mapM and forever and when and (>=>).

By implementing the common Monad API, we get to use the exact same code for working with IO actions as we do with parsers and lists. That's really the only reason we have the Monad class -- to capture the similarities between different types.

Am‚lie

"Given bindIO :: IO a -> (a -> IO b) -> IO b and returnIO :: a -> IO a, we could write any IO program in Haskell without ever thinking about monads." Not true: those functions create a monad. We might be able to write an IO program without thinking of the typeclass Monad, but functions with those signatures (provided they obey some further laws which I assume your hypothetical functions would) constitute being a monad. – Struble

Sure. I mean without thinking of monads-in-general. Every time we use (.), it's a valid implementation of fmap, and it obeys the Functor laws; but that doesn't mean we think about properties of functors in general when we use it. We only get the benefits when we recognize the abstraction. – Am‚lie

This is a good description of State, IO and Monads in Haskell, but it only indirectly answers the user's question. – Marienthal

Answer 2

Another major approach is uniqueness typing, as in Clean. The short story is that handles to state (including the real world) can only be used once, and functions that access mutable state return a new handle. This means that an output of the first call is an input of a second, forcing the sequential evaluation.

Effect typing is used in the Disciple Compiler for Haskell, but to the best of my knowledge it would take considerable compiler work to enable it in, say, GHC. I shall leave discussion of the details to those better-informed than myself.

Roselba

The Disciple Compiler does not compile Haskell code, it compiles Disciple code, which is a different but related language. This cannot be integrated into GHC as effect typing is not a part of Haskell. – Marienthal

Its own documentation claims it to be a dialect of Haskell, which I am willing to grant. It seems little different from GHC and its numerous extensions, albeit harder to integrate with code not using the extensions. – Roselba

Answer 3

Well, first what is state? It can manifest as a mutable variable, which you don't have in Haskell. You only have memory references (IORef, MVar, Ptr, etc.) and IO/ST actions to act on them.

However, state itself can be pure as well. To acknowledge that review the 'Stream' type:

data Stream a = Stream a (Stream a)

This is a stream of values. However an alternative way to interpret this type is a changing value:

stepStream :: Stream a -> (a, Stream a)
stepStream (Stream x xs) = (x, xs)

This gets interesting when you allow two streams to communicate. You then get the automaton category Auto:

newtype Auto a b = Auto (a -> (b, Auto a b))

This is really like Stream, except that now at every instant the stream gets some input value of type a. This forms a category, so one instant of a stream can get its value from the same instant of another stream.

Again a different interpretation of this: You have two computations that change over time and you allow them to communicate. So every computation has local state. Here is a type that is isomorphic to Auto:

data LS a b =
    forall s.
    LS s ((a, s) -> (b, s))

Stoller

Answer 4

Take a look at A History of Haskell: Being Lazy With Class. It describes two different approaches to doing I/O in Haskell, before monads were invented: continuations and streams.

Rento

Answer 5

There is an approach called Functional Reactive Programming that represents time-varying values and/or event streams as a first-class abstraction. A recent example that comes to my mind is Elm (it is written in Haskell and has a syntax similar to Haskell).

Tonneson

Answer 6

I'm curious - what other ways I/O or state can be handled in a pure functional language (both in theory or reality)?

I'll just add to what's already been mentioned here (note: some of these approaches don't seem to have one, so there are a few "improvised names").

Approaches with freely-available descriptions or implementations:

• "Orthogonal directives" - see An alternative approach to I/O by Maarten Fokkinga and Jan Kuper.

• Pseudodata - see Nondeterminism with Referential Transparency in Functional Programming Languages by F. Warren Burton. The approach is used by Dave Harrison to implement clocks in his thesis Functional Real-Time Programming: The Language Ruth And Its Semantics, and name supplies in the functional pearl On generating unique names by Lennart Augustsson, Mikael Rittri and Dan Synek; there are also a few library implementations in Hackage.

• Witnesses - see Witnessing Side Effects by Tachio Terauchi and Alex Aiken.

• Observers - see Assignments for Applicative Languages by Vipin Swarup, Uday S. Reddy and Evan Ireland.

Other approaches - references only:

• System tokens:

  L. Augustsson. Functional I/O Using System Tokens. PMG Memo 72, Dept Computer Science, Chalmers University of Technology, S-412 96 Göteborg, 1989.

• "Effect trees":

  Rebelsky S.A. (1992) I/O trees and interactive lazy functional programming. In: Bruynooghe M., Wirsing M. (eds) Programming Language Implementation and Logic Programming. PLILP 1992. Lecture Notes in Computer Science, vol 631. Springer, Berlin, Heidelberg.

Candent