Research Interests

My general research interests are in the study of programming languages, including their theory, semantics, design, and implementation. In particular, I am interested in the foundations of programming languages and their relation to logic and duality. I'm also interested in understanding aspects of practical languages including computational effects (like mutable state, exceptions, and first-class continuations) and evaluation strategies (strict versus lazy evaluation and memoization), as well as ways for languages to sensibly bridge between high-level abstractions and low-level details.

I am interested in an alternative model for computation based on the connection between programming languages and formal logic (known as the Curry-Howard correspondence or proofs-as-programs interpretation). With a single stroke in 1935, Gentzen laid out the basis for the modern study of formalized logic: natural deduction and the sequent calculus. On the one hand, natural deduction is the logic of the lambda calculus, which serves as the bedrock for functional programming languages (like Scheme, Haskell, and OCaml) and proof assistants (like Coq). On the other hand, the sequent calculus has only recently been connected with a lower-level model for programs that highlights the dualities present in programming languages and details such as evaluation strategies (like strict or lazy evaluation) and control-flow effects (like exceptions). I am interested in developing this view of computation to get another view of programs and languages from different angles:

  • A high-level calculus for reasoning about the behavior of programs (in a similar style as the lambda calculus) while also accounting for low-level details such as evaluation strategy and control flow.
  • A contextual representation of programs that allows for performing context-sensitive analysis and transformation of programs, as done by optimizing compilers like GHC.
  • A dualized framework that gives a symmetric and unified view of programming concepts, as a way to understand differences and similarities in language design, including types and abstraction mechanisms from both functional and object-oriented languages.

Some of these ideas have implemented in the form of a practical intermediate language for GHC, analogous to its Core representation, that can be used for analyzing and optimizing Haskell programs. The current version of Sequent Core can be found on Hackage as a plugin for GHC.

Teaching

My teaching has mainly focused on the theory and practice of programming languages, and how it helps us write better software. Courses I have designed and taught include:
  • Foundations of Programming Languages, an intensive introduction to the fundamentals of the theory of programming languages, for graduate students, advanced undergraduate students, and interested experts from other fields. This course was given at the Oregon Programming Languages Summer School 2017 and 2018.

  • Advanced Functional Programming, an application of advanced topics and techniques of functional programming for writing practical, interactive, and correct software. This course was given in Spring 2018.

I have also given lectures on the application of numerical methods with functional programming in Python, based on John Hughes' fantastic paper "Why Functional Programming Matters."

Publications

Journal Articles

  • Paul Downen and Zena M. Ariola. (2019). Compiling With Classical Connectives.
    (arXiv)

  • Paul Downen, Zena M. Ariola, and Silvia Ghilezan. (2019). The duality of classical intersection and union types. Fundamenta Informaticae, 170, 2019.
    (pdf)

  • Paul Downen, Philip Johnson-Freyd, and Zena M. Ariola. (2019). Abstracting models of strong normalization for classical calculi. Journal of Logical and Algebraic Methods in Programming, 2019.
    (pdf)

  • Paul Downen and Zena M. Ariola. (2018). A Tutorial on Computational Classical Logic and the Sequent Calculus. Journal of Functional Programming, 28, e3.
    (doi) (pdf+appendix)

  • Philip Johnson-Freyd, Paul Downen, and Zena M. Ariola. (2017). Call-by-Name Extensionality and Confluence. Journal of Functional Programming, 27, e12.
    (doi) (pdf+appendix)

  • Philip Johnson-Freyd, Paul Downen, and Zena M. Ariola. (2016). First class call stacks: Exploring head reduction. In Olivier Danvy and Ugo de'Liguoro: Proceedings of the Workshop on Continuations, London, UK, (WoC2015), Electronic Proceedings in Theoretical Computer Science, 212, pp. 18–35.
    (arXiv) (pdf)

  • Paul Downen and Zena M. Ariola. (2014). Delimited control and computational effects. Journal of Functional Programming, 24, pp 1-55.
    (doi) (pdf+appendix)

