David MacQueen has worked at Bell Labs for around 20 years during it’s Golden Age. Professor at Chicago University for 23 years. He is one of the designers of SML, one of the fathers of HOPE the programming language that introduced the notion of Algebraic Datatypes. So this interview was very special to me personally where I could get to hear all t…

I discuss what is called the locally nameless representation of syntax with binders, following the first couple of sections of the very nicely written paper "The Locally Nameless Representation," by Charguéraud. I complain due to the statement in the paper that "the theory of λ-calculus identifies terms that are α-equivalent," which is simply not t…

I discuss the paper POPLmark Reloaded: Mechanizing Proofs by Logical Relations, which proposes a benchmark problem for mechanizing Programming Language theory.Aaron Stump

I continue the discussion of POPLmark Reloaded , discussing the solutions proposed to the benchmark problem. The solutions are in the Beluga, Coq (recently renamed Rocq), and Agda provers.Aaron Stump

In this episode Pierre-Marie Pédrot, one of the main Coq/Rocq developers joins us to talk about Krivine, Kleene and Gödel Realizability Models, how it relates to the BHK interpretation and CPS Translations, and how it was all already part of Gödel's work in Dialectica! If you enjoy the show please consider supporting us at our ko-fi: https://ko-fi.…

In this episode, I begin discussing the question and history of formalizing results in Programming Languages Theory using interactive theorem provers like Rocq (formerly Coq) and Agda.Aaron Stump

In this episode Pierre-Marie Pédrot who is one of the main Coq/Rocq developers joins us to talk about what is Type Theory, what is Martin-Löf Type Theory, what are the properties we should care about in our type theory and why. If you enjoy the show please consider supporting us at our ko-fi: https://ko-fi.com/typetheoryforall Links Pierre-Marie's …

Mario Carneiro is the creator of Mathlib, Lean4Lean and Metamath0. He is currently doing his Postdoc at Chalmers University working on CakeML. In this episode we talk about foundations of theorem provers, type systems properties, semantics and interoperabilities. If you enjoy the show please consider supporting us at our ko-fi: https://ko-fi.com/ty…

In this episode Eric Bond and Patrick Lafontaine joins us to talk about the life in industry vs the life in academia. Eric is a PhD student at Michigan University under Max New, he works with some pretty cool esoteric cubical agda stuff. Before starting his PhD he has spent some time at the consultancy companies Two Six Technologies and 47 Degrees …

In this episode we talk with Fabrizio Montesi, a Full Professor at the University of South Denmark. He is one of the creators of the Jolie Programming Language, President of the Microservices Community and Author of the book 'Introduction to Choreographies'. In today’s episode we talk about the formal side of Distributed Sytems, session types, the …

Satnam Singh has got incredible experience in both academia and industry. He has worked in Google, Facebook, Microsoft, Microsoft Research, Xilinx, etc. He has been a lecturer in Glasgow, Birmingham and University of California for a couple of years. He has worked with many interesting tools such Coq, Haskell, Verilog, Tensorflow. These days he wor…

In this episode we go into a deep dive into the formal methods side of Voting systems, and for this nobody better than our guest: Joe Kiniry, A Principal Scientist at Galois, Principled CEO and Chief Scientist of Free & Fair, a Galois spin-out focused on high-assurance elections technologies and services. For the past 20 years Joe has worked tirele…

In this episode we continue our conversation with David Christiansen, he wrote the books Functional Programming in Lean and the Little Typer. He has also worked as the Executive Director of the Haskell Foundation, at Galois and did his PhD developing a bunch of cool stuff for Idris. In today’s episode we talk about the story behind writing The Litt…

In this episode, I describe the first proof of normalization for STLC, written by Alan Turing in the 1940s. See this short note for Turing's original proof and some historical comments.Aaron Stump

In this episode we talk with David Christiansen, he wrote the books Functional Programming in Lean and the Little Typer. He has also worked as the Executive Director of the Haskell Foundation, at Galois and did his PhD developing a bunch of cool stuff for Idris. David is a super upbeat person and I feel that we could spend hundreds of hours talking…

In this episode, after a quick review of the preceding couple, I discuss the property of normalization for STLC, and talk a bit about proof methods. We will look at proofs in more detail in the coming episodes. Feel free to join the Telegram group for the podcast if you want to discuss anything (or just email me at aaron.stump@gmail.com).…

