[solved] sequent calculus as programming language - MathOverflow

[solved] sequent calculus as programming language

2010-06-26T05:31:17Z

intuitionistic logic ~ programming

natural deduction ~ lambda-calculus

Hilbert system ~ combinatory logic {S, K}

Gentzen system=sequent calculus ~ ?

What would you write in place of the question mark?

Update 0: Common mathematical tree notation for proofs is too cumbersome and redundant. I need a language as compact as e.g.:

data Proof = Apply Proof Proof | S | K {- Haskell, combinatory logic -}

Update 1: After following the links suggested by commentators I found this perfectly concrete and accessible article: "Hugo Herbelin. A Lambda-calculus Structure Isomorphic to Gentzen-style Sequent Calculus Structure." There, "?" language is named "the usual interpretation of LJ cut-free proofs by normal lambda-terms", i.e. is made out of lambda-calculus.

Answer by supercooldave for [solved] sequent calculus as programming language

2010-06-26T09:21:58Z

To answer your question about representing sequent calculi proofs in a computer, you need to look at the Curry-Howard isomorphism. Formula in a sequent are annotated with terms and the sequent calculus for intuitionistic logic resembles the type rules for the typed lambda calculus. If you want to manipulate this, then you need to record the assumptions (left-hand side of the turnstyle $\vdash$), which corresponds to recording the types of free variables. Then the right-hand side is a $\lambda$-term (describing the proof) and its type (the formula proven).

There's a vast amount of literature about this. The reference you probably want is A $\lambda$-calculus structure isomorphic to sequent calculus structure by Hugo Herbelin. The book by Morten Heine B. Sørensen and Pawel Urzyczyn is an extensive study of the topic. This kind of encoding is at the heart of proof assistants such as Coq.

Other possible correspondences include Sequent calculus ~ Abstract Machine. See Sequent calculi and abstract machines by Zena M. Ariola, Aaron Bohannon, Amr Sabry, ACM Transactions on Programming Languages and Systems (TOPLAS) Volume 31 , Issue 4 (May 2009). Or more generally, and perhaps more loosely, Sequent calculus ~ Operational Semantics. You also have proofs ~ processes, as explored by Abramsky and Saraswat, the latter in the context of concurrent constraint programming.

Answer by Neel Krishnaswami for [solved] sequent calculus as programming language

2010-06-26T10:59:19Z

There is no single answer to this question, because of the high degree of nondeterminism inherent in the sequent calculus -- to get a computational interpretation, you need to resolve the ambiguity, and each way of doing so leads to different operational interpretations. Furthermore, the answers differ somewhat for classical and intuitionistic sequent calculi.

Proof term assignments for classical sequent calculi correspond closely to continuation calculi, such as Herbelin's $\lambda\mu$ calculus. Now continuation transforms correspond to double-negation translations of classical logic into intuitionistic logic, and of there are many different double-negation translations possible. Each choice of double-negation translation gives rise to a different evaluation order, which explains why they are so valuable for the study for abstract machines (as in supercooldave's link) -- you can get the benefits of studying different evaluation orders via CPS transforms, without having to code everything up in functions.

Now, you can also try to eliminate the nondeterminism in another way: by fiat. This relies upon Andreoli's idea of focusing for linear logic. In operational terms, the idea is to define logical connectives either in terms of their values, or their elimination forms (this is called polarity). After picking one, the other is determined by the need to satisfy cut-elimination. For linear logic, each of the connectives has unique polarity. For classical logic, every connective can be given either polarity (ie, every connective can be defined either in terms of values or continuations), and the choice of polarities for the connectives essentially determines the evaluation order. This is very well explained in Noam Zeilberger's PhD thesis, http://www.cs.cmu.edu/~noam/thesis.pdf.

For intuitionistic sequent calculi, the proof term assignments still have a lot of nondeterminism in them. When you resolve this through focalization, you find that the resulting calculi are pattern matching calculi. A beautiful abstract take on this is also in Noam's thesis, and I wrote a very concrete paper about this for POPL 2009, "Focusing on Pattern Matching", which showed how to explain Haskell/ML style pattern matching in terms of proof term assignments for focused sequent calculi.

Answer by Noam Zeilberger for [solved] sequent calculus as programming language

2010-06-27T08:38:33Z

To add to Neel's response, you can't get a more concrete answer unless you clarify what you mean by "sequent calculus". If you mean Gentzen's original systems LK or LJ, then the answer is simply that there is no independently discovered/motivated computational system. (Remember that Gentzen's original motivation for introducing sequent calculus was as a tool for studying provability, and natural deduction as a tool for studying proofs.) Different operational interpretations have been associated with sequent calculus by departing from these original systems (or just by being satisfied with a looser "correspondence"), but then the questions are 1. whether you can really call these systems "sequent calculus" (what mathematical properties are invariant?), and 2. whether it really matters that you do?

On the other hand, there are still many aspects of proofs-as-programs that are not understood---as Neel and supercooldave mentioned, pattern-matching and operational semantics are examples---and people have tried to gain a handle on these by studying ideas from sequent calculus and from refinements of sequent calculus.

For example, one important idea from sequent calculus is the "subformula property", that a proof of a formula only needs to mention its subformulas. In natural deduction this property is broken for connectives like disjunction. The connection between focusing proofs and pattern-matching that Neel mentioned can be understood as a way of regaining this normal form property for programs with sum types.

Answer by RD1 for [solved] sequent calculus as programming language

2010-07-29T17:30:21Z

Some additional work on the pattern matching and cut elimination is that of Cerrito and Kesner:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.8703&rep=rep1&type=pdf

The work by Noam gives a more complete view though.

I often think of the situation as that there's clear and strong relationship, but (so far) we don't have a concrete syntax that works out as well as C-H does for introduction and elimination rules in natural deduction.