3 ms·
> DCGs (Definite Clause Grammar), which have the expressive power of regular expressions. DCGs have a lot more expressive power than regular expressions. They
by tom_mellior 8y ago
> DCGs (Definite Clause Grammar), which have the expressive power of regular expressions.
DCGs have a lot more expressive power than regular expressions. They are at least context-sensitive (i.e., stronger than context-free grammars as well). But off the top of my head I don't see why they wouldn't be able to capture recursively enumerable languages (i.e., the languages of completely unrestricted grammars) as well.
> Think of it as a logic search engine.
Think of it as a logic search engine embedded in a general-purpose programming language, because that's what it is.
- adimitrov 8y agoYou're right, of course. I misremembered. The trouble is that your program can become non-terminating in all but the regular case IIRC. Man it's been 10 years since I've done Prolog, so take what I say with a grain of salt.
- danieldk 8y agoEven in the regular case it can be non-terminating by using left-recursive rules. E.g. consider parsing a*: as --> as, [a]. as --> []. Prolog will recurse infinitely on the first rule.
- jmmcd 8y ago> Think of it as a logic search engine embedded in a general-purpose programming language, because that's what it is. I think this is the whole problem. The Prolog language is not great as a general-purpose language, and the "logic search engine" doesn't need be so closely identified with a particular language. Prolog should be a library, not a language, and not the almost sole representative of a programming paradigm.
- fanf2 8y agoIsn’t that kind of what miniKanren is about, embedding logic programming in conventional languages?