Lambda the Ultimate

Okay, I'm doing a self study in techniques for defining the semantics of programming languages. I have found this book( Syntax and Semantics of Programming Languages ) which seems pretty comprehensive. In particular, I was interested if there were any formalisms besides those in the book(Operational, Denotational, Domain Theory, Axiomatic, Algebraic, etc.). I was also interested in people's opinions about the strengths and weaknesses of these formalisms, and if any of them are more popular, or considered "obsolete".

Also, since I'm interested in parsing as well, I was wondering how the use of grammar formalisms to define semantics(such as Attribute Grammars, Affix Grammars, Wijngaarden grammars) is seen in comparison to these formalisms. I guess, this paper(ACM Digital Library membership required) is a good example of one way of using a grammar to define semantics. Is it considered antiquated to use grammar formalisms to do this, or is it simply not popular?

A nice application of category theory to computer science that is rather simpler than its application to semantics tends to get is the single and double pushout approach to graph transformation. Categorical pushouts allow patterns and rewrites on many kinds of structure, in particular graphs, to be specified in a simple manner. The theory can be read forwards, generalising term rewriting systems to graph rewriting systems, or backwards, specifying parsing problems for a graph grammar.

There's a shortage of good introductory material to this idea online. Offline I can recommend Tutorial introduction to the algebraic approach of graph grammars based on double and single pushouts [citeseer]. Online I suggest Practical Use of Graph Rewriting, and I welcome other suggestions.

Fresh O'Caml aims to provide the features of the Objective Caml language (with the exception of native-code compilation) together with:

• a type of names for representing object-level bindable names;
• abstraction expressions for representing object-level binding;
• pattern-matching for deconstructing abstraction values;

and some additional utility operations.

Fresh O'Caml is Mark Shinwell's sucessor to Andrew Pitts's last summer's blockbuster FreshML. It's experimental, but Tom tells me it's very cool, and I trust him. This work comes out of... no, not INRIA, enclave of O'Caml High Acolytes, but rather the University of Cambridge Computer Laboratory Theory and Semantics Group. Here are the obligatory tasty paper morsels:

• Fresh O'Caml User Manual: PostScript, PDF
• Introductory brief (PostScript)
• More in-depth ICFP paper (PDF)

More papers than you can shake a stick at on Fresh O'Caml's dad, FreshML, are also available.
Finally, there's a mailing list you can join for information, updates, and discussion about FreshML and Fresh O'Caml