Denotational semantics is hard

Conal Elliott's blog makes me feel stupid. This isn't a difficult feat; any math I don't understand will generally do the trick. But usually the feeling is misguided, because the problem is ignorance, not stupidity — when I don't understand something, it's probably because I don't know the concepts, not because I can't follow the reasoning.

Conal's blog is different. He builds everything out of simple concepts I already know, and explains his reasoning in painstaking, executable detail, and often I still don't get it. After reading a few such posts, I start to think I'm just too stupid to understand. Or, at least, that denotational semantics with partially defined values is hard enough that I can't wing it by knowing the basic concepts and figuring out the rest as I read. (When I put it that way, I don't feel so bad.)

I think part of the problem, beyond simple unfamiliarity, is that Conal's reasoning is mostly algebraic, and I'm not used to relying on that. Whenever I'm uncertain, I fall back on operational reasoning: I work through the computation and check that the results are what I expect. But this only works when I know what to expect. A typical Conal post is a tower of abstraction so high that when I try to check something, I'm not sure what the results ought to be. I have nothing to anchor my operational rope to, so when I lose my grip on the tower, I fall.

Fortunately, Edward Yang has come to the rescue with some helpful background posts on the very tools Conal uses. He walks the reader through explicit bottoms and the definedness partial ordering and fixpoints and lubs in great detail, with plenty of illustrated examples. (I like the hand-drawn diagrams. They look silly at first, but the absence of typesetting constraints probably allows them to be clearer than machine-drawn pictures would be.) It's all textbook material, and so detailed that it almost seems an insult to the reader's intelligence, but it's a textbook I haven't read, and apparently I deserve the insult. The detail provides valuable practice both at thinking in terms of these concepts and at algebraic reasoning about them, which is just what I needed. Some of Conal's posts are looking a little less mysterious now.