Can a second implementation of a programming language be written in that language?

views:

388

answers:

+5 Q:

Can a second implementation of a programming language be written in that language?

This question is just something that I have been thinking about lately. Can a programming language be written in that language as a second implementation? e.g. Java. Is it possible to rewrite the java programming language using the java programming language?

Apologies if this is a silly question but I need to know!

+10 A:

Always. Any Turing-Complete language is -- well -- a Turing-Complete language. If you can write the compiler in one complete language, you can write it in any equivalent language.

S.Lott 2010-07-15 20:58:21

+3 A:

Yes. As long as the language is Turing Complete, you can implement the language in itself.

Vivin Paliath 2010-07-15 20:58:35

Turing-completeness is not strictly a requirement IIRC. But the existing Turing-incomplete languages (Regex, SQL and such) are still insufficient.

Seva Alekseyev 2010-07-15 21:02:15

You can read a regex using regex, but I think it's impossible to create a regex implementation using it. The turing completeness is theory, in order to write a java compiler you need to manipulate bits and write to disk (Java can do this).

tovare 2010-07-15 21:08:47

@tovare: Actually you cannot even [verify regex using regex](http://stackoverflow.com/questions/172303/is-there-a-regular-expression-to-detect-a-valid-regular-expression/172363#172363) (ie. the language we use to specify regular languages is not regular)!

BlueRaja - Danny Pflughoeft 2010-07-15 21:12:39

@Seva I didn't mean to imply that it was a strict requirement; just that if a language is Turing Complete, then what the OP suggests is possible. :)

Vivin Paliath 2010-07-15 21:12:42

@BlueRaja - Danny Pflughoeft: you're absolutely righ I didn't think about the fact that the regex laguage isn't regular with constructs such as the matching parenthesis.

tovare 2010-07-15 21:18:08

+8 A:

Yes, it is possible. Check out BootStrapping.

Moron 2010-07-15 21:00:02

+1 I was racking my brain (and going on Google) to search for that term. I vaguely remembered something about C compilers being successively implemented in itself.

Vivin Paliath 2010-07-15 21:13:17

+1 A:

It not only can, it is. ecj (Eclipse's compiler) is one example, and I think the SDK itself comes with a pure Java compiler, though I could be wrong about that.

Mark Peters 2010-07-15 21:00:36

+7 A:

Yes for any Turing Complete language. Lisp comes to mind as one of the easiest languages to write an interpreter/compiler for itself.

Mandelbrot 2010-07-15 21:00:49

+2 A:

There are many practical examples of this, one example is the Oberon Language, which is of interest in this discussion because the compiler code is very readable it's in the book Project Oberon available for free:

http://www.oberon.ethz.ch/bibliography/publications

http://en.wikipedia.org/wiki/Bootstrapping_(compilers)

tovare 2010-07-15 21:04:33

Interesting links.thanks.

2010-07-15 21:26:45

+6 A:

It can. A recent example is that python has pypy. A little more information is on the Wikipedia page and some good links.

Zakmobl 2010-07-15 21:04:34

AFAIK Pypy does not interpret, it compile the the VM.

mathk 2010-07-15 21:52:19

Pypy is Python interpreter written in a reduced subset of Python (RPython). However the project can construct a C version and even a tracing JITC by doing transformations on the RPython source.

Axel Gneiting 2010-07-15 21:56:13

Yes but can pypy interpret the VM being design?

mathk 2010-07-16 05:20:30

Of course it can. ./pypy-c pypy.py works.

Axel Gneiting 2010-07-20 12:05:28

Check out 3-LISP

mathk 2010-07-15 21:50:03

Sure. I've even seen someone write a COBOL compiler written in COBOL! (OK, not a full compiler ... but at least a parser.)

Stephen C 2010-07-15 22:32:18

+2 A:

Sure.

Many many years ago one of my first home computers, a Vic 20, came with a built-in BASIC interpreter but that was it. So I wrote the first version of an assembler for it in BASIC. Then I used my first primitive assembler to write a better assembler.

Jay 2010-07-15 23:37:20

+2 A:

The GCC compilers are written in C.

It has been a long time since anyone built any C compilers from assembly.

Zan Lynx 2010-07-15 23:41:17

+1 A:

write a java compiler in java - no problem at all. actually I think Sun's javac is written in java.

however, 'java' usually means more things than just the javac, so your question isn't very clear.

irreputable 2010-07-16 04:13:29

+2 A:

Not just possible, but for native-code compilers, this is the most common implementation technique. A good how-to guide is Andrew Appel's paper Axiomatic Bootstrapping: A Guide for Compiler Hackers.

Norman Ramsey 2010-07-16 13:55:10

ansaurus

tags:

views:

answers:

Can a second implementation of a programming language be written in that language?

related questions