5 ms·

We had to use Prolog in my comparative languages class last semester and it was interesting, to say the least. With any class that brushes over a topic, I didn'

by jplahn 12y ago

We had to use Prolog in my comparative languages class last semester and it was interesting, to say the least. With any class that brushes over a topic, I didn't get a full appreciation for what it can do, but it was an interesting paradigm to be exposed to if nothing else. I didn't feel like I was doing "real programming", which likely says more about what we're taught than the merits of the language. I'd be interested to known how it's being leveraged presently? I know a lot of the standard use cases, but is there anyone solving really unique problems with it?

seanmcdirmid 12y ago
We also studied Prolog for a week in my undergrad PL class (back in...1997?), but we never got to "cut" where things start getting really messy.
- jplahn 12y ago
  Yep, the extent of any programming we did with it was writing a bunch of facts about family relationships and then asking questions about relationships. Basic stuff. It was interesting, but hardly ground breaking.
ditonal 12y ago
I think declarative programming is real programming. The most obvious use case is when you have some sort of list of rules or constraint satisfaction problem. Gerrit uses its for that use case: https://gerrit-review.googlesource.com/Documentation/prolog-cookbook.html https://gerrit-review.googlesource.com/Documentation/prolog-... One of my college professors has a language that's heavily influenced by Prolog and designed to solve NLP problems called Dyna (I think because many NLP parsing problems can be solved by dynamic programing approaches that logic programs can easily express and optimize for). https://github.com/nwf/dyna https://github.com/nwf/dyna I actually think the real reason we don't see more Prolog or Prolog-like languages is not because they are bad approaches, but because it's relatively easy to make your own half-baked constraint satisfaction backtracking solver in a language like Python, and then write rules for it to evaluate, so smart people just write it that way rather than busting out Prolog. http://norvig.com/sudoku.html http://norvig.com/sudoku.html
- danieldk 12y ago
  I think because many NLP parsing problems can be solved by dynamic programing approaches that logic programs can easily express and optimize for Another reason is that you can directly express unification grammars in Prolog e.g., see definite clause grammar: https://en.wikipedia.org/wiki/Definite_clause_grammar https://en.wikipedia.org/wiki/Definite_clause_grammar During my PhD I worked on a parser/generator for Dutch at the University of Groningen, which is written in a mix of Prolog, C, and C++: http://www.let.rug.nl/vannoord/alp/Alpino/ http://www.let.rug.nl/vannoord/alp/Alpino/
  - arnsholt 12y ago
    And backtracking is so useful when doing parsing in general. For an NLP class I did we made a shift-reduce parser with dotted items for an assignment, and my liberally commented Prolog source weighs in a 33 lines of code. My friend's Lisp code which only found one parse (but did make parse trees, to be fair), was several hundred lines if memory serves. The corollary to Greenspun's tenth rule in action, I guess. =)
    - danieldk 12y ago
      Yep. I taught a Prolog NLP course and among the parsers covered was a shift-reduce parser, which would fit on one slide without much trouble. Same thing for chart parsing in Prolog. When you get backtracking and unification for free, implementing a parser is simple ;).
exDM69 12y ago
I'll share an idea for a logic programming project that I've been brewing for quite some time (but never started working on)... As you may know, the engine behind Prolog is based on the unification algorithm (finding substitution values for variables to make two patterns equal). The same algorithm is behind Hindley-Milner -style type inference algorithms. I have been considering writing a compiler for a programming language that would do type inference indirectly in two steps. In the first step (a typical syntax tree walk), rather than doing the actual unification directly, a Prolog -style logic program would be emitted. In the second step, the logic program is evaluated which will result in the types for the program. The advantage of this approach would be allowing function overloading (similarly to C++ or Java) informally without interfaces or type classes. This means that there will be ambiguous types for expressions, something which is quite hairy to implement using a H-M based classic type inference algorithm. If the final output has ambiguous types, it is a compile error in the source program. This is just a crazy idea I've been brewing, but this would definitely be a nice use case for a Prolog -style logic programming language. In practice, it wouldn't probably be Prolog itself, because implementing similar languages is so much fun and writing the code to call an external Prolog interpreter is about as much trouble but a lot less fun. Prolog certainly isn't your every day programming tool, but in some cases it's a really good tool to have. And learning logic programming is one of those ventures that will expand your horizons. Finally, here's a logic programming interpreter I wrote some years ago for a class: https://github.com/rikusalminen/slolog/tree/master/example https://github.com/rikusalminen/slolog/tree/master/example
- ehamberg 12y ago
  > The advantage of this approach would be allowing function overloading (similarly to C++ or Java) informally without interfaces or type classes. I might be misunderstanding something, but how does this allow function overloading more than ordinary let-polymorphism? Functions can already have a type like, say, ∀a.a→Int. It's also quite common to do type inference in two steps where the first pass creates type variables and a list of constraints. The set of constraints are then passed to a unification algorithm, see e.g. http://www.seas.upenn.edu/~cis552/lectures/stub/FunTypes.html http://www.seas.upenn.edu/~cis552/lectures/stub/FunTypes.htm....
