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: <a href="http://racket-lang.org/" rel="nofollow">http://racket-lang.org/</a>

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 <i>Journal of Functional Programming</i> in 2006.<p>There was a nice discussion of it on LtU: <a href="http://lambda-the-ultimate.org/node/569" rel="nofollow">http://lambda-the-ultimate.org/node/569</a><p>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.