[Haskell-cafe] Recommending "Design concepts in programming languages"

[Eugene Kirpichov]

Hi.

To all those people who are in any sense interested in PL theory I'd
like to recommend the book "Design concepts in programming languages",
because I am extremely impressed with it and because I, surprisingly,
have not heard much about it.

So, the book is about various concepts encountered in various kinds of
programming languages: denotational and operational (BOS/SOS)
semantics, issues of state and control, type systems, modules,
modeling effects and compilation.
Every concept is introduced by defining the semantics of a language
that has this concept and exploring the design dimensions and issues
of this concept and language.
Concepts are gradually accumulated, and by the time you reach the
chapter on modules you've got a CBV language with records, mutable
state, polymorphic algebraic data types, a System F type system with
type inference and a hint of dependent types, abstract data types and
first-class dynamically loadable modules.

The tools used for description are of course the good old denotational
and operational semantics and typing judgements and derivation trees;
but each element of those is clearly and succintly described in text;
it happens to me all the time that I am reading a type reconstruction
algorithm and wondering, "why does this rule have that restriction?"
and it immediately turns out that in the next paragraph, the authors
focus attention on why this rule has that restriction; just like if
they were reading my thoughts.
That's why this book feels very comfortable to me: I am absolutely
sure that I won't encounter a point where I am lost and buried under
the notation; but there is also not a single boring moment.

I've been interested in functional programming and PL theory for 2-3
years already, and here's a brief list of the *new* things that I have
learned, at least:
 - What do SOS and BOS mean, and why one should care, and what
properties a SOS might posess (confluence and normalization, for
instance)
 - How many features of languages can be defined in terms of simply
desugaring, and how in some cases they can't
 - How one might use monadic style in the semantics metalanguage  to
greatly simplify the semantic rules for monadic concepts like state,
control and error handling (the authors mention the word "monad" only
once, but they use return- and bind-like operators in their semantics)
 - How powerful records are, and of what use are operators like "conceal"
 - What use is subtyping outside of OOP
 - How does one define CPS-style semantics and how such a style allows
to add state, control and errors with minimal changes
 - How small yet powerful an OOP language core can be
 - How algebraic datatypes can be very useful in a language without
static typing
 - How pattern matching can be desugared into CPS-style deconstructors
 - How many caveats are there in defining typing rules, and how a
small change in them can lead to very big changes in language
expressiveness
 - How HM type inference actually works
 - Why purity is important for certain polymorphism issues
 - What let-polymorphism means
 - What effect systems are
 - How effect reconstruction works and how it is different from type
reconstruction in nature
 - How effect inference can prove the external purity of certain
internally impure programs
That's where I finished my reading for now. The remaining looks even
more intriguing; for example, I don't (yet) know how functional
languages are compiled and how register allocation is done.

I'm afraid to sound like a salesman, but this is absolutely the
best-written technical book I have ever seen in my life, and probably
the most influential one for me, excluding probably SICP.

Here you can check out its table of contents:
http://cs.wellesley.edu/~fturbak/pubs/6821/current/contents-nov22.pdf
I was impressed with the TOC even before buying the book, but turned
out that I was greatly under-estimating it.

Well, that's it :)

-- 
Eugene Kirpichov
Web IR developer, market.yandex.ru