Iowa Type Theory Commute

Aaron Stump

Aaron Stump talks about type theory, computational logic, and related topics in Computer Science on his short commute.

  1. HACE 5 DÍAS

    What are commuting conversions in proof theory?

    Commuting conversions are transformations on proofs in natural deduction, that move certain stuck inferences out of the way, so that the normal detour reductions (which correspond to beta-reduction under Curry-Howard) are enabled.  The stuck inferences are uses of disjunction elimination.  In programming terms, if you have an if-then-else (a simple case of or-elimination) where the then- and else-branches are lambda abstractions, and you apply that if-then-else to an argument, you need commuting conversions to move the argument into the branches, so you can call the functions (in the then- and else-branches) with it. See Section 10.1 of Girard's Proofs and Types for more on the problem, and a nice paper by de Groote on strong normalization with commuting conversions.

    22 min

  2. 16 ENE

    What is Control Flow Analysis for Lambda Calculus?

    I am currently on a frolic into the literature on Control Flow Analysis (CFA), and discuss what this is, for pure lambda calculus.  A wonderful reference for this is this paper by Palsberg.

    19 min

  3. 14/11/2025

    Measure Functions and Termination of STLC

    In this episode, I talk about what we should consider to be a measure function.  Such functions can be used to show termination of some process or program, by assigning a measure to each program, and showing that as the program computes, the measure decreases in some well-founded ordering.  But what should count as a measure function?  The context for this is RTA Open Problem 19, on showing termination for the simply typed lambda calculus using a measure function. Let's call this the start of season 7, because it seems about time for that.

    22 min

  4. 22/08/2025

    Schematic Affine Recursion, Oh My!

    To solve the problem raised in the last episode, I propose schematic affine recursion.  We saw that affine lambda calculus (where lambda-bound variables are used at most once) plus structural recursion does not enforce termination, even if you restrict the recursor so that the function to be iterated is closed when you reduce ("closed at reduction").  You have to restrict it so that recursion terms are disallowed entirely unless the function to be iterated is closed ("closed at construction").  But this prevents higher-order functions like map, which need to repeat a computation involving a variable f to be mapped over the elements of a list.  The solution is to allow schematic definition of terms, using schema variables ranging over closed terms.

    19 min

  5. 19/08/2025

    The Stunner: Linear System T is Diverging!

    In this episode, I shoot down last episode's proposal -- at least in the version I discussed -- based on an amazing observation from an astonishing paper, "Gödel’s system T revisited", by Alves, Fernández, Florido, and Mackie.  Linear System T is diverging, as they reveal through a short but clever example.  It is even diverging if one requires that the iterator can only be reduced when the function to be iterated is closed (no free variables).  This extraordinary observation does not sink Victor's idea of basing type theory on a terminating untyped core language, but it does sink the specific language he and I were thinking about, namely affine lambda calculus plus structural recursion. My notes are here.

    21 min

  6. 01/08/2025

    Terminating Computation First?

    In this episode, I discuss an intriguing idea proposed by Victor Taelin, to base a logically sound type theory on an untyped but terminating language, upon which one may then erect as exotic a type system as one wishes.  By enforcing termination already for the untyped language, we no longer have to make the type system do the heavy work of enforcing termination.

    11 min

  7. 12/05/2025

    Correction: the Correct Author of the Proof from Last Episode, and an AI flop

    I correct what I said in the last episode about the author of the proof of FD from last episode based on intersection types.  I also describe AI flopping when I ask it a question about this.

    7 min

  8. 05/05/2025

    Krivine's Proof of FD, Using Intersection Types

    Krivine's book (Section 4.2) has a proof of the Finite Developments Theorem, based on intersection types.  I discuss this proof in this episode.

    22 min
Ver todo (181)

Acerca de

Aaron Stump talks about type theory, computational logic, and related topics in Computer Science on his short commute.

Información

  • Creador
    Aaron Stump
  • Años de actividad
    2019 - 2026
  • Episodios
    181
  • Clasificación
    Apto
  • Copyright
    © 2026 Iowa Type Theory Commute
  • Mostrar sitio web
    Iowa Type Theory Commute

También te podría interesar