Subject: Re: Idea: [] != '[]'? (off, now playing SGML/XML/RDF)

From: Jan Wielemaker <[email-masked]>
Date: Thu, 18 May 2000 13:35:04 +0200

Richard,

First of all, I do highly respect your opinion.  Actually, this is
sometimes why I put sugestions or indeas into this forum.  Discussion
gets the arguments straight and your encyclopedial knowledge of
programming languages and why they are as they are is very valuable.

> 	One argument for foo() to me is consistency.
> 
> I will buy consistency as an argument for allowing foo() AS A SYNONYM
> for foo.
> 
> 	It is consistent for (especially
> 	non-prolog) programs generating Prolog source and it can improve
> 	readability.
> 	
> Since atoms are just compound terms with no arguments, it would indeed
> be consistent to allow an atom to be written with an empty argument
> package.
> 
> But I thought the exact opposite was being proposed, namely that there
> should be two *different* kinds of terms with no arguments, foo and foo().
> Now that is *IN*consistent, so if consistency is the criterion, that must
> not be done.

Just making foo() and alias for foo doesn't buy very much for which I
wanted to use the construct and though a little better, it probably
isn't worth the deviation from the standard.

I do buy your argument (further down, hard to quote nicely) that if
space and typing is the problem, just turn around what you wrap in
functors.

> 	I agree, but there are two reasons why I don't like this is *sometimes*.
> 	If I have to type the structures I much more like writing
> 	
> 		doit([ 'Hello World', foo(), ... ]).
> 	than
> 		doit([text('Hello World'), foo, ...]).
> 	
> 	especially if there is a lot of text to type.

So, I will write this as
	
	doit([ 'Hello', {foo}, 'World', {bar(1)} ]).

{} is nice for this purpose.  It was invented for terms with a different
meaning in DCG, making it conceptually acceptable to overload it for
this purpose and it has nice (odd) syntactic properties.

> What we have here is a very good argument for a distinct string
> data type, NOT an argument for making functor(T, foo, 0) ambiguous!

