3 ms·
It's Saturday and I'm on my third coffe (in a very tiny cup) so I hope you will excuse me a mini-essay to asnwer your question :) Logic programming languages l
by YeGoblynQueenne 6y ago
It's Saturday and I'm on my third coffe (in a very tiny cup) so I hope you will
excuse me a mini-essay to asnwer your question :)
Logic programming languages like Mercury adopt the syntax and semantics of the
predicate calculus, a.k.a. First Order Logic. FOL is the language of predicates,
where predicates are _relations_ between propositional terms. "Propositional"
here means that a term is a, well, propositional logic object or variable. For
example the objects "stassa" and "mercury" are propositions while the formula
"likes(stassa, mercury)" is a relation between the two (and "likes" itself is
the predicate of the relation).
Now, a "relation" is a generalisation of a function. Recall that functions are
mathematical objects that map input terms to output terms, for example the
function ƒ: X → Y maps elements of the set X to elements of the set Y.
Unlike functions, relations have no concept of "inputs" and "outputs". For
example, take "likes(stassa, mercury)". Suppose "stassa" is an element in the
set of persons (sorry) and "mercury" is an element of the set of programming
languages. The following FOL atomic formulae are both true:
∃y: likes(stassa, y)
∃x: likes(x, mercury)
More precisely, they are true given an interpretation (an assingment of truth
values to atomic formulae) that assigns the value "true" to the atomic formula
"likes(stassa,mercury)". "Atomic" just means these are the simplest kinds of
formulae in FOL syntax. The thing to keep from this is that a truth value can be
assigned to atomic formulae in FOL regardless of which argument is a variable or
a constant term.
By contrast, to implement likes/2 as a function [1] we would have
to split it in two: one function taking as input a "person" and returning a
"language" and the other taking as input a "language" and returning a "person":
ƒ₁: P → L, e.g. ƒ₁(stassa) = mercury
ƒ₂: L → P, e.g. ƒ₂(mercury) = stassa
How this translates in logic programming, and particularly Prolog, practice, is
that Prolog programs can be called with different combinations of instantiated
and non-instantiated arguments.
Here's an example (the typical example is the "append" predicate, mentioned in
the mercury site above, but this should be simpler). The "%" denotes a comment
in Prolog an the example works in Swi-Prolog:
?- length([a,b,c,d], N). % (1)
N = 4.
?- length(List, 3). % (2)
List = [_11524, _11530, _11536]
(Note that the underscored terms are variables created by the Swi-Prolog
internals).
length/2 is a Prolog predicate (a logic program) that determines the length of a
Prolog list (a linked list represented as [H|T] where H is the head element and
T is the rest of the list). The two queries above show that length/2 can be
called with either the first or second argument instantiated to a fully-ground
term (a term that has no variables) and length/2 will work in a way that makes
sense.
The first call, in (1), is made with a ground list "bound" (instantiated) to the
first argument of length/2 and with a free variable (N) as its second argument
(variables start with uppercase letters or the underscore, in Prolog). When
length/2 exits, it binds the constant "4" (an integer) to the second argument
and Prolog reports that the variable N is now bound to 4. Thus length/2 has
determined the length of the list [a,b,c,d]. The second call leaves the first
argument as a variable and binds the integer "3" to the second argument. Now
length/2 _generates_ a list of the given length. The elements of the generated
list are all free variables, a detail of the implementation of length/2.
It is also possible to call length/2 with _both_ arguments as free variables:
?- length(List, N).
List = [],
N = 0 ;
List = [_13650],
N = 1 ;
List = [_13650, _14782],
N = 2 ;
List = [_13650, _14782, _15914],
N = 3 .
In this case, length/2 generates lists of increasing length, again a detail of
its implementation ("[]" is the empty list, of length "0" and ";" asks for more
results).
Now, try to think what would happen if we made the following query; the
findall/3 predicate is used to generate all results of a predicate call:
?- findall(List-N, length(List,N), LNs). % (3)
Well, here's what happens (the output is from Swi-Prolog):
?- findall(List-N, length(List,N), LNs).
ERROR: Stack limit (1.0Gb) exceeded
What happens is that there is no limit to the number of lists of arbitrary
length that can be generated by length/2, so findall/3 continues to generate
them until the Prolog interpreter runs out of its allocated resources. Even
given infinite resources the query in (3) would never terminate- it would
continue to generate lists of increasing length for ever.
A straightforward way to avoid this situation is to avoid calling length/2 with
both arguments as free variables, at least when we want to generate all
solutions. So we could mandate that if one argument is a variable, the other one
must be bound to an at least partially ground term.
In logic programming convention, we represent these acceptable instantiations
with various notations, the most commoon of which is to use "+" to mean that an
argument must be instantiated on call, "-" to mean that an argument must be left
as a free variable and "?" to mean that either is acceptable.
For length/2, we could declare:
length(+, -).
length(-, +).
These are the "modes" in which the programmer of length/2 communicates to users
how the program can be called. We can add some additional information:
length(+, -) is det.
length(-, +) is det.
"det" meaning that the predicate is deterministic _in that mode_, where
"deterministic" means that a call of the predicate at the declared mode succeeds
once, yielding one result, or fails if a result cannot be produced given the
arguments. We could also declare the (?,?) mode as _nondeterministic_ meaning
that it generates multiple results (or fails, once):
length(?, ?) is nondet.
This last mode declaration still allows the dangerous call in (3) above, but at
least now the programmer knows to expect this.
Now, these call and determinism modes are a _convention only_ in Prolog and most
other logic programming languages, meaning that they are solely used for
documentation purposes and are not enforced by interpreters or compilers.
Mercury instead makes mode declarations a part of the syntax of the language.
The Mercury website claims that this helps to catch a lot of bugs. While I have
not actually used Mercury, I certainly agree that having no clear inputs and
outputs, or determinism constraints, is a major source of bugs in Prolog code
and enforcing mode declarations is sure to help avoid some major sources of pain
when programming in Prolog. How good is Mercury at doing that, I can't tell. As
the website says, detecting determinism is undecidable but there seem to be some
heuristics that work "often enough".
________________
[1] I'm fudging the definition of "function" between mathematical functions,
that are typically not discussed in terms of "inputs" and "outputs", or
"returns" and programming-language functions, which are. Apologies, I hope the
meaning is clear from the context.
- rajandatta 6y agoVery well done! And on a Saturday morning! :-)
- scythmic_waves 6y agoThank you! That was very informative :)
- rswail 6y agoGreat answer! I sort of almost understand what is going on and the last time I saw Prolog was literally 30 years ago.