3 ms·
Oh, you need to do more than "nothing special" in Prolog to get anything that is mildly useful. The very notion of constraint programming was born in Prolog com
by thesz 8y ago
Oh, you need to do more than "nothing special" in Prolog to get anything that is mildly useful. The very notion of constraint programming was born in Prolog community to handle... well, to handle constraint programming better than regular Prolog handles it.
Let me bring you another example.
In case of parser combinators over lists you can have a greedy alternative:
newtype P a = P (String -> [(String, a)] -- a parser is a function from input to remaining input and result.
P a <|> P b = P $ \s -> case a s of
[] -> b s
xs -> xs
The regular alternative is this:
P a <|> P b = P $ \s -> a s ++ b s
You can use combinators like that:
many, some :: P a -> P [a]
-- possible empty parse - returns empty list for that
many item = some item <|> pure []
-- parse head item and tail list of items and combine into a list
some item = (:) <$> item <*> many item
This greedy thing above helps greatly when you are dealing with mostly regular grammars (which are aplenty in wild) - it does not hold input for too long, it is faster for no parse situation, etc.
You put a change in a single combinator function and get wastly improved result.
In case of Prolog handling grammars you would have to put cuts all over your grammar definition, risking either loss of specification equivalence or performance.
I have more practical questions. For example, how would you design online parsers - ones that consume item by item and produce intermediate results on the go? How would you design a tree of parsers for editor to speed up reparsing after change?
These kinky Applicative and Alternative combinators let you not to worry about details when specifying the grammar. You specify it with class (pun intended - abstract getting an item into a class and you are done) and lay above the implementation which can be wholesome, streaming, with partial parses, deterministic, etc.
- YeGoblynQueenne 8y ago>> Oh, you need to do more than "nothing special" in Prolog to get anything that is mildly useful. This is really not my experience. I've been coding in Prolog for 10 years and done a bunch of useful stuff, if I say so myself (my latest baby: https://github.com/stassa/metasplain https://github.com/stassa/metasplain). Constraint (logic) programming is cool and useful, but it's not necessary. It's just a particular logic programming paradigm. Actually, although I do find it very nice and pure, in a declarative sense, I don't think I could code all my stuff in CLP. I can't say I understand your parser combination notation. The syntactic sugar of DCGs means that if you can read BNF, you can read a DCG. Simple syntax that doesn't get in your way when you're trying to do complicated things is a hallmark of Prolog in general. Cuts are also not necessary- DCGs are one kind of Prolog program where I almost never use cuts. One reason for that is that you usually want your grammars to be nondeterministic, so that you can use them as generators. DCGs basically just process lists, so it's not usually that hard to ensure a grammar doesn't overgenerate. You really don't have much use of cuts with DCGs, unless you use them to write arbitrary Prolog programs, rather than parsers (which you can do, since DCGs are syntacitc sugar for ordinary Prolog- but I generally don't). The online grammar outputting intermediary results you're describing, I think you're talking about something like this (not tested): s --> a, b. a --> [a], {writeln('Found an a')}. b --> [b], {writeln('Found a b')}. The curly braces, {}, embed arbitrary Prolog code in the body of a rule (which btw makes DCGs Turing-complete, I guess) that is executed as soon as it's found in the body of the grammar. You can go a long way with it. The "parser tree" you describe would probably need some coding around the grammars, i.e. you'd have to write special code to combine a few parsers. Or maybe not, I'm not sure because I haven't tried to do what you say. What do you use something like that for?