TREE-META

TREE-META was instrumental in the development of NLS (oN-Line System) and was ported to many systems including the UNIVAC 1108, GE 645, SDS 940, ICL 1906A, PERQ, and UCSD p-System.

This is a complete example of a TREE-META program extracted (and untested) from the more complete (declarations, conditionals, and blocks) example in Appendix 6 of the ICL 1900 TREE-META manual. That document also has a definition of TREE-META in TREE-META in Appendix 3. This program is not only a recognizer, but also outputs the assembly language for the input. It demonstrates one of the key features of TREE-META, which is tree pattern matching. It is used on both the LHS (GET and VAL for example) and the RHS (ADD and SUB).

% This is an ALGOL-style comment delimited by %

% ====================== INPUT PARSE RULES ======================= %
.META PROG
% A program defining driving rule is required.                     %
% This PROG rule is the driver of the complete program.            %
PROG  = $STMT ;
% $ is the zero or more operator.                                  %
% PROG (the program) is defined as zero or more STMT (statements). %
STMT = .ID ':=' AEXP :STORE[2]*;
% Parse an assignment statement from the source to the tree.       %
% ':=' is a string constant, :STORE creates a STORE node,          %
% [2] defines this as having two branches i.e. STORE[ID,AEXP].     %
% * triggers a unparse of the tree, Starting with the last created %
% tree i.e. the STORE[ID,AEXP] which is emitted as output and      %
% removed from the tree.                                           %
AEXP = FACTOR $('+' FACTOR :ADD[2] / '-' FACTOR :SUB[2]);
% Here we have the recognizer for arithmetic '+' :ADD and '-' :SUB %
% tree building. Again the [2] creates a 2-branch ADD or SUB tree. %
% Unparsing is deferred until an entire statement has been parsed. %
% ADD[FACTOR,FACTOR] or SUB[FACTOR,FACTOR]                         %
FACTOR = '-' PRIME :MINUSS[1] / PRIME ;
PRIME =  .ID / .NUM / '(' AEXP ')' ?3? ;
% ?3? is a hint for error messages.                                %
% ===================== OUTPUT UNPARSE RULES ===================== %
STORE[-,-] => GET[*2] 'STORE ' *1 ;
% *1 is the left tree branch. *2 is the right                      %
% GET[*2] will generate code to load *2.                           %
% The 'STORE' string will be output                                %
% followed by left branch *1 a symbol                              %
% Whatever *2, it will be loaded by GET[*2].                       %
GET[.ID] => 'LOAD ' *1 /
[.NUM] => ' LOADI ' *1 /
[MINUSS[.NUM]] => 'LOADN ' *1:*1 /
[-]  => *1 ;
% Here an .ID or a .NUM will simply be loaded. A MINUSS node       %
% containing a .NUM will have this used, the notation *1:*1 means  %
% the first branch (a .NUM) of the first branch (MINUSS).          %
% Anything else will be passed on for node recognition             %
% The unparse rules deconstruct a tree outputing code.             %
ADD[-,-] =>  SIMP[*2] GET[*1] 'ADD' VAL[*2]  /
SIMP[*1] GET[*2] 'ADD' VAL[*1] /
GET[*1] 'STORE T+' < OUT[A] ; A<-A+1 > /
GET[*2] 'ADD T+' < A<-A-1 ; OUT[A] > ;
% Chevrons < > indicate an arithmetic operation, for example to    %
% generate an offset A relative to a base address T.               %
SUB[-,-]  => SIMP[*2] GET[*1] 'SUB' VAL[*2] /
SIMP[*1] GET[*2] 'NEGATE' % 'ADD' VAL[*1] /
GET[*2] 'STORE T+' < OUT[A] ; A<-A+1 > /
GET[*1] 'SUB T+' < A<-A-1 ; OUT[A] > ;
% A percent character in an unparse rule indicates a newline.      %
SIMP[.ID]           => .EMPTY /
[.NUM]          => .EMPTY /
[MINUSS[.NUM]]  => .EMPTY;
VAL[.ID]             => ' ' *1 /
[.NUM]            => 'I ' *1 /
[MINUSS[.NUM]]    => 'N ' *1:*1 ;
MINUSS[-]            => GET[*1] 'NEGATE' ;
.END

• NLS (computer system)
• META II

