Nikolay,
thanks for answering! I have also tried PAKCS with sicstus and the
same problem occurred. So, I think we cannot blame MCC :-)
In a string setting error correcting parser combinators are well-studied.
For instance, the Utrecht parser combinators incorporate very
sophisticated error handling. However, I deal with graphs (the example
was just a simplification of my problem). I feel that powerful error
correction by edge insertion is in reach and I am quite excited about
this.
Previously I have simply added free variables to my graph to correct errors.
This works, but has several disadvantages:
1. the number of edges that have to be inserted must be known in advance
2. inserting more than 1 free variable results in redundant permutations, i.e.,
given a solution e1=edge1 and e2=edge2 I am not interested in the solution
e1=edge2 and e2=edge1.
Assuming edges if necessary and collecting inserted edges bottom up should
solve this permutation problem. However, without the possibility to
restrict their
number this approach is also doomed to failure.
So, help with this problem is greatly appreciated.
Regards,
Steffen
2008/2/24, Nikolay Orlyuk <virkony_at_gmail.com>:
>
>
> 2008/2/23, Nikolay Orlyuk <virkony_at_gmail.com>:
> >
> >
> >
> > 2008/2/23, Steffen Mazanek <steffen.mazanek_at_unibw.de>:
> >
> > > Hello,
> > >
> > > once again I have a problem with my parser combinators.
> > > Consider the following code:
> > >
> > > --peano numbers
> > > data Nat = Z | S Nat
> > >
> > > le::Nat->Nat->Success
> > > le Z _ = success
> > > le (S x) (S y) = le x y
> > >
> > > plus::Nat->Nat->Nat
> > > plus Z y = y
> > > plus (S x) y = S (plus x y)
> > >
> > > --given a string, a parser returns the remaining string and the
> > > --number of insertions that had been necessary to succeed
> > > type Parser = String->(String,Nat)
> > >
> > > infixl 5 <*>
> > > --sequential composition adds numbers of errors
> > > --and ensures that this number is at most 2
> > > (<*>)::Parser->Parser->Parser
> > > (p1 <*> p2) xs | p1 xs=:=(xs',errs1) & p2 xs'=:=(xs'',errs2) &
> > > errs=:=errs1 `plus` errs2 &
> > > errs `le` (S (S Z)) = (xs'',errs)
> > > where xs',errs1,xs'',errs2,errs free
> > >
> > > pSucceed xs = (xs,Z)
> > >
> > > --a particular character
> > > char::Char->Parser
> > > char c (x:xs) | c=:=x = (xs,Z)
> > > --can also be "assumed", thereby 1 error occurs
> > > char c xs = (xs,S Z)
> > >
> > > --a simple parser for the language (ab)^n
> > > abab::Parser
> > > abab = pSucceed
> > > abab = char 'a' <*> char 'b' <*> abab
> > >
> > > This code does not work properly. abab returns
> > > some results and then does not terminate anymore
> > > although the search space is restricted such that
> > > no more than two errors are allowed. Reordering of
> > > the constraints in <*> does not help.
> > >
> > > Does anybody knows what the problem is? Help is
> > > greatly appreciated.
> >
> >
> > I think your search space is extended by your restriction space :)
> > abab starts to generate and generate while receiving error on "abab = ...
> <*> pSuccess" resulting in rewriting "abab = ... <*> ( ... <*> pSuccess)",
> possibli because of `plus` which requires roll back at this moment to
> recalulate errs =:= errs1 `plus` ... `plus` errsN
>
> Sorry now I'm pretty sure thats the reason is:
> > > errs `le` S(S Z) & errs =:= errs1 `plus` errs2 where errs,errs1
> > ,errs2 free
> > {errs = Z, errs1 = Z, errs2 = Z}
> > More solutions? [Y(es)/n(o)/a(ll)] a
> > {errs = S Z, errs1 = Z, errs2 = S Z} | {errs = S Z, errs1 = S Z, errs2 =
> Z} | {errs = S (S Z), errs1 = Z, errs2 = S (S Z)} | {errs = S (S Z), errs1 =
> S Z, errs2 = S Z} | {errs = S (S Z), errs1 = S (S Z), errs2 = Z}
>
>
> errs2 is not unknown. Thats causes "p2 xs'=:=(xs'',errs2)" to lose lazyness
> earlier than xs'' (when placed after restriction on errors) and refer to p2
> too early to say that we didn't maked by errs1.
>
> Try another implementation of curry, because I think that first solution
> should look like {errs = Z, errs1 = Z, errs2 = _any }
>
> >
> >
> > Thats looks not goode, but I don't see an other way (using MCC) why it
> recurse to inifinity.
> >
> >
> > > Thanks again,
> > > Steffen
> > > _______________________________________________
> > > curry mailing list
> > > curry_at_lists.RWTH-Aachen.DE
> > > http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
> > >
> >
> >
>
>
--
Dipl.-Inform. Steffen Mazanek
Institut für Softwaretechnologie
Fakultät Informatik
Universität der Bundeswehr München
85577 Neubiberg
Tel: +49 (0)89 6004-2505
Fax: +49 (0)89 6004-4447
E-Mail: steffen.mazanek_at_unibw.de
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry
Received on So Feb 24 2008 - 17:32:21 CET