Difference between revisions of "Open research problems"
Jump to navigation
Jump to search
m (Extra pertinent quotes added) |
m |
||
| (8 intermediate revisions by the same user not shown) | |||
| Line 5: | Line 5: | ||
=== Efficiency of lazy functional languages === |
=== Efficiency of lazy functional languages === |
||
:{| |
:{| |
||
| − | This is a problem that came up during IRC discussions. We consider a purely functional language L: |
+ | This is a problem that came up during IRC discussions. We consider a purely functional language ''L'': |
* By "purely functional" we mean a language that has value semantics; that is, there is no function such that after evaluation of the function the value that was referred to by something else changed. (Also known as "No Side Effects"). |
* By "purely functional" we mean a language that has value semantics; that is, there is no function such that after evaluation of the function the value that was referred to by something else changed. (Also known as "No Side Effects"). |
||
* A value is "changed" when it is not the case during an evaluation that when the old value and the new value would both be fully evaluated, there wouldn't be the same result. This should make sure that laziness is allowed in the purely functional language.<br> |
* A value is "changed" when it is not the case during an evaluation that when the old value and the new value would both be fully evaluated, there wouldn't be the same result. This should make sure that laziness is allowed in the purely functional language.<br> |
||
<br> |
<br> |
||
| − | Can purely functional languages like L can implement all algorithms that can be implemented in a language like C as efficiently in an amortized sense, ignoring space-usage? |
+ | Can purely functional languages like ''L'' can implement all algorithms that can be implemented in a language like C as efficiently in an amortized sense, ignoring space-usage? |
|} |
|} |
||
=== I/O === |
=== I/O === |
||
| + | :See [[The I/O problem|the I/O problem]]. |
||
| − | :{| |
||
| − | Some pertinent quotes: |
||
| − | <br> |
||
| − | <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"'', Haskell Discourse.</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 <i>execution</i>, and instead has an order-independent notion of <i>evaluation</i>. 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 IO, 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 <i>letrec</i>, <i>case</i>, 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> |
||
| − | |||
| − | 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 [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.628.7053&rep=rep1&type=pdf practical] to use? |
||
| − | * Or would any denotative language be [https://www.oreilly.com/library/view/programming-perl-3rd/0596000278/ch01s04.html solipsistic?] |
||
| − | |||
| − | |||
| − | 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. |
||
| − | |} |
||
== Specific problems == |
== Specific problems == |
||
| Line 119: | Line 20: | ||
=== Implement encapsulated-state interface entirely in Haskell (no primitives) === |
=== Implement encapsulated-state interface entirely in Haskell (no primitives) === |
||
:{| |
:{| |
||
| − | Implement <code>Data.STRef</code> and <code>Control.Monad.ST.runST</code> without using the built-in monadic <code>ST</code> or <code>IO</code> types. This needs to happen with operations that all run in |
+ | Implement <code>Data.STRef</code> and <code>Control.Monad.ST.runST</code> without using the built-in monadic <code>ST</code> or <code>IO</code> types. This needs to happen with operations that all run in ''O''(1) amortized time. |
|} |
|} |
||
Latest revision as of 12:50, 31 May 2022
General problems
Efficiency of lazy functional languages
-
This is a problem that came up during IRC discussions. We consider a purely functional language L:
- By "purely functional" we mean a language that has value semantics; that is, there is no function such that after evaluation of the function the value that was referred to by something else changed. (Also known as "No Side Effects").
- A value is "changed" when it is not the case during an evaluation that when the old value and the new value would both be fully evaluated, there wouldn't be the same result. This should make sure that laziness is allowed in the purely functional language.
Can purely functional languages like L can implement all algorithms that can be implemented in a language like C as efficiently in an amortized sense, ignoring space-usage?
I/O
- See the I/O problem.
Specific problems
Implement encapsulated-state interface entirely in Haskell (no primitives)
-
Implement
Data.STRefandControl.Monad.ST.runSTwithout using the built-in monadicSTorIOtypes. This needs to happen with operations that all run in O(1) amortized time.