[ohyes]

Well, you have to make the go statement in lexical scope in order for the tagbody to work... that seems reasonable enough to me. You specifically stated:

> Implement an O(1) jump table in Common Lisp that respects the lexical environment.

You don't know the lexical environment until there's a lexical environment to know, you can't have your cake and also eat it (or not have your cake and also know it).

Interestingly, try/catch also solves this problem fairly elegantly without distastefully consing up a list or array at run-time.

  (defun jump2 (i)
    (let ((location nil))
      (tagbody
         (catch 'a
           (catch 'b
             (catch 'c
               (catch 'd
                 (setf location (elt #(a b c d) i))
                 (throw location nil))
               (when location
                 (print "D!")
                 (go end)))
             (when location
               (print "C!")
               (go end)))
           (when location
             (print "B!")
             (go end)))
         (when location
           (print "A!")
           (go end))
       end)))

I'll leave the relevant macro to the reader, it shouldn't be that difficult... (I'm hoping I didn't just do someone's homework).

edit: removed some cruft from experiments and fixed formatting

[dan-robertson]

Well here you can replace the tagbody with a block and replace the (go end) with an appropriate (return) instead do you can get results out of your jump table.

But that’s beside the point because in practice this is probably O(n) not O(1). I think most CL compilers are going to need to push things to the control stack for each catch. Even if the compiler is clever enough to eliminate the catches, it still mightn’t implement the computation of which catch catches as O(n). So even in the best case of a very smart compiler, your code is basically equivalent to:

  (case i
    (0 (print "A!"))
    (1 ...))

Which isn’t guaranteed to be O(1).

The point the GP is making is that the only solution which looks like it might O(1) (and indeed is O(1) if there is no (or just one) lexical scope to capture) is the array-of-lambdas-doing-go, but that this isn’t guaranteed by the language to be O(1) when the lexical scope changes each time because in a naive evaluation, the array of lambdas must be consed before jumping and this is O(n).

The reason that it is reasonable to complain about this is that what one needs for a jump table is weaker than this. The lambdas do capture the lexical scope but they only have dynamic extent and don’t extend the scope at all so a lambda of the form (lambda () (go foo)) only has to be consed each time you hit the jump table because you can only reference foo once you are inside the tagbody. However the code to actually jump is likely to be static for most compilers.

For guaranteed O(1) performance (which doesn’t rely on the cleverness of the compiler) you’d need to introduce a new special form, e.g. (jump n tag1 tag2 ... tagn) which evaluates n and jumps to the nth tag in its arguments in O(1) time.

[reikonomusha]

This is an excellent breakdown and is exactly right. Paul Khuong, an SBCL developer, took exactly this approach you mentioned in a purely experimental implementation of a computed-GO; he essentially added a special form to the guts of the compiler. But that required exactly what you might think: hand-coded assembly and new nodes to SBCL’s IR.

I think this is a fine demonstration of not being able to “macro your way” out of a problem.

As for a sufficiently smart compiler, it probably can’t optimize CATCH/THROW since those have dynamic extent to all callees. The compiler will certainly not be able to prove that a function won’t possibly throw a tag down deep somewhere.

[dan-robertson]

Regarding catch/throw, I don’t believe any current CL implementation could optimise this but:

- if the prints were changed to go outside of the catches before executing (ie so the compiler could know that they wouldn’t throw) then I think a sufficiently smart compiler could prove that nothing else could throw here (it would be allowed to know that elt wouldn’t throw)

- If I recall correctly, there are java compilers which can optimize throw-inside-catch code to not need the catch on the control stack. (Ie the throw is just compiled into a goto)

- some languages allow one to throw things that are unique to the function call which gives a better chance of them being unique.

[gumby]

Btw C++ has the same catch/throw issue. Herb Sutter has proposed a clever approach (essentially using tag bits in the return value) to mitigate the cost.

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

[reikonomusha]

Do note that THROW/CATCH are dynamically established, and each CATCH setup + THROW invocation take a small amount of runtime. THROW usually takes linear time in the number of enclosing CATCH forms. So, despite how it looks, this solution is still linear in both space and time in the number of branches. (This is the same if you were to bind a special variable N times. The setup and tear down aren’t statically or lexically determined.)