From chiqueti@inf.ufsc.br Thu Mar  1 04:23:16 2001
Received: from parkinson.uol.com.br (parkinson.uol.com.br [200.231.206.187])
	by swi.psy.uva.nl (8.11.2/8.11.2) with ESMTP id f213NEZ24119
	for <prolog@swi.psy.uva.nl>; Thu, 1 Mar 2001 04:23:14 +0100 (MET)
Received: from rpacher (200-191-104-189-as.acessonet.com.br [200.191.104.189])
	by parkinson.uol.com.br (8.9.1/8.9.1) with SMTP id AAA05119;
	Thu, 1 Mar 2001 00:21:55 -0300 (BRT)
Message-ID: <002d01c0a1fe$c26f19c0$bd68bfc8@rpacher>
From: "Fabiano Chiqueti" <chiqueti@inf.ufsc.br>
To: "Richard A. O'Keefe" <ok@atlas.otago.ac.nz>, <p.singleton@keele.ac.uk>
Cc: <prolog@swi.psy.uva.nl>
References: <200103010258.PAA00065@atlas.otago.ac.nz>
Date: Thu, 1 Mar 2001 00:21:50 -0300
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.50.4133.2400
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Subject: [SWIPL] I WHANNA GET OUT!!!!!!!!!!!!!!!!!!!!


----- Original Message -----
From: "Richard A. O'Keefe" <ok@atlas.otago.ac.nz>
To: <ok@atlas.otago.ac.nz>; <p.singleton@keele.ac.uk>
Cc: <prolog@swi.psy.uva.nl>
Sent: Wednesday, February 28, 2001 11:58 PM
Subject: Re: [SWIPL] keysort


> Concerning the implementation of bags:
>
Sorry but I'd like to get out of this mail list.Anybody could help me? What
can I do about it?

> "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.
>
>
> ----------------
> * To UNSUBSCRIBE, please use the HTML form at
>
>     http://www.swi.psy.uva.nl/projects/SWI-Prolog/index.html#mailinglist
>
> or send mail to prolog-request@swi.psy.uva.nl using the Subject:
"unsubscribe"
> (without the quotes) and *no* message body.
>
> ** An ARCHIVE of this list is maintained at
>
>     http://www.swi.psy.uva.nl/projects/SWI-Prolog/mailinglist/archive/
>

