Re: Ann: SWI-Prolog 7.1.0

On 24/11/2013, at 5:39 AM, Jan Wielemaker wrote:
> 
> There are several typical cases. One concerns that you map data from a
> language that can uniquely identify lists from symbols, such as JSON.

This is untrue.  THERE ARE NO SYMBOLS WHATEVER IN JSON.

The question of distinguishing [] from '[]' DOES NOT ARISE in JSON
because there isn't anything even remotely like '[]' in JSON.

> Such languages cannot be mapped naturally to Prolog because it is
> unclear whether [] is some kind of identifier or an empty list.

"Such languages"?  You must have something other than JSON in mind.
What?  Javascript doesn't have symbols either.  Ruby _does_, and
	>> [].class
	=> Array
	>> :[].class
	=> Symbol
	>> :[].id2name
	=> "[]"
But of course, Ruby has a huge range of data types that cannot be
mapped into Prolog at all (such as Enumerator, or Set), so there
are _far_ worse problems than [] in such mapping.  To the extent
that such mapping problems can be solved, they are solved like
this:
:- type ruby
   ---> symbol(atom)
      | integer(integer)
      | float(float)
      | string(string) % whatever a string might be
      | array(list(ruby))
      | set(list(ruby))
      | hash(list(pair(ruby,ruby)))
      | ...
so that the Array [] is mapped to array([]) and the
Symbol :[] is mapped to symbol('[]').
*THIS* is what a "natural" mapping from a richer language
to Prolog looks like.  Whether [] == '[]' is *never* an
issue if you do it right, because the mapping encodes the
source language distinctions *explicitly*, so that you
can work with the foreign data using PATTERN MATCHING,
not type tests which are necessarily going to be inadequate
*somewhere*.


> Another
> are expressions such as consult([]), which may mean to consult the file
> '[].pl' or consult nothing.

DEC-10 Prolog ran under TOPS-10, and later TOPS-20.
In neither operating system was "[]" or "[].pl" a *possible*
file name.  It was obvious to all DEC-10 users that this
could only mean to consult nothing.

If DEC-10 Prolog had been designed in a UNIX milieu,
consult/1 would have been designed differently.

> Same for format("", []) with double quotes
> set to 'codes': does this write '' (nothing) or '[]'?

It writes nothing.  

> 
> 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.

> This is all fine, until '[]' may appear as a token in the list.  In that
> case, flatten/2 just removes it.  Due to the ambiguity of the empty list,
> creating a multi list and call flatten/2 is considered bad programming.
> Without this ambiguity, using multi lists is safe

If you are using Prolog as a clumsy and limited Scheme, yes;
if you are using Prolog as a *logic* programming language, no.

> and can be a handy
> solution, in particular for the not-so-experienced Prolog programmer.

No, it can be a deadly trap for the not-so-experienced Prolog
programmer, seducing her into writing non-logical and inefficient
code.  Improving the perfume of the Upas tree is no kindness.

It is so *simple* to write Prolog in a style in which the
vaunted "ambiguity" is irrelevant.

And there are so *many* data structures one wants to design,
unrolled lists (http://www.cs.otago.ac.nz/staffpriv/ok/Ursl.hs
and also the Clean 1.3 version Ursl.{dcl,icl}), trees of
various sorts, where the terminal case IS AN ATOM.  It is
*normal* in Prolog for the terminal case of a recursive
data structure to be an atom.  There is NOTHING special about
lists.  Creating a difference for lists makes the language
MORE COMPLICATED and harder to understand.

Scheme is irrelevant here because Scheme practice doesn't
use sum-of-products algebraic data types.  Scheme programs
cannot rely on data being distinguished by a principal
functor because Scheme doesn't *have* principal functors.
Prolog does, which is why it is quite simply *WRONG* to make
the empty list not be an atom.  It doesn't matter terribly
much _which_ atom it is; if you rename '.'/2 to '$cons'/2
you could probably get away with renaming '[]/0 to
'$nil'/0.  But in order to be consistent with the way other
ADTs work in Prolog, the distinction between empty and
non-empty lists *HAS* to be the same kind of distinction
as the distinction between empty and non-empty trees, namely
a difference of principal functor, with nothing unusual
about the functors per se.


There is a theme here.
A naïve encoding of information into Prolog terms that *looks*
good or "natural" is not always, indeed, not often, an
encoding that *works* well or "naturally" in processing.
It isn't at all hard to stop being naive; all you have to
learn is "if there are two or more possibilities for the
information at a particular point, give each its own explicit
functor".  That's it.

And yes, I do mean that if I want to represent arithmetic
expressions *for processing*, I would use

:- type exp
   ---> number(number)
      | exp + exp
      | exp - exp
      | ...

even though a number can't be anything else.  It makes the
code to _work_ with expressions so much simpler.  It's not
as pretty for human consumption, so you write something
that *converts* from human-oriented form to processing-
oriented form on input and does the opposite on output.
And then you get other benefits, like the ability to plug
in multiple external syntaxes, so you can read in Lisp
style and write out Javascript style, without changing your
processing code at all.