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.
Might wanna read this, probably, too:
Also note that you asked a strongly related question here a while ago.
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.