Agreed. Just there is no room for a distinct string-type (as
SWI-Prolog's packed strings) in Prolog: there are already too many
text representations.

I guess my ideal would be "foo" is internally a packed string, but
behaves exactly as [f,o,o].  Only trouble is that this is pretty messy
in the internal machinery.

> It highlights the *unusual* use of atoms (+CompactString),
> not the *usual* use of atoms (ArbitraryLabel()).
> 
> 	Second reason is sometimes space.  word(hello) takes 3 words,
> 
> In Quintus Prolog, it would have taken 2.

You mean for compounds with arity upto 3 (as you state below) the
initial cell encodes the name, small arity and argument-location? I
don't really see how one could do that. Right now the storage is:

	ptr-to-global+tag(COMPOUND) --> functor
					arg1,
					...

Where functor basically encodes a pointer to a structure holding the
name and arity of the functor.  For arity <= 32 I can tell directly from
the functor what arity it has, for higher arity I have to consult the
referenced structure (SWI-Prolog has no limit on arity, a feature that
allows you to use compound terms for things they are not intended for,
like huge arrays :-)

> I am trying to imagine a situation where it makes sense to have
> literal strings and essentially arbitrary labels in the same list.
> I'm having a really hard time.  Because it _is_ possible to process
> large documents in SML, and SML _can't_ do that.

What is SML?

> I'm working with SGML myself, so I'd be very interested to know more
> about the representations you're using.

The SWI-Prolog SGML parser (actually, there are two, one
quick-dirty-and-small one by me and one based on James Clark's SP
parser which is 3 times as big as SWI-Prolog) uses the following
representation:

	element(Name, ListOfAttributes, ListOfContent)

Where ListOfAttributes is a list of Name = Value, Value converted if
a DTD is present (downcase for anything but CDATA and integer for
SGML numeric attributes).  ListOfContent is a list holding atoms for
CDATA, element/3 terms for encountered elements and entity(Entity)
for characters that cannot be expressed in SWI-Prolog's 8-bit character
set (this is another one on the TODO list).

This works quite nice, though we are still experimenting with the most
ideal way to process these.  We are mainly interested at the moment in
making the structure of a document in terms of headers, summaries,
descriptions, etc. visible.

> Imagine me sobbing and screaming.  PLEASE.  I don't want to have to go
> through a lot of code to change
> 	:- op(..., ..., '[]').
> into	:- op(..., ..., []).
> I've never really felt quite sure whether the latter would work,
> so I've always used the former.

This is odd. Many people indeed write :- op(..., ..., '>>'), but I never
understood why. Being an operator doesn't affect the Prolog tokeniser
and therefore if you think of an operator you look for sequences for
graphics characters, for single punctuation character or for an ordinary
lowercase atom.  Surely nothing that needs quoting, as A '!=' B doesn't
look nice and this is the reason to use operators in the first place.

Nevertheless, it is an example of realistic code that gets broken.

> In all of Prolog, there was only one token didn't correspond to the
> quoted atom with the same spelling, and that was the vertical bar.
> (a | b) == ';'(a, b), not '|'(a, b).
> 
> The ISO standard changed that, and in SWI Prolog,
> (a | b) == '|'(a, b) \== ';'(a, b) == (a ; b).

I must admit I never knew (a | b) == ';'(a, b).  It's just the compiler
that threads them equal (still does I think).

> I can see the point of making [] not be an atom at all.
> Scheme did that: #f, (), and 'nil are all different in Scheme,
> whereas they are all the same in Lisp.

But as pointed out, this would surely break too much.

> '.'('append'('[]',A,A),'.'(':-'('append'('.'(B,C),A,'.'(B,D)),'append'(C,
>     A,D)),'[]')).
> 
> which may not be beautiful for people to read, but it *works*, whatever
> the operator properties of various atoms may be.  And for a program
> generator, the criterion is "is the output CORRECT", not "is the output
> BEAUTIFUL".  If I want it pretty-printed, I can do that in Prolog.  Let
> the C code stay as simple as it can possibly be.
>
> In fact, the rules for when you can omit the quotation marks are
> surprisingly subtle, so it really is *MUCH* simpler not to have to
> have any special cases, including [].

Good point.  write_term/[2,3], trying to get it right, is indeed a very
messy thing (having caused quite a couple of bugs).  If I write C-code
generating Prolog source I usually stay `in the middle' (borrowing code
from SWI-Prolog's write :-).

> I suppose I could add special-purpose code for lists, but why should
> I have to "fix" something that isn't broken?
> 
> 	So with [] \== '[]', but still an atom, this just works right.
> 	
> Yeah, but it removes the whole point of tinkering with [] in the first
> place.  The whole point, if you will recall, was that some people with
> dodgy data structures were irritated by the very fact that [] is an
> atom, not which atom it is.  Changing [] to be something else, 'nil'
> maybe, would break *my* code but wouldn't fix *their* code.  An all-
> round lose, as far as I can see.

Defining [] as an atom that has *no* quoted representation is useful.
It allows me to use atoms-as-text in nested lists:

write_nested_list([]) :- !.
write_nested_list([H|T]) :- !,
	write_nested_list(H),
	write_nested_list(T).
write_nested_list(X) :-
	write(X).

This works nice with my proposal, but there is no way to get this
right in standard Prolog (except for wrapping all text-atoms in a
term).

This ambiguity is everywhere.  Consider ensure_loaded([]).  Should
it load '[].pl' or just do nothing?

Only your examples convince me it will really break code and that is
too high a price, especially as it is not possible to introduce this
possibility using a flag as the system will end up with two
representations of the empty list at the same time.

> 	> Oh, is there any way to eliminate that irritating blank line
> 	> before the answer?)
> 	
> 	:- multifile
> 		prolog:message/3.
> 	
> 	prolog:message(query(yes)) -->
> 		[ 'Yes' ].
> 	
> Hokay, great!  That fixes *one* of the superfluous blank lines.
> Now I get
>     ?- (X = 1; X = 2).
> =>
>     X = 1 ;
> =>
>     X = 2 
>     Yes
> 
> How do I get rid of the extra blank line before each answer?

It's a bit more writing.  You need to redefine the message for
the term query(yes, Bindings), where Bindings is a list of Name = Value.
See pl/boot/messages.pl for the system implementation.

> 	it is just one of these goodies implementors add to their language. 
> 	Like some Prologs allowing for Var(a), gcc allowing for automatic
> 	arrays whose length is defined by a variable, allowing for 0-length
> 	arrays, etc.
> 	
> Those are pretty serious incompatibilities.
> I have had students come to me here and in Australia saying
> "such an such a C compiler rejects this obviously legal C,
> which I got from a lecturer/a textbook/the net/..."
> and I have to tell them, no, that _isn't_ legal "C" and never
> has been, it's "GNU C".

Thats the problem of the `lecturer/a textbook/the net/...'.  It's not
a bad thing if implementations add goodies that do not conflict with
the standard and are in fact natural extensions.  Another example in
structure-copy in C.  This was not allowed in K&R's definition of C,
but most compilers did allow for it and it is in the ANSI standard.
Same story seems to be going on with inlining in C.  This is not
defined in the standard, but many compilers support it.

> Var(a) is actually an excellent example of an incompatibility.
> People get used to it, and then have major problems converting their
> code to more standard dialects.  In fact, to support this, I added a
> hack to Quintus Prolog that X(T1,...,Tn) where X is a variable would
> be read as call(X, T1, ..., Tn).  I believe that was later yanked,
> because Quintus didn't want people thinking that was a sensible way
> to write Prolog.

I didn't think you were capable of such a hack :-)  Var(A), not in
the sense of call/N is quite a nice thing to have.  It just doesn't
fit nicely with how most compilers represent compound terms.  If there
was no problem implementing it, I would probaby do it.  Consider option
lists.  There are two posibilities for this:

	Name = Value
and
	Name(Value)

The latter is attractive as it allows options to have any number of
arguments.  Finding an option with Value=X however is clumsy, forcing
the use of arg/3 (and watch for exceptions.  Grrr).

> PROVIDED that they KNOW which things are standard and which are not.
> PROVIDED that they are provided with a standard operating mode so that
> they can check for portability BEFORE arriving to give the demo and
> finding that nothing works.

Agreed.  Thats why the ISO standard requires a mode to enforce strict
compliance.  I don't know whether there is any implementation providing
this yet.

> Let's *see* it.  If there are so many plain texts as atoms that wrapping
> _them_ is not space efficient, why not wrap the _other_ atoms?  In fact,
> that is _precisely_ what the proposal to make foo() differnt from foo
> amounts to.  Why is it better to write foo() (introducing a fundamental
> incompatibilty in data structures) than to write {foo} or {}(foo) or -foo
> or macro(foo) or whatever, which would presumably have the same space cost?

This is a very good remark!

> 	If you can get these without breaking real-life code (i.e. not
> 	constructed counter examples), I think it is worth it.
> 	
> I see.  If it's existing code of Richard O'Keefe's, it's not "real-life"
> code.  Nice to know where I stand.

I just didn't expect you to write :- op(..., ..., '[]') :-)

> 	For now, it has  to be able to handle RDF-models holding about 3e6
> 	triples.  This takes too long to load and requires too much memory. 
> 	These are the things that have always guided the development of
> 	SWI-Prolog.
> 	
> That really sounds as though improvements to the engine (making it faster
> and take less space) would pay off for *you*, never mind me.

Thats life. The University pays me and wants me to write applications
for their research program. These applications have demands and these
are the first demands to fulfill. Fulfilling demands of the rest of the
user community is valuable too for many reasons, but generally at a
little lower priority.  In the past, a compagny (Sylogics) has paid me
to implement the garbage collector.  You can do the same if you want
to guide the direction of development.

For example, I'm happy to add big numbers if I can turn it into a paid
project. We have no demand for them here, so the only option now is that
at some rainy sunday afternoons I add this facility. That may happen or
not, depending on the climate and my inspiration :-)

