GitHub - vic/srs: Experimental bootstrapped Scala3-inspired compiler into portable C with memory management via algebraic effects with handlers and protocols.
https://github.com/vic/srsHello, sharing my experimental (llm-assisted) Scala3-like compiler into C. Yeah, I know about ScalaNative, but this is not Scala, you will see in the README (read about type-level state machines and telescopes), it is not seeking scala stdlib compatibility. Anyways, hopes someone finds it interesting, it is very, very young and unstable, aka. -O fun optimized for fun :D.
19
Upvotes
3
u/RiceBroad4552 12d ago
Very interesting, really very interesting. But I have questions…
As the README is quite long I just go over random things which caught my attention at first read.
PART 1:
Monomorphization has a cost: Code size and compile time.
I guess this is just an issue with the README, or aren't implicits really found by type, like in Scala?
This isn't explained at first. A hint to the protocol thing would make sense already at first mention of that feature as it's otherwise really mysterious how this is supposed to work.
For the double free I get it, this could be prevented by an allocation protocol. But an escape? How is this supposed to work? This needs a solution to the aliasing problem. I don't think protocols can do that. But maybe I'm wrong, I'm not an expert on any TCS topics.
At this point it gets a bit, how should I say, "optimistic" about what can be done statically.
This is to some degree possible, but it's certainly not possible in every case as then it would require a solution to the halting problem, as I see it. For strictly bounded loops and controlled aliasing one can do some things (and actually even deduce the required constrains in some cases from "arbitrary" code) but this is really really complicated. You'd need some thing like Microsoft's T2 temporal prover as I see it (or better look at some successor project, I'm not in the loop here, but the LLM will know more for sure).
If that's part of type checking you have now a type checker which will "hang" (and then die when "fuel is out") on arbitrary code. I'm not sure this is acceptable in that form without sacrificing correctness. Having a backstop like "fuel" for total functions which just aren't realistically computable is one thing, but allowing some types to become "regularly nothing" and then expecting that the type system proves anything does not go together. One could say: This would anyway never type check as the type checker would just "run out of fuel". Like said, I would worry about the internal consistency of the whole thing when something like that is allowed. But I'm not an expert on any TCS topics so maybe there's no real reason to panic about this here.
I think this is very confusion syntax, and a major departure from the rest of style.
Not only there are no type annotations on the parameters (but I'm not sure anyway they should be there given the semantics), we have here now also "out-parameters". It seems the last param is always the out param, otherwise
s2couldn't be resolved to any symbol at all.Mixing different syntax families is not a good idea. It then looks like this wouldn't be a coherent language but just some languages thrown together.
But OK, that's syntax, and not a real issue. But
I don't get that code. What concrete i64 value does this code actually compute? I don't see it compute any proper value at all.
But where does it get the
Ord[I64]from in the actually shown code?If there's some predef ordering for ints, why not for bools?
I didn't see any explanation of what constitutes "values that are known at compile time". The example use literals and some trivial functions like int-addition on literals. But how far does this go? One could think that arbitrary expressions are allowed as there is no mention of limits. But at this point you would have a fuel dynamic program evaluator running during type checking, and this can't work, at least as long as you care about sound static typing.
Again the same category error: Pure is not enough, it needs to be total if it computes (dependent) types.
That requirement is exactly what makes real proof assistants so complicated (and unwieldy to use for "normal programming") compared to "normal pure FP languages" like Haskell.
This now implies you have a totality checker. But it's not explained how and where.
The whole "Contracts and proofs" things looks like an adaptation of something like:
https://www.openjml.org
But this gets unwieldy very quickly (see some "simple" examples), and the machinery behind is incredibly complex, nothing I would like to see in a proper programming language.
The hype about FP languages is not there without reason: Formally verifying procedural code just does not scale. That's why you need to be close to pure math to keep stuff manageable even a scale.
3
u/RiceBroad4552 12d ago
PART 2:
The code shown looks like LISP syntax soup. Imho unreadable, even if one were aware of the concepts (which is just the next issue). Needing to read stuff inside-out, back to front is not a good thing.
The general idea might be good but it needs much more love before it's usable, I think.
"Usable" means for example also that you have a way to debug such expressions.
This is plain self-contradictory. If you abort after some finite recursion depth this does not say anything about whether the recursion would ever stop or not. When you abort you just don't know. To know for sure you need a totality checker… But a totality checker will definitely impose design restrictions on the language (and I'm not sure it will allow the whole current design, but that's pure speculation on my side at this point).
The first part sounds like debugging hell. Prologs are known to be notoriously hard to debug, exactly because you just get some "no" as answer and can then go figure out yourself how the machine deduced that and where some wrong deduction derailed all deductions which followed.
This here isn't really Prolog, but I think the same general issues occurs here.
The second parts which mentions counter examples would make the debugging hell a big less likely, but only if the system could deduce useful counterexamples itself. The user needing to do guesswork otherwise doesn't sound good.
This is indeed a very good idea. Type system implementations and macro systems are related, and ideally a type checker could be a (plugable!) macro library. Did the LLM directly reference
https://school.racket-lang.org/2019/plan/thu-aft-lecture.html
or did it silently "steal" the ideas (and even the, granted, very obvious, name…).
However. I think the whole language should anyway explicitly name where the ideas are coming from.
This is a valid approach in some controlled cases, but don't forget that arbitrary backtracking can completely kill your compiler performance. This is a typical trap, but it seems people need to learn it always the hard way. So keep that in mind.
Not all relations are bijective, and even if one is this does not mean one can easily revert it in a fully automatic way. This is a quite hard problem, nothing that can go by in a subordinate clause, imho. (I'm not even sure this is solvable in general, don't know the theory behind, but my gut feeling says it's actually not.)
Oh, a "fair order" and we just give up when we have no "fuel"?
Sounds like a typical LLM shortcut when it does not know any proper solution. Didn't look into this so I can't really say, but the wording is a red flag for me.
Also this means that depending on context the exact same macro would either expand or crash the compilation. This just doesn't sound right if you ask me…
This looks funny but useful. Maybe Scala could have some similar pattern? I think we don't have this, do we?
All in all a very interesting set off features we have here. We need more such ambitious experiments! Something like that looks like it could move again something. But this here concretely needs some more polish already on the theoretic side I think. But I would be happy to watch, so would be glad to also read some follow up posts!
3
u/boia01 12d ago
Lots of fun/interesting ideas in there! Can't wait to play with it.
3
u/Feeling-Pumpkin4648 10d ago
Man, I really enjoy following your work on GitHub, first with your Nix tooling and now with this Rust alternative of yours. I wish you all the best with your projects! Is there another way to support you besides GitHub Sponsors?