I have a (hopefully) very simple question for you all lisp experts:
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!
In "real life" capacity is always important and numerical
values used in compressed branching tables are needed,
but how can it be used in LISP?
In article <··········@erinews.ericsson.se>, ·······@garbo.ericsson.se
(Mikael Wittberg) wrote:
> Is it possible to declare and use enumerated symbols in Lisp?
>
> In C we have
>
> 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:
>
> [3-case switch statement omitted]
>
> This statement is really fast, but:
>
> [equivalent chained-IF sequence]
>
> Is terribly slow ...
[Not necessarily, BTW: in your example the chained IF tests are probably
faster--in fact, your C compiler will likely turn your short "switch"
statement into one instead of using a jump table; tables only make sense
for large, dense case sets]
> 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?
No, because in Lisp you can have literal constants which aren't numbers,
but actual symbols:
(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.
pch
···@mystech.com (Pete Halverson) writes:
>In article <··········@erinews.ericsson.se>, ·······@garbo.ericsson.se
>(Mikael Wittberg) wrote:
>> Is it possible to declare and use enumerated symbols in Lisp?
>> .......
>> 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?
>No, because in Lisp you can have literal constants which aren't numbers,
>but actual symbols:
> (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.
The usage of lisp keywords are not really what I want, they fail
in two respects:
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.
>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.
I appreciate the symbolic nature of lisp which I find very powerful..
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.
Mikael.
One way to handle your combination of enumerated types and CASE statements
in LISP is to take advantage of the fact that your input values are
0, 1, 2, ..., n
- 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.
Mike
(······@cs.utexas.edu)
······@cs.utexas.edu (Micheal S. Hewett) writes:
>One way to handle your combination of enumerated types and CASE statements
>in LISP is to take advantage of the fact that your input values are
>0, 1, 2, ..., n
>- 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.
>Mike
>(······@cs.utexas.edu)
The idea of using an array of functions is very good in capacity.
But of course we have to be very careful that we assign the correct function
to the correct index in the array, a misstake here and we have a problem...
So the solution works, but I would dream of having an even better one!
·······@garbo.ericsson.se (Mikael Wittberg) writes:
> 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.
Don't worry about this one. Prolog systems do it _well_ all the time
(the good ones); there's no reason to expect Lisp to be bad at it.
> 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.
What do you mean "costly in capacity"? It is no more than
(defun colour-index->colour-name (index)
(aref '#(red white blue) index))
which is a Good Thing to have around anyway for printing the values
readably.
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.
--
"The complex-type shall be a simple-type." ISO 10206:1991 (Extended Pascal)
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.
··@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes:
>·······@garbo.ericsson.se (Mikael Wittberg) writes:
>> 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.
>Don't worry about this one. Prolog systems do it _well_ all the time
>(the good ones); there's no reason to expect Lisp to be bad at it.
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?
/Mikael
[Mikael Wittberg]
| 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.
#<Erik>
--
sufficiently advanced political correctness is indistinguishable from irony
Mikael Wittberg (·······@garbo.ericsson.se) wrote:
> 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.
In KCL (which is now GNU Common Lisp), you can get efficient code by using CASE
and dispatching on FIXNUMs. CASE statements such as this are converted to
C 'switch' statements by the KCL compiler:
(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,
Jens.
Mikael Wittberg <·······@garbo.ericsson.se> writes:
> Is it possible to declare and use enumerated symbols in Lisp?
>
> In C we have
>
> 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, ...
As Pete Halverson already pointed out, the lispy way to do this is to
use keywords. But if you want them to be numbers try this:
(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.
Kevin Gallagher
In article <...> ·······@garbo.ericsson.se (Mikael Wittberg) writes:
> 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!
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.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu