12 ms·

C4 – C in 4 functions

517 points by petercooper 12y ago

astrodust 12y ago
That is pretty stripped down. Could probably be ported to JavaScript without breaking a sweat.
- Lerc 12y ago
  That was my first thought, a micro-C to asm.js compiler wouldn't be hard.
petercooper 12y ago
I just wanted to credit Reddit's /r/tinycode sub-Reddit for this link: http://www.reddit.com/r/tinycode http://www.reddit.com/r/tinycode - it's a pretty cool place to discover minimalistic implementations of things.
- whitten 12y ago
  Thank you for sharing that link to the tinycode Reddit. Did the original poster (for the C in four functions) participate in that sub-reddit ?
  - deleted 12y ago
    [deleted]
  - pmh 12y ago
    It would appear so. https://www.reddit.com/r/tinycode/comments/2la785/c4_a_c_compiler_in_four_functions/ https://www.reddit.com/r/tinycode/comments/2la785/c4_a_c_com... is the post from /r/tinycode and its OP[0] is the same as the github user[1] for c4. [0]https://www.reddit.com/user/rswier https://www.reddit.com/user/rswier [1]https://github.com/rswier https://github.com/rswier
- diltonm 12y ago
  Other than Minecraft I don't go to Reddit, this is a cool link though and one I'll be checking, thanks.
  - glibgil 12y ago
    Now you mostly go to reddit like anyone else. Is not going to reddit the new "I don't watch TV"?
    - anonbanker 12y ago
      nope. Facebook/Kik/Snapchat/Dropbox is still the new "I Don't Watch TV".
      - 72deluxe 12y ago
        Neat! Then I really Don't Watch TV!
- petercooper 12y ago
  Update: We seem to have made /r/tinycode a trending sub-Reddit of the day :-) http://www.reddit.com/r/tinycode/comments/2lcq17/rtinycode_has_been_chosen_as_a_trending_subreddit/ http://www.reddit.com/r/tinycode/comments/2lcq17/rtinycode_h...
marcofiset 12y ago
I honestly think this is ridiculous. Sure, this is an incredible feat, and congrats. But serioulsy, I would be ashamed to publish such unreadable code under my name. What about naming your variables with descriptive names? What about extracting complex conditions into well named function to understand what is going on (thus defeating the purpose of the "4 functions") ? This list could go on forever... Writing software is not a contest for who can write the most amount of code in the most cryptic way.
- tehwalrus 12y ago
  The variable names thing really annoyed me too - a habit of code golf, and people who were originally trained in an old FORTRAN edition that had a 6 or 7 char limit on names.
  - _wmd 12y ago
    Unless you're talking about a large piece of software composed entirely of single character functions and variable names, I pretty much disagree. Verbose variable names do not magically teach those reading a piece of code how it works, simultaneously they tend to make it impossible to write many kinds of expressions concisely, and consequently they regularly damage the readability of more complex pieces of code (e.g. arithmetic expressions involving 3 or more terms). The same goes for symbolic constants. Sometimes (but not exactly "often"), use of numeric literals can vastly improve the maintainability of some code, assuming the reader understands how to maintain it in the first instance. As for increasing reader comprehension, carefully thought out comments are a better mechanism by far. In this case, it is sufficient to know that the file is a compiler/interpreter for its entirety to make sense, assuming the reader has implemented (or at least understood the principles behind) a compiler/interpreter in their past. Expanding the function/variable names, splitting "complicated" expressions out into their own functions, etc., does not magically improve the uninitiated's chance of understanding what is going on
    - ajkjk 12y ago
      I mostly strongly disagree. I see no value in naming a variable 'tk', 'pp', or 'bt'. It can only help to make the code more readable with less context. I do not need to understand compilers in detail to know what this program is doing, except, for the names being useless. And if I do understand them but have not spent half an hour or probably much more to digest the exact system by which it operates, I would be completely unable to identify bugs or talk about modifying or extending it in any useful way. Well written comments do not make the code below them more intelligible as text even if they do give you good hints for how to load it into your brain. And "Expanding the function/variable names, splitting "complicated" expressions out into their own functions, etc." all ABSOLUTELY improve the uninitiated's chance of understanding what is going on. Speaking as one of the uninitiated (though I can mostly make out how this works). Man, I wish I knew what 'tk' was. That whole section at line 204 would be so clear if I could follow the intent. I agree with you on symbolic constants and arithmetic though.
