Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Writing a C compiler in 500 lines of Python (2023)

vgel.me

Post reply on HN
Print view View original

71–80 of 114 posts

Re: Writing a C compiler in 500 lines of Python (2023)

#71

Post by pjmlp »

flohofwoe wrote: post #56
Buttons840 wrote: post #40

After many years of programming in other languages, I finally learned C, and came to realize that there aren't actually any compilers that implement all of the C spec. Even GCC and Clang have their grey areas and their bugs. Before this, I had thought that C was a simple language. An idea propped up by articles likes this, as well as the oft touted fact that nearly every embedded system has a C compiler; no matter wh…

> I finally learned C, and came to realize that there aren't actually any compilers that implement all of the C spec. I think the main reason for this is that the C spec was always just an attempt to somewhat harmonize the already existing features of different C compilers, e.g. implementations come first and then after one or two decades, the C committee tries to standardize the features that have survived. That doe…

I think it is a side effect of SFI (Secure Safety Initiative) at Microsoft, Azure and Windows development guidelines to use managed safe languages or Rust, leaving C and C++ for existing code bases.

Even though Microsoft employees tend to dismiss this at Reddit discussions, the lack of resources is quite visible.

Re: Writing a C compiler in 500 lines of Python (2023)

#72

Post by pjmlp »

dlcarrier wrote: post #48
Buttons840 wrote: post #40

After many years of programming in other languages, I finally learned C, and came to realize that there aren't actually any compilers that implement all of the C spec. Even GCC and Clang have their grey areas and their bugs. Before this, I had thought that C was a simple language. An idea propped up by articles likes this, as well as the oft touted fact that nearly every embedded system has a C compiler; no matter wh…

C has a lot of feature creep, and C++ is just C with extra feature creep. The original C compiler ran on a PDP-11, which usually had just kilobytes of RAM. The syntax was written around compiling with such limited resources, hence the need for headers, primitives, semicolons, linkers, and so on. It has changed a lot over time, but seems to be adding baggage, not removing it.

Only for C89 versus C++98, in current days of C2y versus C++23, they are two worlds apart.

Re: Writing a C compiler in 500 lines of Python (2023)

#73

Post by jlokier »

bluGill wrote: post #12
weregiraffe wrote: post #2

Now write a Python compiler in 500 lines of C.

I could probably do it - but you wouldn't like it. My dictionaries would be a linked-list, looking for a key becomes a linear search... (if you gave me C++ I'd use std::map) I'm assuming you will allow me to use the C standard library, if I have to implement strlen or malloc in that 500 lines of C I'm not sure I can pull that off. 500 lines is aggressive, but IOCCC gives me plenty of tricks to get the line count down…

If you can search (and do other operations) on a linked list, and the lists are long enough to matter, you can trivially speed it up to a fixed-size hash table with hardly any code changes.

This:

    entry = list_search(key, list);
becomes:

    entry = list_search(key, lists[hash(key) % (sizeof(lists)/sizeof(lists[0]))]);
This:

    list_add(key, entry, list);
becomes:

    list_add(key, entry, lists[hash(key) % (sizeof(lists)/sizeof(lists[0]))]);
etc.

A simple hash(), not high quality but good enough for non-adversarial inputs, can be a one-liner.

A good dictionary does more than this of course, especially dynamic sizing, but this simple change can radically speed up simple linked list code when the lists are long, you don't have a hash table implemention you can use, and you want to keep the code change very small.

The same principle can be used with other things than lists too.

Re: Writing a C compiler in 500 lines of Python (2023)

#74

Post by nurettin »

vidarh wrote: post #58
nurettin wrote: post #43

Earlier quoted context omitted.

Python has the same amount of nightmare. Maybe even more. You can add static class and instance accessors at runtime, it supports full monkey patching just like Ruby does. You can meta program modules, classes, objects, you can decorate classes and functions, declare functions and lambdas anywhere. "compilers" usually disallow monkey business and compile only a subset.

While my (half finished, buggy) Ruby compiler is definitely a subset, it allows the monkey business. There are ways to do it reasonably, but making it fast gets a lot harder when you do...

Best in Class seems to be JRuby, but it needs a JVM in between.

Re: Writing a C compiler in 500 lines of Python (2023)

#75

Post by MarsIronPI »

kragen wrote: post #44
MarsIronPI wrote: post #32

Earlier quoted context omitted.

My impression is that in general the traditional approach of methods as members of a class is more verbose and less extensible than the ML/Lisp generic function approach. I know I certainly prefer generic functions when I have to design polymorphic interfaces.

