7 ms·

Prolog is brilliantly useful for text processing and reasoning about strings, mostly due to its built-in grammar formalism called Definite Clause Grammars (DCGs

by triska 4y ago

Prolog is brilliantly useful for text processing and reasoning about strings, mostly due to its built-in grammar formalism called Definite Clause Grammars (DCGs). In fact, Prolog originates from Q-systems which were specifically designed to process language via grammar rules: https://en.wikipedia.org/wiki/Q-systems https://en.wikipedia.org/wiki/Q-systems The "Q" stands for Québec, where Alain Colmerauer developed this formalism which eventually led to Prolog. A recently released documentary talks a bit about these developments: https://youtu.be/74Ig_QKndvE https://youtu.be/74Ig_QKndvE It is interesting that the very first Prolog systems, Prolog 0 and Marseille Prolog, represented strings as lists of characters, then the Edinburgh tradition used lists of codes (in the implementation defined encoding), and all Prolog systems that have become available in the last 5 years (Scryer Prolog, Tau Prolog, Trealla Prolog and ichiban/prolog) are again using lists of characters to make string processing as convenient and readable as originally intended. For example, we can use definite clause grammars in Scryer Prolog to find occurrences of the same character twice in immediate succession in a string: ?- phrase((...,[C,C],...), "Hello, world!"). C = l ; false. In this string, the character 'l' is the only such letter.

funstuff007 4y ago
> https://youtu.be/74Ig_QKndvE https://youtu.be/74Ig_QKndvE Bon jour, the doc is en Francais. However, it does have legit subtitles (i.e. not auto-generated).
- historia_novae 4y ago
  Thanks, that was an interesting watch.
YeGoblynQueenne 4y ago
To be more precise, most Prologs before the last 5 years have built-in predicates that break _atoms_ up into either character codes, or characters. "String" as a datatype is the novelty of the new generation of Prologs. For instance, here's Sicstus | ?- atom_codes('abcd', Cs). Cs = [97,98,99,100] ? ; no | ?- atom_chars('abcd', Cs). Cs = [a,b,c,d] ? ; no | ?- Personally, I'm kind of ambivalent about this new direction. "String" is a programming language concept, but not a FOL concept. "Atom" is a FOL concept- but Prolog mangles the clean and tidy FOL (and Logic Programming) nomenclature and calls "atom" everything that should really be called a _constant_, and calls what should really be called an "atom", a "term". Then it's all downhill from there. The ideal for me would be to redress the wrong of confusing terminological swaps in Prolog jargon (atom--> constant, term--> bloody everything, predicate--> program, functor--> symbol, etc) and leave the details of the implementation (whether to represent constants as lists of characters or codes, and whether to define built-ins that operate on them) to the implementor. For me, Prolog's Logic Programming roots are the only thing that makes sense and helps understand Prolog. The turn towards programming language semantics and sometimes database semantics, has only served to make a mess of things. I blame it for the notorious difficulty that most programmers face in trying to pick up Prolog, which is seriously incommensurate to the brilliant simplicity of FOL and LP syntax and semantics.
- dallasg3 4y ago
  I didn't know FOL stood for First-Order Logic.
  - YeGoblynQueenne 4y ago
    Oh, sorry, you're absolutely right. I should have explained the acronym before using it.
- jhgb 4y ago
  > "Atom" is a FOL concept- but Prolog mangles the clean and tidy FOL (and Logic Programming) nomenclature and calls "atom" everything that should really be called a _constant_, and calls what should really be called an "atom", a "term". It almost seems like they got all this confusion from badly copying Lisp. What you refer to above is clearly ancient (pre-Common) Lisp's EXPLODE and IMPLODE operators (https://www.cs.cmu.edu/Groups/AI/html/faqs/lang/lisp/part2/faq-doc-3.html https://www.cs.cmu.edu/Groups/AI/html/faqs/lang/lisp/part2/f...). Of course Lisp's symbols are Prolog's atoms, and Lisp's atoms are Prolog's terms.
  - YeGoblynQueenne 4y ago
    Well I confess I don't know LISP nearly as well as Prolog, but they were both languages that came out of a certain tradition of research in FOL and how to calculate it with computers. There was bound to be some overlap. I remember noticing the thing about LISP atoms and symbols etc. and I thought that's probably it.
- triska 4y ago
  In SICStus Prolog, the query I showed yields C = 108 by default, because "Hello, world!" is interpreted as the list of character codes [72,101,108,...]. In contrast, in all the recent systems I mentioned, the double-quoted string "Hello, world!" is interpreted as the list of atoms of length one ['H',e,l,l,o,...]. This is preferable because it is more readable, and also because reasoning about such atoms in Prolog programs does not depend on any system-specific character encoding. In all ISO conforming systems, we can switch between these two interpretations of double-quoted strings by setting the Prolog flag double_quotes to codes and chars, respectively. The interesting phenomenon I mentioned is that both the earliest and the most recent Prolog systems acted as if this flag (which was not available yet in the first Prolog systems) was set to chars, interrupted by a number of years where it was set to a different default value in the Edinburgh tradition of Prolog systems. It is interesting because the newest Prolog systems follow the Marseille tradition in this respect, which precedes the Edinburgh tradition. Prolog does not have a native "string" type, neither SICStus nor the other systems I mentioned have it, because such a type does not fit into the language. Still, we often call a list of characters a string, much like we call a char array a string in C, even though C does not have a native string type either. One can force an ISO conforming Prolog system to interpret double-quoted strings as atoms, i.e., to interpret "Hello, world!" as the atom 'Hello, world!', by setting the flag to the value atom. It is preferable to set it to chars though, because this allows the application of DCGs for reasoning about strings.

by triska 4y ago

funstuff007 4y ago

> https://youtu.be/74Ig_QKndvE https://youtu.be/74Ig_QKndvE Bon jour, the doc is en Francais. However, it does have legit subtitles (i.e. not auto-generated).

historia_novae 4y ago
Thanks, that was an interesting watch.

YeGoblynQueenne 4y ago

To be more precise, most Prologs before the last 5 years have built-in predicates that break _atoms_ up into either character codes, or characters. "String" as a datatype is the novelty of the new generation of Prologs. For instance, here's Sicstus | ?- atom_codes('abcd', Cs). Cs = [97,98,99,100] ? ; no | ?- atom_chars('abcd', Cs). Cs = [a,b,c,d] ? ; no | ?- Personally, I'm kind of ambivalent about this new direction. "String" is a programming language concept, but not a FOL concept. "Atom" is a FOL concept- but Prolog mangles the clean and tidy FOL (and Logic Programming) nomenclature and calls "atom" everything that should really be called a _constant_, and calls what should really be called an "atom", a "term". Then it's all downhill from there. The ideal for me would be to redress the wrong of confusing terminological swaps in Prolog jargon (atom--> constant, term--> bloody everything, predicate--> program, functor--> symbol, etc) and leave the details of the implementation (whether to represent constants as lists of characters or codes, and whether to define built-ins that operate on them) to the implementor. For me, Prolog's Logic Programming roots are the only thing that makes sense and helps understand Prolog. The turn towards programming language semantics and sometimes database semantics, has only served to make a mess of things. I blame it for the notorious difficulty that most programmers face in trying to pick up Prolog, which is seriously incommensurate to the brilliant simplicity of FOL and LP syntax and semantics.

dallasg3 4y ago
I didn't know FOL stood for First-Order Logic.
- YeGoblynQueenne 4y ago
  Oh, sorry, you're absolutely right. I should have explained the acronym before using it.
jhgb 4y ago
> "Atom" is a FOL concept- but Prolog mangles the clean and tidy FOL (and Logic Programming) nomenclature and calls "atom" everything that should really be called a _constant_, and calls what should really be called an "atom", a "term". It almost seems like they got all this confusion from badly copying Lisp. What you refer to above is clearly ancient (pre-Common) Lisp's EXPLODE and IMPLODE operators (https://www.cs.cmu.edu/Groups/AI/html/faqs/lang/lisp/part2/faq-doc-3.html https://www.cs.cmu.edu/Groups/AI/html/faqs/lang/lisp/part2/f...). Of course Lisp's symbols are Prolog's atoms, and Lisp's atoms are Prolog's terms.
- YeGoblynQueenne 4y ago
  Well I confess I don't know LISP nearly as well as Prolog, but they were both languages that came out of a certain tradition of research in FOL and how to calculate it with computers. There was bound to be some overlap. I remember noticing the thing about LISP atoms and symbols etc. and I thought that's probably it.
triska 4y ago
In SICStus Prolog, the query I showed yields C = 108 by default, because "Hello, world!" is interpreted as the list of character codes [72,101,108,...]. In contrast, in all the recent systems I mentioned, the double-quoted string "Hello, world!" is interpreted as the list of atoms of length one ['H',e,l,l,o,...]. This is preferable because it is more readable, and also because reasoning about such atoms in Prolog programs does not depend on any system-specific character encoding. In all ISO conforming systems, we can switch between these two interpretations of double-quoted strings by setting the Prolog flag double_quotes to codes and chars, respectively. The interesting phenomenon I mentioned is that both the earliest and the most recent Prolog systems acted as if this flag (which was not available yet in the first Prolog systems) was set to chars, interrupted by a number of years where it was set to a different default value in the Edinburgh tradition of Prolog systems. It is interesting because the newest Prolog systems follow the Marseille tradition in this respect, which precedes the Edinburgh tradition. Prolog does not have a native "string" type, neither SICStus nor the other systems I mentioned have it, because such a type does not fit into the language. Still, we often call a list of characters a string, much like we call a char array a string in C, even though C does not have a native string type either. One can force an ISO conforming Prolog system to interpret double-quoted strings as atoms, i.e., to interpret "Hello, world!" as the atom 'Hello, world!', by setting the flag to the value atom. It is preferable to set it to chars though, because this allows the application of DCGs for reasoning about strings.