Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!udel!haven.umd.edu!ni.umd.edu!uc780.umd.edu!cs450a03
From: cs450a03@uc780.umd.edu
Newsgroups: comp.lang.misc
Subject: RE: Optional static typing limits
Message-ID: <23APR91.23180618@uc780.umd.edu>
Date: 23 Apr 91 23:18:06 GMT
References: <2325@optima.cs.arizona.edu> <boehm.672447105@siria>
Sender: usenet@ni.umd.edu (USENET News System)
Organization: The University of Maryland University College
Lines: 50
Nntp-Posting-Host: uc780.umd.edu

Hans Boehm    >
David Gudeman >>
Chris Holt [sort taking args:  unsorted list and ordering predicate]

>>I know that is the standard solution, but I wonder if a better
>>solution wouldn't be a function $ord : D -> Int$ that maps domain
>>objects into [list which requires the same permutation as D to sort]

>There is no such function mapping character strings to integers.

I agree with Mr. Gudeman that mapping into some domain for which sort
is defined is a good idea.  And, I agree with Mr. Boehm that it is
important to be able to sort strings.  I disagree with the idea of
using a predicate to specify the order.

If "sort" can order a list of sequences (in addition to a list of
atomic numbers), that should be adequate.  Then if you have some
internal type that sort doesn't know how to deal with you can provide
a sort key which maps to sequences which sort can deal with.

Why provide sort keys, rather than a predicate?

(1) building a key takes O(n) steps, rather than O(n log n) where n is
the length of the unsorted sequence.  (And often, the predicate will
have to extract keys for two arguments each time it is evaluated).

(2) I believe key extraction reduces the communication costs on highly
parallel machines.  [somebody want to verify this or disagree?]

(3) It is simple to derive a predicate from the specification of how
to build a key (if you choose to have the compiler optimize for
minimum dynamic space requirements).  It is not so simple to derive a
key from the specification of how to build a predicate, even when that
is a desireable optimization.

(4) Mapping from one domain to another is a classic (and very general)
mathematical technique.  It is synergistically good to put effort into
supporting this sort of mapping.

Er.. in other words, you don't need to complicate the implementation
of "sort" by trying to generalize the sorting process to all cases.
Just optimize the hell out of a handful of cases and let other
features of the language deal with generalizing to "user-defined"
cases.

Finally, note that the function used for mapping data -> key could be
dynamically bound if the situation calls for it (providing the same
kind of generality as supplying a predicate to sort).

Raul Rockwell