Implementing Type Inference in Jedi

This thesis begins with an overview of type systems: evolution, concepts, and problems. This survey is based on type systems of modern languages like Scala and Haskell. Scala has a very sophisticated type system that includes generics, polymorphism, and closures. It has a built-in type inference mechanism that enables the programmer to exclude certain type annotations. It is often not required in Scala to mention the type of a variable because the compiler can infer the type from the initialization of the variable. Study of such type system is demonstrated by the implementation of the type system. A type system for a demonstration language ‘Jedi’ is developed. It includes a runtime type identification system for Jedi values and a static type system for Jedi expressions. Jedi features include arithmetic, logic, and declarations. It also supports lambda expressions, blocks, and closures. In Jedi, each value and expression have a type, and types are also values. Challenges faced in the Jedi type system include determining the types of complex expressions such as lamdas, function calls, and nested expressions. A Jedi reference interpreter and its type system are implemented in Scala