SKILL for the Skilled: Virtuoso Applications of SKILL++

31 May 2011 • 4 minute read

In this posting, I continue looking at applications of SKILL++. In particular, I'll also discuss how to create functions that hold onto their state. I'll use these functions to implement multiple-criteria (cascading) sort predicates. I'll look at ways to sort layout pins counter-clockwise around the center point of the design.

Quick Review

In the previous posting we looked at an implementation of genCmpFunction which I'll repeat here.

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

The value passed as ?key is a function, which given the sort candidate, retrieves the value to be compared. Thus if we wish to sort a list of db-instances by name, we need to pass as ?key a function that given a db-instance will return its name. In example 5.15, we did just that; we passed ?key 'name (lambda (i) i->name).

The getter function

This idiom is actually common enough that we can introducing a new SKILL++ function, named getter, which generates a read-accessor to access a given property name.

;; Example 5.16
(defun getter (propertyName)
  (lambda (object)
    (get object propertyName)))

The function getter takes a property name as its argument and returns a newly generated unary function which will retrieve the value of that property name from its argument. For example given the symbol name, it will return turn a unary function which will retrieve the value of the property name.

(funcall (getter 'name)
db_inst)

is the same as db_inst->name. Of course this is not very interesting used by itself, but is useful in conjunction with other functions like genCmpFunction and genCascadeCmpFunction which will be seen later.

Example 5.17 shows the code example 5.15 but using the getter function rather than lambda.

;; Example 5.17
(sort (geGetEditCellView)->instances
      (genCmpFunction ?test alphalessp
                      ?key (getter 'name)))

What's a closure?

Functions such as genCmpFunction from example 5.11, and getter from example 5.17 are subtly different than functions available in traditional SKILL++. Notice that genCmpFunction returns an on-the-fly function created by (lambda ...). The code within the lambda found in genCmpFunction references two free variables, test and key. These free variables are not declared by or inside the lambda. Likewise, in the function getter, the lambda expression references but does not define propertyName. Functions which extend the life-time of variables defined elsewhere and hold on to these closed-over variables in this way are referred to as closures. In example 5.17, the sort function is called only after genCmpFunction returns. Nevertheless, the closure returned from genCmpFunction holds onto the local variables of genCmpFunction, namely test and key.

Many other Lisp dialects as well as some other programming languages (such as ML, SmallTalk, and JavaScript) implement and support closures. You can find out more about closures on wikipedia.

Sorting pins in a layout cellView

Example 5.18 shows a function which sorts the pin figures in a given layout cellView into counter-clockwise order around the center of the cellView.

;; Example 5.18
(defun sortPinFigs (cv)
  (let ((cv_center (centerBox cv->bBox))
        (cv_pin_figs (foreach mapcan term cv->terminals
                       (foreach mapcan pin term->pins
                         pin->figs))))
    (sort cv_pin_figs
          (genCmpFunction
            ?key (lambda (fig)
                   (let ((fig_center (centerBox fig->bBox)))
                      (atan2 (yCoord cv_center) - (yCoord fig_center)
                             (xCoord cv_center) - (xCoord fig_center))))))))

Note that the function sortPinFigs in example 5.18 assumes there is no pin whose center is in the cellView center, because in that case atan2 would fail.

Cascading sort

Another limitation of sortPinFigs as implemented in example 5.18 is that two different pin figures might be at the same angle. It would be great if the sortPinFigs function would sort pins deterministically. We need a secondary sort criteria. For example, if two figures appear at the same angle, then sort by their distance from the center. But there might actually be some overlapping pins which have the same center, in which case a third criteria is needed, such as sort by layer name (or terminal name, or pin name, or left edge).

In general, whenever sorting objects based not on their identity but on some attribute, it might happen that two different objects share a value of that attribute. As in the example above, when sorting file names according to file sizes, it might of course happen that two different files have the same size. Example 5.19 shows a function genCascadeCmpFunction which is more general than genCmpFunction. The genCascadeCmpFunction function generates a compare predicate based on a sequence of cascading key/test pairs.

;; Example 5.19
(defun genCascadeCmpFunction (key lessp @rest others)
  (lambda (a b)
    (labels ((cascade (key lessp others "UUl")
               (cond
                 ((lessp (key a) (key b)))
                 ((lessp (key b) (key a))
                  nil)
                 (others
                  (cascade (car others) (cadr others) (cddr others))))))
      (cascade key lessp others))))

Sorting strings by cascading criteria

To sort a list of strings proceed first by string-length, then (if they have the same string-length) alphabetically.

;; Example 5.20
(sort (list "c" "abc" "jkl" "b" "hello" "d" "world" "xyz")
      (genCascadeCmpFunction strlen lessp
                             identity alphalessp))

===> ("b" "c" "d" "abc" "jkl" "xyz" "hello" "world")

Sorting file names by cascading criteria

To sort a list of file names first by file length, then alphabetically according to name, you can use the following.

;; Example 5.21
(sort (getDirFiles ".")
      (genCascadeCmpFunction fileLength lessp
                             identity alphalessp))

Sorting db-shapes by cascading criteria

To sort a list of db-shapes, first according to their layer name, then layer-purpose, then left-to-right by left edge, then right-to-left right edge, then top-to-bottom top edge, then bottom-to-top bottom edge, use the following.

;; Example 5.22
(sort list_of_shapes
      (genCascadeCmpFunction (lambda (obj) obj->layerName) alphalessp
                             (lambda (obj) obj->purpose) alphalessp
                             leftEdge lessp
                             rightEdge greaterp
                             topEdge greaterp
                             bottomEdge lessp))

We can rewrite the call above to something simpler using the getter function defined in example 5.16.

;; Example 5.23
(sort list_of_shapes
      (genCascadeCmpFunction (getter 'layerName) alphalessp
                             (getter 'purpose)   alphalessp
                             leftEdge   lessp
                             rightEdge  greaterp
                             topEdge    greaterp
                             bottomEdge lessp))

Summary

The examples shown above illustrate a interesting and powerful feature of SKILL++, closures. You might also find some of the examples useful to simply copy and paste into your programs. Remember to use the .ils extension.

See also

Jim Newton