[TYPES] Types theories with first-class definitional extensions

Jacques Carette carette at mcmaster.ca
Wed Nov 2 16:21:04 EDT 2016


Thanks for the many answers.  Some of my comments below could have been 
attached to other answers as well - I am not targetting CIC or 
transculent sums in particular!

On 2016-11-02 12:26 PM, William J. Bowman wrote:
> On Tue, Nov 01, 2016 at 10:43:44PM -0400, Jacques Carette wrote:
>> [ The Types Forum, http://lists.seas.upenn.edu/mailman/listinfo/types-list ]
>>
>> I am looking for literature on (higher-order, potentially dependent) type
>> theories where a context (telescope) can contain not just declarations, but
>> also definitions.
> I may misunderstand your question, but doesn't CIC have this (and other languages with dependent let)?
>
> The typing rule for dependent let adds a definition to the context:
>
> Δ;Γ ⊢ e : t
> Δ;Γ,x = e :t ⊢ e' : t
> ----------------------
> Δ;Γ ⊢ let x = e in e' : t[e/x]
>
> https://coq.inria.fr/refman/Reference-Manual006.html
>
> This also reminds me of translucency.
> A translucent type add a definition to the type declaration:
>
> (x = e : t) -> t'
> ∃ (x = e : t). t
>
> The original work on translucent sums:
> https://www.cs.cmu.edu/~rwh/theses/lillibridge.pdf
>
> I've also seen translucent functions here, which has a good explanation of translucency and more
> citations to chase:
> http://dl.acm.org/citation.cfm?id=237791
>

This seems really close, but there is something I don't see: how are the 
morphisms defined in the Contextual Category that corresponds to Coq's 
CIC's term language?  The 'obvious' definition of substitution works, 
but has very unpleasant properties, especially if you are trying to 
build a nice user interface.  The language of "with" for type signatures 
is very impoverished, and not up to the job of doing that.

It is not so much just having definitional extensions which are of 
interest (as that's been around for a long time), but having good 
behaviour, especially good *syntactic* behaviour, under repeated transport.

For an extreme example of this, see
     Adrian Mathias, A Term of Length 4,523,659,424,929 
<http://www.dpmms.cam.ac.uk/%7Eardm/inefff.dvi>, Synthese 133 (2002) 75--86.
     https://www.dpmms.cam.ac.uk/~ardm/inefff.pdf

Buried in an answer on
http://mathoverflow.net/questions/14356/bourbakis-epsilon-calculus-notation
you can also find similar numbers for ZFC.

Without care, the same can happen in a type theory, if definitional 
extensions are not treated as having important syntactic content, along 
with its (trivial!) semantic content.

Jacques


More information about the Types-list mailing list