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
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.
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.
It starts out pretty easy but gets harder and requires more thought. It has different sections on things like list processing or graph problems.
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.
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.
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.)
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.
And I suspect that Prolog's Partial Instantiation is, while not mutating data, but it is mutating references somewhere
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 = (++)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.
?- 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.> 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.
[ 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).
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.
Honestly, the language is super small. Best way to learn IMO is to go on https://swish.swi-prolog.org/ and do the examples / play with it. If you stick to it, then you can branch to other engines later (there are many systems with unique features).
> 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.
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.
[1] https://shchegrikovich.substack.com/p/use-prolog-to-improve-...
Use Prolog to improve LLM's reasoning - https://news.ycombinator.com/item?id=41831735 - Oct 2024 (155 comments)
Theorem Prover ⊃ SMT Solver ⊃ SAT Solver
since
Theorem Prover ⊃ Prolog
> 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.
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.