Hacker News Reader

Comment by sterlind | Hacker News Reader

I'd never considered how the commonplace actor-world/entity-trait model is a neat fit for Prolog's whole relational deal. Though predictable and efficient run-time is also critical, and Prolog typically brute-forces its way through matching terms to satisfy the query. I haven't finished reading the series though - maybe they address it?

View on HN

Brute force search is just the naive way of finding solutions. Just like you can index a SQL table, you can index a Prolog predicate for better performance.

You can index, but iirc Prolog's indexing isn't powerful enough to efficiently handle SQL-like queries. Like, iirc `WHERE Id > 500` still requires trying all the Id values, you can't binary search on keys like that. And clause order matters a lot for perf. Doesn't Datalog use a different sort of evaluator that makes such queries more tractable?

There's no inherent reason you couldn't do that. That's another similarity to SQL: the underlying features of the language will depend on which runtime you're using.

SQL: Postgres, SQLite, MySql, etc. all have different features. Prolog: SWI-Prolog, GNU Prolog, Scryer Prolog, etc. same thing.

It's true that Datalog is better for pure data querying. But there's no theoretical reason it couldn't be implemented in Prolog as well.

Naïve question, but doesn't amount of brute-force search depend on the particular solver used? I'm vaguely aware of finite domain something or other but curious about the affordances prolog has for using different solvers over different parts of your codebase.

At first guess, I would imagine this could look like writing down known constraints on the solution as a kind of "type declaration".

Prolog's clpfd (constrained logic programming over finite domains) is actually just a library - albeit one with very ergonomic bindings that mesh almost invisibly into the language.

Prolog's evaluator backtracks when it hits a conflict while trying to expand a predicate. It evaluates queries top-down, and tries predicate definitions/clauses in order. It's basically eager. This isn't a good fit for math, so CLPFD fixed this by making arithmetic constraints lazy. This works really well, but you're ultimately using Prolog to build a model, then (invisibly) solving the model separately.

Ultimately, the problem is that Prolog looks like a DSL but is Turing-complete. You can weave other solvers into the language, but there's a seam between the evaluators. I like the alternative, which is to sacrifice Prolog's Turing-completeness for a ridiculously powerful DSL. Answer Set Programming (clasp) and Datalog are fine examples of this.

Reply on news.ycombinator.com