Blind Sorting

How to sort a list by sort library without giving sort logic access to list elements.

Kevin Reid broached the problem of using sort code while denying that code access to the sorted things. (He was trying to illustrate a more general problem about which I have nothing to say here.) I have a collection of zots and some notion of total ordering among them. There are several sub-cases:

Perhaps the notion was foreseen by the definer of such zots, as when they are strings, integers, rationals, floats, (but not complexes).
Perhaps you have an exogenous order notion such as ‘height’ of a rational which is the maximum of the absolute values of the numerator and denominator, (actually used in some mathematical proofs)
Perhaps it is a create-as-you-go ordering wherein you decide only on demand an ordering and remember what you decided, and conform to previous decisions.

Sort routines, even 1960’s style commercial routines, took a sort function which took two zots and returned a one-in-three value (=, <, >). These routines had access to the zots. A more general problem is protecting your data from code that manages collections of your data.

We examine OCaml’s solution to sort here.

The Scheme code below seals elements of a list and calls a simple list sorter with a comparator that compares sealed records. Unfortunately it relies on a form of synergy proposed by Rees but unavailable in standard Schemes.

(lambda (ls less) (let* ((sort-seal (new-seal))(unseal (cadr sort-seal)))
  (map unseal ((fileVal "sort") (map (car sort-seal) ls) 
    (lambda (a b) (less (unseal a) (unseal b)))))))

This function is a blind sort and is a simple example of the clan pattern in Scheme. I do not know an efficient implementation in standard Scheme of this pattern.

Keykos seems to require a small box, like Scheme, for each protected record, perhaps 1000 bytes. The box for each Scheme record would require perhaps 100 bytes. The necessary sealer logic is available in Keykos.

Forrest Bennett proposes the following which I express here in Scheme:

(lambda (list less) (let* ((ls (list->vector list)))
  (map (lambda (i) (vector-ref ls i)) (sort
       (let m ((l ()) (n (vector-length ls)))
         (if (= n 0) l (m (cons (- n 1) l) (- n 1))))
      (lambda (a b) (less (vector-ref ls a) (vector-ref ls b)))))))

The list of records is made into an array of records and a list of the integers from 0 to n−1 is passed to the conventional sort routine along with a comparer that is a function that given two indices has the authority to compare the real records. When the sorted list of indexes comes back it is mapped back to a list of the records. With Scheme’s memory management the real records never moved—only record pointers were copied about.

Peter Hendrickson proposed a scheme for the sort routine to send back swap commands to a routine with the authority to swap array entries.

This would often be the best solution but it does not generalize to a set abstraction where representations of multiple sets must persist just as necessary, and be garbage collected as the computation proceeds. The set elements may not all exist at once to be put into an array and elements of the array might outlast their real lifetimes.

Another issue is when the space required to hold the records to too large for real RAM. Classic sort routines could drastically reduce the necessary real I/O that the index abstractions described above require. They sorted real records, like a punched card sorter and could achieve performance of algorithms invented for card sorters.