Terminology for A-B-C

See: SWI-Prolog Glossary

Prolog has Structure or Compound, e.g. a(1,2,3)
Some will cause this a tuple, (1,2,3)

What would this be called 1-2-3, or A-B-C?


This came about in writing some test cases for bagof/3 and order_by/2.


EDIT

After reading this StackOverflow answer by Paulo Moura it is a compound with functor - and arity 2. The arity 2 seems wrong. :thinking:

?- functor(A-B-C,Functor,Arity).
Functor =  (-),
Arity = 2.

?- functor(1-2-3,Functor,Arity).
Functor =  (-),
Arity = 2.

?- functor((1,2,3),Functor,Arity).
Functor =  (','),
Arity = 2.

?- functor([1,2,3],Functor,Arity).
Functor = '[|]',
Arity = 2.

?- functor(group(1,2,3),Functor,Arity).
Functor = group,
Arity = 3.

?- functor(group(1|2|3),Functor,Arity).
Functor = group,
Arity = 1.

?- functor(group(1-2-3),Functor,Arity).
Functor = group,
Arity = 1.
?- write_canonical((1,2,3)).
','(1,','(2,3))
true.

?- write_canonical((1-2-3)).
-(-(1,2),3)
true.

?- write_canonical([1,2,3]).
[1,2,3]
true.

?- write_canonical((1|2|3)).
'|'(1,'|'(2,3))
true.

?- write_canonical(group(1,2,3)).
group(1,2,3)
true.

?- write_canonical(group(1-2-3)).
group(-(-(1,2),3))
true.

?- write_canonical(group(1|2,3)).
group('|'(1,2),3)
true.
?- current_op(Priority,Type,'|').
Priority = 1105,
Type = xfy.

?- current_op(Priority,Type,,).
Priority = 1000,
Type = xfy.

?- current_op(Priority,Type,-).
Priority = 200,
Type = fy ;
Priority = 500,
Type = yfx.

EDIT

Jan B. had the answer to The arity 2 seems wrong. :thinking:, but then erased it.

?- functor(a-b-c-d-e,Functor,Arity).
Functor =  (-),
Arity = 2.

?- write_canonical(a-b-c-d-e).
-(-(-(-(a,b),c),d),e)
true.

You find this terminology:

A-B, 1=2, etc…: Pair
A-B-C, 1+2+3, etc…: Triple
Etc…

https://en.wikipedia.org/wiki/Tuple#Names_for_tuples_of_specific_lengths

For example variable_names/1 read write option uses
(=)/2 to form pairs, while keysort/2 uses (-)/2 to form pairs.
Everything above pairs is a little inefficient in unification,

since it uses multiple functors. So instead of A-B-C with two
binary compounds, maybe better use a single compound
a(A,B,C). Unless you often call (=…)/2, you might then

even want to use a list [A,B,C] instead, which blows up the
number of binary compounds to three.

TL;DR: Python has tuples, Prolog does not. Use a list like [a, b, c] (nested term, uses up more space, accessing arbitrary element means traversal); or use a named compound term like:

'What should I call it? Choices, choices...'(a, b, c)

You have to use arg/3 to get to an element. The third (better for some use cases?) option is dicts: you don’t have to name the structure, you can name the arguments, and arbitrary access does not traverse.

EDIT: well, there is also library(record) which I guess was superseded by dicts for most use cases, but it is still there and I guess it fills a niche?


Many languages have tuples of some sort. Python has (1, 2) which is a pair and (1, 2, 3) which is a triple and so on. My memories are vague but certainly Haskell has something of that kind too, as well as many other languages. Notably, C does not have that: you either have to use a struct or an array.

A “tuple” like that is:

  1. “anonymous” and
  2. “flat”.

“Anonymous” means it is only structure, it doesn’t need a name and it doesn’t need to be declared in any way. “Flat” means that its elements can be addressed as if it was an array, using indices. So this is (if I remember correctly) perfectly good Python and it should give you b:

>>> ('a', 'b', 'c')[1]

This has interesting side effects. One is that you will see a lot of code (on Stackoverflow…) which looks like:

[(1, 2), (3, 4), ...] % look, a list of pairs!

or maybe

X = (1, 2, 3) % I made a tuple with three elements!

Another side effect is that since a-b is a “pair”, it logically follows that a-b-c is a flat triple. Well, it isn’t :slight_smile:

