Re: Parser Combinator in SML -- Problem with MLton

On Wed, Jan 8, 2014 at 2:21 PM, René Neumann <[email protected]> wrote:
> for our project we are using a parser written with a homebrewn parser
> combinator library. This worked out pretty well. But the library was
> very verbose and using an ugly syntax:
>
> (bind (trim (keyword [#"f", #"o", #"r"]))
> (fn _ => bind (trim (symbol [#"{"]))
> (fn _ => bind (seq ())
> (fn sps => bind (trim (symbol [#"}"]))
> (fn _ => return (For sps))))))
>
> Therefore I changed it to use SML's ability to define new operators. For
> example "bind p q" became "p >>= q" and the idiom
> "bind p (fn _ => q)" became "p >> q" (I also changed from char lists to
> strings). So the example above becomes:
>
> $$ "for" >> $"{" >> seq() -- $"}" ==> For
>
> With this I ran into a first problem: Nontermination on compilation when
> using mutual recursive parsers, as everything is now an argument to a
> function (therefore evaluated on the spot) instead of being wrapped in a
> lambda term. But this I could solve by adding some "fn _ =>" to some
> critical spots.

By "Nontermination on compilation", I assume that you mean
non-termination when evaluating the parser combinator expression
(during execution of the program), and not non-termination when
compiling your program using parser combinators (with MLton).

> But now I noticed another BIG problem: It is slow as hell (for larger
> files). While the old ran instantanious, the new one takes several
> seconds. It also takes a lot more memory. What's worse: in PolyML it
> still _is_ instantanious.
>
> Does anyone have an idea what is going on here? Is some optimization in
> MLton backfiring? Especially where nearly everything is now evaluated
> right-away as a function argument instead of the delayed(?) evaluation
> of deeply-nested functions as before?

I don't see anything obvious with the new combinators that would imply
significantly different performance.  Of course, as you note, there
are some substantial differences in the evaluation order between the
old and the new combinators.  One thing that might be happening is
that the new combinators result in fewer functions and, thus, the
remaining functions are larger, which might impact some inlining
behavior.  Similarly, by making some functions not higher-order (e.g.,
>> rather than bind), this might impact the polyvariance optimization
(which duplicates small, higher-order functions to improve the
precision of control flow analysis).

If you have example code with the old and new combinators that
demonstrates the performance difference, then I would be happy to take
a look at them.

To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].

------------------------------------------------------------------------------
CenturyLink Cloud: The Leader in Enterprise Cloud Services.
Learn Why More Businesses Are Choosing CenturyLink Cloud For
Critical Workloads, Development Environments & Everything In Between.
Get a Quote or Start a Free Trial Today. 
http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
_______________________________________________
MLton-user mailing list
[email protected]; [email protected]
https://lists.sourceforge.net/lists/listinfo/mlton-user