Automata via Macros (2006)

cs.brown.edu

20 points·Jtsummers··6 comments

This came up in https://news.ycombinator.com/item?id=40473381

I mentioned this paper and (stupidly) didn't include a direct link to it—definitely worthy of front-page HN attention.

Another cross-ref: EdwardCoffin mentioned a (blog? chatroom?) post [1] by Guy Steele on why OO languages need tail calls; in that chat, Guy Steele references Automata via Macros.

Nice to see a confluence of ideas. :)

[1]: https://web.archive.org/web/20091206042608/http://projectfor...

The paper itself is a PDF linked from that page, but the page also links to an earlier talk that may be of interest.

Direct link to the PDF: https://cs.brown.edu/~sk/Publications/Papers/Published/sk-au...

Automata via Macros (Lisp) [pdf] - https://news.ycombinator.com/item?id=2723429 - July 2011 (3 comments)

FWIW, similar macros in Common Lisp could be implemented using TAGBODY, which would not need tail-call elimination; tags have lexical scope and dynamic, so any functions defined within the tagbody can directly GO to any tag as long as the tagbody has not exited yet.

It should be unsurprising that CL has construct(s) that allow this, given that the specification does not guarantee tail-call elimination.

In 2013, I made Common Lisp macros that provide something that looks like labels but is guaranteed tail recursive.

https://www.kylheku.com/cgit/lisp-snippets/tree/tail-recursi...

No docs or test suite, sorry. Just block comments.

A trampoline based thing, deftail, is provided for global tail calls.

In the paradigm implemented in this file, calls to tail functions are always tail calls, even if not in a tail context. If it looks like the return value of a tail call is used, too bad; that will never be reached.

Do kbd-macros in elisp for automation count?

Reply on news.ycombinator.com