[Agda] about `abstract'
Sergei Meshveliani
mechvel at botik.ru
Mon Feb 29 14:27:51 CET 2016
People,
consider the following example.
------------------------------------------------------- M.agda ----
module M where
open import Relation.Binary.PropositionalEquality as PE using (_≡_)
open import Data.Nat using (ℕ; suc)
_+_ : ℕ → ℕ → ℕ
0 + n = n
suc m + n = suc (m + n)
------------------------------------------------------- M0.agda ---
module M0 where
open import Relation.Binary.PropositionalEquality as PE using (_≡_)
open import Data.Nat using (suc)
open import M using (_+_)
abstract
+0 : ∀ n → n + 0 ≡ n
+0 0 = PE.refl
+0 (suc n) = PE.cong suc n+0≡n where
n+0≡n : n + 0 ≡ n
n+0≡n = +0 n
------------------------------------------------------- M1.agda ---
open import Relation.Binary.PropositionalEquality as PE using (_≡_)
open import M using (_+_)
open import M0 using (+0)
two+0 : 2 + 0 ≡ 2
two+0 = +0 2
========================================================
1. If I put M._+_ under `abstract', then M0.+0 would not type-check.
Because this proof cannot be constructed only from the signature of
_+_, it needs to operate with the implementation rules for _+_.
2. The given proof for two+0 is constructed only from the signature of
+0. Hence +0 can be placed under `abstract' (for this example).
Also I expect that the implementation part for +0 will not be used
anywhere in type-checking any future client function, the type checker
will be satisfied with the signature of +0.
Can you imagine the necessity of using the implementation rules for 0+
in type checking something?
3. I discover some functions in my application program which
a) have implementation that would not be necessary for type-checking
any reasonable future client function (similar as with the example of
+0),
b) when placed under `abstract' reduce greatly the type check cost of
the application.
Am I missing something?
4. My current application consists (approximately) of the modules
M1.agda ... M20.agda, M21.agda, M22.agda.
M1 ... M20, M21 are already type-checked, and M22 presents a cost
problem.
Checking M22 takes more than 180 minutes for 22Gb heap
(-M22G option) on a 32 Gb RAM machine
(I have interrupted it).
M22.g calls for (f x), where f is imported from a parametric module
defined in M21, f implements a certain equality proof.
If I put f (in M21) under 'abstract', then it is sufficient
(12 Gb) * (4 minutes) for type checking M22.
M22.g uses many structures and functions imported from M1 ... M21,
and I cannot predict which call is the most expensive when type-checking
g. There are several calls that look as dangerous as (f x).
So I set `anything' to almost each value defined under `let...in' in g.
Then -- it is type-checked in 4 minutes. Then I start removing
`anything' one by one. Finally it occurs that only a single call for
(f x) is responsible for this enormous type check cost.
Then, I remove `anything', and put M21.f under `abstract'.
(type-checking the calls of f it will need only to analyze the
signature of f).
And this has reduced the type-check cost more than 100 times.
5. Currently I am trying to use _interactive highlighting_ for finding
the above responsible call. I hope that it will highlight the place with
"(f x)" in the text of g and stand there for a long time.
If so, then this will reduce this messy procedure with setting/removing
`anything' (or `postulate') in many places.
What people would note concerning all this?
Thanks,
------
Sergei
More information about the Agda
mailing list