Research Interests

My current 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. 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.

Currently, I am investigating a new, 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.

I'm currently working on implementing an alternative to GHC's Core representation for analyzing and optimizing Haskell programs based on the sequent calculus. Sequent Core is a work in progress available now on Hackage as a plugin for GHC.

Publications

Journal Articles

  • 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 Articles

  • Paul Downen and Zena M. Ariola. (2018). Beyond Polarity: Towards A Multi-Discipline Intermediate Language with Sharing. In Computer Science Logic, Birmingham, United Kingdom (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).
    (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)

  • 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)

  • 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, 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).
    (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

  • 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

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

  • 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.