TazeTSchnitzel 12y ago
Pretty damn impressive. Though I must wonder: how complete is it? What does it and does it not support? It's at least complete enough to be self-hosting, but beyond that? The code doesn't use that much of C.
- cbhl 12y ago
  Judging from the comments in c4.cpp, it probably only supports enough of a subset to compile itself. Granted, while building a parser that can parse (let alone compiling) the full C language is nontrivial, any undergrad should be able to build a parser and compiler for a sufficiently simple subset of it. (In my undergrad, we used this subset to build a "compiler" in second year: https://www.student.cs.uwaterloo.ca/~cs241/wlp4/WLP4.html https://www.student.cs.uwaterloo.ca/~cs241/wlp4/WLP4.html)
  - JoeAltmaier 12y ago
    You can build a C parser in an afternoon. It only has a few language constructs. Declarations are the hardest. Scanners are readily available for expressions and constants.
    - cbhl 12y ago
      I would be worried about handling the not-context-free parts of the language: http://trevorjim.com/c-and-cplusplus-are-not-context-free/ http://trevorjim.com/c-and-cplusplus-are-not-context-free/ How would you handle these?
      - JoeAltmaier 12y ago
        Scanner has to have access to the symbol table, emit 'ident' or 'type' as appropriate. So not a pure context-free parser.
        sedachv 12y ago
        Yes. This is the reason it is way easier to hand-build a parser for C than try to use any kind of parser generator.
methyl 12y ago
Unfortunately, I cannot compile it on my OSX 10.10... here's what I get: http://pastebin.com/cVvaYFEH http://pastebin.com/cVvaYFEH EDIT: just make next() function void and it works. EDIT2: still no fortune :( $ ./c4 hello.c [1] 33920 segmentation fault ./c4 hello.c
- cremno 12y ago
  I think it doesn't work on x86-64, since the code assumes sizeof(int) == sizeof(void*)
  - jparishy 12y ago
    Yep, you can compile it on 64 bit OS X with clang's -m32 option and it should work: ➜ c4 git:(master) ✗ clang -m32 c4.c ... ➜ c4 git:(master) ✗ ./a.out hello.c hello, world exit(0) cycle = 9
- kschults 12y ago
  For now, you need to add both -Wno-return-type and -m32 when compiling.
- ackalker 12y ago
  Please try kbrock's fork at https://github.com/kbrock/c4 https://github.com/kbrock/c4 Check out his 'longs' branch.
0x0 12y ago
Would you call this a compiler, an interpreter, a virtual machine, a scripting engine, or a combination of those?
- marktangotango 12y ago
  It compiles a c subset to byte code, then executes in a virtual machine. I think generally an intepreter can refer to either a byte code interpreter (ie virtual machine) or an AST walking interpreter. I didn't see a way to embed c4 into a host language, so maybe not a scripting language? IMO the real value of exhibits like this are boiling the problem (lexing, parsing, compiler, interpreting) down to their most basic parts. One could easily imagine this same language being implemented over 10's or 100's of class files in a more verbose language.
  - stcredzero 12y ago
    I think generally an intepreter can refer to either a byte code interpreter (ie virtual machine) or an AST walking interpreter. This brings to mind how fuzzy "interpreter" is as terminology. What is a virtual machine that JIT compiles the byte code or the AST? Is it a JIT implementation of an interpreter? What of implementations that only JIT the most frequently used functions? Wouldn't those be half interpreter and half virtual machine? When it comes down to it, they're all really virtual machines. The real distinction is how we've come to think of different implementations and the representations sub-culturally. For some reason, it makes us feel better when we call certain things interpreters, because of some meaningless (and sometimes factually challenged) competitive instincts concerning implementation speed. (Also, we arbitrarily feel that byte code is somehow more "machine-y" than an AST.) So do I have a problem with "interpreter"? Only when people correct others, as if they're making a correction about something fundamental and factual. In reality, the distinction is between machines that are intended to have the same runtime semantics and really the distinction is only around what optimizations are present in their implementations. Furthermore, if you look at those optimizations in detail, the distinction gets even hazier.
    - TazeTSchnitzel 12y ago
abecedarius 12y ago
On a first skim, this looks really nice; complaints that it's unreadable are unfounded. The background that makes it readable are Wirth's Compiler Construction http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf plus precedence climbing http://en.wikipedia.org/wiki/Operator-precedence_parser#Precedence_climbing_method http://en.wikipedia.org/wiki/Operator-precedence_parser#Prec...
- dabockster 12y ago
  complaints that it's unreadable are unfounded Not exactly. You have to remember that language and compiler design require a LOT of work and experience to understand, and that many programmers will only see this as, frankly, spaghetti. I think it could have used some more block comments, but that's just me.
  - abecedarius 12y ago
    I'm writing a chapter for AOSA on something like this: a self-hosting compiler of a subset of Python to Python bytecode. It'll present the full code (about the same length) and try to explain it well for people not into compilers yet, but in the meantime I recommend the Wirth book. What's your favorite shorter intro? I'd especially like to reference other educational compilers that are self-hosting.
    - metaobject 12y ago
      So, there is another version of Architecture of Open Source Applications in the works? I love the first two editions - they are unique books that really are gems. Are you able to divulge what projects are covered in the new version?
      - abecedarius 12y ago
        https://github.com/aosabook/500lines https://github.com/aosabook/500lines and I'm looking forward to reading it too. :) I'm tempted to link to my draft chapter, but though the code is essentially done the text needs a lot of work.
agumonkey 12y ago
I wonder if it's faster than http://bellard.org/tcc/ http://bellard.org/tcc/ (in compiled line per sec)
kgabis 12y ago
Wow, nice. I once managed to write a brainfuck compiler/vm in ~100 lines of C [1], but this is impressive. [1] https://github.com/kgabis/brainfuck-c https://github.com/kgabis/brainfuck-c
kgabis 12y ago
Wow, nice. I once managed to write a brainfuck compiler/vm in ~100 lines of C [1], but this is impressive. [1] https://github.com/kgabis/brainfuck-c https://github.com/kgabis/brainfuck-c
userbinator 12y ago
From a cursory glance this appears to be a much-condensed recursive-descent parser with all of the usual parsing functions moved into one, so it's not all that difficult to understand. I think recursive-descent is one of the easiest to intuitively understand parsing algorithms, and it also makes for some concise code; it's also far easier to debug a recursive-descent parser than one of the traditional table-driven ones. Edit: OTCC (http://www.bellard.org/otcc/ http://www.bellard.org/otcc/ ) is another extremely tiny (to the point of being obfuscated) example of a compiler using a recursive-descent parser.
- barrkel 12y ago
  It's an operator precedence parser, which is actually quite a bit faster than recursive descent for expressions when operator precedence is defined using grammar productions that would otherwise get turned into methods. For example, a simplified expression operator precedence can be expressed like this (where {} denotes repetition, implemented with e.g. a while loop in a recursive descent parser (RDP)): expr ::= term { '+' term | '-' term } ; term ::= factor { '*' factor | '/' factor } ; factor ::= '-' factor | <number> | '(' expr ')' ; Typically this would be parsed in RDP using expr(), term() and factor() functions, where expr() calls term(), term() calls factor(), and factor() calls expr() if it sees an opening parenthesis. The trouble is that this means that every single expression parse needs to call through this deep code flow before it can see a single interesting bit of the expression being parsed. Parsing "2 + 3" will result in 5 function calls: expr, term, factor, then term and factor again. The operator precedence parser presented avoids this deeply nested set of calls before it starts parsing interesting things. This problem is far more acute in a language like C, which has lots of precedence levels, than it is in a language like Pascal, which only has a handful.
  - userbinator 12y ago
    I was contrasting it against table-driven parsers (e.g. typical of the Yacc/Bison type) which I believe don't have any recursive calls and use a separate stack, while this one does make recursive calls. In some ways operator precedence/precedence climbing is like an optimisation of RDP, replacing a set of recursive functions with a level counter and a loop.
UnclePeepingSam 12y ago
that's really few points blowing up a plane!
nichochar 12y ago
For mac users: gcc -Wno-all -arch i386 -o c4 c4.c
jdp 12y ago
This is really similar to Marc Feeley's tinyc.c[0], which implements a C subset parser, code generator, and virtual machine in about ~300 lines of C. [0]: http://www.iro.umontreal.ca/~felipe/IFT2030-Automne2002/Complements/tinyc.c http://www.iro.umontreal.ca/~felipe/IFT2030-Automne2002/Comp...
- abecedarius 12y ago
  That's a nice one. The big difference is that it doesn't compile itself -- not that there's anything magical about that, but it's a kind of threshold of seriousness.
  - userbinator 12y ago
    One of the things I've wondered about is how small one could make an ISO C89-compliant compiler (that would be able to compile itself), and all these tiny compiler projects have inspired me to revisit that thought now... I've written pieces of compilers like expression parsers and tokenisers, and even then I felt like it wouldn't be so hard (if I had the time) to write a full compiler. These are all great for dispelling the notion that all compilers somehow necessarily have to be greatly complex and impenetrable to anyone but highly-trained professionals and theoreticians. (Look at the Dragon Book, for example.)
    - abecedarius 12y ago
      You might enjoy http://canonical.org/~kragen/sw/urscheme/ http://canonical.org/~kragen/sw/urscheme/ -- it's by someone who'd just written his first compiler, with links to other sources he found inspiring (one of them mine). C89 I think has too much complexity for the amount of power it offers. lcc is a nice example: Norman Ramsey said he asked one of the authors what he learned in writing it, and got an answer like "Not to write a compiler in C." But anyway the book about it https://sites.google.com/site/lccretargetablecompiler/ https://sites.google.com/site/lccretargetablecompiler/ is very good. http://www.cs.princeton.edu/~appel/modern/ http://www.cs.princeton.edu/~appel/modern/ is my favorite general text.
vesinisa 12y ago
Neat, but this is not a general purpose C interpreter. It seems to lack the preprocessor and is only able to execute the example program and itself because it has wrapper implementations for a static set of standard library functions including printf(), open(), read() and malloc().[1] Use a standard library function it does not readily support, and you're out of luck. [1]: https://github.com/rswier/c4/blob/master/c4.c#L492-L498 https://github.com/rswier/c4/blob/master/c4.c#L492-L498
amelius 12y ago
Next challenge: a fully compliant C++11 compiler written in 4 functions (1) Then, I'd be impressed :) (1) At maximum 500 lines per function, where each line is at most 200 characters long.
bjornsing 12y ago
This shit doesn't scale: $ time ./c4 c4.c c4.c hello.c hello, world exit(0) cycle = 9 exit(0) cycle = 22614 exit(0) cycle = 9273075 real 0m0.067s user 0m0.067s sys 0m0.000s $ time ./c4 c4.c c4.c c4.c hello.c hello, world exit(0) cycle = 9 exit(0) cycle = 22614 exit(0) cycle = 9273075 exit(0) cycle = 933197195 real 0m5.834s user 0m5.827s sys 0m0.000s $ time ./c4 c4.c c4.c c4.c c4.c hello.c Just kidding. :) Amazingly cool! Does anybody have a smaller self-hosing compiler & bytecode vm?
- abecedarius 12y ago
  Self-hosing, haha. Not that I can think of. My https://github.com/darius/ichbins https://github.com/darius/ichbins is shorter but it's a self-hosting Lisp compiling to C.
- bjornsing 12y ago
  For the record: $ time ./c4 c4.c c4.c c4.c c4.c hello.c hello, world exit(0) cycle = 9 exit(0) cycle = 22614 exit(0) cycle = 9273075 exit(0) cycle = 933197195 exit(0) cycle = -1428163377 real 9m23.409s user 9m22.673s sys 0m0.020s :)
ttouch 12y ago
http://git.dzervas.gr/c4 http://git.dzervas.gr/c4 An attempt to make this readable :) (at least with right syntax...)

517 points by petercooper 12y ago

astrodust 12y ago

That is pretty stripped down. Could probably be ported to JavaScript without breaking a sweat.

Lerc 12y ago
That was my first thought, a micro-C to asm.js compiler wouldn't be hard.

petercooper 12y ago

I just wanted to credit Reddit's /r/tinycode sub-Reddit for this link: http://www.reddit.com/r/tinycode http://www.reddit.com/r/tinycode - it's a pretty cool place to discover minimalistic implementations of things.

whitten 12y ago
Thank you for sharing that link to the tinycode Reddit. Did the original poster (for the C in four functions) participate in that sub-reddit ?
- deleted 12y ago
  [deleted]
- pmh 12y ago
  It would appear so. https://www.reddit.com/r/tinycode/comments/2la785/c4_a_c_compiler_in_four_functions/ https://www.reddit.com/r/tinycode/comments/2la785/c4_a_c_com... is the post from /r/tinycode and its OP[0] is the same as the github user[1] for c4. [0]https://www.reddit.com/user/rswier https://www.reddit.com/user/rswier [1]https://github.com/rswier https://github.com/rswier
diltonm 12y ago
Other than Minecraft I don't go to Reddit, this is a cool link though and one I'll be checking, thanks.
- glibgil 12y ago
  Now you mostly go to reddit like anyone else. Is not going to reddit the new "I don't watch TV"?
  - anonbanker 12y ago
    nope. Facebook/Kik/Snapchat/Dropbox is still the new "I Don't Watch TV".
    - 72deluxe 12y ago
      Neat! Then I really Don't Watch TV!
petercooper 12y ago
Update: We seem to have made /r/tinycode a trending sub-Reddit of the day :-) http://www.reddit.com/r/tinycode/comments/2lcq17/rtinycode_has_been_chosen_as_a_trending_subreddit/ http://www.reddit.com/r/tinycode/comments/2lcq17/rtinycode_h...

