SKILL for the Skilled: Continued Introduction to SKILL++

In my previous posting, which provided an introduction to SKILL++, I showed a simple but powerful design hierarchy descent function that has various potential uses. The function is called walkCvHier. As a reminder, here is the SKILL++ code again.

1.1: (defun walkCvHier (cv consume)
1.2:   (foreach inst cv~>instances
1.3:     (walkCvHier inst~>master consume))
1.4:   (consume cv))

Just to reiterate: this function is naive for demonstration purposes. You can easily imagine ways of enhancing or generalizing this function to be more robust and handle more complicated hierarchy descent. I encourage the reader to experiment with such enhancements, and feel free to post your suggestions, or questions in the comment section of this blog.

In the following paragraphs, I'll show more advanced uses of the walkCvHier function. Please assume that all the code in this article is SKILL++ which means it is defined in a source file with a .ils extension.

Local (private) function

In the previous article I showed how to implement the reportCvHier by writing a private, global function _reportCv. It turns out there are better ways of doing this in SKILL++ which don't require polluting the global function name space. It is not necessary to make this client function visible to the world simply to pass it as a parameter to walkCvHier.

If you are using IC 6.1.5, a more explicit way of defining and referencing private (local) functions is to use the newly available macro flet.

4.1: (defun reportCvHier (top_cv)
4.2:   (flet ((reportCv (cv)
4.3:           (println (list cv~>libName
4.4:                          cv~>cellName
4.5:                          cv~>viewName))))
4.6:     (walkCvHier top_cv reportCv)))

The flet macro may be used to define one or more local functions which are thereafter available for reference by name inside the body of the flet. Such a by-name reference is shown on line 4.6 in the example above, where the local function named reportCv is only visible and callable within the body of the flet form (i.e., within the matching parentheses which surround flet). This local function has a single required argument named cv. Since this is SKILL++, we are free to use function names (global or local) as if they were variable names, as on line 4.6.

One power of local functions over global functions is their ability to securely reference other lexical variables which are in scope. For example, it would be possible for the local function reportCv to reference the variable top_cv if necessary. Because reportCv lies textually within the matching parentheses of the (defun reportCvHier ...) form, it is free to use all the local variables which that form binds, including the formal parameter of top_cv. Other examples of these are shown on lines 6.4 and 7.4 below.

If you don't have access to IC 6.1.5, you may use the following construct. In this case we simply create a function on-the-fly without a name, and pass it directly to reportCvHier.

5.1: (defun reportCvHier (cv)
5.2:   (walkCvHier cv (lambda (cv)
5.3:                    (println (list cv~>libName
5.4:                                   cv~>cellName
5.5:                                   cv~>viewName)))))

Functions that manipulate state

In the next example (lines 6.1-6.5) I'd like to use walkCvHier to count the number of cellViews in the hierarchy, and in (7.1-7.5) build a table mapping each cellView to the number of times it occurs in the hierarchy. In this case the consumer function passed to walkCvHier needs to modify some state (such as, a counter or a hash table) within the calling function.

How would you attack this with traditional SKILL? With traditional SKILL the consumer function would probably need to modify a global variable to maintain the count, introducing two immediately apparent problems. 1) the function would probably not be non-reentrant.That is, you may not be able to pass in consumer function which itself calls walkCvHier. 2) If the consumer function encounters an error, this global variable could be left in an incomplete state, which would confuse subsequent calls.

SKILL++ and state manipulation

Why do these problems vanish with the SKILL++ approach? Because there is no need for the global variable. The variable can remain local and lexical as seen on lines 6.2 and 7.2.

This function countCvHier passes a function to walkCvHier which increments a variable, occurrences, at each step in the hierarchy. Note that the walkCvHier knows absolutely nothing about the local variable occurrences. Moreover, even if walkCvHier were implemented having a local variable of the same name it would not have any ill effect on countCvHier.

6.1: (defun countCvHier (cv)
6.2:   (let ((occurrences 0))
6.3:     (walkCvHier cv (lambda (cv)
6.4:                      occurrences++))
6.5:     occurrences))

In the function occureHier, we use the same technique to pass a function to walkCvHier which modifies a hash table referenced by the local variable, occurrences.

7.1: (defun occureHier (cv)
7.2:   (let ((occurrences (makeTable 'occur 0)))
7.3:     (walkCvHier cv (lambda (cv)
7.4:                      occurrences[cv] = (add1 occurrences[cv])))
7.5:     occurrences))

It is perhaps worth emphasizing that if you were using traditional SKILL rather than SKILL++, this technique would fail for several reasons. These problems boil down in the end to differences between dynamic and global variables. While dynamic variables are interesting and have powerful uses, this is not one such place to use them. Without giving a detailed explanation of subtle errors some of the problems are the following:

• You'd have to be sure to use a variable on lines 6.2, 6.4, 6.5, 7.2, 7.4, and 7.5 which were NOT also defined in the walkCvHier function.
• If the consumer function being passed to walkCvHier actually made an explicit call to walkCvHier with a different consumer function, they would not both be able to use the same variable name.
• You would not be able to know that without access to the source code for walkCvHier, which you might not have.

Purging the hierarchy

If you want to purge all cellViews in a design hierarchy you might think of evaluating something like (walkCvHier cv dbPurge), but that probably wouldn't be a good idea. Why? Well for one reason, the same cellView might (and probably does) occur multiple times. You don't want cellViews being purged while they are still needed for traversal. We need to call dbPurge iteratively over a list of cellViews where each cellView occurs only once and children always precede parents. Here is a function which will do that.

8.1: (defun purgeCvHier (cv)
8.2:   (let ((visited nil))
8.3:     (walkCvHier cv (lambda (cv)
8.4:                      (unless (memq cv visited)
8.5:                        (push cv visited))))
8.6:     (mapc dbPurge (reverse visited))))

How does it work? Neither the consumer function nor consequently the traversal function walkCvHier actually purge anything, but rather the consumer function collects a list of cellViews that are visited. Since the walkCvHier is written such that it descends into children cellViews before applying the consumer function to the parent, purgeCvHier simply uses the SKILL push macro to build a list in reverse order, so that parents come before children -- a small problem that is easily resolved with a call to reverse.

A more robust traversal implementation of walkCvHier function could of course allow two consumer functions to be used -- one which is applied before traversing into children cellViews, and a second to be called after each step of the descent is finished. You, the reader, might consider implementing a function. Alternatively, you could provide an optional argument to walkCvHier which specifies whether the consumer function will be called before or after the descent.

More about flet

There is one important restriction on local functions defined with flet: they are not allowed to call themselves recursively, and if you define more than one local function in a single flet, they are not allowed to call each other. You might initially think this is a limitation, but actually it turns out to be a powerful feature which we can look at in a future posting. If anyone is interested, please ask in the comment section of this blog.

If you really need to call a local function recursively, or you need to write several local functions, some of which call other ones, you can use labels instead. Its syntax is exactly the same as flet, but its scoping rules are different.

Some other Lisp dialects provide implementations of flet and labels. The ones I'm aware of are Common Lisp and Emacs Lisp.

Summary

What you've seen above are some basics and a few more advanced features of SKILL++. Using local functions makes your SKILL++ code more self-contained without sacrificing modularity. And it's pretty easy to use SKILL++ on practical, easy to understand problems.

We'll look at some more examples in future articles.

See Also:

• Lexical vs. dynamic scoping
• flet and labels in Common Lisp and Emacs Lisp.

Jim Newton