Between December 1st 2024 and March 4th 2025 this was a placeholder for a copy of the implementation originally at https://github.com/lugon/TREE-META, with no other content.
The original author deleted his repository, and I believed that I had accidentally deleted the copy which I had downloaded. I find, however, that I still have it.
However the files have no definite indication of authorship, no expression of copyright, and no attached license.
Despite indicating here and on the Wikipedia talk page https://en.wikipedia.org/wiki/Talk:TREE-META#Example_implementation_sources that I intended to republish the files, and attempting to contact the author via his only other project on Github (which is empty), I have received no indication of an objection.
I have applied GPL v3 to this repository, since I believe that it is the best way to protect the original author's rights. If anybody can "show cause" that this is inappropriate, please raise it as an issue.
Share and enjoy. MarkMLl.
This is an implementation of the TREE-META compiler writing system. This version is based on the version of TREE-META for the ICL 1900 described in this manual.
After executing make in the base directory you should get tmc and tmm.
tmc will use a program written in TREE-META to translate a program in the
object language. For example, if we have the description of a compiler for
language X in the file X.tm and a program written in language X that we wish
to compile in the file foo.X, then the following
$ ./tmc X.tm foo.X
will use X.tm to compile foo.X and output the result to stdout.
tmm is the TREE-META equivalent of the META II machine. It reads and executes
programs written in its assembly language. It is used to bootstrap the system.
The TREE-META compiler can be written in its own language. The file treemeta.tm
is a TREE-META program that describes a TREE-META compiler. This compiler translates
TREE-META programs into assembly language for the TREE-META machine (tmm).
The bootstrapping process is as follows (this is what the meta target of the makefile does):
$ ./tmc treemeta.tm treemeta.tm >treemeta1.tmm
$ ./tmm treemeta1.tmm treemeta.tm >treemeta2.tmm
$ cmp treemeta1.tmm treemeta2.tmm #should succeed, meaning we reached a fixed point
Note that above we "cheated" by already having a compiler to start with (tmc).
We used tmc to get a compiled version of treemeta.tm. Alternatively, we would
have to first somehow (by hand, for example) translate treemeta.tm into assembly.
There are some differences with respect to the version of TREE-META described in the manual.
The arithmetic expressions recognized are similar in syntax and precedence/associativity to the ones found in the C language. Signed and unsigned arithmetic is supported through the introduction of new operators. See the annotated grammar at grammar.txt for precise details on the syntax recognized.
C style comments (/*...*/) are automatically recognized in TREE-META programs
and in the input those programs read. They can appear anywhere whitespace can appear.
The stack used for tree-building is cleared after code generation (initiated by *).
The top tree will be processed and everything below will be lost. Generally this
is not a problem because a single tree is passed to the code generation phase.
Code generation must be initiated only from the main syntax rule (the one named
after .META).
Dumping of trees in DOT format is supported. After building a tree you can use
** instead of * to cause the generation of a DOT description of the top tree.
You can render the result with Graphviz (you can
do it online here without installing anything).
Here is an example:
$ cat expr.tm
.META PR
PR = EXPRESSION ** ;
EXPRESSION = TERM $('+' TERM :ADD[2] / '-' TERM :SUB[2]) ;
TERM = FACTOR $('*' FACTOR :MULT[2] / '/' FACTOR :DIV[2]) ;
FACTOR = '+' PRIMARY / '-' PRIMARY :MIN[1] / PRIMARY ;
PRIMARY = .ID / .NUM / '(' EXPRESSION ')' ;
ADD /=> .EMPTY ;
SUB /=> .EMPTY ;
MIN /=> .EMPTY ;
MULT /=> .EMPTY ;
DIV /=> .EMPTY ;
.END
$ cat expr.sr
X/2+Y*(Z-7)
$ ./tmc expr.tm expr.sr >expr.dot
$ dot -Tpng expr.dot -o expr.png
and the result:
- Manual for ICL 1900 version of TREE-META by F R A Hopgood
- A TREE META for the XDS 940 by J. F. Rulifson
- META II A SYNTAX-ORIENTED COMPILER WRITING LANGUAGE by Dewey Val Schorre
- The Tree-Meta Compiler-Compiler System: A Meta Compiler System for the Univac 1108 and the General Electric 645
- Jeff Rulifson discussing Tree Meta at "The Mother of All Demos" (Clip 18)
- The Mother of All Demos (1968)(Complete video) (the above clip is from around minute 53)
- The programming languages behind "the mother of all demos"
- Tree Meta in the On-Line System (NLS)
- Alan Kay about Tree Meta, here and here