Prolog Coding Horror (opens in new tab)

Some applications were discussed in https://news.ycombinator.com/item?id=40994552

Dunno about Prolog, but Datomic uses datalog for its query language, and it’s excellent. Datalog is a subset of Prolog.

Super simple example

    % Prolog
    next_light(green, yellow).
    next_light(yellow, red).
    next_light(red, green).

    % Erlang
    next_light(green)  -> yellow;
    next_light(yellow) -> red;
    next_light(red)    -> green.

Notable differences:

- `;` in Erlang indicates multi clause function

- In Prolog next_light is database, in Erlang it's just a function

Question: What's the light before green?

    % Erlang
    % Returns actual value
    prev_light_search() -> 
    [State || State <- [green, yellow, red], next_light(State) == green].

    % Prolog (?- means that it's in query mode)
    ?- next_light(Light, green).

So syntax IS similar though the thing is that Prolog is more like binding and quering database and Erlang is executing function.

In a nutshell Erlang is more like: "when I have X, then I can calculate Y" and Prolog like "If I want Y, what's the X".

Erlang has very little in common with Prolog, which is a language in an entirely different paradigm (logic programming).

Early versions of Erlang were implemented in Prolog, which is why Erlang's syntax looks a whole lot like Prolog's, but beyond that they're not very similar.

Not familiar with Erlang that much, but it's pretty clear Erlang was prototyped on Prolog because of its convenient facilities for DSLs using op/3 to define new tokens for its built-in bottom-up expression parser (using operator precedence parsing) and its Definite Clause Grammar recursive descent parser as trivial specialization of core SLD resolution (Prolog was created for NLP and planning apps in the first place after all).

I guess what may also have contributed is that there are a number of concurrent logics implemented in Prolog for prototyping Erlang's scheduler such as Concurrent Transaction Logic ([1]).

[1]: https://www.cs.toronto.edu/~bonner/ctr/Home.html

What Joe Armstrong et al took from Prolog is mainly the syntax.

These two languages are completely different paradigms.

And to understand the four-port model is to understand solution-space navigation and pruning.

Sometimes the Biorhythm program on my Apple ][ failed to produce correct answers. But it sure was great for impressing cool hippie chicks.

https://www.youtube.com/watch?v=jYoY1cwAd90

Prolog operators like `4 > 5` are a syntax sugar which desugars into a normal function call `>(4, 5)`. This part of the language is programmable, so you can add your own function `#>(X, Y)` and then declare it as an operator and use it like `4 #> 5`. See [1]. Nitpickingly, this means we can't be sure what #> is without looking, but it's common in Scryer and SWI Prolog (at least) that the #> #< versions of numeric comparison operators are used by constraint solver libraries. In imaginary Python it might be this code:

    import solver

    solver.add_variable(x)
    solver.variable_range(x, 0, 100)
    solver.add_constraint(x, greater_than, 50)

    solver.solve_for(x)

in pseudo-Prolog it can be:

    :- using constraint solver library
    
    X in 0..100,
    X #> 50,

    label(X)

where "in" and "#>" were added into the language at runtime by the import of the constraint library. That is, it calls out to a custom 'function' which tells the constraint solver to restrict possible values for for X from 0..100 down to 51..100.

> "and what ! does"

This is a concept which doesn't translate easily to other languages, but analogously it's like the performance difference between this code which always searches the entire haystack:

    found = false
    for item in haystack:
        if item == 'needle':
            found = true

    return found

and this which stops searching the haystack if the needle is found, but still searches the entire haystack in the worst case:

    for item in haystack:
        if item == 'needle':
            return true

    return false

The catch being that ! is not exactly a performance thing, it's an instruction to the Prolog runtime to skip some of the code, which can speed up performance but if you throw it in carelessly, your code no longer gives the right answers.

[1] They aren't Prolog "functions", they are predicates, functions are different, but it will do for this explanation.

!/0 is the cut. It prunes the search space. Useful to say "do not look at the other alternatives since I know they will fail" (when mutually exclusivity is hard) but also necessary to do negation in Prolog (when negated information cannot be easily or efficiently propagated).

is/2 is arithmetic evaluator. It runs only in one direction and it does not solve equations.

#>, #=, etc. are constraints, like (in)equalities over linear arithmetic. When constraints have the form of some known theory (like in SMT solvers), they can be solved (incrementally). That is called "constraint logic programming" (CLP). Modern Prolog systems are indeed CLP systems.

Prolog is older than CLP. CLP is older than SMT. Prolog+CLP systems are turing complete, can be used as programming languages. SMT is powerful but not a programming language.

Can "impure" features be avoided? Not in all cases. Think of them as 'unsafe' in Rust, but less dangerous.

Markus pushes for more purity in Prolog (using CLPFD), but sometimes some impurity (or imperative-like code with side-effects) is the best solution. Sometimes the pure solution is also the better. In other cases, it is not. Better compilers and static analyzers can reduce the friction between these worlds.

Take away: do pure code if you can afford it and it looks like a natural solution to your problem, use impure features later if you really need them.

You could always read the docs?

https://www.swi-prolog.org/pldoc/man?section=clpfd-integer-a...

https://www.swi-prolog.org/pldoc/doc_for?object=!/0

It reminds me of an old joke:

Radio Yerevan: A listener asks: "Is it true that in Moscow, on Red Square, they are giving away cars?"

Our answer: "Yes, it is true. Except it isn't in Moscow, but in Leningrad. And it isn't on Red Square, but on Palace Square. And they aren't cars, but bicycles. And they aren't giving them away, they are stealing them."