[boost] Challenge: Implement a state machine compiler as a Cpp macro using Order

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2004-09-08 05:43:32

Hi,

During the summer, I have been designing and implementing a
metalanguage for C preprocessor metaprogramming named Order. The
Order language is a *complete* high-level functional programming
language with features such as
- lexical scoping,
- first-class functions,
- anonymous functions,
- partial application of functions (currying),
- intuitive call-by-value semantics, and
- tail-recursion optimization.
The Order prelude supports, among other things,
- arithmetic on arbitrary precision natural numbers and small
  literals {0,...,100},
- sequences (with many higher-order functions),
- tuples, and
- so called token strings/sequences.
The Order interpreter, which is implemented using the C preprocessor
macro mechanism, can be used to generate arbitrary sequences of
preprocessing tokens (read: code). The intepreter also provides a
debug mode that checks for many kinds of programming errors
(syntax-errors, run-time type errors and user assertions). The Order
language has been designed to transform the feel of C preprocessor
metaprogramming from "learning lots of tricky, low-level Cpp
specific idioms" to "thinking in an intuitive high-level language".

Here is a short example of Order code that generates the complete
lyrics to the song "99 Bottles of Beer on the Wall":

#define GEN_phrase(N_bottles, N_minus_1_bottles)    \
  N_bottles of beer on the wall,                    \
  N_bottles of beer, take one down, pass it around, \
  N_minus_1_bottles of beer on the wall.

#define ORDER_PP_DEF_8bottles                          \
ORDER_PP_FN(8fn(8N,                                    \
                8cond((8greater(8N, 1),                \
                       8separate(8N, 8quote(bottles))) \
                      (8equal(8N, 1),                  \
                       8quote(1 bottle))               \
                      (8else,                          \
                       8quote(no more bottles)))))

ORDER_PP(8for_each_in_range
         (8fn(8N,
              8emit(8quote(GEN_phrase),
                    8tuple(8bottles(8N),
                           8bottles(8dec(8N))))),
          100, 1))

(The above is an extract from a completely documented example.)

There are two known caveats. First of all, the Order interpreter
requires standard C variadic macros and placemarkers, which aren't
standard C++, yet. The second caveat is that the Order interpreter
currently requires a standards conforming preprocessor. The
interpreter has been developed on the GNU CPP (3.x). Theoretically,
the interpreter should be quite portable to less conforming
preprocessors, because the interpreter is a "closed system of
macros", but I personally don't have the preprocessors nor the time,
though I would be happy to assist in such porting work by providing
information on the interpreter.

I'm currently working on the Order programming manual. I have
already written several completely documented examples for the
programming manual, which should be enough to get one started in
using the Order interpreter, but one example I'd like to have would
be a state machine compiler (SMC). Instead of implementing and
documenting a SMC myself, I'd like to challenge *you* to write such
a SMC example to be included in the forthcoming manual. Knowing
that the documentation is still unfinished, I will be happy to
assist people writing such a compiler (or some other kind of code
generator) through e-mail (I might setup a mailing list). This might
also help me to identify specific issues (e.g. sources of confusion,
important design heuristics) that need to be addressed in the
forthcoming programming manual.

If you are interested in seeing the future of C preprocessor
metaprogramming by trying out the Order intepreter and implement a
state machine compiler (or some other program generator), please
contact me at vesa_karvonen_at_hotmail.com. Note that you won't need
previous Boost.Preprocessr library experience. Learning to use the
Order interpreter should be an order of magnitude easier than
learning to use the Boost.Preprecessor library.

After I've completed the Order programming manual, I will release
the Order interpreter (independently) and submit it to Boost if
there is enough interest.

Regards,
  Vesa Karvonen

_________________________________________________________________
STOP MORE SPAM with the new MSN 8 and get 2 months FREE* 
http://join.msn.com/?page=features/junkmail