Tree Generator

The tree generator (called TreeGen) reads a set of specifications of tree like (recursive) datatypes, and creates C++ implementations of these datatypes. The specifications are as concise as in a functional language (if not more concise), while at the same time translated into efficient C++ code.

TreeGen automatically creates C++ class definitions from definitions of recursive data types. TreeGen by itself is also written in C++. The generated class definitions use automatic memory management (RAII), and start sharing subtrees when assigned or copied, while at the same time strictly preserving value semantics, which means that there will be no side effects caused by sharing. When an assignment would change a shared subtree, a unique copy is made. Memory management is done by means of reference counting.

The sources are available under the Aladdin Free Public License and can be downloaded in a single zipfile. The manual is here. In order to compile the tree generator, download the Maphoon lexer, and download the utilities. In the Makefile, set Lexing to the directory containing lexing2023, and set Util to the directory containing util. If you want to run the examples, you also need to download the tree virtual machine, and set TVM to the directory containing tvm in the Makefile.

Example: Untyped Lambda Calculus

Below is a description of untyped lambda terms in TreeGen. TreeGen will create an enum type (the selector) with three values (sel_var, sel_apply and sel_lambda, and a class called term. When the selector has value sel_var, the term has one additional field (called var) that contains a string. The # indicates that the string is stored locally (instead of on the heap). When the selector has value sel_apply, there are two additional fields called func and arg, which are both terms again. They cannot be stored locally because they are recursive fields. When the selector has value sel_lambda, there are two additional fields, body of type term, and var of type string (the variable). TreeGen will create C++ code for term, and automatically create constructors and access functions for this class.
%dir .


%define term ( sel_var )
%option var { sel_var } => # var : std::string
%option apply { sel_apply } => func : term, arg : term
%option abstr { sel_lambda } => body : term, # var : std::string

%h_incl {
#include <string>
#include "tvm/includes.h"

   std::ostream& operator << ( std::ostream& out, const term& );