Thank you for the nice overview. When I was still very green when it came to Prolog I dared to suggest (not sure where, a mailing list or maybe some Stackoverflow QA?) that a Prolog list might be implemented as the implementation wishes. I thought that the interface with List = [Head|Tail] and difference lists and so on does not prohibit that.

Well, I was chastised for even suggesting it :slight_smile:

We are drifting quite far off topic, but anyway…

Why would you need two different kinds of lists and multiple dispatch for that? To me it seems that you need a unification algorithm that somehow handles lists as if they were the usual nested structure with [] and .(Head, Tail).

The “somehow” above is of course the difficult part. But is it impossible?

From my narrow angle, it seems like it is not impossible to do it, as long as the list is not “transparent” (so you cannot directly work with the nested term, you can only access it through the square brackets/comma/pipe).

But I cannot at all judge whether this is at all a good idea and what it mean in practice to implement it, or why should anyone bother.

You need at least two types [_|1_] and [_|2_] for open ended and closed lists. [1,2,3] is a closed list, you might want to represent it as an array. But what about [H|T], its an open list? Well you could store open lists also as array, but with a special meaning of the last array element.

Similar considerations would apply to open/closed dicts, but SWI-Prolog has closed dicts natively. Unification for open/closed dicts would also lead to an explosion into 4 cases. But you additionally need two accumulators for the the difference in attribute names. So temporarily your unification routine

would even have more state than usual. You can view such things as unification modulo a theory. If its an equational theory, it would be E-unification. I dont know whether E-unification was ever used for non-functional requirements, such as compact representation of lists,

you also need first a system that can do E-unification or some such. A priorized set of equations might then do what multi-dispatch would do.

Edit 22.07.2020:
Some unification modulo theory axioms, if we would use index+tuple for closed lists, like in the DCG example. I am assuming that arg/3 fails if the index is above the tuple arity:

[H|T] = (N,C) <=> arg(N, C, H), M is N+1, T = (M,C).
(N,C) = [H|T] <=> arg(N, C, H), M is N+1, (M,C) = T.
(N,C) = (P,D) <=> arg(N, C, H), M is N+1, arg(P, D, H), Q is P+1, (M,C) = (P,D).

Just toying around.

1 Like

If you’re playing around with list representations:


http://www.bitsavers.org/pdf/xerox/parc/techReports/CSL-79-7_Compact_Encodings_of_List_Structure.pdf

Also, Python has done a lot of work on improving hash tables (which they call “dicts”) and to a lesser degree arrays, because they’re so core to the implementation (basically, Python is hash-tables-all-the-way-down with syntactic sugar).

I’ve seen people represent “anonymous” tuples like this: '.'(A,B,C) or ''(A,B,C).

?- X = ''(a,b,c), arg(2, X, Z), X = ''(A,_,_).
X = ''(a, b, c),
Z = b,
A = a.

I don’t particularly like dicts with an uninstantiated variable for the tag, so I sometimes do this when I can’t think of a good name for an “anonymous” dict: ''{a:1, b:2}.
Note that {a:1,b:2} might not be what you expect:

?- format('~k~n', [{a:1,b:2}]).
{','(:(a,1),:(b,2))}

?- functor({a:1,b:2}, A,B).
A = {},
B = 1.

?- {a:1,b:2} =.. F, format('~k~n', [F]).
[{},','(:(a,1),:(b,2))]
F = [{},  (a:1, b:2)].

?- format('~k~n', [(a,b,c)]).
','(a,','(b,c))

ECLiPSe Prolog uses [] for arrays/tuples. Like for example:

Vector [1,2,3] becomes [](1,2,3).
Matrice [[1,0],[0,1]] becomes []([](1,0),[](0,1)).
Etc…
http://eclipseclp.org/doc/bips/kernel/termmanip/array_list-2.html

But not all Prolog systems can parse [] and allow it as a functor,
although this would be ISO compliant, since [] is just an atom.
So '' is the more portable easier solution.

BTW: SWI-Prolog could do the ECLiPSe thingy:

Welcome to SWI-Prolog (threaded, 64 bits, version 8.3.3)

?- X = [](1,2,3), functor(X, F, A).
X = [](1, 2, 3),
F = [],
A = 3.

Edit 22.07.2020:
I guess the LISP cdr coding is found in a couple of Prolog systems.
It would make binary list cells smaller and can mimic the (N,C)
coding. Instead of an argument index N and a compound C, you
would have a pointer into the compound.

If your Prolog system supports cdr coding, then also some
operations like for example (=..)/2 can become no-ops, they wont
do much as a destructor. You can just point into the compound after
the functor, and you would have the closed list.