6 ms·

A Short Introduction to Prolog

102 points by aerique 15y ago

andrewcooke 15y ago
so can you define something like transitive(X) :- [ X(A,C) :- X(A,B), X(B,C) ] (which generalises the decendent example)? more generally, i guess i am asking whether those horn clause things are first class.
- _delirium 15y ago
  Unfortunately, no. The names of predicates---functors in Prolog-speak---have to be symbols, not variables, and Horn clauses themselves aren't first-class either. You can do it via metaprogramming; a functor can be converted to a list [name, param1, param2, ...], and then you can write normal Prolog operations on the list that bind variables and such, and then convert back. This page shows how to use that to build a higher-order map function: http://en.wikibooks.org/wiki/Prolog/Higher_Order_Programming http://en.wikibooks.org/wiki/Prolog/Higher_Order_Programming Here's a paper on other approaches; I'm not sure if any of the higher-order Prolog approaches ever caught on, though: http://www.cs.umbc.edu/courses/771/papers/mu_96_02.pdf http://www.cs.umbc.edu/courses/771/papers/mu_96_02.pdf
  - JadeNB 15y ago
    There are also Prolog-derived languages that support higher-order programming 'natively', such as Teyjus (http://teyjus.cs.umn.edu http://teyjus.cs.umn.edu) and Curry (http://www-ps.informatik.uni-kiel.de/currywiki http://www-ps.informatik.uni-kiel.de/currywiki).
    - olliesaunders 15y ago
      Do you use either of these personally? Would you recommend them?
      - JadeNB 15y ago
        I had a terrible time getting Teyjus up and running. I played around with Curry a while ago (using PAKCS (http://www.informatik.uni-kiel.de/~pakcs http://www.informatik.uni-kiel.de/~pakcs), if I recall correctly), but didn't explore enough to say anything about it.
  - deleted 15y ago
    [deleted]
- deleted 15y ago
  [deleted]
- arethuza 15y ago
  As far as I recall you can add new facts easily enough using asserta or assertz but I'm pretty sure this approach doesn't work for rules.
- sp332 15y ago
  Nope, in vanilla Prolog you'd have to type "X(A,C) :- X(A,B), X(B,C)." for every single X you want to be transitive. In formal logic, "A if B" is just syntactic sugar for "(B && A) || (!B)" or in English: when B is true, A is true. (But when B is false, A could be either true or false.) So you could rewrite your expression as (edit: fixed): transitive(X, A, B, C) :- (X(A,B), X(B,C), X(A,C)); not(X(A,B), X(B,C)).
  - JadeNB 15y ago
    Prolog also has syntax for if-then, so x(A, C), x(A, B), x(B, C); not(x(A, C)). can essentially be re-written as x(A, C) -> x(A, B), x(B, C); true. (This saves testing `x(A, C)` twice. Also, `->` implicitly cuts, presenting backtracking over `x(A, C)`; but that shouldn't matter here.) However, this set-up mistakenly has `x(A, C)` as the antecedent; I think you actually want it as the consequent.
    - deleted 15y ago
      [deleted]
  - jimwise 15y ago
    though be careful how you do this -- it's easy to end up with a divergent program, as prolog tries to: * prove X(A,B) * realizes that it can prove this if it can prove transitive(X, A, B, C), and then prove X(B,A) * realizes that it can prove this if it can prove transitive(X, B, A, C), and then prove X(A,B) * ...
    - swannodette 15y ago
      Such behavior is easily avoided with tabling.
      - jimwise 15y ago
        There are a couple of ways around this -- all of which fall under "be careful". :-)
- route66 15y ago
  The problem is that transitive builds up a relationship between a functor and it's variables by trying to unify them with already known facts. But no new fact is generated. transitive(Functor) :- Rel1 =.. [Functor,A,B], Rel2 =.. [Functor,B,C], Rel3 =.. [Functor,A,C], call(Rel1),call(Rel2),call(Rel3). descendant(a,b). #fact1 descendant(b,c). #fact2 transitive(descendant) ;; says 'no' descendant(a,c). transitive(descendant) ;; says 'yes' This functor only tells us if the database has a transitive relationship recorded. If one wants the truth to be derived from the first two facts one would have to say transitive(F,A,B,C) :- R1 =.. [F,A,B], R2 =.. [F,B,C], call(R1),call(R2). which derives transitivity from the first two facts, the last relationship (R3) is what we want to conclude, not what we want to find in the database. Neither call though, will derive from fact1 and fact2 that "descendant(a,c)." is true. To arrive there you would have to "assert" these (new) facts explicitly in the transitive(...) definition. But Prolog is not my comfort zone, there might be (and probably is) a way out of that dilemma.
  - JadeNB 15y ago
    Note that there's another flaw: `transitive` as defined only checks if there's one instance of transitivity that works. If you wanted to check (rather than assert) transitivity, you'd need something more like transitive(Functor) :- not( call(Functor,A,B), call(Functor,B,C), not(call(Functor,A,C)) ). (It's been a while since I've Prologged, so I may be forgetting something subtle about why you'd need to use the dribble `=..` to build something callable; but that's not the point, of course!)
    - route66 15y ago
      Right, I see this as the third way: stating transitivity which must not be asserted explicitly. The question arises what one would want to reach with a call to transitive(descendant). (aside: the X =.. [F,A,B] is the prolog way of saying eval("F(A,B)"). and make it callable)
- JadeNB 15y ago
  A different problem to the 'non-first-class-ness' of clauses that others have mentioned is that Prolog is really just a unification engine, not a reasoning engine. Thus, even a manual definition x(A, C) :- x(A, B), x(B, C). is not always a good idea. For example, if you put this clause first (in the definition of `x`), it'll always try to reason by transitivity, rather than ever checking directly. The sub-clauses will then be checked by transitivity, &c. This is easy to fix by not putting this clause first; but then you run into further problems if `x` is reflexive; consider le(1, 1). le(A, C) :- le(A, B), le(B, C). Now ?- le(1, 0). will unify with `le(A, C)` by `A = 1`, `C = 0`, and then search for `B` such that `le(A, B)`. It'll put `B = 1`, and then try to solve `le(B, C)`, i.e., just `le(1, 0)` --and you're at the first stage of an infinite loop.
metaobject 15y ago
Ok, let's get it out of the way right now: no.
danieldk 15y ago
Good follow-up literature: - Learn Prolog Now! by Patrick Blackburn, Johan Bos, and Kristina Striegnitz provides an introduction to Prolog: http://www.learnprolognow.org/ http://www.learnprolognow.org/ - Prolog and Natural-Language Analysis by Fernando C. N. Pereira and Stuart M. Shieber provides an introduction to Prolog, and applies it to natural language processing. The book is more difficult than Learn Prolog Now!, but if you enjoy SICP, you will enjoy this book. http://www.mtome.com/Publications/PNLA/pnla-digital.html http://www.mtome.com/Publications/PNLA/pnla-digital.html - The Craft of Prolog by Richard O'Keefe is a must to learn writing correct efficient Prolog code. Many eye-openers. http://www.amazon.com/Craft-Prolog-Logic-Programming/dp/0262150395 http://www.amazon.com/Craft-Prolog-Logic-Programming/dp/0262... - Warren's Abstract Machine: A Tutorial Reconstruction by Hassan Ait-Kaci is a thorough overview of David Warren's abstract machine for executing of Prolog code. Since modern Prolog implementations are often based on WAM, it helps in understanding how to design efficient Prolog programs. http://wambook.sourceforge.net/ http://wambook.sourceforge.net/
- mhd 15y ago
  Don't forget Sterling and Shapiro's "Art of Prolog" http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=8327 http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&#38...
- JadeNB 15y ago
  The Craft of Prolog is a beautiful book; it's one of those SICP-style books that doesn't just teach you a programming language, but changes your way of thinking about programming. I am also amused by the sly (and not-so-sly) digs that O'Keefe gets in at, well, everyone else who writes Prolog.
  - br1 15y ago
    It's more down to earth than SICP. O'Keefe is like Michael Abrash in Graphics Programming Black Book.
- bulte-rs 15y ago
  Perhaps a little bit specific, but definitely worth the read: "Prolog Programming for Artificial Intelligence" by Ivan Bratko (0321417461)
datadon 15y ago
I did a university module in Prolog (for programming intelligent systems). Although I have not used it since, I always remember it fondly. It is a totally different paradigm to the Pythons/Rubies/Cs/Javas and really quite refreshing when you get in to it. Unfortunately I now struggle to think of a use for it on a day to day basis.
- ses 15y ago
  I think Prolog still has a place in modern software development. It provides a natural way of carrying out a backwards chaining depth first search through a state space (good for game AI, planning and scheduling etc). Also constraint solving is a very useful feature built into most logic programming languages now. Prolog pureists argue that the whole of Prolog can be used for applications, but I tend to take a different approach that integration of Prolog with other languages can help you to do the things its really good and you can get the best out of multiple languages. That's why I developed a (now open source) platform for integrating Prolog with other applications via web services... see http://kms.intelligent-architectures.co.uk/ http://kms.intelligent-architectures.co.uk/
  - kunley 15y ago
    +1 for the pragmatic use of Prolog. One can have Prolog-as-a-service. The SWI-PL implementation has excellent webserver out of the box. We feed the Prolog database from some external sources, do the reasoning and expose results via dead simple JSON API. It Just Works (tm) !!
  - jethroalias97 15y ago
    I'm a logic fan so I like prolog a lot, though for many people admittedly its greatest attribute will be expanding the way you think about programming. However for some problems you might want to go right to constraint programming as you mentioned if you need speed and ease of modeling. I like MiniZinc for many problems, or if you're interested you could try my constraint programming language (http://sabrlang.org http://sabrlang.org) which is based on spatial and temporal logic.
- alexholehouse 15y ago
barik 15y ago
I'll also chime in and say that Prolog is an interesting language to experiment with even if you don't use it for anything else later. It is said that there are some languages that change the way that you think about programming -- Prolog is definitely one of these. It is one of the few languages where the majority of the work is done through pattern matching (unification), rather than explicit algorithms.
- JadeNB 15y ago
  > It is said that there are some languages that change the way that you think about programming These are also sometimes called 'Perlis languages'. LtU has a nice thread at http://lambda-the-ultimate.org/node/3464 http://lambda-the-ultimate.org/node/3464 about other examples.
swannodette 15y ago
After learning a bit of Prolog and seeing its beauty you may wonder how to leverage the paradigm in your own work. Lispers in particular have pondered this for nearly 3 decades - Peter Norvig's Paradigms of Artificial Intelligence famously includes a Prolog interpreter/compiler. The Reasoned Schemer also continues in this tradition. I used that as my introduction into the beauty of Prolog and created core.logic - https://github.com/clojure/core.logic https://github.com/clojure/core.logic If you're interested in being able to mix functional, object-oriented, and logic programming techniques in a single practical language - I think Clojure is a great place to start (yes, yes, Mozart/Oz is good too ;).
- kunley 15y ago
  On your last sentence: well, dataflow variables plus backtracing are crucial things in Prolog; Mozart/Oz has dataflow vars right away and backtracing can be called on demand. How exactly would you do this in Closure? I'm a big fan of this platform, but can't see how to easily apply above-mentioned techniques. Dataflow library in clojure-contrib seems to have very narrow scope AFAIR.
  - deleted 15y ago
    [deleted]
  - swannodette 15y ago
    Clojure already has numerous concurrency constructs. core.logic doesn't in anyway attempt to add anything there as Mozart/Oz does via dataflow variables.
chipmunkninja 15y ago
Haha, in University, on a project with a friend, we ended up re-writing cpp (the C-compiler preprocessor) in Prolog. We got an A- and "I'm not sure why you'd do this … " on the project. Good times, good times.
cHalgan 15y ago
The reason why prolog is important to learn and play with it is to understand and learn concept of declarative programming as programming paradigm. That is very important skill when designing system because you learn how to define what the system should accomplish, rather than describing how to go about accomplishing it.
ranman 15y ago
This is a great follow up article as well: http://www.amzi.com/AdventureInProlog/ http://www.amzi.com/AdventureInProlog/ Create a text adventure game in Prolog. A great class project. See if you can get them to add networking to it and you can make a MUD!

102 points by aerique 15y ago

so can you define something like transitive(X) :- [ X(A,C) :- X(A,B), X(B,C) ] (which generalises the decendent example)? more generally, i guess i am asking whether those horn clause things are first class.

_delirium 15y ago
Unfortunately, no. The names of predicates---functors in Prolog-speak---have to be symbols, not variables, and Horn clauses themselves aren't first-class either. You can do it via metaprogramming; a functor can be converted to a list [name, param1, param2, ...], and then you can write normal Prolog operations on the list that bind variables and such, and then convert back. This page shows how to use that to build a higher-order map function: http://en.wikibooks.org/wiki/Prolog/Higher_Order_Programming http://en.wikibooks.org/wiki/Prolog/Higher_Order_Programming Here's a paper on other approaches; I'm not sure if any of the higher-order Prolog approaches ever caught on, though: http://www.cs.umbc.edu/courses/771/papers/mu_96_02.pdf http://www.cs.umbc.edu/courses/771/papers/mu_96_02.pdf
- JadeNB 15y ago
  There are also Prolog-derived languages that support higher-order programming 'natively', such as Teyjus (http://teyjus.cs.umn.edu http://teyjus.cs.umn.edu) and Curry (http://www-ps.informatik.uni-kiel.de/currywiki http://www-ps.informatik.uni-kiel.de/currywiki).
  - olliesaunders 15y ago
    Do you use either of these personally? Would you recommend them?
    - JadeNB 15y ago
      I had a terrible time getting Teyjus up and running. I played around with Curry a while ago (using PAKCS (http://www.informatik.uni-kiel.de/~pakcs http://www.informatik.uni-kiel.de/~pakcs), if I recall correctly), but didn't explore enough to say anything about it.
- deleted 15y ago
  [deleted]
deleted 15y ago
[deleted]
arethuza 15y ago
As far as I recall you can add new facts easily enough using asserta or assertz but I'm pretty sure this approach doesn't work for rules.
sp332 15y ago
Nope, in vanilla Prolog you'd have to type "X(A,C) :- X(A,B), X(B,C)." for every single X you want to be transitive. In formal logic, "A if B" is just syntactic sugar for "(B && A) || (!B)" or in English: when B is true, A is true. (But when B is false, A could be either true or false.) So you could rewrite your expression as (edit: fixed): transitive(X, A, B, C) :- (X(A,B), X(B,C), X(A,C)); not(X(A,B), X(B,C)).
- JadeNB 15y ago
  Prolog also has syntax for if-then, so x(A, C), x(A, B), x(B, C); not(x(A, C)). can essentially be re-written as x(A, C) -> x(A, B), x(B, C); true. (This saves testing `x(A, C)` twice. Also, `->` implicitly cuts, presenting backtracking over `x(A, C)`; but that shouldn't matter here.) However, this set-up mistakenly has `x(A, C)` as the antecedent; I think you actually want it as the consequent.
  - deleted 15y ago
    [deleted]
- jimwise 15y ago
  though be careful how you do this -- it's easy to end up with a divergent program, as prolog tries to: * prove X(A,B) * realizes that it can prove this if it can prove transitive(X, A, B, C), and then prove X(B,A) * realizes that it can prove this if it can prove transitive(X, B, A, C), and then prove X(A,B) * ...
  - swannodette 15y ago
    Such behavior is easily avoided with tabling.
    - jimwise 15y ago
      There are a couple of ways around this -- all of which fall under "be careful". :-)
route66 15y ago
The problem is that transitive builds up a relationship between a functor and it's variables by trying to unify them with already known facts. But no new fact is generated. transitive(Functor) :- Rel1 =.. [Functor,A,B], Rel2 =.. [Functor,B,C], Rel3 =.. [Functor,A,C], call(Rel1),call(Rel2),call(Rel3). descendant(a,b). #fact1 descendant(b,c). #fact2 transitive(descendant) ;; says 'no' descendant(a,c). transitive(descendant) ;; says 'yes' This functor only tells us if the database has a transitive relationship recorded. If one wants the truth to be derived from the first two facts one would have to say transitive(F,A,B,C) :- R1 =.. [F,A,B], R2 =.. [F,B,C], call(R1),call(R2). which derives transitivity from the first two facts, the last relationship (R3) is what we want to conclude, not what we want to find in the database. Neither call though, will derive from fact1 and fact2 that "descendant(a,c)." is true. To arrive there you would have to "assert" these (new) facts explicitly in the transitive(...) definition. But Prolog is not my comfort zone, there might be (and probably is) a way out of that dilemma.
- JadeNB 15y ago
  Note that there's another flaw: `transitive` as defined only checks if there's one instance of transitivity that works. If you wanted to check (rather than assert) transitivity, you'd need something more like transitive(Functor) :- not( call(Functor,A,B), call(Functor,B,C), not(call(Functor,A,C)) ). (It's been a while since I've Prologged, so I may be forgetting something subtle about why you'd need to use the dribble `=..` to build something callable; but that's not the point, of course!)
  - route66 15y ago
    Right, I see this as the third way: stating transitivity which must not be asserted explicitly. The question arises what one would want to reach with a call to transitive(descendant). (aside: the X =.. [F,A,B] is the prolog way of saying eval("F(A,B)"). and make it callable)
JadeNB 15y ago
A different problem to the 'non-first-class-ness' of clauses that others have mentioned is that Prolog is really just a unification engine, not a reasoning engine. Thus, even a manual definition x(A, C) :- x(A, B), x(B, C). is not always a good idea. For example, if you put this clause first (in the definition of `x`), it'll always try to reason by transitivity, rather than ever checking directly. The sub-clauses will then be checked by transitivity, &c. This is easy to fix by not putting this clause first; but then you run into further problems if `x` is reflexive; consider le(1, 1). le(A, C) :- le(A, B), le(B, C). Now ?- le(1, 0). will unify with `le(A, C)` by `A = 1`, `C = 0`, and then search for `B` such that `le(A, B)`. It'll put `B = 1`, and then try to solve `le(B, C)`, i.e., just `le(1, 0)` --and you're at the first stage of an infinite loop.

metaobject 15y ago

Ok, let's get it out of the way right now: no.

danieldk 15y ago

Good follow-up literature: - Learn Prolog Now! by Patrick Blackburn, Johan Bos, and Kristina Striegnitz provides an introduction to Prolog: http://www.learnprolognow.org/ http://www.learnprolognow.org/ - Prolog and Natural-Language Analysis by Fernando C. N. Pereira and Stuart M. Shieber provides an introduction to Prolog, and applies it to natural language processing. The book is more difficult than Learn Prolog Now!, but if you enjoy SICP, you will enjoy this book. http://www.mtome.com/Publications/PNLA/pnla-digital.html http://www.mtome.com/Publications/PNLA/pnla-digital.html - The Craft of Prolog by Richard O'Keefe is a must to learn writing correct efficient Prolog code. Many eye-openers. http://www.amazon.com/Craft-Prolog-Logic-Programming/dp/0262150395 http://www.amazon.com/Craft-Prolog-Logic-Programming/dp/0262... - Warren's Abstract Machine: A Tutorial Reconstruction by Hassan Ait-Kaci is a thorough overview of David Warren's abstract machine for executing of Prolog code. Since modern Prolog implementations are often based on WAM, it helps in understanding how to design efficient Prolog programs. http://wambook.sourceforge.net/ http://wambook.sourceforge.net/

mhd 15y ago
Don't forget Sterling and Shapiro's "Art of Prolog" http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=8327 http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&#38...
JadeNB 15y ago
The Craft of Prolog is a beautiful book; it's one of those SICP-style books that doesn't just teach you a programming language, but changes your way of thinking about programming. I am also amused by the sly (and not-so-sly) digs that O'Keefe gets in at, well, everyone else who writes Prolog.
- br1 15y ago
  It's more down to earth than SICP. O'Keefe is like Michael Abrash in Graphics Programming Black Book.
bulte-rs 15y ago
Perhaps a little bit specific, but definitely worth the read: "Prolog Programming for Artificial Intelligence" by Ivan Bratko (0321417461)

datadon 15y ago

I did a university module in Prolog (for programming intelligent systems). Although I have not used it since, I always remember it fondly. It is a totally different paradigm to the Pythons/Rubies/Cs/Javas and really quite refreshing when you get in to it. Unfortunately I now struggle to think of a use for it on a day to day basis.

ses 15y ago
I think Prolog still has a place in modern software development. It provides a natural way of carrying out a backwards chaining depth first search through a state space (good for game AI, planning and scheduling etc). Also constraint solving is a very useful feature built into most logic programming languages now. Prolog pureists argue that the whole of Prolog can be used for applications, but I tend to take a different approach that integration of Prolog with other languages can help you to do the things its really good and you can get the best out of multiple languages. That's why I developed a (now open source) platform for integrating Prolog with other applications via web services... see http://kms.intelligent-architectures.co.uk/ http://kms.intelligent-architectures.co.uk/
- kunley 15y ago
  +1 for the pragmatic use of Prolog. One can have Prolog-as-a-service. The SWI-PL implementation has excellent webserver out of the box. We feed the Prolog database from some external sources, do the reasoning and expose results via dead simple JSON API. It Just Works (tm) !!
- jethroalias97 15y ago
  I'm a logic fan so I like prolog a lot, though for many people admittedly its greatest attribute will be expanding the way you think about programming. However for some problems you might want to go right to constraint programming as you mentioned if you need speed and ease of modeling. I like MiniZinc for many problems, or if you're interested you could try my constraint programming language (http://sabrlang.org http://sabrlang.org) which is based on spatial and temporal logic.
alexholehouse 15y ago

barik 15y ago

I'll also chime in and say that Prolog is an interesting language to experiment with even if you don't use it for anything else later. It is said that there are some languages that change the way that you think about programming -- Prolog is definitely one of these. It is one of the few languages where the majority of the work is done through pattern matching (unification), rather than explicit algorithms.

JadeNB 15y ago
> It is said that there are some languages that change the way that you think about programming These are also sometimes called 'Perlis languages'. LtU has a nice thread at http://lambda-the-ultimate.org/node/3464 http://lambda-the-ultimate.org/node/3464 about other examples.

swannodette 15y ago

After learning a bit of Prolog and seeing its beauty you may wonder how to leverage the paradigm in your own work. Lispers in particular have pondered this for nearly 3 decades - Peter Norvig's Paradigms of Artificial Intelligence famously includes a Prolog interpreter/compiler. The Reasoned Schemer also continues in this tradition. I used that as my introduction into the beauty of Prolog and created core.logic - https://github.com/clojure/core.logic https://github.com/clojure/core.logic If you're interested in being able to mix functional, object-oriented, and logic programming techniques in a single practical language - I think Clojure is a great place to start (yes, yes, Mozart/Oz is good too ;).

kunley 15y ago
On your last sentence: well, dataflow variables plus backtracing are crucial things in Prolog; Mozart/Oz has dataflow vars right away and backtracing can be called on demand. How exactly would you do this in Closure? I'm a big fan of this platform, but can't see how to easily apply above-mentioned techniques. Dataflow library in clojure-contrib seems to have very narrow scope AFAIR.
- deleted 15y ago
  [deleted]
- swannodette 15y ago
  Clojure already has numerous concurrency constructs. core.logic doesn't in anyway attempt to add anything there as Mozart/Oz does via dataflow variables.

chipmunkninja 15y ago

Haha, in University, on a project with a friend, we ended up re-writing cpp (the C-compiler preprocessor) in Prolog. We got an A- and "I'm not sure why you'd do this … " on the project. Good times, good times.

cHalgan 15y ago

The reason why prolog is important to learn and play with it is to understand and learn concept of declarative programming as programming paradigm. That is very important skill when designing system because you learn how to define what the system should accomplish, rather than describing how to go about accomplishing it.

ranman 15y ago

This is a great follow up article as well: http://www.amzi.com/AdventureInProlog/ http://www.amzi.com/AdventureInProlog/ Create a text adventure game in Prolog. A great class project. See if you can get them to add networking to it and you can make a MUD!