8

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!

GF

Carl Smotricz
  • 66,391
  • 18
  • 125
  • 167
Grunge Freak
  • 1,009
  • 2
  • 12
  • 19

13 Answers13

12

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
  • 384,516
  • 81
  • 508
  • 779
  • Even some Turing-Complete languages might have limitations, depending on what we mean by 'implement'. Imagine a Turing-complete language that can only input and output plain ASCII text. Such a language would be unable to output an executable binary and therefore wouldn't be able to build its own "freestanding" interpreter. – Aaron McDaid May 14 '16 at 08:30
  • [Executable ASCII text files](https://astr0baby.wordpress.com/2012/08/31/executable-ascii-files-pt-2/) – barbecue Oct 16 '16 at 19:42
11

Yes, it is possible. Check out BootStrapping.

  • +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 Jul 15 '10 at 21:13
7

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

Mandelbrot
  • 502
  • 1
  • 4
  • 13
6

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

Zakmobl
  • 67
  • 2
  • AFAIK Pypy does not interpret, it compile the the VM. – mathk Jul 15 '10 at 21:52
  • 1
    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 Jul 15 '10 at 21:56
  • Yes but can pypy interpret the VM being design? – mathk Jul 16 '10 at 05:20
4

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
  • 26,876
  • 10
  • 61
  • 112
  • @monojohnny Punch cards are coming back. This USB drive stuff is just a fad. :-) – Jay Dec 29 '14 at 15:02
3

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

Vivin Paliath
  • 94,126
  • 40
  • 223
  • 295
  • 1
    Turing-completeness is not strictly a requirement IIRC. But the existing Turing-incomplete languages (Regex, SQL and such) are still insufficient. – Seva Alekseyev Jul 15 '10 at 21:02
  • 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 Jul 15 '10 at 21:08
  • 2
    @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 Jul 15 '10 at 21:12
  • @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 Jul 15 '10 at 21:12
  • @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 Jul 15 '10 at 21:18
2

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
  • 4,027
  • 5
  • 29
  • 30
2

The GCC compilers are written in C.

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

Zan Lynx
  • 53,022
  • 10
  • 79
  • 131
2

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
  • 198,648
  • 61
  • 360
  • 533
1

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
  • 80,126
  • 17
  • 159
  • 190
1

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
  • 44,725
  • 9
  • 65
  • 93
0

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
  • 698,415
  • 94
  • 811
  • 1,216
-1

Check out 3-LISP

mathk
  • 7,973
  • 6
  • 45
  • 74