[Agda] Level constraints

Martin Escardo m.escardo at cs.bham.ac.uk
Thu Nov 14 20:53:29 CET 2013


There is one more option, which I favour: Feferman's "typical 
ambiguity", with Harper's algorithm or similar.

The idea is that you just write "Set", perhaps many times in the same 
definition, and then Agda adds (different) indices as appropriate. This 
feels like working with type-in-type, but it is actually working with 
what we already have, with the difference that the universe levels are 
inferred rather than written down.

Moreover, it should be possible to be compatible with what we already 
have (perhaps writing e.g. Set_0 rather than Set if that's what you 
really mean). So, if you put levels i,j,k in your context and write 
Set_i, Set_{i \sqcup j}, etc. then it would work as it does now, but if 
you write Set in several places in the same definition, then it would 
invoke the typical ambiguity conventions and algorithm to fill in the 
missing indices and the missing indices. This should make things much 
easier, very much in the spirit of implicit arguments.

Let Agda do the laborious, but routine, work of figuring out and writing 
down (implicitly) the optimal levels, and in cases where you want to be 
in control, use the current system (perhaps improved by cumulativity as 
below).

Currently, definitions with levels tend to obscure the essential aspects 
of types with an excessive amount of clutter, which is formally 
necessary but also distracting.

M.

On 14/11/13 18:43, Nils Anders Danielsson wrote:
> On 2013-11-14 16:34, Christian Sattler wrote:
>> What do you think?
>
> There are many options (at least if we restrict the discussion to
> lifting):
>
> * The status quo.
>
> * Something like what you suggest.
>
> * Some kind of cumulativity.
>
> * Conor's lifting primitive (Crude but Effective Stratification,
>    http://sneezy.cs.nott.ac.uk/epilogue/?p=857.html).
>
> * Allowing the solver to produce non-unique solutions. (I believe that
>    Mattieu has implemented something like this for Coq.)
>
> * …
>
> I think it would be interesting to see a careful discussion of the pros
> and cons of these different designs.
>

-- 
Martin Escardo
http://www.cs.bham.ac.uk/~mhe


More information about the Agda mailing list