A new way to process lists

Introduction

The aim here is to create a simple interpreter, able to process lists in a different way from the one lisp does. To do this, we will need the function eval2, and triggers. Triggers are so general that they can handle functions, macros, but also variables, binary or unary operators, and much more. There is a notion of priority, and we do not need more parentheses than in any language different from lisp. The priority will not be defined once and for all. When you define what the + operator does, you will also define its priority over other operators.

In twinlisp, some operators are necessarily binary, some are unary... Here, it is not so. A symbol could correspond to anything, depending on what you do with it. The code will be written in common-lisp. It is not intended to be used, but to explain how triggers can process lists. Here, we will simply interpret code. However, I have also made a program using triggers, but to compile code. So, the aim is to write an eval2 function, which will evaluate lisp lists. A few triggers, which will be called by eval2 will also be entered.

The principles of eval2 and of the triggers

A lisp interpreter needs to know what the arguments of a function or a macro are before to call it. With triggers, it is really different. In fact, the idea is to pass the whole list to process to the trigger, and it the trigger which will decide what to do with it. The trigger also gets what was previously evaluated. It returns a result, and the remaining list to evaluate. A trigger has a priority: The smaller it is, the more prioritary it is. the trigger structure can simply be entered in common-lisp by:

(defstruct trigger func prio)

the function func takes a result (the result of the previous evaluation) a list (which it has to evaluate). prio is the priority, and it is a real number. The name trigger comes from the fact that triggers are used to trigger the call of a function. The eval2 function takes a list and a maximal priority. It returns the result and the remaining list to evaluate. It will call any trigger it encounters, and also call itself when it encounters a sublist. It will stop when it encounters a trigger whose priority is bigger than the maximal priority.

(defun eval2(f prio)
  (let ((result nil))
    (loop
      (if (null f) ; if is has arrived to the end of the form, it returns
        (return-from eval2 (values result nil))
        (let ((a (first f)))
          (if (symbolp a)
            (if (boundp a)
              (let ((trig (symbol-value a)))
                (if (< (trigger-prio trig) prio) ; tests the priority of the trigger
                  (multiple-value-setq (result f) (funcall (trigger-func trig) result (rest f) trig))
                  (return-from eval2 (values result f))))
              (error (format nil "unknown ~a" a)))
            (if (not (null result))
              (error "two elements which are not symbols following")
              (progn
                (if (listp a) ; to evaluate sublists
                  (setf result (eval2 a most-positive-single-float))
                  (setf result a))
                (pop f)))))))))

This function alone is the core.

Binary operators

Let's program binary operators: + * called in infix notation. When called, a trigger corresponding to a binary operator will store the previous result sent by eval2. It will use eval2 to evaluate the remaining form, and call the function corresponding to the operator with the previous result and the new result.


(defun make-binary-operator (lisp-func prio)
  (make-trigger
    :prio prio 
    :func 
    (lambda (result f)
      (if (null f) 
        (error "syntax error: nothing after a binary operator")
        (multiple-value-bind (result-r f-r)
          (eval2 f prio)
          (values (funcall lisp-func result result-r) f-r))))))

The add-operator function will be used to enter a new trigger for an operator. Now we can enter the + and * operators:

(setf + (make-binary-operator #'+ 4))
(setf * (make-binary-operator #'* 3))

We simply need to put a bigger priority to + than to * since * is prioritary over + (the smaller the priority, the more prioritary it is)
Defining + will not interfere with the common-lisp +, since we define a variable and + is a function, and variables and functions have different namespaces. Now, we can run:

(eval2 '(2 * 4 + 2 * ( 5 + 3 )) most-positive-single-float)

which will return 24

constants

Handling binary operators is just a tiny part of what triggers can do. They can also handle constants. A trigger corresponding to a constant will simply return the value of the variable (stored in the data of the trigger) and the remaining form.

(defun set-constant (value)
  (make-trigger
    :prio 0 
    :func 
    (lambda (result f)
      (if (not (null result))
        (error "syntax error")
        (values value f)))))

We can now run: (setf a (set-constant 3)) This will print 11 We will now enter the trigger set-value to enter variables.

(setf set-constant 
  (make-trigger
    :func 
    (lambda (gauche f)
      (let ((symb (first f))) 
        (multiple-value-bind (val rest-f) 
          (eval2 (rest f) 100)
          (set symb (set-constant val))
          (values nil rest-f))))
    :prio 0))

We can now use it with: (eval2 '(set-value a 4 + 2 * 3) most-positive-single-float)

other triggers

We will enter the print2 trigger to print something To use it, we will simply run for example (eval2 '(print2 3 + 4))

(defun make-command (func)
  (make-trigger
    :prio 0
    :func
    (lambda (result f)
      (multiple-value-bind (val r-f) (eval2 f 100)
        (values (funcall func val) r-f)))))

(setf print2 (make-command #'print))

The & trigger will be used as an equivalent of the ; in C to separate instructions

(setf &
  (make-trigger
    :func
    (lambda (gauche f)
      (multiple-value-bind (val r-f)
        (eval2 f most-positive-single-float)
        (values val r-f)))
    :prio 200))

When set-value or print call eval2, eval2 must not evaluate the & trigger. This is why we put the priority 100 to set-value and print2 and 200 to & Now we can run:

(eval2 '(set-value a 5 + 6 & print2 a & print2 (a + 4) * 2 ) most-positive-single-float)

conclusion

We could continue like this, implementing functions called like in C, macros, quote... However, it would not be very useful, since interpreted code is really much slower than compiled one. So, I have made a program which is also using triggers, but it produces lisp-code which will then be compiled by a lisp implementation. I did not present it directly beccause I wanted something simple to explain what triggers can do.