Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Power of Prolog

metalevel.at

Post reply on HN
Print view View original

21–30 of 164 posts

Re: The Power of Prolog

#21

Post by gugagore »

fizixer wrote: post #2

Roughly half the 'power of prolog' comes from the 'power of logic programming' and prolog is by far not the only logic programming language, e.g., - You can do logic programming using minikanren in scheme. (you can also extend the minikanren system if you find a feature missing). - Minikanren was implemented in clojure and called core.logic. - It was also ported to python by Matthew Rocklin I think, called logpy. - T…

Here are some (I thought helpful) comments regarding some of the tools you mentioned https://github.com/logpy/logpy/issues/24#issuecomment-269444...

Re: The Power of Prolog

#22

Post by haddr »

There is a class of problems which you can solve using Prolog with pure pleasure.

There is one thing however: Prolog can magically hide the complexity of many things, which is a two-sided sword. On many occasions you are hiding away the computational complexity and wonder why the execution is so slow. This rarely happens in imperative languages (where you are more aware of all the loops and recursions). I guess this is why many people hate Prolog...

Re: The Power of Prolog

#23

Post by sordina »

hexmiles wrote: post #19

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…

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.

Re: The Power of Prolog

#24

Post by na85 »

sordina wrote: post #23
hexmiles wrote: post #19

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…

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.

Re: The Power of Prolog

#25

Post by colanderman »

colanderman wrote: post #6
timonoko wrote: post #4

Never understood why natural numbers (or some set of N) is not in the search space: fib(X,X):- X fib(X,Y1+Y2):- fib(X-1,Y1),fib(X-2,Y2). I tried to get answer to this kwestion in reddit, but all I got was personal insults.

You can do this in SWI Prolog using the between/3 predicate for the inequality, and the is/2 predicate for the arithmetic.

Example, now that I'm at a terminal:

    fib(X, X) :- between(0, 1, X).
    fib(X, Y) :-
      (var(Y) -> between(2, infinite, X);
        MaxX is Y + 1, between(2, MaxX, X)),
      X1 is X - 1, X2 is X - 2,
      fib(X1, Y1), fib(X2, Y2),
      Y is Y1 + Y2.
The trick with var/1 allows the fib(-, +) instantiation to terminate (albeit very slowly). Otherwise it's not necessary.

What's even cooler is SWI-Prolog's CLP support. You can write fib/2 in the obvious manner and support all instantiations:

    ?- use_module(library(clpfd)).
    fib(X, X) :- X #>= 0, X #== 2, X #=

Re: The Power of Prolog

#26

Post by Karrot_Kream »

haddr wrote: post #22

There is a class of problems which you can solve using Prolog with pure pleasure. There is one thing however: Prolog can magically hide the complexity of many things, which is a two-sided sword. On many occasions you are hiding away the computational complexity and wonder why the execution is so slow. This rarely happens in imperative languages (where you are more aware of all the loops and recursions). I guess this…

> On many occasions you are hiding away the conputational complexity and wonder why the execution is so slow.

I disagree. Prolog is a language where it's quite easy to lose performance because of the density of each goal (a goal is "dense" and is basically a form of executable pseudocode), but equally easy to diagnose because of the terse expressiveness of the language. What gets a lot of Prolog beginners is the execution model: a lot of beginners just don't understand how the depth first search unification algorithm really works. Playing around in the REPL should help build that Intuition fairly quickly though.

I can post a concrete example if you want. Recently I changed an O(n^2) goal to an O(n) one and didn't have much trouble debugging it at all. I'm on mobile now but can post it later if you want.

Re: The Power of Prolog

#27

Post by tathougies »

na85 wrote: post #24
sordina wrote: post #23

Earlier quoted context omitted.

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

Re: The Power of Prolog

#28

Post by tomdre »

hexmiles wrote: post #19

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…

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.

Re: The Power of Prolog

#29

Post by carapace »

hexmiles wrote: post #19

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…

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

Re: The Power of Prolog

#30

Post by kevhito »

na85 wrote: post #24
sordina wrote: post #23

Earlier quoted context omitted.

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.

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.

Post reply on HN