marcofiset 12y ago

I honestly think this is ridiculous. Sure, this is an incredible feat, and congrats. But serioulsy, I would be ashamed to publish such unreadable code under my name. What about naming your variables with descriptive names? What about extracting complex conditions into well named function to understand what is going on (thus defeating the purpose of the "4 functions") ? This list could go on forever... Writing software is not a contest for who can write the most amount of code in the most cryptic way.

tehwalrus 12y ago
The variable names thing really annoyed me too - a habit of code golf, and people who were originally trained in an old FORTRAN edition that had a 6 or 7 char limit on names.
- _wmd 12y ago
  Unless you're talking about a large piece of software composed entirely of single character functions and variable names, I pretty much disagree. Verbose variable names do not magically teach those reading a piece of code how it works, simultaneously they tend to make it impossible to write many kinds of expressions concisely, and consequently they regularly damage the readability of more complex pieces of code (e.g. arithmetic expressions involving 3 or more terms). The same goes for symbolic constants. Sometimes (but not exactly "often"), use of numeric literals can vastly improve the maintainability of some code, assuming the reader understands how to maintain it in the first instance. As for increasing reader comprehension, carefully thought out comments are a better mechanism by far. In this case, it is sufficient to know that the file is a compiler/interpreter for its entirety to make sense, assuming the reader has implemented (or at least understood the principles behind) a compiler/interpreter in their past. Expanding the function/variable names, splitting "complicated" expressions out into their own functions, etc., does not magically improve the uninitiated's chance of understanding what is going on
  - ajkjk 12y ago
    I mostly strongly disagree. I see no value in naming a variable 'tk', 'pp', or 'bt'. It can only help to make the code more readable with less context. I do not need to understand compilers in detail to know what this program is doing, except, for the names being useless. And if I do understand them but have not spent half an hour or probably much more to digest the exact system by which it operates, I would be completely unable to identify bugs or talk about modifying or extending it in any useful way. Well written comments do not make the code below them more intelligible as text even if they do give you good hints for how to load it into your brain. And "Expanding the function/variable names, splitting "complicated" expressions out into their own functions, etc." all ABSOLUTELY improve the uninitiated's chance of understanding what is going on. Speaking as one of the uninitiated (though I can mostly make out how this works). Man, I wish I knew what 'tk' was. That whole section at line 204 would be so clear if I could follow the intent. I agree with you on symbolic constants and arithmetic though.

