I am moving this blog to kazimirmajorinc.com.
In the meantime, some posts may be unavailable.

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.
;

6 comments:

  1. You can say what you want, that NewLisp names FEXPRs 'macros' does not make them macros. They are still FEXPRs. A totally different mechanism from macros. You are comparing apples and oranges. MACROS are defined by some expansion/replacement mechanism. That's how macros work in C, C++, macro assemplers, Lisp etc. Since Newlisp FEXPRs don't do macro expansion, they are no macros. They are just another evaluation strategy. Claiming that Newlisp FEXPRs are macros is just silly. Even if they can compute similar things does not make them macros. They simply lack an macro mechansim. The original idea of a macro is that it is a code template where parts of the expressions can be filled in - before runtime. People were using assembler and were tired to write similar expressions with some variations. So macros assemblers where used, where groups of instructions were used as a template, with some values filled in from macro parameters. The assembler then ran an macro expansion phase, before the assembly phase.

    Common Lisp advocates argue that they compile code like yours at runtime once and then call it repeatedly. Your example is trivial. It runs in 4ms on my laptop - including runtime compilation.

    ReplyDelete
  2. Do you understand why I have loop? It is just like I want to benchmark addition, and (+ 2 2) is too fast, so I do (dotimes(i 177000)(+ 2 2)). There is no point in "factoring out" addition and doing (dotimes(i 177000)4).

    On the same way, there is no point in factoring out compilation or macroexpansion in this example. I could rewrite this test so it makes 177000 different random expressions, and compiling is impossible. But there is no need for that.

    Then, about terminology, you are maybe right that fexpr would be historically or generally better. I am not sure, but you are maybe right. However, Newlisp author called it macro. I try to write on the way everyone understands me.

    ReplyDelete
  3. Everyone but Newlisp understands 'macro' to be something different. Better change the Newlisp terminology than confuse everybody but Newlisp users.

    You may want to work on examples where FEXPRs are actually useful.

    (dotimes (i 824082304) 4) - a Lisp compiler may replace that with just 4.

    (dotimes (i 8402983) (+ 2 2)) - still a Lisp compiler may replace that with 4.

    It simply makes no sense to evaluate code that is static in shape to evaluate over and over.
    The majority of code is like that. Common Lisp implementations are putting the optimizations into the compiler - because that is the default most developers use. Some popular implementations don't even have an interpreter anymore (SBCL) or don't use it by default (CCL).

    No matter how you want to sell Newlisp fexprs, for the majority of code a Lisp compiler will outperform Newlisp and its Fexprs by several orders of magnitudes.

    ReplyDelete
  4. fexprs are called macros in newLISP, because from an usage/application's point of view fexprs in newLISP are used for a similar *purpose* macros are used in Common Lisp: to write special forms with special evaluation rules. E.g. to write a form like "dotimes" in Common Lisp you would use a macro. If "dotimes" wouldn't exist in newLISP you could use fexprs (define-macro in newLISP) to do the same.

    L.M.

    ReplyDelete
  5. I don't have a car. I use a bicycle for shopping. Is my bicycle now a car?

    Languages BEFORE Common Lisp and neWLisp had already BOTH macros AND fexprs as DIFFERENT mechanisms. Newlisp has fexprs, no macros and named fexprs as macros.

    In languages like Common Lisp DOTIMES could also be implemented as functions: (my-dotimes 10 'print) would print the numbers from 0 to 9. Often code is implemented like that and the macro only improves the syntax, but the implementation is not done in the macro, it expands to the functional expression.

    ReplyDelete