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

vgel.me

Post reply on HN
Print view View original

161–170 of 183 posts

Re: Writing a C compiler in 500 lines of Python

#161

Post by hot_gril »

59nadir wrote: post #132
hot_gril wrote: post #95

Earlier quoted context omitted.

Yeah, nowadays a DSL is almost never a good idea. A library for some pre-existing flexible language can do the job without reinventing a whole lot of wheels. The most specific languages I can think of that make sense are SQL and Solidity. But DSLs are tempting, especially among the more passionate programmers, so at work we've ended up with a lot of them. All of them are tripping hazards.

As far as languages go SQL is pretty bad, though. It's not even really a good representation of what it's trying to do. I think if SQL is a good domain specific language the bar seems very low.

Nothing has done SQL's job better than SQL (or its Postgres/Oracle/MySQL variants) so far. The closest would be the map-reduce idiom.

Re: Writing a C compiler in 500 lines of Python

#162

Post by circuit10 »

foldr wrote: post #146
circuit10 wrote: post #137

Earlier quoted context omitted.

If you’re writing code for those why not just use the smaller data types if you don’t need bigger ones? That way it will work efficiently on both and the behaviour will be consistent

Fair point. I guess the issue is with library code that uses int. But you aren't typically going to use lots of general-purpose library code if you're targeting a microcontroller.

If that library code doesn’t use the smaller types then it probably isn’t designed for those platforms, which means it won’t be tested with the smaller int types and they will likely cause lots of bugs. The one advantage I do see is that it might avoid extra sign extension instructions on some architectures when working with less than the native size, but there’s int_fast16_t for that

Re: Writing a C compiler in 500 lines of Python

#163

Post by hot_gril »

eru wrote: post #150
hot_gril wrote: post #99

Earlier quoted context omitted.

> Most DSLs are bad, partially because most people are bad at designing languages. A perfectly-designed DSL is still bad just because it's a whole 'nother language for you to build, and for others to learn, that probably isn't needed for whatever project.

I don't know. Eg people seem perfectly happy to use regular expressions for matching text, instead of accessing the same functionality via eg regular functions in their favourite language.

There are a few exceptions that have made the cut for a useful DSL, like SQL, Solidity, and Regex. Unless your project is totally groundbreaking, odds are low that you invent a new language that can be widely adopted.

Re: Writing a C compiler in 500 lines of Python

#164

Post by hot_gril »

friendzis wrote: post #123
hot_gril wrote: post #95

Earlier quoted context omitted.

Yeah, nowadays a DSL is almost never a good idea. A library for some pre-existing flexible language can do the job without reinventing a whole lot of wheels. The most specific languages I can think of that make sense are SQL and Solidity. But DSLs are tempting, especially among the more passionate programmers, so at work we've ended up with a lot of them. All of them are tripping hazards.

DSLs are awesome for what they are. DSLs let you ingest/load untrusted user code directly and have strong isolation barrier, allowing for very powerful user customizations with "native" implementations of certain features /functions. Anything from programmable authorization to custom views becomes safely and relatively easily available. Say what you want about ESB pattern, but you can implement ESB transformers in a…

React and RN let users define views with JSX that are natively implemented. Not sure if that counts as a DSL, but it's JS extended to allow embedded HTML with custom tags, so it's not really a new thing to learn. Part of what made React popular was how vanilla it felt compared to other things that defined whole new languages or heavy-handed frameworks. And now that it exists, it doesn't need to be reinvented.

At work, we had two painful DSLs for monitoring queries. Our team changed monitoring systems entirely just to use SQL instead.

Re: Writing a C compiler in 500 lines of Python

#165

Post by elvis70 »

kwhitefoot wrote: post #51
dugmartin wrote: post #46

Earlier quoted context omitted.

I think Borland’s Turbo Pascal was also a single pass compiler that emitted machine code as COM files.

Surely it is a feature of all Pascal compilers that they are single pass. I thought that it was part of the specification of the language that it be possible to compile in a single pass.

Microsoft Pascal was a two-pass compiler. It was slower to compile than Turbo Pascal and that pissed off Bill Gates when he realized than Turbo was the most successful.

