7 ms·

i have always trouble understaing prolog, lot of guide online seem to just tackle the syntax or assume you already know a lot of logic programming, for example

i have always trouble understaing prolog, lot of guide online seem to just tackle the syntax or assume you already know a lot of logic programming, for example the first example in the link (https://www.metalevel.at/prolog/facets https://www.metalevel.at/prolog/facets): list_length([], 0). list_length([_|Ls], N) :- N #> 0, N #= N0 + 1, list_length(Ls, N0). i don't undestand it, i read the segment describing it multiple time but i still don't get it, and is not the syntax i don't undestand how it should work, a tried reading the next few chapter but i feel i'm missing something! is there a "prolog for dummies" out there?

sordina 10y ago
Check out https://en.wikipedia.org/wiki/Horn_clause https://en.wikipedia.org/wiki/Horn_clause You can read this as two statements: "The length of a list is 0, if the list is empty." "Otherwise, if the length of a list Ls is N0, and N is N0 + 1, and N is greater than 0, then Ls with an additional element is of length N.
- na85 10y ago
  Good lord, does that mean it's necessary to explicitly tell the compiler the length of an empty list? Shouldn't the list type already know its own size? I fail to see the benefit... honestly it just seems like a waste of time.
  - tathougies 10y ago
    No. This is the standard implementation of the length/2 predicate. Like any other language, prolog has a standard library that includes this predicate. You'd never need to write this in practice, but this is how it would be written in the standard library. In general, any general purpose language worth it's salt will have substantial portions of its standard library written in that language, and in this regard, prolog meets the criteria for respectsbl languages
    - Koshkin 10y ago
      I guess, the point was, if list is a built-in construct, the function length should be also built in. (Unless, that is, natural numbers are defined in the standard library.)
      - YeGoblynQueenne 10y ago
        Prolog lists are predicates, like pretty much everything else in the language. Lists have the functor '.' (the dot) and two arguments, a term and a list, so they're defined recursively. Frex, this is a list: .(a, .(b, .(c, .(d, [])))) '[]' is an atom that stands for the empty list. Normally however we write lists like this: [a,b,c,d] Which is syntactic sugar used in the vast majority of Prolog code. The easiest way to think of it is that a list is a pattern, consisting of two square brackets enclosing any number of terms. You can't really call functions on it, but you can pass it as an argument to other predicates, and match it to other patterns.
      - tom_mellior 10y ago
        > I guess, the point was, if list is a built-in construct, the function length should be also built in. It is built in. No need to write your own length predicate. The quoted example is an illustration of a possible implementation. (Cue boring discussion of "built in" vs. "defined in the standard library".)
      - vidarh 10y ago
        That something is "built in" doesn't mean it won't be defined somewhere, such as in the standard library.
  - kevhito 10y ago
    It's no different than: public class LinkedList { ... public int size() { if (head == null) { return 0; } else { int n0 = 1 + head.size(); } } Actually, it is different. In prolog, you don't tell it how to compute an answer. You tell it what the answer is, and it figures out the rest. In the previous example, I'd phrase it more like this: I am sure [] has 0 length. I would be sure [_:Ls] has N length, if I was sure N>0 and N=N0+1 and [Ls] has N0 length. Notice I never really told prolog how it is supposed to go about figuring out that [Ls] has N0 length -- prolog might use recursion. Or there might be other facts which let it figure out the length of [Ls]. Prolog will try to find a way. For example, I might introduce a rule list_length(join(a, b), N) :- N #= NA + NB, list_length(a, NA), list_length(b, NB) Now prolog knows that when you join two lists of known length, the lengths can be summed, without actually counting the length of either list or the combined list. And actually prolog doesn't even know or care what "join" means here, it just knows that "join" will cause the lengths to get summed.
    - na85 10y ago
      Why on earth doesn't LinkedList already have a size() method? I'm thinking of typed languages, I guess, but surely any sane collection type knows how to perform addition/concatenation with other instances of its own type, right?
      - YeGoblynQueenne 10y ago
        Prolog is a logic programming language. It's not object-oriented, so it doesn't have objects or methods. If you want to know the length of a list you can use the predicate length/2: ?- length([a,b,c,d], N). N = 4. The example above just shows you how length/2 works (albeit with some CLP operators that are not typical). Edit: also, lists are not a "collection type" or any type at all. They're predicates, like everything else in the language. See my comment below - the easiest way to think of them is as patterns (just like in regexes, only Turing complete).
      - saghm 10y ago
        This is describing how you would implement LinkedList. Obviously, the size method has to be defined somewhere, and this is showing a potential implementation of it
  - outworlder 10y ago
    It is not a waste of time. Stop trying to match it to programming languages you already know and try to think in the abstract. This example is about a list. But you could be very well telling the system about relationships between car parts instead. Or git commits. Gerrit provides an actual real world use case: https://gerrit-review.googlesource.com/Documentation/prolog-cookbook.html https://gerrit-review.googlesource.com/Documentation/prolog-...
  - nwatson 10y ago
    In Prolog you can "run your logic backwards". In Java you can declare a list "my_list" and then ask for its length as in "my_list.size()". You can do the same in Prolog. Given the above Prolog definitions, here's an example of computing a list's length: | ?- list_length([13, 42], ListLength). ListLength = 2 yes | ?- NOT VERY EXCITING. But wait, you can run your logic BACKWARD. You can say instead, I have a list of length 2 -- what's inside the list?????? | ?- list_length(MyList, 2). MyList = [_,_] ? yes | ?- So that's strange. Prolog just gave us the form of an entity whose list-length is 2. And because we didn't say ANYTHING MORE SPECIFIC about the elements of the list, Prolog just gave us two placeholders for the items in the list ... '_' and '_'. Java can't do that out-of-the-box -- you can't say a list is size 2 and then ask for all the possible lists back. In our backwards-running Prolog example, we might have attached other conditions to the elements of the list ... in which case Prolog would (possibly) not have returned placeholders for the elements of the list, but might have done further work to figure out proper values to put into the list to satisfy the further conditions we gave for them.
- StreamBright 10y ago
  Excellent. How am I supposed to interpret this, or being able to write code? Even Erlang is much more readable and understandable at the first sight. :)
  - naasking 10y ago
    That's because Erlang is still a traditional imperative programming language, so it just slightly tweaks what you're already used to. Logic programming is completely different.
