Language w/ the smallest interpreter written in itself

Question

What is the smallest (code-golf) interpreter that is written in the language it interprets.

I think overall this would be a good indicator as to the balance of how robust a language is.

Extremely simple (turing tarpits) languages are difficult to write large programs like interpreters in.

More 'sugary' languages are simpler to write in, but require a more complicated interpreter.

I'm looking for a balance between the two.

I would also like to include compiled languages, but I'm not sure if it's fair to compare interpreters and compilers.

Thanks!

Answer 1

python:

exec "code"

Answer 2

In rebuttal to Aaron Digulla's answer:

If language X is a Turing-complete language for which interpreters exist, then it must be possible to write an interpreter for language X, in language X.

Proof:

If language X is Turing-complete, then it can therefore compute any computable function.

If interpreters exist for language X, then an interpreter for language X must be a computable function.

Ergo, language X must be able to run an interpreter for language X.

Answer 3

Formal answer:

The "empty" language where there is just one valid program, the empty program, which does nothing. The empty program is also a valid interpreter for this language, because when given the empty program, it does nothing, which is a valid interpretation of that program.

Another language, the language "Hello world", consists of just one valid program: "Hello world" which contains one instruction "printHelloWorld" which prints Hello World. It too, is a valid interpreter for "Hello world" programs. When given a "Hello world" program, it prints hello world, which is a valid interpretation.

Useful answer:

Scheme is probably one of the simplest languages that can implement an interpreter for itself, because its parsing is nearly trivial, and its semantics are simple yet powerful.

I don't think it is indeed a good measure of "robustness", just of the ratio between expressiveness (of interpreter writing) and complexity. Indeed, this is good evidence that Scheme's expressiveness in the realm of language interpretation is very high compared to its size/complexity.

Answer 4

I think you're looking for meta circular interpreters. Straight from the famous Portland wiki (I don't claim to understand this):

For example, here is a simple metacircular interpreter in arbitrary dialect Forth:

: myInterpreter
  begin 32 word find dup if execute else number then again ;

Answer 5

Alan Kay, in "The Early History of Smalltalk":

One day, in a typical PARC hallway bullsession, Ted Kaeh;er, Dan Ingalls, and I were standing around talking about programming languages. The subject pf power came up and the two of them wondered how large a language one would have to make to get great power. With as much panache as I could muster, I asserted that you could define the "most powerful language in the world" in "a page of code." They said, "Put up or shut up."

Needless to say, he picked the former.

Answer 6

Using Scheme:

(define (scheme)
  (write (eval (read)))
  (scheme))

Simple : ).

Answer 7

For an interpreter one key question is how many language features are still in the host-language.

Here is an interpreter that allows you during runtime to change for example the definition of "if" or "eval" (which also makes it pretty much uncompileable).

Note the construct flambda is the same as lambda except it does not evaluate its parameters

(apply
  (lambda (make-toplevel make-flambda flambda? flambda-apply)
    (set! make-toplevel
          (lambda (prompt-in prompt-out)
            (call/cc 
             (lambda (exit)
               (monitor (lambda (c b) (exit b))
                 ((lambda (it extend error global-env 
                           toplevel eval evlis eprogn reference )
                    (set! extend
                          (lambda (env names values)
                            (if (pair? names)
                                (if (pair? values)
                                    ((lambda (newenv)
                                       (begin 
                                         (set-variable-value! 
                                          (car names) 
                                          newenv
                                          (car values) )
                                         (extend newenv (cdr names) 
                                                 (cdr values) ) ) )
                                     (enrich env (car names)) )
                                    (error "Too few arguments" names) )
                                (if (symbol? names)
                                    ((lambda (newenv)
                                       (begin 
                                         (set-variable-value! 
                                          names newenv values )
                                         newenv ) )
                                     (enrich env names) )
                                    (if (null? names)
                                        (if (null? values)
                                            env
                                            (error 
                                             "Too much arguments" 
                                             values ) )
                                        env ) ) ) ) )
                    (set! error (lambda (msg hint)
                                  (exit (list msg hint)) ))
                    (set! toplevel
                          (lambda (genv) 
                            (set! global-env genv)
                            (display prompt-in)
                            ((lambda (result) 
                               (set! it result)
                               (display prompt-out)
                               (display result)
                               (newline) )
                             ((lambda (e)
                                (if (eof-object? e)
                                    (exit e)
                                    (eval e global-env) ) )
                                (read) ) )
                            (toplevel global-env) ) )
                    (set! eval
                          (lambda (e r)
                            (if (pair? e) 
                                ((lambda (f)
                                   (if (flambda? f)
                                       (flambda-apply f r (cdr e))
                                       (apply f (evlis (cdr e) r)) ) )
                                 (eval (car e) r) )
                                (if (symbol? e) 
                                    (reference e r)
                                    e ) ) ) )
                    (set! evlis
                          (lambda (e* r)
                            (if (pair? e*)
                                ((lambda (v)
                                   (cons v (evlis (cdr e*) r)) )
                                 (eval (car e*) r) )
                                '() ) ) )
                    (set! eprogn
                          (lambda (e+ r)
                            (if (pair? (cdr e+))
                                (begin (eval (car e+) r)
                                       (eprogn (cdr e+) r) )
                                (eval (car e+) r) ) ) )
                    (set! reference 
                          (lambda (name r)
                            (if (variable-defined? name r)
                                (variable-value name r)
                                (if (variable-defined? name global-env)
                                    (variable-value name global-env)
                                    (error "No such variable" 
                                           name ) ) ) ) )
                    ((lambda (quote if set! lambda flambda monitor)
                       (toplevel (the-environment)) )
                     (make-flambda 
                      (lambda (r quotation) quotation) )
                     (make-flambda
                      (lambda (r condition then else)
                        (eval (if (eval condition r) then else) r) ) )
                     (make-flambda
                      (lambda (r name form)
                        ((lambda (v) 
                           (if (variable-defined? name r)
                               (set-variable-value! name r v)
                               (if (variable-defined? name global-env)
                                   (set-variable-value! 
                                    name global-env v )
                                   (error "No such variable" 
                                          name ) ) ))
                         (eval form r) ) ) )
                     (make-flambda
                      (lambda (r variables . body)
                        (lambda values
                          (eprogn body 
                                  (extend r variables values) ) ) ) )
                     (make-flambda
                      (lambda (r variables . body)
                        (make-flambda
                         (lambda (rr . parameters)
                           (eprogn body 
                                   (extend r variables 
                                           (cons rr 
                                                 parameters 
                                                 ) ) ) ) ) ) )
                     (make-flambda
                      (lambda (r handler . body)
                        (monitor (eval handler r)
                                 (eprogn body r) ) ) ) ) )
                  'it 'extend 'error 'global-env 
                  'toplevel 'eval 'evlis 'eprogn 'reference ) ) ) ) ) ) 
    (make-toplevel "?? " "== ") )
  'make-toplevel 
  ((lambda (flambda-tag)
     (list (lambda (behavior) (cons flambda-tag behavior))
           (lambda (o) (if (pair? o) (= (car o) flambda-tag) #f))
           (lambda (f r parms) (apply (cdr f) r parms)) ) )
   98127634 ) ) 

For example the definition of if from above is:

(make-flambda
   (lambda (r condition then else)
           (eval (if (eval condition r) then else) r) ) )

But in order to really understand the interpreter I recommend reading the book, since there are some non-standard functions (like the-environment and other wierdness especially at the end ;).

All code from chapter "8.8 Reflective Interpreter" of the book "Lisp in Small Pieces" by Christian Queinnec.