Re: Parser Combinator in SML -- Problem with MLton

Am 10.01.2014 16:48, schrieb Matthew Fluet:
> 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).

Yes, you are right. My misconception of the 'nontermination on
compilation' came from my development with PolyML (for interactive
testing), where it indeed hang on 'use'ing certain files with only
parser definitions and no applications in it.

Interestingly, I noted that the following works in PolyML, while MLton
hangs on evaluation (full file including Basic.sml is attached):

(* consumes usage of an operator, which may be existant zero or more times

nxt is the next operator in the hiearchy *)
fun sop opStr opF nxt =
                nxt ()
            >>| list (trim (item opStr) >> nxt ())
            =|> foldl opF

fun expr _ = exprAdd ()
and exprAdd _ = sop #"+" (op +) exprMul
and exprMul _ = sop #"*" (op *) exprBase
and exprBase _ = "expression expected" !!
            trim (item #"(") >> expr() -- trim (item #")")
         || trim number

val _ = expr(); (* here MLton hangs *)

To make it work in MLton, I need to change the middle line of exprBase into:

trim (item #"(") >>= (fn _ => expr() -- trim (item #")"))

My first wild guess would be: PolyML and MLton differ in when to
evaluate 'sop'.

> 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.

I'll try to write something up that does not include the full-blown parser.

Thanks,
René
-- 
René Neumann

Institut für Informatik (I7)
Technische Universität München
Boltzmannstr. 3
85748 Garching b. München

Tel: +49-89-289-17232
Office: MI 03.11.055

------------------------------------------------------------------------------
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