Like addition and multiplication on Church-encoded numbers, exponentiation can be assigned a type in simply typed lambda calculus (STLC). But surprisingly, the type is non-uniform. If we abbreviate (A -> A) -> A -> A as Nat_A, then exponentiation, which is defined as \ x . \ y . y x, can be assigned type Nat_A -> Nat_(A -> A) -> Nat_A. The second a…

It is maybe not so well known that arithmetic operations -- at least some of them -- can be implemented in simply typed lambda calculus (STLC). Church-encoded numbers can be given the simple type (A -> A) -> A -> A, for any simple type A. If we abbreviate that type as Nat_A, then addition and multiplication can both be typed in STLC, at type Nat_A …

I review the typing rules and some basic examples for STLC. I also remind listeners of the Curry-Howard isomorphism for STLC.Aaron Stump

In this episode, after a pretty long hiatus, I start a new chapter on simply typed lambda calculus. I present the typing rules and give some basic examples. Subsequent episodes will discuss various interesting nuances...Aaron Stump

In this episode we talk with Guannan Wei, from Purdue University. Guannanfinished his PhD last year under Tiark Rompf, and is currently doing hisPost-Doc with Tiark. Guannan has worked on a plethora of differentcompilers topics, and in this conversation we will talk about Staging,Futamura Projections, Symbolic Execution, Compiler Applications in Sm…

In this episode we celebrate 3 years of existence of this podcast byreflecting on the journey so far, what is my philosophy, how do Iapproach the interviews, my overall goals for the show, and some of our plansfor the future. In order to achieve this, I first take a detour and tell you a little moreabout my personal history, and my carreer in type …

In this episode we talk with Eduardo Rafael. He isself-thaught programming languages enthusiast, youtuber, twitch streamer,multi-skilled programmer that has worked in different aspects of computerscience such as PL, operating systems, blockchain, and many other stuff. Inthis conversation we talk about his experience as a developer and hacker thatdi…

Andrew Marmaduke is a PhD Candidate from the University of Iowa, he worksunder Aaron Stump and has been working on revamping the theorem proverCedille 2. In this episode we tackle fundamental questions about thefoundations of the theorem provers, Cedille and Cedille 2. If you enjoy the show please consider supporting us at our ko-fi: https://ko-fi.…

This episode presents two somewhat more advanced examples in DCS. They are Harper's continuation-based regular-expression matcher, and Bird's quickmin, which finds the least natural number not in a given list of distinct natural numbers, in linear time. I explain these examples in detail and then discuss how they are implemented in DCS, which ensur…

In this episode, I continue introducing DCS by comparing it to termination checkers in constructive type theories like Coq, Agda, and Lean. I warmly invite ITTC listeners to experiment with the tool themselves. The repo is here.Aaron Stump

In this episode, I talk more about the DCS tool, and invite listeners to check it out and possibly contribute! The repo is here.Aaron Stump

Not satisfied with implementing one of the most popular automated theoremprovers, Z3, Leo de Moura also tackles another extremely hard problem inour field and implements a brand new interactivetheorem prover from scratch, Lean. In this episode we dive into the mind andphilosophy of this man. If you enjoy the show please consider supporting us at ou…

DCS is a new functional programming language I am designing and implementing with Stefan Monnier. DCS has a pure, terminating core, around which monads will be layered for possibly diverging, impure computation. In this episode, I talk about this basic design, and its rationale.Aaron Stump

I answer a listener's question about the semantics of subtyping, by discussing two different semantics: coercive subtyping and subsumptive subtyping. The terminology I found in this paper by Zhaohui Luo; see Section 4 of the paper for a comparison of the two kinds of subtyping. With coercive subtyping, we have subtyping axioms "A

In this episode we continue our conversation with Jan de Muijnck-Hughes aResearch Associate at Glasgow University. He works using all sorts of fancytype systems mostly targeted for hardware specification, particularly withthe aid of the theorem prover Idris. This episode we start by talking alittle about Impostor Syndrome in academia and how he has…

I continue the discussion of Mitchell's paper Type Inference with Simple Subtypes. Coming soon: a discussion of semantics of subtyping.Aaron Stump

In this episode we have a deep conversation with Jan de Muijnck-Hughes, talksabout all the cool research he has done with idris, hardware and different kindsof interesting type systems such as session types, quantitative types and gradedtypes. In the second half we discuss all the different kinds of problems thathas been going on in PL academia lat…

In this episode, I wax rhapsodic for the potential of subtyping to improve the practice of pure functional programming, in particular by allowing functional programmers to drop various irritating function calls that are needed just to make types work out. Examples are lifting functions with monad transformers, or even just the pure/return functions…

