Editing The I/O problem (section)

== The problem is mathematical in origin ==

The various fields of study collectively referred to as <i>mathematics</i> are abstract in one or more ways:

<blockquote>
In a preliminary sense, mathematics is abstract because it is studied using highly general and formal resources.

:<small>[https://iep.utm.edu/math-app The Applicability of Mathematics], from the [https://iep.utm.edu/ Internet Encyclopedia of Philosophy].</small>
</blockquote>

For a declarative programming language like Haskell, which is based on one of these individual fields of study - higher-order functions - being so abstract then raises the question of I/O and its observable effects:

<blockquote>
How must interactions between a program and an external environment
(consisting of, e.g., input/output-devices, file systems, ...) be described in
a programming language that abstracts from the existence of an outside world?

:<small>[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.9846&rep=rep1&type=pdf Functions, Frames and Interactions], Claus Reinke (page 10 of 210).</small><!-- 1998 -->
</blockquote>

and effects more generally, with a preference for a denotational (as opposed to [[Monad_tutorials_timeline|inexplicable]]) semantics:

<blockquote>
During the 1960s, several researchers began work on proving things about programs. [...]

Several difficult problems emerged from this work. One was the problem of <i>specification</i>: before
one can prove that a program is correct, one must specify the meaning of "correct", formally and
unambiguously. Formal systems for specifying the meaning of a program were developed, and they
looked suspiciously like programming languages.

Researchers began to analyze why it is often harder to prove things about programs written in
traditional languages than it is to prove theorems about mathematics. Two aspects of traditional
languages emerged as sources of trouble because they are very difficult to model in a mathematical
system: mutability and sequencing.

:<small>[https://core.ac.uk/download/pdf/214330064.pdf The Anatomy of Programming Languages], Alice E. Fischer and Frances S. Grodzinsky (page 353 of 600).</small><!-- 1993 -->
</blockquote>

* mutability:

<blockquote>
There is <i>in principle</i> nothing to stop functional programs from
passing a single extra parameter into and out of every single function in the
entire system. If this extra parameter were a collection (compound value)
of some kind then it could be used to <i>simulate</i> an arbitrarily large set of
mutable variables. In effect this approach recreates a single pool of global
variables - hence, even though referential transparency is maintained, ease
of reasoning is lost (we still know that each function is dependent only upon
its arguments, but one of them has become so large <i>and contains irrelevant
values</i> that the benefit of this knowledge as an aid to understanding is
almost nothing).

:<small>[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.8928&rep=rep1&type=pdf Out of the Tar Pit], Ben Moseley and Peter Marks (page 17 of 66).</small><!-- 2006 -->
</blockquote>

* sequencing:

<blockquote>
We have experimented for some time with a means for the programmer to specify a
‘syntactic’ partial order between subexpressions, with the intended effect that the ‘semantic’
order in which the input actions occur during the evaluation is not in conflict with the specified
‘syntactic’ partial order on the subexpressions (which carries over to the input actions evoked
by those subexpressions). As a consequence, whenever the evaluator is about to execute an
input action, it first has to decide whether there will occur in the future another input action
that should be done first according to the specified ‘syntactic’ partial order. That problem,
however, is undecidable.

:<small>[https://maartenfokkinga.github.io/utwente/mmf2001c.pdf An alternative approach to I/O], Maarten Fokkinga and Jan Kuper (page 6 of 12).</small><!-- 2001 -->
</blockquote>

=== The technical difficulty ===

[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.144.2237&rep=rep1&type=pdf In 1994] researchers showed that mutability and sequencing, if restricted, could be used anonymously in Haskell:

<blockquote>
The reason for introducing a <i>different</i> monad <code>ST</code>, rather than just providing
these operations over the <code>IO</code> monad, is that destructive updates to variables in 
a program are not <i>externally visible</i> side-effects. We can therefore encapsulate
these imperative effects [...] Using <code>runST</code> we can write pure (non-monadic) functions
whose implementation uses imperative features internally.

:<small>[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.697.6499&rep=rep1&type=pdf Monads and Effects], Nick Benton, John Hughes and Eugenio Moggi (pages 33-34 of 82).</small><!-- 2002 --> 
</blockquote>

So I/O is a problem because of its external visibility, and that visibility demands the side effects of I/O have the appropriate sequencing:

<blockquote>
By introducing <i>side effects</i> in expressions, the semantics becomes
significantly more complex. At the same time, several issues arise,
related to the <i>evaluation order</i>, i.e. the order in which the subparts of
an expression are evaluated. If the evaluation order is not strictly defined,
the presence of side effects in expressions is a source of non-deterministic
behaviour.

:<small>[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.9189&rep=rep1&type=pdf Denotational Semantics of Evaluation Order in Expressions with Side Effects], Nikolaos S. Papaspyrou (first page).</small><!-- 1998 -->
</blockquote>

<blockquote>
When combining effects,
their order is often highly important (the reader might want to try different
combinations of the effects “Open door”, and “Walk through door”, for example).

:<small>[https://cth.altocumulus.org/~hallgren/Thesis/fudgets_thesis_color.pdf Fudgets – Purely Functional Processes with applications to Graphical User Interfaces], Magnus Carlsson and Thomas Hallgren (page 12 of 263).</small><!-- 1998 -->
</blockquote>

...and the machinery which runs our programs relies on mutability:

<blockquote>
An “automatic” machine becomes a “choice” machine as soon as we allow the machine’s tape
to be modified by external entities: the tape itself becomes a means of communication. This is
essentially what happens in “real” computers (memory-mapped I/O); for example, we can write
to the computer’s screen by modifying one particular area of memory, or find out which key was
pressed on the computer’s keyboard by reading another.

It is less obvious how to add interaction to the lambda calculus.

:<small>[http://edsko.net/pubs/thesis.pdf Making Uniqueness Typing Less Unique], Edsko de Vries (page 23 of 264).</small><!-- 2008 -->
</blockquote>

<blockquote>
This problem affects communication with users as well as explicit control over
the state of the computing equipment and the programming environment or any
other state- or communication-based computation. Without an adequate solution,
functional languages could hardly be called general purpose.

:<small>[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.9846&rep=rep1&type=pdf Functions, Frames and Interactions], Claus Reinke (page 10 of 210).</small><!-- 1998 -->
</blockquote>

<blockquote>
Stream transformers are fragile to use, continuations are powerful
but somewhat clutter the syntax of functions. Monads and
uniqueness types both present a trade-off, do we accept
the over-sequentialisation imposed by monads, or the visual
disorder of explicit environment passing? We believe that a
compromise is still to be found [...]

:<small>[https://www.owenstephens.co.uk/assets/static/research/masters_report.pdf Approaches to Functional I/O], Owen Stephens (final page).</small><!-- 2011 -->
</blockquote>

Using prior research:

<blockquote>
The theory of relative computability developed by Turing and Post and
the <i>o</i>-machines provide a precise mathematical framework for interactive
or online computing just as Turing <i>a</i>-machines provide one for offline
computing processes such as batch processing.

:<small>[http://www.people.cs.uchicago.edu/~soare/Turing/shagrir.pdf Turing-Post Relativized Computability and Interactive Computing], Robert Irving Soare (page 7 of 76).</small><!-- 2011 -->
</blockquote>

a more satisfactory solution could be obtained. Another possibility is a completely-new discovery: the investigation [http://conal.net/blog/posts/can-functional-programming-be-liberated-from-the-von-neumann-paradigm#comment-598 continues]. In the meantime, those who work with programming languages will have to contend with I/O as best they can:

<blockquote>
By its very nature I/O does not fit in well
with programming language design. Every language
designer has encountered the problem that the task of
including usable I/O facilities invariably seems to make it
necessary to break some of the rules or design principles
of the language. In many languages with clean and
simple concepts I/O is the "odd one out".

:<small>[https://www.cs.kent.ac.uk/pubs/1997/2176/content.pdf I/O Considered Harmful (At Least for the First Few Weeks)], John Rosenberg and Michael Kölling (first page).</small><!-- 1997 -->
</blockquote>

<blockquote>
[...] I/O calls are side effects and make impure functions. Impure functions
are hard to test.

:<small>[https://refactoringjs.com/files/refactoring-javascript.pdf Refactoring JavaScript], Evan Burchard (page 437 of 499).</small><!-- 2017 -->
</blockquote>

...especially considering the ever-expanding state space in which memory-mapped I/O resides:

<blockquote>
<b>Definition 6.1.</b> A <i>state</i> is an element of 2<sup><i>n</i></sup> for some fixed <i>n</i>; that is, it is a finite
sequence of 1s and 0s. The space 2<sup><i>n</i></sup> is called the <i>state space</i>.

The number <i>n</i> is the size of the memory in bits, and will usually be rather large.
On modern personal computers at the time of this writing, <i>n</i> would be on the order
of several billion.

:<small>[https://math.uchicago.edu/~may/VIGRE/VIGRE2011/REUPapers/Berger.pdf On Some Aspects of The Theory of Monads], Carsen Berger (page 14 of 16).</small><!-- 2011 -->
</blockquote>