Richard Feldman (Feb 03 2025 at 01:38): Richard Feldman (Feb 03 2025 at 01:38):it occurred to me that our interpreter can be faster than a lot of interpreters because it doesn't need to do runtime type checking
Richard Feldman (Feb 03 2025 at 01:38):because we'll already have type-checked it, so we know that if there are any type mismatches, we've already dealt with them at compile time
Brendan Hansknecht (Feb 03 2025 at 01:40):Yes, though we will have to still dispatch on type for at least refcounting
Richard Feldman (Feb 03 2025 at 01:40):oh sure, and also for static dispatch
Brendan Hansknecht (Feb 03 2025 at 01:41):Yeah, and to call zig builtins
Richard Feldman (Feb 03 2025 at 01:41):today, the way we (very often incorrectly) deal with type mismatches in the "I want to run my program anyway even though I know there are type mismatches" scenario is that during the building process, whenever we encounter a canonical IR node and go ask it what its type is, we then notice when its type is "type mismatch" and emit an IR node that's supposed to crash at runtime
Brendan Hansknecht (Feb 03 2025 at 01:41):Well, not dispatch on type, but fill out type specific information for the call
Richard Feldman (Feb 03 2025 at 01:42):in the case where we're not doing a full build, and are instead running an interpreter right after type checking finishes, we aren't doing any more compile-time passes over the canonical IR, so we don't have the same opportunity to detect those type mismatches at compile time
Richard Feldman (Feb 03 2025 at 01:42):one way we could deal with those is to, at runtime, always check every single canonical IR node's type to see if it happens to be a type mismatch, and then crash if so
Richard Feldman (Feb 03 2025 at 01:43):but at that point we're potentially worse off than languages that check types at runtime :sweat_smile:
Richard Feldman (Feb 03 2025 at 01:43):I think there's a much simpler solution
Richard Feldman (Feb 03 2025 at 01:44):every time the type checker hits a type mismatch, in addition to pushing a Problem onto a list (to be reported later), it also pushes a "hey this Variable was a type mismatch" onto a list too
Richard Feldman (Feb 03 2025 at 01:45):then after type-checking is done, if we're going to be interpreting, we have one very quick pass where we go through the list of recorded type mismatches and replace all the canonical IR nodes corresponding to those Variables with crash nodes
Richard Feldman (Feb 03 2025 at 01:45):if the list is empty and there are no type mismatches, this is free
Richard Feldman (Feb 03 2025 at 01:45):if there are type mismatches, then we only pay for however many we actually need to fixup
Richard Feldman (Feb 03 2025 at 01:45):and then at runtime we don't need to check for any type mismatches at all!
Richard Feldman (Feb 03 2025 at 01:47):also, we can make the "get the canonical IR node from the Variable" lookup trivial if we assign variables to be the same number as nodes by default, except for nodes that have multiple variables (in which case we can hand out those extra Variables starting from -1 and decrementing, whereas the canonical IR node IDs would all be 0 or positive)
Brendan Hansknecht (Feb 03 2025 at 01:47):Richard Feldman said:
are instead running an interpreter right after type checking finishes, we aren't doing any more compile-time passes over the canonical IR, so we don't have the same opportunity to detect those type mismatches at compile time
Can you explain this more? In the current pipeline does creating these nodes happen later in the pipeline like after specialization or something?
Richard Feldman (Feb 03 2025 at 01:47):yeah exactly
Richard Feldman (Feb 03 2025 at 01:47):I think it's during specialization actually
Richard Feldman (Feb 03 2025 at 01:48):because we go and look up the type associated with the node to see what its layout is
Richard Feldman (Feb 03 2025 at 01:48):and then if the type is a mismatch, instead of getting a layout we replace it with a crash (in theory, although in practice we mess this up often)
Richard Feldman (Feb 03 2025 at 01:48):I don't think this strategy could be done with other forms of dispatch though
Brendan Hansknecht (Feb 03 2025 at 01:48):In the interpreter, we would instead do it when calling a function (cause we know the concrete types for that call at that point)?
Richard Feldman (Feb 03 2025 at 01:49):it relies on the fact that once we hit a type mismatch in solving, we know it's game over
Richard Feldman (Feb 03 2025 at 01:49):I'm proposing that we do one more pass before we run the interpreter
Richard Feldman (Feb 03 2025 at 01:49):after type checking has completed
Richard Feldman (Feb 03 2025 at 01:50):and in that pass we go fixup some canonical IR nodes
Richard Feldman (Feb 03 2025 at 01:50):to replace them with crash nodes
Richard Feldman (Feb 03 2025 at 01:50):so the interpreter just encounters them and says "oh, a crash, I guess I will crash"
Brendan Hansknecht (Feb 03 2025 at 01:51):How does that work for a function that is called with 4 different specializations?
Brendan Hansknecht (Feb 03 2025 at 01:52):Like each specialization might or might not have the crash
Richard Feldman (Feb 03 2025 at 01:52):they'll all have it for sure
Richard Feldman (Feb 03 2025 at 01:52):type mismatches apply before specializations
Richard Feldman (Feb 03 2025 at 01:52):it's not possible in Roc to have a type mismatch for one specialization but not others
Richard Feldman (Feb 03 2025 at 01:52):like it would happen at the call site
Richard Feldman (Feb 03 2025 at 01:52):either that call site is busted or it isn't
Brendan Hansknecht (Feb 03 2025 at 01:53):Oh, then sounds like in general type checking can just change the the node to a crash?
Richard Feldman (Feb 03 2025 at 01:53):yeah exactly
Brendan Hansknecht (Feb 03 2025 at 01:53):Yeah, sounds reasonable to fold into type checking or a pass right after.
Richard Feldman (Feb 03 2025 at 01:54):yeah I think we'd want to do it right after because:
roc check or editor analysis, fixing up the canonical IR is a waste of time Brendan Hansknecht (Feb 03 2025 at 01:55):What about static dispatch?
Brendan Hansknecht (Feb 03 2025 at 01:55):That would depend on the specific arg type for whether or not it is a crash.
Richard Feldman (Feb 03 2025 at 01:56):static dispatch always resolves to the same type
Richard Feldman (Feb 03 2025 at 01:56):one way to think of it is that
Richard Feldman (Feb 03 2025 at 01:56):if you have a language like Elm or OCaml or Haskell
Richard Feldman (Feb 03 2025 at 01:56):they don't monomorphize, there is no specialization pass
Richard Feldman (Feb 03 2025 at 01:56):but of course they still have type mismatches
Richard Feldman (Feb 03 2025 at 01:57):we have specialization, but there's no such thing as a "specialization error"
Richard Feldman (Feb 03 2025 at 01:57):like we don't report compile-time problems in that pass because all the userspace errors occur before that
Richard Feldman (Feb 03 2025 at 01:57):(I guess we can still have bugs in our compiler implementation though haha)
Richard Feldman (Feb 03 2025 at 01:57):so Elm, Haskell, OCaml, and Roc would all implement this feature in the same way
Brendan Hansknecht (Feb 03 2025 at 01:58):If we have this function
fn: x -> U64 where x.len() -> U64
At one call sight, it might need to crash due to the type being passed in not having .len() and at another it might run just fine, right?
Richard Feldman (Feb 03 2025 at 01:58):yes, but we'd know that after type-checking
Richard Feldman (Feb 03 2025 at 01:58):we wouldn't need to specialize
Richard Feldman (Feb 03 2025 at 01:58):maybe I should clarify that when I say specialize I'm talking about monomorphization
Brendan Hansknecht (Feb 03 2025 at 01:58):But we now have one call site that runs the crash and another call site that doesn't run the crash.
Richard Feldman (Feb 03 2025 at 01:58):there's also function application, which is arguably a form of specialization, but that's not really the term I hear used for that :big_smile:
Richard Feldman (Feb 03 2025 at 01:59):totally!
Richard Feldman (Feb 03 2025 at 01:59):but we have all the info necessary to do that after type-checking
Richard Feldman (Feb 03 2025 at 01:59):we don't need to perform specialization
Richard Feldman (Feb 03 2025 at 01:59):like Haskell literally has this feature haha
Richard Feldman (Feb 03 2025 at 02:00):and they have ad-hoc polymorphism (typeclasses, not static dispatch, but they both look up implementations based on their type)
Richard Feldman (Feb 03 2025 at 02:00):https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/defer_type_errors.html
Brendan Hansknecht (Feb 03 2025 at 02:00):Interesting. I trust you, but I definitely don't understand.
Richard Feldman (Feb 03 2025 at 02:00):fair enough, I don't think I'm doing a good job explaining it :sweat_smile:
Richard Feldman (Feb 03 2025 at 02:00):Ayaz could probably explain it better
Brendan Hansknecht (Feb 03 2025 at 02:00):Oh, I guess you could always generate a .len() that just calls crash for the type that is missing .len()
Richard Feldman (Feb 03 2025 at 02:24):well we'd just crash at the call site
Richard Feldman (Feb 03 2025 at 02:24):like replace the call itself
Richard Feldman (Feb 03 2025 at 02:24):not the function
Richard Feldman (Feb 03 2025 at 02:24):so when you get to the call, instead of calling anything it just crashes
Brendan Hansknecht (Feb 03 2025 at 02:40):main! = ||
x = []
y = "string has no len()"
tmp = fn(x, Bool.true) + fn(y, Bool.false)
z = fn(y, Bool.true)
fn : a, Bool -> U64 where a.len() -> U64
fn = |a, b|
if b then
a.len()
else
0
In the above, the first two calls to fn should pass with no issues. Only on the third call to fn (line with z = ...), it should crash. In this case, the crash should be generated from the line a.len() due to the type of a being a Str.
Joshua Warner (Feb 04 2025 at 05:48):We could/should crash on the second call site because its type is malformed. The type signature doesn’t match the args provided.
Brendan Hansknecht (Feb 04 2025 at 05:50):Yeah, I guess that would be valid.
Last updated: Jul 06 2025 at 12:14 UTC