50 Years of Prolog and Beyond(arxiv.org)
arxiv.org
50 Years of Prolog and Beyond
https://arxiv.org/abs/2201.10816
33 comments
I'm not a big fan of Prolog, but its descendents like Datalog or Answer-Set Programming are excellent. Datalog in particular I find much nicer than SQL as a database language. All the "normal forms" are basically how you'd model things in Datalog anyway.
> The great initiatives consisting of a small group of experts, such as the ISO working group or the Prolog Commons project, with some tweaks that we hope to have covered, can be re-invigorated to make stronger progress in the future. However, they may not be enough to bring together a user community that contributes to the language and its growth.
Not wanting to take away from that Festschrift and the wealth of authors covering generations of Prolog programming, but realistically, Prolog Commons contributed very little, was almost entirely ignored, had its last update almost ten years ago, can't be contributed towards, and those things it did add feel distinctly un-Prolog-ish and procedural, such as get_ and put_ primitives for maps.
Also, ISO/IEC 13211-1:1995/Cor.2:2012(E) feels kindof rushed (eg specifying false/0 thereby trivially breaking existing Prolog code such as ILP packages for no reason, insufficient description for subsumes_term/2, introducing call/N and the concept of closures without sufficient precedent, etc.)
Not wanting to take away from that Festschrift and the wealth of authors covering generations of Prolog programming, but realistically, Prolog Commons contributed very little, was almost entirely ignored, had its last update almost ten years ago, can't be contributed towards, and those things it did add feel distinctly un-Prolog-ish and procedural, such as get_ and put_ primitives for maps.
Also, ISO/IEC 13211-1:1995/Cor.2:2012(E) feels kindof rushed (eg specifying false/0 thereby trivially breaking existing Prolog code such as ILP packages for no reason, insufficient description for subsumes_term/2, introducing call/N and the concept of closures without sufficient precedent, etc.)
Hi, can you please explain how false/0 breaks ILP packages? I'm asking agnostically: I neither disagree nor agree with you. I study ILP, but I can't think of how false/0 would break Aleph, for instance (although truth be told I'm not as experienced with pre-2000 systems). And thanks in advance!
Aleph uses rules of the form false :- whatever(x) to represent negative examples, and will load those from a file derived from the project name with ".n" suffix and then assert these clauses dynamically. But this will be rejected (or at least warned against) by eg SWI beginning with version 6 (I believe) introducing ISO 2012 corrigenda, since false/0 is a static procedure ie. SWI's bootstrap file contains a definition false :- fail but doesn't declare false/0 to be dynamic.
Thanks, I didn't know that. I haven't worked with Aleph much and when I used it I didn't have any negative examples so I missed the problems with false/0.
Yes, SWI will probably complain of an attempt to redefine a static procedure if false/0 is redefined. It's actually defined in the system module (or a module imported therein) so I guess that an error will be raised even if the negative examples are declared in a module.
I wonder then, how does Aleph work around that? Or does it?
Yes, SWI will probably complain of an attempt to redefine a static procedure if false/0 is redefined. It's actually defined in the system module (or a module imported therein) so I guess that an error will be raised even if the negative examples are declared in a module.
I wonder then, how does Aleph work around that? Or does it?
Aleph was developed for running on YAP, then ported by the original developers to SWI when false/0 and other 2012 corrigenda adaptions weren't specced-out yet, and hasn't changed since. So Aleph itself doesn't work around anything, and we can only look at a recent SWI port of Aleph instead.
[1] quite radically changes the presentation of examples and background knowledge, triggering their loading off a single Prolog source file and making heavy use of directives to switch between pos/neg examples and background knowledge. I'm sure the author has somehow taken care of false/0, but a problem of that port of Aleph is that it won't work with the relative wealth of existing problem/data files in their original representation.
[1]: https://github.com/friguzzi/aleph
[1]: https://github.com/friguzzi/aleph
Thank you for your patience! Looking at the github repository for aleph, under
examples/abduce.pl I can see the source of my confusion: like you say, negative
examples are now given as (FOL) atoms (Prolog "facts"). I seem to remember that
in Aleph (as in Progol) examples are arbitrary definite clauses (with or without
bodies) and _negative_ examples are arbitrary Horn _goals_ (from which
"constraints" can be learned- i.e. Horn goals again). If that's so, then the
notation "false:- <body>" is a convention to facilitate parsing of negative
examples; because writing them as Horn goals (:-A,B,C...) would cause them to be
parsed as directives by the Prolog interpreter- and executed...! So "false" in
the head is a bit of a hack to begin with, or anyway a bit of syntactic sugar.
This actually points to a slight inconsistency between theory and practice in ILP, at least when the target language is Prolog. As a reminder, this is the standard setting for ILP: given background knowledge B and positive and negative examples E⁺, E⁻, find a hypothesis H such that H ∧ B ⊨ E⁺ and ∀e⁻ ∈ E⁻: H ∧ B ⊭ e⁻.
That makes a lot of sense intuitively: we want a correct hypothesis that entails all the positive and none of the negative examples, with respect to background knowledge. But it leaves open the question of what, exactly, are the negative examples. Especially when the target language is Prolog where we're operating under a closed-world assumption, where we only define the things we know to be true, it gets a bit tricky to explain how some examples (be they clauses or atoms) are "negative" when there's no real way to represent negation (only negation-as-failure) in a logic program (i.e. a set of definite clauses- no Horn goals in there!).
For me the ideal answer is that positive examples are atoms in the Herbrand base of a target predicate (the "top" predicate in H) that are assigned the value "true" by an interpretation ι, where H is a "name" for ι. So, negative examples must be the same as positive examples: atoms, assigned the value "false" by ι. So they should be written as atoms, without negation. That simplifies notation, allows learning a "contra-theory" (by switching the signs of E⁺ and E⁻) and avoids the need for syntactic conventions like "false:- <body>". But, my intuition is coloured from my experience with Meta-Interpretive Learning systems where examples are always atoms and learning is a proof by SLD-refutation of examples, both positive and negative (as opposed to inverse resolution which is... more complicated; let's just say that MIL makes a lot more sense to me than IR).
Digression, eh!
This actually points to a slight inconsistency between theory and practice in ILP, at least when the target language is Prolog. As a reminder, this is the standard setting for ILP: given background knowledge B and positive and negative examples E⁺, E⁻, find a hypothesis H such that H ∧ B ⊨ E⁺ and ∀e⁻ ∈ E⁻: H ∧ B ⊭ e⁻.
That makes a lot of sense intuitively: we want a correct hypothesis that entails all the positive and none of the negative examples, with respect to background knowledge. But it leaves open the question of what, exactly, are the negative examples. Especially when the target language is Prolog where we're operating under a closed-world assumption, where we only define the things we know to be true, it gets a bit tricky to explain how some examples (be they clauses or atoms) are "negative" when there's no real way to represent negation (only negation-as-failure) in a logic program (i.e. a set of definite clauses- no Horn goals in there!).
For me the ideal answer is that positive examples are atoms in the Herbrand base of a target predicate (the "top" predicate in H) that are assigned the value "true" by an interpretation ι, where H is a "name" for ι. So, negative examples must be the same as positive examples: atoms, assigned the value "false" by ι. So they should be written as atoms, without negation. That simplifies notation, allows learning a "contra-theory" (by switching the signs of E⁺ and E⁻) and avoids the need for syntactic conventions like "false:- <body>". But, my intuition is coloured from my experience with Meta-Interpretive Learning systems where examples are always atoms and learning is a proof by SLD-refutation of examples, both positive and negative (as opposed to inverse resolution which is... more complicated; let's just say that MIL makes a lot more sense to me than IR).
Digression, eh!
No worries, I enjoy discussing my favourite programming languages and stuff. Though tbh you lost me with those ILP details; it's not directly my area of expertise after all. I just wanted to point out that inclusion of false/0 in ISO Prolog wasn't well motivated and seems to create more trouble than it solves IMO.
Yeah, sorry, I thought I was going a bit overboard with the ILP exposition there :)
One of the most transformative parts of Prolog is the DCG(Definite Clause Grammars), you can specify a parser as regular Prolog code out of the box. Combine that with strings just being lists of chars, and it becomes super easy to write parsers, which simplifies a lot of issues.
Could you point me to some resources about this sort of thing? I remember hearing about someone implementing transpilation of some subset of C++ to some subset of Java using Prolog but I couldn't find the actual code.
You can have a look at my mini-Pascal parser, it was a toy exercise for the university almost 30 years ago, and some day I decided to uploaded into github.
https://github.com/pjmlp/Analyzer
https://github.com/pjmlp/Analyzer
Learn Prolog Now! [1] has a chapter on DCGs [1].
1: http://www.let.rug.nl/bos/lpn//lpnpage.php?pagetype=html&pag...
1: http://www.let.rug.nl/bos/lpn//lpnpage.php?pagetype=html&pag...
Not a tutorial resource, but the following is an example from my degree project,
that I wrote back in 2011 (don't judge me, OK? I've improved since then!). My
project was a Magic: the Gaterhing expert system that included a rules engine,
an AI player and an interpreter for the language on M:tG cards. The interpreter
was written using Prolog's DCGs. The project was written in a proprietary Prolog
(Win LPA Prolog) and I've had a lot of trouble porting it over to the free
SWI-Prolog - you can't run the entire project. But the DCG rules in links I give
below more or less work for any Prolog with a DCG module. Anyway, just looking
at the grammars in them should help get an idea of DCGs in an application that
is a step above trivial.
First, this is the main M:tG game language interpreter (the "MGL" interpreter; "MGL" is my own terminology, since the langauge on M:tG cards doesn't have an official name):
https://github.com/stassa/Gleemin/blob/master/mgl_interprete...
The first two-thirds of the source in the linked file is a grammar of a subset of the M:tG game language as a set of production rules in DCG form. That's already a parser for that subset of the M:tG language, right there in the DCG rules themselves (DCGs are just syntactic sugar for ordinary Prolog clauses so a grammar in DCG form is a Prolog program that can be executed as any Prolog program). The rest of the file implements rule engine functions some of which are called by the grammar, while others act as an interface with the rest of the rules engine. Probably. I don't remember what everything does...
The next file is a DCG for M:tG mana costs:
https://github.com/stassa/Gleemin/blob/master/mana_grammar.p...
This grammar is referenced from the previous source file where the "mana" nonterminal appears. So that's just an example of how you can modularise your code to avoid having all the rules in one big endless file. On the other hand, nothing stops you from making a big ball of mess by interleaving your grammar with the rest of your code.
Like all Prolog programs, DCG grammars can be "run backwards" so that a grammar that acts as a recogniser when given an input string, can act as a generator when given no input (Prolog doesn't have clear input and outputs, just variables to be instantiated as the program runs). So with my M:tG grammar above I could generate text for new M:tG cards. To facilitate this I set up the "MGL parser interface" below:
https://github.com/stassa/Gleemin/blob/master/mgl_parser_int...
The first defined predicate in there, identify_MGL/0 is used to identify the type of an M:tG language expression (given or generated), such as "activated ability", "triggered ability", "static ability" etc. So that's one example how to use a DCG for semantic analysis of a bit of text. As a for instance, you could use my identify_MGL/0 to search for abilities of a certain type (alongside a keyword search) which most search engines don't really let you do. My "parser interface" used it to generate abilities of a given type.
Anyway, that's an example of DCGs "in the wild" (though from someone who had no clue what she was doing when she wrote it). I hope it's instructive and I didn't just toot my own horn for no reason!
First, this is the main M:tG game language interpreter (the "MGL" interpreter; "MGL" is my own terminology, since the langauge on M:tG cards doesn't have an official name):
https://github.com/stassa/Gleemin/blob/master/mgl_interprete...
The first two-thirds of the source in the linked file is a grammar of a subset of the M:tG game language as a set of production rules in DCG form. That's already a parser for that subset of the M:tG language, right there in the DCG rules themselves (DCGs are just syntactic sugar for ordinary Prolog clauses so a grammar in DCG form is a Prolog program that can be executed as any Prolog program). The rest of the file implements rule engine functions some of which are called by the grammar, while others act as an interface with the rest of the rules engine. Probably. I don't remember what everything does...
The next file is a DCG for M:tG mana costs:
https://github.com/stassa/Gleemin/blob/master/mana_grammar.p...
This grammar is referenced from the previous source file where the "mana" nonterminal appears. So that's just an example of how you can modularise your code to avoid having all the rules in one big endless file. On the other hand, nothing stops you from making a big ball of mess by interleaving your grammar with the rest of your code.
Like all Prolog programs, DCG grammars can be "run backwards" so that a grammar that acts as a recogniser when given an input string, can act as a generator when given no input (Prolog doesn't have clear input and outputs, just variables to be instantiated as the program runs). So with my M:tG grammar above I could generate text for new M:tG cards. To facilitate this I set up the "MGL parser interface" below:
https://github.com/stassa/Gleemin/blob/master/mgl_parser_int...
The first defined predicate in there, identify_MGL/0 is used to identify the type of an M:tG language expression (given or generated), such as "activated ability", "triggered ability", "static ability" etc. So that's one example how to use a DCG for semantic analysis of a bit of text. As a for instance, you could use my identify_MGL/0 to search for abilities of a certain type (alongside a keyword search) which most search engines don't really let you do. My "parser interface" used it to generate abilities of a given type.
Anyway, that's an example of DCGs "in the wild" (though from someone who had no clue what she was doing when she wrote it). I hope it's instructive and I didn't just toot my own horn for no reason!
Sometime ago I came across Flix [1] which supports "First-class Datalog Constraints". I feel like this is the "right way" to implement Prolog: provide syntax/semantics for supporting logic programming, but don't force everything to be a Prolog predicate. Would be nice if more languages provided syntax and support for unification of data types and Prolog style searches.
1: https://flix.dev/
1: https://flix.dev/
Are there real world use cases of Prolog outside of purely theoretical or academic areas? Logic programming is often named together with the other major programming paradigms like functional, object-oriented or imperative, but I have never seen the use of Prolog in any actual project. Introductions rarely go beyond some primitive examples of filling a Prolog interpreter with data and running some deductions on it.
IBM Watson was using Prolog when it won in a Jeopardy! game:
"We required a language in which we could conveniently express pattern matching rules over the parse trees and other annotations (such as named entity recognition results), and a technology that could execute these rules very efficiently. We found that Prolog was the ideal choice for the language due to its simplicity and expressiveness."[0]
[0] https://www.cs.nmsu.edu/ALP/2011/03/natural-language-process...
[0] https://www.cs.nmsu.edu/ALP/2011/03/natural-language-process...
I use Prolog to build AI systems for robots. It's a very powerful tool, albeit with a pretty steep learning curve.
Interesting. Are you able to expand in this?
Can I read something about this? Sounds very interesting!
Prolog has traditionally been associated with various AI projects (although a bit different than some of the modern AI techniques I think). You should be able to find something high level in many of the prolog texts from the late 80s/90s.
There is apparently a web framework (http://eu.swi-prolog.org/), and they do mention commercial sponsors both as users and as contributors. It's no PHP or Javascript to be sure, but there are some users.
I read about a use for it in printing factories in Germany, using it to deduce the optimal number at to print different shapes on set sized paper.
Apparently there was a massive prolog-based component in the Windows NT kernel, to do with hardware monitoring or something.
I can't remember details, although last time I mentioned this here, I remember some guy replied to my comment and confirmed with details, so ... Angola Search is your friend :)
I can't remember details, although last time I mentioned this here, I remember some guy replied to my comment and confirmed with details, so ... Angola Search is your friend :)
I guess it was this article? http://web.archive.org/web/20040603192757/research.microsoft...
Sicstus Prolog claims that it's used in the transport and logistics industries,
in particular, handling a third of all airline tickets worldwide:
“Most people probably have used SICStus Prolog without knowing it,” says Mats Carlsson, its lead developer. “One of our customers runs a flight booking system on SICStus which handles nearly a third of all airline tickets in the world.”
https://www.sics.se/projects/sicstus-prolog-leading-prolog-t...
Quite substantial (for Prolog) applications in Prolog are commonly developed in the field of Inductive Logic Programming research most of which studies algorithms that learn Prolog programs from input-output examples. Here's a nice, recent overview:
Inductive logic programming at 30
https://link.springer.com/article/10.1007%2Fs10994-021-06089...
Historically, you would have found a lot more Prolog (more precisely, resolution-based logic programming) used in commercial software mostly around the 1980's and 1990's. Hard to believe today, but there was a time when Prolog was hyped about as much as deep learning today, as the hot new stuff in AI. The hype cycle started with the initiation of the Fifth Generation Computer project in Japan, in 1982:
The Fifth Generation Computer Systems (FGCS) was an initiative by Japan's Ministry of International Trade and Industry (MITI), begun in 1982, to create computers using massively parallel computing and logic programming. It was to be the result of a government/industry research project in Japan during the 1980s. It aimed to create an "epoch-making computer" with supercomputer-like performance and to provide a platform for future developments in artificial intelligence.
https://en.wikipedia.org/wiki/Fifth_generation_computer
The hype cycle picked up steam with a book, published in the US in 1983, written by Pamela McCorduck and Ed Feigenbaum (Turing Award recipient and the "father of expert systems") titled: The Fifth Generation: Artificial Intelligence and Japan's Computer Challenge to the World.
The book awakened a huge FOMO in Western industry and political figures and for a while everybody was trying to follow on the Japanese' footsteps. Unfortunately their project failed and probably took logic programming and Prolog with it. However, for a while at least, you'd have found a whole bunch of quite substantial Prolog projects being created in industry... and, knowing industry, it's very likely that quite a few of them are still putt-putt-putting quitely in some forgotten back-end in a bank, detecting fraud, or in a shipping agency planning routes etc. People invested lots of money on such systems and they worked reasonably well (like all software, that is) so nobody would have happily thrown them out when the AI winter of the '90s hit for good.
I wasn't around back then to see all this happening first hand so I'm guesstimating about the continued existence of Prolog systems. Anyway, when I first got interested in Prolog, when I was doing my degree back in 2011, I read the McCorduck and Feigenbaum book and I was struck by how confident its authors were that the Fifth Generation Computer project was poised to do to the computer industry what the Japanese had already done to the home appliances and automotive industry. I also remember reading a Prolog textbook from the 1990's (I forget the title- it was not one of the better known ones) whose introduction chapter opened with a certain exuberance about the usefuleness of knowning Prolog saying that it is now the language to know and that it's poised to take over the world, kind of thing.
There's perhaps a lesson to be learned from all this, for people studying more modern approaches to AI.
“Most people probably have used SICStus Prolog without knowing it,” says Mats Carlsson, its lead developer. “One of our customers runs a flight booking system on SICStus which handles nearly a third of all airline tickets in the world.”
https://www.sics.se/projects/sicstus-prolog-leading-prolog-t...
Quite substantial (for Prolog) applications in Prolog are commonly developed in the field of Inductive Logic Programming research most of which studies algorithms that learn Prolog programs from input-output examples. Here's a nice, recent overview:
Inductive logic programming at 30
https://link.springer.com/article/10.1007%2Fs10994-021-06089...
Historically, you would have found a lot more Prolog (more precisely, resolution-based logic programming) used in commercial software mostly around the 1980's and 1990's. Hard to believe today, but there was a time when Prolog was hyped about as much as deep learning today, as the hot new stuff in AI. The hype cycle started with the initiation of the Fifth Generation Computer project in Japan, in 1982:
The Fifth Generation Computer Systems (FGCS) was an initiative by Japan's Ministry of International Trade and Industry (MITI), begun in 1982, to create computers using massively parallel computing and logic programming. It was to be the result of a government/industry research project in Japan during the 1980s. It aimed to create an "epoch-making computer" with supercomputer-like performance and to provide a platform for future developments in artificial intelligence.
https://en.wikipedia.org/wiki/Fifth_generation_computer
The hype cycle picked up steam with a book, published in the US in 1983, written by Pamela McCorduck and Ed Feigenbaum (Turing Award recipient and the "father of expert systems") titled: The Fifth Generation: Artificial Intelligence and Japan's Computer Challenge to the World.
The book awakened a huge FOMO in Western industry and political figures and for a while everybody was trying to follow on the Japanese' footsteps. Unfortunately their project failed and probably took logic programming and Prolog with it. However, for a while at least, you'd have found a whole bunch of quite substantial Prolog projects being created in industry... and, knowing industry, it's very likely that quite a few of them are still putt-putt-putting quitely in some forgotten back-end in a bank, detecting fraud, or in a shipping agency planning routes etc. People invested lots of money on such systems and they worked reasonably well (like all software, that is) so nobody would have happily thrown them out when the AI winter of the '90s hit for good.
I wasn't around back then to see all this happening first hand so I'm guesstimating about the continued existence of Prolog systems. Anyway, when I first got interested in Prolog, when I was doing my degree back in 2011, I read the McCorduck and Feigenbaum book and I was struck by how confident its authors were that the Fifth Generation Computer project was poised to do to the computer industry what the Japanese had already done to the home appliances and automotive industry. I also remember reading a Prolog textbook from the 1990's (I forget the title- it was not one of the better known ones) whose introduction chapter opened with a certain exuberance about the usefuleness of knowning Prolog saying that it is now the language to know and that it's poised to take over the world, kind of thing.
There's perhaps a lesson to be learned from all this, for people studying more modern approaches to AI.
I loved Turbo Prolog.
Creating many cool things: graphical chess problem solver, watching the search process on a VGA screen on a 386 CPU, expert systems, logic analyzers.
But it's been a long time. C became my next new love (Turbo C first), and many years later a plethora of OO languages.
But Prolog still holds a special place. Too bad it really didn't catch on in my professional career.
Creating many cool things: graphical chess problem solver, watching the search process on a VGA screen on a 386 CPU, expert systems, logic analyzers.
But it's been a long time. C became my next new love (Turbo C first), and many years later a plethora of OO languages.
But Prolog still holds a special place. Too bad it really didn't catch on in my professional career.
Should be noted that Turbo Prolog is/was kind of a special thing on its own - unlike "regular" Prolog, TP is statically typed and has a more "rigid" form with its explicit "domains" (basically type declarations), "predicates", "clauses", etc sections. It isn't a huge difference in practice (and you can declare multiple versions of predicates - sort of like overloaded functions) aside from having to declare upfront of what you intend to do, but writing Turbo Prolog's dialect does feel quite different from other dialects.
AFAIK nowadays the compiler is still being developed as Visual Prolog.
AFAIK nowadays the compiler is still being developed as Visual Prolog.
I had no idea Visual Prolog existed! Thanks for that mention.
It is one of my favourite programming languages, pity that after university logic programming competitions I never found a use case where I could profit from it.
Happy birthday Prolog.
Happy birthday Prolog.
Prolog is beautiful. I don't necessarily use it much these days, but it completely transformed the way I see coding since.
I always wondered how this compared to something like CLIPS[1]
[1] http://www.clipsrules.net/index.html
[1] http://www.clipsrules.net/index.html
The main difference is that CLIPS is a forward chaining rule system, while Prolog is backward chaining. This is a big difference in how rules are defined and how do you use them (in Prolog you start with a query always and you try to prove it, in CLIPS you just run it to get some rules dispatched).
However, Prolog is also a valid general purpose programming language, so you can actually implement forward chaining rule systems in them (see for example CHR[1] and Heiseneye [2]). CLIPS is not a general purpose programming language.
[1] https://www.swi-prolog.org/man/chr.html [2] https://github.com/IDLabResearch/Heiseneye
However, Prolog is also a valid general purpose programming language, so you can actually implement forward chaining rule systems in them (see for example CHR[1] and Heiseneye [2]). CLIPS is not a general purpose programming language.
[1] https://www.swi-prolog.org/man/chr.html [2] https://github.com/IDLabResearch/Heiseneye