From ok@hermes.otago.ac.nz  Tue Jan 25 00:44:35 2000
Received: from hermes.otago.ac.nz (hermes.otago.ac.nz [139.80.32.49])
	by swi.psy.uva.nl (8.9.3/8.9.3) with ESMTP id AAA23858
	for <prolog@swi.psy.uva.nl>; Tue, 25 Jan 2000 00:44:33 +0100 (MET)
Received: (from ok@localhost)
	by hermes.otago.ac.nz (8.9.3/8.9.3) id MAA11037;
	Tue, 25 Jan 2000 12:44:29 +1300 (NZDT)
Date: Tue, 25 Jan 2000 12:44:29 +1300 (NZDT)
From: "Richard A. O'Keefe" <ok@hermes.otago.ac.nz>
Message-Id: <200001242344.MAA11037@hermes.otago.ac.nz>
To: p.singleton@keele.ac.uk, prolog@swi.psy.uva.nl
Subject: Re: [Fwd: abolish/1 in 3.3.0]

I wrote:
	
	>  4. It just "feels" wrong.  Atoms are *symbolic*; it's the *identity* of
	>     atoms that matters, not their *spelling*.  Strings are *textual*;
	>     it's their *spelling* that matters, not their identity, for they have
	>     none.
	
Paul Singleton replied:
	Surely atoms and character-code lists are two alternative
	implementations of the same abstract type?
	
NO.

I offer you the following reductio ad absurdum.

    Given a sequence <Cn,...,C1> of character codes drawn from
    a set of B distinct characters,
    define N(<Cn,...,C1>) = 
       sum from i = 1 to i = n of (Cn + 1) * B**(i-1)

This defines a bijection between character strings and non-negative
integers.

By Paul Singleton's argument, we would have to accept non-negative
integers as an "alternative implementation of the [string] abstract type".

That's something I am unwilling to do.

Remember, an abstract data type is *NOT* just a set of values,
it's a set of values *plus* a set of operations.

Atoms and character lists do *not* have the same set of operations.

In fact, in DEC-10 Prolog, they didn't quite have the same set of
values either.
    :-	String = "01",
	name(Atom, String),
	atom(Atom).
fails.  Why?
    :-	String = "01",
	name(Atom, String),
	name(Atom, String).
fails too.  Why?

There's an even more obvious way in which they fail to have the same
set of values.  Let's imagine you are dealing with a cross-word puzzle.
The clue might be
	A thin rope to hang thoughtless programmers? (6)
and you might know that the first letter is an S and the last letter
is a G.  A chars like [0'S,_2,_3,_4,_5,0'G] will do the job nicely.
There is NO way to do that with an atom.  You could only reasonably
call atoms an alternative representation if they could represent the
same things!

Remember, the people who designed DEC-10 Prolog, and the people who
worked on Quintus Prolog, knew about and had some experience with Lisp.
We remembered the *nightmare* of working with Lisp systems that used
symbols to represent characters

name/2, or rather, atom_chars/2 (which name I invented; the _chars
suffix was invented by me specifically for the purpose of referring
to a list of numeric codes) states a relationship between atoms
and strings.  That's the *only* way that atoms and strings are
connected at all.

	Both are immutable, hence are better seen as values, not objects.
	
	In this view, neither has "identity", only equality.
	
