'App' is a preprocessor for C++ that accepts as input arbitrary C++ code that may contain embedded constructs for specifying algebraic data types and associated pattern matching operations, and produces as output the same code with all such constructs translated to normal C++. 'Applib' is the associated runtime library that supports the core run time requirements of the translated code, and which provides additional utilities.
The notion of algebraic types comes from the world of functional programming, where such types are relied on as a way to reason about program semantics. For example in the functional language Haskell one can define an algebraic parametric type for trees with arbitrary labels as follows.
data Tree x = Tip x | Node x (Tree x) (Tree x)
This type is parametric because the type of tree labels x is a parameter. To count the number of tree tips one can define a pattern matching function.
ntips (Tip _) = 1 ntips (Node _ left right) = ntips left + ntips right
The ntips function is defined over all such trees because (by examination) it is defined over all structures of such trees. This is an example of definition by structural induction, in which simple structures (e.g. Tip) form base cases, and compound structures (e.g. Node) form inductive cases.
More pragmatically, algebraic types can be considered forms of discriminated unions. The cases of Tree (i.e. Tip and Node) can be considered injectors of discreet types and the whole type (i.e. Tree) can be considered a union of such types together with the means for discriminating at run time between the individual cases in order to project the constituents of the cases.
More formally, algebraic types are sums of products, and pattern matching is a more or less formal way of doing casing.
The casing style is certainly not limited to the functional world. It is straightforward enough to do pretty much the same thing in C++ (notwithstanding the apparent lack of formality).
template <class X>
class Tree {
public:
virtual ~Tree() {}
};
template <class X>
class Tip : public Tree<X> {
public:
X label;
Tip(X x) : label(x) {}
};
template <class X>
class Node : public Tree<X> {
public:
X label;
Tree<X>* left;
Tree<X>* right;
Node(X x, Tree<X>* l, Tree<X>* r) : label(x), left(l), right(r) {}
};
template <class X>
int ntips(Tree<X>* t) {
if (dynamic_cast<Tip<X>*>(t))
return 1;
else if (Node<X>* u = dynamic_cast<Node<X>*>(t))
return ntips(u->left) + ntips(u->right);
else
return 0;
}
void test_0() {
Tree<int>* t = new Node<int>(1, new Tip<int>(2), new Tip<int>(3));
cout << ntips(t) << endl;
}
Naturally there are some linguistic differences such as the use of pointers and explicit dynamic casting & allocation, but the basic idea is the same. However the casing style as illustrated above can itself be a source of problems especially for less trivial examples: What if a dynamic cast isn't done just so? What if the underlying case structure changes, and how does one know if all such changes are accounted for?
In a functional language like Haskell, there are no dynamic_casts or the like, at least not at the linguistic level. And if the underlying case structure changes, it is technically not difficult for a functional language compiler to let the programmer know about it, because all relevant cases are statically related by the algebraic typing system. All the compiler really has to do is a simple case analysis of related patterns, and check that all relevant cases are at least mentioned, as pretty much all that is needed is to make sure the programmer is at least aware of changes to the underlying structure as defined by the type equations.
It would appear then that at least theoretically, functional languages such as Haskell simply do not suffer from the difficulties that the casing style tends to impose on most other kinds of languages including C++. This is where app comes in. What app essentially does is provide for C++ pretty much the same capabilities that functional languages have regarding algebraic types. In a sense app can be viewed as bringing C++ closer to the functional programming world, although perhaps just as well app can be viewed as directly supporting certain kinds of visitor-style patterns in C++, insofar as algebraic types can be viewed as supporting such patterns. In any event, here is the tree example, done the app way.
namespace alpha
{
$data Tree<class X>
= Tip(X label)
| Node(X label, Tree<X> left, Tree<X> right)
;
} // namespace alpha
using namespace alpha;
template <class X>
int ntips(Tree<X> t) {
int result;
$match (t) {
(Tip<X>(_)) => {result = 1;}
(Node<X>(_, left, right)) => {result = ntips(left) + ntips(right);}
}
return result;
}
void test_1() {
Tree<int> t = Node<int>(1, Tip<int>(2), Tip<int>(3));
cout << ntips(t) << endl;
}
The output from app for this example follows verbatim (option --pretty). Notice that the generated code does not use pointers directly. The handle/body idiom with reference counting is employed instead; class 'Top' forms the base class of the handle hierarchy, and class 'Top__' the base class of the body hierarchy. It should also be noted that in app terminology "base" is typically used when referring to relatively simple kinds of algebraic types. Context should suffice to distinguish between the senses.
namespace alpha
{
template<class X>
class Tree : public Top {
public:
Tree() : Top() {}
Tree(Top__* handle, Copy docopy = nocopy) : Top(handle, docopy) {}
};
template<class X>
class Tip__ : public Top__ {
X label_;
public:
const char* raw_type() const {return "Tip";}
Tip__(X label) :
label_(label)
{}
X label() {return label_;}
void write(ostream& _os_) {
show_begin(_os_, form_using_rtti() ? typeid(*this).name() : "Tip");
_os_ << label();
show_end(_os_);
}
};
template<class X>
class Tip : public Tree<X> {
public:
Tip(X label) :
Tree<X>(new Tip__<X>(label))
{}
Tip(Top__* handle, Copy docopy = copyok) :
Tree<X>(handle, docopy)
{}
Tip__<X>* operator->() const {
return static_cast<Tip__<X>*>(handle);
}
Tip__<X>& operator*() const {
return static_cast<Tip__<X>&>(*handle);
}
static Tip<X> nil() {return Tip<X>(0, nocopy);}
};
template<class X>
class Node__ : public Top__ {
X label_;
Tree<X> left_;
Tree<X> right_;
public:
const char* raw_type() const {return "Node";}
Node__(X label, Tree<X> left, Tree<X> right) :
label_(label),
left_(left),
right_(right)
{}
X label() {return label_;}
Tree<X> left() {return left_;}
Tree<X> right() {return right_;}
void write(ostream& _os_) {
show_begin(_os_, form_using_rtti() ? typeid(*this).name() : "Node");
_os_ << label();
show_delim(_os_);
_os_ << left();
show_delim(_os_);
_os_ << right();
show_end(_os_);
}
};
template<class X>
class Node : public Tree<X> {
public:
Node(X label, Tree<X> left, Tree<X> right) :
Tree<X>(new Node__<X>(label, left, right))
{}
Node(Top__* handle, Copy docopy = copyok) :
Tree<X>(handle, docopy)
{}
Node__<X>* operator->() const {
return static_cast<Node__<X>*>(handle);
}
Node__<X>& operator*() const {
return static_cast<Node__<X>&>(*handle);
}
static Node<X> nil() {return Node<X>(0, nocopy);}
};
} // namespace alpha
using namespace alpha;
template <class X>
int ntips(Tree<X> t) {
int result;
//$$ begin $match
{ bool _alpha_fail = true;
Tree<X> _alpha_norm_1 = t;
if (dynamic_cast<Tip__<X> *>(_alpha_norm_1())) {
Tip<X> _alpha_cast_1(_alpha_norm_1());
_alpha_fail = false;
//$$ begin user statement code
result = 1;
//$$ end user statement code
}
if (_alpha_fail && dynamic_cast<Node__<X> *>(_alpha_norm_1())) {
Node<X> _alpha_cast_1(_alpha_norm_1());
Tree<X> left = _alpha_cast_1->left();
Tree<X> right = _alpha_cast_1->right();
_alpha_fail = false;
//$$ begin user statement code
result = ntips(left) + ntips(right);
//$$ end user statement code
}
if (_alpha_fail) escape("match failed");
}
//$$ end $match
return result;
}
void test_1() {
Tree<int> t = Node<int>(1, Tip<int>(2), Tip<int>(3));
cout << ntips(t) << endl;
}