On 30/12/2011 15:23, Gregg Reynolds wrote:
Now one way of understanding all this is to say that it implicates the static/dynamic (compile-time/run-time) distinction: you don't know what e.g. IO values are until runtime, so this distinction is critical to distinguishing between pure and impure. I gather this is your view. Yes. I think that is reasonable, but with the caveat that it must be at the right level of abstraction. I don't think ASTs etc. enter into it - those are implementation techniques, and the only generalization we can apply to compilers is that they do implement the language definition, not how they do it (not all C compilers use ASTs). I would argue that AST is more an analogy than an implementation - I don't really care if a person dry-runs the code by reading and rewriting fragments of the source code in notepad - there is still something that represents an unevaluated function but which is itself being treated as a value - the fallback result in this model.
A possible way to implement a Haskell program would be... 1. Apply rewrite rules to evaluate everything possible without executing primitive IO actions. 2. Wait until you need to run the program. 3. Continue applying rewrite rules to evaluate everything possible, but this time executing primitive IO actions (and substituting run-time inputs into the model) as and when necessary so that the rewriting can eliminate them. The model correctly describes how the program should behave. It requires no metaphors, only a very careful person to do the re-writing and (unavoidably) to execute the primitive IO actions.
The right level of abstraction (IMHO) is the distinction between atemporality and temporality. The functional stuff is atemporal, which means among other things that evaluation is unordered (evaluation being a temporal process). Adding IO etc. capabilities to the purely functional fragment of a language infects it with temporality. But we can model temporality using order, so we can dispense with the notion of run-time and say that IO etc. stuff adds an ordered fragment to the unordered fragment. One goal of the language is then to enforce a strict correspondence between the order of events outside the program (e.g. keystrokes) and "events" inside the program (getchar). Nice way to put it. The beauty of the monad solution is not that it magically transforms non-functional stuff like IO into functional stuff, but that it exploits type discipline to make such operations *mimic* purely functional stuff in a sense - but only at the level of typing. Impure operations then have purely functional type discipline while remaining essentially non-functional. So I think of Haskell as a quasi-pure or hybrid language. C on the other hand is totally impure (except for predefined constants like '1'). For totally pure languages you have to look elsewhere, e.g. logics - there are no pure programming languages. Well - on C is impure, it depends how you look at that. If it's valid to say that your home-grown "while" loop is a function that accepts two actions as parameters, well, C has an equivalent function built into the compiler. Again you can separate the pure from the impure, and the impurity is only realized when the program is executed. The correspondence between orderings arises in different ways, but even C only demands that results are "as if" the standards-defined evaluation order were followed - partial-evaluation and other optimisations during compilation are done in whatever order the C compiler finds convenient, exploiting associativity and commutativity where those are guaranteed etc.
It's fairly easy to grasp the point by going back to Turing's original insight. The cornerstone of his ideas was not the machine but the human calculator working with pencil and paper, finite memory, etc. So to see the diff all you have to do is think about what a human does with a problem (program) written on paper. Give the human calculator a computable task - add 2+2 - and you can be confident you will receive a definite answer in a finite amount of time. Lard this with a non-computable step - add 2 + 2 + getInt - and all bets are off. Precisely my point with my bind example - in the expression "getAnIntFromTheUser >>= \i -> return (i+1)" you cannot know the value of i at compile-time, or within the realm of the atemporal. But even if at one level you consider that expression still to be evaluated within
It doesn't make Haskell and C the same thing, of course. the atemporal realm, it is still evaluated also (in translated/rewritten/whatever form) in the temporal realm - at run-time. If the user happens to enter the value 1, at some point, the expression i+1 is conceptually rewritten to 1+1 and then to 2. Arguably everything that can be evaluated at compile-time - everything in the atemporal realm - is just optimisation. That's a narrow view, and not one that I (now) agree with. The distinction is useful for understanding the program - probably even more so calling it temporal vs. atemporal because that removes the issue of how much partial evaluation will the compiler choose to do, or for that matter am I running an interpreter.
Regarding side-effects, they can be (informally) defined pretty simply: any non-computational effect caused by a computation is a side-effect. Well, pedanting, there are computation effects that we pretend are non-computational. The trivial case is using return. Another case might be an overliteral translation of...
int i = 0; int j = 0; while (i < 10) { j += i; i++; } If you literally translate this to Haskell using a hand-rolled while-loop, that condition is sensitive to effects of the loop body. The variable i must be implemented as an IORef. You have a computational effect treated as a non-computational effect. You can feed the composed IO action to unsafePerformIO to do all this in a non-IO context, and you won't violate referential transparency - but it's ugly and klunky, and something that should be in the atemporal realm has been artificially moved into the temporal realm. Practically, that's a good reason to use recursion or a fold or whatever instead of a hand-rolled while loop. In this case, idiomatic Haskell would be sum [0..9] - a clear win for Haskell, I think. Different languages have different idioms - no biggie. I'm just saying that a non-trivial computational effect may be dressed up as a non-computational effect, and most functional programmers in my experience would call each mutation of i a side-effect - or else would refuse to call the corresponding C mutations side-effects.