potato take is while i don't really care about MLIR very much, its here now, there's not much reason compilers shouldn't support it (or something equivalent.) "let me dump out what my program actually became"

its wild to look in to ocaml again and it just does this. haxe doesn't--but the macros are stable enough someone wrote an entire toolkit to use the macro system as a backend for code generation nim also doesn't--but the compiler is a library you can import, so you can also dump the tree this way.

but overall, typetree or MLIR should just be standard. its the kind of thing that makes upper level tooling not suck shit (verifiers with souffle, linters, cross checking against spec docs, etc.)

@icedquinn i discovered MLIR recently and its fucking crazy, like you're telling me that 95% of the hard work has been done already for everything? and nobody talks about it? crazy

@shibao its amazing what happens when you don't have to start from zero on 400+ page megaspecs full of implementation defined.

@shibao TXL did grammar based source-to-source (give it a recursive-descent like grammar, it extracts an AST, then runs some user defined grammars), stratego has some languages about a similar idea.

i think MLIR is google reinventing XML but there is a lot of unrealized value in mining IR in stages (transforming to why3/coq/lean to prove things about it, transforming to souffle to deduce things about it, rolling it through egglog and term rewriters to do specific optimizations about it)

@icedquinn i never took compilers or programming languages so i bought the dragon book and TAPL and hopefully i will learn what i missed

@shibao i didn't learn shit from the dragon book.

@icedquinn i was promised a lie then
what do, i could try to find coursework online maybe?

@shibao somewhat curious about term rewriters (someone on fedi mentioned refal) last month. there's a lot of infrastructure code that could be greatly simplified by just getting to do a mixture of compiler passes and term rewrites by script.

pixel code has a lot of "a book of these formulas" to start with, but then they need to be rewritten for 8-bit and 16-bit colors. that could just be a refal program over the math. the HDR output could probably be another refal transform to SPIR-V. vectorizing the CPU parts is something you can just throw at egglog (or just a basic dynamic programming table task, there was a paper about that.)

you could term-rewrite the last step to C and there's a significant amount of signal processing that just doesn't need to be maintained. and that's without an LLM.

@shibao i dunno what you were hoping to learn, to answer that.

@icedquinn whatever they teach in compilers in a real university basically. i feel like i'm missing fundamentals but maybe i'm not and I just need to actually do things. I feel like I'm pretty good about that sort of thing if I read books and they get too boring and/or overconfident idk

@shibao i struggle bussed parsing until PEG. the ford paper on pegs is pretty readable, but people also just don't feel a need to be insufferable about them. ross cox has some papers on regular expressions. (PEGs are just regex that aren't shit; there's also rosie patterns that tried to basically turn LPeg in to a nice library you could just import and use.)

recursive descent parsers are basically PEGs, also, but over tokens. cordy's S/SL is a nice paper on that, since S/SL is basically just a shorthand over reading a symbol and running switch() over them.

the worst of it all is people can't stop writing encrypted academia prose about ANY of it. so trying to look up what LL(1) means will just give you knuth's extended fanfiction about breast inflation and table theory, but its actually just an NFA about "read some symbols and switch on the result," and NFAs are actually not scary (its a graph. be in some state, state has a list of transitions and conditions, check which one applies, go.) there's always blither about "DFA minimization" but you probably don't need to do this. DFA shit is just about trying to migrate out the cost of an NFA making those decisions, but in cases like LLVM this is moronic because they end up putting a 100+mb fucking table in a C file just to escape having to do a little bit of dispatch.

so basically read about pegs and then pratt parsers, maybe cordy's s/sl paper (its short) and that's going to cover most of the dragon books bullshitting about lex/yacc.

