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

31–40 of 164 posts

Re: The Power of Prolog

#31

Post by carapace »

Karrot_Kream wrote: post #26
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 exec…

I'd like to hear that story, when you get the chance. ;-)

Re: The Power of Prolog

#33

Post by Koshkin »

tathougies wrote: post #27
na85 wrote: post #24

Earlier quoted context omitted.

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, prolo…

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

Re: The Power of Prolog

#34

Post by est »

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…

what about this?

https://github.com/Z3Prover/z3

Is it comparable with prolog or just a subset of prolog?

Re: The Power of Prolog

#35

Post by haddr »

Karrot_Kream wrote: post #26
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 exec…

Thanks! it's good to know that it is easier now to diagnose those complexity issues. Anyway if you can post an example, that could be really cool!

Re: The Power of Prolog

#36

Post by na85 »

kevhito wrote: post #30
na85 wrote: post #24

Earlier quoted context omitted.

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…

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?

Re: The Power of Prolog

#37

Post by YeGoblynQueenne »

na85 wrote: post #36
kevhito wrote: post #30

Earlier quoted context omitted.

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…

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

Re: The Power of Prolog

#38

Post by saghm »

na85 wrote: post #36
kevhito wrote: post #30

Earlier quoted context omitted.

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…

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?

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

Re: The Power of Prolog

#39

Post by YeGoblynQueenne »

Koshkin wrote: post #33
tathougies wrote: post #27

Earlier quoted context omitted.

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, prolo…

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.

Re: The Power of Prolog

#40

Post by outworlder »

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

Post reply on HN