Sync IR changes

[CAG2Mark]

The trivial changes look fine. However, there is a pain point with LetMethodCall, which from what I know, is used for virtual dispatch.

We definitely want to optimize method calls. For instance, List.map and List.foldLeft, when implemented in a recursive manner, should definitely have the tail-rec (mod cons) optimizations applied. However, the optimization is quite aggressive, in the sense that it needs to analyze the code itself, pluck out certain bits of code, replace them with other things and then possibly merge several functions into one. This is fundamentally incompatible with LetMethodCall, which defers resolving the virtual method calls to a later stage.

Temporary Solution

One temporary solution is to reduce LetMethodCalls to LetCalls when we can resolve the method call at compile-time and throw an error if a LetMethodCall appears inside a @tailrec strongly-connected component of the call graph. Specifically, if

• V <: T,
• foo is a virtual method of T,
• V implements foo,
• x: V implies x.foo resolves to V's implementation of foo (note that if x: W, then W <: V is possible),

then for any x: V, we can resolve x.foo to V's implementation of foo.

Possible Fix

I think the cleanest fix is to scrap LetMethodCall (or only have it in an intermediate processing step and not in the final IR) and implement virtual dispatch in the IR directly. From what I know, we plan to implement a switch statement in the IR which matches the scrutinee in constant time. Either that, or it is directly implemented into the current Case node. In either case, it will be adequately performant.

As an example, if we have

fun bar(x: T, y: Int): Int = x.foo // --#1

trait T {
    fun foo: Int  // --#2
}

class T1 extends T {
    fun foo = bar(this, 0)
}

class T2 extends T {
    fun foo = bar(this, 1)
}

Then we would have any instance of T have an extra parameter clsId. Let's say that T1 has clsId = 1 and T2 has clsId = 2. In the IR, we would then have functions T1_foo(this_: T) and T2_foo(this_: T) as T1 and T2's implementations of foo.

Then x.foo at #1 will be replaced with a call to T_foo_lookup, and #2's "implementation" will be T_foo_dispatch, which would look something like

fun T_foo_dispatch(this_: T, clsId: Int) = switch clsId {
  case 1 => T1_foo(this_)
  case 2 => T2_foo(this_)
}

Now, note that every single function call in the strongly-connected component { bar, T_foo_dispatch, T1_foo and T2_foo } are tail-calls. Therefore, the tailrec optimizer can optimize them into one function.

Of course, this idea is provisional for now and I would like @LPTK's approval before going ahead with either of these ideas, if at all.

[LPTK]

@CAG2Mark Thanks for the comments.

What you're proposing is fine in principle, but it makes a close-world assumption. However, the IR should be able to represent and optimize open-world code, as we won't always have the entire program on hand (modules could even be loaded dynamically), or in other situations we might have the entire program available but global whole-program optimizations might be too expensive (esp. for debug/test builds) if that program is very big.

It's better to cleanly separate these distinct concerns. LetMethodCall is meant to be for those calls we don't resolve statically, either because we can't or because we don't want to analyze/optimize them. If the source method call is to a static or final method, the elaborator or IR lifter might probably change it into a LetCall anyway before it even reaches the IR. Or there might be a separate IR pass that does this change. @tailrec should simply be blind to LetMethodCall and that's fine. It is a reasonable restriction that @tailrec only be specified to handle direct/concrete calls.

I think the cleanest fix is to scrap LetMethodCall (or only have it in an intermediate processing step and not in the final IR) and implement virtual dispatch in the IR directly.

But LetMethodCall is our direct implementation of virtual dispatch already...

What you're proposing here is not a virtual dispatch implementation, it's a defunctionalized (or more specifically "demethodized") representation of it. Defunctionalization is an orthogonal IR transformation pass. Currently we plan to do it only internally to modules/compilation units. Virtual calls across compilation units will remain virtual by default to preserve separate compilation.

Besides, your defunctionalization proposal is not very good as it assumes all call sites have to assume all possible class implementations flow into the receiver. In practice we'll want to base this on a local flow analysis, so that each method call will become a switch of only those classes that can flow there, with possibly a default case resolving to the original virtual call, if unknown implementations may flow there.

[CAG2Mark]

Got it, so now we have a question of semantics: If a function is annotated with @tailrec, and we have an unresolved call, which could possibly recurse back to the annotated function, should we ignore it or should we error?

I suppose the semantics should be the same as calls to anonymous functions (which can be implemented using virtual dispatch anyway) but I don't exactly remember the required semantics of those either.

