C4 – C in 4 functions

https://github.com/rswier/c4

by petercooper • 12 years ago

517 138 12 years ago

github.com

astrodust• 12 years ago

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

Lerc3• 12 years ago

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

petercooper2• 12 years ago

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

whitten• 12 years 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 ?

pmh• 12 years ago

It would appear so. 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

[1]https://github.com/rswier

diltonm• 12 years ago

Other than Minecraft I don't go to Reddit, this is a cool link though and one I'll be checking, thanks.

glibgil• 12 years ago

Now you mostly go to reddit like anyone else. Is not going to reddit the new "I don't watch TV"?

petercooper2• 12 years 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_h...

marcofiset3• 12 years 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.

tehwalrus4• 12 years 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• 12 years 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

emmanueloga_• 12 years ago

I used to rather long names too... but now I think short variables have their place, and sometimes they even improve readability.

This code seems to follow a lot of conventions (if I see the var "i" I could bet a million dollars is an int that is being used as a counter, probably to go through the positions of an array). It uses plenty of enumerated constants, which is good too.

I've been doing some functional programming, where you find that often types are more important than names. See the "Names are overrated" section of this article [1] ( although this point may not apply to this piece of software... C being the language that it is :p).

1: http://techblog.realestate.com.au/the-abject-failure-of-weak...

privong• 12 years ago

Writing software is not a contest for who can write the most amount of code in the most cryptic way.

It can be: http://ioccc.org/

Lerc3• 12 years ago

And indeed, that is how TCC http://bellard.org/tcc/ began its life http://bellard.org/otcc/

tromp• 12 years ago

The IOCCC is more about writing the least amount of code in the most cryptic way.

For example, my entry http://www.ioccc.org/2012/tromp/hint.html is a 25 line "BLC in 7 functions".

Similar to C4, but completely unmaintainable, it compiles Binary Lambda Calculus to bytecode which is then interpreted by a virtual machine.

mappu• 12 years ago

I assume it's a minified version of the other C compiler in his Github account, which does have better variable names and some comments. https://github.com/rswier/swieros/blob/master/root/bin/c.c

mturmon• 12 years ago

This list could go on forever...

Yes it could. While you are adding to your list of coding rules, the OP will have written another fun, tiny compiler.

Who is having more fun?

marcofiset3• 12 years ago

Those are not rules, they are mostly common sense to help the next programmer who has to maintain your code.

cbhl4• 12 years ago

I actually found the code surprisingly easy to read; "tk" stands for "token", "ty" for "type", and so forth.

It's worth noting that compilers don't pop out of thin air -- you have to start with something simple in order to compile a more complicated compiler. Bootstrapping your own self-hosting compiler is a useful academic exercise, and you should try it sometime if you haven't already: http://en.wikipedia.org/wiki/Bootstrapping_(compilers)

marcofiset3• 12 years ago

Well, if this particular compiler is defined in 4 functions, why couldn't it be made out of more functions, enhancing the readability and maintainability of the code?

fla• 12 years ago

The goal here is to write a compiler that can compile itself.

jessaustin• 12 years ago

Yeah I loved this part:

  ./c4 c4.c c4.c hello.c

Granted, most compilers can do the equivalent, but it's rarely so simple to invoke.

more_original• 12 years ago

I honestly think this is ridiculous. Sure, this is an incredible feat, and congrats.

It's not that bad (or difficult), really. It's a hand-written parser for a subset of C that emits assembly code right away. This is how compilers like Turbo Pascal used to work (see http://www.pcengines.ch/tp3.htm for an explanation of what's happening).

Sure, you could apply cosmetic changes like making "*++e = bla;" into "emit(bla);" and you could move the cases into independent methods (that are used once), but this isn't meant to be a state-of-the art compiler and it won't become one if one applies best practices to it.

sehugg• 12 years ago

I don't think it supports forward references either, which also makes it more like Pascal.

karlgrz• 12 years ago

I honestly think this comment is ridiculous. Sure, this is an incredible feat, and congrats. But seriously, I would be ashamed to publish such unreadable English under my name. What about spelling all the words correctly? What about not being an asshole and criticizing someone just because? This list could go on forever... Writing comments is not a contest for who can write the most amount of bullshit in the most non-constructive way.

PavlovsCat• 12 years ago

Writing software is not a contest, period :) It may be for some, it may be for you, but you don't get to sign up other people for it without their consent.

nikki93• 12 years ago

But, "it is only as an aesthetic phenomenon that existence and the world are eternally justified." This piece of code can be viewed aesthetically. Artificial guidelines take the fun out of coding.

