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

61–70 of 164 posts

Re: The Power of Prolog

#61

Post by tom_mellior »

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

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

Re: The Power of Prolog

#62

Post by ahelwer »

lacampbell wrote: post #60

Can anyone give examples of the kinds of problems prolog is ideally suited to? I took a course on it at university. It looked interesting but I didn't really "get it". It might be worth another look now I have a bit more experience under my belt. I've got a lingering feeling it would solve a certain kind of problem very easily.

It's pretty much Backtracking as a language. So stuff like N Queens, Einstein's Puzzle (the Englishman lives in the red house, the Swede in the blue house, etc.) and so on. Any time you want to write down the rules of a discrete system and ask questions about the properties of that system, Prolog is a great way to do it.

One practical application: it's very easy to write the logic for a network firewall in Prolog.

Re: The Power of Prolog

#63

Post by mballantyne »

zodiac wrote: post #43

I wrote some prolog for a PL class recently and had to debug some cases of nontermination caused by the depth-first-search unification algorithm. I was wondering why prolog (or some other logic programming language) couldn't use breadth-first search instead, to avoid those cases, but couldn't find answers online - could someone who knows prolog better here have an answer?

Other search algorithms can take up lots of memory to store progress they've made down different paths. Having only one active state also lets you map unification down to efficient low level cpu operations. If you have multiple states, you either have to copy lots of data when you fork the state or you use a persistent data structure but can't use side effects, so everything is a bit slower.

It's a tradeoff though. I work on miniKanren, which is a logic programming language with a complete search that doesn't hit the nontermination issues you mention. The complete search lets us do some pretty cool stuff with program synthesis (though we're not about to put any programmers out of business just yet): https://www.youtube.com/watch?v=er_lLvkklsk

Note that you can implement iterative deepening depth first search on top of prolog if you want a complete search there. Iterative deepening takes a little more time but avoids the memory problems with breath-first. SWI has tools built in to help there: http://www.swi-prolog.org/pldoc/doc_for?object=call_with_dep... And I believe Ciao implements its iterative deepening library with a meta-interpreter: https://ciao-lang.org/docs/ciao/id_doc.html#0

Re: The Power of Prolog

#64

Post by saosebastiao »

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…

You forgot the most successful logic programming language to date: SQL.

Re: The Power of Prolog

#65

Post by tom_mellior »

lacampbell wrote: post #60

Can anyone give examples of the kinds of problems prolog is ideally suited to? I took a course on it at university. It looked interesting but I didn't really "get it". It might be worth another look now I have a bit more experience under my belt. I've got a lingering feeling it would solve a certain kind of problem very easily.

I've used it with enjoyment and success in several programming language projects (compilation, program analysis). It's well suited for these things for the same reason that languages like OCaml and Haskell are well suited and commonly used for them: algebraic data types and pattern matching (called terms and unification in Prolog, and a bit more powerful than simple pattern matching). You can more easily and directly access your data than is usual in imperative or object-oriented languages.

I do note that this is a domain where you have less need to "get" the backtracking search part of Prolog, it's more like functional programming. The point being that you can do useful programming, even imperative, in Prolog, not only logical "automatically exploring a large search space" stuff.

It's a general-purpose programming language plus a search system that you can choose to use or ignore as it fits your problem. But yeah, it's not usually presented as such.

Re: The Power of Prolog

#66

Post by lacampbell »

ahelwer wrote: post #62
lacampbell wrote: post #60

Can anyone give examples of the kinds of problems prolog is ideally suited to? I took a course on it at university. It looked interesting but I didn't really "get it". It might be worth another look now I have a bit more experience under my belt. I've got a lingering feeling it would solve a certain kind of problem very easily.

It's pretty much Backtracking as a language. So stuff like N Queens, Einstein's Puzzle (the Englishman lives in the red house, the Swede in the blue house, etc.) and so on. Any time you want to write down the rules of a discrete system and ask questions about the properties of that system, Prolog is a great way to do it. One practical application: it's very easy to write the logic for a network firewall in Prolog.

ah! backtracking. combinatorial optimisation would be incredibly useful for me. if prolog is indeed backtracking as a language I definitely need to look into it.

Re: The Power of Prolog

#67

Post by tom_mellior »

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…

Ah, blaming the language. See https://accidentallyquadratic.tumblr.com/ for other languages and systems (including HN's current favorite, Rust), which apparently also "[hide] away the computational complexity and [make you] wonder why the execution is so slow".

Not saying Prolog performance can't be tricky, but it's not that easy in other languages.

Re: The Power of Prolog

#68

Post by julian_1 »

Jtsummers wrote: post #13
andai wrote: post #11

Earlier quoted context omitted.

I don't get it. Isn't that the same thing but worse? Edit: Also, Greenspun's Tenth Rule of Programming: Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

It was worse. That office had an aversion to anything not-Microsoft for dev tools unless they were for the embedded systems we maintained. They also had an aversion to any language that wasn't "industry standard", whatever that meant (because, clearly, prolog and others do have industry standards associated with them; here they meant commonly used and easy to hire for).

This is a frustration of mine. At university they try to install a knowledge of all kinds of crazy languages, before you're ready to appreciate their value and the issues they attempt to address. The most glaring example is probably teaching Haskell in first-year. As a working programmer, you're then corralled into following prescriptive industry-practice - that always errs on the side of dumbing down the choice of technologies available.

Re: The Power of Prolog

#69

Post by dmh2000 »

nwatson wrote: post #53

The Japanese government spent US $400 million in the '80's (a lot in those days) to try to jump ahead of "western" computer technology via its "5th Generation Project". https://news.ycombinator.com/item?id=14047780 The basis for it all ... Prolog.

and it was an epic fail https://en.wikipedia.org/wiki/Fifth_generation_computer#Fail...

A primary problem was the choice of concurrent logic programming as the bridge between the parallel computer architecture and the use of logic as a knowledge representation and problem solving language for AI applications.

Re: The Power of Prolog

#70

Post by mballantyne »

est wrote: post #34
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?

My understanding is that Z3 is primarily an SMT solver (https://en.wikipedia.org/wiki/Satisfiability_modulo_theories), though it has also expanded to support queries beyond SMT.

SMT solvers excel at solving finite sets of equations involving finite or atomic data, like numbers, bitvectors, strings, and arrays of fixed length. They've been very successfully applied in software and hardware verification. They're also the essential tool for a big category of approaches to program synthesis.

This has some overlap with the sorts of numeric constraint solving available in prolog and with non-recursive prolog goals. Prolog however can express turing-complete computation with recursive goals, dynamically allocate data structures of unknown size, etc. that SMT cannot easily encode.

Z3 also has support for datalog-like queries. I don't know much about datalog, but my understanding is that it supports a more limited set of queries than prolog but can solve them more efficiently with a totally different algorithm than prolog's goal-directed depth first search.

Post reply on HN