Kazimir Majorinc, Crawler Tractor

Crawler Tractor

Kazimir Majorinc
November 6th, 2013.

Example of the self-processing Lisp program is presented. The function f, written in Newlisp dialect of Lisp, continously increments the value of the variable counter and prints its value. However, implementation of f doesn't contain a loop or recursion. Instead, the function changes the code of its definition during evaluation.

(set 'f
     (lambda()
       (begin (print "Hi for the "
                     (inc counter)
                     ". time. ")
              (push (last f) f -1)
              (if (> (length f) 3)
                  (pop f 1)))))

The result of evaluation of (f) is:

Hi for the 1. time.
Hi for the 2. time.
Hi for the 3. time.
Hi for the 4. time.
...

The evaluation reminds on the work of the crawler tractor, popular construction vehicle. Initially, interpreter encountered "stack overflow" after counter was incremented few hundreds of thousands times. Lutz Mueller, the author of Newlisp promptly resolved the issue. The speed penalty was, according to Mueller, very low.

As a proof of the concept, Joel Ericson defined two factorial functions that evaluate on similar way. In one of these even variables are not used.  

(define (f)
  (begin
    (when (> (length f) 2)
             (pop f -1))
    (push '(if (> 0 1)
               (begin ; Increase return value

                      (setf ((last f) -1)
                            (* $it ((last f) 1 1)))
                      
                      ; Change exit condition

                      (dec ((last f) 1 1)) 

                      ; Shorten f if too long

                      (if (> (length f) 4)         
                          (pop f 2))

                      (push (last f) f -1))
               1)
          f
          -1)
    (setq ((last f) 1 1) (args 0))))

The result of evaluation of (f 4) is 24.