fsloth• 12 years ago

Look, one aspect of programming is producing production code that is maintainable, etc.

There are other aspects that are equally as important, and sometimes even more so. Exploring, learning and prototyping are among them, as are "back of the envelope" constructs.

This is a really cool example that shows how far you can go with tiny amounts of code.

Pithyness is actually one way to make code _more_ understandable, given that the reader is familiar with the subject area.

Don't be a snob. The world is a better place because someone wrote this and not worse off.

Since compiler construction is kinda a deep technical field, documenting this in pedagocially sane way would have been a huge task.

I'm happy the author took the effort of writing and publishing this piece, it would be sad if he hadn't just because it's missing an embedded tutorial.

He's not asking you to maintain it. There are references in this thread that explain what is going on...

I write and maintain C++ production code as a day job and some of that stuff is an order of magnitude harder to grok than this (no, it's not documented in any _helpfull_ way either).

boomlinde4• 12 years ago

Writing software is not a contest for who can write the most amount of code in the most cryptic way.

Except when it is.

TazeTSchnitzel4• 12 years 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.

cbhl4• 12 years 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)

JoeAltmaier6• 12 years 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.

verytrivial• 12 years ago

Indeed. The lack of a case statement in the run loop is a bit of a giveaway. Excellent work nonetheless.

Lerc3• 12 years ago

It's clear from the huge number of 'else if' statements that it doesn't support switch statements.

This is also a bit of a clue

    p = "char else enum if int return while "
    "open read close printf malloc memset memcmp exit main";

TazeTSchnitzel4• 12 years ago

Ah, the lack of struct explains why the compiler doesn't use any structs.

methyl• 12 years ago

Unfortunately, I cannot compile it on my OSX 10.10... here's what I get: 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• 12 years ago

I think it doesn't work on x86-64, since the code assumes

    sizeof(int) == sizeof(void*)

jparishy• 12 years 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• 12 years ago

For now, you need to add both -Wno-return-type and -m32 when compiling.

ackalker• 12 years ago

Please try kbrock's fork at https://github.com/kbrock/c4 Check out his 'longs' branch.

0x0• 12 years ago

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

marktangotango• 12 years 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.

stcredzero2• 12 years 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.

abecedarius8• 12 years 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 plus precedence climbing http://en.wikipedia.org/wiki/Operator-precedence_parser#Prec...

dabockster• 12 years 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.

abecedarius8• 12 years 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.

anigbrowl3• 12 years ago

I had the same first instinct, but given that a) it's very very tidy code and b) if you want to understand the inner workings of a compiler then you really do need to figure this out, I decided on review that it's basically self-documenting.

Of course figuring out what it's doing is one thing - understanding why it is done in this particular way is another, and while I was able to find my way around fairly quickly I'd cry if I had to re-implement it. I do love how small it is though, that gives it great educational value.

ezy• 12 years ago

Well, the goal is for it to be minimal, and C doesn't actually do a lot of work for you. On reading it, the algorithm it uses to parse was of less interest than the various tricks it uses to initialize and manage the state of the parser in a compact way.

qznc• 12 years ago

Compilers are also a very well understood topic. If you have seen (and understood) a recursive decent parser with precedence climbing, the code looks as expected. It is a pretty straightforward implementation.

sklogic3• 12 years ago

Basically, what you're saying is that any toy compiler example should be accompanied with a copy of the Dragon Book.

shangxiao3• 12 years ago

It is unreadable. Lumping code together into big functions just so you can say "Look I've created a compiler in 4 functions" is pointless, unless your goal is to post it to HN to show everyone how clever you are.

This is not how you code when you work in a team or when you know some other poor soul has to come along and maintain it.

I suggest you take a look at [1] then go and read this excellent book by Martin Fowler: "Refactoring: Improving the Design of Existing Code" [2]

[1] https://en.wikipedia.org/wiki/Code_smell

[2] http://www.goodreads.com/book/show/44936.Refactoring

RubyPinch• 12 years ago

I have a feeling that the project is a mix of for-fun and to-see-if-its-possible.

Not all programming is enterprise quality, some programming is intentionally not.

Being so dismissive of that, seems a little silly to me.

The demoscene doesn't exist because of a bunch of programmers trying to make the lives of every other programmer more difficult, it exists because people like the challenge.

userbinator4• 12 years ago

This also is not code that would need to be written by a team.

The functions may be big, but they also don't have all that much duplicate code inside them. The choice of 4 functions isn't arbitrary either - they nicely divide the problem into:

- next() - splits the source code into a series of tokens

- expr() - parses expressions

- stmt() - parses statements

