Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1685 > unrolled thread

Self compiling compiler

Back to article view | Back to comp.compilers

Contents

  Self compiling compiler ERSHC <ershc123@nyc.rr.com> - 2016-03-31 03:54 +0000
    Re: Self compiling compiler Kaz Kylheku <545-066-4921@kylheku.com> - 2016-03-31 15:01 +0000
    Re: Self compiling compiler Thomas Goorden <thomas.goorden@gmail.com> - 2016-03-31 17:50 +0200
    Re: Self compiling compiler "Nils M Holm" <nmh@t3x.org> - 2016-03-31 19:41 +0200
      Re: Self compiling compiler Kaz Kylheku <545-066-4921@kylheku.com> - 2016-04-03 10:34 -0400
        Re: Self compiling compiler Nils M Holm <nmh@t3x.org> - 2016-04-04 12:54 +0000
    Re: Self compiling compiler Thomas David Rivers <rivers@dignus.com> - 2016-03-31 14:16 -0400
    Re: Self compiling compiler alexfrunews@gmail.com - 2016-03-31 12:27 -0700
    Re: Self compiling compiler Jens Kallup <jkallup@web.de> - 2016-03-31 21:29 +0200
    Re: Self compiling compiler ERSHC <ershc123@nyc.rr.com> - 2016-04-02 20:58 +0000
    Re: Self compiling compiler federation2005@netzero.com - 2016-05-25 16:41 -0700
      Re: Self compiling compiler federation2005@netzero.com - 2016-05-28 14:49 -0700
        Re: Self compiling compiler rockbrentwood@gmail.com - 2016-08-22 15:56 -0700

#1685 — Self compiling compiler

