netzstaub

Eine Funktionalität des Javascript Compilers (über den ich hier und hier schon gebloggt habe) war recht interessant. Und zwar geht es darum, die vollgeklammerten und in Prefix-Syntax geschriebenen arithmetischen Ausdrücke aus dem Lisp-Javascript-Dialekt zu lesbaren Javascript-Ausdrücken umzuformen. Also z.B.

(+ (* 3 4) 9 (- 10 5)) => (3 * 4) + 9 + (10 - 5) bzw. 3 * 4 + 9 + 10 - 5

Mit einem Trivialansatz, bei dem alles geklammert wird, um die korrekte Auswertung zu gewährleisten, sieht das Ergebnis richtig unlesbar aus:

((3) * (4)) + (9) + ((10) - (5))

Der bessere Ansatz ist eher, so wenig Klammern wie möglich einzusetzen, und dazu müssen wir die Operatorpräzedenzen berücksichtigen. Im Javascriptstandard steht jetzt keine klare Tabelle mit der Reihenfolge der Operatoren drin, sondern nur eine BNF-Syntax, aus der man sich das Ganze extrahieren muss. Zum Glück gibt es im Netz eine Tabelle die man verwenden kann. Anstatt die jetzt doof abzutippen werden wir uns dort nur die Reihenfolge der Operatoren abgucken, und diese in Lisp giessen:

(defparameter *op-precedences*
  '((aref)
    (* / %)
    (+ -)
    (<< >>)
    (>>>)
    (< > <= >=)
    (in)
    (eql == !=)
    (=== !==)
    (&)
    (^)
    (\|)
    (\&\& and)
    (\|\| or)
    (setf)))

Diese Liste hat die Operatoren in Reihenfolge abnehmender Präzedenz. Wie bei den Specialforms werden wir diese Liste verarbeiten und die einzelnen Operatoren in eine Hashtabelle speichern. Das wollen wir natürlich zur Ladezeit machen, also verwenden wir eine EVAL-WHEN Form:

(defvar *op-precedence-hash* (make-hash-table))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (let ((precedence 1))
    (dolist (ops *op-precedences*)
      (dolist (op ops)
        (setf (gethash op *op-precedence-hash*) precedence))
      (incf precedence))))

Jetzt sind in der Hashtabelle *OP-PRECEDENCE-HASH* die Präzedenzen der Operatoren gespeichert. Z.B.:

CL-USER> (gethash '< *op-precedence-hash*)
6

< hat also die Präzedenz 6. Anhand der Tabelle können wir auch bestimmen ob ein Ausdruck eine Expression ist (die Funktion OP-FORM-P ist uns gestern schon begegnet):

(defun op-form-p (form)
  (and (listp form)
       (not (null (gethash (first form) *op-precedence-hash*)))))

Letztendlich wollen wir die Präzedenz von einer Expression bestimmen. Da müssen wir die Spezialfälle von Funktionsaufrufen und atomaren Expressions (Strings, Variablen oder Nummern) berücksichtigen). Das macht die Funktion OP-FORM-PRECEDENCE, die im bekannten Stil wieder ein grosses COND einsetzt:

(defun op-form-precedence (form)
  (cond ((op-form-p form)
         (gethash (first form) *op-precedence-hash*))
        ((or (atom form)
             (js-funcall-p form))
         0)
        (t (error "~A is not an expression" form))))

Atomare Expressions (Funktionsaufrufe, Strings, Variablen oder Nummern) haben die niedrigste Präzendenz, und binden so am “Stärksten”, d.h. man braucht da nie Klammern herum zu packen. Anhand dieser Werkzeugsfunktionen können wir jetzt den Expression-Compiler angehen, der in Form einer Funktion namens JS-EXPRESSION implementiert ist:

(defun js-expression (form)
  (if (or (atom form)
          (js-funcall-p form))
      (js-compile-single form)
      (let ((args (cdr form))
            (name (js-op-name (car form)))
            (precedence (op-form-precedence form)))
        (string-join (mapcar #'(lambda (x) (let ((prec (op-form-precedence x)))
                                             (if (> prec precedence)
                                                 (klammer (js-expression x))
                                                 (js-expression x))))
                             args)
                     (format nil " ~A "  name)))))

Wenn die Expression “atomar” ist, brauchen wir nicht zu klammern, und rufen den “normalen” Compiler auf. Wenn aber FORM eine komplexere Expression ist, also eine Expression wo Operatoren zum Einsatz kommen, müssen wir die Präzedenz des Ausdrucks ermitteln. Das Ergebnis von (OP-FORM-PRECEDENCE FORM) wird an PRECEDENCE gebunden. Wenn jetzt ein Argument der Expression von höherer Präzedenz ist (also loser bindet), müssen Klammern eingesetzt werden. Sonst kann der Ausdruck so eingesetzt werden. Für die Argument einer Expression, die selber wieder Expressions sein müssen, wird JS-EXPRESSION rekursiv aufgerufen. Einen kleinen Trick gibt es hier noch, und zwar wird die Funktion JS-OP-NAME eingesetzt um “Lisp-typische”-Namen zu übersetzen, also z.B. EQL nach ==. Zum Schluss noch ein kleines Beispiel:

CL-USER> (js-expression '(+ (* 3 4) 9 (- 10 5)))
"3 * 4 + 9 + 10 - 5"
CL-USER> (js-expression '(+ (setf a (blorg 2)) (* 4 5 2)))
"(a = blorg(2)) + 4 * 5 * 2"