- main() - starts the processing of the source, and also contains the main interpreter VM's execution loop

Code generation is integrated into the parsing, since it's generating code for a stack-based machine and that also very nicely follows the sequence of actions performed when parsing.

In fact I'm of the opinion that the obsession with breaking up code into tiny pieces (usually accompanied by the overuse of OOP) is harmful to the understanding of the program as a whole since it encourages looking at each piece independently and misses "seeing the forest for the trees".

In contrast, this is code that is designed to be easily read and understood by a single person, showing how very simple an entire compiler and interpreter/VM can be. It doesn't attempt to hide anything with thick layers upon layers of abstraction and deep chains of function calls, but instead is the "naked essence" of the solution to the problem.

Someone used to e.g. enterprise Java may find this style of code quite jarring to their senses, but that's only because they've grown accustomed to an environment in which everything is highly-abstracted and indirect, hiding the true nature of the solution. Personally, I think the simplicity and "nakedness" of this code has a great beauty to it --- it's a functional work of art.

Confusion• 12 years ago

I suggest you consider how someone could know of, and understand, your suggestions very well, while still having the opinion he does. Don't underestimate other people.

pvidler• 12 years ago

Most of it was readable, but the printf on lines 57--59 made me retch. I see what it's doing, but it's not what I'd call easily maintainable:

  printf("%8.4s", &"LEA ,IMM ,JMP ,JSR ,BZ ,BNZ ,ENT ,ADJ ,LEV ,LI ,LC ,SI ,SC ,PSH ,"
         "OR ,XOR ,AND ,EQ ,NE ,LT ,GT ,LE ,GE ,SHL ,SHR ,ADD ,SUB ,MUL ,DIV ,MOD ,"
         "OPEN,READ,CLOS,PRTF,MALC,MSET,MCMP,EXIT,"[*++le * 5]);

manish_gill• 12 years ago

I'd like to know why this was downvoted, and if people who down voted it can explain what the code is doing please?

PhasmaFelis• 12 years ago

On a first skim, this looks really nice; complaints that it's unreadable are unfounded.

Man, I can't even tell what this is supposed to be. My confusion is entirely founded. My thought process with articles like this goes something like "C in four functions, huh? Sounds like it could be clever. I'll just click and read the explanation... Oh, there isn't an explanation. Well, maybe this file will explain things! ...Nope, it's 500 lines of mostly-uncommented if-else statements. Maybe it's a compiler? I dunno!"

I'm sure there's a subset of the programming community for whom this is crystal clear on first sight, and that's great; but there's a lot more of us who could probably get the joke with a few hints, so it would be nice if you'd help out instead of declaring that if you understand it, it must be easy.

boomlinde4• 12 years ago

In the sense that some people won't have an idea of what's going on, this community altogether isn't particularly inclusive at all. Personally, I really don't want the topics this site covers to cater to a lowest common denominator, and I'm sure that isn't what you had in mind either, but that's the effect of taking "more of us" to mean more than you personally.

abecedarius8• 12 years ago

Yes, I'm sorry: I meant to defend this code from the charge of being pointless code golf, and inadvertently disparaged people without the background to enjoy reading it. It really is hard to follow without that background, which lots of good programmers don't have.

I hope someone will write an explanation. I'm still working on one for my own (quite different) little compiler.

tomp• 12 years ago

complaints that it's unreadable are unfounded

    int *a, *b;
    int t, *d;

I can't really see how anyone can say that code that uses one-letter variable names (with the exception of the "standard ones", whose meaning is defined at the top) is readable.

abecedarius8• 12 years ago

OK, 'unfounded' was a little too strong. I'd change some things myself, including comments on those declarations; but if this looks like a code-golf game to you, it's not, it's a style you're not used to.

agumonkey• 12 years ago

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

kgabis• 12 years 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

userbinator4• 12 years 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/ ) is another extremely tiny (to the point of being obfuscated) example of a compiler using a recursive-descent parser.

barrkel4• 12 years 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.

userbinator4• 12 years 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• 12 years ago

that's really few points blowing up a plane!

nichochar• 12 years ago

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

jdp• 12 years 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/Comp...

abecedarius8• 12 years 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.

userbinator4• 12 years 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.)

vesinisa• 12 years 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

amelius• 12 years 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.

bjornsing2• 12 years 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?

abecedarius8• 12 years ago

Self-hosing, haha. Not that I can think of. My https://github.com/darius/ichbins is shorter but it's a self-hosting Lisp compiling to C.

bjornsing2• 12 years 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• 12 years ago

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

C4 – C in 4 functions

Related Stories