[Agda] type check explosion

Sergei Meshveliani mechvel at botik.ru
Wed Feb 5 08:10:21 CET 2014


Dear Agda developers,

the issue 1041 on the bug tracker presents a full code showing a type
check explosion.

Main.agda  builds a certain table of pairs, which key type is a certain
record  R  defined in a complex way, and including other nested records.

The  value  field in each table item is of   Dec (RightQuotient ...)
-- a result of a certain partial division.

Now, 
(1) let the final test function only  map  isYes  to the value parts 
    in this table.
    Then  Main is type checked in
                                   1 sec.   

(2) Let the test only convert each value part from  (Dec ...)  into  
    Maybe R  in a simplest way.
    Then  Main is type checked in
                                   680 sec.   

(3) Let the test build a similar table where a key  has type 
                                                        R \times R 
    and the result pairs are then summed into one pair.   

    After  4500 seconds  the checker reports that  11 Gb space is not 
    enough.

(1) and (2) are presented on the tracker.
And (3) is a real example -- I could provide it, if asked.  


There is no code complexity difference in these programs except this:

  adding one constructor of  \times,
  adding a pattern 
                   f (x , yes (y ,_)) = .. just y.,   for  x y : R

-- small type changes in the main test, in Main.agda only.

It looks like each such additional constructor makes the  type check
cost  increase 5-20 times.  

Main.agda  demonstrates the cases  (1) and (2).

Can you, please, look into the code, and advise me how to essentially
reduce the type check expense in (2) ?

If I know how to optimize (2), then I could hope to also get the example
of (3) into the machine memory.  

For: how can I continue the project if I cannot type-check real
examples?


About module size
-----------------
People could say that I need to make the modules smaller.
But I suspect that they still are all right. 
(?)
Because
a) Euclidean1.agda  uses intensively all the others (except Main), 
   and still it is type-checked in a moment,
b) Main  is small,
c) each module is type-checked in a moment -- except Main.

But the type check cost seems depending in 5-20 times on each additional
constructor  (\times, Maybe ...)  and its related _pattern_  used in the
Main test.

Ulf Norell has demonstrated that a dummy record wrapper over R, reduces
the type-check cost about 100 times -- in my first example.
But 
* I failed to apply this approach to the example of (2),
* I do not think that this can be a regular programming style.

Please, advise,

------
Sergei



More information about the Agda mailing list