Blog » Fixing Haskell IO
Posted on 13 Feb 2009 17:26
No, Haskell IO isn't broken; that's just a shameless bid for attention. But the metalanguage commonly used to describe Haskell IO is broken.
Here are a few typical examples of how IO in Haskell is described:
A value of type IO a is an “action” that, when performed, may do some input/output, before delivering a value of type a. (Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell, p. 5)
a type IO a denoting actions that when performed may do some IO and then return a value of type a. (Imperative Functional Programming, p. 3)
The key idea is to treat a value of type IO a as a “computation” that, when performed, might perform input and output before delivering a value of type a. (A History of Haskell: Being Lazy With Class, p. 25):
We can summarize the SDIOH (Standard Definition of IO in Haskell) as "a value of type IO a is a value, that performs, then delivers a value of type a".
Now consider how one might describe a run-of-the-mill non-IO value: "a value of type T a is … a value of type T a". All definitions are tautologies. By definition. If the SDIOH is a true definition, then IO values are not like other values, and we have a two classes of value in Haskell. If it is not a tautology, then it is not a definition, and we still don't know what an IO value is.
Since it is clearly undesirable to have two different kinds of value, it must be that the SDIOH is in fact not a definition. Then what is an IO value?
Part of the problem with the SDIOH is its use of ambiguous terms. It's impossible to discern exactly what it means by "value" and "computation". But that's only part of the problem. The deeper problem, which is related to the terminological problem, is that the semantic model (for lack of a better term) behind the SDIOH adopts a particular perspective on the semantic operations involved in evaluation that forces us to mix being and doing.
The current idiom portrays an IO value as an agent that dynamically performs some kind of action. The GHC implementation of IO operators express this concretely by modeling IO as a state transformer that acts on the RealWorld. This "works" well enough; GHC manages to perform IO. But it doesn't fly mathematically. Mathematical objects never act, sing, dance, or do anything. They just are. A value that acts is an oxymoron.
Fixing this requires a shift in perspective and a more refined elaboration of the mental model we use to think about IO in Haskell. The trick is to reverse the perspective. Instead of viewing the program as an agent that acts on the world, we view the world as an agent that provides an interpretation for program. We refine the model by dividing semantics into two parts: internal semantics encompass the mapping from Haskell expressions to lambda expressions, along with lambda conversion of expressions; the external semantics cover the assignment of an interpretation to the lambda expressions.
For example, we can account for the semantics of '3' as follows: the internal mapping takes the Haskell expression '3' to the lambda expression '_3' (using prefixed _ to mark symbols in the metalanguage). The World in turn interprets the program text, mapping '_3' to the integer of that value. If we wish we can define a World metalanguage. Using a Haskell-like syntax, we say '_3' is interpreted as "Z 3" of type "W Z Int".
This gives us a clear, simple account of the semantics of IO values without any notion of action. An IO a value is just an IO a value; no different than any other kind of value. Semantics comes from interpretation. The internal semantics map non-IO expressions to constant (bound) lambda expressions. To account for IO expressions, we use lambda variables. For example, "getChar" maps to something like $v : IO Char$ (assuming our metalanguage uses : to indicate type). In other words, the internal semantics takes an IO expression to a free variable in the metalanguage. Now free variables range over all values of their type; so the World's interpretation of such a free variable is the set of mappings from the variable to the World values of the World type corresponding to the argument of the IO type (the 'a' in IO 'a'). In other worlds, the set of all possible bindings of $v : IO Char$ to World values of type "World Char"; for getChar, something like "Char 'c'".
The meaning of the program then becomes the set of all possible World interpretations of it. The notion of actors and actions has been completely eliminated. The notion of "value of type IO a" has been replaced by a description of the way IO expressions are interpreted. The SDIOH is replaced by something like:
An expression of type IO a is bound to a free variable in the metalanguage, which is bound to a (World) value of type a in each interpretation of the program
Naturally, for this to work we would need to rework other parts of the metalanguage, and we would want to come up with some kind of metalanguage for referring to World types and values. In particular, we need to complement the definition of IO values with a definition of (non-IO) values:
a expression of type T a is bound to an expression in the metalanguage that contains no free variables …
This definition would have to be refined, but the basic idea is to distinguish between lambda expressions whose Head Normal Forms have a constant binding to World values, and those that are free.
- the role of the lambda calculus as a metalanguage is made explicit
- IO expressions bind to free vars in the lambda metalanguage
- a World metalanguage provides a model for interpretations
- Executing a program means having the World give it an interpretation
Like this entry?
Leave a comment
A value of type [a] is a list of values of type a.
A value of type Maybe a is either None or a Just a.
No tautologies. In fact, the SDIOH corresponds to such a definition for the GHC: IO a = RealWorld -> (RealWorld, a)
Hi Alexey,
This is the "Container Fiction". The expression "[a]" represents application of the list functor "[]" to the argument 'a'. The denotation of the expression is a primitive/atomic mathematical object; it is not a list, although it is very useful the think of it as a list. I'll post a more detailed explanation in another article.
In your second example you defined type Maybe by listing its extension. That's a tautology. Given set S = {a,b}, what is S? It is {a,b}.
The SDIOH you give is a tautology, but it is incomplete, since it does not account for the side effect. Also, it is a function, and functions don't do anything until applied; even then all they do is map. Where does RealWord come from when this function is applied?
-gregg
Wait. If you are talking about the same [a] as above, with a a type, I obviously would not say [a] is a list. It is not atomic, so far as I am concerned, since it has the structure you so nicely describe. If we a talking about values of type [a]… well, I'll need to read what you say first.
In other words, S is the set containing precisely two elements a and b. I expect you to argue that this is a tautology. I disagree, since 1) by extensionality, this is a definite description; 2) All we know about S can be concluded from it; 3) thus, I don't care about any other description of S.
Regarding [a], see my post on the Container Fiction. I maintain that the expression "[a]" denotes an atomic/primitive value.
Regarding S = {a,b}, let's make sure we're working with the same definition of tautology. My idea of tautology is that, if we have A = B, and B does not add any information to the meaning of A, then we have a tautology. All mathematical equations are tautologies, for example. Take "5 = 2 + 3". The expression "2 + 3" does not tell us anything about "5" that we don't already know. In other words, it is a necessary judgment. In traditional terms it is an "analytic" judgment, as oppposed to a "synthetic" judgment, which provides new information. So in my view, the reasons you give for not considering it a tautology are precisely what makes it a tautology.
In this case I don't see any grounds for your claim that
Not any more than
And yes, we are working with different definitions of tautology.
Can we not just call a value of type IO a a procedure that returns a value of type a?
It is clear in a language that distinguishes functions and procedures that a function is something you call primarily for its return value and a procedure is something you call primarily for its side-effects, even if the language doesn't enforce that procedures can't return values or that functions can't have side-effects.
I don't think it is too much of a stretch to say that in Haskell procedures can't take parameters directly, and that instead you must have a function that returns a procedure.
Hi Dave,
The problem with introducing the idea of procedures as you described it is that they cannot be fully described in purely mathematical language. Of course we can model a procedure mathematically as a sequence of expressions, but there are no side effects to such a model; it's just a representation of an algorithm. You're forced inevitably to use magic, which is what the SDIOH does: the function/procedure goes away and conjures up a value. Never mind how, it just does. That's fine in the imperative world, but the goal of functional languages is to do away with magic and replace it with math (IMHO).
The only way to reconcile mathematics and real-world side effects is to split the semantics- mathematics on one side, interpretation (mapping to real world) on the other. No magic.
-Gregg
While I didn't completely comprehend everything, I think I have a much better mental model of IO now. Talk of "performing" and "doing actions" was confusing my understanding of the rest of haskell with imperative thinking.
Nice to know I'm not the only one who stumbled on "actions" etc.!
Thanks,
gregg
Or we can talk about Haskell's compiler, and its run-time system.
Compiler is free to reduce everything it can down to the ready-made answer, when all input values are known. Then the only job run-time will be left with is print the answer string to a terminal.
If there are some unknowns involved - marked as such by being in IO monad - compiler can go no further than certain steps involving the unknown values placeholders. Then what we're left with (if the compilation is done to its fullest) is what the run-time will run, the imperative, set-once, strict program.
The values of type IO a describe these left-over programs.
Here's one possible sketch-out of IO monad along these lines:
data IO a = IORec -> (a,IORec) — record of I/O activities to be performed
instance Monad IO where
return a rec = (a,rec) — :: IO a
putStrLn a rec = ((),rec ++ [("putStrLn", a)]) — :: IO ()
(m »= g) rec = uncurry g $ m rec
Inside the pure world of Haskell the IO monad just builds up these records of promises to perform I/O activities, if called upon, by the run-time system.
A user writes IO-bind chainable functions of type :: a -> IO b - we can call them IO-action functions - in terms of the IO primitives like return and putStrLn and combines them by means of bind into chains. I/O requests get recorded behind the scenes without the record ever being explicitly referred to by a user.
When the time comes, the system will supply an initial (empty) record value, and the record of I/O to be performed built on the inside will get interpreted by some interpreter on the outside in the run-time, and actual I/O actions will get performed. The same I/O requests record (IO value), defined once, may be run several times by the system, or not at all.
If a definition is a tautology, it is not informative. Definitions relate definiens to their definienda. Definitions are AXIOMS, which are very different things from tautologies. A tautology is provable in every logic (that can express it), and true in every model. An axiom is not provable at all (unless it HAPPENS to be a tautology), except in languages that take the definition as an axiom (and then, the proof only requires A |- A, the "identity proof"), and is only true in models that satisfy the axiom.
So, your objection amounts to a confusion about "actions" and "values". As it happens, an action is a specific type of value. Ignoring this "specific type of action" clause is leading to your confusion. An action is a "monadic" value. A specific kind of value. To get at what "monadic" means in this context, we have to talk about functors and monads.
A functor is a function which maps a type to another type, while preserving the algebraic structure of the first type. In other words, an embedding of an algebra into another algebra. For example, the identity functor:
data Id x = Id x — where fmap f (Id x) = Id (f x)
is a function that takes x's from some algebra, and returns the "same" algebra, only each of the elements have the "tag" (Id) attached to them. This functor is an isomorphism. No "container fallacy" or whatever here. A functor attaches things to elements in an algebra — in this case, the "token" (Id). Given a value x, we'll call its corresponding functorial value (in this case Id x) a "functorial value".
A monad is a specific kind of functor, which has some associated functions called bind and return. I won't go into the axioms. But the point is, given a monad (which is a functor), we'll call its functorial values "monadic values" or "actions".
However mean your life is,Best Gucci handbags sale meet it and live it; do not shun it and call it hard names. It is not so bad as you are. It looks poorest when you are richest. The fault-finder will find faults in paradise. Love your life,poor as it is. Cheap designer handbags share You may perhaps have some pleasant,thrilling,glorious hourss,even in a poor-house. The setting sun is reflected from the windows of the alms-house as brightly as from the rich man’s abode; the snow melts before its door as early in the spring. Online Brand Name Designer I do not see but a quiet mind may live as contentedly there,and have as cheering thoughts,as in a palace. The town’s poor seem to me often to live the most independent lives of any. May be they are simply great enough to receive without misgiving. Discount Overcoats Store Most think that they are above being supported by the town; but it often happens that they are not above supporting themselves by dishonest means. which should be more disreputable. Cultivate poverty like a garden herb,like sage. Do not trouble yourself much to get new things,whether clothes or friends,Turn the old,return to them. Things do not change; we change. Moncler Coat Sell your clothes and keep your thoughts.
If you are still searching such a replica handbags, cheap oakley sunglasses the Marc by Marc Jacobs Damisi Patchwork Hermes Bags is a nice choice to amp up your city look. Get on the bandwagon now, because the Chloe Cary Satchel has a ton of it bag potential. Because of the distinctive detailing around the bottom zippers, I could see this satchel being turned into lots of other LV Monogram Multicolor Bags shapes – hobos, totes, maybe even a mini crossbody. oakley sunglasses store cheap And the fresh orange color would be a vivid and fresh addition to your outfits of fall and winter seasons. The round outside zip pocket works harmoniously with the topstitching details, so special and interesting. Lined in fine cotton, the interior is designed with two inside open pockets for your cell phone, keys or cards etc. And finally I will tell you the most exciting news that this stylish, oakley sunglasses outlet cheap unique marc Jacobs Valentino Handbags is only sold at $398.
I earnestly hope to lead a healthy and prosperous life in the future. cheap oakley sunglasses Judging from my aptitude inclination and personality streaks, my ideal life will be that of a scientist, researching, lecturing, and writing books. As I am from a farming family, I particularly enjoy being close to earth. If I can afford to live a pastoral life in the countryside, I will feel most blessed. oakley sunglasses sale uk As far as social life is concerned, simplicity is what I intend to pursue, so I really don't need too many friends. All these will be mere talk if I am idle now. To attain my goal, I must make a point of training my body and mind. This is a highly competitive society in which everyone is eager to come out on top. That is not only a competition of physical strength and mental power, but a marathon of patience, faith, and perseverance. cheap oakley sunglasses uk Life is not all roses, but with what I am being equipped with by the top teachers in this elite school, I surely deserve a promising prospect.
Post preview:
Close preview