> In particular, making terms like text(X) take 2 words instead of 3 would
> seem to be a clear space saving; presumably it would (like QP) also make
> triples t(X,Y,Z) take 3 words instead of 4.

Stack space here is not my biggest concern.  Program space and program
load time are the issues here.  SWI-Prolog is already very fast in this
respect, but this simply makes too high requirements.  There is very
little to gain along the track of loading the QLF files (and saved
states).  Most of the time is spend loading the symbol-table in memory,
especially with RDF descriptions that produce huge amounts of atoms.
Clauses go through a very minor mapping when loaded.  Hash indices are
already build on demand (i.e. at first call).

Demand-loading appears to be the solution.  The current idea is to use
a database (I'm looking at the DB library) and be able not only to load
predicates from this database, but to load individual indexed clauses.

DB appears attractive: widely available with access at various levels
providing tradeof between security, client/server, locking, transactions
and speed.

The idea is that small predicates (=few clauses) are demand-loaded as a
whole. Predicates with many clauses are demand-loaded clause-by-clause.
A certain maximum can be set to the size of the program that is actually
in core.

For playing around with an RDF model this implies that the accessed part
of the model is in core and the other clauses stay in the database.  Of
course, if you make a non-indexed access to this predicate you will be
doing a lot of demand-loading and destroying of clauses, but no serious
inferencing is possible with non-indexed access on such large
predicates anyway.

First step I'm working on is indexed access to arbitrary Prolog terms in
a DB database. A good deal of the rest can actually be written in Prolog
if I provide a hook in finding clauses.

> I stand by what I said.  Let's see some *specifics* about code that would
> benefit from these 

You convinced me that the costs are greater than the benefits. With
SWI-Prolog I've always put compatibility high on the priority list.

	Regards --- Jan