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 alsoJim Newton