I wrote a lisp interpreter, and I'm now finding that speed is
becoming important for me. Could any one supply me with
info on what order of magnitude speed up I can expect
(roughly) when I add in a byte-code compiler? (I do want to
keep it portable...)

   Thanks in advance.
   Ayal Pinkus

If what you mean by byte-code compiler is that the compiler generates byte
codes that are then interpreted by a byte-code interpreter, then you could
get Emacs (free).  Emacs implements a byte-code compiler and interpreter.
You could compare test code using your interpreter then with Emacs, which is
probably (my guess) as fast as your going to get for a p-code interpreter
(anyone know differently?).

I recommend that you FTP Emacs 19 as it includes a pretty full Common Lisp
addition.  You can FTP Emacs 19 from site prep.ai.mit.edu in directory
pub/gnu .

--

(defun foo () "Foo")
(setq test #'foo)
(funcall test) --> [CL and elisp] "Foo"
(defun foo () "Bar")
(funcall test) --> [elisp] "Bar"
                   [CL]    "Foo"

Well, it's not like a real common lisp. You're probably much better off with
CLISP.

] Note, however, that elisp (Emacs Lisp) is not lexically scoped, so you
] won't have closures. You get the CL extensions by doing (require 'cl);

Actually you do get closures, but you have to use lexical-let rather than let.
Those closures are a bad hack, but it works.

And generally the CL support in emacs is slow (elisp is not a speed deamon, but
it's worse when you add the CL layer on top of it).

|   I wrote a lisp interpreter, and I'm now finding that speed is becoming
|   important for me.  Could any one supply me with info on what order of
|   magnitude speed up I can expect (roughly) when I add in a byte-code
|   compiler?  (I do want to keep it portable...)

take a look at CLISP.  it compiles to a reasonably fast byte code.
ftp://ma2s2.mathematik.uni-karlsruhe.de/pub/lisp/clisp or see the FAQ.

|   XEmacs 19.13 also has CL-style backquote in the default environment.

so did Emacs 19.29 (released 1995-06-21).

|   Finally, XEmacs lets you do #'(lambda ...) so that the lambda gets
|   byte-compiled, but you still don't get closures, and #'foo looks up the
|   definition of foo at runtime, unlike in CL where you get the definition
|   at compile time.

I didn't know that XEmacs had #'.  I proposed adding it to Emacs because I
wanted to make it easier to make lambda forms compilable (seeing how so few
Emacs Lisp programmers know how to do this right).  RMS convinced me it was
not a good idea when I admitted that #'foo meant (symbol-function 'foo) in
CL and not in the proposed Emacs syntax change.  however, this is not an
entirely sound argument.  (function 'foo) in Emacs and Common Lisp is the
real difference, while #'foo would mean (function 'foo) in both syntaxes.

;;; Here is some Common Lisp code that outlines some evaluation strategies
;;; that can be useful in genetic programming.  The approach used here
;;; basically follows the approach in Koza's first book.

;;; For example, say we have some data:

(setq data '(1.0 2.0 3.0))

;;; and we'd like to evaluate the expression, EXP, which was generated by a
;;; genetic program:

(setq exp '(+ (* 3.0 (square x)) 2.0))

;;; Here we use Lisp s-expressions, but the follow ideas work for other
;;; data structures as well.

;;; How the expression is evaluated is a major performance issue in genetic
;;; programming.  See for example, ftp: openmap.bbn.com: pub/kanderson/
;;; faster94/faster94/postscript/profile.ps

;;; Here are 4 approaches to EVAL.  The fourth one, gp-eval-3, uses the
;;; closure compiler idea of Marc Feeley, which is the main point of this
;;; message.  This compiler is very fast and can do some very useful
;;; optimizations.  I have not used this in a genetic programming
;;; application, i thought the idea was worth sharing.

;;; While the examples are in Lisp, the ideas can be ported to other
;;; languages, perhaps with a bit more work.

(defun square (x) (* x x))

(defun gp-eval-0 (data exp)
  ;; Use Common Lisp's EVAL.
  ;; Problem: EVAL is too general.
  (mapcar
   #'(lambda (x)
       (declare (special x))
       (eval exp))
   data))

(defun gp-eval-1 (data exp)
  ;; Use COMPILE and FUNCALL instead of EVAL.
  ;; Problem: Combined time of COMPILE + N*FUNCALL can be larger than N*EVAL.
  (let ((f (compile 'nil `(lambda (x) ,exp))))
    (mapcar f data)))

(defun gp-eval-error (exp) (error "Can't handle ~a" exp))

(defun gp-eval-2 (data exp)
  ;; Use specialized version of EVAL
  ;; Problem: still must recursively EVAL EXP.
  ;; Could do a data parallel version.
  ;; Could unroll the recursion.
  ;; Could use a variable stack rather than recursion.
  (labels
      ((eval (x exp)
         (cond ((eq exp 'x) x)
               ((consp exp)
                (case (car exp)
                  (+ (+ (eval x (cadr exp)) (eval x (caddr exp))))
                  (* (* (eval x (cadr exp)) (eval x (caddr exp))))
                  (square (square (eval x (cadr exp))))
                  (t (gp-eval-error exp))))
               (t exp))))                       ; Constant.
    (mapcar #'(lambda (x) (eval x exp)) data)))

In CLISP, interpreting bytecodes usually results in a speedup of
between 4 and 20.