Smart Case [Re: [Agda] A puzzle with "with"]
Thorsten Altenkirch
txa at Cs.Nott.AC.UK
Sat Jul 4 23:13:22 CEST 2009
>>> Consider the booleans with identity and negation defined by case
>>> distinction. Then, the constraints
>>>
>>> id x = true
>>> not x = true
>> I don't understand this, since "id x" is not normal, but if we
>> reduce it it becomes x=true and hence not x reduces to false and
>> this is inconsistent.
>
> I think you should read Andreas' statement as "(identity and negation)
> defined by case distinction", not "identity and (negation defined by
> case distinction)".
Yes, we discussed this already offline. Here is the relevant part of
our exchange:
>> I meant identity also defined by cases,
>>
>> id true = true
>> id false = false
>>
>> Then, id x is neutral.
>
> Yes, but then the inconsistency is not derivable unless you assume
> strong equality for coproducts.
>
> So what is the problem?
>>
>> Or take something more complicated like
>>
>> prime n = true
>> composite n = true
>>
>> Agda cannot know that a number cannot be both prime and composite.
>>
>> In the complicated case, it is sufficiently clear to the user that
>> Agda can't do magic. In the simple case above it might not be so
>> clear, but that is just tough luck.
>
> I think the spec is quite clear (see our paper). We use the usual
> rules of lambda calculus to derive consequences from the equational
> assumptions. But already this is quite difficult.
>
>> Did you do any models for type theory with constraints which can be
>> used to prove termination?
>
> We were looking at algorithms to handle constraints using big step
> normalisation. Basically, when you get stuck on a neutral term you
> check whether it matches any of your constraints (which are always
> of the form neutral -> constructor) using equality. To prove
> normalisation will be tricky but we were most interested in
> completeness which is already quite difficult.
>
This message has been checked for viruses but the contents of an attachment
may still contain software viruses, which could damage your computer system:
you are advised to perform your own checks. Email communications with the
University of Nottingham may be monitored as permitted by UK legislation.
More information about the Agda
mailing list