On: Static Type Checking in Common Lisp

[reikonomusha]

Neither of your examples allow the branch bodies to capture the lexical environment seen at the time of the jump. Nobody disputes that it’s possible to make a vector of function pointers.

Write your second example where the lambda bodies depend on the function parameter i, or indeed any other binding in the scope of the “jump”. This is a very normal and natural thing to do in other languages, such as C. Forget big-O, complexity, whatever. In a language such as C, you incur no runtime penalty for using local scope in the branches.

In Common Lisp, you incur a runtime penalty dependent on the size of the table. This penalty rears its head either in the number of comparisons that must be made to find the branch (dependent on the size of the table), or in terms of memory allocation (allocating closures for each branch). Either of those penalties can be expressed as a linear (or at least non-constant) function in the size of the table.

You are incorrect that lexical scope is at odds with a jump table. This can be formally proven, but it has also been empirically shown in actual (non-portable) implementations of a jump table.

[ohyes → reikonomusha]

Here you go.

  (defvar *my-variable* nil)
  
  (let ((jump-table (vector (lambda () (list 'a *my-variable*))
                            (lambda () (list 'b *my-variable*))
                            (lambda () (list 'c *my-variable*))
                            (lambda () (list 'd *my-variable*)))))
    (defun jump-table-caller3 (i)
      (let ((*my-variable* i))
        (funcall (aref jump-table i)))))

It's getting late for me so I'm headed to sleep, but this has been interesting, thanks!

[reikonomusha → ohyes]

This is dynamic scope, not lexical. They are not equivalent. You might further attempt to solve this by locally binding a lexical variable of the same name to the special variable, in order to “recreate” the lexical environment. (A quicker way to do this would be to pass these values to the branch functions directly.)

You will quickly find that this also will not work, for if a closure was made inside of each branch, the environment would not be shared among them.

The original intent of this exercise was to demonstrate you can’t macro your way out of all deficiencies in Lisp. And certainly in this case, even if we were to accept this dynamic variable rigamarole, we would find that we could not write a macro that, e.g., replaces CASE.