Re: Ann: SWI-Prolog 7.1.0

The discussion below (I've snipped some) is very valuable for 
every programmer to understand.  To explain slightly (because 'defaulty'
isn't a self-evident term):

The idea is that if your datastructure uses named compounds to distinguish 
the possible content options, then you never have to write code that
goes 
foo(X) :- atom(X), !, ....
Instead you write
foo(word(X)) :- ....
and Prolog generates code without choicepoints and the code itself is 
easier to read and write. 

This argument demonstrates that atom(X) and empty_list(X) are unneeded in 
well-designed code.  However, I fail to see the argument that atom([]) 
is essential or good and not just a historical relic.

Alan Baljeu


----- Original Message -----
From: Richard A. O'Keefe <[email protected]>
To: Prolog mailing list <[email protected]>
Cc: 
Sent: Tuesday, November 26, 2013 9:55:28 PM
Subject: Re: [SWIPL] Ann: SWI-Prolog 7.1.0


On 24/11/2013, at 5:39 AM, Jan Wielemaker wrote:
> In practical programming, you have cases where you have a list of
> `tokens' (atoms) and you want to explode some tokens or other special
> symbols into a sequence. The clean way is to use DCGs or difference list
> to create a nice and flat holding the expansion. In some cases however,
> it is way simpler if you can just explode the objects into lists, so you
> get [ 'The', [quick, brown, fox], jumps, over, the, [lazy dog] ].

Producing that kind of data structure would be exceedingly bad Prolog
style *whatever* the empty list is represented as.  It's the kind of
data structure design that "The Craft of Prolog" calls "defaulty".
Here elements are classified as "lists or non-lists".  (Or should
we say "owned by the emperor vs tremble as if mad".)  The hell of
that is that if an element isn't instantiated yet you can't _tell_
what it is going to be.  With *good* design, every possibility gets
its own distinct tag:

thingy = word(atom) | phrase(list(thingy))

e.g.

  phrase([word('The'),
          phrase([word(quick),word(brown),word(fox)]),
          word(jumps),word(over),word(the),
          phrase([word(lazy),word(dog)]) ]).

We can flatten that in perfect safety:

thingy_words(word(X)) --> [X].
thingy_words(phrase(L)) --> thingy_phrase(L).

thingy_phrase([]) --> [].
thingy_phrase([X|Xs]) --> thingy_words(X), thingy_phrase(Xs).

This works even if some of the words are still unbound variables.
The defaulty approach does not.

We can with some caution adopt a different definition:

thingy = word(atom) | [] | [thingy|thingy].

-- note that this naturally and reasonably allows [word(so)|word(there)],
constant-time concatenation just like Erlang iolists.  It simply is not
the case that all, or even all reasonable, uses of [_|_] are for lists,
anymore than that all, or even all reasonable, uses of [] are for lists.

thingy_words([]) --> [].
thingy_words([A|B]) --> thingy_words(A), thingy_words(B).
thingy_words(word(X)) --> [X].

[word('The'),[word(quick),word(brown),word(fox)],
word(jumps),word(over),word(the),[word(lazy),word(dog)]]

Here again, each possibility for a thingy is flagged by a
different functor: word/1, '[]'/0, or '.'/2.  There is no
way to mistake them, EVEN IF SOME OF THE WORDS ARE STILL
UNBOUND VARIABLES.

Non-defaulty data structures are good for efficiency because
you get fewer choice-points created and need fewer cuts.

With the defaulty version,

thingy = atom | [] | [thingy|thingy]

there _is_ an ambiguity between atoms and [] and worse still
there is an ambiguity between unbound variables and everything
else.  So you have to write

thingy_words(X) --> {var(X)}, !, ... what the heck goes here? ...
thingy_words([]) --> !.
thingy_words([A|B]) --> !, thingy_words(A), thingy_words(B).
thingy_words(W) --> {atom(W)}, [W].

If you design your data structures well, you never *care*
whether [] is an atom or not except when you are writing
meta-level code, in which case you care that it *is*.
If you design defaulty data structures, nothing will save you.