listsyntaxprologoperatorsswi-prolog

What exactly is the vertical slash function in PROLOG? Is it an operator?

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:

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?

Solution

  • 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,[]))