Blog » "Computation" considered harmful. "Value" not so hot either.

Posted on 13 Feb 2009 15:50

The term "computation" has at least six different senses, all of which are commonly used in technical literature:

- a dynamic computing process
- the result of a computational process
- an algorithm that describes a computational process
- a formal description of an algorithm in a specific language
- a formal description of the semantics of a computational process; e.g. a lambda expression
- a dynamic process that converts a lambda expression to normal form
- a formal description of lambda conversion

One could probably come up with additional technical uses for the term. Even worse, "computation" is an ordinary word with well-understood if inexact semantics. Readers come to a technical text with a well-formed idea of what the word means, and thus no reason to think their notion is incorrect.

"Value" is even worse. It too carries multiple technical meanings in the literature, and it is even more common in ordinary language. Same for "evaluation".

These terms are ambiguous. They should be banned from technical discourse.

Usually this ambiguity is tolerable, at least for subject matter experts. But when it becomes a problem, it's a big problem. It cost me many exasperating hours of head-scratching when I decided to finally get to the bottom of monads and IO in Haskell.

The texts that flummoxed me are Moggi's paper on "notions of computation" and the standard idiom used to describe IO in Haskell.

Moggi (Notions of computation and monads, p. 3):

In particular, we identify the type A with the object of values (of type A) and obtain the object of computations (of type A) by applying an unary type-constructor T to A. We call T a notion of computation , since it abstracts away from the type of values computations may produce.

A typical example of how IO is described in Haskell (A History of Haskell: Being Lazy With Class, p. 25):

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.

Obviously this language is "good enough", since Moggi's paper was very influential, and Haskell is very successful. But both passages immediately struck me as hazy and somewhat absurd. Try as I might, I could find no way to assign a precise meaning to them. It took a lot of research and a flurry of messages on the haskell-cafe mailing list to figure out why they didn't work for me and discover what the authors (probably) meant.

Needless to say, part of the problem was the ambiguity of the terms "computation" and "value". I came to the texts thinking that a value is either a "datum" like 3 or a function like sqrt. They're just static mathematical objects, so I could not conceive of how a value could "be" a computation, or could "be performed".

The scales fell from my eyes when I came across the following passage buried in the Wikipedia article on Theory of Computation:

A computation consists of an initial lambda expression (or two if you want to separate the function and its input) plus a finite sequence of lambda terms, each deduced from the preceding term by one application of Beta reduction.

I was already familiar with the lambda calculus, but I had never thought of a lambda expression as a "computation". I still don't like it; a lambda expression is not a computation, it's a formal *representation* of a mathematical object (a *value*). Lambda conversion is a purely syntactic calculation that yields a different notational representation of the same value. The lambda calculus is a *formal model* of computation; the same computation could be represented in a different formalism. So it's just wrong to say that a computation *is* a sequence of lambda expressions.

Nonetheless, it's clear why one might think in these terms and use this language, and I think that is what's going on in the passages quoted above. My ideas of computation and value were based on the idea of a direct mapping from expression to mathematical object. Even though I was quite familiar the notions of language and metalanguage, I thought of a metalanguage as serving mainly to clarify meaning; once you understand the semantics of the language, you can disregard the metalanguage and think directly in terms of abstract semantic objects (e.g. numbers and functions.)

But in Haskell that's not good enough; to understand how lazy evaluation works, you need to keep lambda calculus (or the equivalent) in mind, because denotation has to pass through lambda expressions in various states of reduction before arriving at normal form and then semantic objects. You cannot disregard the lambda metalanguage, because the different forms lambda expressions may take constitute part of the semantic universe. Make it explicit and things become more clear. The above definition of Haskell IO becomes:

The key idea is to treat a value of type IO a as a “lambda expression” that, when converted to normal form, might perform input and output before delivering a value of type a.

Unfortunately, that's not good enough: how can a lambda expression in normal form "be performed" and "deliver" a value?

That is the subject of my next post, wherein I will discuss weaknesses in Haskell's informal metalanguage and suggest replacements for "computation", "value", and "evaluation".

Like this entry?

## Leave a comment

Somehow an acutal piece of code seems a good way to cut through the fog generated by all the hand waving.

As a Haskell n00b who is still trying to grasp monads, I found this reading quite interesting. Thank you.

ReplyOptionsHi Chis,

I'm afraid the only sample code is "getChar". My motivation is to figure out how to describe what it means in purely mathematical terms. Showing how to

useit involves monads, but that's a different topic.Some diagrams would be useful, though. I'm working on a paper with simple diagrams that I hope will clarify my points.

-gregg

ReplyOptionsI agree completely. Bring on the next post.

Paul

ReplyOptions"The key idea is to treat a value of type IO a as a “lambda expression” that, when converted to normal form, might perform input and output before delivering a value of type a."

Would "The key idea is to treat an expression of type IO a as a lambda calculus term with a normal-form value of type a, and also possible side effects of accepting input and producing output during the reduction of the term to normal form" be better? I still don't like that it really isn't the term itself that is performing IO; it's the language implementation performing it as directed by the reduction.

ReplyOptionsHi PO8 - Yes, something like that did finally dawn on me. I think a conceptual intro to Haskell absolutely must sketch out the lambda calculus-computation relation - I understood lambda

notationwhen I started, but had never put much thought into thecalculus. Realizing (thanks to people on haskell-cafe) that "computation" often (usually?) means "lambda conversion" was the turning point to understanding why the SDIOH is written the way it is. At least I think it is. ;)I've done further investigation and expect to take another crack at articulating this stuff sometime. Soare's paper on "Computation and Recursion" (see the link on my "Resources" page) is extremely enlightening.

-gregg

ReplyOptionsIf 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.

ReplyOptionsI 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.

ReplyOptionsHowever 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.

ReplyOptions## Post preview:

Close preview