A self-evaluating evaluator

December is always a busy month, so the number of blog posts have been low for a while. To make up for it, I have been digging in the archives and found a self-evaluating evaluator. Erann Gat back in 2002 asked the following question in comp.lang.scheme:

The topic of self-generating programs (a program whose output is itself) comes up periodically here, but I've never seen the topic of a self-evaluating program discussed. Of course, meta-circular interpreters are ubiquitous, but the usual metacircular interpreter you find in textbooks typically evaluates a slightly different dialect than it is actually written in.

My question is: what is the shortest meta-circular
interpreter that is actually capable of evaluating itself?

It was quite fun to write a short meta-circular interpreter. The shortness-constraint creates a tension between powerful constructs and easily-implementable constructs, when choosing language features to include in the language. My solution below has the following features:

• conditional construct
• functions (of one argument)
• application
• quotation
  

This set of features is pretty minimal. The requirement that the evaluator must be self-evaluating means, it must be possible to pass the code of the evaluator to the evaluator, so quotation is just the right tool. Note that variable assignment (set!) is missing.

Since only functions of one argument is supported, it is necessary to curry the normal Scheme functions in the initial environment given to the evaluator. This can be seen in the following version of factorial:

; Support code for fak-example
(define (plus a) (lambda (b) (+ a b)))
(define (mult a) (lambda (b) (* a b)))
(define (one? x) (= x 1))
(define (sub1 n) (- n 1))

(define fact '(lambda (f)
               (lambda (n)
                 (cond
                   [(one? n)  1]
                   [#t        ((mult n) ((f f) (sub1 n)))]))))

(define fact-code (list (list fact fact) 5))

The standard definition of factorial is recursive. The chosen languages supports neither recursive bindings nor assignment, so instead we use the same trick, the Y-combinator uses. To calculate factorial of 5, one must write: ((fact fact) 5).

Since the evaluator must be self-evaluating, the definition of the evaluator uses the same trick as the factorial example. To call the evaluator on the factorial program, one writes:

(((jas-eval jas-eval) expression) initial-env)

And if we want to let the evaluator evaluate

(jas-eval (fak 5) initial-env) 

we write

 (define expression (list (list (list code-jas-eval code-jas-eval) (list 'quote fac-code)) initial-env))
(((jas-eval jas-eval) expression) initial-env)

After posting version 1 of the evaluator, Joe Marshall asked a very interesting question:

For the sake of curiosity, how much slower is the extra interpretation layer?

Can you go another level deeper?

The timings on my current computer is as follows:

; jas-eval evaluating "(fact 5)"
cpu time: 0 real time: 0 gc time: 0
120
; jas-eval evaluating "(jas-eval (fact 5))"
cpu time: 15 real time: 16 gc time: 0
120
; jas-eval evaluating "(jas-eval (jas-eval (fact 5)))"
cpu time: 922 real time: 954 gc time: 0
120
; jas-eval evaluating "(jas-eval (jas-eval (jas-eval (fact 5))))"
cpu time: 63891 real time: 66109 gc time: 12122
120

Exponential regression reveals the slow down to be 65 per level (R squared is 0.9999).

; Self evaluating evaluator, version 2
; Jens Axel Soegaard, oct 2002

(define first car)
(define second cadr)
(define third caddr)
(define rest cdr)

; Support code for fak-example
(define (plus a) (lambda (b) (+ a b)))
(define (mult a) (lambda (b) (* a b)))
(define (one? x) (= x 1))
(define (sub1 n) (- n 1))

(define fact '(lambda (f)
                (lambda (n)
                  (cond
                    [(one? n)  1]
                    [#t        ((mult n) ((f f) (sub1 n)))]))))

(define fact-code (list (list fact fact) 5))

; Conventions:  n name, v value, r environment, e expression
(define code-jas-eval
  '(lambda (ev)
     (lambda (e)
       (lambda (r)
         (cond
           [(symbol? e)      (r e)]
           [(not (pair? e))  e]
           [(pair? e)        (cond
                               [((ceq? (first e)) 'quote)  (first (rest e))]
                               [((ceq? (first e)) 'cond)
                                (cond
                                  [(((ev ev) (first (second e))) r)  (((ev ev) (second (second e))) r)]
                                  [#t                                (((ev ev) ((ccons 'cond) (rest (rest e)))) r)])]
                               [((ceq? (first e)) 'lambda)              (lambda (x)
                                                                       (((ev ev) (third e))
                                                                        (lambda (n)
                                                                          (cond
                                                                            [((ceq? (first (second e))) n)   x]
                                                                            [#t                           (r n)]))))]
                               [#t                                   ((((ev ev) (first e)) r)
                                                                      (((ev ev) (second e)) r))])])))))

; setup initial environment;
; currying the primitives used in the evaluator
(define (ceq? a)
  (lambda (b)
    (eq? a b)))

(define (ccons a)
  (lambda (b)
    (cons a b)))

(define initial-env eval)

; use Scheme-eval to get jas-eval
(define jas-eval (eval code-jas-eval))
(define initial-env eval)

; use jas-eval to evaluate (fact 5)
(define expression fact-code)
(time (((jas-eval jas-eval) expression) initial-env))

; use jas-eval to evaluate (jas-eval (fact 5) initial-env)
(define expression (list (list (list code-jas-eval code-jas-eval) (list 'quote fact-code)) initial-env))
;expression
(time (((jas-eval jas-eval) expression) initial-env))

; use jas-eval to evaluate (jas-eval (jas-eval (fact 5) initial-env))
(define expression (list (list (list code-jas-eval code-jas-eval) (list 'quote fact-code))  initial-env))
(define expression (list (list (list code-jas-eval code-jas-eval) (list 'quote expression)) initial-env))
;expression
(time (((jas-eval jas-eval) expression) initial-env))


; use jas-eval to evaluate (jas-eval (jas-eval (jas-eval (fact 5) initial-env)))
(define expression (list (list (list code-jas-eval code-jas-eval) (list 'quote fact-code))  initial-env))
(define expression (list (list (list code-jas-eval code-jas-eval) (list 'quote expression)) initial-env))
(define expression (list (list (list code-jas-eval code-jas-eval) (list 'quote expression)) initial-env))
;expression
(time (((jas-eval jas-eval) expression) initial-env))