140000144%EDXA%UCL-CS@sri-unix.UUCP (01/28/84)
From: Prolog FHL (on ERCC DEC-10) <140000144%EDXA@UCL-CS>
I've read his article a couple of times. If I understand it
correctly, when you think you've got an array, what you have is
a pointer to one of two sorts of things:
- a real Lisp-machine array
- a pair (list of changes, pointer to an "array")
where when you use the second sort of thing, you check if the
index is in the list of changes, and only look at the "base"
array if it's not there. That's a neat idea, which is almost
the exact opposite of the scheme used in the Prolog arrays
library package. In that, the old version is the base version,
and you have more overhead for updates, until a critical point
is reached and the whole array is copied. His approach, I think,
can only coded in the host language, as the change which has to
be undone by the trail entry is not just a variable binding.
ARRAYS.PL was constrained by the fact that the only reversible
change it could use was Prolog variable binding.
It looks as though you should be able to make several copies of
the same version of an array, and change them independently.
The trouble is that ONE of them wins and gets to use a "real"
array, while the others are reduced to using association lists.
So it isn't just ancestor references which are penalised by
updated, it is cousin references as well. So using his method,
one version of an array is cheap and all other versions are
dear, while using pure Prolog binary trees, every version is a
wee bit dearer than using arrays, but no version gets very dear.
And of course there is no reason why a binary tree can't be used
to implement multi dimensional arrays.
He says that using this representation of arrays, you can represent
strings "at least 8 times more densely than by using lists". The
only exception of course is DEC-10 Prolog, where a list cell *can*
cost you just one molecule, around 5 bytes. In most Prologs, a
list cell is around three pointers, say 12 bytes, so he is being
too kind. Using Lisp-Machine character arrays in LM-Prolog makes
a great deal of sense, as there are ever so many handy functions
lying around for doing interesting and useful things to these
objects. But this has nothing to do with mutability. Poplog
makes "strings" available to its Prolog component as primitive
objects, and Prolog-X and NIP have "boxes", one form of which
is a "string", again a linear sequence of 8-bit characters. There
is no reason why ANY Prolog compiler or interpreter can't suuport
strings as primitive values like integers, and there are excellent
reasons why strings should be immutable.. I would have thought
that strings would have been available as primitive (to Prolog)
values in LM-Prolog since the first version was shown to the second
person. I would also have expected that LM-Prolog would use Lisp
Machine lists to represent lists, so that a list cell there should
cost an average of 5 bytes, or does the way Prolog handles lists
remove the payoff from CDR-coding entirely ?
Anyway, here is a suggestion. The good thing about using lists to
represent strings in Prolog is that you can do pattern matching
using grammar rules. Now the grammar rule pre-processor in DEC-10
Prolog and C-Prolog turns e.g.
p --> [a].
into e.g.
p(S0, S) :- 'C'(S0, a, S).
where
'C'([H|T], H, T).
I may have the arguments of 'C' the wrong way around, but no
matter. If we add a second clause to 'C',
'C'(Index@String, C, Jndex@String) :-
succ(Index, Jndex), % 0 <= Index = -1+Jndex
1 =< Index, Index =< sizeof(String),
char_of(String, Index, C).
then we can write our grammar rules the same way irrespective of
whether they are to be used on lists or character arrays. Indeed,
in LM-Prolog, there should be a third clause for 'C' so that a
character position can be a position in a ZMACS buffer, and then
we could use Prolog grammar rules to define patterns for ZMACS
to search for or move over. How about it?