Lisp source code rewriting system

Question

I would like to take Emacs Lisp code that has been macro expanded and unmacro expand it. I have asked this on the Emacs forum with no success. See: https://emacs.stackexchange.com/questions/35913/program-rewriting-systems-unexpanded-a-defmacro-given-a-list-of-macros-to-undo

However one would think that this kind of thing, S-expression transformation, is right up Lisp's alley. And defmacro is I believe available in Lisp as it is in Emacs Lisp.

So surely there are program transformation systems, or term-rewriting systems that can be adapted here.

Ideally, in certain situations such a tool would be able to work directly off the defmacro to do its pattern find and replace on. However even if I have to come up with specific search and replace patterns manually to add to the transformation system, having such a framework to work in would still be useful

Summary of results so far: Although there have been a few answers that explore interesting possibilities, right now there is nothing definitive. So I think best to leave this open. I'll summarize some of the suggestions. (I've upvoted all the answers that were in fact answers instead of commentary on the difficulty.)

First, many people suggest considered the special form of macros that do expansion only,or as Drew puts it:

macro-expansion (i.e., not expansion followed by Lisp evaluation). Macro-expansion is another way of saying reduction semantics, or rewriting.

The current front-runner to my mind is in phils post where he uses a pattern-matching facility that seems specific to Emacs: pcase. I will be exploring this and will post results of my findings. If anyone else has thoughts on this please chime in.

Drew wrote a program called FTOC whose purpose was to convert Franz Lisp to Common Lisp; googling turns up a comp.lang.lisp posting

I found a Common Lisp package called optima with fare-quasiquote. Paulo thinks however this might not be powerful enough since it doesn't handle backtracking out of the box, but might be programmed in by hand. Although the generality of backtracking might be nice, I'm not convinced I need that for the most-used situations.)

Side note: Some seem put off by the specific application causing my initial interest. (But note that in research, it is not uncommon for good solutions to get applied in ways not initially envisioned.)

So in that spirit, here are a couple of suggestions for changing the end application. A good solution for these would probably translate to a solution for Emacs Lisp. (And if if helps you to pretend I'm not interested in Emacs Lisp, that's okay with me). Instead of a decompiler for Emacs Lisp, suppose I want to write a decompiler for clojure or some Common Lisp system. Or as suggested by Sylwester's answer, suppose I would like to automatically refactor my code by taking into account the benefit of using more concise macros that exist or that have gotten improved. Recall that at one time Emacs Lisp didn't have "when" or "unless" macros.

Answer 1

30-some years ago I did something similar, using macrolet.

(Actually, I used defmacro because we had only an early implementation of Common Lisp, which did not yet have macrolet. But macrolet is the right thing to use.)

I didn't translate macro-expanded code to what it was expanded from, but the idea is pretty much the same. You will come across some different difficulties, I expect, since your translation is even farther away from one-to-one.

I wrote a translator from (what was then) Franz Lisp to Common Lisp, to help with porting lots of existing code to a Lisp+Prolog-machine project. Franz Lisp back then was only dynamically scoped, while Common Lisp is (in general) lexically scoped.

And yes, obviously there is no general way to automatically translate Lisp code (in particular), especially considering that it can generate and then evaluate other code - but even ignoring that special case. Many functions are quite similar, but there is the lexical/dynamic difference, as well as significant differences in the semantics of some seemingly similar functions.

All of that has to be understood and taken for granted from the outset, by anyone wanting to make use of the results of translation.

Still, much that is useful can be done. And if the resulting code is self-documenting, telling you what it was derived from etc., then when in the resulting context you can decide just what to do with this or that bit that might be tricky (e.g., rewrite it manually, from scratch or just tweak it). In practice, lots of code was easily converted from Franz to Common - it saved much reprogramming effort.

The translator program was written in Common Lisp. It could be used interactively as well as in batch. When used interactively it provided, in effect, a Franz Lisp interpreter on top of Common Lisp.

The program used only macro-expansion (i.e., not expansion followed by Lisp evaluation). Macro-expansion is another way of saying reduction semantics, or rewriting.

Input Franz-Lisp code was macro-expanded via function-definition mapping macros to produce Common-Lisp code. Code that was problematic for translation was flagged (in code) with a description/analysis that described the situation.

The program was called FTOC. I think you can still find it, or at least references to it, by googling (ftoc lisp). (It was the first Lisp program I wrote, and I still have fond memories of the experience. It was a good way to learn both Lisp dialects and to learn Lisp in general.)

Have fun!