37

monads are described as the haskell solution to deal with IO. I was wondering if there were other ways to deal with IO in pure functional language.

Cheick
  • 2,154
  • 24
  • 28
  • You can build an interpreter for an embedded DSL using ADTs or GADTs that only allows the effects you want. Maybe with the use of quasi/quotes you can reuse a lot of the Haskell syntax tree... IO Actions would either run inside your embedded DSL, or they would transform the parse tree of your eDSL... – aoeu256 Aug 15 '19 at 21:22

7 Answers7

37

What alternatives are there to monads for I/O in a pure functional language?

I'm aware of two alternatives in the literature:

  • One is a so-called linear type system. The idea is that a value of linear type must be used exactly one time: you can't ignore it, and you can't use it twice. With this idea in mind, you give the state of the world an abstract type (e.g., World), and you make it linear. If I mark linear types with a star, then here are the types of some I/O operations:

    getChar :: World* -> (Char, World*)
putChar :: Char -> World* -> World*

    and so on. The compiler arranges to make sure you never copy the world, and then it can arrange to compile code that updates the world in place, which is safe because there is only one copy.

    The uniqueness typing in the language Clean is based on linearity.

    This system has a couple of advantages; in particular, it doesn't enforce the total ordering on events that monads do. It also tends to avoid the "IO sin bin" you see in Haskell where all effectful computations are tossed into the IO monad and they all get totally ordered whether you want total order or not.

  • The other system I'm aware of predates monads and Clean and is based on the idea that an interactive program is a function from a (possibly infinite) sequence of requests to a (possibly infinite) sequence of responses. This system, which was called "dialogs", was pure hell to program. Nobody misses it, and it had nothing in particular to recommend it. Its faults are enumerated nicely in the paper that introduced monadic I/O (Imperative Functional Programming) by Wadler and Peyton Jones. This paper also mentions an I/O system based on continuations which was introduced by the Yale Haskell group but which was short-lived.

Norman Ramsey
  • 198,648
  • 61
  • 360
  • 533
  • 1
    Sequencing via monad binding is pretty much just type-checked continuation-passing style anyway, isn't it? My impression was that monads and continuations are mostly interchangeable, except that continuations are decidedly not, in general, either warm *or* fuzzy. – C. A. McCann Jan 28 '10 at 23:09
  • 2
    Continuations form a monad but monads are decidedly *not* continuations. CPS is way more powerful because you're allowed to make copies of things (including continuations!). Monads restrict things much more severely than mere type-checking. – Norman Ramsey Jan 28 '10 at 23:24
  • 1
    "Monads are decidedly not continuations" - no, but the relationship isn't just an InstanceOf one. Cf. http://lambda-the-ultimate.org/node/3235 Lawvere Theories and Monads, Hyland & Power, 2007. – Charles Stewart Jan 29 '10 at 13:17
  • Haven't had the time to read that Wadler & Jones paper yet, but I'm curious--any examples of something that could be done with real continuations (without wrecking type safety or referential transparency) that can't be done with the `Cont` monad? Obviously there are many unsafe things that continuations enable, but a hypothetical Haskell-with-call/cc would presumably disallow those anyway. Or if this is discussed in the paper, I'll make time to read it this weekend... – C. A. McCann Jan 29 '10 at 13:45
  • 1
    How does the linear type system work with concurrency? – CMCDragonkai Feb 20 '15 at 04:53
  • 1
    I'm pretty sure the statements "Nobody misses [dialog-based I/O], and it had nothing in particular to recommend it" are unconditionally false. I would omit them, and I would *definitely* avoid citing a single paper (by partisans of another I/O system!) as evidence for them. Dialogs have several advantages which are difficult/impossible to recover with GHC's implementation of the IO monad (although implementing IO on top of dialogs instead would give you the best of both worlds). – Jonathan Cast Sep 14 '16 at 14:59
  • isn't the Dialog type the exact opposite of what you show? a user program *makes* (produces) *requests* of the run-time system, and *gets* back its *responses* from it. – Will Ness Jun 07 '20 at 10:01
9

Besides linear types, there's also effect system.

Wei Hu
  • 2,888
  • 2
  • 27
  • 28
6

If by "pure" you mean "referentially transparent", that is, that an applied function is freely interchangeable with its evaluated result (and therefore that calling a function with the same arguments has the same result every time), any concept of stateful IO is pretty much excluded by definition.

There are two rough strategies that I'm aware of:

  • Let a function do IO, but make sure that it can never be called twice with the exact same arguments; this side-steps the issue by letting the functions be trivially "referentially transparent".

  • Treat the entire program as a single pure function taking "all input received" as an argument and returning "all output produced", with both represented by some form of lazy stream to allow interactivity.

There are a variety of ways to implement both approaches, as well as some degree of overlap--e.g., in the second case, functions operating on the I/O streams are unlikely to be called twice with the same part of the stream. Which way of looking at it makes more sense depends on what kind of support the language gives you.

In Haskell, IO is a type of monad that automatically threads sequential state through the code (similar to the functionally pure State monad), such that, conceptually, each call to an otherwise impure function gets a different value of the implicit "state of the outside world".

The other popular approach I'm aware of uses something like linear types to a similar end; insuring that impure functions never get the same arguments twice by having values that can't be copied or duplicated, so that old values of the "state of the outside world" can't be kept around and reused.

C. A. McCann
  • 76,893
  • 19
  • 209
  • 302
  • For examples of the first approach, see F. Warren Burton's [Nondeterminism with Referential Transparency in Functional Programming Languages](https://academic.oup.com/comjnl/article-pdf/31/3/243/1157325/310243.pdf). – atravers Feb 19 '21 at 01:17
  • Your second rough strategy defines even a C program as a purely functional one! :-D – Student Jul 01 '22 at 13:20
5

Uniqueness typing is used in Clean

Doug Currie
  • 40,708
  • 1
  • 95
  • 119
5

Imperative Functional Programming by Peyton Jones and Wadler is a must read if you are interested in functional IO. The other approaches that they discuss are:

  • Dialogues which are lazy streams of responses and requests

type Dialogue = [Response] -> [Request]

main :: Dialogue

  • Continuations - each IO operation takes a continuation as argument

  • Linear types - the type system restricts you in a way that you cannot copy or destroy the outside state, which means that you can't call a function twice with the same state.

Daniel
  • 26,899
  • 12
  • 60
  • 88
4

Functional Reactive Programming is another way to handle this.

Dobes Vandermeer
  • 8,463
  • 5
  • 43
  • 46
1

I was wondering if there were other ways to deal with IO in a pure functional language.

Just adding to the other answers already here:

  • The title of this paper says it all :-)
  • You could also look at:

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

  • When Haskell was young, Lennart Augustsson wrote of using system tokens as the mechanism for I/O:

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

I've yet to find a online copy but I have no pressing need for it, otherwise I suggest contacting the library at Chalmers.

atravers
  • 455
  • 4
  • 8