A Type System From Scratch – Robert Widmann | Functional Swift

The podcast episode explores the intricacies of type systems in programming languages, particularly focusing on Swift. It simplifies Swift's type checking to closures, variables, and applications, using sequence notation to define rules for type inference and checking. The discussion covers literals, closures, and subtyping, illustrating how these rules compose. It distinguishes between type inference and type checking, noting Swift's tendency to trust user annotations, which can lead to error messages far from the actual mistake. The speakers also delve into the computational complexity of Swift's type system, touching on polymorphism, subtyping, and function overloading, and introduce graph theory as a method to manage the complexity of type inference.

Outlines

Part 1: Introduction, Type Systems

Part 2: Rules, Notation, Inference

Part 3: Complexity, Graph Theory

Part 4: Practical Application, Q&A

Sign in to continue reading, translating and more.

Continue

A Type System From Scratch – Robert Widmann

Functional Swift

Part 1: Introduction, Type Systems

Introduction to Type Systems and the Use of Jargon in Functional Programming

Types in Swift: Error Messages and the Need for Context

The Lambda Cube: Classifying Programming Languages by Type System Power

Part 2: Rules, Notation, Inference

Exploring Swift's Type System and Simplifying for Reasoning

Notation and Rules for Type Checking: Sequences, Literals, and Closures

Composing Type Checking Rules and the Difference Between Type Inference and Checking

Inference Rules: Inferring Types of Literals, Variables, and Function Applications

Inferring Types in Swift: Breaking Down and Rolling Up Expressions

Complex Type Inference: Closures and Type Variables

Part 3: Complexity, Graph Theory

Complexity of Type Inference in Swift: A Feature-Based Analysis

The Growing Rule Set and the Need for Graph Theory

Representing Type Constraints as a Graph: Nodes and Numbers

Solving the Type Constraint Graph: Linked Expression Analysis and Guessing

Discharging Constraints and the Importance of Feature Reduction

Part 4: Practical Application, Q&A

Homework and Q&A Introduction

Debugging Type Errors and the Role of Annotations

Impact of Let Variables on Compilation Time

Graph Theory and Encoding Swift in Coq

Overload Resolution and Guessing

Debugging Constraints

A Type System From Scratch – Robert Widmann

Functional Swift

Part 1: Introduction, Type Systems

00:00Introduction to Type Systems and the Use of Jargon in Functional Programming

Introduction to Type Systems and the Use of Jargon in Functional Programming

00:41Types in Swift: Error Messages and the Need for Context

Types in Swift: Error Messages and the Need for Context

02:22The Lambda Cube: Classifying Programming Languages by Type System Power

The Lambda Cube: Classifying Programming Languages by Type System Power

Part 2: Rules, Notation, Inference

05:07Exploring Swift's Type System and Simplifying for Reasoning

Exploring Swift's Type System and Simplifying for Reasoning

06:19Notation and Rules for Type Checking: Sequences, Literals, and Closures

Notation and Rules for Type Checking: Sequences, Literals, and Closures

13:31Composing Type Checking Rules and the Difference Between Type Inference and Checking

Composing Type Checking Rules and the Difference Between Type Inference and Checking

14:44Inference Rules: Inferring Types of Literals, Variables, and Function Applications

Inference Rules: Inferring Types of Literals, Variables, and Function Applications

19:11Inferring Types in Swift: Breaking Down and Rolling Up Expressions

Inferring Types in Swift: Breaking Down and Rolling Up Expressions

21:27Complex Type Inference: Closures and Type Variables

Complex Type Inference: Closures and Type Variables

Part 3: Complexity, Graph Theory

24:24Complexity of Type Inference in Swift: A Feature-Based Analysis

Complexity of Type Inference in Swift: A Feature-Based Analysis

27:34The Growing Rule Set and the Need for Graph Theory

The Growing Rule Set and the Need for Graph Theory

29:05Representing Type Constraints as a Graph: Nodes and Numbers

Representing Type Constraints as a Graph: Nodes and Numbers

31:11Solving the Type Constraint Graph: Linked Expression Analysis and Guessing

Solving the Type Constraint Graph: Linked Expression Analysis and Guessing

34:31Discharging Constraints and the Importance of Feature Reduction

Discharging Constraints and the Importance of Feature Reduction

Part 4: Practical Application, Q&A

36:20Homework and Q&A Introduction

Homework and Q&A Introduction

37:44Debugging Type Errors and the Role of Annotations

Debugging Type Errors and the Role of Annotations

39:36Impact of Let Variables on Compilation Time

Impact of Let Variables on Compilation Time

41:31Graph Theory and Encoding Swift in Coq

Graph Theory and Encoding Swift in Coq

45:00Overload Resolution and Guessing

Overload Resolution and Guessing

46:15Debugging Constraints

Debugging Constraints