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:
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:
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.
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.
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.
> "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/f...). Of course Lisp's symbols are Prolog's atoms, and Lisp's atoms are Prolog's terms.
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.
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.
Thanks. Prolog doesn't have a native string type- indeed. And so atoms must be converted into lists. That's were trouble begins, I fear. Split the atom, and what do you get? Fallout.
I would phrase it like this: If you are using, in Prolog code, an atom of length greater than 1, then consider using a list of characters instead, especially if you want to reason about the data itself within your program. If you use lists of characters throughout, then no conversion to or from longer atoms is needed.
For example, in the sample queries you posted, instead of the atom abcd, consider using the list of characters "abcd" (i.e., [a,b,c,d]) instead, because such lists of characters can be readily described and analyzed with DCGs. In addition to this convenience, as a secondary concern, lists of characters provide an efficiency advantage, because they can be more transiently allocated on the Prolog heap instead of in the atom table, and are therefore immediately reclaimed on backtracking.
Characters, i.e., 1-char atoms, are indeed a good use case of atoms. For anything longer, lists of characters are in many cases a better option: In addition to their being amenable to reasoning with DCGs and the mentioned efficiency advantage, they also allow partial instantiations, such as [a,b,c|Ls] and [a,B,c,d], a feature that atoms do not support. Hence, when using atoms, the code tends to become more moded, whereas lists of characters readily allow generalizations.
Existing and upcoming Prolog implementation techniques allow a very compact internal representation of lists of characters as packed UTF-8 encoded sequences of bytes, and also a very efficient representation of each character as a single heap cell. Scryer Prolog and Trealla Prolog are the first Prolog systems that provide such an efficient internal representation of lists of characters, and are therefore already especially useful for efficient text processing.
>> I would phrase it like this: If you are using, in Prolog code, an atom of length greater than 1, then consider using a list of characters instead, especially if you want to reason about the data itself within your program. If you use lists of characters throughout, then no conversion to or from longer atoms is needed.
That's a very good point and I agree. It reminds a little of how, in formal texts, constants are most often single characters, especially when we just want to refer to some abstract constant in which case we say "c" or "a" or "b" or "α", "β", "γ" and whatever (I do the latter because I have a Greek keyboard and it's easy).
But there's a problem with that. In many cases in everyday Prolog programming it makes a lot of sense to represent constants by more than one character. For example, in the perennial family tree motivating example for ILP, you have (FOL) atoms like father(bob,alice) and mother(alice,dhalia) etc. That makes for a very natural notation- "bob" is clearly the name of a person. And then we end up with multi-character atoms that we might need to split or concatenate.
Representing such constants as lists of characters would be cumbersome and unnatural- for example father([b,o,b],[a,l,i,c,e]), looks awful, even if it's actually very practical. That's partly what the double-quoted atoms are supposed to achieve, but father("bob", "alice") again introduces unnecessary visual clutter. Perhaps the standard should be for multi-character atoms (or, well, all atoms) to be expanded to lists of atoms by the interpreter by default (without having to double quote) so that you know that writing father(bob,alice) is exactly the same as writing father([b,o,b],[a,l,i,c,e]) and you can then do some list processing, e.g. starting with father(X,Y), then append(X,...) and so on.
To be honest, I don't know much about how data are represented in memory in a Prolog engine- I think you know much more about all that, than me. So I can't imagine what the right answer is.
A compact, efficient representation of lists of characters sounds useful, for sure.
In my experience, data in Prolog programs will look like alice, bob and dhalia only in very artificial examples or exercises. For example, I have never seen a person's name spelled bob, and spelled like this, it is rather unlikely to be the name of a person one would represent in a Prolog program.
In Prolog programs that arise in practice, names are far more likely to look like "Alice", "King Solomon's Mines" and "La Grande Bellezza", and these names would need single-quotes or escape sequences for atoms too.
I disagree! 'bob' is a fine identifier for an object in the domain of discourse and an excellent key to bind together disparate facts representing diverse information about the object. For example:
And so on. And if there's multiple Bobs, 'bob1', 'bob2', 'bob3' etc, are also fine identifiers.
You certainly don't want to have "King Solomon's Mine" as the first term in a fact. That's fine for user-level representation, but not so much as a system-level representation. 'place_name("King Solomon's Mine") would look downright awful during debugging, especially if it were expanded into a character list.
(I use text debugging exclusively, so YMMV).
Anyway that's how I write all my Prolog programs so it certainly arises in practice.
Your example code now already uses lists of characters for names, and it is very readable. A good debugger will emit the exact same representation you are now using in the code, such as "Bobberton", "Bobbing" etc., and it will be very readable as well.
I remember reading and re-reading that article back when it first appeared on the 'net, right after I graduated from CompSci with a big crush on Prolog, paired to gigantic gaps in my understanding of it (and of Logic Programming in general).
The article looked... not enough. I got a general idea of how Prolog was used in Watson, but not clear enough that I could easily reproduce it myself. Or so I thought back then.
Reading it again now, it's clear to me that they used Prolog to implement the rule-based part of their system, whose function was, essentially, to map from an initial parse of a Jeopardy qustion to a semantic representation of the question, then find an answer for it.
Similar to what Triska points out in another comment in this thread, this is Prolog's bread and butter and the kind of thing that modern AI approaches can still not do very well, or at all. The downside of course is that they had to encode all those rules in Prolog by hand.
Which is not strictly necessary thanks to Inductive Logic Programming approaches, that can learn Prolog programs from data, either on their own, or in an interactive session, collaborating with a human programmer. I hear that IBM now have a dedicated ILP team who seem to be working on problems like that. Let's hope that the Watson debacle doesn't drag the whole thing down with it.
Regarding modern AI approaches not being great at what Prolog does, I'm curious if this will ever translate into an uptick in job postings for Prolog (or, at least, rule-based/declarative) jobs. One would expect hybrid systems in which the old school approach played some significant role, but I haven't noticed that happening in the market.
Rules-based/declarative seems to have ended up as “business rules/logic” in the commercial world (including RPA (feh)). Same uses but devoid of the magic AI glow.
I was doing lots of Prolog in the past, inspired by The Art / Craft of Prolog plus PAIP, and I also tried to find information to implement a toy Watson but there's next to none. I even talked to some consultants from IBM about this, but all the information I could get was very vague. This might have changed in the meantime.
BTW, I had seen your ILP publications in other previous posts and they are quite cool! Contrary to the popular belief, I think there is still a lot of room for logic-based approaches to AI.
All the information that IBM have released about Watson (the original system that won that Jeopardy game) was spread around a dozen reports published in the "IBM Journal of Research and Deelopment". I have the lot on a drive half a continent away, otherwise I'm sure it would be OK to share them. You might be able to find them online, but a very quick look didn't locate them for me. Online versions might be accessible from a university library, although I don't even remember their titles.
In short, from memory, Watson started with a shallow parse that was then used to fill in good old frames. If I remember correctly those were then queried by the Prolog rulebase. The shallow parse was by means of a dependency grammar trained from an annotated corpus (so not a language model, say). That's the very high level of it- I read all that back in 2014 or so and I only half-understood it. I seem to remember that one of the reports made a big to-do about a shallow parse being sufficient to solve a good chunk of information retrieval problems.
Other then that after the hype generated by Watson initially, it seems to have made only a very modest, perhaps underwhelming impact. To those not so familiar with the project, could you elaborate in which sense it has been a debacle?
I don't really know that much about it. It's just that every article I've read after the Jeopardy game, when IBM tried to flog Watson as a super NLP AI for medicine has been strongly negative, to the point that the entire brand has been soiled irreparably to the minds of many, far as a I can tell. More than underwhelming impact, that is.
25 comments
[ 3.1 ms ] story [ 70.5 ms ] threadIn fact, Prolog originates from Q-systems which were specifically designed to process language via grammar rules:
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
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:
In this string, the character 'l' is the only such letter.Bon jour, the doc is en Francais. However, it does have legit subtitles (i.e. not auto-generated).
For instance, here's Sicstus
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.
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/f...). Of course Lisp's symbols are Prolog's atoms, and Lisp's atoms are Prolog's terms.
I remember noticing the thing about LISP atoms and symbols etc. and I thought that's probably it.
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.
I'll get my coat.
For example, in the sample queries you posted, instead of the atom abcd, consider using the list of characters "abcd" (i.e., [a,b,c,d]) instead, because such lists of characters can be readily described and analyzed with DCGs. In addition to this convenience, as a secondary concern, lists of characters provide an efficiency advantage, because they can be more transiently allocated on the Prolog heap instead of in the atom table, and are therefore immediately reclaimed on backtracking.
Characters, i.e., 1-char atoms, are indeed a good use case of atoms. For anything longer, lists of characters are in many cases a better option: In addition to their being amenable to reasoning with DCGs and the mentioned efficiency advantage, they also allow partial instantiations, such as [a,b,c|Ls] and [a,B,c,d], a feature that atoms do not support. Hence, when using atoms, the code tends to become more moded, whereas lists of characters readily allow generalizations.
Existing and upcoming Prolog implementation techniques allow a very compact internal representation of lists of characters as packed UTF-8 encoded sequences of bytes, and also a very efficient representation of each character as a single heap cell. Scryer Prolog and Trealla Prolog are the first Prolog systems that provide such an efficient internal representation of lists of characters, and are therefore already especially useful for efficient text processing.
That's a very good point and I agree. It reminds a little of how, in formal texts, constants are most often single characters, especially when we just want to refer to some abstract constant in which case we say "c" or "a" or "b" or "α", "β", "γ" and whatever (I do the latter because I have a Greek keyboard and it's easy).
But there's a problem with that. In many cases in everyday Prolog programming it makes a lot of sense to represent constants by more than one character. For example, in the perennial family tree motivating example for ILP, you have (FOL) atoms like father(bob,alice) and mother(alice,dhalia) etc. That makes for a very natural notation- "bob" is clearly the name of a person. And then we end up with multi-character atoms that we might need to split or concatenate.
Representing such constants as lists of characters would be cumbersome and unnatural- for example father([b,o,b],[a,l,i,c,e]), looks awful, even if it's actually very practical. That's partly what the double-quoted atoms are supposed to achieve, but father("bob", "alice") again introduces unnecessary visual clutter. Perhaps the standard should be for multi-character atoms (or, well, all atoms) to be expanded to lists of atoms by the interpreter by default (without having to double quote) so that you know that writing father(bob,alice) is exactly the same as writing father([b,o,b],[a,l,i,c,e]) and you can then do some list processing, e.g. starting with father(X,Y), then append(X,...) and so on.
To be honest, I don't know much about how data are represented in memory in a Prolog engine- I think you know much more about all that, than me. So I can't imagine what the right answer is.
A compact, efficient representation of lists of characters sounds useful, for sure.
In Prolog programs that arise in practice, names are far more likely to look like "Alice", "King Solomon's Mines" and "La Grande Bellezza", and these names would need single-quotes or escape sequences for atoms too.
You certainly don't want to have "King Solomon's Mine" as the first term in a fact. That's fine for user-level representation, but not so much as a system-level representation. 'place_name("King Solomon's Mine") would look downright awful during debugging, especially if it were expanded into a character list.
(I use text debugging exclusively, so YMMV).
Anyway that's how I write all my Prolog programs so it certainly arises in practice.
The article looked... not enough. I got a general idea of how Prolog was used in Watson, but not clear enough that I could easily reproduce it myself. Or so I thought back then.
Reading it again now, it's clear to me that they used Prolog to implement the rule-based part of their system, whose function was, essentially, to map from an initial parse of a Jeopardy qustion to a semantic representation of the question, then find an answer for it.
Similar to what Triska points out in another comment in this thread, this is Prolog's bread and butter and the kind of thing that modern AI approaches can still not do very well, or at all. The downside of course is that they had to encode all those rules in Prolog by hand.
Which is not strictly necessary thanks to Inductive Logic Programming approaches, that can learn Prolog programs from data, either on their own, or in an interactive session, collaborating with a human programmer. I hear that IBM now have a dedicated ILP team who seem to be working on problems like that. Let's hope that the Watson debacle doesn't drag the whole thing down with it.
I guess it will take some time to become a bit more mature and get to the job market, maybe 5 years?
Some groups to look at (not exhaustive): Tenenbaum (MIT), De Raedt (KU Leuven), Muggleton (Imperial).
BTW, I had seen your ILP publications in other previous posts and they are quite cool! Contrary to the popular belief, I think there is still a lot of room for logic-based approaches to AI.
All the information that IBM have released about Watson (the original system that won that Jeopardy game) was spread around a dozen reports published in the "IBM Journal of Research and Deelopment". I have the lot on a drive half a continent away, otherwise I'm sure it would be OK to share them. You might be able to find them online, but a very quick look didn't locate them for me. Online versions might be accessible from a university library, although I don't even remember their titles.
In short, from memory, Watson started with a shallow parse that was then used to fill in good old frames. If I remember correctly those were then queried by the Prolog rulebase. The shallow parse was by means of a dependency grammar trained from an annotated corpus (so not a language model, say). That's the very high level of it- I read all that back in 2014 or so and I only half-understood it. I seem to remember that one of the reports made a big to-do about a shallow parse being sufficient to solve a good chunk of information retrieval problems.