Open research problems
Revision as of 11:20, 30 October 2021 by Atravers (Added links for I/O, state, and effect-related articles)
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?
Some pertinent quotes:
- 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 denotative), while keeping the resulting language practical to use?
- Or would any denotative language be solipsistic?
- An alternative approach to I/O, Maarten Fokkinga and Jan Kuper.
- Witnessing Side Effects, Tachio Terauchi and Alex Aiken.
- Assignments for Applicative Languages, Vipin Swarup, Uday S. Reddy and Evan Ireland.
- Imperative Functional Programming, Uday S. Reddy.
- Functional Programming with Side Effects, Mark B. Josephs.
- Lambda Calculus For Engineers, Pieter H. Hartel and Willem G. Vree.
- On Zero-Side-Effect Interactive Programming, Actors, and FSMs, Sergey Ignatchenko.
- Unique Identifiers in Pure Functional Languages, Péter Diviánszky.
- Call-by-Need Is Clairvoyant Call-by-Value, Jennifer Hackett and Graham Hutton.
- FUNDIO: A Lambda-Calculus With
case, Constructors, and an IO-Interface: Approaching a Theory of
unsafePerformIO(Technical Report Frank-16), Manfred Schmidt-Schauß.
Implement encapsulated-state interface entirely in Haskell (no primitives)
Control.Monad.ST.runSTwithout using the built-in monadic
IOtypes. This needs to happen with operations that all run in O(1) amortized time.