Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
TREE-META
open-in-new
<h2 id="history">History</h2> <p>TREE-META was instrumental in the development of <a href="/facts/NLS_(computer_system)/SCr9PYJF">NLS</a> (oN-Line System) and was ported to many systems including the <a href="/facts/UNIVAC_1100%2f2200_series/F4JQVK33">UNIVAC 1108</a>, <a href="/facts/GE_645/dAYNeJwJ">GE 645</a>, <a href="/facts/SDS_940/sXGtoKny">SDS 940</a>, <a href="/facts/ICT_1900_series/P5wtuSGU">ICL 1906A</a>, <a href="/facts/PERQ/V68LfsKQ">PERQ</a>, and <a href="/facts/UCSD_Pascal/xxmwFYV5">UCSD p-System</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p> <h2 id="example">Example</h2> <p>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.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> 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 <a href="/facts/Assembly_language/7XuV0cla">assembly language</a> 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). </p><p>% This is an <a href="/facts/ALGOL/wlFJGNEx">ALGOL</a>-style comment delimited by % </p> % ====================== 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 <h2 id="see-also">See also</h2> <ul><li><a href="/facts/NLS_(computer_system)/SCr9PYJF">NLS (computer system)</a></li> <li><a href="/facts/META_II/eA8GbqrX">META II</a></li></ul> <ul><li>C. Stephen Carr, David A. Luther, Sherian Erdmann, <a href="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</a>, University of Utah Technical Report RADC-TR-69-83.</li> <li>Englebart, D. C .; English, W. K.; Rulifson, J . F. (April 1968). <a href="https://www.chilton-computing.org.uk/acl/pdfs/treemeta_apr68.pdf"><i>Development of a Multidisplay, Time-shared Computer Facility and Computer-augmented Management-system Research</i></a> (PDF). Menlo Park, California: <a href="/facts/Stanford_Research_Institute/flSHunVK">Stanford Research Institute</a>. Prepared for <a href="/facts/Rome_Laboratory/SXh2mCrh">Rome Air Development Center</a>, <a href="/facts/Griffiss_International_Airport/V0kjNVXF">Griffiss Air Force Base</a>, New York, New York. And <a href="https://apps.dtic.mil/sti/trecms/pdf/AD0843577.pdf">alternate website</a>. 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 <a href="/facts/NLS_(computer_system)/SCr9PYJF">oN-Line System</a></li> <li>Donald I. Andrews, <a href="/facts/Jeff_Rulifson/16J94NMy">J. F. Rulifson</a> (1967). <a href="https://archive.org/details/bitsavers_sriarcrulimpilerSystemForTheSDS940Dec67_3967472">Tree Meta (Working Draft): A Meta Compiler for the SDS 940</a>, Stanford Research Institute, Menlo Park, CA. Engelbart Collection, Stanford University Archive, M 638, Box 16, Folder 3.</li> <li>Andrews, Lehtman, and WHP. "Tree Meta – a metacompiler for the Augmentation Research Center". Preliminary draft, 25 March 1971.</li> <li>Alan C. Kay <a href="http://www.mprove.de/diplom/gui/kay69.html#IV">The Reactive Engine</a> Ph.D. thesis 1969 University of Utah. Notes that Henri Gouraud did the FLEX compiler in TREE-META on the SRI (Engelbart) SDS-940.</li> <li><a href="http://www.chilton-computing.org.uk/acl/literature/progress/basic_progress/q3_75.htm">Atlas Computer Laboratory quarterly report</a> (21 November 1975), F. R. A. Hopgood documents work using TREE-META to create a compiler generating FR80 assembler output.</li> <li><a href="http://www.chilton-computing.org.uk/acl/literature/progress/basic_progress/q3_73.htm">Atlas Computer Laboratory quarterly report</a> (12 October 1973), C. J. Pavelin documents (section 4.10) TREE-META being ported to the <a href="/facts/ICT_1900_series/P5wtuSGU">1906A</a>.</li> <li>TREE-META: a meta-compiler for the Interdata Model 4 by W. M. Newman. Queen Mary College, London. November 1972.</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="https://github.com/MarkMLl/TREE-META">TREE-META</a> on <a href="/facts/GitHub/n1hNCsc3">GitHub</a>, coded in C, based on ICL 1900 version</li> <li><a href="https://github.com/jimwhite/treemeta">TREE-META compiler-compiler revival</a> on <a href="/facts/GitHub/n1hNCsc3">GitHub</a></li> <li><a href="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.</a></li> <li><a href="http://www.ifcx.org/wiki/TREEMETA.html">Wiki for collecting information about TREE-META</a></li> <li><a href="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</a></li> <li><a href="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</a></li> <li><a href="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</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Donald I. Andrews, J. F. Rulifson (1967). 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. <a href="/wiki/Jeff_Rulifson" target="_blank">/wiki/Jeff_Rulifson</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>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 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Bowles, K. L. (May 1978). "UCSD Pascal: A (nearly) machine independent software system for micro and mini computers". Byte. Vol. 3, no. 5. pp. 46, 170–173 – via Internet Archive.{{cite magazine}}: CS1 maint: date and year (link) <a href="https://archive.org/stream/byte-magazine-1978-05-rescan/1978_05_BYTE_03-05_Graphics_in_Depth#page/n47/mode/1up" target="_blank">https://archive.org/stream/byte-magazine-1978-05-rescan/1978_05_BYTE_03-05_Graphics_in_Depth#page/n47/mode/1up</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Hopgood, F. R. A. 1974, "TREE-META Manual", Atlas Computer Laboratory. <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> </ol>