TazeTSchnitzel 12y ago

Pretty damn impressive. Though I must wonder: how complete is it? What does it and does it not support? It's at least complete enough to be self-hosting, but beyond that? The code doesn't use that much of C.

cbhl 12y ago
Judging from the comments in c4.cpp, it probably only supports enough of a subset to compile itself. Granted, while building a parser that can parse (let alone compiling) the full C language is nontrivial, any undergrad should be able to build a parser and compiler for a sufficiently simple subset of it. (In my undergrad, we used this subset to build a "compiler" in second year: https://www.student.cs.uwaterloo.ca/~cs241/wlp4/WLP4.html https://www.student.cs.uwaterloo.ca/~cs241/wlp4/WLP4.html)
- JoeAltmaier 12y ago
  You can build a C parser in an afternoon. It only has a few language constructs. Declarations are the hardest. Scanners are readily available for expressions and constants.
  - cbhl 12y ago
    I would be worried about handling the not-context-free parts of the language: http://trevorjim.com/c-and-cplusplus-are-not-context-free/ http://trevorjim.com/c-and-cplusplus-are-not-context-free/ How would you handle these?
    - JoeAltmaier 12y ago
      Scanner has to have access to the symbol table, emit 'ident' or 'type' as appropriate. So not a pure context-free parser.
      - sedachv 12y ago
        Yes. This is the reason it is way easier to hand-build a parser for C than try to use any kind of parser generator.

methyl 12y ago

Unfortunately, I cannot compile it on my OSX 10.10... here's what I get: http://pastebin.com/cVvaYFEH http://pastebin.com/cVvaYFEH EDIT: just make next() function void and it works. EDIT2: still no fortune :( $ ./c4 hello.c [1] 33920 segmentation fault ./c4 hello.c

cremno 12y ago
I think it doesn't work on x86-64, since the code assumes sizeof(int) == sizeof(void*)
- jparishy 12y ago
  Yep, you can compile it on 64 bit OS X with clang's -m32 option and it should work: ➜ c4 git:(master) ✗ clang -m32 c4.c ... ➜ c4 git:(master) ✗ ./a.out hello.c hello, world exit(0) cycle = 9
kschults 12y ago
For now, you need to add both -Wno-return-type and -m32 when compiling.
ackalker 12y ago
Please try kbrock's fork at https://github.com/kbrock/c4 https://github.com/kbrock/c4 Check out his 'longs' branch.

0x0 12y ago

Would you call this a compiler, an interpreter, a virtual machine, a scripting engine, or a combination of those?

marktangotango 12y ago
It compiles a c subset to byte code, then executes in a virtual machine. I think generally an intepreter can refer to either a byte code interpreter (ie virtual machine) or an AST walking interpreter. I didn't see a way to embed c4 into a host language, so maybe not a scripting language? IMO the real value of exhibits like this are boiling the problem (lexing, parsing, compiler, interpreting) down to their most basic parts. One could easily imagine this same language being implemented over 10's or 100's of class files in a more verbose language.
- stcredzero 12y ago
  I think generally an intepreter can refer to either a byte code interpreter (ie virtual machine) or an AST walking interpreter. This brings to mind how fuzzy "interpreter" is as terminology. What is a virtual machine that JIT compiles the byte code or the AST? Is it a JIT implementation of an interpreter? What of implementations that only JIT the most frequently used functions? Wouldn't those be half interpreter and half virtual machine? When it comes down to it, they're all really virtual machines. The real distinction is how we've come to think of different implementations and the representations sub-culturally. For some reason, it makes us feel better when we call certain things interpreters, because of some meaningless (and sometimes factually challenged) competitive instincts concerning implementation speed. (Also, we arbitrarily feel that byte code is somehow more "machine-y" than an AST.) So do I have a problem with "interpreter"? Only when people correct others, as if they're making a correction about something fundamental and factual. In reality, the distinction is between machines that are intended to have the same runtime semantics and really the distinction is only around what optimizations are present in their implementations. Furthermore, if you look at those optimizations in detail, the distinction gets even hazier.
  - TazeTSchnitzel 12y ago

abecedarius 12y ago

On a first skim, this looks really nice; complaints that it's unreadable are unfounded. The background that makes it readable are Wirth's Compiler Construction http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf plus precedence climbing http://en.wikipedia.org/wiki/Operator-precedence_parser#Precedence_climbing_method http://en.wikipedia.org/wiki/Operator-precedence_parser#Prec...

dabockster 12y ago
complaints that it's unreadable are unfounded Not exactly. You have to remember that language and compiler design require a LOT of work and experience to understand, and that many programmers will only see this as, frankly, spaghetti. I think it could have used some more block comments, but that's just me.
- abecedarius 12y ago
  I'm writing a chapter for AOSA on something like this: a self-hosting compiler of a subset of Python to Python bytecode. It'll present the full code (about the same length) and try to explain it well for people not into compilers yet, but in the meantime I recommend the Wirth book. What's your favorite shorter intro? I'd especially like to reference other educational compilers that are self-hosting.
  - metaobject 12y ago
    So, there is another version of Architecture of Open Source Applications in the works? I love the first two editions - they are unique books that really are gems. Are you able to divulge what projects are covered in the new version?
    - abecedarius 12y ago
      https://github.com/aosabook/500lines https://github.com/aosabook/500lines and I'm looking forward to reading it too. :) I'm tempted to link to my draft chapter, but though the code is essentially done the text needs a lot of work.

agumonkey 12y ago

I wonder if it's faster than http://bellard.org/tcc/ http://bellard.org/tcc/ (in compiled line per sec)

kgabis 12y ago

Wow, nice. I once managed to write a brainfuck compiler/vm in ~100 lines of C [1], but this is impressive. [1] https://github.com/kgabis/brainfuck-c https://github.com/kgabis/brainfuck-c

kgabis 12y ago

Wow, nice. I once managed to write a brainfuck compiler/vm in ~100 lines of C [1], but this is impressive. [1] https://github.com/kgabis/brainfuck-c https://github.com/kgabis/brainfuck-c

userbinator 12y ago

From a cursory glance this appears to be a much-condensed recursive-descent parser with all of the usual parsing functions moved into one, so it's not all that difficult to understand. I think recursive-descent is one of the easiest to intuitively understand parsing algorithms, and it also makes for some concise code; it's also far easier to debug a recursive-descent parser than one of the traditional table-driven ones. Edit: OTCC (http://www.bellard.org/otcc/ http://www.bellard.org/otcc/ ) is another extremely tiny (to the point of being obfuscated) example of a compiler using a recursive-descent parser.

barrkel 12y ago
It's an operator precedence parser, which is actually quite a bit faster than recursive descent for expressions when operator precedence is defined using grammar productions that would otherwise get turned into methods. For example, a simplified expression operator precedence can be expressed like this (where {} denotes repetition, implemented with e.g. a while loop in a recursive descent parser (RDP)): expr ::= term { '+' term | '-' term } ; term ::= factor { '*' factor | '/' factor } ; factor ::= '-' factor | <number> | '(' expr ')' ; Typically this would be parsed in RDP using expr(), term() and factor() functions, where expr() calls term(), term() calls factor(), and factor() calls expr() if it sees an opening parenthesis. The trouble is that this means that every single expression parse needs to call through this deep code flow before it can see a single interesting bit of the expression being parsed. Parsing "2 + 3" will result in 5 function calls: expr, term, factor, then term and factor again. The operator precedence parser presented avoids this deeply nested set of calls before it starts parsing interesting things. This problem is far more acute in a language like C, which has lots of precedence levels, than it is in a language like Pascal, which only has a handful.
- userbinator 12y ago
  I was contrasting it against table-driven parsers (e.g. typical of the Yacc/Bison type) which I believe don't have any recursive calls and use a separate stack, while this one does make recursive calls. In some ways operator precedence/precedence climbing is like an optimisation of RDP, replacing a set of recursive functions with a level counter and a loop.

UnclePeepingSam 12y ago

that's really few points blowing up a plane!

nichochar 12y ago

For mac users: gcc -Wno-all -arch i386 -o c4 c4.c

jdp 12y ago

This is really similar to Marc Feeley's tinyc.c[0], which implements a C subset parser, code generator, and virtual machine in about ~300 lines of C. [0]: http://www.iro.umontreal.ca/~felipe/IFT2030-Automne2002/Complements/tinyc.c http://www.iro.umontreal.ca/~felipe/IFT2030-Automne2002/Comp...

abecedarius 12y ago
That's a nice one. The big difference is that it doesn't compile itself -- not that there's anything magical about that, but it's a kind of threshold of seriousness.
- userbinator 12y ago
  One of the things I've wondered about is how small one could make an ISO C89-compliant compiler (that would be able to compile itself), and all these tiny compiler projects have inspired me to revisit that thought now... I've written pieces of compilers like expression parsers and tokenisers, and even then I felt like it wouldn't be so hard (if I had the time) to write a full compiler. These are all great for dispelling the notion that all compilers somehow necessarily have to be greatly complex and impenetrable to anyone but highly-trained professionals and theoreticians. (Look at the Dragon Book, for example.)
  - abecedarius 12y ago
    You might enjoy http://canonical.org/~kragen/sw/urscheme/ http://canonical.org/~kragen/sw/urscheme/ -- it's by someone who'd just written his first compiler, with links to other sources he found inspiring (one of them mine). C89 I think has too much complexity for the amount of power it offers. lcc is a nice example: Norman Ramsey said he asked one of the authors what he learned in writing it, and got an answer like "Not to write a compiler in C." But anyway the book about it https://sites.google.com/site/lccretargetablecompiler/ https://sites.google.com/site/lccretargetablecompiler/ is very good. http://www.cs.princeton.edu/~appel/modern/ http://www.cs.princeton.edu/~appel/modern/ is my favorite general text.

vesinisa 12y ago

Neat, but this is not a general purpose C interpreter. It seems to lack the preprocessor and is only able to execute the example program and itself because it has wrapper implementations for a static set of standard library functions including printf(), open(), read() and malloc().[1] Use a standard library function it does not readily support, and you're out of luck. [1]: https://github.com/rswier/c4/blob/master/c4.c#L492-L498 https://github.com/rswier/c4/blob/master/c4.c#L492-L498

amelius 12y ago

Next challenge: a fully compliant C++11 compiler written in 4 functions (1) Then, I'd be impressed :) (1) At maximum 500 lines per function, where each line is at most 200 characters long.

bjornsing 12y ago

This shit doesn't scale: $ time ./c4 c4.c c4.c hello.c hello, world exit(0) cycle = 9 exit(0) cycle = 22614 exit(0) cycle = 9273075 real 0m0.067s user 0m0.067s sys 0m0.000s $ time ./c4 c4.c c4.c c4.c hello.c hello, world exit(0) cycle = 9 exit(0) cycle = 22614 exit(0) cycle = 9273075 exit(0) cycle = 933197195 real 0m5.834s user 0m5.827s sys 0m0.000s $ time ./c4 c4.c c4.c c4.c c4.c hello.c Just kidding. :) Amazingly cool! Does anybody have a smaller self-hosing compiler & bytecode vm?

abecedarius 12y ago
Self-hosing, haha. Not that I can think of. My https://github.com/darius/ichbins https://github.com/darius/ichbins is shorter but it's a self-hosting Lisp compiling to C.
bjornsing 12y ago
For the record: $ time ./c4 c4.c c4.c c4.c c4.c hello.c hello, world exit(0) cycle = 9 exit(0) cycle = 22614 exit(0) cycle = 9273075 exit(0) cycle = 933197195 exit(0) cycle = -1428163377 real 9m23.409s user 9m22.673s sys 0m0.020s :)

ttouch 12y ago

http://git.dzervas.gr/c4 http://git.dzervas.gr/c4 An attempt to make this readable :) (at least with right syntax...)