{{Reflist|refs=

Donald I. Andrews, J. F. Rulifson (1967). [https://archive.org/details/bitsavers_sriarcrulimpilerSystemForTheSDS940Dec67_3967472 Tree Meta (Working Draft): A Meta Compiler for the SDS 940], Stanford Research Institute, Menlo Park, CA. Engelbart Collection, Stanford University Archive, M 638, Box 16, Folder 3.

Bowles, K. L., 1978. A (nearly) machine independent software system for micro and mini computers. SIGMINI Newsl., 4(1), 3–7. {{doi|10.1145/1041256.1041257}}

{{cite magazine |last=Bowles |first=K. L. |year=1978 |title=UCSD Pascal: A (nearly) machine independent software system for micro and mini computers |magazine=Byte |date=May 1978 |volume=3 |number=5 |pages=46, 170–173 |url=https://archive.org/stream/byte-magazine-1978-05-rescan/1978_05_BYTE_03-05_Graphics_in_Depth#page/n47/mode/1up |via=Internet Archive}}

Hopgood, F. R. A. 1974, "TREE-META Manual", Atlas Computer Laboratory.}}

• C. Stephen Carr, David A. Luther, Sherian Erdmann, [https://apps.dtic.mil/sti/citations/AD0855122 The TREE-META Compiler-Compiler System: A Meta Compiler System for the Univac 1108 and General Electric 645], University of Utah Technical Report RADC-TR-69-83.
• {{cite book |last1=Englebart |first1=D. C . |last2=English |first2=W. K. |last3=Rulifson |first3=J . F. |date=April 1968 |title=Development of a Multidisplay, Time-shared Computer Facility and Computer-augmented Management-system Research |url=https://www.chilton-computing.org.uk/acl/pdfs/treemeta_apr68.pdf |publisher=Stanford Research Institute |place=Menlo Park, California}} Prepared for Rome Air Development Center, Griffiss Air Force Base, New York, New York. And [https://apps.dtic.mil/sti/trecms/pdf/AD0843577.pdf alternate website]. A report on Tree Meta's use in what they called Special-Purpose Languages (SPL), which are now called Domain Specific Languages (DSL), in the oN-Line System
• Donald I. Andrews, J. F. Rulifson (1967). [https://archive.org/details/bitsavers_sriarcrulimpilerSystemForTheSDS940Dec67_3967472 Tree Meta (Working Draft): A Meta Compiler for the SDS 940], Stanford Research Institute, Menlo Park, CA. Engelbart Collection, Stanford University Archive, M 638, Box 16, Folder 3.
• Andrews, Lehtman, and WHP. "Tree Meta – a metacompiler for the Augmentation Research Center". Preliminary draft, 25 March 1971.
• Alan C. Kay [http://www.mprove.de/diplom/gui/kay69.html#IV The Reactive Engine] Ph.D. thesis 1969 University of Utah. Notes that Henri Gouraud did the FLEX compiler in TREE-META on the SRI (Engelbart) SDS-940.
• [http://www.chilton-computing.org.uk/acl/literature/progress/basic_progress/q3_75.htm Atlas Computer Laboratory quarterly report] (21 November 1975), F. R. A. Hopgood documents work using TREE-META to create a compiler generating FR80 assembler output.
• [http://www.chilton-computing.org.uk/acl/literature/progress/basic_progress/q3_73.htm Atlas Computer Laboratory quarterly report] (12 October 1973), C. J. Pavelin documents (section 4.10) TREE-META being ported to the 1906A.
• TREE-META: a meta-compiler for the Interdata Model 4 by W. M. Newman. Queen Mary College, London. November 1972.

• {{GitHub|MarkMLl/TREE-META}}, coded in C, based on ICL 1900 version
• {{GitHub|jimwhite/treemeta|TREE-META compiler-compiler revival}}
• [http://www.chilton-computing.org.uk/acl/literature/manuals/tree-meta/contents.htm Manual for ICL 1900 version of TREE-META by F R A Hopgood.]
• [http://www.ifcx.org/wiki/TREEMETA.html Wiki for collecting information about TREE-META]
• [http://bitsavers.org/pdf/sri/arc/rulifson/Tree_Meta_A_Meta_Compiler_System_For_The_SDS_940_Dec67.pdf TREE META Draft Document December, 1967 at bitsavers.org]
• [http://bitsavers.org/pdf/sri/arc/rulifson/A_Tree_Meta_For_The_XDS_940_Appendix_D_Apr68.pdf TREE META Release Document April, 1968 at bitsavers.org]
• [https://web.stanford.edu/dept/SUL/library/extra4/sloan/mousesite/EngelbartPapers/B2_F8_ARNAS4.html Study for the Development of Human Intellect Augmentation Techniques, by D. C. Engelbart]

{{DEFAULTSORT:Tree-Meta}}

Category:1960s software

Category:Parser generators

Category:Programming languages

Category:Domain-specific programming languages

Category:SRI International software

Category:Articles with example code