Steel Bank Common Lisp

Hello Martin,

Martin C. Martin wrote:
> Is there a common idiom for macros that need two passes?  For example,
> suppose I have a macro that takes a keyword, and when expanded, pushes
> the keyword onto a global list.  Once all instances of the macro have
> been expanded, so we have the full set of keywords, we then figure out a
> perfect hash function for the keywords, and replace each instance of the
> keyword with its hash.

What good would that do? Do you have a pseudo-code example?

  Leslie

-- 
http://www.linkedin.com/in/polzer

"Martin C. Martin" <martin@...> writes:

> Is there a common idiom for macros that need two passes?  For example, 
> suppose I have a macro that takes a keyword, and when expanded, pushes 
> the keyword onto a global list.  Once all instances of the macro have 
> been expanded, so we have the full set of keywords, we then figure out a 
> perfect hash function for the keywords, and replace each instance of the 
> keyword with its hash.  Is there a standard way to do this in Common 
> Lisp?  Is it possible?

In general it's not possible portably without using a code-walker.

I think you could come up with a kludgy but portable solution which
would work as long as the whole frobbage happens in the same file, and
you always compile the file.

In case of SBCL that solution would could also work across multiple
files (compile-time effects affect the environment in which COMPILE-FILE
was run), though it would easily get very hairy.


Is the scope bound by a surrounding form? I.e. is it like

  (with-registered-keywords (...)
    ... (register-keyword :foo) ...
    ... (register-keyword :bar) ... )

For something like that, a code walker is ideal. Take a look at cl-walker on
common-lisp.net. If you do not want drag in that dependency, take a look
at SB-WALK. In particular,

   (let ((sb-walker:*walk-form-expand-macros-p* t))
    (sb-walker:walk-form form))

is MACROEXPAND-ALL which you can call in WITH-REGISTERED-KEYWORDS to
expand all the REGISTER-KEYWORD which would push to a locally
established list.


If you don't want the surrounding form, but are content with file-only
scope, you could perhaps do something like

  (declaim (special *perfect-hashtable*))

  (eval-when (:compile-toplevel)
    (defvar *compiling* t)
    (defvar *keywords* nil))
  (eval-when (:load-toplevel :execute)
    (defvar *compiling* nil))

  (defmacro register-keyword (keyword)
    (when *compiling*
      (push keyword *keywords*))
    `(whatever ...))

  ....

  (macrolet ((define-perfect-hashtable (...)
                `(defvar *perfect-hashtable*
                         (create-perfect-hashtable
                            :keywords ,@*keywords*))))
    (define-perfect-hashtable ...))
                            

And don't forget to always compile that file. :-)

  -T.

2009/5/14 Martin C. Martin <martin@...>:
> Is there a common idiom for macros that need two passes?  For example,
> suppose I have a macro that takes a keyword, and when expanded, pushes
> the keyword onto a global list.  Once all instances of the macro have
> been expanded, so we have the full set of keywords, we then figure out a
> perfect hash function for the keywords, and replace each instance of the
> keyword with its hash.  Is there a standard way to do this in Common
> Lisp?  Is it possible?

LOAD-TIME-VALUE probably comes closest in terms of how people usually
implement optimizations like yours:

;;; Of the first time COMPUTE-PERFECT-HASH is called it should probably arrange
;;; for future calls to REGISTER-NAME for new names to signal an
error, or something.
(define-compiler-macro get-by-name (&whole form name store)
  (cond ((constantp name)
         (register-name name)
         `(%get-by-hash (load-time-value (compute-perfect-hash ',name)) ,store))
        (t
         form)))

The other option is to expand into a call to a function (one function
per constant key), and define those functions at the very end with a
macro:

(defmacro define-optimized-hash-accessors ()
  `(progn
     ,@(mapcar (lambda (spec)
                 (destructuring-bind (key fname) spec
                   `(defun ,fname (store)
                      (%get-by-hash ,(compute-perfect-hash key) store))))
               *collected-keyword-specs*)))

The final option -- to do exactly what you say -- is to write your own
preprocessor... but I'm thinking LOAD-TIME-VALUE is probably what you
want.

Though for your specific _example_ I would probably require separately
defining each hash key before it can be used -- one mammoth
DEFINE-PERFECT-HASH with all the keys in there.

Cheers,

 -- Nikodemus