Some Ragel Ideas

[Steve Horne]

> > First off, could Ragel be extended to handle tail recursion?

> The user currently relies on
> the parse tree structure to reason about the order of execution of
> multiple actions on a single transition. Also, the parse tree is very
> important when reasoning about ambiguities. Parse tree rewrites might
> make reasoning about these things harder.

Understood.

It should be possible to do this without a parse tree rewrite, though
- think of the recursion as a 'goto' rather than as a structured loop.

Any tail call results in a special annotation in the state model. When
this machine gets inserted into the appropriately named larger
machine, the annotations are detected and result in appropriate
epsilon -like transitions being added, linking back to the larger
machines start state. At least, I think that would work.

The most obvious problem is that you don't know whether a call is
indirectly tail-recursive or not at the point when you first compile
it. Resolving that would probably be a big problem, and in any case,
allowing it would make it difficult to detect and reject non-tail
recursion (raising the possibility of state model compilation failing
to terminate).

That's why I suggested that direct recursion (where legal tail
recursion can be accurately detected from the start) would be
sufficient.

An explicit 'this is recursive' operator might resolve these issues...

x := a b ~z;
y := c d x;
z := e f y;

In the definition of x, the '~' indicates both a forward reference to
'z', and that 'x' *must* be called from 'z' (the recursion is
compulsory). But that's yet another cryptic operator ;-)

The same thing could probably be done explicitly, using labels and
epsilon transitions, of course. Just not as neat.

It's still just an idea, though. I've probably been looking at Scheme
too much recently.

> > Second, how about an equivalence assertion operator?
>
> Ragel deals strictly with constructing deterministic state machines
> (that sometimes backtrack).

Equivalence would be tested as Ragel compiles the machine, and one of
the two equivalent models would then be discarded. The idea is
redundant definition with compile-time validation, not a run-time
mechanism.

Possibly pointless, though, and more difficult than I thought because
checking whether actions match would be a problem.

IOW it's a bit daft, on reflection.

> main := m1 <-embedding_name(action_name)
> main := m1 <-embedding_name{code}

This looks pretty good to me.

I'm a little confused about user-defined embedding types, though - how
would they be used?