Hacker News Reader

Comment by hexmiles | Hacker News Reader

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):

        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?

View on HN

Well do you know what a predicate is, in logic? 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

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

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.

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

Another interesting language in the same domain is Picat http://picat-lang.org/

Check out 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.

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.

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

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

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.

> 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".)

That something is "built in" doesn't mean it won't be defined somewhere, such as in the standard library.

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.

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?

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

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

There is a built in function for it in Prolog. But when it's presented as an example of how to implement it in the same way that list classes are often used as examples in OO languages even if they language implementation includes one.

Those collections have to be implemented by someone. You seem to be assuming that these collections spring fully formed into the world and are black boxes without an implementation.

I think you are willingly missing my point, because I believe it is obvious that I am not making that assumption.

Looking at the other responses to your comment, clearly it is not obvious that you're not making that assumption.

If that's not what you were trying to say, then I still don't understand what you were trying to say.

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

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.

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. :)

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.

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.

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

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.

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.

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=G_eYTctGZw8

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

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.

Reply on news.ycombinator.com