[Agda] Normalization by evaluation, plain Agda types and impredicativity.

flicky frans flickyfrans at gmail.com
Sun Sep 28 12:32:12 CEST 2014


Hello. I am searching for a paper, that describes normalization by
evaluation for roughly this representation of the lambda-calculus:

{-# OPTIONS --type-in-type #-}

mutual
  data Term : Set -> Set where
    ↑ : {A : Set} -> A -> Term A
    _·_ : {A : Set} {B : A -> Set}
        -> Term ((x : A) -> B x) -> (e : Term A) -> Term (B (eval e))
    ⇧ : {A : Set} {B : A -> Set}
      -> ((x : A) -> Term (B x)) -> Term ((x : A) -> B x)

  eval : ∀ {A} -> Term A -> A
  eval (↑ v)   = v
  eval (f · x) = eval f (eval x)
  eval (⇧ f)   = λ x -> eval (f x)

I've searched, but haven't found any NbE algorithm for representation,
that contains dependent meta-language types. I wrote one [1] and want
to study other approaches, if they exist.

Also, there are a lof of `subst`s in normalized terms in my code,
probably because of the postulated functional extensionality axiom. Is
it possible to remove them without searching for another proof of the
`eval∘reify∘reflect` lemma? I could "prove" `fun-ext` from Girard's
paradox, but that's very dirty.

[1] http://lpaste.net/111763


More information about the Agda mailing list