Re: Parser combinator problem

From: Bernd Brassel <bbr_at_informatik.uni-kiel.de>
Date: Fri, 08 Feb 2008 14:38:07 +0100

Steffen Mazanek wrote:
> Hello,
>
> I have a question regarding the <*> operator (successive
> application) known from parser combinator libraries,
>
> Normally, I would define it as follows:
>
> (<*>)::Parser (res1->res2)->Parser res1->Parser res2
> (p1 <*> p2) g = (pv qv, g'')
> where
> (pv, g') = p1 g
> (qv, g'') = p2 g'
>
> However, applied to real input this results in stack overflow
> in the Münster Curry Compiler and non- or really late
> termination in PACKS.
>
> If I use this formulation, no problems occur:
>
> (p1 <*> p2) g | p1 g =:= (pv,g') & p2 g' =:= (qv, g'') = (pv qv, g'')
> where g',g'',pv,qv free
>
> However, I think, that the latter one is not as intuitive as the
> first one, so I wonder why it performs so much better.

I think it is because of the lazy matching you introduced by "where".
Try this version:

(<*>)::Parser (res1->res2)->Parser res1->Parser res2
(p1 <*> p2) g = case p1 g of
  (pv, g') -> case p2 g' of
                (qv, g'') -> (pv qv, g'')

I do not say it is elegant but it might be faster than the (=:=) solution.

Greetings
Bernd
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on Fri Feb 08 2008 - 15:58:57 CET

This archive was generated by hypermail 2.3.0 : Mon Nov 18 2019 - 07:15:06 CET