Background read: Can Scala have a highly parallel typechecker?

This is a meta issue with a quick overview of all tasks I came up when I thought of adding support for the As Seen From (ASF) algorithm and for processing the Scala std lib to Kentucky Mule.

I'm following the format from my work on zinc that turned out to be successful in managing the complexity of a difficult project I worked on in the past: sbt/sbt#1104
It shipped as part of the sbt 1.0 release recently.

This ticket describes the second stage in Kentucky Mule's development. The first stage was about validating whether the ideas for rethinking compiler's design with focus on performance are in touch with how fast computers actually compute. The second stage is about confronting Kentucky Mule's ideas with what I consider the most tricky aspects of Scala's design to implement in a performant way.

I'm planning to update this issue with interesting findings and roadblocks I hit working towards finishing the tasks listed below. My intent for this issue is twofold:

• keep me organized in marching towards adding support for processing Scala's standard library in Kentucky Mule
• give busy but curious passerby a place to track the progress of Kentucky Mule's evolution

Context

In my most recent blog post on Kentucky Mule, I wrote:

Adding support for processing Scala’s standard library in Kentucky Mule would be a good trial for the As Seen From treatment. The standard library makes a heavy use of mix-ins, abstract types that are refined multiple times in the inheritance chain and type constructors. These are the features that remain the riskiest for the architecture to support.

I think adding support for Scala standard library to Kentucky Mule should take another 15 days of deeply focused effort. And I think it would be a really captivating project to work on. Once that is done, I think Kentucky Mule would become a complete proof of concept for a highly parallel Scala compiler architecture.

I'm breaking up the work required for adding the As Seen From and some other missing Scala language features to Kentucky Mule into a list of smaller tasks. The list is not meant to be set in stone and will get refined as more issues and tasks come to light.

Once I surfaced the list, I realized the scope is a bit larger than I originally speculated. I'm revising previous prediction of 15 days of deeply focused effort to complete this project and bump it to 20 days.

Tasks

Missing language features

• monomorphic type aliases: type T = String
• polymorphic type aliases: type Foo[T] = List[T]
• package objects
• constructor multiple param list
• def multiple param list
• method dependent types
• resolution of this in paths
• type bounds for type members
• type bounds for type parameters
• implicit import of Predef to every compilation unit
• implicit import of scala and java packages to every compilation unit
• support for super in paths
• singleton types
• type projections
• tuple types (contributed by @trane in #7)
• function types
• import renames
• self-types
• method-dependent types

Implementation features

Features that are not strictly language features but need to be implemented for other reasons.

• empty package handling (surprisingly hard to get right)
• cycle detection between completers

As Seen From

Surprisingly, Kentucky Mule implements some aspects of the ASF already. E.g. Rule 3 for the type parameters is partially supported. I don't have a good intuition what's missing even when I have ASF's precise definition in front of my eyes. For performance reasons, Kentucky Mule implements ASF's features differently from how they're specified so simple diffing between the implementation and the spec doesn't cut it.
I'll come back to this section as the implementation of the other language features mentioned above progresses.

Status

I haven't touched Kentucky Mule for almost a year and I'm picking it up now to work on tasks in this ticket continously until I check all the boxes. Kentucky Mule remains my side project so I aim for a steady but slow progress done over the course of some of my evenings.

I implemented the original, first stage of Kentucky Mule in a short span of time when I was working on it full time. I'm curious if my 20 days prediction of completing this project will hold when the days are broken into a larger number of evenings.

Please include a license so that people can use, build on, or even look at, your work.

I recommend any libre software license compatible with the gpl https://www.gnu.org/licenses/license-list.en.html#GPLCompatibleLicenses and, if you choose to license permissively, to Apache 2.0

(paraphrasing from @gkossakowski)

Currently, kentuckymule does not parse jars or look at the classpath for the code it is type checking. The sample code it's being tested against is the scala standard library which has a minimal set of dependencies (mostly or all in the java standard library?) and so when kentuckymule needs to search for information on one of these symbols, it uses a shim to avoid having to do proper jar and classpath parsing (the shim is called ScalaLibHelper).

This ticket tracks implementation of a proper jar parser to avoid having to use the shim. This would also empower kentuckymule to be run over other codebases, specifically the scala community build, which would help develop benchmarks to support collaboration!

The following code:

class Hi {
  class A
}

class Foo {
  val x = new Hi
  import x._
  def bar: A = new A
}

fails with:

java.lang.RuntimeException: Can't resolve selector Ident(A)

It seems that either importing from something with type InferredTypeMarker should be disallowed or that everything in scope after such an import should get type InferredTypeMarker.

As far as I can see, everything is hardcoded to compile scalap, what would be needed to be able to do:

> run foo.scala

from sbt, and have it just work?

How tractable would it be to get kentucky mule tested against the scala community build? What are the barriers to running this? Is the scala community build a closed system, or can kentuckymule get access to that infrastructure to experiment? Will we need to roll-out our own and if so how much work would that be?