IRC channel logs
2026-09-23.log
back to list of logs
<siraben>E2E TCC bootstrap under 10 minutes now <siraben>astra suggests some changes to M2 that would further reduce times but I am weighing the additional complexity tradeoff <siraben>I'm already overfitting the vm.c to M2 of course here, e.g. switch case statements are arranged in order of branch frequency since M2 does it linearly <notgull>Question: what’s the stance on LLM-generated code in the live-bootstrap? I’m not sure if LLM-generated code counts as "generated source" à la Yacc tables for the live bootstrap. <matrix_bridge><Jeremiah Orians> The most valuable result is not the working code but a mind that understands the what, how and why. Which enables new ideas and new insights that could not be discovered without that mind’s learning from the collective knowledge and experience of other minds. <notgull>It’s why I don’t use LLMs for personal projects <matrix_bridge><Jeremiah Orians> I definitely share that sentiment. Personal projects are like a reflection of who you are and what you value. Those sorts of things get in the way of that. <notgull>For me it’s journey before destination <notgull>Having a pretty C compiler pales in comparison to understanding a C compiler <matrix_bridge><Jeremiah Orians> Well having an easy to understand compiler would be easier with a typed S-expression language but unfortunately language wars make it hard to get people to agree on it. Which tragically makes C and its weird behavior incur additional complexity for any implementation. <matrix_bridge><Jeremiah Orians> Like half the complexity in cc_x86 is just dealing with C’s operator priority and clunky index/pointer handling when a lisp style indexing and classes would have been much simpler to implement in assembly <matrix_bridge><Jeremiah Orians> No, Mes was janneke’s idea to create a minimal lisp that could run a c compiler written in that subset as quickly as possible. Only after he did his first talk about it did we start working together <notgull>I know there’s a page on the bootstrap wiki regarding Lisp and why it wasn’t chosen as a C predecessor. Did this predate the implementation of sectorlisp? <matrix_bridge><Jeremiah Orians> And sectorlisp doesn’t support half the things that one needs to run mescc <notgull>I know sectorlisp is slow but I think with a few modifications (like actual number types) you could get to having a decent-ish lisp <matrix_bridge><Jeremiah Orians> There are a good few things that are in lisp that can’t be implemented in lisp unless that lisp already supports them. <notgull>Actually, I just remembered macros exist <matrix_bridge><Jeremiah Orians> And I tried writing a lisp in M2-Planet for a while that would run mescc and there was years worth of work needed to close that gap. Janneke closed that gap in mes.c much faster <matrix_bridge><Jeremiah Orians> (He is forever going to be much better at Lisp than I shall ever be) <matrix_bridge><Jeremiah Orians> Turns out; you need less C features in a Lisp interpreter than you need Lisp features in a proper C compiler. <matrix_bridge><Jeremiah Orians> And minimal C compilers are self-hosting with just a tiny subset of the C language (like about 2-4% of the full c89 standard) and mescc supports more of the C language (for now and one day M2-Planet will grow to the point that it is able to compile TCC directly) <notgull>I was trying to get M2 to compile TCC a while back <notgull>Biggest missing thing seems to be vararg support <matrix_bridge><Jeremiah Orians> In C a[3] == 3[a]; that doesn’t hold true for M2-Planet <notgull>Do compilers depend on that behavior? <matrix_bridge><Jeremiah Orians> There are some C programs that do definitely depend on it. <matrix_bridge><Jeremiah Orians> Not to mention the programs that depend on C specific macro behavior that borders on violating the C specification <matrix_bridge><Jeremiah Orians> The TCC/clang growing to be able to build GCC are filled with stories of the various standards questioning things needed to be done <notgull>You’d think that GCC of all things would use less pathological primitives <samplet>You are right: you can make a decent Lisp that way. <matrix_bridge><Jeremiah Orians> Oh yeah; C compilers that support the C standards are insane beasts because the standards are insane <matrix_bridge><Jeremiah Orians> If you told me that jumbo jets full of drugs were involved in the creation of any of the C standards; I honestly would not doubt it because that shit is crazy. <matrix_bridge><Jeremiah Orians> Any compiler that fully supports a C standard is going to have to include some insane things <matrix_bridge><Jeremiah Orians> It is why I wish there was a minimal C language standard that could be on a single sheet of paper. <notgull>Idk I think cproc is fairly well put together <matrix_bridge><Jeremiah Orians> I don’t deny the excellent work involved in those compilers and the skill needed in their implementations <matrix_bridge><Jeremiah Orians> I just recognize the insanity of trigraphs <matrix_bridge><Jeremiah Orians> The insanity that C macro support is supposed to be recursively implemented such that one could play Tetris in their compiler by compiling C file. <xentrac>I feel like a minimal version of C would need static types, functions with arguments, globals, locals, for, if/else, arithmetic, arrays, pointers, chars, and ints, at least, and maybe structs. Does that sound familiar? I'm not sure you can define that on one sheet of paper, even if you use S-expression syntax <notgull>You know, since C macros are monads that makes C a functional langauage <matrix_bridge><Jeremiah Orians> You don’t need static types and structs are really trivial <mwette>IMO, a minimal C would have no function preprocessor macros, no typedef, no bitfields. <matrix_bridge><Jeremiah Orians> As static variables are just global variables with restricted access scopes. <mwette>None of the oddball struct array declarations (e.g., [], [*], ...) that noone uses. <matrix_bridge><Jeremiah Orians> No need for static initialization for arrays or structs either <xentrac>do you mean that structs are trivial to implement? They add a lot of expressivity to the language, I think <matrix_bridge><Jeremiah Orians> Less than 20 lines of assembly to implement struct support in cc_x86 <xentrac>by "static types" I didn't mean declarations like `static int n;`, which I agree are not central. I meant the fact that the compiler can assign a type at compile time to every expression. <xentrac>the antonym here is "dynamic types", as in Lisp, where the running program can assign a type at runtime to every value, but that type can't necessarily be determined from looking at the program text <mwette>Is that 20 lines without bitfields? <notgull>Minimal C would be like Golang but without the pathological runtime <xentrac>"static" vs. "dynamic" here refers to the distinction between the static source code and the dynamic running process of the program <xentrac>my claim here is that the statically-typed nature of C is in some sense central to its essence <matrix_bridge><Jeremiah Orians> Well type information about function returns is not actually central to it’s essence as one could implement a compiler that doesn’t even look or care about that type information and it would work fine <notgull>I think you could get away with something like B, where everything is an int or a pointer <matrix_bridge><Jeremiah Orians> It is why M2-Planet has raw FUNCTION types that can be passed to functions that don’t carry any argument or return information <matrix_bridge><Jeremiah Orians> Well the minimal types required would be int, unsigned, char. <matrix_bridge><Jeremiah Orians> Then structs and arrays of them and pointers to structs and char arrays <xentrac>in B there was no distinction between ints and pointers, and it didn't have chars <xentrac>which made sense on the 18-bit word-addressed PDP-7 where it was born <xentrac>the hardware didn't support char pointers <matrix_bridge><Jeremiah Orians> But you need a pointer to an int array or a struct array if you end up wanting to use malloc/calloc <mwette>Would removing pointers create problems with auditing code? <xentrac>C doesn't generally use pointers to arrays when it takes pointers to arrays <xentrac>instead it uses pointers to the element type of the array <xentrac>so you don't really need pointers to char arrays; you could have just pointers to chars <matrix_bridge><Jeremiah Orians> argv and envp require pointer support in C <xentrac>pointers are generally somewhat more type-safe than not having pointers <matrix_bridge><Jeremiah Orians> enums (or cc_* style CONSTANT statements) definitely are needed by standard C libraries <xentrac>yes, but that's getting outside of the goal of a C you can write on one piece of paper <xentrac>lots of things in standard C libraries are needed by things that wont' fit on that sheet of paper, not just enums <xentrac>you do probably want to have some way to define compile-time constants though. otherwise you'll end up using a preprocessor <xentrac>the alternative to pointers is that there's some humongous array somewhere of things of a given type, and you pass around ints that your callee understands as indices into that array <xentrac>or maybe multiple parallel arrays, one for each struct field ("struct of arrays") <matrix_bridge><Jeremiah Orians> Although CONSTANT statements are pretty trivial: CONSTANT name value or CONSTANT name sizeof(type) <xentrac>at that point any kind of type safety goes out the window, and code becomes significantly more difficult to audit <matrix_bridge><Jeremiah Orians> C is not a type safe language. One can redefine what int and char mean <xentrac>there are different levels of type safety <xentrac>certainly C doesn't aspire to soundness, but its type system can still catch a large fraction of programming errors <xentrac>speaking of compile-time constants, one of the things Faré considered for his TUNES project was actually m4, which is just a Turing-complete macro preprocessor. It has quite a large strength-to-weight ratio but it's ridiculously bug-prone and eventually he decided it had been a terrible, stupid idea <xentrac>m4's predecessor m6 was actually somewhat less terrible <matrix_bridge><Jeremiah Orians> Honestly I think once you get into macros. It is probably time to pick up a language that is better than C <matrix_bridge><Jeremiah Orians> Because C macros are terrible and other macro languages generating C code are either ad-hoc and terrible or already abandoned the idea of writing that program in C <notgull>S tier is Lisp, A tier is Rust, D tier is C <xentrac>Historically I think the preprocessor was a fantastic idea because it allowed you to get a much more powerful language running on a PDP-11, where the whole address space was just 65536 bytes <matrix_bridge><Jeremiah Orians> #ifdef variable is fine for dealing with compiler differences and library differences but once you get past that; abandon all hope. <notgull>Once I wrote a library where I used the C preprocessor with JavaScript <xentrac>well, also macros with parameters are good for abstracting over data structures, like in Nethack, where there are macros to define monster types, treasure types, etc. <xentrac>I wrote some X-macros once that let you define a binary record type along with a struct type to hold its deserialized values, and serialization and deserialization code <xentrac>that kind of thing is often in the critical performance loop of a networked program, and writing the code by hand is very boring and error-prone <matrix_bridge><Jeremiah Orians> Don’t get me wrong; I am certain that every single C preprocessing feature is useful to someone/something. I just don’t think any of them belong in a minimal C subset. <xentrac>but I think the C preprocessor was probably the wrong feature for that <xentrac>but on the PDP-11, the C preprocessor gave you inline functions, compile-time constants, a crude sort of module system that let you share your data dictionaries between .c files, and conditional compilation, which is a lot of powerful language features for adding zero bytes to the compiler's executable size (since the preprocessor ran as a separate process) <xentrac>also there is a parametrically polymorphic library of C data structures such as red-black trees and hash tables written in the C preprocessor whose name I forget. zero-overhead abstraction and parametric polymorphism <xentrac>again, though, that's kind of a questionable use for the preprocessor in my view <matrix_bridge><Jeremiah Orians> No denying its value and the level of brilliance involved given the resource constraints of its time. But I don’t think it is a good foundation for a clean standard. <xentrac>and it was something of a questionable decision even at the time <xentrac>I mean a lot of people did question it :-) <xentrac>anyway, back to "what would C on a single sheet of paper look like", if you're sacrificing the ability to compile any existing C, it might make sense to reshape the grammar a little bit in the direction of Golang to make it easier to parse, since the parser is a significant piece of a tiny compiler <xentrac>ACTION verifies that it is human in order to read the paper <matrix_bridge><Jeremiah Orians> Well minimal subsets still have to be valid C; such that existing C compilers don’t need to be modified to comply <xentrac>oh, that's a different constraint. that probably means you have to suffer the cost of C's hairy parsing <matrix_bridge><Jeremiah Orians> To a degree but as you can see in M2-Planet it just requires an ugly function callback stack to support <notgull>cproc currently just straight up doesn’t implement it <matrix_bridge><Jeremiah Orians> if I were to do an ideal bootstrapping language. It would be a typed S-expression language with type pattern matching and no baked in types <mwette>If you eliminate typedef, C becomes context-free. That would help. I believe typedef could be replaced by plain macros: #define foo_t struct foo <matrix_bridge><Jeremiah Orians> The only baked in bits would be (define name thing) (let name value) (if condition true-statement false-statement) (asm block) such that one had to write (define (+ a :int b :int) (asm “load r0 [sp+4]” “load r1 [sp+8]” “add r0 r1”)) <matrix_bridge><Jeremiah Orians> Then pattern matching would allow following code to write (+ 1 1) <matrix_bridge><Jeremiah Orians> One could probably add (loop statement) and (return) and (return variable) <matrix_bridge><Jeremiah Orians> Although I think I skipped the type annotation on the function definition >.< <matrix_bridge><Jeremiah Orians> Unfortunately I know such a language would be terrible to use and absolutely no one would ever prefer to use it <matrix_bridge><Jeremiah Orians> As it quickly becomes a porting nightmare and a halfway point between C and assembly <matrix_bridge><Jeremiah Orians> and ultimately I keep getting stuck on it because of how simple it is and the only non-portable parts are library bits that are relatively straightforward <matrix_bridge><Jeremiah Orians> And then I look at things like forsp and can’t help but think that might be simpler <matrix_bridge><Jeremiah Orians> But there is definitely an excellent high level language that exists below the complexity of cc_x86 to be found. I just don’t know what it is yet. <notgull>I was considering building on RetroForth to see if I could get to somewhere that I could get to something that could implement a LALR parser and therefore C <notgull>Unfortunately it sucks to write Forth, even in good dialects <matrix_bridge><Jeremiah Orians> Yeah FORTH keeps showing up because it can be implemented in under 510 bytes but it somehow becomes harder to write big programs in than it is hard to write big program in assembly <notgull>I think it’s a weakness of most Forth dialects. In my experience I’ve been able to get OOP stuff up and running in Forth <matrix_bridge><Jeremiah Orians> Someone once did a C in FORTH (it only supported ints and single letter variables) and it ended up being longer than cc_x86 <xentrac>the problem with Forth is that it tempts you to be tricky, I think <xentrac>like the C preprocessor, but more so <xentrac>what do you mean by "type pattern matching"? <xentrac>I think you might be able to get the S-expression language to be significantly more usable if you relax the grammar constraints slightly. have a few different nonterminals instead of just one, so the grammar is maybe five or ten lines instead of three <matrix_bridge><Jeremiah Orians> As in there can be an infinite number of functions with the exact same name but the arguments can be different types and there could be a different return type. <xentrac>notgull: I eventually got to where I could write Forth about half as fast as I could write C <xentrac>by virtue of resisting the temptation to be clever <xentrac>I don't think Forth will ever be as readable as C for me, and by leaving so much implicit, I think it does actually have some drawbacks in readability compared to assembly <matrix_bridge><Jeremiah Orians> Kinda but with nothing being there prior to the type specific implementation and the last definition prior to use taking priority