[ohyes]

O(n) and O(1) are an inappropriate and incorrect way of describing what you guys are taking issue with. These functions all run in constant O(1) time. The argument being made by you all is extremely confusing because of the incorrect terminology. What you all are actually complaining about is the branching complexity and performance of the underlying assembly code.

This is further confused by the inclusion of 'lexical scope' as a priority. Lexical scope is a thing, and of course the jump table will have to do more work if handling lexical scope involved. If you aren't managing the stack, you aren't dealing with lexical scope appropriately. You have incompatible requirements here.

If you were simulating the equivalent of a C jump table, you would simply have an array of functions, and you'd call the function that you want based on a reference.

This is very easy to do in common lisp, trivial in fact, so I'm a little confused about what the commotion is about, in that case.

  (defvar *jump-table* (vector (lambda () 'a) (lambda () 'b) (lambda () 'c) (lambda () 'd)))
   
  (defun jump-table-caller (i)
    (funcall (aref *jump-table* i)))
   

  (let ((jump-table (vector (lambda () 'a) (lambda () 'b) (lambda () 'c) (lambda () 'd))))
    (defun jump-table-caller2 (i)
      (funcall (aref jump-table i))))

Is the issue then, that it doesn't produce the correct machine language instructions? That seems to be an implementation detail of the compiler honestly more than anything else.

[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]

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]

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.