I am currently creating my own compiled programming language, and I have come to a point where I would like to start working on the type system and introduce some type checking. Ideally I would like to introduce type inference.

Right now I'm using the Visitor pattern to traverse the AST produced by the parser. I started implementing a pretty naive and ugly solution, but wasn't very happy with it. It seemed pretty hacky. Type checking that fits with this pattern would be great, but not critical.

I have looked into algorithms like the Hindley-Milner. I'm developing the programming language in Swift, so I found this GitHub gist that shows how it can be implemented, but opening the lid on this code immediately gets me to Lambda Calculus, which seems like a beast. I know Swift uses a variant of the Hindley-Milner type inference, so that would be incredibly sexy to implement, but it's way over my head at this point.

Since this is my first programming language, what's a good first attempt at a type system with type checking, possibly with type inference?


1 Answer 1


You could start with the simple cases of Swift. Literals have type “Literal”, for example, and known variables have their known types. When you evaluate an expression you may know what type you want and evaluate accordingly, or you don’t know and get the type from the expression.

(Anyone not knowing the language: let x: Int = 7/2 assigns 3. let x: Double = 7/2 assigns 3.5 because assignment to Double wants a Double expression, therefore / wants two Double operands, therefore the literals 7 and 2 are Double).

Keep in mind you can always report an error if you can’t handle a situation, as long as the code can be changed to work without complaints.

  • $\begingroup$ Thank you, I'll look into that. I'm not sure if this answer satisfies my question, but I'm also having a hard time expressing myself any better than what I did, so I'll hold on to marking this as an answer until there comes other answers. If not, I'll mark it. $\endgroup$
    – eirikvaa
    May 5, 2019 at 20:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.