tomdre 10y ago
The fact list_length([], 0) says "the length of an empty list [] is 0". The clause says "the length of the list [_|Ls] (i.e, any element concat Ls) has length N if N>0, N=N0+1, and the length of Ls is N0". Hope this helps.
- FabHK 10y ago
  Why do you have to specify that N>0? Seems to me that this ought to be sufficient: the list [_|Ls] has length N if N=N0+1, and the length of Ls is N0
  - tom_mellior 10y ago
    In this particular example, specifying that N > 0 helps with running the predicate "backwards": You can use the query "length(L, 3)" to enumerate "all" lists of length 3, for example: ?- length(L, 3). L = [_G926, _G929, _G932]. This is not particularly informative for beginners, but it's a list containing exactly three distinct logic variables. Any three-element list is an instance of this. When running in this mode, the N #> 0 constraint ensures termination; otherwise, the recursive clause would find the three-element list, but then continue a futile infinite search for further lists (of negative length, which cannot exist). It takes a bit of getting used to Prolog's execution model to really understand why this is the case.
    - FabHK 10y ago
      Thanks for the informative reply. A related observation, by the way, regarding programming languages: often it all sort of makes sense, and you can put stuff together that gets you the correct result without really knowing what's actually going on behind the scenes. However, when you need stuff to go fast, then you really need to know the underlying runtime, execution model, memory model, etc. to find the incantation that's not only right, but efficient.
