@@ Line 1: / Line 1: @@
+#redirect [[The I/O problem]]
-<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
-[...] we need to come up with better answers about how to interact with the world. The blanket answer of “just push the <code>IO</code> monad through the entire codebase” is not great for a number of reasons [...]
+[[Category:Pages to be removed]]
-<tt>[https://discourse.haskell.org/t/using-unsafeperformio-safely/4146/47 Using <code>unsafePerformIO</code> safely], Victor Miraldo.</tt>
-</div>
-<br>
-<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
-This is hard stuff. Two years ago I spent several hours to write 3 lines invoking <code>IO</code> computations.
-<tt>[https://discourse.haskell.org/t/trying-to-understand-the-io/1172/8 Trying to understand the <code>IO ()</code>], ''"belka"''.</tt>
-</div>
-<br>
-<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
-<code>IO</code> is indeed a monad instance, but not a very nice one - the compiler treats it specially, and it is not very nice to reason about [...]
-<tt>[https://nickhu.co.uk/Monads.pdf Understanding Monads], Nick Hu.</tt>
-</div>
-<br>
-<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
-Haskell compromises brilliantly, by fencing off pure and impure functions from one another [...] The illusion is so good that programmers are fooled into thinking I/O is pure in Haskell. And now that we can write mostly pure code with occasional impure wrappers, researchers have mostly stopped seeking superior alternatives.
-<tt>[https://crypto.stanford.edu/~blynn/haskell/io.html A Problem With I/O], Ben Lynn.</tt>
-</div>
-<br>
-<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
-Once you’re in the <code>IO</code> monad, you’re stuck there forever, and are reduced to Algol-style imperative programming. You cannot easily convert between functional and monadic style without a radical restructuring of code.
-<tt>[https://existentialtype.wordpress.com/2011/05/01/of-course-ml-has-monads Of Course ML Has Monads!], Robert Harper.</tt>
-</div>
-<br>
-<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
-Functional programmers used to worry about how to solve “the I/O problem”. Functional programming (FP) eschews any notion of side-effect or order of ''execution'', and instead has an order-independent notion of ''evaluation''. In contrast, input & output (I/O) seems to be an inherently effectful, ordered notion.
-[...]
-In a sense, I see us as in a worse position than before. Since the adoption of monadic <code>IO</code>, it’s been less immediately apparent that we’re still enslaved [...] Our current home is not painful enough to goad us onward, as were continuation-based I/O and stream-based I/O. (See [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.168.4008&rep=rep1&type=pdf A History of Haskell], section 7.1.) Nor does it fully liberate us.
-<tt>[http://conal.net/blog/posts/can-functional-programming-be-liberated-from-the-von-neumann-paradigm Can functional programming be liberated from the von Neumann paradigm?], Conal Elliott.</tt>
-</div>
-<br>
-<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
-Sadly [...] many Haskell programmers believe that <code>IO</code> is necessary to do "real programming", and they use Haskell as if it were C (relegating lots of work to <code>IO</code>). In other words, monadic <code>IO</code> has proved to be such a comfortable "solution" to I/O in a functional language, that very few folks are still searching for a genuinely (not merely technically) functional solution. Before monadic <code>IO</code>, there was a lot of vibrant and imaginative work on functional I/O. [...]
-<tt>[http://conal.net/blog/posts/the-c-language-is-purely-functional#comment-467 The C language is purely functional], Conal Elliott.</tt>
-</div>
-<br>
-<div style="border-left:1px solid lightgray; padding: 1em" alt="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 [...]
-<tt>[https://www.owenstephens.co.uk/assets/static/research/masters_report.pdf Approaches to Functional I/O], Owen Stephens.</tt>
-</div>
-<br>
-<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
-The common method to relieve the programming language designer from the inherent IO-problems is to shift responsibility to the programmer who has to sequentialize all IO-requests. This is also true for the monadic approach implemented in Haskell.
-<tt>[https://core.ac.uk/download/pdf/14504553.pdf FUNDIO: A Lambda-Calculus With ''letrec'', ''case'', Constructors, and an IO-Interface:], Manfred Schmidt-Schauß.</tt>
-</div>
-<br>
-<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
-The programming style in a lazy functional language is heavily influenced by the supported I/O-mechanism. Modifying the I/O-behaviour or debugging some lazy functional program that uses I/O is a black art. It is interesting that novices in lazy functional programming in general expect that there is some direct (side-effecting) I/O using a function call.
-<tt>[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.1076&rep=rep1&type=pdf A Partial Rehabilitation of Side-Effecting I/O:], Manfred Schmidt-Schauß.</tt>
-</div>
-<br>
-<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
-The downside of I/O using monads is the need for a monad that can not be unwrapped. So, when using monadic I/O there is no way to get rid of the I/O monad. Furthermore, it is not as intuitive as one would like it to be. A prerequisite to good software design is a thorough understanding of the structures and glues of the implementation language. [...]  Yet the understanding of monads is not trivial. The extensive amount of tutorials and questions on the Internet strengthen this thought.
-<tt>[https://essay.utwente.nl/57287/1/scriptie_Rorije.pdf Input/Output in Functional Languages (Using Algebraic Union Types)], R.J. Rorije.</tt>
-</div>
-<br>
-<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
-The notation for interactive programs written in the monadic style is irritatingly close to the notation used in imperative languages.<br>
-[...]<br>
-Uniqueness typing addresses the more general problem of statically controlled use of resources in functional programs and, even if combined with passing unique representations of environment objects as arguments to these programs, it does not suffice to solve the input/output-problem. [...] The reason is that the environment is not updated in one conceptual step after the evaluation of a program [...] but rather in small steps whenever the environment representation is modified during program evaluation. The primitive interactions are thus implemented as side-effecting operations, the use of which is rendered safe in the uniqueness-typed environment passing framework.
-<br>
-[...]<br>
-Similarly, monads are used to address the more general problem of computations (involving state, input/output, backtracking, ...) returning values: they do not solve any input/output-problems directly but rather provide an elegant and flexible abstraction of many solutions to related problems. [...] For instance, no less than three different input/output-schemes are used to solve these basic problems in [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.9725&rep=rep1&type=pdf Imperative functional programming], the paper which originally proposed `a new model, based on monads, for performing input/output in a non-strict, purely functional language'.<br>
-[...]<br>
-So, both input/output-schemes merely provide frameworks in which side-effecting operations can safely be used with a guaranteed order of execution and without affecting the properties of the purely functional parts of the language.
-<tt>[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.9846&rep=rep1&type=pdf Functions, Frames and Interactions], Claus Reinke.</tt>
-</div>
-<br>
-<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
-Although we all love the beautiful aspects of functional languages we must admit that it is difficult to deal with a beast called Input-Output (I/O).
-<tt>[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.43.6060&rep=rep1&type=pdf The Beauty and the Beast], Peter Achten and Rinus Plasmeijer.</tt>
-</div>
-<br>
-__TOC__
-== The I/O problem is mathematical in origin ==
-The various fields of study collectively referred to as <i>mathematics</i> are abstract in one or more ways:
-<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
-In a preliminary sense, mathematics is abstract because it is studied using highly general and formal resources.
-<tt>[https://iep.utm.edu/math-app The Applicability of Mathematics], from the [https://iep.utm.edu/Internet Encyclopedia of Philosophy].</tt>
-</div>
-In particular, they abstract from the existence of an external environment. So programming languages based on one or more of these individual fields of study:
-* Haskell, Clean, Miranda<sup>(R)</sup>: higher-order functions,
-* Prolog: first-order predicate logic,
-* Mercury: both;
-are left with a problem with regards to I/O and its observable effects:
-<div style="border-left:1px solid lightgray; padding: 1em" alt="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?
-<tt>[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).</tt>
-</div>
-<sup> </sup>
-<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
-Input/output is [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.13.9123&rep=rep1&type=pdf awkward] in declarative languages. Some functional languages like LISP have procedural read and write operations. Prolog has ugly read and write "predicates" that execute in sequence.
-<tt>[https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.227.6709&rep=rep1&type=pdf Specifying Input/Output by Enumeration], Walter W. Wilson and Yu Lei.</tt>
-</div>
-It should then be of little surprise that attempts to find a <i>"mathematical solution"</i> for I/O have been less than successful:
-<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
-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 <b>very difficult to model in a mathematical system</b>: mutability and sequencing.
-<tt> [https://core.ac.uk/download/pdf/214330064.pdf The Anatomy of Programming Languages], Alice E. Fischer and Frances S. Grodzinsky (emphasis added).</tt>
-</div>
-* What would be ideal is an extension of one or more fields of mathematics which can [https://www.cs.kent.ac.uk/people/staff/dat/krc/paraffins-turner.pdf elegantly] describe interactions with external environments -  the appropriate denotational semantics can then be used to map it into languages like Haskell or Prolog.
-* Alternately (and less ideally), if it can be proven that one cannot exist (like the solution to the halting problem) then implementors everywhere can just select the most-suitable model of I/O, as they see fit.
-== On being denotative ==
-Another possibility which has been put forward by [[Denotative programming timeline|some]] is for languages like Haskell to not just be declarative, but [[Denotative|denotative]]:
-<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
-My vision of “solving the I/O problem” for functional programming is nothing like Haskell’s semantically imperative (non-)solution (called <code>IO</code> in Haskell), but rather to continue shifting semantically imperative mechanisms out of the programming model and into the implementation of (semantically simple) function application.
-<tt>[http://conal.net/blog/posts/can-functional-programming-be-liberated-from-the-von-neumann-paradigm Conal Elliott.]</tt>
-</div>
-because of how various other effects have been moved out of previous languages:
-<div style="border-left:1px solid lightgray; padding: 1em" alt="blockquote">
-The imperative interfaces in today OSs and data-bases are troubling at first, and indeed I often hear people (even on <tt>#haskell</tt>) using these examples as demonstration that the imperative programming model is inescapable. These examples don’t trouble me, however, because I see that we’ve already dealt with others of their kind. Underneath the implementation of our current functional abstractions (numbers, strings, trees, functions, etc), there are imperative mechanisms, such as memory allocation & deallocation, stack frame modification, and thunk overwriting (to implement laziness). Every one of these mechanisms can be used as evidence against the functional paradigm by someone who hasn’t yet realized how the mechanism can be shifted out of the role of a programming model notion and into the role of implementation of a programming model notion. The new notion is more composable by virtue of being semantically simpler and mathematically more well-behaved.
-Stack and register munging and jump/<code>GOTO</code> are implementations of the semantically simpler notion of function application. (I mean “function” in the sense of math and of pure functional programming.) Moreover, stack & register munging is the input/output (IO) part of the implementation of function application. Information goes <b>out</b> of one context and <b>in</b>to another.
-</div>
-However, there is a crucial difference between those and the effects of I/O - apart from debugging purposes, there is the expectation that effects in an implementation are <i>"hidden"</i> : they should not make their presence known. In contrast, the simplest of I/O effects are <b>intended</b> to be observable - that is their [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.13.9123&rep=rep1&type=pdf <i>raison d’être!</i>]
-Then there's the need to reuse foreign code: an FFI potentially allows countless more effect-centric operations to be accessed. Moving all of them into a finite implementation isn't just impractical - it's impossible.
-So there are limits to the ongoing confinement of effects inside implementations, and thus the ability of a language to be both denotative and [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.628.7053&rep=rep1&type=pdf practical]. To truly be considered general-purpose, a programming language must be capable of outside interactions.
-<small>
-Note: none of this constitutes a <i>"proof of impossibility"</i>, as eluded to earlier. For example, changing away from the solid-state Turing machines currently in widespread use may render this particular argument academic: only time will tell.
-</small>
-== Open questions ==
-* Is there an alternate standalone model of I/O with less problems than each of the current models?
-* If not, can I/O be moved away from the language (as a model) and into the implementation (making the language [https://www.cs.cmu.edu/~crary/819-f09/Landin66.pdf denotative]), while keeping the resulting language relatively [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.628.7053&rep=rep1&type=pdf practical] to use?
-== Other 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 [[Referential transparency|referentially transparent]], which severely restricts the ability to use [[Equational reasoning examples|equational reasoning]].
-* Is the Haskell language "purely functional"?
-::[https://chadaustin.me/2015/09/haskell-is-not-a-purely-functional-language Haskell is not a purely functional language], but is often described as being referentially transparent.
-* Can functional programming be liberated from the von Neumann paradigm?
-::Only if no-one proves it to be impossible (e.g. like trying to solve the halting problem).
-* Why do our programs need to read input and write output?
-::Because programs are usually written for [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.628.7053&rep=rep1&type=pdf practical] purposes, such as implementing domain-specific [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.7.2089&rep=rep1&type=pdf little languages] like [https://dhall-lang.org Dhall].
-== Other articles ==
-* [https://maartenfokkinga.github.io/utwente/mmf2001c.pdf An alternative approach to I/O], Maarten Fokkinga and Jan Kuper.
-* [https://www.f.waseda.jp/terauchi/papers/toplas-witness.pdf Witnessing Side Effects], Tachio Terauchi and Alex Aiken.
-* [https://www.cs.bham.ac.uk/~udr/papers/assign.pdf Assignments for Applicative Languages], Vipin Swarup, Uday S. Reddy and Evan Ireland.
-* [https://www.cs.bham.ac.uk/~udr/papers/imperative-functional.pdf Imperative Functional Programming], Uday S. Reddy.
-* [https://core.ac.uk/download/pdf/82162724.pdf Functional Programming with Side Effects], Mark B. Josephs.
-* [https://www.cs.ru.nl/barendregt60/essays/hartel_vree/art10_hartel_vree.pdf Lambda Calculus For Engineers], Pieter H. Hartel and Willem G. Vree.
-* [https://accu.org/index.php/journals/2199 On Zero-Side-Effect Interactive Programming, Actors, and FSMs], Sergey Ignatchenko.
-* [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.128.9269&rep=rep1&type=pdf Unique Identifiers in Pure Functional Languages], Péter Diviánszky.
-* [https://www.cs.nott.ac.uk/~pszgmh/clairvoyant.pdf Call-by-Need Is Clairvoyant Call-by-Value], Jennifer Hackett and Graham Hutton.
-* [https://academic.oup.com/comjnl/article-pdf/31/3/243/1157325/310243.pdf Nondeterminism with Referential Transparency in Functional Programming Languages], F. Warren Burton.

Difference between revisions of "Open research problems/The I/O quandary"

Latest revision as of 21:19, 12 July 2022

Navigation menu

Search