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

Only slightly related, I wish there were a way to express this in run-off-the-mill, imperative/eager languages. Eg some way to explicitly mark a class, or something like it, as immutable-but-partially-instantiated. TypeScript supports this a tiny bit by means of its `readonly` keyword which lets you assign a value in the constructor, or in any method called from the constructor. But no later than that! If there was a way to make a field "readonly once_assignable" or something like that, you could do something like in this article (esp if you nest instances of a class that uses this) with an eager language, albeit with a lot more boilerplate (and getters, I assume).

It’s a beautiful construction. It reminds me a bit of the “canonical” quicksort in Haskell [1].

Neither of these implementations is going to be displacing absl::btree_map or std::sort any time soon, but I do feel we have a lot of “room at the bottom” for making simple and elegant code practical on real machines.

[1] https://stackoverflow.com/questions/7717691/why-is-the-minim...

Edit: replaced poorly formatted code with SO link.

It seems like whether this represents a mutable or immutable data structure depends on the operations you allow. If polling with nonvar() is allowed, couldn’t you see variables mutate as you do more unification? But if it’s not allowed, I guess you get a variable to be defined later?

Compare with a Promise. If you can check whether it resolved, you can see it mutate. If the only operation allowed is to await it then from the code’s point of view, it might be considered an immutable reference to the pending result.

Partially instantiated data structures are also available in Haskell (via Laziness), in OCaml (via tail modulo cons, https://inria.hal.science/hal-03146495/document) and Koka (via constructor contexts, https://dl.acm.org/doi/pdf/10.1145/3656398)

I don't get where the `-` comes from in `key-value` result lines after the "refactoring" title. I feel like it should stay a `,` like at the beginning. Can someone more knowledgeable in Prolog explain that? Is that because of an hidden use of this `to_list` predicate that comes later in the post?

Is "The Art of Prolog" a good place to start with the lanugage?

A classic library, you can play with it here: https://ciao-lang.org/playground/#https://github.com/ciao-la...

This is philosophically intriguing.

I am actually working on a logical query language that's a successor to prolog here: https://memelang.net/02/. Any feedback appreciated!

I've noticed quite a lot of Prolog content lately. I don't know if it's just a case of the Baader–Meinhof phenomenon, but it looks to me that recent article[1] about Prolog being able to improve LLM reasoning abilities renewed some interest in the language.

[1] https://shchegrikovich.substack.com/p/use-prolog-to-improve-...

Partial instantiation is cool and all, but tbh I prefer just capturing the initial incomplete attributes in one complete record, pass that around, and then instantiate the real thing when you have all attributes

    data class IncompletePerson(val name: String)

    data class Person(
      val name: String, 
      val email: String
    )

or

    data class Person(
      val initialAttributes: IncompletePerson, 
      val email: String
    )

if you want to nest it.

if you're the type to instead do this

    data class Person(
      val name: String, 
      val email: String?
    )

I never want to work with your code. Now, there's no disambiguation between the complete object and the incomplete one, I always have to check before doing anything with it, and people will inevitably try send an incomplete object someplace that can't handle it and generate bugs.

Laziness and TMC are fundamentally different from partial instantiation in that they are implementation details, mostly/wholly invisible to the language semantics themselves.

A key aspect of partial instantiation is that the "holes" may be filled in by a semantically unrelated piece of code, which is not the case for either laziness or TMC (wherein the contents data structure must be defined in one place, even if the implementation does not evaluate it immediately).

(I don't know Koka so I can't speak to that.)

Also, you can do lazy initialization in any language that has functions by passing a getter function around instead of a value.

I recently had need for this to implement validation for recursive data structures in TypeScript. It depends on support for forward references in the body of a function. The tricky bit is ensuring that the getter isn’t called until the cycle is completed by defining the forward reference’s target. The type system doesn’t help; you just have to write the implementation so it doesn’t call the getter.

I don't think Haskell can do this, can have a growable linked list for example. 'last a' is 'last a', regardless what is between them (modulo shadowing and such).

And I suspect that Prolog's Partial Instantiation is, while not mutating data, but it is mutating references somewhere

    type DList a = [a] -> [a]

    concat :: DList a -> DList a -> DList a
    concat = (.)

    toList :: DList a -> [a]
    toList d = d []

    fromList :: [a] -> DList a
    fromList = (++)

Operators like - are just an infix functor for a Prolog term with arity 2:

    ?- functor(123-"foo", Name, Arity, Type).
    Name = (-),
    Arity = 2,
    Type = compound.

    ?- 1-"foo" = '-'(1,"foo").
    true.

Functors like - only become arithmetic in combination with is:

    ?- A is '-'(42, 1).
    A = 41.
    
    ?- A is 42 - 1.
    A = 41.

(The initial version of this comment missed the point of your question; sorry.) The author says:

> We also store pairs as the pair type (Key-Value), instead of two separate values. This makes easy to serialize a dictionary into a list of pairs, which are sortable using the builtin keysort/2.

`Key, Value` is two values, not one. I suspect something like `kv(Key, Value)` would work as well.

By the way, I disagree that the refactored version doesn't cut; `-> ;` is syntactic sugar over a cut.

It's purely a convention to use terms of the form "key - value" for 2-tuples here (or '-'(key, value) in funtional/canonical notation which can be used as well). minus is just used because it's already predeclared as an infix operator, and indeed ','(key, value) could be used as well but comma is also used as argument separator and for conjunctions in clause bodies and thus tends to be avoided. You also can see '=' being used for the same thing eg.

    [ key = value, ...]

(for example, as used for representing attributes by SGML/XML parsing libs for SWI, Quintus/SICStus, and others), not to be confused with '=' being interpreted as unification operation in goals/clause bodies.

If you think about it, the simplest convention in Prolog to represent "assignment" of a value to a symbol (not a variable) would be

    key(value).

That is, to use the "key" atom as functor itself, rather than use functors/operators in ad-hoc ways. This is exactly what Quantum Prolog can do (optionally, and in addition to ISO Prolog's conventions).

Specifically, if you have a list of fact-like terms

    L = [ p(1), q(2), r(what(ever)) ]

then Quantum Prolog can answer queries against such term list, just like answering against the global default database eg.

    call(L ?- q(X))

binds

    X = 2

and would also bind additional values for q(X) on backtracking if the term list contained any. This is a natural extension to regular querying in Prolog because a term list [a, b] in Prolog's square bracket notation is just syntactic sugar for using the dot operator

    '.'(a, '.'(b, []))

and a Prolog program is syntactically just a list of clause terms.

In the container planning demo on the Quantum Prolog site [1], this feature is used for backtracking over (un)loading and travelling actions which would normally change state via destructive assert and retract calls and hence not allow backtracking to search for optimal sequences of actions.

[1]: https://quantumprolog.sgml.net/container-planning-demo/part2...

  lookup(Key, dict(Key,X,Left,Right), Value) :-
      !
      ,X=Value.
  lookup(Key, dict(Keyl,X,Left,Right), Value) :-
      Key < Keyl
      ,lookup(Key,Left,Value).
  lookup(Key, dict(Keyl,X,Left,Right), Value) :-
      Key > Keyl
      ,lookup(Key,Right,Value).