Subject: Re: [SWIPL] keysort

From: "Richard A. O'Keefe" <[email-masked]>
Date: Wed, 21 Feb 2001 12:53:02 +1300 (NZDT)

I think there's a case for choosing a compound term to represent the arc:

	          a-b
	
	and a compound term to represent the weighted arc:
	
	          (a-b)-2
	
except that if you want to keysort by the weight, as Cecilia Wong did,
you actually need 2-(a-b).

	I only mention this to illustrate a weakness of Prolog (compared
	to e.g. Java) in defining new types:  it doesn't support
	implementation inheritance, so I cannot define a specialisation
	of an old type which both inherits useful operations yet has its
	own identity (for polymorphism etc.).
	
It's not that Prolog doesn't support implementation inheritance,
it's that it doesn't support the idea of attaching operations to
types AT ALL.

Note that there have been versions of Prolog, typically implemented in
Lisp, which _did_ allow operations to be associated with types, even
unification itself.

For what it's worth, Java isn't terribly good at implementation inheritance
compared with say Eiffel or Lisp.

	E.g. ordsets are conventionally represented as, and indistinguishable
	from, lists.
	
That's what strong compile-time types (as in Mercury) are for.

	So there often seems to be a conflict between choosing a data
	structure for design-time efficiency and choosing it for
	run-time efficiency, and between expressing its particular
	semantics and compactly representing its essential structure.

I don't know what you mean by design-time efficiency.
Can you explain?

I'll grant you that well-chosen Prolog data structures are notably
more space-efficient than Java ones, if that's what you're talking
about.

	Is this inherent in a dynamically typed language?
	
Such as Lisp?  Such as Smalltalk?

	Are there any general techniques for gettiong the best of both worlds?
	
Have a look at Mercury.	

On the subject of sorting lists, some Prologs (LPA if my memory serves me,
which it probably doesn't) have a sorting predicate which accepts an
additional parameter:  a number saying which argument of the terms is the
key.  I thought about adding that to Quintus Prolog, but decided that it
was too limiting.  In general, the most efficient method really is to
walk down the list computing the keys and gluing them on with (-)/2,
sort, and then walk down the list stripping the keys off.