[LPTK]

Got it, so now we have a question of semantics: If a function is annotated with @tailrec, and we have an unresolved call, which could possibly recurse back to the annotated function, should we ignore it or should we error?

Yes, the intended semantics is to ignore them. Just like in Scala (in fact Scala ignores even more calls, as you know). @tailrec does not guarantee that the same function won't ever be called indirectly in non-tail position. In general it doesn't guarantee that the body won't overflow the stack due to calls to other methods, and for all intents and purposes these indirect calls aren't so different from other methods. Think of a tail-recursive implementation of List.fold(f) and a call that wants to fold sublists as part of f's implementation. We certainly don't want that to be rejected as "not tail-recursive". Doing so would also be anti-modular anyway.

[CAG2Mark]

Got it, the changes should be fairly simple then. I'll suggest them soon.

[LPTK]

I think one important thing to do to make testing the IR more practical is to allow later test blocks to depend on earlier test blocks. This way we could define class True and class False once in text at the beginning of the file and use them in later blocks. And both he IR and the C++ codegen should take these previous defs into consideration.

[LPTK]

BTW nice work! The code overall is pretty clean and nice to read.

[LPTK]

FYI I fixed the DiffTests setup on the main branch; you should merge it into this branch. Now the diff-tests behave like in the main project: if there are unstaged changes, only those files are re-tested.

[waterlens]

I think one important thing to do to make testing the IR more practical is to allow later test blocks to depend on earlier test blocks. This way we could define class True and class False once in text at the beginning of the file and use them in later blocks. And both he IR and the C++ codegen should take these previous defs into consideration.

Currently, these frequently used classes are defined internally. Are we going to move it back into the source file?

[waterlens]

I started to review your changes and already have several comments.

First of all, where are all the tests? This PR introduces many diff-test options but basically does not test them. C++ code-gen is virtually untested. At the very least there should be a couple simple but representative tests that show the generated C++ code as part of their diff output. And this output should not be polluted with all the predefined boilerplate inserted on top of every C++ generated file; it should only have the specifics of the tested code block.

Second, you should always use :NewDefs and you should not use :ParseOnly in the tests. Just fix the resulting errors. We're not trying to create two separate languages. This code is still MLscript code and there's no reason not to also test the JS backend at the same time and compare that the results are the same/similar. If builtin classes like True and False are needed, just adapt the current builtin stuff accordingly in the type checker and JS backend.

Third, there are no instructions on how to install things. The project seems to require a bunch of stuff like Boost and mimalloc. We need to create a nix configuration to get these in order automatically without the users having to fiddle with this and the C++ tests should actually be compiled and run as part of the DiffTests. This could be done in a separate PR tho, possibly with the help of our resident nix nerd @pca006132.

By the way, for class field selection, the IR builder only accepts syntax like Pair.x(a_pair). How to make it compatible with the standard syntax? The syntax above will trigger this error. I guess they only accept a_pair.x?

//│ ╟── reference of type `forall ?A ?B. (x: A, y: B) -> Pair[?A, ?B]` does not have field 'x'
//│ ║  l.698:   fun foo(a) = Pair.x(a) + Pair.y(a)

[LPTK]

Currently, these frequently used classes are defined internally. Are we going to move it back into the source file?

It might be the simplest way to do it. Because currently in the legacy compiler there's no other easy way of adding new classes visible to all of: the type checker, the JS backend, and the C++ backend. It's probably not a big deal to declare a couple of classes in every test file.

[LPTK]

By the way, for class field selection, the IR builder only accepts syntax like Pair.x(a_pair). How to make it compatible with the standard syntax? The syntax above will trigger this error. I guess they only accept a_pair.x?

Ah, right, the type checker would need to be updated to support this style. Ok, let's do this in a different PR, then, and after moving to the new compiler frontend.

[waterlens]

Currently, these frequently used classes are defined internally. Are we going to move it back into the source file?

It might be the simplest way to do it. Because currently in the legacy compiler there's no other easy way of adding new classes visible to all of: the type checker, the JS backend, and the C++ backend. It's probably not a big deal to declare a couple of classes in every test file.

The internal definitions have been moved outside. They are hidden to make the output clear. I also added pretty printers for the IR output. It should look nice now.

[waterlens]

Third, there are no instructions on how to install things. The project seems to require a bunch of stuff like Boost and mimalloc. We need to create a nix configuration to get these in order automatically without the users having to fiddle with this and the C++ tests should actually be compiled and run as part of the DiffTests. This could be done in a separate PR tho, possibly with the help of our resident nix nerd @pca006132.