This misses my point completely.
Let us temporarily put atom_chars/2 aside.
In pure logic programming, the only operation of interest on
atoms is (=)/2.  Replacing `thomas' by `thomasina' has no effect
on the behaviour of the program as long as `thomasina' was not
already in use.
In a pure logic programming language equipped with arithmetic,
the same is not true of integers.  You cannot replace one number
by another without also changing all the arithmetic relations
to maintain the same algebraic properties.
Even without arithmetic, you again cannot replace one list with
another arbitrarily.   [t,h,o,m,a,s] has length 6 and
[t,h,o,m,a,s,i,n,a] does not.

DEC-10 Prolog has name/2 and compare/3.  Quintus Prolog added
atom_chars/2.

THESE PREDICATES WERE WIDELY FELT TO BE WARTS ON THE LANGUAGE,
as bad as or even worse than I/O, because they touched _every_
part of the language.


	Which you use depends on which operations are more common:
	
	  if you mostly compare for equality, then the costs of the dictionary
	  scheme (internment and garbage collection) are probably worth paying
	
That's "interning", not "internment".

	  if you often want to decompose them, then the costs of the "chars"
	  representation may be worth paying
	
	  if you generate lots of them, e.g. retrieving fields from databases,
	  then the chars repn may be cheaper overall, even though comparison
	  is expensive
	
	(Other schemes are feasible which may suit the third case better.)
	
It's useful to distinguish _unification_ (looking for equal or not equal)
from _comparison_ (checking the term total order), because they have
different costs.

Some logic programming language implementations had a hack in unification
that if two terms were found to be identical (unify without binding any
variables) one of the pointers is bent to point to the other copy.  In
the long run, that makes character list unification fairly cheap too.

The crucial point is that atoms are supposed to be ATOMIC.
For REFLECTION purposes you are provided with means for composing them
and taking them apart.  But implementors are under no obligation to
make the reflection operations particularly fast.

	Some programmers may prefer to use the atom ADT throughout an
	application, despite its inefficiency in some respects, in the
	belief that it contributes to overall simplicity.

I searched for simplicity and elegance in Prolog for years, hence the
book.  Some programmers may well have such a belief, but that is not
at all the same as saying that the belief is ever _justified_.

Prolog atoms were never _intended_ to be an ADT for strings.

	I.e. there
	may be a stylistic rationale for using the "wrong" ADT.
	
I'm about to describe the only good reason I know for doing the
wrong thing.


	I think I'm arguing that both implementations should support the
	same interface, e.g.
	
	    atom_length/2      chars_length/2
	    atom_member/2      chars_member/2
	    atom_append/3      chars_append/3
	    atom_to_term/2     chars_to_term/2
	    etc.               etc.
	
	in the name of orthogonality, and in the interest of simplifying
	migration from one scheme to another.
	
chars_length/2, chars_member/2, chars_append/3 are of course just
length/2, member/2, and append/3.

I wish the Quintus manuals were freely available on the Web.  I'd like
to see some of my designs live on.  One of the designs I am still
pleased with is the way I handled substrings in library(strings).

I did the port of Quintus Prolog to Xerox Lisp Machines (1108, 1109,
1185, 1186; lovely little machines and I'd still give you thank-you
for one of them).  An important part of this was that we had to
interoperate with Lisp.  In particular, what were we going to do
with Lisp strings?  Were we going to do anything useful with them at
all?

In this case, we were talking about a Prolog system with a data
type (Lisp string) that *was* by design a string representation.
So we had

	atom_chars(?Atom, ?Chars)
	number_chars(?Number, ?Chars)
	string_chars(?String, ?Chars)
	atom_string(?Atom, ?String)
	number_string(?Number, ?String)
	char_atom(?Char, ?Atom)
	char_string(?Char, ?String)

	compare_strings(?Order, +Text1, +Text2)
	compare_strings(?Order, +Text1, +Text2, +PadChar)
	
	concat(?Text1, +Constant2, ?Text3)
	 Text1 and Text3 are both atoms or both strings,
	 atomic(Constant2), name(Text3)=name(Text1)++name(Constant2)
	string_append(?TextA, ?TextZ, ?TextAZ)
	 the texts are all atoms or all strings
	concat_atom(+ListOfConstants, -Atom)
	concat_atom(+ListOfConstants, +Separator, -Atom)
	concat_string(+ListOfConstants, -String)
	concat_string(+ListOfConstants, +Separator, -String)
	concat_chars(+ListOfConstants, -Chars)
	concat_chars(+ListOfConstants, +Separator, -Chars)

	string_size(+Text, -Length)	% fails if Text not atom or string
	string_length(+Text, -Length)	% errs if given bad Text

	string_char(?Index, +Text, ?Char) % 1 origin
	nth_char(?Offset, +Text, ?Char)   % 0 origin, compatibility

	midstring(ABC, B, AC, LenA, LenB, LenC)
	midstring(ABC, B, AC, LenA, LenB)
	midstring(ABC, B, AC, LenA)
	midstring(ABC, B, AC)
	 <-> ABC, B, AC are all strings or all atoms
	   & ABC = A++B++C & AC = A++C for some A, C
	   & string_length(A, LenA)
	   & string_length(B, LenB)
	   & string_length(C, LenC)
	   All +ABC ?B ?AC or -ABC +B +AC

	substring(+ABC, ?B, ?LenA, ?LenB, ?LenC)
	substring(+ABC, ?B, ?LenA, ?LenB)
	substring(+ABC, ?B, ?LenA) % actually called string_search/3
	substring(+ABC, ?B)        % didn't exist but should have
	 <-> ABC and B are both strings or both atoms	
	   & ABC = A++B++C for some A, C
	   & string_length(A, LenA)
	   & string_length(B, LenB)
	   & string_length(C, LenC)
	   
	subchars(+ABC, ?B, ?LenA, ?LenB, ?LenC)
	subchars(+ABC, ?B, ?LenA, ?LenB)
	subchars(+ABC, ?B, ?LenA) % didn't exist but should have
	subchars(+ABC, ?B)        % didn't exist but should have
	 <-> ABC is a string or atom, B is chars
	   & ABC = A++B++C for some A, C
	   & string_length(A, LenA)
	   & length(B, LenB)
	   & string_length(C, LenC)

	span_left(+ABC, +Set, ?LenA, ?LenB, ?LenC)
	span_left(+ABC, +Set, ?LenA, ?LenB)
	span_left(+ABC, +Set, ?LenA)
	   no character in A is in Set
	   every character in B is in Set
	   B is not empty
	   A and B are as long as possible

	span_right(+ABC, +Set, ?LenA, ?LenB, ?LenC)
	span_right(+ABC, +Set, ?LenA, ?LenB)
	span_right(+ABC, +Set, ?LenA)
	   no character in C is in Set
	   every character in B is in Set
	   B is not empty
	   C and B are as long as possible

	span_trim(+ABC, +Set, ?LenA, ?LenB, ?LenC)
	    every character in A is in Set
	    every character in C is in Set
	    A and C are as long as possible

    For the span_* predicates, a Set is an atom, a string, a list
    of character codes, a CHARTABLE object, or not(Set).

	gensym(+Prefix, -Atom)
	gensym(-Atom) :- gensym('%', Atom)

Case conversion was split out into another library, because Xerox Lisp
used a 16-bit character set, and it really wasn't clear what case
conversion should do with for example German sharp S.

This package was mainly provided to let Prolog manipulate Lisp strings
conveniently.  Some of the things (like gensym/2) that didn't really
fit anywhere else went here too.

The package was made to accept atoms as "text objects" so that code
developed on Lisp machines could be ported to UNIX and VMS boxes,
where Quintus Prolog had no native string type.

Another reason for having this package was that I envisaged providing
a compatibility kit for another Prolog dialect that had (packed
array style) strings using $...$ syntax.  That never happened.

In practice library(strings) saw very little use, because strings
(in the sense of packed arrays of codes) are just a very clumsy and
costly way to manipulate text.  Even in C there are far better approaches.

Singleton			library(strings)

atom_length(A, N)		string_length(A, N)
atom_member(C, A)		string_char(_, A, C)
atom_append(A, B, AB)		string_append(A, B, AB) or
				midstring(AB, B, A, _, _, 0)

A very special problem with (packed array of code) strings and
atoms is that they don't even come close to 

	I agree that the semantics of XXX_to_term/2 are so narrow and
	arbitrary as to make it unworthy of being regarded as a "primitive",
	but whether a Prolog system implements it in native library code,
	in foreign library code, or deep within the kernel is surely
	down to efficiency?
	
From a software engineering point of view, no.
Time spent implementing it deep within the kernel is time wasted that
could have been spent on improving system efficiency or quality.

	I'm sure we agree that it is out of order for Prolog implementors
	to attempt to force application developers to use one or other ADT
	in particular circumstances by not implementing certain operations.
	
No, I can't agree with that.  It's a demand that _every_ operation,
plausible and implausible, be provided for every type, whether the
inventors of that type intended it to be used that way or not.

Does Paul Singleton really mean to say that it is "out of order for
Prolog implemenntors to attempt to force application developers"
not to use integers to represent strings "by not implementing certain
operations" such as `appending' two Goedelised strings to make another
Goedelised string?

Quintus Prolog basically implemented
    - here is a list, give me an atom (C)
    - here is an atom, how many characters (C)
    - here is an atom and an index, give me the character (C)
    - are these two atoms the same (emulator)
    - rank these two atoms (emulator + C)
as primitives.  That suffices to implement everything else,
INCLUDING atom_to_term/2, library(read) having been provided.

	I agree with Richard that atom_to_term "feels wrong", but disagree
	that this in any way justifies not implementing it.
	
Then what in the name of sanity _would_ justify not implementing it?

What we did was to provide all the primitives necessary to implement it,
and an unbounded number of other more useful things.  In fact we _did_
implement atom_to_term/2 in the __unsupported__ library.

Look, any organisation such as Quintus or SWI has only a finite number
of people and they can only work 16 hours a day for so long.  There are
all _sorts_ of important things to put in which will have a high payoff
for thousands of well written programs.  (Top of my list was bignums
and rationals; the low-level machinery necessary to support that was
just going in when I left Quintus; that machinery could have supported
packed array style strings as well.)  Time spent implementing atom_to_term/2
(which should never be used in well designed code) is time NOT spent on
speeding up the garbage collector (used in every single program).

