Re: [Caml-list] Incremental, undoable parsing in OCaml as the general parser inversion

[skaller <skaller@users.sourceforge.net>]

On Thu, 2007-07-05 at 01:13 -0700, oleg@pobox.com wrote:
> Paul Snively wrote:
> > I've attempted to rewrite this in terms of your  
> > monadic version of delimited continuations, as included in the  
> > pa_monad syntax extension distribution.
> 
> I'm afraid that cannot be done. That is, short of re-writing
> make_lexer and all other library functions in the monadic style. 

That was my original point. You wrote:

"This message is to show that the incremental parsing in OCaml is a
solved problem -- essentially for any parser. Moreover, the procedure
to convert from a regular parser to an incremental one is independent
of the parser implementation."

But this isn't so, because you confuse the meaning of 'parser'
and 'implementation' to a programmer, as compared to a
theoretician. A programmer thinks an 'implementation' is
concrete syntax .. i.e. an actual text file.. a theoretician's
'concrete syntax' is still an abstract encoding.

What you've shown is that it is possible to *manually*
control invert a given algorithm.

Now you should note what Felix does. It *mechanically*
control inverts any algorithm encoded with Felix procedures.
And I mean *concrete syntax* here :)

That translation is universal and generated code is expensive
to run due to many closures,  but the cost is reduced by the
optimiser so that code not requiring control inversion reduces
to plain old subroutines.

[Literally, procedure calls are converted to yielding
the procedure to call, etc .. it's continuation passing]

I am guessing my technique differs from what you describe
in that the 'continuations' aren't statically delimited.

That's a serious drawback of the current Felix implementation.
The effect is that the inverted code only works with channels
at the top level, that is, not inside a functional closure,
because the latter use the machine stack and do cannot
yield to the driver (scheduler).

BTW: procedural code is just 'code written in a monadic
style'. Every imperative programming language is just a 
purely functional one with monads..

This shows that monads have all the same problems as
ordinary imperative code if you over use them
(as of course is common practice in low level procedural
programming languages).


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net