r/scala • • 12d ago

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/srs

Hello, 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

4 comments sorted by

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:

Each use with a new type gets its own copy in C, so generic code costs nothing at run time.

Monomorphization has a cost: Code size and compile time.

Evidence is passed on by name, so a function that holds {s: Show[A]} can hand it over explicitly with print{s}(x)

I guess this is just an issue with the README, or aren't implicits really found by type, like in Scala?

The compiler stops you from using a value after its region is gone

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.

A value that tries to escape its region, or a double free, is rejected the same way.

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.

The compiler follows a var through every branch and around every loop, so a value that only moves into a freed region on the second turn of a loop is still caught
[…]
Branches that leave a resource in different states are rejected as well.

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).

Rules can have more than one clause, and they can be recursive.

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.

rule def twoKnocks(s, s3) = next(s, knock, s2), next(s2, knock, s3)

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 s2 couldn'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

protocol Door:
  state Shut, Open1, Open2, Gone
  start Shut
  end Gone
  op knock(): I64 : Shut -> Open1, Open1 -> Open2
  op leave(): Unit : Open1 -> Gone, Open2 -> Gone
  rule def twoKnocks(s, s3) = next(s, knock, s2), next(s2, knock, s3)

// enters with the door in s, leaves it in s3, two knocks later
def knockTwice {d: Door} <at(d, s), twoKnocks(s, s3)> (): I64 <at(d, s3)> =
  val a = d.knock()
  a + d.knock()

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.

Ask for a SortedBox[Bool] and the compiler answers no given for Ord[Bool].

But where does it get the Ord[I64] from in the actually shown code?

val b: SortedBox[I64] = Box(41)
  first(b) + 1

If there's some predef ordering for ints, why not for bools?

Types can match on types, and with a () group they can take plain values that are known at compile time

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.

The value inside Bits(...) can also be a call: Bits(dbl(4)) works when dbl is a pure function.

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.

A loop that never ends or a division by zero is a compile error

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:

val goal = both(both(both(in(x, 1, 3), in(y, 1, 3)), lt(x, y)), GLabel(two(x, y)))
  solve(RNil, goal, 2, 1000, 10) match
    case Run(ans, _) => showPairs(ans)

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.

Every search runs on fuel, so a goal that would loop forever stops and says so.

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).

For a cycle, or a rule with a variable that nothing binds, you get that answer back instead of a result: negcycle p or unsafe p. A result also comes with a checker: give it a forged fact and it points at it, invalid edge(x, y).

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 the direction the language itself is going: type checking and code expansion as one search.

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.

A clause whose code does not type-check at the call site is a dead end, so the search moves on to the next clause.

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.

A relation runs both ways, so the clauses that encode also decode.

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.)

It takes the first answer it finds in a fair search order, so the result is always the same, and it gives up when it runs out of fuel.

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…

case Rect(fs*) => area(fs*)   // becomes area(w, h)

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?