A general-purpose macrogenerator
code-golf interpreter
Briefly: Implement Christopher Strachey's “General-purpose macrogenerator”.
Background
In section 1.2 (Historical References) of the manual for GNU M4, an early macro processor is mentioned:
An important precursor of m4 was GPM; see C. Strachey, “A general purpose macrogenerator”, Computer Journal 8, 3 (1965), 225–41, http://dx.doi.org/10.1093/comjnl/8.3.225. GPM is also succinctly described in David Gries’s book Compiler Construction for Digital Computers, Wiley (1971). Strachey was a brilliant programmer: GPM fit into 250 machine instructions!
Your goal is to implement GPM, as described below, in the fewest bytes of source code possible.
Overview
The version of GPM in this challenge is very close to that described in the original paper.
GPM operates quite like m4, but there are some important differences. I assume that you already have an idea of what a macro is in general.
Input to GPM is a sequence of ASCII characters, which should be copied to the output verbatim, except that macros calls are expanded. Macro calls consist of a dollar sign $ followed by a name, followed by a comma ,, followed by a comma-separated list of arguments, followed by a semicolon ;. Here is an example of a macro call:
$macro,x,yy,z;
In this case the name is macro, and there are three arguments (x, yy, and z). A macro call with no arguments is the name preceded by $ and followed by ;, as in $noarguments;.
Macro names consist of letters and/or digits. (So 1232 is a valid name.) There are no limitations on the length of a name.
When a macro call is encountered, it is replaced by the text currently associated with the name. (How text is associated with a name will be explained later; it is done by a macro named DEF.) This replacement text is also a sequence of characters suitable for input to GPM; in particular, it may itself include other macro calls. However, occurrences of ~1, ~2, ~3, etc. are replaced by the text of the corresponding argument given. The string ~0 is replaced by the macro's name.
Macro calls can be arguments, as in $macroA,$macroB,$macroC;,$macroD;;;. Dollar signs and semicolons must be balanced. Even the macro name in a macro call can be a macro call, so that $$x;; is valid.
The name and arguments are evaluated from left to right before replacement begins. It is not a problem if more arguments are given than are used by the replacement text.
After the call has been replaced, the resulting text is re-examined, in order to allow further expansion.
For example, suppose that macro names a macro whose replacement text is ~1~1~2~2~3~3. Then the call given previously, namely $macro,x,yy,z;, would be replaced by xxyyyyzz.
Outside of a replacement text, the meaning of ~ followed by a digit is undefined. Your program need support only nine arguments, numbered ~1 to ~9.
The usual treatment of a string of characters can be prevented by using the “quotes” < and >: Characters between < and > are not examined for macro calls. The evaluation of a quoted string is the string between the quotes but without the quotes. Quotes can nest.
Quoted text need not be valid input. Thus <$> and <;> are OK. It is not possible to quote a quoting character: <<> and <>> are invalid. However, <<><>> is fine; it evaluates to <><>.
Here are some examples, mostly taken from Strachey's paper. Assume that the following definitions are active:
| Name |
Replacement text |
A |
A~1A |
B |
B$A,X~1X;B |
APA |
P~1~1P |
Then we will have
| Input |
output |
$A,C; |
ACA |
$A,ACA; or $A,$A,C;; |
AACAA |
$A,XDX; |
AXDXA |
$B,D; |
BAXDXAB |
$A,P; |
APA |
$$A,P;,Y; |
PYYP |
Q<$A,C;>R |
Q$A,C;R |
$A,<$A,X;>; |
A$A,X;A |
Q<$>R<;> |
Q$R; |
Q<<$A,C;>>R |
Q<$A,C;>R |
Macro definitions
GPM maintains an environment of macro definitions, which is an ordered list of pairings of names and replacement texts. Entries are added and removed in a last-in-first-out manner. When it is time to expand a macro, the name is searched for in the environment, beginning with the most-recently-added definition and moving backwards. The first matching definition is the one used.
After an expansion has finished, the environment returns to the state it was in before the expansion begun. Thus any macros defined in the process are forgotten.
The built-in macro DEF can be used to modify the environment. It takes two arguments; the first is the name to define, and the second is the definition. The DEF macro is treated just as any macro is, except that the first argument, the name, is not evaluated. The effect of DEF is always to add a new definition to the environment, rather than to change an existing one.
Here are some definitions for simple arithmetic:
$DEF,Suc,<$1,2,3,4,5,6,7,8,9,10,$DEF,1,<~>~1;;>;
$DEF,Successor,<$~2,$DEF,~2,~1<,$Suc,>~2<;>;
$DEF,9,<$Suc,>~1<;,0>;;>;
$DEF,Sum,<$S,~1,~2,0,$DEF,S,
<$~3,$DEF,~3,<$S,>$Successor,~1,~2;
<,>$Suc,~3;<;>;
$DEF,>~3<,~1<,>~2;;>;;>;
The output of $Sum,3,4,2; is the sum of \$34\$ and \$2\$, expressed as 3,6.
Another basic macro, VAL, takes a name (which is not evaluated) as an argument and returns its unevaluated definition. Thus after defining $DEF,A,A;, $VAL,A; gives A (without evaluating it and getting into an infinite loop).
To change a definition, instead of (possibly temporarily) overriding it, the UPDATE macro is available. It is used like DEF, but changes the currently active definition of the name and does not add an entry. There must already be a definition before calling UPDATE.
The expansion of DEF and UPDATE is empty.
No limitations are placed on the number of characters making up a macro's replacement text. In the original program, the size of the new replacement text after an UPDATE call was restricted to being at most as long as the previous definition. You need not implement this restriction, but you also need not remove it.
Implementation
Your program can get input from a file, from standard input, or from a string. Output can be to a file, to standard output, or to a string.
Whitespace (ASCII space, horizontal tab, vertical tab, line feed, carriage return) should be ignored but copied to the output. Thus $ n a m e; is the same as $name. Strachey's implementation most likely did not differentiate between uppercase and lowercase letters, so you do not have to. The test does not depend on case differences.
Strachey's paper includes a detailed discussion of GPL's implementation, which you might find useful/interesting. It is not particularly easy to read. I don't think the 250-instruction machine code program has survived anywhere.
User tociyuki on GitHub has implemented the algorithm in Ruby and published it as a Gist, although UPDATE is not supported. I have not tested it.
Previously I have remarked that name length and replacement text size are not limited. This was true of Strachey's program but only to a certain extent. He enforced a limit on the total number of characters stored, but the length of any name or text was not fixed. You can do this as well, but your program must support storing at least 10000 characters, as he suggested.
Your program should allow at least 100 levels of expansion.
Don't bother with handling erroneous input; if given something invalid, your program can do anything.
Test case
Input:
$DEF,Suc,<$1,2,3,4,5,6,7,8,9,10,$DEF,1,<~>~1;;>;
$DEF,Successor,<$~2,$DEF,~2,~1<,$Suc,>~2<;>;
$DEF,9,<$Suc,>~1<;,0>;;>;
$DEF,Sum,<$S,~1,~2,0,$DEF,S,
<$~3,$DEF,~3,<$S,>$Successor,~1,~2;
<,>$Suc,~3;<;>;
$DEF,>~3<,~1<,>~2;;>;;>;
$DEF,A,<A~1A>; /* First line of output
$DEF,B,<B$A,X~1X;B>;
$DEF,APA,<P~1~1P>;
This should be the second line of output.
The expansion of Suc is $VAL,Suc;.
And I wrote that by saying: <The expansion of Suc is $VAL,Suc;>.
<<<Quote quote quote>>>
$A,C;
$A,ACA; = $A,$A,C;;
$A,XDX;
$B,D;
$A,P;
$$A,P;,Y;
Q<$A,C;>R
$A,<$A,X;>;
Q<$>R<;>
Q<<$A,C;>>R
Q < < $ A , C ; > > R */
#include <<stdio.h>>
int main(void)
{
puts("Unaffected by the processor.");
printf("Here's a sum: 34+2=%d%d.\n",$Sum,3,4,2;);
}
Expected output:
/* First line of output
This should be the second line of output.
The expansion of Suc is $1,2,3,4,5,6,7,8,9,10,$DEF,1,<~>~1;;.
And I wrote that by saying: The expansion of Suc is $VAL,Suc;.
<<Quote quote quote>>
ACA
AACAA = AACAA
AXDXA
BAXDXAB
APA
PYYP
Q$A,C;R
A$A,X;A
Q$R;
Q<$A,C;>R
Q<$A,C;>R */
#include <stdio.h>
int main(void)
{
puts("Unaffected by the processor.");
printf("Here's a sum: 34+2=%d%d.\n",3,6);
}
I believe that the computer for which Strachey's machine-code program was written used forty-eight-bit words (at least its predecessor did), so the mark to beat is 1500 bytes.