"Generic functions" is the Common Lisp name for writing a separate method for each class, the same as in Python except that you also have to define the generic function itself before you can define the methods. I'm not sure if that's what you meant; the ML approach is quite different. This is Common Lisp, which I am not an expert in: ;;; Stupid CLOS example. (defgeneric x (point)) ; make X a method (defgeneric y (poi…

> I'm not sure if that's what you meant; the ML approach is quite different. There is a difference in approach because in Common Lisp each method is a separate function definition (though macros can alleviate this), but my point is that both CL and ML are more function-oriented, if you will; i.e. "methods" (or whatever you want to call ML pattern-matched functions) aren't defined in a class body and are just ordinary functions.

I think this more function-focused approach is more elegant, but also more extensible and possibly less verbose when dealing with multiple classes that share the same interface.

> the same as in Python except that you also have to define the generic function itself before you can define the methods. As a side note, though it's not terribly important, the "defgeneric" can be omitted if you don't care to specify docstring or any special behavior.

Re: Writing a C compiler in 500 lines of Python (2023)

#76

Post by flohofwoe »

pjmlp wrote: post #71
flohofwoe wrote: post #56

Earlier quoted context omitted.

> I finally learned C, and came to realize that there aren't actually any compilers that implement all of the C spec. I think the main reason for this is that the C spec was always just an attempt to somewhat harmonize the already existing features of different C compilers, e.g. implementations come first and then after one or two decades, the C committee tries to standardize the features that have survived. That doe…

I think it is a side effect of SFI (Secure Safety Initiative) at Microsoft, Azure and Windows development guidelines to use managed safe languages or Rust, leaving C and C++ for existing code bases. Even though Microsoft employees tend to dismiss this at Reddit discussions, the lack of resources is quite visible.

In that case they should really just deprecate MSVC and point C and C++ devs to Clang. Would make life a lot easier for library authors.

Re: Writing a C compiler in 500 lines of Python (2023)

#77

Post by alienbaby »

I thought I had learned a new word reading this, but instead I just have something that seems like it should be a word given the context it was discovered in. Perhaps that in itself should be considered cremement. A word that looks like it should be a word but isn't.

Re: Writing a C compiler in 500 lines of Python (2023)

#78

Post by pjmlp »

flohofwoe wrote: post #76
pjmlp wrote: post #71

Earlier quoted context omitted.

I think it is a side effect of SFI (Secure Safety Initiative) at Microsoft, Azure and Windows development guidelines to use managed safe languages or Rust, leaving C and C++ for existing code bases. Even though Microsoft employees tend to dismiss this at Reddit discussions, the lack of resources is quite visible.

In that case they should really just deprecate MSVC and point C and C++ devs to Clang. Would make life a lot easier for library authors.

Clang is included on Visual Studio installer for ages.

It was the official answer back when they decided only to do C++ and leave C behind, until the change of heart with C11/C17 support.

Also note Apple and Google aren't any longer the nice sponsors of clang, hence it has also lost steam as other contributors aren't at the same level as they used to be.

Re: Writing a C compiler in 500 lines of Python (2023)

#79

Post by Arch-TK »

anta40 wrote: post #45
pjmlp wrote: post #42

Earlier quoted context omitted.

That is a myth often spread by folks that think K&R C book is everything there is to know, never opened the ISO C draft PDF, learned the differences between POSIX and standard library, tried to make their code portable outside GCC or nowadays clang, or even checked the extensions chapter on the compiler.

Who told that? I still hear K&R being recommended as introduction material. If you want to write portable/production-grade C code, well definitely need to study another references.

There are very few resources for learning C which aren't themselves full of terrible C.

If you want a short introduction with the caveat that it only covers C89, only covers parts of it, and doesn't cover e.g. POSIX or anything outside of standard C then K&R2 + errata is fine.

If you want a long book on C which has a more modern approach then there is K. N. King's C a Modern Approach.

Jens' book is at least vouched for by https://iso-9899.info/wiki/Books . So I have to assume it's also okay.

Re: Writing a C compiler in 500 lines of Python (2023)

#80

Post by 1vuio0pswjnm7 »

Buttons840 wrote: post #40

After many years of programming in other languages, I finally learned C, and came to realize that there aren't actually any compilers that implement all of the C spec. Even GCC and Clang have their grey areas and their bugs. Before this, I had thought that C was a simple language. An idea propped up by articles likes this, as well as the oft touted fact that nearly every embedded system has a C compiler; no matter wh…

"Before this, I had thought that C was a simple language."

It was a simple language. It can still be used that way

As hobbyist I write simple programs that can be compiled with -std=c89

I use these programs every day. They are faster than their equivalents in python, smaller than their equivalents in go, and require less resources or dependencies to compile than their equivalents in rust

It is easy to take something simple and make it complex

Software developers do this consistently; software/language "by committee" faciltates it

Generally developers commenting publicly do not like "simple", they prefer "easy"

C89 is still useful and there are lots of things that rely on it

Post reply on HN