[Agda] Strange behaviour of instance search.

Andreas Abel abela at chalmers.se
Mon Jun 1 12:23:59 CEST 2015


Seems like you want to report an issue or add your description to the 
existing issues.

   https://code.google.com/p/agda/issues/list?q=label%3AInstance

On 01.06.2015 01:31, effectfully wrote:
> Hi. I want to adapt Conor McBride's trick
>
>      https://personal.cis.strath.ac.uk/conor.mcbride/fooling/Jigger.agda
>
> to basic encoding of STLC:
>
>      data _⊢_ Γ : Type -> Set where
>        var : ∀ {σ}   -> σ ∈ Γ     -> Γ ⊢ σ
>        ƛ_  : ∀ {σ τ} -> Γ ▻ σ ⊢ τ -> Γ ⊢ σ ⇒ τ
>        _·_ : ∀ {σ τ} -> Γ ⊢ σ ⇒ τ -> Γ ⊢ σ     -> Γ ⊢ τ
>
> I started from
>
>      _▻▻_ : Con -> Con -> Con
>      Γ ▻▻  ε      = Γ
>      Γ ▻▻ (Δ ▻ σ) = Γ ▻▻ Δ ▻ σ
>
>      postulate
>        naive-lam : ∀ {Γ σ τ} -> ((∀ {Δ} -> Γ ▻ σ ▻▻ Δ ⊢ σ) -> Γ ▻ σ ⊢
> τ) -> Γ ⊢ σ ⇒ τ
>
>      yellow : Term (ι ⇒ ι)
>      yellow = naive-lam λ x -> x
>
> But Agda can't infer `Δ' from (Γ ▻ σ ▻▻ Δ), since there is pattern
> matching on `Δ'.
> So I switched to instance arguments:
>
>      postulate
>        _extends_ : Con -> Con -> Set
>
>        instance
>          extends-stop : ∀ {Γ} -> Γ extends Γ
>          extends-skip : ∀ {Γ Δ σ} {{_ : Δ extends Γ}} -> (Δ ▻ σ) extends Γ
>
>        lam : ∀ {Γ σ τ} -> ((∀ {Δ} {{_ : Δ extends (Γ ▻ σ)}} -> Δ ⊢ σ)
> -> Γ ▻ σ ⊢ τ) -> Γ ⊢ σ ⇒ τ
>
>      I : Term (ι ⇒ ι)
>      I = lam λ x -> x
>
>      K : Term (ι ⇒ ι ⇒ ι)
>      K = lam λ x -> lam λ y -> x
>
> So far so good, but when I tried
>
>      A : Term ((ι ⇒ ι) ⇒ ι ⇒ ι)
>      A = lam λ f -> lam λ x -> f · x
>
> Agda just started to consume memory, and I killed the process after it
> had eaten 1+ GB of memory.
>
> But if I provide instance arguments explicitly
>
>      A : Term ((ι ⇒ ι) ⇒ ι ⇒ ι)
>      A = lam λ f -> lam λ x -> f {{extends-skip {{extends-stop}}}} · x
> {{extends-stop}}
>
> Agda happily accepts the definition.
>
> Is it the expected behaviour?
>
> The code: https://github.com/effectfully/random-stuff/blob/master/stuff/TypedJigger.agda
>
>
>
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda
>


-- 
Andreas Abel  <><      Du bist der geliebte Mensch.

Department of Computer Science and Engineering
Chalmers and Gothenburg University, Sweden

andreas.abel at gu.se
http://www2.tcs.ifi.lmu.de/~abel/


More information about the Agda mailing list