Re: What is the smallest self-hosting language?

torbenm@diku.dk (Torben Ægidius Mogensen)
11 Feb 2003 01:18:04 -0500

          From comp.compilers

Related articles
[2 earlier articles]
What is the smallest self-hosting language? cdc@maxnet.co.nz (Carl Cerecke) (2003-01-25)
Re: What is the smallest self-hosting language? qsmgmt@earthlink.net (Alan Lehotsky) (2003-01-26)
Re: What is the smallest self-hosting language? ed_davis2@yahoo.com (2003-01-29)
Re: What is the smallest self-hosting language? s_dubrovich@yahoo.com (2003-01-30)
Re: What is the smallest self-hosting language? idbaxter@semdesigns.com (Ira Baxter) (2003-02-05)
Re: What is the smallest self-hosting language? alexc@world.std.com (2003-02-06)
Re: What is the smallest self-hosting language? torbenm@diku.dk (2003-02-11)
Re: What is the smallest self-hosting language? peter.r.wilson@boeing.com (Peter Wilson) (2003-02-11)
Re: What is the smallest self-hosting language? nworth@earthlink.net (Norman Worth) (2003-02-21)
| List of all articles for this month |

From: torbenm@diku.dk (Torben Ægidius Mogensen)
Newsgroups: comp.compilers
Date: 11 Feb 2003 01:18:04 -0500
Organization: Department of Computer Science, University of Copenhagen
References: 03-01-013 03-01-106 03-01-133 03-01-175 03-02-010
Keywords: theory
Posted-Date: 11 Feb 2003 01:18:04 EST

"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


Post a followup to this message

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