Hacker News Reader

Comment by jplahn | Hacker News Reader

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?

View on HN

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

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

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

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

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/

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

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

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

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

In a classic Hindley-Milner type inference algorithm, you can't have a function "add(int, int) -> int" and "add(float, float) -> float". E.g. in Haskell, you'd need a type class for this.

Modern functional programming languages use a type inference algorithm more sophisticated than the original H-M algorithm which are more flexible than the original algorithm. The link you gave as an example is Haskell with a handful of language extensions related to the type checker - something entirely different to the H-M algorithm.

There can be other ways of implementing a similar type checker in a different manner, this was just a fun idea I came up with.

minor nitpick:

Prolog does not have functions. It has functors/predicates.

Unlike functions there is no distinct set of inputs and outputs. In prolog you can solve car(Foo,Bar):-some_rule. for Foo or Bar.

> Prolog does not have functions. It has functors/predicates.

I know.

I was talking about functions in the source language of the hypothetical compiler. The Prolog -style logic programs would be an internal data structure of that compiler.

It's easy to get confused when talking about compilers and interpreters because the source, target and host language concepts can get mixed up. Adding one or more intermediate languages to the mix doesn't help either. Either I was unclear or you didn't read my comment carefully enough :)

I wonder if you could do this for something like Python - perhaps with the assistance of the type annotations?

> I wonder if you could do this for something like Python

For something like Python, yes. For Python the language (as it currently is), no, not to the degree that I was talking about (ie. fully statically typed to enable compiling to native code).

But clever type inference algorithms for dynamic languages are a field of active research. Because static type information is the key to compiling fast code, a lot of the research going on in using type inference algorithms in fast JavaScript and other dynamic language runtimes.

At best, programming with a language using a clever type inference algorithm is almost as flexible as programming with a dynamic language - I wish there was more work going on in implementing nicer type inference -based static programming languages for the mainstream.

I was actually more thinking about at edit time - IDEs already do a limited about of inference about dynamic languages (e.g. PyCharm, and VS and JavaScript) - I was wondering about the benefits about having an interactive Prolog model able to make inferences about your application as you write it....

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.

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

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

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.

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.

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

Reply on news.ycombinator.com