carapace 10y ago
Well do you know what a predicate is, in logic? https://en.wikipedia.org/wiki/Predicate_%28mathematical_logic%29 https://en.wikipedia.org/wiki/Predicate_%28mathematical_logi... What this prolog code is doing is defining a predicate called “list_length“, which captures the relation between a list and the integer that represents the length of the list. To do that you start with a base case, the relation between an empty list and the integer that represents the length of the list. That's the first prolog statement: list_length([], 0). It has no Body so this Head clause is always true: we are defining the list_length predicate for [] and 0. (Another way of saying that is that the pair ([], 0) is in some set called list_length.) The second statement has three Body clauses that specify three conditions: 1. You have an integer (technically a Natural number, not negative) named 'N' that is greater than zero. We do not care which integer it actually is at this point, just that it's greater than zero. 2. That integer 'N' is the sum of some other integer named 'N0' and one. We also do not care what 'N0' actually is, just that it is one less than 'N'. 3. There is some list named 'Ls', and the pair (Ls, N0) is in the set named 'list_length'. We also do not care what this list actually contains, just that it exists and that list_length(Ls, N0) is True. Given the above three conditions are satified, Prolog can conclude: 4. The pair ([_|Ls], N) is in the set named 'list_length'. You have to understand that the '_' mean anything, and '[foo|bar]' is how you add foo to the list bar to make a new longer list. (Like [1|[2|[3|[]]]] is the list 3 2 1.) See https://en.wikipedia.org/wiki/Cons#Lists https://en.wikipedia.org/wiki/Cons#Lists That code is enough information for the underlying Horn Clause Resolution to be able to do things like find the length of a list, or find lists of a given length. It's very powerful. https://en.wikipedia.org/wiki/Horn_clause https://en.wikipedia.org/wiki/Horn_clause
dreamcompiler 10y ago
Couple of weird things about Prolog: It's a pattern-matcher, in much the same way Haskell is -- but Prolog invented it first. Thus the first rule tries to match the args you give it, and if you give it the literals [] and 0, it just says "True" or "Yes" (depending on which Prolog you're using). If you give it something it cannot match to [] and 0, it will try the second clause and assume the first arg is a list with a head and a tail, and the second arg is an integer. The other weird thing is that Prolog functions can often run backwards. If you ask Prolog ?- list_length(Foo, 4) it will hand you back a list of 4 elements that it just made up on the spot. This is why Prolog rules are considered generalizations of functions: They don't have explicit inputs vs. outputs. They're relations, not functions. This stuff blew my mind when I first encountered Prolog and it changed forever how I thought about programming.
- doublec 10y ago
  The reversibility of Prolog computations was a big eye opener for me too back when I first encountered it. I recently wrote a post about relational programming using Prolog and Mozart/Oz as examples https://bluishcoder.co.nz/2017/03/20/relational-programming-in-mozart-oz.html https://bluishcoder.co.nz/2017/03/20/relational-programming-... Another interesting language in the same domain is Picat http://picat-lang.org/ http://picat-lang.org/
StreamBright 10y ago
Same here, I don't think this is a particularly great way of starting with Prolog. I have found these videos helpful for understanding Prolog: https://www.youtube.com/watch?v=SykxWpFwMGs https://www.youtube.com/watch?v=SykxWpFwMGs https://www.youtube.com/watch?v=G_eYTctGZw8 https://www.youtube.com/watch?v=G_eYTctGZw8
vram22 10y ago
I see there are multiple good answers already, but I'll just add my 2c - which answers from a different angle, sort of (though partially similar to some of the other answers). It may help, if you understand recursive calls to functions, and an imperative language like Python - the examples are in Python: Recursive computation of simple functions: https://jugad2.blogspot.in/2016/03/recursive-computation-of-simple_2.html https://jugad2.blogspot.in/2016/03/recursive-computation-of-... The first example shown is for computing the length of a list, recursively. Edit: To make it clear, my example uses an imperative approach, while your Prolog example uses a declarative approach. As the excellent comments by carapace and kevhito show, the two approaches are different. Just that my example may help you to get the solution used. But in Python, we tell the interpreter how to compute the length of a list. In Prolog, it is sort of as though we tell the interpreter what we want it to find out (a goal), and give it some facts / properties and rules to help it do that. It then does that, using its inference engine. HTH.

