The ancient artefact described also featured in a Jonathon Blow lecture, as an example of an engineering skill we lost for 1600 years: https://youtu.be/ZSRHeXYDLko?t=402
I'm interested in making a really simple compiled scripting language. I don't understand why most scripting languages compile to bytecode and then interpret that. This requires the following steps:
1: Design a bytecode. 2: Write a compiler. 3: Write an interpreter.
It seems like it would be simpler to not bother with 1 and 3 and instead use machine code as the bytecode. A side benefit is that programs will run faster.
I think it is easy to generate machine code for x86_64, ARM64 and risvc64, as long as you don't mind it being 3x larger and slower than an optimizing compiler would generate. It ought to be easy because it is possible to only target the common subset of features these architectures support.
I made a start, https://github.com/abainbridge/mortar, but haven't got much past being able to compile and run a Fibonacci sequence generator. I have no experience with language design or compiler implementation. I was somewhat gobsmacked when the fib generator ran 380x faster than an almost identical looking Python program.
Any comments or suggestions, including, "that's a bad idea, you will fail because of XYZ", or, "save yourself the effort, here's one I wrote earlier..."?
is probably a non-starter, so compiler writers tend to attack the problem by breaking it down into lots of passes.
Parsing into an AST is obviously the first, then you might opt into other passes, like type-checking, handling closures, simplifying into some kind of IR, and finally generating code. Each of those stages can be effectively unit-tested (except maybe the last). If you make a mistake in parsing (e.g. mistaking a statement for an expression), you don't want to have to catch that error by inspecting machine code. It's nice if each pass can be easily tested. And one simple way to test these things is to write an interpreter for each pass (mostly because you get to enjoy the facilities of whatever host language you're writing in). Then you can start saying things like "for all inputs, interpreting the AST gives the same result as interpreting the type-checked-AST, gives the same results as interpreting the closured-AST, gives the same results as interpreting the list of IR instructions."
You mention "It ought to be easy because it is possible to only target the common subset of features these architectures support." <- That's your IR right there!
Once you have an IR that looks close enough to the target machine language, it shouldn't be too hard to translate the final step. Or just use LLVM.
I noticed in your code that you're using C, and really there's no need. Languages don't need to be stacked in a hierarchy (e.g. Clojure on top of the JVM which is C++ which compiles to asm). The compiler can be any language, because it only needs to be able to take in source code and spit out bytes.
> I think the viewpoint that your're missing is: how do I make sure the machine code means the same thing as the source code?
Ooo, no. I already have an AST. When writing the code gen for a node type in the AST, I normally start by typing a few lines of C into godbolt that exercises the same kind of thing represented by the node type. I try a few different compilers and optimization settings and look at what gets generated. I pick an approach that looks simple and good enough. Then I ask an AI to assemble the instructions I see the compilers using. I like to ask an AI to do this because it will explain what all the bits do in the instruction encoding and it is less error prone at reading the ISA docs than I am. The description from the AI might prompt me to ask things like, "what if the jump target doesn't fit in the 32-bit immediate" etc.
All I was claiming was that this is easier than generating code for a byte code of my invention, partly because I don't have to invent a byte code and partly because I can use existing tools to help, eg disassemblers/debuggers to check my output or compilers to give me ideas on how to convert C-like statements into machine code.
I don't have any IR at the moment. I'll have a think about what benefits that might bring.
The reason I posted my project under this top level thread is because I'm interested in Small Programs and Languages. My experiment is in what I can remove from a language implementation to make it simpler. Adding a dependency on LLVM is the opposite of what I had in mind :-)
There are many reasons I'm writing it in C but mainly because I like C.
I would recommend reading a book about programing languages, most of those explain this imo.
What I understand from that is, byte code is portable while machine code isn't.
So you can write a byte code interpreter in C and you have fully cross platform toolchain.
It is also supposedly easier to generate bytecode compared to generating something like x86_64 machine code or assembly.
Imo what matters more is the execution and not the idea anyway so you shouldn't care about this:
> Any comments or suggestions, including, "that's a bad idea, you will fail because of XYZ", or, "save yourself the effort, here's one I wrote earlier..."?
> What I understand from that is, byte code is portable while machine code isn't.
This is an area I want to explore. It seems to me that it is less true than it used to be. x86_32 was the last significant architecture that made things hard. Now we can ignore that. All desktop or server class CPUs support 8, 16, 32 and 64-bit integers. And they all have at least 10 general purpose registers. They all have a sensible set of memory access modes. As a result, the same code generator works for them all. As it stands, my code generator calls functions like emit_indexed_load, emit_conditional_jump etc. There are currently 26 of those functions and they're all trivial.
So far I have only implemented them for x86_64 machine code output. But writing versions that output ARM64 or risvc doesn't seem hard. I expect I'll find small problems which will cause me to have to tweak the set of CPU features my code gen depends on.
As for generating bytecode being easier than x86_64 machine code, I disagree. There are lots of tools for validating x86_64 machine code (ie disassemblers). There aren't any for a bytecode I might invent. And I can ask an AI how to generate x86_64 machine code to do an indexed load. I immediately get the answer. I don't have to think about how to make an efficient bytecode encoding.
The hardest thing I've encountered so far is getting the ABI right so that my compiled code can call existing functions (eg libc). But I'd have to do that even if I was using an interpreter.
It is straightforward to pick an isa and then design an ir that closely mirrors it. Codegen from the ir the original isa is dead simple. Other isas are also straightforward except that it may be necessary to introduce virtual registers and implement certain instructions as multiple instructions if there isn't a 1:1 correspondence.
I think the op is far too pessimistic about code size and performance. TCC for example produces terrible machine code but I rarely see 3x size or performance diffs compared to clang (at least for the kinds of programs I tend to write). It is also very easy to find edge cases where the clang optimizer makes heinously bad decisions. In one trivial example, I've written a program that has a helper function with no arguments that simply prints "Hello, world!" and a main function that calls the helper 1 million times. With optimizations, the version of clang on my computer inlined the helper call 1 million times, which made the binary I believe 4-6x bigger than -O0. With -O0, I believe compilation took 6 seconds compared to something like 15 minutes with -O2 (tcc took maybe 250ms and produced a binary that I think was about 2x the size of gcc -O0). All that is to say, I have less faith in the quality of optimizing compilers than most.
> I think the op is far too pessimistic about code size and performance
My code gen is definitely worse than TCC! But I think modern CPUs see all my redundant register-register moves and just treat them as a no-ops. Probably performance isn't much worse than TCC. But currently I can hardly compile a program complex enough for a meaningful comparison to be made.
You should do it. But I recommend a book or two on compiler design. There are useful techniques (like SSA) that simplify program analysis if you decide you want to dip your toes into adding optimizer passes. Building stuff yourself, the hard way, is definitely the best way to learn. I wish I had unbounded time to do it…
Edit: I like the Appel compiler book. One of my students enjoyed “Writing a C compiler” by Nora Sandler. There are also a number of classic compiler books that feel more relevant once you are deep in the weeds.
I didn't know about the Appel book. I'll take a look. Thanks.
I feel like the way we write about compiler design could be reduced in complexity too. I read the blog posts by Nora Sandler and they did a great job compared to "the Dragon book" (confusing now because her book has a dragon on the front too). But we still ought to replace phrases like "lexical analysis" with "character grouping" (credit to Sam H Smith for forcing that one into my brain).
For code generation, you can just walk the AST and either;
1) Emit the text of the assembly code for x86_64/ARM64/RISC-V and then leave the rest to the system assembler.
Or,
2) If you want to be even more professional, emit text of LLVM IR and then leverage its complete toolchain.
From your github i see you mention the "MicroC" subset of C language. Maybe follow the above but with the syntax/grammar of MicroC for your implementation.
I have used tcc as a scripting language in the past. I expect that if your shell script catches the compilation, that sort of approach will satisfy your requirements, even if tcc itself does not.
TCC is partly what motivated me to try. But I want to get closer to lower the Kolmogorov Complexity. I'm happy to sacrifice C compatibility. In fact I'm happy to sacrifice much of the power of C. And I'd be happier with code that was somewhat slower.
And the original TCC code is not easy to understand. It is a lot cleverer than I can cope with!
Some high level features of the language might be more complicated to implement in assembly than in bytecode. The latter can have instructions more closely matching the language's features.
Similarly, it is quite rare to compile programs directly to assembly. In general, you have some intermediate representations... which can closely resemble some bytecode. The reason is the same: compiling to a higher-level IR is simpler than going directly to assembly.
Hand-hinted by Fabrizio:
”More than 9000 characters optimized from 9pt to 48pt to guarantee the best possible readability.”
It is the ultimate “programmer’s font” and well worth the money for something you stare at every day and the next best thing to a bitmap font in today’s “Retina resolution” world.
I don’t prefer bitmap fonts (anymore) because I find subpixel antialiasing beneficial. But I’m with you regarding low-DPI monitors, and the lack of pixel-grid hinting in modern fonts is a pity.
It’s similar to vector icons versus hand-drawn bitmap color icons.
Below phone-level PPI values, font AA still just looks blurry to me. As I like 'em large though, there are not too many bitmap options (terminus, for example, looks quite brittle at large sizes). I seem to have settled on lode 1.5 from here on a ~110 PPI display: https://github.com/B2HDPI/B2HDPI
I want to see the same graph but for number of CVEs introduced. ie, when we find a CVE, find out which kernel version introduced it. This would only be useful for kernel versions that were a few years old, so we'd have had time to find most of the CVEs. But it'd still be interesting.
There's a graph for bugs and bug-fixes (not CVEs, but in linux close) near the end of this article that looks approximately like what you are interested in: https://lwn.net/Articles/1088776/
Yes. I don't really understand why Zig gets more attention than dlang. It seems that it is more to do with the personality of the authors, rather than the technicalities. I get the impression that Walter is more laissez-faire, while Andrew is more single-minded. I'm grateful to the contributions both have made.
Pardon any corruption in my memory. But I think D in it`s early days had non-optional garbage collection. Which seemed like a bad choice at a time when I think many of us wanted a better C, not a more inconvenient C#. Then they made garbage collection optional, which split the ecosystem into garbage collected and manual libraries. Not a great choice either. Then there was a drama and split because of two competing standard libs. And also the compiler was closed source which turned some people of in a time where open source compilers had become an expectation. So all in all, some wrong turns made it lose momentum and I don`t think it can recover in todays climate.
Zig, for better or worse, have a strong messaging and isn’t afraid of making big claims. That they don’t always pan out (”faster than C”, ”colorless async” etc), doesn’t matter. Zig was the first C alternative to spring from the interest Jon Blow ignited with his language dev and that marketing lead has been superbly well maintained by Andrew.
Odin and C3 has at least a magnitude fewer people knowing about them. More modest claims, less marketing potential.
So for D, it was to my memory never sold as a silver bullet either. A better C++ certainly, but with enough humility to not market itself as some game changer.
Compare Zig, V and Rust marketing with D’s and you’ll see what I mean.
For me it's because Zig presents a novel and even revolutionary new coherent design for low-level programming, whereas D is mostly a collection of many ideas, many of them are good, but they don't coalesce into a simple design philosophy. I think somebody once said that good (or coherent) design is what happens not when there's nothing left to add but when there's nothing left to remove. That product X has all the components of product Y and possibly more doesn't mean that it contains within it Y's design. The novelty of the iPhone wasn't that it had a touchscreen, but that it had little else. Such a coherent design grabs, and deserves, attention.
For example, another language that immediately grabbed my attention (aspirationally; I haven't looked at it closely yet) is https://github.com/aardappel/goose/. That's not because it has arenas, but because it doesn't have anything else.
Another point I liked was that there was, apparently, an influential book called Structured Programming, whose content was so universally agreed upon, that all programming became Structured Programming. Nobody needs the book anymore.
It's not the focus of the talk and so it's hard to tell if Casey understands (the choice to separate the words GO TO in several places suggests he does) but the `goto` keyword you've seen in several modern languages is not the problematic "GO TO statement", it's a de-fanged remnant, the toy poodle to GO TO's wolf pack.
The actual GO TO complained of is, like the jump instruction in machine code, just entirely unbothered by context. Want to go from the middle of this code about employee payroll processing to mid-way through initializing a weather simulation? No problem. Well. No problem for the machine, for a human programmer it's a complete nightmare. Actually that's putting it mildly, nightmares have more structure. You cannot do anything like that with for example C's goto.
You compiler can, and in a few cases (that's what the discussion about the tail-call optimisation is about for example) it will, but the program you wrote doesn't do this and so you don't have to try to keep the whole program in your head.
So in that sense GOTO died out with, maybe BASICs? I think the BASICs tend to have that wolf nature GOTO feature, but nothing modern has it.
In the early 90s I was doing IT type C with SQL database software. There was one pattern of goto usage common: clean up at the end of a function if something went wrong (close db cursor, log something, return error code, and the like). When that space went to Java and to some extent C++ (and later C#) exceptions could be used instead. A defer statement would have been a more direct replacement for the pattern, though.
So, I have never seen anyone actually use GOTOs, so maybe a lot of the stigma comes from excessive, poor usage or something.
However, having written a good chunk of ASM in my life. I don't think jumps or branches are really that hard to follow. Jumps/Branches and GOTOs specify the next location. It is not as though one has to guess where.
It's not the arrow, it's the archer that is the problem.
Never as in, in BASIC, or you've never seen goto in C? The de-fanged C "goto" is all over the place in Linux and in similar close-to-metal C software. C does not (yet, likely C2Y will fix this) have labelled break, so goto is used to say "I am inside a mess of nested loops, we're done, end the loops" and as a catch-all failure handler in some codebases.
My guess is that your ASM is inflected by structured programming everywhere. Yes, unlike COME FROM we can see where we're going next with GO TO but if you go back 60+ years there is some scary code that even today's optimizers probably wouldn't emit because it's too crazy. Suppose calculate-total-fuel ends with three CPU instructions which copy register F into register H then add register C to it and multiply the sum by four. Over in locate-horizon it so happens we need to add two things together and multiply them by four and we could do that last. So, if those two things were in registers F and C we could just GO TO that last part of calculate-total-fuel.
You're correct that we don't need to "guess where" it goes, but good luck understanding why the program works when it's like this, let alone the ordinary maintenance work of making small modifications.
> My guess is that your ASM is inflected by structured programming everywhere.
I think you're probably right. To expand on this:
In asm, you can have things that are clearly functions. You have a stack discipline going in and out of them. They end with stack cleanup, then a RET or some such, which pops the return address off of the stack and jumps to it. Within that function, you have JMP instructions (or whatever) that move around within the function. You may also call other functions, by pushing variables on the stack, and then calling JSR or whatever to push the program counter on the stack and jump, and when those functions return, you'll be right where you were in this function. That's all sane, and it's "structured assembly".
Non-structured assembly would be like the example in your second paragraph. You're in one function, and you JMP (not JSR) into the interior of a second function. Or, you simply don't have functions, just labels that you jump around do. That's not structured, and not sane.
I have no idea what the parent meant by, "My guess is that your ASM is inflected by structured programming everywhere."
(I am the GP)
Your response was far better than mine. If those instructions were executed more than a couple of times and the constraints/assertions were identical, I'd absolutely throw them in a function. I'll handle what I need to before/after the function.
I would never branch to some coincidental label. That is why I love ASM so much. If you are sloppy or lazy, you will most likely be punished severely for those choices.
(Tangential, but when I first learned ASM in college, I felt like I learned more in that one semester than all the sum of all classes in my entire degree.)
By "inflected by..." I'm suggesting that Structured Programming has altered how you write assembler even though of course assembler doesn't inherently provide that structure.
When you need to do X here and there, you write code to X and then you call it where it was useful - you don't have code in one function just jump to a label in a completely different function because, in this era where structured programming is taken for granted - that seems crazy. And it is, but only the same way that chattel slavery seems crazy today, in the Antebellum South it was just usual and likewise in 1950s computer software just jumping into unrelated code was normal.
One of the principles of structured programming is that you organize your code into functions, and that they have single points of entry, and single points of exit. We still have a lot of multiple points of exit in functions these days, but the reasons for them usually fall into either those of clarity (less nesting/branching) or performance by skipping unnecessary work, and the consequences of them are less dire in modern high level languages because such languages have GC (no fear of skipping a memory cleanup step) and features like try..finally to ensure code closing file handlers or logging or whatever is executed at the end. But we have largely eliminated multiple points of entry from most code. The main remnant I can think of is in the form of coroutines, though they are structured and limited enough (like modern gotos) and have well defined lifecycles that it's more forgivable.
To be honest, I do not have much experience with C nor BASIC. I only know the extreme basics of C, and I have never written a line of BASIC in my entire life. My first real exposure to programming was in high school (Java). From there, I basically went from high-level languages -> x86 -> high-level languages again -> starting to play with AArch64 in an attempt to but some grooves back in my smooth brain.
> My guess is that your ASM is inflected by structured programming everywhere.
I am not certain what you mean.
> if you go back 60+ years there is some scary code that even today's optimizers probably wouldn't emit because it's too crazy.
Why was this as common as the allegations lead me to believe? Was it just a product of time? No better way to handle such logic at the time?
As for your example, I know it is intended to be interpreted trivially, but I just want to clarify I understand you correctly. Is the issue due to locate-horizon depending on logic from a completely orthogonal operation?
If so, I see the red flag immediately. However, I do not see an issue with creating a separate function. I'd just have to be damn sure H was not storing anything used for some other upcoming operation prior to the function call, I'd check F and C for valid state (if necessary), take other potential side-effects into account, etc.
It feels a lot like the DRY advice being abused in higher-level languages, you know? I agree with expression, "duplication is better than the wrong abstraction."
Same reason that nobody did the Fosbury Flop at the 1948 Olympics - Dick Fosbury hasn't shown this technique yet and it's not obvious if you've never seen it that this is a better way to perform an Olympic regulation high jump. Twenty years later, he does exactly that and wins Gold and by the 1988 Olympics this is how everybody does a high jump, but in 1948 nobody knows it.
Your instinct to "create a separate function" is exactly Structured Programming.
No, they're not sarcastic. It was an interesting point; if an idea succeeds well enough people just do it and make it "common sense". It's a point in the talk.
There are many well documented cases of rapid evolution: a population of African elephants became 50% tuskless at birth in a single generation, urban fox anatomy diverged from rural, frogs in the Chernobyl Exclusion Zone turned black, the Peppered Moth turned black in the industrial revolution.