Re: A "killer" macro
- From: Eli Bendersky <eliben@xxxxxxxxx>
- Date: Thu, 13 Sep 2007 09:11:41 -0000
On Sep 12, 7:54 pm, Alan Crowe <a...@xxxxxxxxxxxxxxxxxxxxxxx> wrote:
Eli Bendersky <eli...@xxxxxxxxx> writes:
In short: I'm looking for a "killer" macro - a macro (or a couple of
related ones) that show what Lisp can do and other languages (those
without uniform syntax) can not.
Any suggestions for such an example ?
Many computer programming languages have the concept of an
enumeration or symbolic constant. At compile time the
constant is a string of characters, meaningful to humans,
but comparision is character by character, so long names are
slower than short names. At run time this name has gone
away, leaving a number fitting in a machine word. So items
from small sets are represented efficiently, as a code
number in a machine word, while the programmer does not have
to learn the code numbers. He programs with symbolic names.
Lisp has a better idea - the translation from names to
numbers takes place at read time, and the number is the
address of the symbol. We get the efficiency of representing
the constant as a single word, but the name is still
available at run-time.
However, sometimes the coding scheme for these code numbers
is not internal to the program. Sometimes the numbers come
from outside, as for example in the instruction set of a
microprocessor. The first idea here is something like
(defconstant load 8)
(defconstant store 9)
but CL:CASE stops working.
(case mnemonic
(load ....)
(store ...)
has to be replace by
(case mnemonic
(8 ...)
(9 ...)
which is unacceptable.
A better idea is to stick with symbols and write assemby and
disassembly functions, so that
(motorola6800 'load) => 10
(intel8086 'load) => 32
(motorola6800 10) => load
(intel8086 10) => decrement
or whatever, I don't know the actual code.
Well, that is a potentially better idea. You don't what to
be stuck for hours typing these things. You want want to be
type in something simple, such as
(define-opcodes mc6809
(8 load store
16 add sub mul div
24 fetch write))
On the other hand, they might get heavily used, the program
had better scale well. The target is for constant time
translation, regardless of the number of opcodes.
So one design is to have a vector of symbols, with each
symbol in the right place to be looked up directly, and to
use the machine name as an indicator on each symbols plist,
giving the opcode behind that mnemonic on that architecture.
At this point I just paste in the file from alan/lisp/utils
#| the built in case macro doesn't evaluate the keys
This causes grief when you want symbols to work like C-style
#define LOAD 0
#define STORE 3
#define ADD 4
#define SUBTRACT 5
(defmacro define-opcodes ... )
(define-opcodes octium (0 load 3 store add subtract))
and then you have
(octium 'store) => 3
(octium 4) => add
You work with symbols and case works fine.
The bonus is that you can define different encodings and
parameterise your assembler and dis-assembler
(funcall #'machine opcode) => mnemonic
|#
(defmacro define-opcodes (machine condensed-list)
"number mnemonic mnemnonic number ...."
(let* ((code-assoc (expand condensed-list))
(least-opcode (reduce #'min code-assoc :key #'cdr)))
`(let ((opcode-vector ,(make-decode-table code-assoc least-opcode))
(least-opcode ,least-opcode))
(defun ,machine (thing)
(etypecase thing
(number (aref opcode-vector (- thing least-opcode)))
(symbol (get thing ',machine))))
,(cons 'setf
(loop for (mnemonic . code) in code-assoc
append
`((get ',mnemonic ',machine) ,code)))
',machine)))
(defun expand (list)
(let ((expansion '())
(index 0))
(dolist (item list expansion)
(etypecase item
(symbol (push (cons item index) expansion)
(incf index))
((integer 0) (setf index item))))))
(defun make-decode-table (code-assoc least-opcode)
(let ((greatest-opcode (reduce #'max
code-assoc
:key #'cdr)))
(let ((table (make-array (+ 1 (- greatest-opcode
least-opcode)))))
(loop for (mnemonic . code) in code-assoc
do (setf (aref table (- code least-opcode))
mnemonic))
table)))
Quite a short file.
(macroexpand-1 '(define-opcodes mc6809
(8 load store
16 add sub mul div
24 fetch write)))
=>
(LET ((OPCODE-VECTOR
#(LOAD STORE 0 0 0 0 0 0 ADD SUB MUL DIV 0 0 0 0 FETCH WRITE))
(LEAST-OPCODE 8))
(DEFUN MC6809 (THING)
(ETYPECASE THING
(NUMBER (AREF OPCODE-VECTOR (- THING LEAST-OPCODE)))
(SYMBOL (GET THING 'MC6809))))
(SETF (GET 'WRITE 'MC6809)
25
(GET 'FETCH 'MC6809)
24
(GET 'DIV 'MC6809)
19
(GET 'MUL 'MC6809)
18
(GET 'SUB 'MC6809)
17
(GET 'ADD 'MC6809)
16
(GET 'STORE 'MC6809)
9
(GET 'LOAD 'MC6809)
8)
'MC6809)
T
I've not used this for real. If I were going to I would add
more error checking (and some eval-when), which would make
it more complicated and less useful as a simple example.
I think it serves to bring out the idea of writing code, and
not just pasting code into a template, while being
unsophisticated enough to explain to non-lispers.
Alan Crowe
Edinburgh
Scotland
Alan,
This is an interesting example, but except for the minor nicety of
opcode numbers growing automatically, it looks just like a
sophisticated way to work around the limitations of the "case" macro.
Why not just write an "evaluating case" macro and get done with it ?
Writing macros to overcome problems in other macros isn't a good
example of a language's power. Besides, someone can correctly note he
just does this easily in C:
#define LOAD 0
#define STORE 3
#define ADD STORE+1
#define SUBTRACT STORE+2
.
- References:
- A "killer" macro
- From: Eli Bendersky
- Re: A "killer" macro
- From: Alan Crowe
- A "killer" macro
- Prev by Date: Re: Trying to learn Common Lisp
- Next by Date: Re: A "killer" macro
- Previous by thread: Re: A "killer" macro
- Next by thread: Re: A "killer" macro
- Index(es):
Relevant Pages
|