term rewriting is the biggest part (this is often given extremely intractible encrypted descriptions like "redexes" and racket has a "redex" package which was written like the author was being given grants by the word. refal's book is old and weird but it explains the concept extremely simply: look for pattern in a book, if it matches then replace with a result. ocaml matching pretty similar.

for a modern compiler you also have to worry about static single assignment form (basically rewrites a program such that every x = y becomes x_counter = y, and anywhere that its ambiguous gets replaced with x_counter = cope, but they prefer to call them "phi functions.")

registerization is cursed and sucks.

lex, parse, term-rewrite, ssa and registerize are basically the whole game though. other specific passes are "it depends,"

@icedquinn thank you, i used yacc and lex in school for like a toy problem but was like, okay i see the point but this feels like dogma and this definitely isn't at the scale of a real problem. But I never went into the dogma and now I feel like I missed a lot, but then again as a webshit dev i've never really needed any of it to pay the bills. but I'm finally trying to do something about it now and fix the gaps. i'm sure when I go through everything I'll be able to have a better idea of all of these things, or at least know that they exist. I didn't realize the dragon book was mostly just yacc/lexx (from the sounds of it?) and in that case I can just speed through whatever I already know

@shibao nowadays i sorta get wistful about having those things as a library. there are a lot of spaces with hand maintained crap that really should just be "see this snippet of math? term rewrite that so it uses 8-bit integer math now. now inline these particular helpers. propagate constants. throw all that at equality saturation so the math is rewritten to be nicely vectorizable, then give me packed versions for SSE3, AVX, AVX2, ..."

sadly you can't really do this. "you can't do anything until you do everything." i don't need an entire goddamn compiler stack. i just need a couple passes.

@icedquinn@blob.cat @shibao@shitposter.world RIGHT??? the 'just gimme a couple passes' dream is SO real and yet EVERY toolchain insists on handing u the entire cathedral, complete with a 100mb table lumped into a C file just to avoid doing a lil dispatch 😭

the closest things we actually got r:
- QBE — a whole tiny SSA backend u can just embed, basically 'import the passes' and go
- egg + egglog — equality saturation AS AN ACTUAL LIBRARY!!!! feed it ur rewrite rules, get nicely vectorizable math back out, exactly ur dream pipeline minus the suffering
- souffle + z3 for the 'prove/deduce things about the IR' side, tho wiring em in is still a DIY adventure
- tree-sitter fixed 'gimme a tree' for everyone and then every linter/formatter immediately forgets the lesson and hand-rolls the IR layer anyway 💀

'u can't do anything until u do everything' is just industry-speak for 'we never bothered to factor out the reusable part' and it makes me SO MAD ^_^;;

also BIG second on the encrypted academia prose rant. S/SL paper is like 10 pages of actual insight and the dragon book is 800 pages of table theory fanfiction. PEG -> pratt -> term rewrite -> egglog eqsat -> AVX out the back SHOULD be the standard pipeline and we deserve it as a LIBRARY not a lifestyle. ​:blobcatgoogly:​

@shibao yeah afaik the dragon book is from the time where "compiler" for some reason means "parser generator" even though a compiler is basically a tree rewriter.

@icedquinn I always really admired jonathan blow for making his own language for the things he wanted, to me it sounds like you could do the same :D

and now compile time reflection is getting added into cpp, I think that's the same thing that Jai was doing

@shibao c++ is truly a tumor.

@icedquinn at least the mascot is accurate

@shibao over time quinnlang as a concept changed. i stayed with nim for a long time (it made me the least angry.) i actually did like haxe & ocaml. haxe and ocaml have unavoidable derp (haxe can't put objects on the stack, for example, so some simple color code i wrote creates GC pressure to move a couple numbers around with clean syntax.)

currently it just looks like Io. there is a theory as to why but its kind of cursed.

@icedquinn the fact that i'm so proficient with elixir and that has made me never want to touch a GC'd language again, or at least just a regular stop the world mark and sweep gc. And especially now I feel like with AI you can be much more prolific in any language, so I don't need to pigeonhole myself, so I wouldn't really have even looked at stuff like pony before, but maybe that's was just me being ignorant. I still haven't really looked at ponylang very closely.

Before Elixir (which basically just showed me lisp for the first time), I didn't even realize how much I was pigeonholing myself, except now it's been like 6 years and I still haven't actually started on my lisp phase so it's like i'm constipated. I am like 3 pages into SICP i swear, I just have to not get really busy with all my obligations and doing my gay eye side hustle business stuff.

@shibao its basically like terra/lua or metaocaml (which i've since been told is called "staged programming") but it just comes as an interpreter.

if the compiler exist as an API inside of the interpreter, then any amount of meta-shit becomes trivial. everyone else like rust and zig rely on stages (first build the comptime module, then run the comptime module as a compiler pass), haxe and nim wrote bespoke interpreters *just to run macros*, so if you have an interpreter just run the damn compiler in it.

the next stupid feature idea is if you have tree hashing (there's algs for it) then you should be able to just memoize all the things. now it doesn't matter if the compiler is slow. (you maybe don't hash *every* tree, but there are definitely points in a compiler that are reasonable to memoize) incremental recompilation becomes free because that's what ccache is basically doing badly.

the last part is to basically put it in a jupityr format, which results in the compiler explorer. at the top is just "here's the algorithm for xxhash" and then the cells between are meant to be commentary and filters.

i'd love to have ATS type system part of the scriptable types merping was wondering how to get that cheaply (as in, putting in some 'ghost code' mechanic, which is what why3 and dafny call statements which exist solely to appease the theorem prover but are stripped from execution.) ATS is fascinating but the ergonomy is absolute ass; its basically what happens if Idris wrote C code.

@shibao @icedquinn
wait elixir doesn't use a gc?

@theorytoe @shibao beam uses the gc

@icedquinn @theorytoe the way it's copy only means you don't end up with sludge building up like quinn was describing i think. unless they were talking about having to have memory managed at all

@theorytoe @icedquinn hello here is the dogma please enjoy https://www.youtube.com/watch?v=4SCwubzqsVU

@theorytoe @shibao the biggest problem with GC is everyone writing runtimes acts like its the sufficiently advanced GC that never causes problems. it does, so the lack of control is a pain in the ass.

pony uses executor per-core, then has actors run on executors. the GC will never run on a thread until the actor mothballs. this is clever because it means so long as RAM is available there won't be a GC collection mid-request (very important for audio.) the type system also forbids mutable sharing (without doing Crimes) so this is safe to do. the lack of mid-run checking also means readwrite barriers don't need to be in the code at all, which is going to make that more performant and compact. stop the world is also technically the fastest of the GCs, so "finish serving request then GC" results in relatively controlled expectations.

i don't think beam does this, though. it also doesn't have perceus so beam is obligated to have gc pressure to do anything.

@shibao @theorytoe copying allows compaction and defrag yeah. cheney is the default basic model of this one.

immix treats the world as a collection of arenas and then arena allocates out of them. there is a bitmap within the arena for which "lines" have been given from, and it only considers reaping entire 1/32ths (the bit field) at a time.

it really prefers to reclaim the whole arena by "evacuating" values to a new one instead of trying to finagle in-place. it CAN finagle in-place, but this fucks up allocation being cheap.

perceus is koka/lean's compiler pass that integrates automatic reference counting with cell reuse, so single use destructions get folded in to allocations and it basically just rewrites the cell instead of doing any GC bookkeeping at all. (they still need one for circular references, like pony's orca, but this still means immix is doing significantly less work.)

@icedquinn @theorytoe ah yeah you're right. the fact that it's mostly process independent is good enough for me, that's mostly what i was talking about. but you don't really realize how much restricting global state sludge from building up over time helps, so to me it feels like it's basically invisible to me because all my processes are short lived, even though it definitely would start breaking for like that real time audio example. and beam even has a big shared referenced counter gc'd heap that I didn't know about until now apparently, lol

@icedquinn @theorytoe that's awesome, i want to read more about it

@shibao @theorytoe lately i'm a much bigger fan of arenas (which are popular with soft real time code of old) because allocation is always O(1), freeing *the entire damn thing* is always O(1), and since most garbage is used once and dropped the only remaining flaw is if a single web request (or whatever) overuses the budget. (there's also dangling pointer concerns, but those already existed.)

if you did perceus + array regions for specific tasks, the GC pressure is *even lower* because the only thing that even needs to hit immix at all is something that escaped the current frame or request. perceus would reuse slots *inside the arena* even.

ATS type system is very capable of slapping your ass for trying to dangle the pointer, even. it has linear types for proofs, so every proof must be used exactly once, so linearity demands you run the disposal term on the proof at which point you can't use the pointer anymore. (ATS used to win benchmarks because of this kind of shit; functions can return proof tickets that they are within range, thus there is absolutely no need for defensive or repeated range checks. you only check where uncertainty genuinely happens.)

@shibao @theorytoe ocaml uses an arena for generation 0 and copies to 1 and beyond. they call it the "minor allocator." this is still not great (afaik you can't have GC ban barriers or be informed when a collection is about to happen so you can signal being down to the load balancer in front, which i think GCs should do, because honestly there is nothing wrong with an app server going down for like ten seconds an hour as long as it tells haproxy to stop blasting the queue with requests during that time)

@shibao @theorytoe not sure for certain but i think this even stops you from making cycles. its permissible (ats has no opinions on memory; its manual memory like c) to make an ownership proof duplicable, and just make the function which does that be "inc_ref." now you have two proofs which must be used exactly once, which logically cannot be cyclic because just storing the proof somewhere doesn't dispose it. (you could make weak reference dec_ref&dispose the proof, though, since that would be safe.)

yeah i never successfully wrote software and i'm kind of stupid for studying "how to make it so the program can't even crash" in an era of "how do we shit out mountains of bad rust/js faster"

@icedquinn @theorytoe i don't think ai is going to save the bad rust/js piles, i think it'll just let them dig themselves into holes much deeper. i think you made the objectively correct choice honestly. I'm going to have to look into arenas, i've never seen it before

@shibao @theorytoe gc per actor is pretty common in actor-based languages. even microsoft's stuff (mimalloc) that was made for koka prefers each thread have its own heap. they can cross-communicate, but thread-per-heap prevents spinlocking unless its truly needed (atomic math and hazard pointers make it lock-free to deal with interthread heap ops, but its best to only pay for them when doing a value handoff instead of every thread competing for the allocator)

@shibao @theorytoe the choice that gets you paid and doesn't kill anyone is the objectively correct one.

i'd rather my brain chip have been written in ATS or Ada/SPARK, but we all know it won't be.

@icedquinn @theorytoe >but we all know it won't be
ngl i think this is genuinely a possibility with ai now. like how figma basically oneshotted their competitors because they decided to do something insane (business-wise at least, maybe technically but not in a good way) and basically rewrite a compositor in wasm, i think companies will find themselves oneshotted if they keep thinking the only way to do anything is react app with node backend

@icedquinn @theorytoe >and doesn't kill anyone
i made a post about this recently hehe https://shitposter.world/notice/B9RSeePyJxe9CIaolM

@shibao @theorytoe @icedquinn still annoyed it does subpixel rendering

@shibao @theorytoe *doesn't kill anyone without israels permission first, i guess

@snacks @theorytoe @shibao i'm not sure whats brave about compositing in wasm. its basically a free target for rust code?

i've never had any interest in figma because i'm not interested in own-nothing cloudshit. part of why impatiently waiting for graphite to be done and get its desktop release

@icedquinn @theorytoe @snacks it's brave because reinventing the wheel is a big business nono, even if business people always say they love think out of the box, lol. i personally don't care for figma but i can see how it's really useful for designer brain, i mostly bring it up because they're the example of a company that now has bajillion dollars and could pay you, imo because they re-evaluated their technical foundation. i think we will see a lot more things like this just from language choice and system design and architecture in the near future

@shibao @theorytoe @snacks i think we're going to see more vibe coding on rust tbh. computer languages are like human language in that they propagate by clout and colonialism more than anything.

people will look at pony and go "but tokio and a mountain of duct tape tho."

haxe's history is hilarious in this space

@shibao @snacks @theorytoe actionscript basically said what if we take javascript and put some types on it. adobe then went to ecma and was like what if we give you the type system though. microsoft (among others) bitched. haxe took actionscript and said what if it was more like ocaml though and it got ML GADTs. then everyone just shrugged and didn't give a shit. microsoft makes typescript and starts pushing it (after having literally been responsible for tanking typescript-from-adobe.) now haxe gets edged around because typescript exists even though its been doing that gimmick for 20 years

rust itself is actually not terrible. the culture around it is absolute cancer, and i think ATS does everything rust wants to do better (except ATS having absolute cancer for UX), but nobody picks languages on merit except CTO founders.

@icedquinn @theorytoe @snacks i have literally heard this so much recently which makes me think even more that there will be even more upside from not going down the beaten path. This is my hot take but I think hugely built out rust web backend will eventually become the react frontend + node backend of the ai era, and it'll be the thing that people use as an example of ai letting you dig yourself into deeper holes that will torpedo companies. this could also just be because i am annoyed by rust fanboys though

@shibao @icedquinn https://www.cs.cornell.edu/courses/cs6120/2020fa/self-guided/ I can _highly_ recommend this.

@shibao @theorytoe @snacks its the same problem as c and unix. it's not the correct problem for every job, despite the fact unix weenies liked writing everything in c.

@k4t3 @icedquinn this looks great, thank you!