In this episode, I begin discussing a paper titled "Type Inference with Simple Subtypes," by John C. Mitchell. The paper presents algorithms for computing a type and set of subtype constraints for any term of the pure lambda calculus. I mostly focus here on how subtype constraints allow typing any term (which seems surprising). You can join the tel…

In this episode, I discuss a few of the basics for what we expect from a subtyping relation on types: reflexivity, transitivity, and the variances for arrow types.Aaron Stump

We begin a discussion of subtyping in functional programming. In this episode, I talk about how subtyping is a neglected feature in implemented functional programming languages (for example, not found in Haskell), and how it could be very useful for writing lighter, more elegant code. I also talk about how subtyping could help realize a new vision …

In this episode we have over Dan Plyukhin, a PhD Candidate fromthe University of Illinois Urbana-Champaign. We talk about Dan’s research is in the field of parallelism, morespecifically garbage collection in the presence of actors. Then we also talk about Pedro's research on translating GADTs from OCaml to Coq,and the burnout process that lead him …

In this episode, I conclude my discussion of some (but hardly all!) points from Pujet and Tabareau's POPL 2022 paper, "Observational Equality -- Now for Good!". I talk a bit about the structure of the normalization proof in the paper, which uses induction recursion. See this paper by Peter Dybjer for more about that feature. Also, feel free to join…

Jimmy Koppel, got his PhD at MIT and found the Mirdin Company, where heteaches engineers to write better code! In this interview we talk about howto make better code, how the knowledge of computer science theory andprogramming languages can help engineers to achieve that, and much more! Links Jimmy's Personal Website Jimmy's Twitter Mirdin's Websit…

I continue discussing the Puject and Tabareau paper, "Observational Equality -- Now for Good", in particular discussing more about how the equality type simplifies based on its index (which is the type of the terms being equated by the equality type), and how proofs of equalities can be used to cast terms from one type to another. Also, in exciting…

In this episode, I introduce an important paper by Pujet and Tabareau, titled "Observational Equality: Now for Good", that develops earlier work of McBride, Swierstra, and Altenkirch (which I will cover in a later episode) on a new approach to making a type theory extensional. The idea is to have equality types reduce, within the theory, to stateme…

I pause the chapter on extensionality in type theory to talk about something very exciting that I just learned about (though the project was completed Summer 2022): the so-called Liquid Tensor Experiment, to formalize a recent very difficult proof by a mathematician named Peter Scholze, in Lean. This is the first time in history, that I know of, wh…

In this episode we host another company that does formal method in thecontext of the Everscale Blockchain, and Solidity smart contracts.How and why they use formal methods in this context? Who are their clients?What are the caveats? Links Pruvendo's Website Pruvendo's Linkdin Pruvendo's TwitterPedro Abreu

In this episode talk with Gerwin Klein about the formal verification of themicrokernel seL4 which was done using Isabelle atNICTA / Data61 in Australia. We also talk a little about his PhD Projectveryfing a piece of the Java Virtual Machine. Links Gerwin's Twitter Gerwin's Website ProofCraft's Website…

In this episode, I discuss the basic distinguishing rule of Extensional Martin-Loef Type Theory, namely equality reflection. This rule says that propositional equality implies definitional equality. Algorithmically, it would imply that the type checker should do arbitrary proof search during type checking, to see if two expressions are definitional…

This episode begins a new chapter on extensionality in type theory, where we seek to equate terms in different ways based on their types. The basic example is function extensionality, where we would like to equate functions from A to B if given equal inputs at type A, they produce equal outputs at type B. With this definition, quicksort and mergeso…

Kevin Buzzard has been very passionate spreading the word amongmathematicians to use theorem provers mechanize theorems of modernmathematics. In this conversation we will talk about his vision in teachingundergrads to use the Lean theorem prover, what is the Xena Project, his viewof how theorem provers can change the way we do mathematics, and much…

In this episode, I talk about two papers from the 3rd International Workshop on Formal Methods for Blockchains, 2021. Also, I am continuing my request for your small donations ($5 or $10 would be awesome) to pay my podcast-hosting fees at Buzzsprout. To donate, click here, and then under "Gift details" select "Search for additional options" and the…

In this episode, I discuss this paper, "Mi-Cho-Coq, a Framework for Certifying Tezos Smart Contracts", by Bernardo et al. The paper gives a nice and very clear introduction to the Michelson language, and a formalization of it in Coq. This is used to prove a correctness property about a Multisig contract. I also kindly solicit your small donations (…