13.2 Type theory and programming languages

Type theory bridges logic and programming, showing how proofs relate to programs. It's the backbone of modern programming languages, ensuring code correctness and catching errors early. This connection helps create safer, more reliable software.

Type systems in programming languages enforce data constraints, enable modular coding, and serve as documentation. Advanced features like dependent types and polymorphism allow for more expressive and flexible code, while type inference and checking improve development efficiency and program safety.

Type Systems and Lambda Calculus

Foundations of Type Theory

Top images from around the web for Foundations of Type Theory

• 

  Probabilistic Type Theory for Incremental Dialogue Processing - ACL Anthology View original

  Is this image relevant?

• 

  Haskell for Lambda Calculus, Type Inferencing - Stack Overflow View original

  Is this image relevant?

• 

  Homotopy type theory - Wikipedia View original

  Is this image relevant?

• 

  Probabilistic Type Theory for Incremental Dialogue Processing - ACL Anthology View original

  Is this image relevant?

• 

  Haskell for Lambda Calculus, Type Inferencing - Stack Overflow View original

  Is this image relevant?

1 of 3

Top images from around the web for Foundations of Type Theory

• 

  Probabilistic Type Theory for Incremental Dialogue Processing - ACL Anthology View original

  Is this image relevant?

• 

  Haskell for Lambda Calculus, Type Inferencing - Stack Overflow View original

  Is this image relevant?

• 

  Homotopy type theory - Wikipedia View original

  Is this image relevant?

• 

  Probabilistic Type Theory for Incremental Dialogue Processing - ACL Anthology View original

  Is this image relevant?

• 

  Haskell for Lambda Calculus, Type Inferencing - Stack Overflow View original

  Is this image relevant?

1 of 3

• Type systems classify program phrases according to the kinds of values they compute
  • Help prevent certain kinds of programming errors by defining and enforcing interfaces between different parts of a program
• Lambda calculus is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution
  • Serves as a theoretical foundation for functional programming languages ($\lambda$-calculus)
• Curry-Howard correspondence establishes a direct relationship between mathematical proofs and computer programs
  • Proofs correspond to programs (propositions as types)
  • The proof of a proposition corresponds to a program of the corresponding type
• Type safety guarantees absence of certain run-time errors
  • Well-typed programs cannot "go wrong" ($\mathtt{if}$ $\vdash$ $t : \tau$ $\mathtt{then}$ $t \Downarrow v$ for some $v : \tau$)

Applications of Type Systems

• Type systems used in programming languages to enforce data type constraints
  • Prevent errors such as adding a number to a string (

    3 + "hello"

    )
• Type systems enable modular programming by enforcing interfaces between components
  • Ensure functions receive arguments of expected types (function expecting

    int

    receives

    int

    )
• Type systems catch certain errors at compile-time rather than run-time
  • Reduces debugging effort and improves software reliability
• Type systems serve as a form of documentation, making code easier to understand and maintain
  • Type signatures convey expected inputs and outputs of functions

Advanced Type System Features

Dependent Types

• Dependent types allow types to depend on terms
  • Type of function's output can depend on the value of its input ($\mathtt{Vec} : \mathtt{Nat} \rightarrow \mathtt{Type}$)
• Dependent types enable expressing precise properties of programs in their types

  • append : (n m : Nat) → Vec A n → Vec A m → Vec A (n + m)

• Dependent types blur the line between types and terms
  • Allows proving properties of programs within the type system itself (e.g.,

    (n : Nat) → Vec A n → Vec A (double n)

    )

Polymorphism and Subtyping

• Polymorphism allows code to be more generic by abstracting over types
  • Parametric polymorphism: Code is written without mentioning specific types (

    id : ∀ A . A → A

    )
  • Ad-hoc polymorphism: Code can have different implementations for different types (operator overloading)
• Subtyping allows a value of one type to be used in a context expecting another type
  • Subtype relation $\leq$ is reflexive, transitive, and antisymmetric ($S \leq T$ if every value of type $S$ can safely be used where a value of type $T$ is expected)
  • Enables substitutability and code reuse (functions accepting

    Animal

    can accept

    Cat

    or

    Dog

    )

Type Inference and Checking

Type Inference

• Type inference automatically deduces types of expressions based on context
  • Relieves burden of manual type annotations (

    val x = 3

    inferred as

    val x: Int = 3

    )
• Hindley-Milner type inference algorithm used in ML-family languages
  • Infers most general type of an expression ($\mathtt{id} : \forall \alpha . \alpha \rightarrow \alpha$)
• Bidirectional type inference combines top-down (checking) and bottom-up (synthesis) propagation
  • Reduces annotation burden while supporting advanced type system features

Type Checking

• Type checking verifies type-correctness of a program against a type system
  • Detects type errors such as applying a function to an argument of the wrong type
• Type checking can be static (at compile-time) or dynamic (at run-time)
  • Static type checking catches errors early but requires more annotations
  • Dynamic type checking defers checks to run-time but allows more flexibility
• Gradual typing combines static and dynamic typing
  • Allows mixing typed and untyped code (

    any

    type in TypeScript)
  • Performs static checks where possible and defers remaining checks to run-time