I'd like to teach an undergraduate class based on the Thompson hack
(see Ken Thompson's Turing Award lecture). I don't want to write a
"whole" compiler, so need a compiler that can compile itself,
preferably one that runs under Linux and is reasonably small. Can
anyone point me to something more appropriate than gcc (which is far
from small)?

Thanks.

[toc] | [next] | [standalone]

#1686

On 2016-03-31, ERSHC <ershc123@nyc.rr.com> wrote:
> I'd like to teach an undergraduate class based on the Thompson hack
> (see Ken Thompson's Turing Award lecture). I don't want to write a
> "whole" compiler, so need a compiler that can compile itself,
> preferably one that runs under Linux and is reasonably small. Can
> anyone point me to something more appropriate than gcc (which is far
> from small)?

If you do the hack in a Big Important Compiler like gcc, the lesson will
have greater psychological impact, and you will have bigger hacker creds
in front of the students.

[Perhaps we should figure out how to walk before we run marathons. -John]

[toc] | [prev] | [next] | [standalone]

#1687

Self-compiling compilers are pretty common:
https://en.wikipedia.org/wiki/Bootstrapping_(compilers)

If it's C you're after, TCC is intentionally small: http://bellard.org/tcc/

Good luck!

On Thu, Mar 31, 2016 at 5:54 AM, ERSHC <ershc123@nyc.rr.com> wrote:

> Can anyone point me to something more appropriate than gcc (which is far
> from small)?

[toc] | [prev] | [next] | [standalone]

#1688

ERSHC <ershc123@nyc.rr.com> wrote:
> I'd like to teach an undergraduate class based on the Thompson hack
> (see Ken Thompson's Turing Award lecture). I don't want to write a
> "whole" compiler, so need a compiler that can compile itself,
> preferably one that runs under Linux and is reasonably small. Can
> anyone point me to something more appropriate than gcc (which is far
> from small)?

For something really small, check out Lindberg's Foogol. Here's a version
I converted to C89: http://www.t3x.org/files/foogol5.shar.Z

For something more complete, but still much simpler than GCC, have a look
at SubC: http://www.t3x.org/subc/index.html  There's also a book describing
its internals: http://www.t3x.org/reload/index.html  (Yes, I'm the author!)

There are various other small compilers, from very simple ones to
multi-platform optimizing compilers on my home page. Feel free to
look around!

--
Nils M Holm  < n m h @ t 3 x . o r g >  www.t3x.org

[toc] | [prev] | [next] | [standalone]

#1692

On 2016-03-31, Nils M Holm <nmh@t3x.org> wrote:
> ERSHC <ershc123@nyc.rr.com> wrote:
>> I'd like to teach an undergraduate class based on the Thompson hack
>> (see Ken Thompson's Turing Award lecture). I don't want to write a
>> "whole" compiler, so need a compiler that can compile itself,
>> preferably one that runs under Linux and is reasonably small. Can
>> anyone point me to something more appropriate than gcc (which is far
>> from small)?
>
> For something really small, check out Lindberg's Foogol. Here's a version
> I converted to C89: http://www.t3x.org/files/foogol5.shar.Z
>
> For something more complete, but still much simpler than GCC, have a look
> at SubC: http://www.t3x.org/subc/index.html  There's also a book describing
> its internals: http://www.t3x.org/reload/index.html  (Yes, I'm the author!)
>
> There are various other small compilers, from very simple ones to
> multi-platform optimizing compilers on my home page. Feel free to
> look around!

What matters here is not the compiler size but:

- The compiler has to be self-bootstrapping.
  The Thompson trick can't be perpetuated on something which
  strictly requires another compiler in order to build, and is then
  not re-compiled with itself.  The end goal of the trick is not
  to have any traces of that trick in any piece of source code;
  the result is a rogue compiler binary which replicates the rogue
  code when it is used to compile itself, and which alters
  some additional program, like a security-sensitive utility
  (su, login, ..)

- how easy is it, within the compiler's framework, to do this:
 - insert a piece of code which recognizes a static source
   code structure (perhaps as an abstract-syntax-tree-level pattern
   match) so that it can say "hey, I'm compiling myself: that parse is a
   piece of *me*!" or "hey, I'm compiling the login program!".
 - obtain the above AST-recognizing code not as C source, but as as a
   piece of AST material which the compiler itself can insert into a
   parse.
 - obtain, as an AST, some rogue code which the malicious compiler
   inserts into the parse of the target program such as login,
   as well as the rogue code which perpetuates all of this.

If the compiler is small, but its data structures and internal API's are
a dog's breakfast, it will be tedious to do.

(Mind you GCC is big *and* a dog's breakfast.).

[toc] | [prev] | [next] | [standalone]

#1697

Kaz Kylheku <545-066-4921@kylheku.com> wrote:
> What matters here is not the compiler size but:
>
> - The compiler has to be self-bootstrapping.
>   [...]
> - how easy is it, within the compiler's framework, to do this:
>  - insert a piece of code which recognizes a static source
>    code structure (perhaps as an abstract-syntax-tree-level pattern
>    match) so that it can say "hey, I'm compiling myself: [...]
>  - obtain the above AST-recognizing code not as C source, but as as a
>    piece of AST material which the compiler itself can insert into a
>    parse.
>  - obtain, as an AST, some rogue code which the malicious compiler
>    inserts into the parse of the target program such as login,
>    as well as the rogue code which perpetuates all of this.

Right, I missed that point when suggesting Foogol! Most other compilers
on my page do fit that bill, and their design is quite clean and modular.
The T3X compiler even uses glue code to communicate between phases which,
I guess, would make it a good candidate for Thompson's stunt. SubC uses
an AST.

--
Nils M Holm  < n m h @ t 3 x . o r g >  www.t3x.org

[toc] | [prev] | [next] | [standalone]

#1689

ERSHC wrote:

>I'd like to teach an undergraduate class based on the Thompson hack
>(see Ken Thompson's Turing Award lecture). I don't want to write a
>"whole" compiler, so need a compiler that can compile itself,
>preferably one that runs under Linux and is reasonably small. Can
>anyone point me to something more appropriate than gcc (which is far
>from small)?

Nicklaus Wirth's "Compiler Construction" text (his 3rd in this genre)
describes the small language Oberon-0 and walks thru writing a compiler
for this.

The compiler targets a RISC architecture for which he provides an emulator.

And - Dr. Wirth made the book available for free - you can get it from:

   http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf

and - you can read an HTML version (as well as get a copy of the sources)
from:

    https://www.inf.ethz.ch/personal/wirth/CompilerConstruction/index.html

as with all of Dr. Wirth's code - it is very small and very elegant while
simulaneously touching on all the major topics.  The text and the code
are very approachable to an undergraduate student.

   - Dave Rivers -

--
rivers@dignus.com  Work: (919) 676-0847

[toc] | [prev] | [next] | [standalone]

#1690

On Thursday, March 31, 2016 at 7:47:59 AM UTC-7, ERSHC wrote:
> I'd like to teach an undergraduate class based on the Thompson hack
> (see Ken Thompson's Turing Award lecture). I don't want to write a
> "whole" compiler, so need a compiler that can compile itself,
> preferably one that runs under Linux and is reasonably small.

Per a Reddit commenter, this very task has been done with my compiler:
https://github.com/alexfru/SmallerC
Alex

[toc] | [prev] | [next] | [standalone]

#1691

have a look:

http://asm.sourceforge.net/articles/smc.html

Jens

[toc] | [prev] | [next] | [standalone]

#1694

On Thu, 31 Mar 2016 03:54:00 -0000 (UTC), ERSHC <ershc123@nyc.rr.com> wrote:
> I'd like to teach an undergraduate class based on the Thompson hack
> (see Ken Thompson's Turing Award lecture). I don't want to write a
> "whole" compiler, so need a compiler that can compile itself,
> preferably one that runs under Linux and is reasonably small. Can
> anyone point me to something more appropriate than gcc (which is far
> from small)?
>
> Thanks.

Wow! Thanks to all for the suggestions. I seem to have some work cut
out for me chosing among the plethora of resources.

[toc] | [prev] | [next] | [standalone]

#1704

On Thursday, March 31, 2016 at 9:47:59 AM UTC-5, ERSHC wrote:
> I'd like to teach an undergraduate class based on the Thompson hack
> (see Ken Thompson's Turing Award lecture). I don't want to write a
> "whole" compiler, so need a compiler that can compile itself,
> preferably one that runs under Linux and is reasonably small. Can
> anyone point me to something more appropriate than gcc (which is far
> from small)?

cfront In a Picard voice: "make it work and compile right Riker."

If you want to REALLY take this to extreme: use the February 1985 printout
PDFs http://www.softwarepreservation.org/projects/c_plus_plus

The other versions are there too; but the dialect is old (the for loop
variables have different scoping, the new and delete operators are not
recognized and the libraries are not compatible if you try to use gcc
with this). There are scratch files in old versions there or elsewhere
in C and an empty scratch directory in version 3 and maybe 2 in the
archive.

[toc] | [prev] | [next] | [standalone]

#1706

On Wednesday, May 25, 2016 at 7:07:16 PM UTC-5, federat...@netzero.com wrote:
> If you want to REALLY take this to extreme: use the February 1985 printout
> PDFs http://www.softwarepreservation.org/projects/c_plus_plus
> The other versions are there too;

I transcribed much of the version 1 PDF. It has to be cross-checked
against the version 2 tarball since the laser printer they used at
AT&T didn't wrap around and a lot of places the printout got clipped.

[toc] | [prev] | [next] | [standalone]

#1726

On Wednesday, May 25, 2016 at 7:07:16 PM UTC-5, federat...@netzero.com wrote:
> ...use the February 1985 printout PDFs
http://www.softwarepreservation.org/projects/c_plus_plus

On Sunday, May 29, 2016 at 8:02:22 PM UTC-5, federat...@netzero.com wrote:
> I transcribed much of the version 1 PDF. It has to be cross-checked...

Done. Paul McJones posted the transcription of Version E from 1985 ...

http://www.softwarepreservation.org/projects/c_plus_plus/index.html#release_e

... 450 pages of printout verified against the 1986 so as to minimize diffs.
That resolves most of the 365 places printout got clipped and restores most of
the spaces and tabs.

Not all the files required for compilation were in the printout; stuff would
have to be scavenged from the 1986 version and pulled back -- if necessary --
to the earlier dialect. Neither version is in a C++ dialect recognized today.
It compiles itself and only the 1986 version has C files.

If interested in doing work on self-compiling compilers; picoc can be found on
the net -- a C interpreter. It is only about 4000 lines when in minimal
configuration. However it is (self-described) legacy code and serious recoding
and redesign of the data structures will be needed; particularly to remove the
"God" objects that the entire parser; stack frame and lexer states were each
wrapped up in. The parser is recursive descent with backtracking. But the
grammar processed by it is not large enough to allow the interpreter to run
itself. A large part of the complication is that it uses no byte-code
compiling (but yet you gotta do something with the function bodies and loop
bodies -- you'll have to look and see how it's handled.)

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web