A simple pattern matching tool for C++

Fellow C++ programmers,


      I am building a simple extension of C++ called Prop to be used in
tasks such as compiler construction and program transformation. While much
of the research and development is still incomplete, one small extension on
(Standard ML-like) algebraic datatypes and pattern matching is quite robust,
and can be used independently of other features.


      I invite everyone to try it (source available via anonymous
ftp://ftp.netcom.netcom:/pub/aleung/Prop), and perhaps give me some
feedback in return. All the source code is in the public domain; and if you
can actually use it to do useful work, so much the better. Documentation
is available in texinfo and dvi format.


      Currently, the system has been tested on gcc 2.5.7 and 2.5.8, under
Unix and DOS. It comes with a home-grown C++ library, and Bison and flex
are needed. Please email me for more details.


best,
allen. (aleung@netcom.com, leun7056@cs.nyu.edu)


-------------------------- A brief demo -------------------------------------


      Algebraic datatypes declarations in Prop can used to specify typed,
attributed, graph structures that are used extensively in compiler front-ends,
i.e. structures such as abstract syntax trees.


      For example, a (very simple) expression tree type EXP can be specified in
Prop with the following two type equations:


      datatype EXP = integer (int) // integer literals
                                | ident (char) // identifiers
                                | binop (BINOP, EXP, EXP) // binary operator node
      and BINOP = add | sub | mul | div // arithmetic operators
                                ;


    Now, expressions such as `1 + 2' can be represented as the labeled-tree:


          binop(add, integer(1), integer(2));


    Since EXP (and BINOP) are valid C++ types(i.e. there is no data impedence
mismatch between C++ and Prop), we may actual say things like the following
in our C++ programs:


            EXP e1 = binop(add, ident('A'), integer(1));
            EXP e2 = binop(mul, e1, e1);


    Variable `e2' now contains the dag representing the expression:
          (A + 1) * (A + 1)


    Testing and decomposing an alg-type value is accomplished using pattern
matching thru the `match' statement. The match statement can be seen as
a generalisation of `switch' and `if'. For example, an expression
evaluator can be written as a topdown tree traversal, but without having to
mess around with pointers or variant tags:


      int eval(EXP e, int env[])
      { match (e) {
                  case integer i: return i;
                  case ident v: return env[v];
                  case binop(add,a,b): return eval(a,env) + eval(b,env);
                  case binop(sub,a,b): return eval(a,env) - eval(b,env);
                  case binop(mul,a,b): return eval(a,env) * eval(b,env);
                  case binop(div,a,b): return eval(a,env) / eval(b,env);
            }
      }


    In general, datatype declarations can be mutually recursive
and patterns can be nested arbitrarily deep. The Prop preprocesser
will translate all algebraic datatype specifications into C++ class hierarchies
[before compilation] and all pattern matching into efficient tree traversal
code.


      The preprocessor is written in itself; the core algorithms(
Milner-style type inference, Wadler's pattern matching compilation, and AST
traversal) involving trees and dags are written using pattern matching.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.