sordina 10y ago

Check out https://en.wikipedia.org/wiki/Horn_clause https://en.wikipedia.org/wiki/Horn_clause You can read this as two statements: "The length of a list is 0, if the list is empty." "Otherwise, if the length of a list Ls is N0, and N is N0 + 1, and N is greater than 0, then Ls with an additional element is of length N.

na85 10y ago
Good lord, does that mean it's necessary to explicitly tell the compiler the length of an empty list? Shouldn't the list type already know its own size? I fail to see the benefit... honestly it just seems like a waste of time.
- tathougies 10y ago
  No. This is the standard implementation of the length/2 predicate. Like any other language, prolog has a standard library that includes this predicate. You'd never need to write this in practice, but this is how it would be written in the standard library. In general, any general purpose language worth it's salt will have substantial portions of its standard library written in that language, and in this regard, prolog meets the criteria for respectsbl languages
  - Koshkin 10y ago
    I guess, the point was, if list is a built-in construct, the function length should be also built in. (Unless, that is, natural numbers are defined in the standard library.)
    - YeGoblynQueenne 10y ago
      Prolog lists are predicates, like pretty much everything else in the language. Lists have the functor '.' (the dot) and two arguments, a term and a list, so they're defined recursively. Frex, this is a list: .(a, .(b, .(c, .(d, [])))) '[]' is an atom that stands for the empty list. Normally however we write lists like this: [a,b,c,d] Which is syntactic sugar used in the vast majority of Prolog code. The easiest way to think of it is that a list is a pattern, consisting of two square brackets enclosing any number of terms. You can't really call functions on it, but you can pass it as an argument to other predicates, and match it to other patterns.
    - tom_mellior 10y ago
      > I guess, the point was, if list is a built-in construct, the function length should be also built in. It is built in. No need to write your own length predicate. The quoted example is an illustration of a possible implementation. (Cue boring discussion of "built in" vs. "defined in the standard library".)
    - vidarh 10y ago
      That something is "built in" doesn't mean it won't be defined somewhere, such as in the standard library.
- kevhito 10y ago
  It's no different than: public class LinkedList { ... public int size() { if (head == null) { return 0; } else { int n0 = 1 + head.size(); } } Actually, it is different. In prolog, you don't tell it how to compute an answer. You tell it what the answer is, and it figures out the rest. In the previous example, I'd phrase it more like this: I am sure [] has 0 length. I would be sure [_:Ls] has N length, if I was sure N>0 and N=N0+1 and [Ls] has N0 length. Notice I never really told prolog how it is supposed to go about figuring out that [Ls] has N0 length -- prolog might use recursion. Or there might be other facts which let it figure out the length of [Ls]. Prolog will try to find a way. For example, I might introduce a rule list_length(join(a, b), N) :- N #= NA + NB, list_length(a, NA), list_length(b, NB) Now prolog knows that when you join two lists of known length, the lengths can be summed, without actually counting the length of either list or the combined list. And actually prolog doesn't even know or care what "join" means here, it just knows that "join" will cause the lengths to get summed.
  - na85 10y ago
    Why on earth doesn't LinkedList already have a size() method? I'm thinking of typed languages, I guess, but surely any sane collection type knows how to perform addition/concatenation with other instances of its own type, right?
    - YeGoblynQueenne 10y ago
      Prolog is a logic programming language. It's not object-oriented, so it doesn't have objects or methods. If you want to know the length of a list you can use the predicate length/2: ?- length([a,b,c,d], N). N = 4. The example above just shows you how length/2 works (albeit with some CLP operators that are not typical). Edit: also, lists are not a "collection type" or any type at all. They're predicates, like everything else in the language. See my comment below - the easiest way to think of them is as patterns (just like in regexes, only Turing complete).
    - saghm 10y ago
      This is describing how you would implement LinkedList. Obviously, the size method has to be defined somewhere, and this is showing a potential implementation of it