Conference and Workshop Papers

  • Paul Downen and Zena M. Ariola. (2020). A Computational Understanding of Classical (Co)Recursion. In Principles and Practice of Declarative Programming (PPDP2020).
    (doi) (pdf)

  • Paul Downen, Zena M. Ariola, Simon Peyton Jones, and Richard A. Eisenberg. (2020). Kinds Are Calling Conventions. In International Conference on Functional Programming (ICFP2020).
    (doi) (pdf)

  • Paul Downen, Zachary Sullivan, Zena M. Ariola, and Simon Peyton Jones. (2019). Making a Faster Curry with Extensional Types. In Haskell Symposium, Berlin, Germany (Haskell2019).
    (pdf)

  • Paul Downen, Zachary Sullivan, Zena M. Ariola, and Simon Peyton Jones. (2019). Codata in action. In European Symposium on Programming, Prague, Czech Republic (ESOP2019).
    (pdf)

  • Paul Downen and Zena M. Ariola. (2018). Beyond Polarity: Towards A Multi-Discipline Intermediate Language with Sharing. In Computer Science Logic, Birmingham, UK (CSL2018).
    (doi) (pdf) (pdf+appendix)

  • Paul Downen, Philip Johnson-Freyd, and Zena M. Ariola. (2018). Uniform Strong Normalization for Multi-Discipline Calculi. In International Workshop on Rewriting Logic and its Applications, Thessaloniki, Greece (WRLA2018).
    (pdf+appendix)

  • Luke Maurer, Paul Downen, Zena M. Ariola, and Simon Peyton Jones. (2017). Compiling without Continuations. In Programming Language Design and Implementation, Barcelona, Spain (PLDI2017). Best Paper Award.
    (acm) (doi) (pdf) (pdf+appendix)

  • Paul Downen, Luke Maurer, Zena Ariola, and Simon Peyton Jones. (2016). Sequent calculus as a compiler intermediate language. International Conference on Functional Programming, Nara, Japan (ICFP2016).
    (acm) (doi) (pdf) (appendix) (pdf+appendix)

  • Luke Maurer, Paul Downen, Zena Ariola, and Simon Peyton Jones. (2016). Administrative normal form, continued. Higher-Order Programming with Effects, Nara, Japan (HOPE2016).
    (pdf)

  • Paul Downen, Philip Johnson-Freyd, and Zena M. Ariola. (2015). Structures for structural recursion. International Conference on Functional Programming, Vancouver, BC, Canada (ICFP2015).
    (acm) (doi) (pdf) (extended)

  • Philip Johnson-Freyd, Paul Downen, and Zena M. Ariola. (2015). Control controls extensional execution. Higher-Order Programming with Effects, Vancouver, BC, Canada (HOPE2015).
    (pdf)

  • Paul Downen and Zena M. Ariola. (2014). Compositional semantics for composable continuations: from abortive to delimited control. International Conference on Functional Programming, Gothenburg, Sweden (ICFP2014).
    (acm) (doi) (pdf)

  • Paul Downen and Zena M. Ariola. (2014). Delimited control with multiple prompts in theory and practice. Higher-Order Programming with Effects, Gothenburg, Sweden (HOPE2014).
    (pdf)

  • Paul Downen, Luke Maurer, Zena M. Ariola, and Daniele Varacca. (2014). Continuations, processes, and sharing. Principles and Practice of Declarative Programming, Canterbury, UK (PPDP2014).
    (acm) (doi) (pdf)

  • Paul Downen and Zena M. Ariola. (2014). The duality of construction. European Symposium on Programming, Grenoble, France (ESOP2014).
    (doi) (pdf)

  • Zena M. Ariola, Paul Downen, Hugo Herbelin, Keiko Nakata, and Alexis Saurin. (2012). Classical call-by-need sequent calculi: The unity of semantic artifacts. International Symposium on Functional and Logic Programming, Kobe, Japan (FLOPS2012).
    (doi) (pdf)

  • Paul Downen and Zena M. Ariola. (2012). A Systematic Approach to Delimited Control with Multiple Prompts. European Symposium on Programming, Tallinn, Estonia (ESOP2012). Best Paper Award nominee.
    (doi) (pdf)

