Path: utzoo!censor!becker!geac!jtsv16!uunet!samsung!gem.mps.ohio-state.edu!tut.cis.ohio-state.edu!ucbvax!cogsci.berkeley.edu!norvig
From: norvig@cogsci.berkeley.edu (Peter Norvig)
Newsgroups: comp.lang.lisp
Subject: Can there be an efficient SWITCH form in CL?
Message-ID: <32711@ucbvax.BERKELEY.EDU>
Date: 21 Nov 89 00:51:29 GMT
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: norvig@cogsci.berkeley.edu (Peter Norvig)
Distribution: usa
Organization: University of California, Berkeley
Lines: 55

Many languages support a syntactic construct that compiles into a
dispatch table.  For example, in C, the statement:

switch(opcode) {
  case 0: /* noop */ break;
  case 1: acc+=arg;  break;
  case 2: acc-=arg;  break;
  ...
  }

can (at the compiler's discretion) dispatch directly to the right code
fragment, rather than comparing the key (opcode) against each case.  In
Common Lisp, one could use CASE and hope that the compiler optimizes
into a dispatch table when appropriate, but in my experience compilers
do not make this optimization.  I tried to write a macro to do this, but
it proved difficult.  For simplicity, let's ignore the key processing of
SWITCH; and try to implement a zero-based computed-goto.  Thus, the
fragment above would be:

(computed-goto opcode
  () ; noop
  (incf acc arg)
  (decf acc arg)
  ...
  )

And my first attempt at the macro is:

(defmacro computed-goto (key &rest clauses)
  `(funcall
    (aref (vector ,@(loop for c in clauses collect `#'(lambda () ,c)))
	  ,key)))

This works, but it conses the vector and possibly some closures
on each application, so it is very inefficient.  We need to create
the vector at compile time.  Consider:

(defmacro computed-goto (key &rest clauses)
  `(funcall
    (aref ',(apply #'vector (loop for c in clauses collect `#'(lambda () ,c)))
	  ,key)))

This produces a constant vector, but the vector holds s-expressions, not
closures, so local variables like acc and arg are not accessible.  We
could try evaluating the `#'(lambda () ,c) expressions, but they have to
be evaluated in the calling environment, not the compiler's environment,
and the calling environment can change each time.  Thus, I conclude that
an efficient computed-goto cannot be written in Common Lisp.

Does anybody have another approach?  Or should we just insist that
compiler writers produce better code for (CASE n ...), and for
(aref (vector ...) n)?


- Peter Norvig					norvig@cogsci.Berkeley.EDU