ryangittins 12y ago
I had a very similar experience. We went over Prolog for five weeks or so, and while I did thoroughly enjoy learning a whole new paradigm, it still felt like it was just a toy. All programs amounted to `YES` or `NO`, without any building of an interface or other components I'd spent so long learning about. I can definitely identify with the feeling that it wasn't "real" programming. That being said, one use case which I did find interesting was that of graph theory and graph-based problems. I don't know much about graph theory beyond the basics, but simple things like tree traversal, the Shortest Path Problem, Dijkstra's algorithm, and other things revolving around nodes and edges seemed like a perfect fit for Prolog. You don't have to build a node object and write a bunch of code to create a tree and then a bunch more to traverse it. You just tell it some simple rules, give it a graph, and away you go. It can have incredibly low overhead, at least in terms of line count, for problems like these. I'm not sure whether or not these properties would make Prolog helpful in solving harder problems than these, but I suspect it would. It's just too simple not to be useful in some cases. Here are the rules, find something that satisfies them.
gowan 12y ago
Prolog is great at modeling complex logic. As an Automation Developer I use Prolog (swi-prolog) to generate test cases for some of the systems I test. In paticular I use prolog to model the high level buisness rules. This would be an example of an "expert system".
dwc 12y ago
So I've dabbled in Prolog and used it a few times, like many here. But yes, there are people doing significant and interesting work in Prolog. A friend of a friend who I followed when I was on Facebook uses Prolog quite a bit[1]. He's not an "all Prolog all the time" person. Rather, he's well acquainted with and likes Prolog and knows when it's a good fit for the problem at hand, or for pieces of the problem at hand. Search his site for prolog and you'll get a lot of interesting info. 1. http://covingtoninnovations.com/michael/index.html http://covingtoninnovations.com/michael/index.html
kazagistar 12y ago
The swi-prolog website (http://www.swi-prolog.org/ http://www.swi-prolog.org/) is written in prolog. People can hack a web server in anything.

by jplahn 12y ago

seanmcdirmid 12y ago

We also studied Prolog for a week in my undergrad PL class (back in...1997?), but we never got to "cut" where things start getting really messy.

jplahn 12y ago
Yep, the extent of any programming we did with it was writing a bunch of facts about family relationships and then asking questions about relationships. Basic stuff. It was interesting, but hardly ground breaking.

ditonal 12y ago

I think declarative programming is real programming. The most obvious use case is when you have some sort of list of rules or constraint satisfaction problem. Gerrit uses its for that use case: https://gerrit-review.googlesource.com/Documentation/prolog-cookbook.html https://gerrit-review.googlesource.com/Documentation/prolog-... One of my college professors has a language that's heavily influenced by Prolog and designed to solve NLP problems called Dyna (I think because many NLP parsing problems can be solved by dynamic programing approaches that logic programs can easily express and optimize for). https://github.com/nwf/dyna https://github.com/nwf/dyna I actually think the real reason we don't see more Prolog or Prolog-like languages is not because they are bad approaches, but because it's relatively easy to make your own half-baked constraint satisfaction backtracking solver in a language like Python, and then write rules for it to evaluate, so smart people just write it that way rather than busting out Prolog. http://norvig.com/sudoku.html http://norvig.com/sudoku.html

danieldk 12y ago
I think because many NLP parsing problems can be solved by dynamic programing approaches that logic programs can easily express and optimize for Another reason is that you can directly express unification grammars in Prolog e.g., see definite clause grammar: https://en.wikipedia.org/wiki/Definite_clause_grammar https://en.wikipedia.org/wiki/Definite_clause_grammar During my PhD I worked on a parser/generator for Dutch at the University of Groningen, which is written in a mix of Prolog, C, and C++: http://www.let.rug.nl/vannoord/alp/Alpino/ http://www.let.rug.nl/vannoord/alp/Alpino/
- arnsholt 12y ago
  And backtracking is so useful when doing parsing in general. For an NLP class I did we made a shift-reduce parser with dotted items for an assignment, and my liberally commented Prolog source weighs in a 33 lines of code. My friend's Lisp code which only found one parse (but did make parse trees, to be fair), was several hundred lines if memory serves. The corollary to Greenspun's tenth rule in action, I guess. =)
  - danieldk 12y ago
    Yep. I taught a Prolog NLP course and among the parsers covered was a shift-reduce parser, which would fit on one slide without much trouble. Same thing for chart parsing in Prolog. When you get backtracking and unification for free, implementing a parser is simple ;).

