Is there somewhere a published description of the Scala (2 or 3) subtype algorithm? Given two types A and B, how does Scala determine whether A is a subtype of B. I suppose that mathematically, this amounts to simply walking up the type lattice from A in attempt to find B, and simultaneously walking up from B in attempt to find A. However, my guess is that this is computational expensive, so there is some efficient algorithm which obviates an exponential search.

This might be relevant. For scala 3, I don’t know if there’s similar publications done for scala 2.

1 Like

Might wanna read this, probably, too:

Thanks for the article, a brief look confirms my suspicions that the algorithm does seem to be exponential in time. Since I haven’t yet read the paper (it’s not light reading) I don’t know whether their proposed approach avoids the exponential explosion by sacrificing expressivity.