[Haskell-cafe] Frisby (PEG parser) unbiased-choice thoughts
Isaac Dupree
isaacdupree at charter.net
Sat Jul 14 14:21:02 EDT 2007
since I don't like unexpected behavior happening when something not
intended to happen, happens, and it's better documentation (a free
assertion) -- I find myself making Haskell comments to specify whether
the left-biasedness of each (//) is important, various places in my own
code that uses frisby. We examine how could such an operator could
behave, having similar effect to (//) but symmetric (call it (=|=);
(p1 =|= p2) should be equivalent to (p2 =|= p1) )...
I will use original frisby syntax (see
<http://repetae.net/john/computer/frisby/>), not the
Applicative/Alternative instances I added, to be clearer. "Thought 1"
could make a different but valid Alternative instance, after all.
Prototype implementations are given... so it's clearly still O(1).
thought 1:
(=|=) :: P s a -> P s a -> P s a
a =|= b = ((peek a <> peek b) `onlyIf` (error "BUG in (=|=) user"))
// (a // b)
thought 2:
(=|=) :: Eq a => P s a -> P s a -> P s a
a =|= b = ((peek a <> peek b) `onlyIf` (check))
// (a // b)
where
check (ra,rb) = if ra /= rb then error "BUG in (=|=) user" else False
--This one "unnecessarily" requires Eq just to check a programmer's
--assertion of equivalence, but allows overlaps that give the same
--result. On second thought... 'a' and 'b' could consume different
--amounts of input and produce the same result, so this is buggy.
thought 3:
symmetricDifference :: P s a -> P s a -> P s a
a `symmetricDifference` b =
(doesNotMatch a ->> b) // (doesNotMatch b ->> a)
feeding arbitrary inputs using quickcheck should hopefully catch
incorrect usages of the (=|=)s that can be used in error, since it is
well known that one cannot systematically determine for all PEG parsers
whether the assertion will hold true (it must be at least as difficult
as determining whether any two are exactly equivalent). HOWEVER it
would also be interesting to see a similar system that could be
restricted enough that one could show the correctness of such a
non-intersection claim (I wonder how frequently such claims are fairly
trivial to prove correct, anyway)
Isaac
More information about the Haskell-Cafe
mailing list