Re: Writing a C compiler in 500 lines of Python

#166

Post by rkangel »

ak_111 wrote: post #124

Somewhat unrelated question, but I think one of the second most difficult things of learning C for coders who are used to scripting languages is to get your head around how the various scaler data types like short, int, long,... (and the unsigned/hex version of each) are represented and how they relate to each other and how they relate to the platform. I am wondering if this complexity exists due to historical reason…

The simple version is that there are two use cases - the world where you want the size of types to match the target (e.g. int) and the world where sizes are defined by the coder (uint32_t). You want to handle both of those.

That's a nice theory and is what we've got, but it falls down in a few places.

The first is that the "int" world has got a bit munged - some platforms make some slightly strange choices for long and short and so you can't always rely on it (although int is usually pretty sensible).

The other is that when doing unsigned maths, rollover is silent so generally you really need to know the exact size at coding time so that you can ensure that rollover doesn't happen silently.

Together, these mean that you're generally just better using uint32_t (etc.) all over the place and you get more predictable results.

Re: Writing a C compiler in 500 lines of Python

#167

Post by pragma_x »

brundolf wrote: post #6

> Instead, we'll be single-pass: code generation happens during parsing IIRC, C was specifically designed to allow single-pass compilation, right? I.e. in many languages you don't know what needs to be output without parsing the full AST, but in C, syntax directly implies semantics. I think I remember hearing this was because early computers couldn't necessarily fit the AST for an entire code file in memory at once

I can't say if that was a design goal, but it sure looks like it. That's also the way to avoid scaling compiler memory use to program size.

At first I thought that it wasn't possible for C. After I thought about it, as long as you disallow forward references, and rely on a single source file as input, it's possible to compile a complete C program in one pass. Anything else requires a preprocessor (e.g "#include") and/or linker (e.g. "extern" and prototypes) to solve. The implementation in the article dodges all of these and focuses on a very pure subset of C.

Re: Writing a C compiler in 500 lines of Python

#168

Post by vgel »

Joker_vD wrote: post #152

I am pretty certain the following is a valid "for"-loop translation: block ;; code for "i = 0" loop ;; code for "i It doesn't require cloning the lexer so probably would still fit in 500 lines? But yeah, in normal assembly it's way easier, even in one-pass: ;; code for "i = 0" .loop_test: ;; code for "i Of course, normally you'd want to re-arrange things like so: ;; code for "i = 0" jmp .loop_test .loop_body: ;; code…

Oh, interesting--I remember messing around with flags on the stack but was having issues with the WASM analyzer (it doesn't like possible inconsistencies with the number of parameters left on the stack between blocks). I think your solution might get around that, though!

Re: Writing a C compiler in 500 lines of Python

#169

Post by brundolf »

pragma_x wrote: post #167
brundolf wrote: post #6

> Instead, we'll be single-pass: code generation happens during parsing IIRC, C was specifically designed to allow single-pass compilation, right? I.e. in many languages you don't know what needs to be output without parsing the full AST, but in C, syntax directly implies semantics. I think I remember hearing this was because early computers couldn't necessarily fit the AST for an entire code file in memory at once

I can't say if that was a design goal, but it sure looks like it. That's also the way to avoid scaling compiler memory use to program size. At first I thought that it wasn't possible for C. After I thought about it, as long as you disallow forward references, and rely on a single source file as input, it's possible to compile a complete C program in one pass. Anything else requires a preprocessor (e.g "#include") and…

I think this goal may also have shifted over time. I remember when I learned C, we used c89, which required declaring all local variables at the top of the block. This seemed like a weird/arbitrary requirement at the time (and is no longer required in later versions), but it makes a lot of sense in a single-pass context! It would allow the stack frame for the current function to be fully sized before any other logic is compiled

Re: Writing a C compiler in 500 lines of Python

#170

Post by andrewmcwatters »

WalterBright wrote: post #43

This looks a lot like the Tiny Pascal compiler that BYTE published a listing of back in 1978. http://www.trs-80.org/tiny-pascal/ I figured out the basics of how a compiler works by going through it line by line.

Thanks for sharing this, Walter. I'm always curious where language developers get their experience from.
Post reply on HN