The Coq mailing list

[Xavier Leroy <xavier.leroy AT college-de-france.fr>]

On Tue, Apr 2, 2019 at 4:39 PM Thorsten Altenkirch <Thorsten.Altenkirch AT nottingham.ac.uk> wrote:

Hi Xavier,

 

If you are not (yet) interested in logical consistency

Don't get me wrong: when I'm doing Coq proofs, I am very much interested in logical consistency; when I'm designing or teaching programming languages, nontermination is generally accepted.

 

then isn’t Type : Type better? At least there is no pretence of being consistent (or strongly normalising).

 

I call this “honest impredicativity”.

Personally I find the idea of programming languages with "Type:Type" interesting.  There was some work on this topic in the 80's, esp. by Cardelli (http://lucacardelli.name/Papers/TypeType.A4.pdf). 

The usual objection is that typechecking is undecidable.  The party line for typed programming languages is that they should be Turing-complete but have decidable type-checking, or maybe even type inference.  F_omega + general recursion fits this profile.

This said, OCaml's type checking is undecidable (at the level of modules), and so is Java's (at the level of generics), so there is also room for type systems with undecidable type-checking.

Best,

- Xavier

 

Cheers,

Thorsten

 

From: <coq-club-request AT inria.fr> on behalf of Xavier Leroy <xavier.leroy AT college-de-france.fr>
Reply-To: "coq-club AT inria.fr" <coq-club AT inria.fr>
Date: Tuesday, 2 April 2019 at 15:16
To: "coq-club AT inria.fr" <coq-club AT inria.fr>
Subject: Re: [Coq-Club] Impredicative Set

 

On Tue, Apr 2, 2019 at 3:42 PM Thorsten Altenkirch <Thorsten.Altenkirch AT nottingham.ac.uk> wrote:

 

Maybe you can tell us for what you actually want to use an impredicative universe?

 

The question is not addressed to me, but at any rate:

 

Impredicative systems such as F and F_omega may be questionable from a logical point of view, but make perfect sense as type systems for programming languages.  Haskell contains F_omega, OCaml contains F (in the core language) and bits of F_omega (at the module level).  Strong normalization doesn't really matter since those languages have general recursion to begin with.  But stratification by universes is not nice in programming languages: it gets in the way of some programming idioms, as JF Monin alluded to. 

 

Coming back to the original question, my only use for Coq's impredicative-Set option is to learn and teach about system F / F_omega and their impredicative encodings of data types.  I think Coq works better than Haskell or OCaml for this teaching purpose, as Coq's presentation of F_omega is closer to the textbook presentations.

 

Best,

 

- Xavier

 

 

Thorsten

On 15/03/2019, 18:35, "coq-club-request AT inria.fr on behalf of Jay Kruer" <coq-club-request AT inria.fr on behalf of kruerj AT reed.edu> wrote:

    Hi coq-club,

    I am wondering how “sketchy” the use of impredicative Set in Coq developments is considered. I have seen that impredicative Set is inconsistent with some axioms of classical mathematics (e.g. excluded middle), but for the careful user who avoids such axioms (or needs no axioms in their development at all) is there any reason to avoid it? The Coq reference manual alludes to some intuitionists taking issue with impredicative Set even before one introduces inconsistency with axioms but I haven't been able to find any of those arguments.

    Thanks,
    — Jay




This message and any attachment are intended solely for the addressee
and may contain confidential information. If you have received this
message in error, please contact the sender and delete the email and
attachment.

Any views or opinions expressed by the author of this email do not
necessarily reflect the views of the University of Nottingham. Email
communications with the University of Nottingham may be monitored
where permitted by law.

This message and any attachment are intended solely for the addressee
and may contain confidential information. If you have received this
message in error, please contact the sender and delete the email and
attachment. 

Any views or opinions expressed by the author of this email do not
necessarily reflect the views of the University of Nottingham. Email
communications with the University of Nottingham may be monitored 
where permitted by law.