[Agda] Strange behaviour of instance search.
effectfully
effectfully at gmail.com
Mon Jun 1 01:31:27 CEST 2015
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
More information about the Agda
mailing list