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.
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.
;; Example 5.1(sort (list "this" "is" "a" "list" "of" "words") 'alphalessp) ==> ("a" "is" "list" "of" "this" "words")
seen previously, if your code is in SKILL++, you can simply
reference the global variable whose name is the same as the function
;; 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.
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
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
;; 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
;; 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)
;; 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(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.
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)
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))
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(sort (geGetEditCellView)->instances (genCmpFunction ?test alphalessp ?key (lambda (i) i->name)))
In this posting we looked at the following concepts.
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.
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
Hi kb, Good to see that you liked the article.
This is very good