[Agda] type check performance

Sergei Meshveliani mechvel at botik.ru
Fri Jan 13 20:13:41 CET 2017


On Fri, 2017-01-13 at 12:00 -0500, Jacques Carette wrote:
> Investigate what "open ... public" does.  This is useful to 'flatten' 
> hierarchies.


The code in my last letter does make use of  open-public.
Thus in the function

  f : ∀ {α α=} → (upR : UpCommutativeRing α α=) →
                 UpCommutativeRing.Carrier upR  →
                 UpCommutativeRing.Carrier upR

  f upR a =  let open UpCommutativeRing upR
             in  a + (a * a + 1#)


Carrier, +, *, 1#  are not operations in  UpCommutativeRing.

This structure definition is
 
 record UpCommutativeRing (α α= : Level) :  Set _
   where
   constructor upCommRing′

   field  upRingWithOne   : UpRingWithOne α α=
          commutativeRing : CommutativeRing upRingWithOne

   open CommutativeRing commutativeRing public hiding (upRingWithOne)


CommutativeRing  also does not have them, instead it (besides having
operations of its own) declares open-public for certain lower level
structures, and so on.
So that
1# appears only at the level of RingWithOne, and comes as 
   (Monoid._∙_ *monoid).
_+_ appears only from Ringoid, and is substituted as  
    (Magma._∙_ +magma).
 
and Carrier appears only at the lowest level of  (Dec)Setoid.

Each of these operations is declared only once in one place in the
hierarchy.
So, I have an impression that open-public does not help to have a type
expression printing size comparable to the one of Standard library.

One of the differences to Standard library is that  Standard library
re-declares some operations.
For example, Setoid declares Carrier and _≈_.  
And DecSetoid re-declares these two, and also adds  isDecEquivalence.
And Semigroup re-declares these two, and also adds  _∙_ and isSemigroup.
And Monoid  re-declares Carrier, _≈_, _∙_,  
            and adds  ε  and  isMonoid.
And so on.
This re-declaring looks strange to me. I suspected that this was set
according some subtle considerations about type expressions size.

I always thought that I need another approach. Because DoCon-A has more
levels and more operations at each level, and such a re-declaring will
probably lead to exponentially grown code, the program will hardly be
possible to read even to myself.

Now, the type sizes, and the type check cost are this way ...

I do not know of whether it is due to different architecture or due to
other features (there are a lot of proofs, some additional
operations).  

I also do not understand of whether this can, in principle, be
essentially improved by fixing the type checker. 
Or may be, a machine checking of some full formal constructive proof of
a small size may require exponentially large cost as minimum.
I just suspect that this particular DoCon-A-0.04.1 can be type-checked
in  500 Mb * 10 minutes  on a 3 GHz computer,  if only Agda is somehow
optimized.

The current simplest question is:  

why the above  type(f) related to CommutativeRing  is printed about 10
times shorter for Standard library,
and whether this size difference has a real relation to the type check
cost.

Regards,

------
Sergei

 
 




> 
> 
> On 2017-01-13 11:47 AM, Sergei Meshveliani wrote:
> > Am I missing something?
> > Why does not it mention the intermediate structure names, like
> > Semigroup, Group, AbelianGroup ... ?
> >
> >
> 
> 




More information about the Agda mailing list