Unpublished Manuscripts

  • Paul Downen. Sequent Calculus: A Logic and a Language for Computation and Duality. (2017). Ph.D. thesis, University of Oregon.
    (pdf)

  • Paul Downen and Zena M. Ariola. A Polar Basis for Simple Types. (2017).
    (pdf)

  • Paul Downen. Computational Duality and the Sequent Calculus. (2014). Comprehensive Area Exam Report, University of Oregon.
    (pdf)

Presentations

Conference Talks

  • A Computational Understanding of (Co)Recursion.
    Venue: Principles and Practice of Declarative Programming. September 10, 2020.
    Slides: (pdf)
    Video (mp4)

  • Kinds are Calling Conventions.
    Venue: International Conference on Functional Programming. August 27, 2020.
    Slides: (pdf)
    Video (mp4)

  • Codata in action.
    Venue: European Symposium on Programming, Prague, Czech Republic. April 8, 2019.
    Slides: (pdf)

  • Beyond Polarity: Towards A Multi-Discipline Intermediate Language with Sharing.
    Venue: Computer Science Logic, Birmingham, UK. September 4, 2019.
    Slides: (pdf)

  • Sequent calculus as a compiler intermediate language.
    Venue: International Conference on Functional Programming, Nara, Japan. September 19, 2016.
    Slides: (pdf)
    Video: (youtube)

  • Structures for structural recursion.
    Venue: International Conference on Functional Programming, Vancouver, BC, Canada. August 31, 2015.
    Slides: (pdf)
    Video: (youtube)

  • Continuations, processes, and sharing.
    Venue: Principles and Practice of Declarative Programming, Canterbury, UK. September 8, 2014.
    Slides: (pdf)

  • Compositional Semantics for Composable Continuations: From Abortive to Delimited Control.
    Venue: International Conference on Functional Programming, Gothenburg, Sweden. September 1, 2014.
    Slides: (pdf)
    Video: (youtube)

  • The duality of construction.
    Venue: European Symposium on Programming, Grenoble, France. April 9, 2014.
    Slides: (pdf)

  • A Systematic Approach to Delimited Control with Multiple Prompts.
    Venue: European Symposium on Programming, Tallinn, Estonia. March 26, 2012.
    Slides: (pdf)

Workshop Talks

  • Control controls extensional execution.
    Venue: Higher-Order Programming with Effects, Vancouver, BC, Canada. August 30, 2015.
    Slides: (pdf)

  • Delimited control with multiple prompts in theory and practice.
    Venue: Higher-Order Programming with Effects, Gothenburg, Sweden. August 31, 2014.
    Slides: (pdf)
    Video: (youtube)

Invited Talks

  • Kinds Are Calling Convnetions: Intensional Static Polymorphism.
    Venue: Principles of Programming and Verification, Boston University, Boston, MA. November 17, 2020.
    Slides: (pdf)

  • Beyond Polarity: Towards A Multi-Discipline Intermediate Language with Sharing.
    Venue: University of Cambridge, UK. September 11, 2019.
    Venue: Microsoft Research, Cambridge, UK. September 10, 2019.
    Slides: (pdf)

  • The structures of induction and co-induction.
    Venue: Microsoft Research Lecture, Cambridge, UK. September 17, 2015.

  • The duality of construction.
    Venue: McGill University, Montreal, QC, Canada. November 6, 2014.

  • Building up delimited control with multiple prompts.
    Venue: INRIA Preuves, Programmes et Systèmes, Théorie des types et réalisabilité, Paris, France. December 19, 2012.

  • Opening the Black Box: Profiling Computer Memory.
    Venue: Lawrence Technological University, Arts and Science Seminar Series, Southfield, MI, USA. February 11, 2010.