disco-lang / disco

Functional teaching language for use in a discrete mathematics course
Other
164 stars 23 forks source link

Display multiple example types for things with nontrivial (non-parametric) polymorphism #388

Closed byorgey closed 5 months ago

byorgey commented 6 months ago

Closes #169. Previously, we did this:

Disco> :type \x. x - 2
λx. x - 2 : ℤ → ℤ

However, this was a lie since in fact \x. x - 2 is more general than that; but showing only one possible monomorphic type was still better than showing some generic monstrosity like forall a. (N <: a, subtractive a) => a -> a.

Now, with this PR, we do this:

Disco> :type \x. x - 2
This expression has multiple possible types.  Some examples:
λx. x - 2 : ℤ → ℤ
λx. x - 2 : ℚ → ℚ

See #169 for more context and examples.

Briefly, in this PR, we:

It is still possible to make the solver blow up in case there are many possible container variables to instantiate. e.g. expressions like \x. \y. \z. \w. (set(x), set(y), set(z), set(w)) take a very long time to typecheck. I have some ideas for how to improve this situation, but for now it's an uncommon corner case.

byorgey commented 6 months ago

@justingrubbs , @LeitMoth I'd love for you to take a look at this when you get a chance (no rush). I certainly don't expect you to read and understand all the code changes, though you're welcome to look at it in whatever detail you like. But see if the overall idea makes sense, play with some examples, see if you can break it, that kind of thing.