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. Links Andrew’s Website AndrasKovacs’ Smalltt Failure of Normalization in Impredi…

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. Links Leo’s Website Lean Z3 The Church of Logic Podcast…

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 Twitterبقلم Pedro 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 (…

In this episode we partner with Formal Land, a company that works in formallyverifying the Tezos codebase! I have worked with them in the past developingnew features to their source-to-source compiler CoqOfOcaml. In this episode wetalk about their work with Tezos and how their techniques are applicable toother codebases as well! For this we talk wi…

In this episode (proudly wearing my "I am not an expert" hat), I discuss efforts by Runtime Verification to verify the Dexter2 defi smart contract, using their K-Michelson tool, which provides an executable description of the operational semantics of the Michelson language used for smart contracts on the Tezos blockchain.…

I start off a new chapter (seventeen!) of the podcast, to talk about formal methods for blockchain systems. In the next few episodes, we will look at some verification efforts related to the Tezos blockchain.بقلم Aaron Stump

In this episode we interview Lawrence Paulson, one of the creating fathers ofIsabelle. We talk about the development process, how it drew inspirations andideas from LCF and Boyer Moore. What tools were used, it’s strenghts andweaknesses, and all about the historical context at the time! We also brieflytalk about his formalization of the Gödel’s Inc…

In this episode we talk about Sigplan, the organization behind the mostimportant conferences and proceedings in our field. What is the SIGPLAN? Whatexactly does it do? How is it organized? How are things published? To answerthese and many other questions we talk with Jens Palsberg, a professor atUCLA, who is the past chair of the SIGPLAN. And also …

I discuss separation logic basics some more, as presented in the seminal paper by John C. Reynolds. An important idea is describing data structure using separating conjunction and recursive predicates.بقلم Aaron Stump

In this episode Cody Roux teaches some interesting concepts that people careabout in Mathematics and Logic as a way to try to understand what is going onin the universe around us! In particular we will try to explain concepts suchas Impredicativity, Excluded Middle, Group Theory, Model Theory, KripkeModels, Realizability, The Markov Principle, Cut …

In this episode Conal Elliott gives a more concrete presentationon what is Denotational Design is and how to use it in practice. It is a continuation of episode #17, in which we had an in-depth philosophicalconversation to explain why he believes thatDenotational Design is a superior form of reasoning in the realm of computerscience. We also contin…

I discuss separation logic, as presented in this seminal paper by the great John C. Reynolds. I did not go very far into the topic, so please expect a follow-up episode.بقلم Aaron Stump

In this episode, I talk briefly about Rust, which uses compile-time analysis to ensure that code is memory-safe (and also free of data races in concurrent code) without using a garbage collector. Fantastic! The language draws on but richly develops ideas on ownership that originated in academic research.…

In this episode, me and Eric Bond have a great conversation with Dan R.Ghica, a professor at Birmingham University and Director of the ProgrammingLanguage Research Lab of the Huaweii Research Centre Edinburgh. We talk about his work on both institutions, which includes topics such asCategory Theory, String Diagrams, and Game Semantics. We also brie…

I discuss the idea of statically typed region-based memory management, proposed by Tofte and Talpin. The idea is to allow programmers to declare explicitly the region from which to satisfy individual allocation requests. Regions are created in a statically scoped way, so that after execution leaves the body of the region-creation construct, the ent…

In this episode, I start a new chapter (we are up to Chapter 16, here), about verifying safe manual management of memory. I have personally gotten pretty interested in this topic, having seen through some simple experiments with Haskell how much time can go into garbage collection for seemingly simple benchmarks. I also talk about why verifying mem…

In today’s episode I invite two friends of mine Patrick Lafontaine and SupunAbeysinghe. We will talk about their experience learning Coq and we guideourselves in a survey that I gave all the 83 students in the class.The class was thought by my advisor Benjamin Delaware and I was his TA. Patrick researches compilers and have done work in particular …

I laud the Metamath proof checker and its excellent book. I am also looking for suggestions on what to discuss next, as I am ready to wrap up this chapter on proof assistants.بقلم Aaron Stump

In this episode Cody Roux talks about the Gödel’s Incompleteness Theorems. We gothrough it’s underlying historical context, Hilbert’s Program, how it relateswith Turing, Church, Von Neumann, Termination and more. Links Cody’s website Cody’s dblp The Lady or the Tiger? - Short Story The Lady or the Tiger? - Amazon Logicomix An Introduction to Gödel’…

In this episode I had the pleasure to have an in-depth conversation with ConalElliott about his life, his work, his philosophy and his many opinions aboutresearch and the current state of PL Research and how it lead him to come withthe concept of Denotational Design. Conal got his PhD at CMU in the 90s underFrank Pfenning working on Higher-Order Un…

In this episode I share my initial impressions -- very positive! -- of the Metamath system. Metamath allows one to develop theorems from axioms which you state. Typing or other syntactic requirements of axioms or theorems are also expressed axiomatically. The system exhibits an elegant coherent vision for how such a tool should work, and was super …

I discuss a book edited by Freek Wiedijk (pronounced "Frake Weedike"), which describes the solutions he received in response to a call for formalized proofs of the irrationality of the square root of 2. The book was published in 2006, and made an impression on me then. The provers we have discussed so far all have a solution in the book, except for…