Re: [] \= '[]' (was Re: Ann: SWI-Prolog 7.1.0)

On 27/11/2013, at 6:51 PM, Boris Vassilev wrote:

> After reading more or less carefully all emails, and Section 5 of the
> manual, can someone please answer these questions:
> 
> 1. What are the practical situations in which " [] \== '[]' " becomes a
> problem? (I don't mean existing code that assumes " [] == '[]' ", but
> rather a problem with defining a predicate doing something with lists, or
> not trying to do anything with lists.)

One important thing to remember is that not all Prolog data is
generated by Prolog, and not all SWI Prolog data is generated
by SWI Prolog.

my_write(Term) :-
    (   numbervars(Term, 0, _),
        my_write_aux(Term),
        fail
    ;   true
    ).

my_write_aux('$VAR'(N)) :- integer(N), N >= 0, !,
    print('$VAR'(N)).  % write as a variable name
my_write_aux(Term) :-
    functor(Term, F, N),
    (   N > 0 ->
	my_write_atom(F),
	my_write_aux(0, N, Term, 0'()
    ;   atom(F) ->
	my_write_atom(F)
    ;   writeq(F)
    ).

my_write_atom(A) :-
    (   put_code(0''),
        atom_codes(A, Cs),
        member(C, Cs),
        (   C == 39 -> put_code(92)
	;   C == 92 -> put_code(92)
	;   true
	),
	put_code(C),
	fail
    ;   put_code(0'')
    ).

my_write_aux(N, N, _, _) :- !,
    put_code(0')).
my_write_aux(I, N, Term, C) :-
    put_code(C),
    J is I + 1,
    arg(J, Term, Arg),
    my_write_aux(Arg),
    my_write_aux(J, N, Term, 0',).

has been a reliable way to write acyclic terms that do not use
attributed variables.  For example,

?- H = my_write_atom(_), clause(H, B), my_write((H :- B)),
|    put_code(0'.), nl.

produces

':-'('my_write_atom'(A),';'(','('put_code'(39),','('atom_codes'(A,B),
','('member'(C,B),','(';'('->'('=='(C,39),'put_code'(92)),';'('->'('=='(C,92),
'put_code'(92)),'true')),','('put_code'(C),'fail'))))),'put_code'(39))).

In particular,

?- my_write_aux([1,2,3]).

produces

'.'(1,'.'(2,'.'(3,'[]')))

By the way, these lines:
'.'(1,'.'(2,'.'(3,'[]')))
':-'('my_write_atom'(A),';'(','('put_code'(39),','('atom_codes'(A,Cs),','('member'(C,Cs),','(';'('->'('=='(C,39),'put_code'(92)),';'('->'('=='(C,92),'put_code'(92)),'true')),','('put_code'(C),'fail'))))),'put_code'(39))).
which read just fine into SWI Prolog 6, were in fact generated
by Smalltalk code.  About 150 SLOC for output.  Input is simplified
if you don't have to worry about list syntax.

Now, there's no compelling reason to do this in Prolog,
because we have write_canonical/1.  But I have C code,
Smalltalk code, Scheme code, and even AWK code doing pretty
much this.  I don't worry about the fine points of Prolog
syntax.  EVERY atom gets quoted whether it needs it or not.

By the way, these lines:
'.'(1,'.'(2,'.'(3,'[]')))
':-'('my_write_atom'(A),';'(','('put_code'(39),','('atom_codes'(A,Cs),
','('member'(C,Cs),','(';'('->'('=='(C,39),'put_code'(92)),';'('->'('=='(C,92),
'put_code'(92)),'true')),','('put_code'(C),'fail'))))),'put_code'(39))).
which read just fine into SWI Prolog 6, were in fact generated
by Smalltalk code.  About 150 SLOC for output.  Input is simplified
if you don't have to worry about list syntax too.

> 2. In "plain" Prolog, is there any other compound term treated like a list
> is (compound terms are all equal, I guess, but lists are definitely more
> equal)? My main conceptual problem with lists (at the beginning) was that
> the properties and uses of lists really did not seem to necessitate them
> being defined like they were: " .(a, .(b, ..., []))".

Except for syntax, EVERY compound term is treated like a list pair.
Some Prolog implementations store (.)/2 terms specially compactly,
taking just 2 machine words.  Some don't.  However, this is semantically
invisible.  There is nothing *semantically* special about lists whatsoever.
(There are a few built-in predicates that accept and/or generate lists,
just as there are a few built-in predicates that accept arithmetic
expressions.)

The properties and uses of lists are those consistent with the
definition

:- type list(T)
   ---> '[]'
      ; '.'(H, list(T)).

and no others.  They act just the way anyone used to F#, ML,
Haskell, or Clean would expect, modulo issues of laziness
-vs- strictness and logical terms with variables -vs- ground terms,
and are so similar to the way things were done in Lisp and Pop-2
that people experienced in Lisp and Pop-2 had few or no surprises.
At Edinburgh, the Lisp and Pop-2 manuals were on the same shelf
as the Prolog manual, and the DEC-10 Prolog developers were
thoroughly familiar with Lisp and Pop-2.  The Marseilles Prolog
inventors, who started it, were certainly familiar with Lisp.

Historically, '.' was an xfy operator of precedence 600, so that
[a,b,c] = a.b.c.[].  (One reason for old-timers to be unhappy
about dots in names.)

By the way, one of the things that has caused a lot of confusion
is the fact that dots _are_ allowed in unquoted atoms but _not_
in variables, so that x.y is an atom but X.Y is a syntax error.
I don't think this has ever made sense to anyone.
> 
> To rephrase, I see how list properties (and operations on lists) follow
> directly from them being defined as they were, but I don't see how why
> lists *must* have this particular representation.

Ever since 1959, lists in functional languages have been visibly
made out of pairs in a singly-linked style.

*Sequences* don't have to have that particular representation.
You could perfectly well represent a sequence as

:- type seq(T)
   ---> empty
      ; unit(T)
      ; even(seq(T), seq(T))    % in even(X,Y) X and Y must be same size not empty
      ; odd(seq(T), T, seq(T))  % in odd(X,_,Y), ditto.
      .

E.g., <1,2,3> => odd(unit(1),2,unit(3)).

But to be *called* a list in the functional world, it has to be
suitable for incremental construction and processing (which the
usual lists are and the seq/1 type above is _not_).

The great thing about lists being _only_ special syntax,
_not_ special semantics, is that if you don't like this representation,
you don't have to use it.  You can make your own sequence representation
and use that.

> These questions are really in good faith, I see that there is quite a bit
> of excitement about the changes to lists in particular and SWI-Prolog in
> general and I am trying to understand the exact reasons.

As I see it, the change to the empty list
 - is gratuitously incompatible with the ISO standard
 - does break working code (not all of it in Prolog!)
 - does NOT offer any significant benefit to ordinarily
   careful programmers (defined here as ones who do not
   go out of their way to use defaulty data structures)
 - makes a fairly unhelpful distinction for the sake of
   one admittedly common data structure while FAILING to
   make the same distinction for any other.

For example, there is no proposal to make {} not be an atom.
In Erlang, which uses Prolog-based syntax, [] and {} are
atomic but not atoms.  So why not make {} a non-atom in Prolog?
Why not make {T1,...,Tn} a distinct data type which really is
the tuple it looks like?  It _is_ in Erlang, and was in Poplog.
And it would be a much better fit to JSON arrays than lists are.
And it would ease communication with Lisp.  And ...