Lambda the Ultimate

Tom 2.6 was just released, and includes a whole lot of interesting things.

Among them, there are :
- the introduction of constraints in the matching algorithm, improving the readability of programs
- strategies now work with zero efforts on any java data structure, all you have to do is provide the tom mapping, which you already did since you use %match
- a much better integration of the antlr parser generator
- term graph rewriting

have fun !

The complete announce:
-------------------------------------------------------------------------
Tom 2.6 announcement

It is our great privilege and pleasure to announce the availability of
Tom version 2.6 .

This release continues our work on the integration of pattern matching
and rule based programming facilities into Java and C.

Tom is a pattern matching compiler developed at INRIA. It is
particularly well-suited for programming various transformations on
trees/terms and XML based documents. Its design follows our research on
the semantics and the efficient compilation of rule based languages.

Many applications have been developed in Tom, both in academia and
industry. Among them, let us mention:
- the Tom compiler itself
- languages semantics, interpreters and program transformation tools
- a generator of canonical abstract syntax trees (Gom)
- a proof assistant for supernatural deduction
- a compiler algorithm for anti-pattern matching and disunification

Tom is a complex compiler which adds powerful constructs to Java and C:
rewrite rules, strategies, non linear syntactic matching, associative
matching with neutral element (a.k.a. list-matching), XML based pattern
matching, string matching, and equational rewriting.
This offers the possibility to analyze and transform any kind of
data-structure. Tom can be used for large scale developments and
applications. It comes with a detailed documentation, as well as with
programming and debugging support.

This new release contains many improvements and new features:

- new alternative syntax for '%match', based on atomic constraints
that can be combined with '&&' and '||' operators. This gives a
higher expressiveness and conciseness. Works also in '%strategy'

- hand-written strategies became easier to write. No more 'Forward'
class is needed.

- strategy support for hand-written mappings

- new tool based on ANTLR 3 for implementing parsers that
directly output Gom terms: GomAntlrAdapter.

- term-graph rewriting support in Gom

- Gom's lists now implement the interface Collection. Consequently,
Java's classic iteration techniques can be employed.

- several speed-ups of the compilation process as well as for the
generated code.

- a lot of new features for the Eclipse plug-in, including the
availability of all the functionalities of the Java editor for
".t" files ( a complete list is available on the plug-in page:
http://tom.loria.fr/plugin.php )

Tom is available, in open source (GPL/BSD License), from the web page:

http://tom.loria.fr/

Best regards,
Tom's development team

So as I understand it, describing a language semantics in terms of execution by the SECD machine, is an acceptable presentation of small-step operational semantics. What I don't know is whether small-step operation semantics are still in fashion or considered outdated. One of the practical advantages of small-step operational semantics presented in this manner, seems to me at least, that it facilitates the verification of the language semantics, and for other people to create their own implementations. Is this the common wisdom?

Well given that, I have to wonder why not describe the small-step operational semantics using an even simpler stack machine, one without registers or environment (instead allowing first-class functions on the stack). That seems to me to offer some advantages over the SECD machine. For example, we obviously don't have to worry about environment and registers, and we also don't need to perform defunctionalization.

I am asking, because I want to formally present the semantics (without regard for types) of a simple imperative OO language with some functional features.

Some of my reading material concerning operational semantics:

• A Rational Deconstruction of Landin's SECD Machine by Olivier Danvy
• Syntax and Semantics of Programming Languages by Ken Slonneger, specifically Chapter 8
• Lecture Notes on Semantics of Programming Languages by Andrew Pitts

Please feel free to add more to my list.