- outworlder 10y ago
  It is not a waste of time. Stop trying to match it to programming languages you already know and try to think in the abstract. This example is about a list. But you could be very well telling the system about relationships between car parts instead. Or git commits. Gerrit provides an actual real world use case: https://gerrit-review.googlesource.com/Documentation/prolog-cookbook.html https://gerrit-review.googlesource.com/Documentation/prolog-...
- nwatson 10y ago
  In Prolog you can "run your logic backwards". In Java you can declare a list "my_list" and then ask for its length as in "my_list.size()". You can do the same in Prolog. Given the above Prolog definitions, here's an example of computing a list's length: | ?- list_length([13, 42], ListLength). ListLength = 2 yes | ?- NOT VERY EXCITING. But wait, you can run your logic BACKWARD. You can say instead, I have a list of length 2 -- what's inside the list?????? | ?- list_length(MyList, 2). MyList = [_,_] ? yes | ?- So that's strange. Prolog just gave us the form of an entity whose list-length is 2. And because we didn't say ANYTHING MORE SPECIFIC about the elements of the list, Prolog just gave us two placeholders for the items in the list ... '_' and '_'. Java can't do that out-of-the-box -- you can't say a list is size 2 and then ask for all the possible lists back. In our backwards-running Prolog example, we might have attached other conditions to the elements of the list ... in which case Prolog would (possibly) not have returned placeholders for the elements of the list, but might have done further work to figure out proper values to put into the list to satisfy the further conditions we gave for them.
StreamBright 10y ago
Excellent. How am I supposed to interpret this, or being able to write code? Even Erlang is much more readable and understandable at the first sight. :)
- naasking 10y ago
  That's because Erlang is still a traditional imperative programming language, so it just slightly tweaks what you're already used to. Logic programming is completely different.

tomdre 10y ago

The fact list_length([], 0) says "the length of an empty list [] is 0". The clause says "the length of the list [_|Ls] (i.e, any element concat Ls) has length N if N>0, N=N0+1, and the length of Ls is N0". Hope this helps.

FabHK 10y ago
Why do you have to specify that N>0? Seems to me that this ought to be sufficient: the list [_|Ls] has length N if N=N0+1, and the length of Ls is N0
- tom_mellior 10y ago
  In this particular example, specifying that N > 0 helps with running the predicate "backwards": You can use the query "length(L, 3)" to enumerate "all" lists of length 3, for example: ?- length(L, 3). L = [_G926, _G929, _G932]. This is not particularly informative for beginners, but it's a list containing exactly three distinct logic variables. Any three-element list is an instance of this. When running in this mode, the N #> 0 constraint ensures termination; otherwise, the recursive clause would find the three-element list, but then continue a futile infinite search for further lists (of negative length, which cannot exist). It takes a bit of getting used to Prolog's execution model to really understand why this is the case.
  - FabHK 10y ago
    Thanks for the informative reply. A related observation, by the way, regarding programming languages: often it all sort of makes sense, and you can put stuff together that gets you the correct result without really knowing what's actually going on behind the scenes. However, when you need stuff to go fast, then you really need to know the underlying runtime, execution model, memory model, etc. to find the incantation that's not only right, but efficient.

carapace 10y ago

