5 ms·

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,

by 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.

by sordina 10y ago

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.