Hacker News new | ask | show | jobs
by openasocket 594 days ago
I've never used it in production, but I have a deep love of Prolog, just because of how different it is from any other programming language I've used. As a programming paradigm, it found it as eye-opening as functional programming. What I found interesting is that you are operating on logical statements and pattern matching, which often means that the same "function" can be used for multiple different things. For example:

append([], List, List).

append([Head|Tail], List, [Head|Rest]) :- append(Tail, List, Rest).

Is a simple list append function: append(X, Y, Z) is a predicate that match if Z is the list of all elements of X, followed by all elements of Y. You can use it to concatenate lists, of course. But you can also use it to confirm that a particular list start with a particular sequence, or ends with a particular sequence! The idea that the same predicate can be used in multiple different ways is really fascinating to me. I have no idea to what extent that would scale in a large system, but it's very interesting

4 comments

It doesn't scale that well because integers are their own, opaque thing in Prolog, and the is predicate is unidirectional. However, there's no inherent reason this has to be the case: you can construct your own representation of the integers from the Peano axioms, and recover bidirectionality of addition. (You'll want to be using some typed variant of Prolog with the "unary tree of units" optimisation, otherwise integers take O(n) space in memory, but it's possible in the language.) Prolog works how it does, because it's (mostly) backwards-compatible with a facts database used for symbolic AI research, where all atoms were opaque.
Check out the CLP(ℤ) library by Markus Triska, who is also the author of Scryer Prolog. It defines new comparison predicates that lets you use bidirectional logical programming on standard integers with standard math operations.

https://github.com/triska/clpz

Markus is not the author of Scryer Prolog, Mark Thom is.
“you can construct your own representation of the integers from the Peano axioms”

This is how the Idris prelude defines nat, the type of natural numbers (with some magic making it actually fast). I think that’s very cool.

There are many ways to recover relational behaviour. Libs such as clp(fd) (superseded by clp(Z)), clp(BNR) and others.
BNR notably works with real numbers and non linear constraints.
Modern Prolog libraries have handled the issues of unidirectional integer predicates, so the old ways of handling numeric values is not relevant for most problems.
Many times the algorithm that you are implementing requires a precise data flow that is not reversible, so using traditional arithmetic (is/2) is better for catching errors.

On the other hand CLP(FD) is not new at all (it is very popular for constraint programming).

Why would it be better for error handling? If you'll be using unidirectional flow only, then the point is moot. But using clp is arguably better IMO, allowing type and range checks while allowing relational execution.
I always thought that pattern matching would be an excellent feature for other programming languages, but it seems that it hasn't become popular. Many strategies available to Prolog could become possible just by the addition of this feature. One possible implementation of the idea occurs with C++ templates specialized with numerical parameters. It also seems that Mathematica provides pattern matching, but I don't use that language.
Matching of patterns, with only a single occurrence allowed for each variable, is fairly popular in languages designed in the last two decades, isn’t it? A lot of those have or at least borrow from ML heritage, and that of course places a big emphasis on algebraic types and pattern matching. Full-blown unification remains niche, that’s true, but it’s just a fairly heavyweight feature, and I don’t really know how you’d integrate it without turning your language into (a superset of) Prolog.
Simon Peyton Jones (of Haskell) is working on Verse, a functional relational programming language, that merges the ideas of both functional and logical programming into one.

It’s being done to facilitate Fortnite metaverse, as he’s doing this work at Epic.

https://youtu.be/OJv8rFap0Nw?si=OmBT9CBJIxdJE1Jv

Functional logic programming much before Verse https://mercurylang.org/
Which interestingly enough is used to make PrinceXML [1] one of the only "browsers" to fully support CSS print media.

1. https://www.princexml.com

Erlang, Elixir, Swift, Rust, Python, probably some others.

That list is roughly in order of how capable and useful the pattern matching is in each of those languages. Erlang was originally written in Prolog.

Also, I definitely agree it's a feature I miss everywhere when not using Erlang/Elixir.

I mostly ignored Python until my job required it, about 8 years ago. Coming from Erlang, I was pleasantly astonished to find that I could use tuple pattern matching in function headers… until I discovered that was dropped in Python 3 and I had been using the mostly-dead version 2 runtime.
I think I'd call this destructuring, as opposed to patterns and matches, and Python still does it, just not in the function head.

I do wish they went the opposite direction and made the feature better instead of keeping it as a weird assignment thing in the body. The match statement is a similarly unfortunate solution, in my opinion.

Oh well. :)

You're correct, destructuring is the appropriate term.

I checked the release notes, and the reason they removed it: no one was using it. I guess it's unsurprising, but sad.

I looked at Erlang and it is closest to the Prolog idea (clearly because Erlang was originally implemented in Prolog). Other languages are not really what I mean by pattern matching, the matching should go on the selection of functions to apply to a particular parameter expression. In the compiled world, C++ is the one that gets closest to this behavior. Python would be able to do it due to its dynamic nature, but for some reason it decided not to implement this feature.
I'm curious, how does Swift have better pattern matching than Rust?
I agree with sulam, in that I think they're roughly equally nice to work with. Not as powerful as Erlang/Elixir, but more capable than Python.

There's a decent discussion from a few years ago on hn, as well: https://news.ycombinator.com/item?id=24662262

These are probably tied TBH.
Same, I love the bidirectional aspect of relations
Do you have a suggestion on where to / how to start learning Prolog beyond towers-of-hanoi? Prolog is basically the last language on my list of things I want to look at, but whenever I tried, I failed to find anything practical to do/try.
Try a rules-based synthesis problem. Prolog style (put simplisticly) is to write down what is true about a solution, and turn the search engine loose. Prolog is still procedural, unfortunately, so practical Prolog requires understanding the search algorithm. A suggestion: produce the XY locations of the nails for a building-code-compliant nailing pattern for a panel of plywood roof sheathing. Allow different stud spacing and wind speed zones. This is a small toy problem but will channel your thought process toward something Prologgy.
I love this example so much. I used a similar kind of problem a year or so ago when playing with some kind of logic/linear programming/optimization system: given a set of shelves (width and length), find the set of guillotine cuts (cuts across the entire sheet) that minimizes how many sheets of plywood are needed. If I recall the general problem is actually in NP but by formulating it as a problem of finding a list of operations (new sheet, cut sheet X horizontally, cut sheet X vertically) the solver was able to come up with high quality solutions in seconds.

I then took it and added a second level: once it has found a minimal number of sheets, minimize the number of cuts. Super handy little tool! Once I had the solver part figured out and added a little tweak for handling kerf, it was quite simple to have it spit out an SVG that showed all of the pieces and cuts.

And now… I want to go find that code and play with it again. Super fun stuff outside of the daily grind.

I’ve enjoyed https://www.metalevel.at/prolog but I’m not a Prolog Programmer.
Ah, thanks for the link! I know his YouTube channel, but somehow I never realized there is a webpage too!
I have been going through https://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/pro...

It starts out pretty easy but gets harder and requires more thought. It has different sections on things like list processing or graph problems.