exDM69 12y ago

I'll share an idea for a logic programming project that I've been brewing for quite some time (but never started working on)... As you may know, the engine behind Prolog is based on the unification algorithm (finding substitution values for variables to make two patterns equal). The same algorithm is behind Hindley-Milner -style type inference algorithms. I have been considering writing a compiler for a programming language that would do type inference indirectly in two steps. In the first step (a typical syntax tree walk), rather than doing the actual unification directly, a Prolog -style logic program would be emitted. In the second step, the logic program is evaluated which will result in the types for the program. The advantage of this approach would be allowing function overloading (similarly to C++ or Java) informally without interfaces or type classes. This means that there will be ambiguous types for expressions, something which is quite hairy to implement using a H-M based classic type inference algorithm. If the final output has ambiguous types, it is a compile error in the source program. This is just a crazy idea I've been brewing, but this would definitely be a nice use case for a Prolog -style logic programming language. In practice, it wouldn't probably be Prolog itself, because implementing similar languages is so much fun and writing the code to call an external Prolog interpreter is about as much trouble but a lot less fun. Prolog certainly isn't your every day programming tool, but in some cases it's a really good tool to have. And learning logic programming is one of those ventures that will expand your horizons. Finally, here's a logic programming interpreter I wrote some years ago for a class: https://github.com/rikusalminen/slolog/tree/master/example https://github.com/rikusalminen/slolog/tree/master/example

ehamberg 12y ago
> The advantage of this approach would be allowing function overloading (similarly to C++ or Java) informally without interfaces or type classes. I might be misunderstanding something, but how does this allow function overloading more than ordinary let-polymorphism? Functions can already have a type like, say, ∀a.a→Int. It's also quite common to do type inference in two steps where the first pass creates type variables and a list of constraints. The set of constraints are then passed to a unification algorithm, see e.g. http://www.seas.upenn.edu/~cis552/lectures/stub/FunTypes.html http://www.seas.upenn.edu/~cis552/lectures/stub/FunTypes.htm....

ryangittins 12y ago

I had a very similar experience. We went over Prolog for five weeks or so, and while I did thoroughly enjoy learning a whole new paradigm, it still felt like it was just a toy. All programs amounted to `YES` or `NO`, without any building of an interface or other components I'd spent so long learning about. I can definitely identify with the feeling that it wasn't "real" programming. That being said, one use case which I did find interesting was that of graph theory and graph-based problems. I don't know much about graph theory beyond the basics, but simple things like tree traversal, the Shortest Path Problem, Dijkstra's algorithm, and other things revolving around nodes and edges seemed like a perfect fit for Prolog. You don't have to build a node object and write a bunch of code to create a tree and then a bunch more to traverse it. You just tell it some simple rules, give it a graph, and away you go. It can have incredibly low overhead, at least in terms of line count, for problems like these. I'm not sure whether or not these properties would make Prolog helpful in solving harder problems than these, but I suspect it would. It's just too simple not to be useful in some cases. Here are the rules, find something that satisfies them.

gowan 12y ago

Prolog is great at modeling complex logic. As an Automation Developer I use Prolog (swi-prolog) to generate test cases for some of the systems I test. In paticular I use prolog to model the high level buisness rules. This would be an example of an "expert system".

dwc 12y ago

So I've dabbled in Prolog and used it a few times, like many here. But yes, there are people doing significant and interesting work in Prolog. A friend of a friend who I followed when I was on Facebook uses Prolog quite a bit[1]. He's not an "all Prolog all the time" person. Rather, he's well acquainted with and likes Prolog and knows when it's a good fit for the problem at hand, or for pieces of the problem at hand. Search his site for prolog and you'll get a lot of interesting info. 1. http://covingtoninnovations.com/michael/index.html http://covingtoninnovations.com/michael/index.html

kazagistar 12y ago

The swi-prolog website (http://www.swi-prolog.org/ http://www.swi-prolog.org/) is written in prolog. People can hack a web server in anything.