Implementing case-lambda for SKILL++

For a few years now, my day job at Cadence Design Systems has been working on Virtuoso Schematic Editor. Virtuoso is the most widely-used tool for designing analogue and mixed-signal integrated circuits. For reasons of commercial confidentiality, I haven't been able to write much about my work.

Virtuoso can be customized extensively by writing code in the SKILL programming language. This is a Lisp. It actually comes in 2 variants:

• SKILL, which is a variant of Common Lisp
• SKILL++, which is a variant of ANSI Scheme.

I do as much of my work as possible in SKILL++, and in recent years I have created a bunch of internal development tools to help me with that. This has included implementing some of the Scheme Requests For Implementation (SRFIs), because they describe well-thought-out and useful libraries that SKILL++ doesn't provide.

I recently came across a situation where I really needed the ability to define a procedure that could be called in two different ways. When this procedure was originally added decades ago, it could only be called with a lot of positional arguments, something like:

(someFunc 1 2 3 4 5 6 7 8)

Most callers of the procedure only ever need to pass meaningful values to a few of these parameters. This meant that a lot of the calls looked like this:

(someFunc nil nil nil nil nil importantValue nil nil)

This produced verbose code and hard-to-read code, and it was impossible to correctly write code using this procedure without having the product manual to hand to know where to put the importantValue. Was it the 5th or 6th parameter?

So, we wanted to allow myFunc to be called with named arguments, to make the code more concise and self-explanatory. Something like:

(someFunc ?sixthParam importantValue)

However, this presented a challenge. How do you make a function that can be called both with positional arguments (because we don't want to break any existing code that uses it), and with keyword arguments (for new, improved usage?

Designing caseLambda for SKILL

SRFI-16, Syntax for procedures of variable arity, provides the outline of a solution. It proposes the case-lambda syntax, that creates a function that dispatches between alternatives depending on how many arguments it takes.

(define plus
  (case-lambda 
    (() 0)
    ((x) x)
    ((x y) (+ x y))
    ((x y z) (+ (+ x y) z))
    (args (apply + args))))

Two properties are immediately notable:

1. SRFI-16 only defines syntax that works for clauses with fixed numbers of positional arguments, or which accept any number of arguments. For my use-case, I would need to extend the syntax.
2. The rule is first match, i.e. when called with some set of arguments, the first clause which could be called with those arguments are selected. If there were 2 clauses with 5 arguments, only the first would ever actually end up getting called.

SKILL has built-in syntax for allowing procedures to be defined with either optional or keyword arguments:

;; Function that writes to a file if given, otherwise to standard output
(define (writeString text @optional filename)
  (let ((port (if filename (outfile filename) poport)))
    (write text port)))
    
;; Using keyword arguments to allow specifying port or filename
(define (writeString text @key port filename)
  (let ((port (cond
                (port port)
                (filename (outfile filename))
                poport)))
    (write text port)))

The final design challenge was related to the way that keyword arguments work in SKILL. In SKILL, any symbol that starts with a ? character is a keyword and is self-evaluating. It's otherwise just a regular value. This means that a function that accepts positional parameters can happily consume a keyword as a regular argument. Take the built-in list constructor, for example:

(list ?hello world)
--> (?hello world)

The current recommendation in the community of Scheme implementers is that you shouldn't have self-evaluating keywords, and that keywords should have special handling rather than being treated as ordinary data. Well, that genie fled the bottle in 1993; no putting it back in now!

So, the design I settled on was very strict first match: the first clause of the caseLambda that can be called with the provided argument list will be selected, no matter what. This requires some caution in writing functions that use it:

(define ohNo
  (caseLambda
    ((x y)      'positional)
    ((@key x y) 'keyword)))

(ohNo ?x 42)
--> positional

I came up with some guidelines to get the best success when using SKILL caseLambda:

1. Put your clauses in increasing order of number of required arguments, followed by increasing order of optional arguments.
2. Put @key clauses before @optional clauses.
3. N-ary clause (with @rest clauses) will almost always prevent any subsequent clauses from being reachable, so you can really have at most one N-ary clause per caseLambda.

Implementation challenges

SRFI-16's reference implementation is written entirely in syntax-rules. This is neat, because you can get case-lambda without any special support from your Scheme implementation!

However, this didn't seem like a good approach for adding caseLambda to SKILL.

When a SKILL function is called, the SKILL bytecode virtual machine already has to check the arguments passed against the function's parameter list to make sure the call is valid, and so the information about the positional and keyword parameters of each function are baked into every function object. I decided it would be better to make a generic matcher that could use this information, than to write a complicated metaprogram to generate a custom matcher for each caseLambda.

I therefore decided to implement caseLambda as a very simple macro that compiles each clause into a function object, and then dispatches to a primitive to choose between the clauses at runtime. Something almost but not exactly like:

(define-syntax caseLambda
  (syntax-rules ()
    ((caseLambda "CLAUSE" (formals expr ...))
     (lambda formals expr ...))
    ((caseLambda clause ...
     (lambda args
       (apply (%caseLambda-match% args (caseLambda "CLAUSE" clause) ...)
              args)))))

This approach is faster to compile, easier to implement and maintain, and generates much smaller bytecode. All complexity is contained in the matcher primitive, which is reused for every caseLambda function.

I suspect that it would have been even better to make caseLambda into compiler builtin syntax and add "case function" objects into the data model, so that the bytecode virtual machine could choose between clauses simultaneously with validating the argument list for the call. As far as I can tell, most Scheme implementations that have both keyword-based function calls and case-lambda implement it as a builtin.

Conclusions

I'd been hankering after this language feature for a few years, but I'd been putting it off because it seemed unreasonably difficult. I was fiddling with something related when I suddenly had the inspiration for how to do this and, in the end, it only took me a couple of days to get it to the point that I feel happy using it in production.

Perhaps you are a customer CAD team engineer who happens to be reading this and thinking, "This sounds useful! Can I use it?" Alas, the answer is no -- pretty much all of the work I've been doing on SKILL++ libraries and development tools is for use only by Cadence R&D. Sorry!