[GSoC] Type Inference Algorithm Improvements

Hello all!

I am Dane, an undergraduate university computer science student, and I was looking to participate in GSoC in 2022, specifically the improvement of debugging output of the type inference algorithm.

I haven't yet worked with a type inference algorithm so I familiarized myself with the current design implementation of the type inference algorithm that Swift incorporates. However, I am confused as to why Swift undergoes such complexity with intertwining the bi-directional type inference, the more classical type, with non classical systems? I guess I am also confused as to how the two are incorporated into the algorithm.

I was also wondering where to start when expanding my overall knowledge regarding the constraint system and why it was implemented in the type inference algorithm over other programming logics.

I have also started becoming far more familiar with Swift as a programming language, and have experienced the effects of the interface of the type inference algorithm. Is there any other way to view the algorithm?



Here are two documents you can review to start:

Also, try type checking a simple source file with the '-Xfrontend -debug-constraints' flag.

What do you mean by non-classical systems?

What other programming logics do you have in mind?

You can find the code in https://github.com/apple/swift/tree/main/lib/Sema; the solver is implemented in various files whose names start with "CS", as well as "ConstraintSystem.cpp", "ConstraintGraph.cpp", "Constraint.cpp", and "TypeCheckExpr.cpp".


Thank you, Slava! Just to add to your links - swift/DebuggingTheCompiler.md at main · apple/swift · GitHub. This has an example of output we are seeking to improve and other details.


Thank you for your response!

I have been reading the documents you have sent, and when referencing non-classical systems, I was referring to the Hindley-Milner system. I believe I better understand the type inference algorithm system and how it connects to the debugging system.

Thank you for your help!