Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!samsung!olivea!mintaka!bloom-beacon!eru!hagbard!sunic!mcsun!ukc!warwick!nott-cs!piaggio!anw
From: anw@maths.nott.ac.uk (Dr A. N. Walker)
Newsgroups: comp.lang.misc
Subject: Re: Optional static typing limits
Message-ID: <1991Apr19.144812.5958@maths.nott.ac.uk>
Date: 19 Apr 91 14:48:12 GMT
References: <LIBERTE.91Apr16164831@babbage.ncsa.uiuc.edu> <8493:Apr1719:30:0791@kramden.acf.nyu.edu>
Reply-To: anw@maths.nott.ac.uk (Dr A. N. Walker)
Organization: Maths Dept., Nott'm Univ., UK.
Lines: 56

In article <8493:Apr1719:30:0791@kramden.acf.nyu.edu>
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:

>And, as a first sample problem to be solved by a typing system: How do
>we write a generic, type-safe sorting routine? What's the best that
>available languages can do to make this work?

	I quote [without permission, and somewhat edited] from Charles
Lindsey's paper on modals, Algol Bulletin #37, p28, July 1974:

[Start of quote.]

Example 1 -- A (very slow) sort routine.

    proc sort = (mode z, ref [] z vec, proc (ref z, ref z) bool swapped)
           void: for i from upb vec by -1 to lwb vec + 1
                  do for j from i to upb vec
                        while swapped (vec[j-1], vec[j]) do skip od
                  od;

    [For example ...]

	mode person = struct (string name, int age);
	proc ageswap = (ref person lo, hi) bool:
		if age of hi < age of lo
		  then person p := hi; hi := lo; lo := p; true
		  else false
		fi;

whereupon a row of persons could be sorted thus:

	[1000] person people; read (people);
	sort (person, people, ageswap)

[End of quote.]

Re-implementing "sort" as a Quicksort or similar is left as an exercise!
Apart from the actual sorting technique, this seems to me to be the same
as C's "qsort" library routine, but type-safe in Dan's sense.  Any
advances in the last 17 years?

	I don't think there is any theoretical objection to deleting the
"swapped" parameter to "sort", replacing the call "while swapped (...)"
by "while vec[j-1] < vec[j]", and defining

	op < = (ref person lo, ho) bool: (...)

in which case "sort" would compile for any "z" for which the operator
"<" was defined.

	C could do this if types were allowed to be parameters to
functions.

-- 
Andy Walker, Maths Dept., Nott'm Univ., UK.
anw@maths.nott.ac.uk