[Agda] type check performance
Sergei Meshveliani
mechvel at botik.ru
Thu Jan 12 19:35:26 CET 2017
On Wed, 2017-01-11 at 14:21 -0500, Wolfram Kahl wrote:
> On Wed, Jan 11, 2017 at 09:46:00PM +0300, Sergei Meshveliani wrote:
> > And my case is different. I define standard classical algebraic
> > structures: Semigroup, Group, Ring, EuclideanRing, and such, and prove
> > in Agda certain well-known properties of their operations. There cannot
> > appear such type expressions like above for id id ... id.
> >
> > And still its type check needs 7Gb RAM and 60 minutes of time (on a 3
> > GHz computer).
> >
> > [...]
> >
> > There is something strange in these 60 minutes and 7 Gb minimum.
> > For example, EuclideanRing is far enough in the hierarchy.
> > And I ask to print the type (C-c C-d) of the function (lemma)
> >
> > remByDivisor : (a b : C) → b ∣ a → eucRem a b ≈ 0#
> >
> > in the module parameterized by an instance of EuclideanRing.
> > It shows
> >
> > (a b : UpIntegralRing.Carrier upIR) →
> > (UpIntegralRing.*upMonoid upIR UpMonoid.∣ b) a →
> > (upIR UpIntegralRing.≈ EuclideanRing.eucRem upIR∣? E a b)
> > (UpIntegralRing.0# upIR)
> >
> > This does not look like a large expression
> > (though it contains several parts that may need to be replaced with
> > their expanded definitions, depending on situation).
>
> Can you go to the top-level of the file module in which this is defined,
> and ask for the type (C-c C-d) of the qualified name of remByDivisor,
> qualified as necessary to be able to refer to it from the top-level
> of the file module?
>
> And also do that for each of ∣ , eucRem , ≈ , and 0# ?
>
> If my understanding is correct, then at least in some circumstances
> and to a certain degree, these are the types that Agda is really dealing with.
>
I have there
--------------------------------------------
open import Level using (_⊔_)
...
...
module OfEuclideanRing {α α=} (upIR∣? : UpIntegralRing-with∣? α α=)
(open OverIntegralRing-0 upIR∣? using (EuclideanRing))
E : EuclideanRing)
where
upIR = proj₁ upIR∣?
_∣?_ = proj₂ upIR∣?
open UpIntegralRing upIR using
(setoid; ... _≈_; ... 0#; ... *upMonoid)
renaming (Carrier to C)
open UpMonoid *upMonoid using (_∣_; _∤_; ∣cong; ... ∣trans)
renaming (∣∙ to ∣*; _~asd_ to _~_)
...
open EuclideanRing E using (eucRem; ...)
...
remByDivisor : (a b : C) → b ∣ a → eucRem a b ≈ 0#
...
--------------------------------------------
I go to the beginning of this file and command
C-c C-d
remByDivisor
And it prints its type.
Now, try with the _∣_.
This _∣_ instance is opened from open UpMonoid *upMonoid,
and *upMonoid is opened from open UpIntegralRing upIR.
What expression need I to put to the C-c C-d input window?
I try
let *UM = UpIntegralRing.*upMonoid upIR in UpMonoid._∣_ *UM
It reports
---------------
Structures0.DSet.Carrier
(.Structures0.Magma.dS (Structures0.UpMagma.magma
(.Structures0a.UpSemigroup.upMagma
(UpMonoid.upSemigroup (UpIntegralRing.*upMonoid upIR))))) →
Structures0.DSet.Carrier
(.Structures0.Magma.dS (Structures0.UpMagma.magma
(.Structures0a.UpSemigroup.upMagma
(UpMonoid.upSemigroup (UpIntegralRing.*upMonoid upIR))))) →
Set (α= ⊔ α)
------------------
It searches down:
UpIntegralRing --> UpMonoid --> UpSemigroup --> UpMagma --> DSet -->
Carrier
for each argument in the signature of _∣_ -- as it was intended.
Further:
C-c C-d
EuclideanRing.eucRem E
leads to an error:
------------------
(OverIntegralRing-0.EuclideanRing upIR∣?) !=<
(Data.Product.Σ (UpIntegralRing (_α_0 upIR∣? E) (_α=_1 upIR∣? E))
(λ upR → Decidable₂ (Magma._∣_ (UpIntegralRing.*magma upR))))
of type (Set (α= ⊔ α))
when checking that the expression E has type
UpIntegralRing-with∣? (_α_0 upIR∣? E) (_α=_1 upIR∣? E)
------------------
E is a parameter in the head module, and eucRem is opened in
open EuclideanRing E ...
as shown above.
I wonder, why does this C-c C-d fail.
Thanks,
------
Sergei
More information about the Agda
mailing list