On Macros, Eval and Generated Code in Lisp.
; Unlike Common Lisp or Scheme macros, Newlisp macros do not expand ; during compile time; instead, these are evaluated during runtime, ; similarly like functions. ; ; That kind of macros - under the name of fexprs - existed in older ; dialects of Lisp. Probably the most influential work on fexprs ; is Kent Pitman's "Special Forms in Lisp" presented at 1980s' ; Lisp Conference. Pitman described few reasons pro and contra ; fexprs and macros and advised omission of fexprs from the future ; Lisp dialects. Regarding runtime efficiency, Pitman argues that ; "In the compiler, MACRO's are used to transform source code into ; compilable code which contains no MACRO forms. Hence, a MACRO ; definition can in some sense afford to use more time in its ; transformation than any other type of operator can afford to ; do in similar case analysis at runtime. This is because a macro ; form will be expanded exactly once (at compile time) while any ; other type of operator may be called repeatedly at runtime and ; will have to make decisions anew each time it is called." ; ; However, it is not discussed what happens if the same code has ; to be evaluated only once or few times, especially if code is ; generated during runtime. In that case macroexpansion itself ; might require significant, theoretically unlimited time. ; ; ; I'll demonstrate it by comparing evaluation times of one Lisp ; expression in recent implementation of Newlisp and six versions ; of the CL: Allegro, Clozure, Corman, LispWorks, GNU CL and GNU ; Clisp. The code is ; (dotimes (i 177000) (eval '(at-least 6 t ;;For Newlisp use true, not t nil nil nil nil nil t nil nil nil nil nil t nil nil nil nil nil t nil nil nil nil nil))) ; Where at-least is macro, generalized version of the operator ; OR. For example (at-least 2 (= x 3) (> 7 2) (= 6 6)) is true ; if and only if, well, at least two of these expressions are true. ; The purpose of the loop (dotimes(i 177000) is only to allow me ; to measure the time of the evaluation of the expression inside. ; Otherwise, running time would be too short. Nothing else. ; So, no, main expression, compilation or macroexpansion ; cannot be factored out of loop. ; Strange number 177000 was my rough estimation of realistic evaluation. ; time. The form (eval '(....)) is used because I want to replicate ; the situation in which code is generated during runtime. ; ; I use only t and nil to minimize influence of other operations ; on test. But, the macros I'll use are defined for general case, ; discussed in the previous post Challenged by Common Lispers: ; ;;Newlisp - author Kazimir Majorinc (define-macro (at-least at-least_n) (let ((at-least_en (eval at-least_n))) (doargs(at-least_i (zero? at-least_en)) (when (eval at-least_i) (dec at-least_en))) (zero? at-least_en))) ;;Common Lisp - author Raffael Cavallaro (defmacro at-least (n &rest es &aux (nsym (gensym)) (carsym (gensym))) (if (null es) nil `(let ((,nsym ,n)) (if (zerop ,nsym) t (let ((,carsym ,(car es))) (if (= ,nsym 1) (or ,carsym ,@`,(cdr es)) (at-least (if ,carsym (1- ,nsym) ,nsym) ,@`,(cdr es)))))))) ;; Common Lisp - author Rainer Joswig [doesn't work for n=0] (defmacro at-least (n &rest es &aux (c (gensym))) `(let ((,c 0)) (or ,@(loop for e in es collect `(and ,e (= (incf ,c) ,n)))))) ################# # THE RESULTS # ################# | Majorinc | Cavallaro | Joswig ======================================================= Newlisp 10.0.3 | 1.115 | X | X ------------------------------------------------------- Gnu Clisp 2.43 | X | 81.323 | 27.533 ------------------------------------------------------- Gnu CL 2.6.1 | X | 77.033 | 29.617 ------------------------------------------------------- ABCL 0.18 | X | 135.862 | 38.301 ------------------------------------------------------- Lispworks 5.1 | X | 156.018 | 48.374 ------------------------------------------------------- Allegro 8.1 | X | 1296.929 | 382.676 ------------------------------------------------------- Corman 3.01 | X | 8900.000 | 987.907 ------------------------------------------------------- Clozure 1.3 | X | 23000.000 | 1871.000 ------------------------------------------------------- SBCL 1.0.29 | X | 12800.000 | 3700.000 ------------------------------------------------------- ; all times are expressed in seconds. The numbers for Clozure and SBCL ; are estimations: loop was evaluated 17700 times and result was ; multiplied with ten. ; As you can see, in this particular case, using macros writen ; by me and two competent Common Lisp programmers, and few existing ; Common Lisp implementations working on Windows, Common Lisp is ; between 25 and 25 000 times slower. Hence, Common Lisp kind of ; macros slows down evaluation of the code generated during runtime ; considerably, while Newlisp style macros also known as fexprs do not ; have such effect. ; ; Furthermore, note that many Common Lisp built in operators (setf, ; push, pop ...) are defined as macros and cannot be easily avoided. ; ; Common Lisp advocates can argue that their programs are faster ; if they do not have to generate and evaluate code during runtime ; and time spent for compilation and macroexpansion doesn't count. ; |
Subscribe to:
Posts (Atom)