SKILL for the Skilled: Sorting With SKILL++

In the previous couple of SKILL for the Skilled postings we looked at some of the features of SKILL++. In fact, we saw local functions, higher-order functions, and lexical scoping. In this episode of SKILL for the Skilled I would like to show a few more practical examples of these concepts.

Functions are first class

In the SKILL language, functions are themselves first class objects. They can be created dynamically, and they can be passed around as arguments to other functions. We'll see in the examples how to write functions that generate functions, and why you might want to do that.

Review of the SKILL sort function

The SKILL primitive sort function, takes two arguments. The first is the list to be sorted, and the second is a function designator indicating a compare predicate. A predicate is a function whose return value is to be interpreted as TRUE or FALSE. A compliant compare predicate (for sort) promises to accept two arguments and return a boolean value indicating whether the two arguments given are in order in some appropriate sense. Often there is already a built-in SKILL function which does the type of comparison needed, and sometimes an on-the-fly function does the trick. The code in example 5.1 uses a pre-existing function, alphalessp as a compare predicate. In this case, the sort function reorders the list of strings alphabetically.

Sorting with built-in sort predicates

 

;; Example 5.1
(sort (list "this" "is" "a" "list" "of" "words")
      'alphalessp)
  ==> ("a" "is" "list" "of" "this" "words")

As seen previously, if your code is in SKILL++, you can simply reference the global variable whose name is the same as the function name: alphalessp.

 

;; Example 5.2
(inScheme
  (sort (list "this" "is" "a" "list" "of" "words")
        alphalessp))
  ==> ("a" "is" "list" "of" "this" "words")

For the rest of this article, please assume all top level SKILL expressions reside in a (inScheme ...) form.

Implementing SKILL++ sort predicates

The compare predicate of sort may actually be any callable object. Several types of objects are callable in SKILL. Symbols such as alphalessp are callable if they name existing functions or are somehow auto-loadable. Function objects created by lambda are also callable.

Global functions get created and named when you use procedure or defun. As we saw previously functions can also be created and named locally using flet and labels. But you can also create nameless functions with lambda.

The code in example 5.3 creates a function named fileLengthLessp.

;; Example 5.3
(defun fileLengthLessp (f1 f2)
  (lessp (fileLength f1)
         (fileLength f2)))

The code in example 5.4 creates an equivalent function, i.e., a function that does the same thing as fileLengthLessp when called, but which has no name. You have to store the value in a variable or pass the value directly to a function, such as to the sort function.

 

;; Example 5.4
(lambda (f1 f2)
  (lessp (fileLength f1)
         (fileLength f2)))

In the following examples (5.5, 5.6, and 5.7) we want to sort a list of file names (strings) according to the file size (in bytes). There are several ways to do this. There is a SKILL built-in function to return the file size, but there is no built-in SKILL function which compares file sizes. However Example 5.3 above implements one named fileLengthLessp. We can use that function as an argument to sort.

 

;; Example 5.5
(sort (getDirFiles ".")
      fileLengthLessp)

You can also build the function on-the-fly without a name as in Example 5.6.

 

;; Example 5.6
(sort (getDirFiles ".")
      (lambda (f1 f2)
         (lessp (fileLength f1)
                (fileLength f2))))

You can also do this using flet as in example 5.7.

 

;; Example 5.7
(flet ((lesspFileLength (f1 f2)
         (lessp (fileLength f1)
                (fileLength f2))))
  (sort (getDirFiles ".")
        lesspFileLength))

 

Reversing the sort order

Two more examples are seen in examples 5.8 and 5.9. Example 5.8 shows how to sort a list of strings in decreasing order according to (string) length; i.e., longest string first.

 

;; Example 5.8
(sort list_of_strings
      (lambda (a b)
         (greaterp (strlen a)
                   (strlen b))))

Example 5.9 shows how to sort a list of sub-lists by decreasing order according to (list) length.

;; Example 5.9
(sort list_of_lists
      (lambda (a b)
         (greaterp (length a)
                   (length b))))

 

Components of the sort predicate

Notice the similar code structure in examples 5.6, 5.8, and 5.9. There are a couple characteristics of the compare function which we can factor out.

• test: the kind of relation function, numerical relation such as greater (greaterp) than or less than (lessp), or an alphabetic type of relation such as alphalessp.
• key: the kind of attribute we want to compare such as length, strlen, fileLength, or identity.

The identity function

It will simplify a few things later if we first define a very simple function called identity to be a unary function which returns its argument. The identity function defined in example 5.10 is to function application, as zero is to addition, and 1 is to numerical multiplication.

;; Example 5.10

(defun identity (x)
  x)

Higher order functions -- calculating a sort predicate

We can use SKILL++ to calculate the compare function to pass to sort. Writing functions that generate functions is an easy thing to do in SKILL++.

 

;; Example 5.11
(defun genCmpFunction (@key (test lessp)
                            (key  identity)) ;; see example 5.10
   (lambda (A B)
      (test (key A)
            (key B))))

The function, genCmpFunction defined in Example 5.11, can be called with keyword arguments ?test and ?key and returns a function which is compatible with sort; i.e., it returns a binary function which can be used as a sort predicate. The names test, and key are somewhat standard names--even if a bit confusing. Usage examples are shown in example 5.12. The key defaults to the identity function, and the test defaults to the lessp function.

Using the higher order function

Now, the SKILL sort can be used in a more generalized way. We can rewrite the code examples in 5.5, 5.6, and 5.7.

 

;; Example 5.12

;; reimplementation of example 5.6
;; sort a list of file names by increasing file size
(sort (getDirFiles ".")
      (genCmpFunction ?key fileLength))

;; reimplementation of example 5.8
;; sort a list of strings by decreasing string length
(sort list_of_strings
      (genCmpFunction ?key strlen
                      ?test greaterp))

;; reimplementation of example 5.9
;; sort a list of sub-lists by decreasing list length
(sort list_of_lists
      (genCmpFunction ?key length
                      ?test greaterp))

Reimplementing the sortcar function

Notice that if the built-in function sortcar did not exist in SKILL, we could implement it using sort as shown in example 5.13.

 

;; Example 5.13
(defun sortcar (list predicate)
  (sort list
        (genCmpFunction ?test predicate
                        ?key car)))

Sorting objects from the Cadence Database

The genCmpFunction can generate useful sort predicates for sorting data base objects under various criteria. Example 5.14 shows how to sort shapes in a Virtuoso layout from top-to-bottom according to top edge.

 

;; Example 5.14
(sort (geGetEditCellView)->shapes
      (genCmpFunction ?test greaterp
                      ?key  topEdge))

Example 5.15 shows how to sort the db-instances in a schematic alphabetically according to instance name. In this example, we pass ?key as a function which will retrieve value of the name property from a db-instance.

 

;; Example 5.15
(sort (geGetEditCellView)->instances
      (genCmpFunction ?test alphalessp
                      ?key (lambda (i) i->name)))

Review

In this posting we looked at the following concepts.

• The SKILL built-in sort function
• Sorting list of string alphabetically (examples 5.1, 5.2)
• Sorting file name by file size (examples 5.5, 5.6, 5.7)
• Calculating sort predicates programmatically (example 5.11)
• Reimplementing sortcar based on a generalized sort predicate
• Using higher-order function in conjunction with sorting strings and db-objects.

To Be Continued

In the next posting we'll see more examples of how to use these types of higher order functions with virtuoso, for example to sort pin figures clockwise around the boundary of the cellView. In addition we'll generalize the genCmpFunction further to allow for secondary and ternary sorting criteria.

Jim Newton

Previous Posts

SKILL for the Skilled: Continued Introduction to SKILL++

SKILL for the Skilled: What is SKILL++?

SKILL for the Skilled: Rule of English Translation

SKILL for the Skilled:  Making Programs Clear and Concise