# Difference between revisions of "Output/Input"

m |
m (Example type corrected >_<) |
||

Line 106: | Line 106: | ||

An early implementation of Fran represented behaviors as implied in the formal semantics: | An early implementation of Fran represented behaviors as implied in the formal semantics: | ||

<haskell> | <haskell> | ||

− | data Behavior a = Time -> a | + | data Behavior a = Behavior (Time -> a) |

</haskell> | </haskell> | ||

</div> | </div> |

## Revision as of 04:52, 5 December 2021

## Contents

__Clearing away the smoke and mirrors__

The implementation in GHC uses the following one:

```
type IO a = World -> (a, World)
```

An `IO`

computation is a function that (logically) takes the state of the world, and returns a modified world as well as the return value. Of course, GHC does not actually pass the world around; instead, it passes a dummy “token,” to ensure proper sequencing of actions in the presence of lazy evaluation, and performs input and output as actual side effects!

`A History of Haskell: Being Lazy With Class, Paul Hudak, John Hughes, Simon Peyton Jones and Philip Wadler.`

...so what starts out as an I/O action of type:

```
World -> (a, World)
```

is changed by GHC to approximately:

```
() -> (a, ())
```

As the returned unit-value `()`

contains no useful information, that type can be simplified further:

```
() -> a
```

_{Why "approximately"? Because "logically" a function in Haskell has no observable effects.}

__Previously seen__

The type `() -> a`

(or variations of it) have appeared elsewhere:

- page 2 of 13 in A Correspondence Between ALGOL 60 and Church's Lambda-Notation: Part I by Peter Landin:

The use of

`λ`

, and in particular (to avoid an irrelevant bound variable) of`λ()`

, to delay and possibly avoid evaluation is exploited repeatedly in our model of ALGOL 60. A function that requires an argument-list of length zero is called a*none-adic*function.^{ }(\ () -> …) :: () -> a

- page 3 of Assignments for Applicative Languages by Vipin Swarup, Uday S. Reddy and Evan Ireland:

A value of type

`Obs 𝜏`

is called an*observer*. Such a value observes (i.e. views or inspects) a state and returns a value of type`𝜏`

. [...] An observer type`Obs 𝜏`

may be viewed as an implicit function space from the set of states to the type`𝜏`

.^{ }type Obs tau = State -> tau

- page 15 of
*Non-Imperative Functional Programming*by Nobuo Yamashita:

type a :-> b = OI a -> b

- MTL style for free by Tom Ellis:

data Time_ a = GetCurrentTime (UTCTime -> a)

- An impure lazy programming language, also by Tom Ellis:

data IO a = IO (() -> a)

- page 2 of Unique Identifiers in Pure Functional Languages by Péter Diviánszky:

[...] The type

`Id`

can be hidden by the synonym data type:: Create a :== Id -> a

^{ }type Create a = Id -> a

- page 7 of Functional Reactive Animation by Conal Elliott and Paul Hudak:

An early implementation of Fran represented behaviors as implied in the formal semantics:

data Behavior a = Behavior (Time -> a)

- page 26 of How to Declare an Imperative by Philip Wadler:

The type

`'a io`

is represented by a function expecting a dummy argument of type`unit`

and returning a value of type`'a`

.type 'a io = unit -> a

^{ }type Io a = () -> a

- Free Monads for Less (Part 3 of 3): Yielding IO by Edward Kmett:

newtype OI a = forall o i. OI (FFI o i) o (i -> a) deriving Functor

^{ }type Oi a = forall i . i -> a

- page 27 of Purely Functional I/O in Scala by Rúnar Bjarnason:

class IO[A](run: () => A)

^{ }class Io a where run :: () -> a

Let's say you want to implement

`IO`

in SML :structure Io : MONAD = struct type 'a t = unit -> 'a ⋮ end

^{ }type T a = () -> a

newtype IO a = IO { runIO :: () -> a }

newtype Supply r a = Supply { runSupply :: r -> a }

As long as we have its special case

`IO c = () ~> c`

, we can represent (up to isomorphism) […]`a ~> c`

[…]

Of these, it is the implementation of `OI a`

in Yamashita's oi package which is most interesting as its values are *monousal* - once used, their contents remain constant. This single-use property also appears in the implementation of the abstract `decision`

type described by F. Warren Burton in Nondeterminism with Referential Transparency in Functional Programming Languages.

`IO`

__, redefined__

Based on these and other observations, a reasonable distillment of these examples would be `OI -> a`

, which then implies:

```
type IO a = OI -> a
```

Using Burton's *pseudodata* approach:

```
-- abstract; single-use I/O-access mediator
data Exterior
getchar :: Exterior -> Char
putchar :: Char -> Exterior -> ()
-- from section 2 of Burton's paper
data Tree a = Node { contents :: a,
left :: Tree a,
right :: Tree a }
-- utility definitions
type OI = Tree Exterior
getChar' :: OI -> Char
getChar' = getchar . contents
putChar' :: Char -> OI -> ()
putChar' c = putchar c . contents
part :: OI -> (OI, OI)
parts :: OI -> [OI]
part t = (left t, right t)
parts t = let !(t1, t2) = part t in
t1 : parts t2
```

Of course, in an actual implementation `OI`

would be abstract like `World`

, and for similar reasons. This allows for a simpler implementation for `OI`

and its values, instead of being based on (theoretically) infinite structured values like binary trees. That simplicity has benefits for the `OI`

interface, in this case:

```
data OI
part :: OI -> (OI, OI)
getChar' :: OI -> Char
putChar' :: Char -> OI -> ()
```

^{ }

__Various questions__

- Is the C language "purely functional"?

- No:
- C isn't "pure" - it allows unrestricted access to observable effects, including those of I/O.
- C isn't "functional" - it was never intended to be referentially transparent, which severely restricts the ability to use equational reasoning.

- No:

- Can functional programming be liberated from the von Neumann paradigm?

- That remains an open research problem.

- Can a language be "purely functional" or "denotative"?

- Conditionally, yes - the condition being the language is restricted in what domains it can be used in:

- If a language is free of observable effects, including those of I/O, then the only other place where those effects can reside is within its implementation.
- There is no bound on the ways in which observable effects can be usefully combined, leading to a similarly-unlimited variety of imperative computations.
- A finite implementation cannot possibly accommodate all of those computations, so a subset of them must be chosen. This restricts the implementation and language to those domains supported by the chosen computations.

- Why do our programs need to read input and write output?

- Because programs are usually written for practical purposes, such as implementing domain-specific little languages.