By the way, John mentioned that it looks funny to test Cpp backend in target compilerJVM/test. Shall we add a target for this? He has drafted a nice Nix conf that invokes sbt to run the given test.

[LPTK]

By the way, John mentioned that it looks funny to test Cpp backend in target compilerJVM/test. Shall we add a target for this?

What? He must be misunderstanding what compilerJVM/test means. This just means the MLscript compiler source code is being tested by being run on the JVM. The output code of course has to be run on the intended target. That's already the case when running test output on NodeJS in most tests. The result of running the output code should be summarized into the DiffTest as the testing progresses, so I don't see how we'd separate this into a different target.

He has drafted a nice Nix conf that invokes sbt to run the given test.

Nice! But there's no need to invoke SBT. It's the SBT-ran tests that should invoke the C++ compiler using the toolchains set up by nix. Is that possible? It should be.

[waterlens]

By the way, John mentioned that it looks funny to test Cpp backend in target compilerJVM/test. Shall we add a target for this?

What? He must be misunderstanding what compilerJVM/test means. This just means the MLscript compiler source code is being tested by being run on the JVM. The output code of course has to be run on the intended target. That's already the case when running test output on NodeJS in most tests. The result of running the output code should be summarized into the DiffTest as the testing progresses, so I don't see how we'd separate this into a different target.

He has drafted a nice Nix conf that invokes sbt to run the given test.

Nice! But there's no need to invoke SBT. It's the SBT-ran tests that should invoke the C++ compiler using the toolchains set up by nix. Is that possible? It should be.

OK got it. I will modify the conf to make it.

[LPTK]

If the compiler project's tests now need to run only from the nix command (which I don't like), you should change the build.sbt so compilerJVM is not part of the .aggregate root project.

But I don't like this very much. Can't we just run something like "nix install" and then make sure the correct tools are used when calling them from SBT?

[waterlens]

If the compiler project's tests now need to run only from the nix command (which I don't like), you should change the build.sbt so compilerJVM is not part of the .aggregate root project.

But I don't like this very much. Can't we just run something like "nix install" and then make sure the correct tools are used when calling them from SBT?

I think Nix never changes things outside the environment, rather they have overlays where you have your settings and then offer you commands to go inside to use it.

It could be quite slow to invoke nix like using make in DiffTests, because we need to do that for every single runCpp test. If we want that, it would also require us to write the intermediate cpp code into a file in the source tree, otherwise, I don't know how to put it into the nix env ...

[pca006132]

You can treat nix develop as setting up a docker/vm, and it has the environment variables set inside it.

Technically you can install things globally, but it is not idiomatic and kind of violates the nix philosophy.

[LPTK]

@pca006132 Could you please describe the full solution that using nix develop implies?

1. What are the commands, if any, that the CI and local users need to run in order to install the tools? (Of course, no global installs!)
2. What are the commands that the SBT process is supposed to shell out in order to run the C++ compiler?

[LPTK]

It's probably fine if we have to use the SBT command from some sort of special command like <setup nix env> sbt test

[pca006132]

CI: nix develop --command sbt compilerJVM/test.

Local user:

# enter shell
nix develop
# inside the shell...
sbt compilerJVM/test

I typically use direnv. If you use it with the file .envrc with use_flake in the directory, you can just enter the directory and just run sbt compilerJVM/test, the environment is automatically setup when you enter the directory and destroyed when you exit.

[LPTK]

@pca006132 Thanks!

@waterlens Does this work for you?

[waterlens]

@pca006132 Thanks!

@waterlens Does this work for you?

I think I have used it in the CI. So, what's the next step? Moving compilerJVM out of the root target?

[LPTK]

I just checked the CI config. I don't understand why you used nix develop --command sbt compilerJVM/test instead of running everything under the nix environment as nix develop --command sbt test (replacing the old test command).

[waterlens]

I once thought it was only used to set up the environment for testing cpp backend. Anyway, if you accept the idea to test the whole project in a nix environment, I will change it accordingly.

[LPTK]

Yeah, there's no reason not to place the whole thing under nix. It would also be useful to fix the nodejs version while we're at it!

[waterlens]

As far as I know, nixpkgs only support LTS version NodeJS. Can we upgrade the version from 17 to 18? Otherwise, I may need to install NodeJs from the tarball.

[LPTK]

Ok I managed to fix the CI and to make the tests pass on my older local macOS version by switching to g++!