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:
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
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.
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.
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.
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.
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.
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).
Yes, that is true! Koka's constructor contexts also allow you to do this. A constructor context is a data structure with exactly one hole which you can fill in with an arbitrary value (or even several arbitrary values, copying the constructor context in the process).
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
Technically, Haskell laziness is just mutability under the hood :)
And the "difference list" mentioned in the article is also in Haskell - although framed differently (more "functionally")
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 = (++)
Haskell has cyclic data structures, which also can’t be implemented without a mutable reference somewhere, though it may be buried in the implementation.
The difference is being able to define an incomplete data structure (with a forward reference) and then defining the target of the reference at runtime. Most languages will complain about an undefined reference if it’s not defined by the end of a module.
You could do it with soft references, though. Use a symbol or string to refer to something and define it later.
I rather think the fact the the same symbol/string always denotes the same thing is especially helpful for cyclic structures.
Anyway I think I misunderstood the article, I thought they added things to a dictionary in the prolog repl, which would be impossible in haskell/ghci afaik.
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.
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.
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?
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.
You can also see that in the first call to lookup/3 where there's no -/2.
If I understand correctly, that's what the OP is asking: Where did the -/2 come from, not what it's for.
The call with the -/2 is under the heading "Refactoring the dictionary" so it's possible the author mixed up the implementations while writing the article and listed the output of an implementation that represents key-value pairs as -/2 terms.
The refactored version makes more sense btw and indeed I see the author switches to K-V later on in the article.
(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 a bold statement to call something a Prolog successor! Are you aiming for a general purpose logic programming language like Prolog, or targeting the use case of querying knowledge bases?
One of the draws to Prolog is its immensely simple syntax:
A.R:B = true in your case would be represented as simply r(A, B).
It looks like you've elevated some set theory properties to syntax, and have added some neat sugar over chained relations. Have you found areas where this really shines as compared to writing more standard Prolog/Datalog queries? I'm afraid I couldn't see many examples on first look at your Github.
It might be worth using standard vocabulary. For example:
> Reciprocal relations are their own inverse.
The usual word for this is "symmetric".
> Recursive relations can be chained to themselves infinitely. For example, "my ancestor's ancestor is also my ancestor."
The usual word for this is "transitive".
A reflexive, symmetric, transitive relation is called an "equivalence relation", and it can be used much like equality. It'd be nice if your language had support for this, though I don't immediately see how to add it.
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.
Which is strange considering how old and limited Prolog in a sense is. I wonder why no superset ever gained traction and what it would look like. I imagine it fitting somewhere in the hierarchy
> Why Prolog? [...] Due to it's declarative nature it might be a bit easier for LLMs to generate code, because LLM doesn't need to generate precise control flow.
This is an interesting point, and my guess is that prolog is the declarative programming language with most example code out there for it to learn on(excluding SQL). Alternatively it could try to create some problem description for an automated theorem prover. My (absolute ignorant) guess is that the prolog aproach works better for two reasons:
- The amount of prolog code in the training set is higher
- It is still only able to create code for problems easy enough that prolog can handle them.
He might be thinking about the SLDNF resolution happening. But yes, you can implement any prover in prolog. This distinction is discussed a bit here: https://www.metalevel.at/prolog/theoremproving
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.
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
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.
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.
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’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!
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
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.
“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.
Same, I love the bidirectional aspect of relations
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)
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.)
Yes, that is true! Koka's constructor contexts also allow you to do this. A constructor context is a data structure with exactly one hole which you can fill in with an arbitrary value (or even several arbitrary values, copying the constructor context in the process).
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
Technically, Haskell laziness is just mutability under the hood :)
And the "difference list" mentioned in the article is also in Haskell - although framed differently (more "functionally")
Haskell has cyclic data structures, which also can’t be implemented without a mutable reference somewhere, though it may be buried in the implementation.
The difference is being able to define an incomplete data structure (with a forward reference) and then defining the target of the reference at runtime. Most languages will complain about an undefined reference if it’s not defined by the end of a module.
You could do it with soft references, though. Use a symbol or string to refer to something and define it later.
I rather think the fact the the same symbol/string always denotes the same thing is especially helpful for cyclic structures.
Anyway I think I misunderstood the article, I thought they added things to a dictionary in the prolog repl, which would be impossible in haskell/ghci afaik.
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.
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.
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?
Operators like - are just an infix functor for a Prolog term with arity 2:
Functors like - only become arithmetic in combination with is: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.
(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
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
then Quantum Prolog can answer queries against such term list, just like answering against the global default database eg. binds 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 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...
There's no -/2 operator in the initial definition of lookup/3 though:
You can also see that in the first call to lookup/3 where there's no -/2.If I understand correctly, that's what the OP is asking: Where did the -/2 come from, not what it's for.
The call with the -/2 is under the heading "Refactoring the dictionary" so it's possible the author mixed up the implementations while writing the article and listed the output of an implementation that represents key-value pairs as -/2 terms.
The refactored version makes more sense btw and indeed I see the author switches to K-V later on in the article.
(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.
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...
I am actually working on a logical query language that's a successor to prolog here: https://memelang.net/02/. Any feedback appreciated!
It's a bold statement to call something a Prolog successor! Are you aiming for a general purpose logic programming language like Prolog, or targeting the use case of querying knowledge bases?
One of the draws to Prolog is its immensely simple syntax: A.R:B = true in your case would be represented as simply r(A, B).
It looks like you've elevated some set theory properties to syntax, and have added some neat sugar over chained relations. Have you found areas where this really shines as compared to writing more standard Prolog/Datalog queries? I'm afraid I couldn't see many examples on first look at your Github.
Alternative would be interesting, but successor is though provoking. Do you mean to say most all Prolog capabilities will be possible to do in Meme?
That's the goal, but please let me know if there's anything you find that you can't do.
It might be worth using standard vocabulary. For example:
> Reciprocal relations are their own inverse.
The usual word for this is "symmetric".
> Recursive relations can be chained to themselves infinitely. For example, "my ancestor's ancestor is also my ancestor."
The usual word for this is "transitive".
A reflexive, symmetric, transitive relation is called an "equivalence relation", and it can be used much like equality. It'd be nice if your language had support for this, though I don't immediately see how to add it.
This is philosophically intriguing.
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-...
Here's the hacker news post: https://news.ycombinator.com/item?id=41831735
Thanks! Macroexpanded:
Use Prolog to improve LLM's reasoning - https://news.ycombinator.com/item?id=41831735 - Oct 2024 (155 comments)
Which is strange considering how old and limited Prolog in a sense is. I wonder why no superset ever gained traction and what it would look like. I imagine it fitting somewhere in the hierarchy
Theorem Prover ⊃ SMT Solver ⊃ SAT Solver
since
Theorem Prover ⊃ Prolog
The post in OP has the following hyphothesis:
> Why Prolog? [...] Due to it's declarative nature it might be a bit easier for LLMs to generate code, because LLM doesn't need to generate precise control flow.
This is an interesting point, and my guess is that prolog is the declarative programming language with most example code out there for it to learn on(excluding SQL). Alternatively it could try to create some problem description for an automated theorem prover. My (absolute ignorant) guess is that the prolog aproach works better for two reasons:
- The amount of prolog code in the training set is higher
- It is still only able to create code for problems easy enough that prolog can handle them.
Learning curve perhaps? There doesn't have to be an overlap between people working on this and the tools you have mentioned
limited in what sense?
prolog is turing complete.
He might be thinking about the SLDNF resolution happening. But yes, you can implement any prover in prolog. This distinction is discussed a bit here: https://www.metalevel.at/prolog/theoremproving
Indeed, you can get a lot more from dependent types than Damas-Hindley-Milner inference, yet does it mean that you should use the former everywhere?
Another attractive feature of Prolog is that it’s homoiconic, like lisp.
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
or if you want to nest it.if you're the type to instead do this
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.How would you define a cyclic data structure?