IRC channel logs
2026-05-21.log
back to list of logs
<siraben>i tried doing graph coloring but it would have added too much complexity to an already-complex C compiler in Haskell :P <xentrac>yeah, register allocation is a pretty high-payoff optimization, but it's definitely for after you're committed to writing an optimizing compiler <matrix_bridge><wildwestrom> Sorry if this has been answered many other times. Why is Forth considered a "dead end" for bootstrapping. I'm in a Discord group with some other programmers, and I talked about the bootstrapping problem. Overwhelmingly I hear them tell me Forth is a great language for this purpose, and they seem really surprised that the current path is just C compiler after C compiler. Personally I find Forth code... <matrix_bridge>... harder to reason about than assembly, but I just chalked it up to me not understanding it. <lanodan>Well… not really a dead-end when CollapseOS seems to have done it via Forth, that said might need to dig a bit more in what they do to really judge if it's a "dead end" or not (doesn't really interests me, seems more ideological than technical so far). <xentrac>I think the "dead end" comment is outdated <Googulator>AFAIK the difficulty is in "escaping" the Forth environment, which necessary if your goal is to bootstrap a "mainstream" OS <xentrac>but basically the issue with Forth is that it sure *feels* like a very promising avenue to bootstrapping (or de-bootstrapping), but most of the people who have tried that avenue haven't been very successful <xentrac>but vdupras has done it since oriansj came to that conclusion, which I think probably merits reconsidering the conclusion <xentrac>I think what happens is that you really can get stuff working in Forth in an astonishingly tiny amount of code, but debugging that code is a slower process than debugging code in more conventional languages. There may also be a familiarity aspect: people are much more familiar with C and its strengths and weaknesses than with Forth's <xentrac>Forth's strengths include things like interactivity and metaprogramming (things like macros and decompilers) but people like me coming from a C background (well, really a Python background) don't think of how to capitalize on those strengths <matrix_bridge><Jeremiah Orians> To be precise. I didn’t say that it couldn’t be done but rather no one bothered to do it yet. And as xentrac rightly pointed out, duskOS did in fact get to M2-Planet parity. <xentrac>yeah, I forget where the "dead end" comment is exactly, if wildwestrom is quoting or paraphrasing <xentrac>its weaknesses include being less readable and more error-prone, though some Forth enthusiasts disagree with me on either or both of those. I argue that Forth lets you make nearly all of the errors you can make in C, and it also doesn't check your parameter passing (and return value passing) or type checking. The only exception I can think of is that sometimes C's implicit coercion rules, <xentrac>especially between signed and unsigned, create opportunities for bugs that don't arise in Forth <xentrac>I think we can make a more precise statement that a Forth bootstrap is feasible and has been done a number of times, mostly back in the 01970s, but is more difficult than it appears at first, or than it appears when you are just looking at the resulting code <matrix_bridge><Jeremiah Orians> Well it was a dead end for me once I wrote cc_x86 and knew how easy it was to write a C compiler in assembly. I spent months on my FORTH interpreter (got it to support a huge chunk of the standard too) but once you get the lambda core of C you can convert basically any C program to work within its limits <xentrac>on https://collapseos.org/forth.html vdupras describes his reasoning for choosing Forth, and his early experience with it: "To be clear: Forth doesn't elegantly describe complex algorithms, at least not when compared to languages like C. Those generally make the head hurt when reading. However, this mental pain does makes you question your need for complexity and encourages "sideways" solutions." <xentrac>but there's a very interesting addendum describing how his perception of Forth changed after more experience <xentrac>"I wrote this page, what, 4 years ago? I'm irked by me writing that C is more expressive than Forth. The thing is that generally, when you write Forth, you write your own language. So it's as expressive as you make it. (...) Today, whenever I write C code, I find the language underpowered. Sure, you can, kind of, build your own language through macros, but seriously, textual-based macros? How <xentrac>blunt! Forth can take you to the next level, macro-wise." <xentrac>(that's a quote from vdupras on that page, just to be clear) <xentrac>which *I* think is sort of flawed! and I'm not clear whether it's been used <xentrac>I've been exploring an alternative approach I call "Qfitzah <xentrac>it's an interpreter for a higher-order programming language with pattern matching, flexible parametrically-polymorphic data containers, and dynamically dispatched method calls with multiple dispatch, written in assembly, and the Linux executable is currently 828 bytes <xentrac>I thought that a language like that might be a better substrate for writing compilers than something like C or Forth, although I have to admit that Qfitzah might be a more compelling platform for compilers if it supported, for example, arithmetic, strings, or arrays <xentrac>all of which are present out of the box in C, Forth, and most assembly languages <xentrac>from a purely computational perspective you can implement them all in Qfitzah, but they might be so inefficient that you wouldn't want to <matrix_bridge><Jeremiah Orians> I have been toying with the idea of committing to creating my own language to fix all the short sighted ideas in C but honestly it will never be elegant <xentrac>I don't know if Qfitzah is the right direction to explore, but it's sort of an indication that there are a lot of possible directions to explore <xentrac>that sounds interesting! I'd be interested to see what you've been thinking! <xentrac>including an implementation of Peano arithmetic <matrix_bridge><Jeremiah Orians> Well it starts with the blasphemy of removing the macro and preprocessing entirely. Adding 3 stacks(return, bound/base, Exception), the CONSTANT keyword and replacing malloc with 3 variants (stack, heap, gc space) <xentrac>for bootstrap purposes you might be able to just leak memory until the compiler terminates <matrix_bridge><Jeremiah Orians> And turning int foo(int a) into define foo as () function (:int a) returns (:int result){…} <xentrac>that sounds like it might be easier to implement but harder to read <matrix_bridge><Jeremiah Orians> Optional gc for only the objects that you want to let gc handle <xentrac>so the output produced by the example.qf1 line (Map (Cover Chocolate) (Cons Police (Cons Raisins (Cons Oreos Nil)))) is: <xentrac>(Cons (Some Chocolate Covered Police) (Cons (Some Chocolate Covered Raisins) (Cons (Some Chocolate Covered Oreos) Nil))) <xentrac>from which you may be able to infer a lot of the structure of the system <matrix_bridge><Jeremiah Orians> Figuring out exactly what is on the variable stack when unwinding exceptions and letting the programmer have access to them if necessary <xentrac>how were you thinking about handling non-GCed heap allocations during exception unwinding? <matrix_bridge><Jeremiah Orians> I was leaving it as an exercise to the programmer, as gc only deals with explicitly gc allocated objects <xentrac>right, and presumably would eventually deallocate GC-allocated objects references to which were dropped by stack unwinding <matrix_bridge><Jeremiah Orians> One could also allocate on the stack to skip the gc overhead and automatically deallocate when the bound/base is popped <matrix_bridge><Jeremiah Orians> And because one is able to write define + (:int8 a) function (:int8 b) returns (:int8 result; :bool overflow) {…} <matrix_bridge><Jeremiah Orians> Then the language doesn’t need more than a handful of keywords <xentrac>right, which is sort of Lispy or Smalltalky <matrix_bridge><Jeremiah Orians> You pattern match on the name and types and you can have a much richer typing and eliminate undefined behavior <matrix_bridge><Jeremiah Orians> You could even define a type like :knight8 which is 8bits long but is in symmetric (not 2s ) complement and thus has 11111111 encoded as NaN <xentrac>much richer typing can be a pain if it imposes more demands on the compiler <matrix_bridge><Jeremiah Orians> Honestly the biggest problem is one basically has to write a huge base module to present a more normal sort of programming experience (otherwise you would have to start by defining types and even the most basic functions like +, -, *,/,% <xentrac>yeah, an 8-bit or 16-bit unboxed representation of what OCaml calls "int option" would be useful surprisingly often, but it's necessarily kind of inefficient, I think even on custom hardware <xentrac>in Java I've used the Integer class for this, although it's sort of made for storing integers in generic containers; it can either be a null or a pointer to a boxed integer <matrix_bridge><Jeremiah Orians> I was really tempted to steal the type syntax from ADA <xentrac>it might be moderately more efficient to use 1000 0000 as the NaN value so you can use regular twos-complement arithmetic without requiring the end-around carry that ones-complement demands. you still need the NaN-case check on the *inputs* of an addition or subtraction but I think that then you can avoid having to add a check to the *outputs* <xentrac>please don't steal anything from Ada D-: <xentrac>I think stealing syntax from Ada is the main reason most logic designers today prefer Verilog to VHDL <xentrac>and the reason my wife is hating her databases class this semester, because Oracle created PL/SQL by adding Ada syntax to SQL <matrix_bridge><Jeremiah Orians> DEFINE :int8 as TYPE BITS(8); doesn’t seem like that bad of a thing <xentrac>the capital letters are already making me think of COBOL <xentrac>but how about `type :int8 is bits(8);`? <xentrac>or `:int8 is type bits(8);` or just `:int8 = type bits(8);`? <xentrac>putting the thing being defined in the left margin is pretty helpful to readability or rather skimmability, although it conflicts with allowing simple recursive-descent parsing without backtracking, which tends to give your language better compiler syntax error messages <xentrac>conceivably if you're going to have tokens that begin with sigils (like Ruby, Perl, and PHP) it might be worthwhile reserving a sigil for types, so you could just write something like `,int8 = ,bits(8)` <matrix_bridge><Jeremiah Orians> Yeah, there are a bunch of trade offs and tweaks and ideas for how to keep it all simple, consistent and ultimately flexible enough to evolve <matrix_bridge><Jeremiah Orians> I keep bouncing between C style syntax and just S-expressions <xentrac>yeah, if you optimize any one aspect, everything else goes to hell <xentrac>an S-expression is either an atom or a cons of an S-expression and an S-expression <xentrac>a rose tree is an atom and an ordered list of zero or more children, which are also rose trees <xentrac>my motivation is that Qfitzah became super awkward with the distinction between Foo and (Foo) <xentrac>Prolog is the most common language based on rose trees <xentrac>I feel like rose trees are almost exactly as simple as S-expressions but maybe more ergonomic in some ways <matrix_bridge><Jeremiah Orians> C with a handful of tweaks would be just as easy to parse as s-expressions <xentrac>I don't see how that could possibly be true! <matrix_bridge><Jeremiah Orians> Most of the complexity is not in the parsing but in the order of operations and the ordering around of a few syntax stumbles <matrix_bridge><Jeremiah Orians> Which is why s-expressions are so tempting. No need to see * and then make sure that the compiler handles it before + <xentrac>I mean the C grammar in K&R is, I forget, three or four pages long. it's going to require more than a handful of tweaks to bring that down to `sexp ::= \s* atomchar+ | \s* "(" sexp* \s* <xentrac>I mean the C grammar in K&R is, I forget, three or four pages long. it's going to require more than a handful of tweaks to bring that down to `sexp ::= \s* atomchar+ | \s* "(" sexp* \s* ")"` <matrix_bridge><Jeremiah Orians> Oh K&R C is just terrible. The C lambda core is tiny <matrix_bridge><Jeremiah Orians> If, else, while, asm, “string”, goto, label: <xentrac>struct, function, variable, call, infix <xentrac>just the syntax of C types is several times bigger than the syntax of S-expressions <xentrac>AwesomeAdam54321: that sounds interesting but it says <xentrac>Your requested paste entry 'edc5cf85' could not be found <matrix_bridge><Jeremiah Orians> xentrac: granted in formal definitions but when implemented in assembly, not so much <xentrac>I don't see how you can get by without at least a few lines of assembly for each production in the grammar, so if you have dozens of productions it is going to be bigger than if you have just, like, three <xentrac>it looks like the C parser here is roughly from line 105 to line 774? <matrix_bridge><Jeremiah Orians> And in_set is a utility function used outside of the parser too <matrix_bridge><Jeremiah Orians> One additional detail that you might have noticed is if + is just a function like all the others; how exactly would order of operations be encoded as users may write a := b+c*d; <xentrac>actually there's quite a bit of parser way down in the file. the while keyword is defined on line 4162 and matched against the input on lines 2317-2318, then the following left paren is checked for at line 2403 <xentrac>well, you could declare that b+c*d is a syntax error so that you have to explicitly write b+(c*d) or (b+c)*d <xentrac>or you could enable user-defined left and right precedences like Prolog does <xentrac>or you could define a simple but error-prone left-to-right or right-to-left ordering like Smalltalk and APL do <xentrac>maybe you mean that the C tokenizer is from lines 290 to 423, and I certainly do agree that a C tokenizer can be only a little more complex than an S-expression parser <xentrac>if you wanted to eliminate control structures like if and while from your grammar, you could extend the function-call syntax to support block arguments (as Ruby and Lobster do) or just make blocks a kind of expression (as Smalltalk and arguably Rust and JS do) <matrix_bridge><Jeremiah Orians> loop{…} and you have to use break or goto to get out <xentrac>that's certainly workable but I question whether it's a good tradeoff. even the first version of Emacs Lisp had while <xentrac>leaving out `do`, especially in early stages, seems justifiable <matrix_bridge><Jeremiah Orians> While(cond){…} is effectively identical to loop{if cond break; …} <xentrac>yes, it is, except that the first one is shorter and much more readable <xentrac>it seems like leaving out `for` simplifies a compiler slightly at a major readability and bug-proneness cost to all the code you compile with it <xentrac>I did this in StoneKnifeForth; the only looping construct was do-while <matrix_bridge><Jeremiah Orians> Well one doesn’t want to just recreate Algol68 with trying to go too far down that road <xentrac>well, and line 344, since nothing else in StoneKnifeForth uses `jnz` <xentrac>it was definitely a better tradeoff in that context than implementing an endless `loop{}` and goto, but part of that is that Forth (even StoneKnifeForth) isn't C <xentrac>so for example the jump destination is pushed on a compile-time stack, so SKF doesn't need a label mechanism <matrix_bridge><Jeremiah Orians> Granted, I can certainly see why people would prefer while,do and for over a spartan endless loop <xentrac>but the loop construct gets used on lines 313, 318, 322, and 394, so even for SKF itself, switching to an even more primitive looping construct could easily make the compiler more complex by imposing more complexity on those four locations <xentrac>I thought do-while was already pretty spartan! <xentrac>if you have enough memory you could omit looping constructs entirely and just use recursio <matrix_bridge><Jeremiah Orians> A c implementation would just be a label and a jump; then a label for the break to jump to <xentrac>assuming you support it, which StoneKnifeForth doesn't <xentrac>well, you need to implement the label and the jump for the loop construct, but then you also need to implement the goto statement, and the whole label mechanism (but maybe you can inherit labels from an assembler or linker) <matrix_bridge><Jeremiah Orians> Break would just be a jump to the second label <xentrac>Clojure has an additional Spartan alternative: its main looping construct is `recur`, which just jumps to the top of the current function <xentrac>(perhaps partly because you can't do tail-call elimination on the JVM) <xentrac>grammatically, the way to outlaw the ambiguous b+c*d is to require the children of an infix-operator expression to be something that binds strictly *more* tightly than an infix-operator expression, such as a parenthesized expression <matrix_bridge><Jeremiah Orians> The label is just a variable that we push and pop off the stack <xentrac>what's the relationship between labels and variables that you push and pop off the stack? <xentrac>I feel like labels are a pretty powerful mechanism; with a single mechanism, sort of, you get (non-reentrant) variables, named subroutines, separate compilation, and a large part of control structures, relieving the compiler of any necessity to backpatch <matrix_bridge><Jeremiah Orians> Break just outputs a jump to the label variable and after the closing } in the while/for loops. You just pop the old value off the stack and assign it to the variable <xentrac>that sounds more like what I'm doing in SKF than it sounds like labels as I understand them ;) <matrix_bridge><Jeremiah Orians> On start of the while/for/do loops; you just push the current variable onto the stack and assign a new label to the variable <matrix_bridge><Jeremiah Orians> Thus break always goes to the right place and is trivial <xentrac>are you emitting an indirect jump instruction that fetches the address to jump to at runtime? I'm not understanding yet, possibly because I don't understand the Knight <xentrac>so you emit a relocation for each break statement, and then the linker goes through those relocations and fixes up all the jump offsets so they go to the end of the loop, where the label was defined? <matrix_bridge><Jeremiah Orians> (As cc_* and M2-Planet output M1 assembly and M1 lets hex2 resolve the labels) <xentrac>I mean that's the conventional label mechanism, but the code you linked to doesn't seem to be iterating over relocations and fixing up jump offsets <matrix_bridge><Jeremiah Orians> No need to relocate or fix up anything if it is always perfect <xentrac>I guess the label mechanism is in hex2? <xentrac>btw, I don't know if you saw what I was saying in here the other day about discrete-logic CPUs? <matrix_bridge><Jeremiah Orians> I did and honestly 100khz is plenty fast enough to get to M2-Planet in about 30 minutes <xentrac>that might depend on how wimpy the instructions are and how many cycles they take <xentrac>when I sketched out Calculus Vaporis down to the gate level, I was surprised to see that while the bit-parallel version was about 1000 NAND gates, going to bit-serial only brought it down to about 600 <xentrac>because each instruction would require 12 clock cycles instead of 4 <xentrac>for a machine with a less cramped word size, such as 16 or 20 bits, the bit-serial slowdown would be greater <matrix_bridge><Jeremiah Orians> Well, people used to hand design CPUs with thousands of gates <xentrac>also making it bit-parallel doesn't actually make the design process take any longer <xentrac>you need 12 or 16 or 32 copies of a certain part of the CPU <xentrac>what takes longer is soldering it together <matrix_bridge><Jeremiah Orians> And even if we went with a 6502 equivalent, we would still be looking at under 9K transistors <xentrac>and tracking down the places where you screwed up <xentrac>another thing to keep in mind is that companies like JLCPCB generally won't want to make you a single instance of a PCB, even a prototype <xentrac>which tends to favor a bit-parallel design <matrix_bridge><Jeremiah Orians> I wouldn’t mind paying for 50 and giving copies away for free <xentrac>do you think you could find funding for me to work on this? <xentrac>yes, it'd be great to have more than one working CPU, but probably the first couple of board spins will have dumb errors that require a respin <matrix_bridge><Jeremiah Orians> I definitely would be willing to donate some money to get progress on the hardware bootstrapping <xentrac>I think success would be much more achievable with something similar to RISC-V than with something similar to Knight <matrix_bridge><Jeremiah Orians> Most likely and there is probably some government funding from the EU available <matrix_bridge><Jeremiah Orians> Turns out the USA threatening to steal Greenland; really super charged funding for projects that would benefit the EU infrastructure being independent and secure against the USA <xentrac>but I think that's probably *too* far <xentrac>I mean I did write some programs for it; it's not *completely* unusable <xentrac>Europe should be able to get their infrastructure independent from the USA and secure against the USA, but China is going to be a lot harder <xentrac>sorry, either Aisler *or* *PCBWay*. PCBWay is the other Chinese PCB maker <matrix_bridge><Jeremiah Orians> Well if we can create a cheap hardware path to military grade trusted software that is fully bootstrapped. Then they might have a chance <xentrac>it's probably worth trying to clarify what defenses would be sufficient for different threat models <xentrac>night before last I went to the L∃∀N meetup in San Francisco (I'm visiting the US, did I mention that?) <xentrac>Lean is maybe one of the more practical proof assistants out there <matrix_bridge><Jeremiah Orians> Well if it gets to defending against molecular assemblers; I vote punt until someone figures out how to disable them and keep them out of our fabrication plants. <matrix_bridge><Jeremiah Orians> Least I get converted into a stack of paper clips. <xentrac>is Mono moribund? Because Ximian abandoned it. Does it have new maintainers, at least to fix security holes? <xentrac>oriansj: you probably need nanobots to defend against nanobots infiltrating your fabrication plant, or to prevent future nanobots from executing a denial of service, but there's a known defense against future nanobots exfiltrating confidential information or forging your attestations <xentrac>you float the computer in a tank of water, equipped with lights and cameras, and power it from outside the tank inductively using a magnetic field <xentrac>it uses active control to stay in the center of the tank <xentrac>if it detects intrusion into the tank or if the power supply fails, it self-destructs by igniting a thermite charge <xentrac>fortunately we don't have to worry about this threat model for at least several months <xentrac>this defense dates back to at least the 90s. Mark S. Miller is the one who told me about it, but I don't know if it's been published <xentrac>however, hardware backdoors and software supply-chain attacks are active threats that are currently very important <xentrac>siraben: right, that's what you said! <siraben>I was just looking at things Guix has bootstraped that we have not bootstrapped yet <siraben>whether or not the language/framework is moribund is no relevance to me! <siraben>Unfortunately the mrustc bootstrap was met with resistance because we can't afford the long bootstrapping time every time we make a change to core packages, and other maintainers said it would lead to bitrot if we included but never exercised it <siraben>e.g. minimal-bootstrap bitrotted many times in nixpkgs until it was part of the core set <matrix_bridge><Jeremiah Orians> I use warzone2100 as my build canary. It is well maintained upstream and Guix only breaks the build if someone made a change and didn’t clean up all impacted packages (and because it is a game, they are more likely to punt on doing the work) <stikonas>yeah, unfortunately maintaining bootstrap chains is a lot of work :(, so I can see why nix might be reluctant <stikonas>I was recently trying to update my gentoo-bootstrap overlay (that has go and openjdk bootstraps) and in 2 months I still haven't fixed everything <stikonas>it builds now on x86_64 with GCC 15 but on aarch64 I have only reached openjdk:8