11 Feb 2003 01:18:04 -0500

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) |

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.