Subject: Re: [SWIPL] keysort

From: "Richard A. O'Keefe" <[email-masked]>
Date: Thu, 1 Mar 2001 15:58:56 +1300 (NZDT)

Concerning the implementation of bags:

	"Richard A. O'Keefe" wrote:
	
	> ...you cannot actually implement bag in terms of ordset(pair)
	>         without cracking open the ordset abstraction.  For example, taking
	>         the union of two ordsets of pairs is *NOT* the same as taking the
	>         union of two bags, so special-purpose code has to be written
	>         anyway.  That is, you have to work *inside* the ordset abstraction.
	
	OO folk would say you have to override some of the operations
	(others would still be valid); I guess this could be done without
	reference to the actual representations of either ordset or pair?  And
	maybe PE could rewrite it to be efficient?  in principle at least...

I teach OO.  In fact, I gave the first lecture of the 4th year OO paper
this very morning.

With reference to the specific case of (ordered) bags and (ordered) sets
there aren't *ANY* operations that bags could inherit from sets, with
the trivial exception of "is this thing empty".

library(bags)    has 33 operations.
library(ordsets) has 19 operations of its own (it picks up a lot from lists).
They have exactly *one* trivial operation that could be the same.

No, an object-oriented programmer would *not* have bags inherit from ordsets.
It just plain doesn't make any kind of OO sense.

	> If you meant why isn't it list(pair(Element,integer)),
	
	Probably :-) Except I assumed there'd be some benefit in keeping
	the list ordered on the elements?
	
Yes, but there isn't an existing type "list ordered by some key other than
the whole element".

Above all, one of the key aspects of good object oriented design is that
if a child type is derived from a parent type, it should not inherit any
operations that do not make sense.

If the parent has some operations that the child must not have (for example,
the ability to insert arbitrary elements anywhere in the sequence, thus
destroying the child's class invariant) then either
 - the child should delegate to an instance of the parent, or
 - you have to refactor, introducing a grandparent class that contains
   the features that make sense for both classes.

	> Debugging:
	>         By attaching a distinctive functor to bags, I could give them their
	>         own portray/1 definition.
	
	...this being the only way to attach an operation to a type :-)
	
	(thinks: 'CB8AD857-BBEE-11D4-B806-525400DFC059'/3 would have been more
	distinctive :-)
	
Not for human beings it would not.  Remember, I had to *key in* the name
quite a few times.  Functor names (other than machine-generated ones) should
be readable.

	> Error prevention:
	>         I did NOT want bags to unify with lists.  Distinct abstract data
	>         types should have implementations that do not unify.
	
	Even where one is a specialisation on the other?
	
I'd say "a specialisation OF", but which type is a specialisation of what
in this thread?  Bags are *not* a specialisation of sets.  If they were
a specialisation of sets, they would have to satisfy the axioms that sets
satisfy.  One of those axioms is "x U x = x" for any set x.  But that fails
for every bag except the empty bag.  So bags cannot be a specialisation of
sets.

In particular, the *bag* with elements 'a', 'b', 'c' each occurring once
does not have the same behaviour as the *set* with elements 'a', 'b',
'c' each occurring once, so should not unify with it.  (Fundamental
rule of unification:  two terms should unify only if by binding variables
you can make them represent abstract values with *IDENTICAL* properties.)

	>         And wrappers
	>         are Bad Style, so it is not enough to put a wrapper around a list.
	
	Wrappers don't appeal to me, but I can't see why they are "not enough":
	they seem to do the job just fine.  You only pay the overhead once per
	bag, not per element, both in space and in operations such as intersection.

When I say that someone is using a wrapper, I mean that they are using
a term like foobar(X) simply to "label" X as belonging to type "foobar",
without actually distinguishing it from other values of the same type or
using the functor to group together more than one attribute.

People use wrappers when what they really want is Haskell's "newtype";
a way of "painting" a value "a different colour" without actually paying
any time or space cost for the paint.

Newtypes are *good* in Haskell because they really do have zero cost;
you can (and normally DO) use them *inside* the encapsulation layer.

Wrappers are *bad* in Prolog because
 - they don't actually help module users very much, because if you know
   the wrapper exists you have *already* breached encapsulation.
 - they are NOT free; you pay a non-trivial price on every operation
 - because of that, people don't use them inside modules, but people
   who implement data types make mistakes too.

	The use of a list becomes a purely internal matter.

The use (or non-use) of a wrapper should ALSO be a purely internal
matter, as should the representation of every abstract data type.

	Sadly the wrapper adds to (but not compounds) the already
	higher-than-necessary costs of the list-of-pairs representation.
	
without actually buying you any real error prevention to speak of.
In fact having to deal with two representations (the wrapped and the
unwrapped ones) *increases* your chance of making a mistake.

	I never doubted that you'd made a justifiable decision, but I was
	interested in your rationale.  I assumed that, for a long-lived, perhaps
	widely-used library, run-time efficiency wins over what I called "design
	time efficiency".
	
Correctness comes first.  As a matter of fact, I didn't know that this was
going to be long-lived code when I wrote it.  When I joined Quintus, I did
think of changing it (and the new merged Quintus/SICStus library *will*
change some of the representations, but not this one) but decided it wasn't
broken.

In fact the main thing I did to improve efficiency was to go through the
DEC-10 library very carefully ripping out as many cuts as I could, making
sure that I used non-defaulty representations so that the cuts were not
needed in the first place.

	> You should combine existing data types WHEN THAT WILL WORK.
	
	Yes, but when we do, we lose the benefits of distinctiveness :-/
	
	Given that Prolog denies us the "best of both worlds"
	compromises which OO supports (with inheritance and overriding),
	I'm inclined to say:  do it whichever way you want:  it will be
	locally optimum in some sense, and you can claim that your
	values at the time made it the best choice!

As I explained in the OO lecture this morning, here are some of the
things that aid in re-use:

    1. Inheritance.
    2. Fully automatic storage management (reduces coupling)
    3. Type parameters or run-time typing
    4. Encapsulation.
    5. Documentation.

Of these, perhaps the least important is number 1.  (It is no surprise
that the C++ STL depends heavily on 3 and hardly at all on 1.  It is
also no surprise that the inheritance hierarchy in Smalltalk is quite
independent of the subtype hierarchy, even to some extent at odds with
it.)

The thing that Prolog needed was good encapsulation.
DEC-10 Prolog and C Prolog had none.
Quintus Prolog has a module system which is pretty darned good,
but is something of a compromise, and doesn't encapsulate data at all.
(Backwards compatibility with Edinburgh Prologs meant that there were
insuperable difficulties in the way of data encapsulation.)

Mercury has 2, 3, 4, and 5.  It also has overloading; you can attach
operations to types but not (at least last time I looked) inherit them.