0

while reading the documentations and testing examples of SWI PROLOG implementation I began to go deeper into lists. PROLOG lists are no different from most languages: it has a Head and a Tail.

I then learned that SWI PROLOG lists can be expressed like this:

  • [ Head | Tail ]

The syntax is pretty simple, square brackets with a head and a tail, separated by a vertical slash |.

Then I started wondering: what is the meaning (the semantics) of the vertical slash | in PROLOG?

I know that the vertical slash is indeed a special character, but why does it necessarily have to be a vertical slash? Is it an operator? Is it used for system or language (meta) applications? What is its specific function in the language?

NickS1
  • 496
  • 1
  • 6
  • 19
  • 1
    `|` itself is not an operator, `[|]` is. If you are familiar with any lisps, it is equivalent to `cons`. https://en.wikipedia.org/wiki/Cons – rajashekar May 12 '21 at 04:25
  • 2
    Yes, `|` is an operator. Check it out here: https://www.swi-prolog.org/pldoc/doc_for?object=op/3. – TA_intern May 12 '21 at 12:56
  • 2
    _Au contraire_, @rajashekar: `|` is just an operator. Try `current_op(Precedence, Type, '|'). You don't _have_ to use it for lists (but if you did, you'd likely confuse the heck out of anybody else looking at your code.) – Nicholas Carey May 12 '21 at 17:45
  • `|` is a (vertical) bar. It serves as a head tail separator and as an operator. – false May 13 '21 at 11:25
  • Hmm, so `|` is also a deprecated `;/2` https://www.swi-prolog.org/pldoc/doc_for?object=%27|%27/2 . – rajashekar May 14 '21 at 04:48
  • Very interesting information about deprecation! – NickS1 Aug 10 '21 at 19:52

2 Answers2

2

Yes, | is a right-associative infix operator of precedence 1105, right-associative meaning that an expression like

 a|b|c|d

binds as

'|'( a , '|'( b , '|'( c , d ) ) )

rather than the left-associative binding

'|'( '|'( '|'( a , b ) , c ) , d )

It is part of Prolog's syntactic sugar for list notation. In Prolog, any non-empty list, has a single item that is denoted as its head, and the remainder of the list, itself another list (which may be empty), denoted as the tail. (A rather nice recursive definition, eh?)

So one can easily partition a list into its head and tail using |. So

[Head|Tail] = [a,b,c,d]

results in

Head = a
Tail = [b,c,d]

From my answer here,

Prolog's list notation is syntactic sugar on top of very simple prolog terms. Prolog lists are denoted thus:

  1. The empty list is represented by the atom []. Why? Because that looks like the mathematical notation for an empty list. They could have used an atom like nil to denote the empty list but they didn't.

  2. A non-empty list is represented by the term .\2, where the first (leftmost) argument is the head of the list and the second (rightmost) argument is the tail of the list, which is, recursively, itself a list.

Some examples:

  • An empty list: [] is represented as the atom it is:

      []

  • A list of one element, [a] is internally stored as

      .(a,[])

  • A list of two elements [a,b] is internally stored as

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

  • A list of three elements, [a,b,c] is internally stored as

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

Examination of the head of the list is likewise syntactic sugar over the same ./2 notation:

  • [X|Xs] is identical to .(X,Xs)

  • [A,B|Xs] is identical to .(A,.(B,Xs))

  • [A,B] is (see above) identical to .(A,.(B,[]))

Nicholas Carey
  • 71,308
  • 16
  • 93
  • 135
  • 1
    Rather, `s/'|' d/d/ ` – false May 12 '21 at 20:02
  • Sorry for my ignorance, but I don't understand what "right-associative" and "left-associative" bindings are. I know that association is a property that can be used in logical propositions. Is this the idea? Is it like a precedence order? What does it change in practice? – NickS1 May 14 '21 at 01:08
  • 1
    _Right-associative_ operators bind to the right, so `a|b|c|d` is parsed as if it were `a|(b|(c|d))`; _left-associative_ operators bind to the left, so `a|b|c|d` is parsed as if it were `((a|b)|c)|d`. – Nicholas Carey May 14 '21 at 01:45
  • 1
    But it is just an operator: it doesn't actual _do_ anything, except in the context of list notation. Except create terms. Outside of list notation, an expression like `a|b` just creates the term `'|'(a,b)`. – Nicholas Carey May 14 '21 at 01:47
  • 1
    Oh, now I understand. Thank you SO much for clarifying it! Now it makes total sense, thank you @NicholasCarey – NickS1 May 14 '21 at 20:14
  • 1
    Thank you for your answers and contributions, reading the information you shared made me understand things deeper. – NickS1 Aug 10 '21 at 19:49
0

There seems to be a bit of confusion b/w the usage of vertical bar | generally used in list pattern matching and the |/2 operator.

I am not familiar with other prologs so this might be swi-prolog specific. Help for '|' states the following:

help('|').
:Goal1 | :Goal2
    Equivalent to ;/2. Retained for compatibility only. New code should use ;/2.

So, the | used in list notation is not this operator.

?- X = '[|]'(1, []).
X = [1].

?- X = '|'(1, []).
X =  (1| []).

?- [1] = '|'(1, []).
false.

?- [1] = '[|]'(1, []).
true.

As seen above using just | only creates a compound term and not a list.

Following uses Univ =.. and makes it more clear.

?- X = '[|]'(a, '[|]'(b, [])).
X = [a, b].

?- [a, b, c] =.. X.
X = ['[|]', a, [b, c]].

?- deep_univ([a, b, c, d], X).
X = ['[|]', a, ['[|]', b, ['[|]', c, ['[|]', d, []]]]].

I have used deep_univ/2 from here

rajashekar
  • 3,460
  • 11
  • 27