Automata via Macros (Lisp) [pdf]

For those interested, Scheme is now Racket and there may be other changes brought on by time. The list is quite responsive with a very satisfactory STN ratio so use it as a resource as this looks like an interesting project. See: http://racket-lang.org/

This is an old paper: you should give the year in the title, by appending "(2005)" - it was circulated as a preprint in 2005 and published in the Journal of Functional Programming in 2006.

There was a nice discussion of it on LtU: http://lambda-the-ultimate.org/node/569

The discussion focussed on whether it was good to do this internally using macros, rather than use an external code-generating tool.

As this is a DFA, I wonder if it is possible to create a NFA via macros. One way would obviously be to turn the NFA into the DFA at compile-time, and then apply the DFA-macro, but that may possibly kill efficiency. Is it possible to do without creating infinite loops because of ϵ-transitions, and with tail calls? I have my doubts, but that would be amazing.