[Agda] strictness application not unifying in the typechecker

Ulf Norell ulf.norell at gmail.com
Wed Sep 7 07:19:50 CEST 2016


Unification is based on reduction, so since primForce x f doesn't
immediately reduce to f x (which is the whole point) they also don't unify.
To reason about programs using primForce you have to use primForceLemma,
something I think is pretty clear from the documentation. In your example
you can define wrap→dup as follows:

subst : {A : Set} (P : A → Set) {x y : A} → x ≡ y → P y → P x
subst P refl px = px

wrap→dup : ∀ {n : Nat} → (w : Wrap n) → Dup (unwrap w)
wrap→dup (wrap 0) = zero
wrap→dup (wrap (suc n)) = subst Dup (primForceLemma (unwrap (wrap n)) suc)
suc

/ Ulf

On Wed, Sep 7, 2016 at 3:43 AM, Martin Stone Davis <
martin.stone.davis at gmail.com> wrote:

> The typechecker seems unwilling to unify 'primForce x f' with 'f x', as
> the code below shows. Is this a bug in Agda? I.e. shouldn't it unify? I'm
> unclear. The documentation on strictness (at
> https://agda.readthedocs.io/en/latest/language/built-ins.html#strictness)
> mentions how it impacts on the compiler, but there seems to be no mention
> of how it works with the typechecker.
>
> I'm hoping that it *should* unify because I've run into a catch-22: I
> started using applications of strictness (Agda.Builtin.Strict.primForce)
> in order to try to reduce a space leak during typechecking. Unfortunately,
> doing so led to some typechecking errors. In the code below, 'unwrap'
> represents one of those functions that--I /think/---without an application
> of strictness, would result in a space leak (but with such an application,
> leads to typechecking errors further down). If Agda is behaving
> appropriately here, is there a clear way out of my dilemma? I.e. is there
> something I could change about 'wrap→dup' to get it to type-check?
>
>   open import Agda.Builtin.Strict using (primForce)
>   open import Agda.Builtin.Nat using (Nat; zero; suc)
>
>   infixr 0 _$!_
>   _$!_ : ∀ {a b} {A : Set a} {B : A → Set b} → (∀ x → B x) → ∀ x → B x
>   f $! x = primForce x f
>
>   data Wrap : Nat → Set where
>     wrap : (n : Nat) → Wrap n
>
>   data Dup : Nat → Set where
>     zero  : Dup zero
>     suc : ∀ {n : Nat} → Dup (suc n)
>
>   unwrap : ∀ {n : Nat} → Wrap n → Nat
>   unwrap (wrap 0) = 0
>   unwrap (wrap (suc n)) = Nat.suc $! (unwrap (wrap n))
>
>   wrap→dup : ∀ {n : Nat} → (w : Wrap n) → Dup (unwrap w)
>   wrap→dup (wrap 0) = zero
>   wrap→dup (wrap (suc n)) = suc
>   {- ERROR:
>        suc (_n_34 n) != primForce (unwrap (wrap n)) suc of type Nat
>        when checking that the expression suc has type
>        Dup (unwrap (wrap (suc n)))
>
>      No error if the strictness application is removed from 'unwrap'.
>   -}
>
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.chalmers.se/pipermail/agda/attachments/20160907/e8fd265c/attachment.html


More information about the Agda mailing list