Is it possible to declare and use enumerated symbols in Lisp?

  In C we have of course the enum type definition:

    typedef enum colours {
      RED, BLUE, BLACK
    } colours;

  This defines three constants RED (value 0), BLUE (value 1) and
  BLACK (value 2). When coding in C we do not need to ever
  reference these values as numbers we can always use the
  enumerated symbolic names. Also the "switch" statement in C
  is useful here, we can easily make a very fast decision
  branch statement that is implemented as a table, we do not
  need to implement three if statements, example:

    switch (my_colour) {
      case RED:
        ...
      case BLUE:
        ...
      case BLACK:
        ...
    }

  This statement is really fast, but:

    if (my_colour == RED) {
    }
    else if (my_colour == BLUE) {
    }
    else if (my_colour == BLACK) {
    }

  Is terribly slow ...

  I know there is a statement in LISP that you use as the
  C switch statement (called CASE?) but it seems that this
  statement requires a constant, does this mean that you
  must use literal numbers here? If so I do not like it!

      (case my-colour  
        (:red ...)
        (:blue ...)
        (:black ...))

The :RED, :BLUE, and :BLACK tokens in this fragment aren't program
constructs which stand for numbers, they are first-class literal values
that can be assigned, passed as arguments to functions, compared to other
variable values, and otherwise used as you would integers, characters,
floating point values, or any other primitive type.

This ability to work directly with symbols, rather than having to use
barely-disguised numbers to represent symbolic data, is generally
recognized as one of the major strengths of Lisp.

  1. They may be represented internally by big numbers which make
     the branching (CASE) on these values slow, that is if you
     have many values that you need to branch on.

  2. In my actual problem I read in literal numbers from a file
     (0, 1, 2,...) so I am restricted in using these values.
     I could possible convert these numbers to keywords when I
     read them, but that is of course costly in capacity and it
     forces me to write a converter function.

But in a few cases, like the one above, I would also like to be
able to use a more efficient programming construct. I am really
only after a way to solve this problem in lisp, even if the possible
solutions are not very easily expressed in lisp.

Lisp experts have pointed out to me that by using DEFCONSTANT you can
define symbolic names to represent numbers, and you can even define
your own macro (called DEFENUM?) that will automatically define constants
with increasing numbers as there values. This solution is ok, even though
not perfect.

- Write a LISP function to handle each distinct branch of the CASE
  statement.

- Create an array [0..n] of function pointers and initialize it
  to contain the CASE branch functions.

- Your code is then:

  (setq value (read ...))
  (funcall (aref my-case value) <args>)

I don't think you can get much faster than that in any language.

(defenum red green blue)

(defun foo (x)
  (my-case x
    (red   ...)
    (green ...)
    (blue  ...)))

The enabling macros:

(defmacro defenum (&rest names)
  (let ((value -1))
    `(progn
       ,@(mapcar #'(lambda (name)
                     `(defconstant ,name ,(incf value)))
                 names))))