Well do you know what a predicate is, in logic? https://en.wikipedia.org/wiki/Predicate_%28mathematical_logic%29 https://en.wikipedia.org/wiki/Predicate_%28mathematical_logi... What this prolog code is doing is defining a predicate called “list_length“, which captures the relation between a list and the integer that represents the length of the list. To do that you start with a base case, the relation between an empty list and the integer that represents the length of the list. That's the first prolog statement: list_length([], 0). It has no Body so this Head clause is always true: we are defining the list_length predicate for [] and 0. (Another way of saying that is that the pair ([], 0) is in some set called list_length.) The second statement has three Body clauses that specify three conditions: 1. You have an integer (technically a Natural number, not negative) named 'N' that is greater than zero. We do not care which integer it actually is at this point, just that it's greater than zero. 2. That integer 'N' is the sum of some other integer named 'N0' and one. We also do not care what 'N0' actually is, just that it is one less than 'N'. 3. There is some list named 'Ls', and the pair (Ls, N0) is in the set named 'list_length'. We also do not care what this list actually contains, just that it exists and that list_length(Ls, N0) is True. Given the above three conditions are satified, Prolog can conclude: 4. The pair ([_|Ls], N) is in the set named 'list_length'. You have to understand that the '_' mean anything, and '[foo|bar]' is how you add foo to the list bar to make a new longer list. (Like [1|[2|[3|[]]]] is the list 3 2 1.) See https://en.wikipedia.org/wiki/Cons#Lists https://en.wikipedia.org/wiki/Cons#Lists That code is enough information for the underlying Horn Clause Resolution to be able to do things like find the length of a list, or find lists of a given length. It's very powerful. https://en.wikipedia.org/wiki/Horn_clause https://en.wikipedia.org/wiki/Horn_clause

dreamcompiler 10y ago

Couple of weird things about Prolog: It's a pattern-matcher, in much the same way Haskell is -- but Prolog invented it first. Thus the first rule tries to match the args you give it, and if you give it the literals [] and 0, it just says "True" or "Yes" (depending on which Prolog you're using). If you give it something it cannot match to [] and 0, it will try the second clause and assume the first arg is a list with a head and a tail, and the second arg is an integer. The other weird thing is that Prolog functions can often run backwards. If you ask Prolog ?- list_length(Foo, 4) it will hand you back a list of 4 elements that it just made up on the spot. This is why Prolog rules are considered generalizations of functions: They don't have explicit inputs vs. outputs. They're relations, not functions. This stuff blew my mind when I first encountered Prolog and it changed forever how I thought about programming.

doublec 10y ago
The reversibility of Prolog computations was a big eye opener for me too back when I first encountered it. I recently wrote a post about relational programming using Prolog and Mozart/Oz as examples https://bluishcoder.co.nz/2017/03/20/relational-programming-in-mozart-oz.html https://bluishcoder.co.nz/2017/03/20/relational-programming-... Another interesting language in the same domain is Picat http://picat-lang.org/ http://picat-lang.org/

StreamBright 10y ago

Same here, I don't think this is a particularly great way of starting with Prolog. I have found these videos helpful for understanding Prolog: https://www.youtube.com/watch?v=SykxWpFwMGs https://www.youtube.com/watch?v=SykxWpFwMGs https://www.youtube.com/watch?v=G_eYTctGZw8 https://www.youtube.com/watch?v=G_eYTctGZw8

vram22 10y ago

I see there are multiple good answers already, but I'll just add my 2c - which answers from a different angle, sort of (though partially similar to some of the other answers). It may help, if you understand recursive calls to functions, and an imperative language like Python - the examples are in Python: Recursive computation of simple functions: https://jugad2.blogspot.in/2016/03/recursive-computation-of-simple_2.html https://jugad2.blogspot.in/2016/03/recursive-computation-of-... The first example shown is for computing the length of a list, recursively. Edit: To make it clear, my example uses an imperative approach, while your Prolog example uses a declarative approach. As the excellent comments by carapace and kevhito show, the two approaches are different. Just that my example may help you to get the solution used. But in Python, we tell the interpreter how to compute the length of a list. In Prolog, it is sort of as though we tell the interpreter what we want it to find out (a goal), and give it some facts / properties and rules to help it do that. It then does that, using its inference engine. HTH.