[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?

@xedin

2 Likes

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".

2 Likes

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.

3 Likes

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!