;; You can call this `switch' if you wish...

(defmacro my-case (var &rest clauses)
  "My-case is similar to the normal Common Lisp case except that
   if the key of a clause is a constant symbol (i.e., declare by
   defconstant) then that symbols value at macro expansion time
   is used."
  (flet ((fixup-clause (clause)
           (let ((key (first clause)))
             (cond ((and (symbolp key)
                         (boundp key)
                         (constantp key))
                    `(,(symbol-value key) ,@(rest clause)))
                   (t
                    clause)))))
    `(case ,var
       ,@(mapcar #'fixup-clause clauses))))

You can add bells and whistles, but this should get you started.

Of course, if the file contains numbers rather than names, you will
want to use them.  But Common Lisp makes that easy too:

        (defconstant red 0     "Encodes RED in the FOO file")
        (defconstant white 1   "Encodes WHITE in the FOO file")
        (defconstant blue 2    "Encodes BLUE in the FOO file")

        ...
            (case colour-from-foo-file
                ((#.red)
                    --what to do for red--)
                ((#.white)
                    --what to do for white--)
                ((#.blue)
                    --what to do for blue--)
                (t
                    --what to do if it is none of them--))
        ...

Actually, if it was me, I'd just go ahead and do

            (cond
                ((eql red   colour-from-foo-file)
                    --what to do for red--)
                ((eql white colour-from-foo-file)
                    --what to do for white--)
                ((eql blue  colour-from-foo-file)
                    --what to do for blue--)
                (t
                    --what to do it if is none of them--))

Just because it has the _form_ of a sequence of tests against constants
(whose values are known to the compiler) doesn't mean that it won't use
a jump table, just as something having the _form_ of a (case) doesn't
mean it won't use a sequence of tests against constants.

        (defun dispatcher (selector)
          (declare (fixnum selector))

          (case
            (0
              (do-stuff-for-0-case))

            ((1 2)
              (do-stuff-for-1-and-2))

            (42
              (print *answer*))

            (otherwise
              (foo))))

Hope this helps,

  If the jump is represented by a table it will cost me:
    100 instructions.

  If the jump is represented by IF's it will cost me:
    100 * (100 / 2) = 5000 instructions on avarage.

This makes the execution difference = 5000/100 = 50.
Thus a program using the first aproach may execute 50
times quicker than the latter one. this is quite a difference
I would say!

Is it so that I can assume that a LISP compiler uses an efficient
algorithm to jump on large values? Can I assume for instance that
some kind of binary search is used?

|   I do not quite see why I should not worry about this one.  Say if I
|   need to make 100 branches on 100 numbers each time:
|  
|     If the jump is represented by a table it will cost me:
|       100 instructions.
|  
|     If the jump is represented by IF's it will cost me:
|       100 * (100 / 2) = 5000 instructions on avarage.
|  
|   This makes the execution difference = 5000/100 = 50.  Thus a program
|   using the first aproach may execute 50 times quicker than the latter
|   one. this is quite a difference I would say!
|  
|   Is it so that I can assume that a LISP compiler uses an efficient
|   algorithm to jump on large values? Can I assume for instance that some
|   kind of binary search is used?

what would it take for you to be satisifed with an answer, Mikael?  seems
like you're increasing desperately trying to show that Lisp is a bad
choice.  were you forced to use Lisp by someone who didn't listen to your
reservations?  if so, don't take it out on Lisp, please.

because the ability to reason about a Lisp program is so much higher than,
e.g., C programs, a compiler can be made arbitrarily intelligent and
optimizations could conceivably counter-act premature optimizations made by
programmers used to stupid compilers (that's you), in addition to make the
most efficient code there is.

you will find that run-time efficiency has a compile-time cost.  if you
want to fast compilation, you don't get fast execution.  in most Lisp
systems, you can tweak compiler speed, optimization, safety, etc, etc.

have you tried to read the manual to investigate the differences caused by
various compilation switches?  see the chapter on Declarations in CLtL2.

Well, if this is the critical bottleneck in the code, then you would
always be advised to code your algorithm to avoid having to do the
search.  But in Lisp, it is not clear that a jump table would
necessarily be the most efficient implementation.  (I don't think it
would be the most lisp-like either).  If you have a dense set of
numbers, then you could use the array of functions discussed earlier.

If the numbers are just an artifact of using enumerated symbols, where
the numerical relationship is not exploited to do any comparisons, the
normal lisp method of doing things would be to use symbols directly.  In
this case, one could define functions with the names of the symbols and
then  (funcall (symbol-function current-symbol)).

 > Is it so that I can assume that a LISP compiler uses an efficient
 > algorithm to jump on large values? Can I assume for instance that
 > some kind of binary search is used?

I don't think you can make any such assumptions about a language in
general.  In fact, I would be surprised if many lisp implementations did
anything at all fancy with case statements.  In part that is because
most times, case statements are used with symbols instead of numbers and
symbols don't have the nice ordering property that numbers would have.

There are many more efficient ways to program branching in lisp than by
writing a 100 clause case statement.