Re: What is the smallest self-hosting language?

"Ira Baxter" <idbaxter@semdesigns.com> writes:


> > > I found myself wondering what the smallest self-hosting language would
> > > look like.
>
> Um, I think the Turing machine theorists have beat this to death.
> There's a 3-state, 7 symbol Universal Turing machine. By definition,
> self hosting.
>
> So I think the discussion need to focus on what's the smallest
> *expressive* self-hosting language.


The pure untyped lambda calculus is arguably a small language and I
find it very expressive as a programming language -- I can write a
Turing-machine simulator in about 10 lines of lambda calculus, but I
wouldn't want to try writing a lambda calculus evaluator in a Turing
machine. And you can write a self-interpreter in the pure lambda
calculus very compactly.


The problem boils down to how you represent lambda terms in the lambda
calculus. The tempting idea of letting them be represented by
themselves and just use the identity function as a self-interpreter
doesn't really pan out: You, for example, can't compare represented
terms for alpha-equality, so saying that it is a representation is
stretching it a bit. But the representation function [·] described
below does the trick:


                          _
    [M] = \ab.M
        _
        x = x
      __ _ _
      MN = a M N
    ____ _
    \x.M = b \x.M


This allows a self-interpreter to be written as


\m.m (\x.x) (\x.x)


which is hard to beat in any language that doesn't have this built in
(like EVAL in LISP). For extra details, see the paper


Torben Æ. Mogensen,
Linear-Time Self-Interpretation of the Pure Lambda Calculus,
Higher-order and symbolic computation, vol. 13, no. 3, sep. 2000


or the shorter version in Springer LNCS 1755.


Torben

Return to the comp.compilers page.
Search the comp.compilers archives again.