Знакомство с Lift и Setω, а также с появлением переменных в выражениях

Question

В предыдущем вопросе у меня были типы для игрушечного языка

data Type : Set where
  Nat  : Type
  Prp : Type

Я думал о том, чтобы интерпретировать их, используя несвязанный союзType → Set ⊎ Set₁, но подъем уровня мышления был бы лучшим и помог получить

⟦_⟧ₜ : Type → Set₁
⟦ Nat ⟧ₜ = Lift ℕ
⟦ Prp ⟧ₜ = Set

Теперь предположим, что мой игрушечный язык имеет переменные и выражения

data Variable : Type → Set where
  x y : ∀ {t} → Variable t

data Expr : Type → Set₁ where
  Var : ∀ {t} (v : Variable t) → Expr t      -- varaible symbols
   : ℕ → Expr Nat                         -- constant symbols
   : Set → Expr Prp
  _+_ : (m n : Expr Nat) → Expr Nat          -- binary function symbol
  _≈_ : (e f : Expr Nat) → Expr Prp          -- binary relation symbol

Тогда семантика выражений,

State = ∀ {t} → Variable t → ⟦ t ⟧ₜ

⟦_⟧ₑ : ∀ {t} → Expr t → State → ⟦ t ⟧ₜ
⟦_⟧ₑ (Var v)  σ = σ v
⟦_⟧ₑ ( q)   σ = lift q
⟦_⟧ₑ ( p)   σ = p
⟦_⟧ₑ (e + e₁) σ = lift $ lower (⟦ e ⟧ₑ σ) +ℕ     lower (⟦ e₁ ⟧ₑ σ)
⟦_⟧ₑ (e ≈ e₁) σ = lift (lower (⟦ e ⟧ₑ σ)) ≡ lift (lower (⟦ e₁ ⟧ₑ σ))

Я вроде понимаю, что в целом lift (lower x) ≠ x из-за "обновления уровня" из-за lift, но все же почему последняя строка просто не может быть ⟦ e ⟧ₑ σ ≡ ⟦ e₁ ⟧ₑ σ?

Я должен признать, что это мой первый раз, используя Lift и, к сожалению, не нашел учебника / объяснения по этому поводу - кроме идеи, что он встраивает мелкие типы в большие типы, как указано в его определении.

---

Поскольку я все изложил, позвольте мне сделать довольно конкретный запрос.

Со стандартными / производными равенствами,

-- no quick `deriving Eq' mechanism, yet.
postulate _≟ₜ_ : Decidable {A = Type} _≡_   
postulate _≟ᵥ_ : ∀ {t s} → Variable t → Variable s → Bool

Я могу определить текстовую подстановку над выражениями,

_[_/_] : ∀ {s t} → Expr t → Variable s → Expr s → Expr t
_[_/_] {s} {t} (Var v) u e with s ≟ₜ t
Var v [ u / e ] | yes refl = if v ≟ᵥ u then e else Var v
Var v [ u / e ] | no ¬p = Var v
 n [ v / e ] =  n
 p [ v / e ] =  p
(E + F) [ v / e ] = E [ v / e ] + F [ v / e ]
(E ≈ F) [ v / e ] = E [ v / e ] ≈ F [ v / e ]

Теперь проблема вхождений переменных в выражениях.

_not-occurs-in₀_ : ∀ {t} → Variable t → Expr t → Set₁
v not-occurs-in₀ E = ∀ {e} → E [ v / e ] ≡ E

_not-occurs-in₁_ : ∀ {t} → Variable t → Expr t → Set₁
v not-occurs-in₁ E = ∀ {e} {σ : State} → ⟦ E [ v / e ] ⟧ₑ σ ≡ ⟦ E ⟧ₑ σ

У меня были проблемы с использованием любого определения. В частности, я не мог даже определить одно в терминах другого. Любая помощь в этом будет оценена!

---

После некоторого копания я попытался

levelOf : Type → Level
levelOf Nat = zero
levelOf Prp = suc zero

New⟦_⟧ₜ : (t : Type) → Set (levelOf t)
New⟦ Nat ⟧ₜ = ℕ
New⟦ Prp ⟧ₜ = Set    

Тем не менее, теперь я получаю Setω ошибки в определении State выше! То есть,

-- works fine if i use the risky {-# OPTIONS --type-in-type #-}
NState = {t : Type} → Variable t → New⟦ {!t!} ⟧ₜ

Насколько я знаю, такая ошибка возникает, примерно, при назначении уровней вселенным.

Какие махинации я неосознанно делаю, чтобы получить эту проблему?

Answer 1

Напомним, что Set₁ ∋ Lift ℕ ∋ ⟦ e ⟧ₑ σ а также Set α ∋ (Set α ∋ A ∋ x) ≡ (Set α ∋ A ∋ y), где _∋_ от Function модуль:

infixl 0 _∋_
_∋_ : ∀ {a} (A : Set a) → A → A
A ∋ x = x

Отсюда и выражение ⟦ e ⟧ₑ σ ≡ ⟦ e₁ ⟧ₑ σ заключается в Set₁ (потому что типы ⟦ e ⟧ₑ σ а также ⟦ e₁ ⟧ₑ σ роды Set₁), пока вам нужно, чтобы он был в Set, Вы можете написать

⟦_⟧ₑ (e ≈ e₁) σ = lower (⟦ e ⟧ₑ σ) ≡ lower (⟦ e₁ ⟧ₑ σ)

или переопределить _≡_ использование новой функции, которая позволяет "вытеснять" уровни, которые появляются только в типах параметров и индексов типа данных:

data _≡′_ {a} {A : Set a} (x : A) : A → Set where
  refl′ : x ≡′ x

Обратите внимание Set вместо Set a, Тогда это

⟦_⟧ₑ (e ≈ e₁) σ = ⟦ e ⟧ₑ σ ≡′ ⟦ e₁ ⟧ₑ σ

Я выберу первый вариант.

---

Ваш _not-occurs-inₙ_ не совсем не происходит, так как e может быть Var v а также E [ v / Var v ] ≡ E несмотря на погоду v происходит в E или нет. Почему бы не определить _not-occurs-in_ как тип данных? Кстати, я думаю, что было бы более стандартным произносить замены либо как E [ v ≔ e ] или же [ e / v ] E,

Вы можете перейти от _not-occurs-in₀_ в _not-occurs-in₁_ как это:

+-inj : ∀ {E₁ E₂ E₃ E₄} -> E₁ + E₂ ≡ E₃ + E₄ -> E₁ ≡ E₃ × E₂ ≡ E₄ 
+-inj refl = refl , refl

≈-inj : ∀ {E₁ E₂ E₃ E₄} -> E₁ ≈ E₂ ≡ E₃ ≈ E₄ -> E₁ ≡ E₃ × E₂ ≡ E₄ 
≈-inj refl = refl , refl

coe : ∀ {t s} {v : Variable t} → (E : Expr s) → v not-occurs-in₀ E → v not-occurs-in₁ E
coe {t} {v} (Var w)  q {e} rewrite q {e} = refl
coe ( n)  q = refl
coe ( p)  q = refl
coe (E + E₁) q =
  cong₂ (λ n m → lift $ lower n +ℕ lower m) (coe E (proj₁ (+-inj q))) (coe E₁ (proj₂ (+-inj q)))
coe (E ≈ E₁) q =
  cong₂ (λ p₁ p₂ → lower p₁ ≡ lower p₂) (coe E (proj₁ (≈-inj q))) (coe E₁ (proj₂ (≈-inj q)))

---

Невозможно дать имя типу ∀ α -> Set (f α) потому что этот тип не имеет типа в Agda, как объяснено в ссылке, которую вы упомянули. Но вы можете немного преобразовать выражение, чтобы получить функцию:

F : ∀ α -> Set (suc (f α))
F α = Set (f α)

Используя то же преобразование, вы можете определить NState а также ⟦_⟧ₑ:

NState : ∀ t → Set (levelOf t)
NState t = Variable t → New⟦ t ⟧ₜ

⟦_⟧ₑ : ∀ {t} → Expr t → (∀ {t} -> NState t) → New⟦ t ⟧ₜ
⟦_⟧ₑ (Var v)  σ = σ v
⟦_⟧ₑ ( q)   σ = q
⟦_⟧ₑ ( p)   σ = p
⟦_⟧ₑ (e + e₁) σ = ⟦ e ⟧ₑ σ +ℕ ⟦ e₁ ⟧ₑ σ
⟦_⟧ₑ (e ≈ e₁) σ = ⟦ e ⟧ₑ σ ≡ ⟦ e₁ ⟧ₑ σ

Попробуй уйти от текущего NState к вашему оригиналу NState чтобы увидеть проблему с последним: какой тип ∀ {t} -> NState t? Set применяется к чему? Тип NState t зависит от t, но когда t повсеместно количественно эта зависимость не может быть отражена на уровне типа.

Было бы неплохо написать

syntax (∀ {t} -> NState t) = State

но Агда не позволяет этого.

Кстати, в теории вселенная вселенных (т.е. Setω) существует: это супер вселенная. Хоть, Setω это неудачное название, потому что такая вселенная не Set - это больше, чем любой Setпотому что он содержит их всех. Вы можете найти эти идеи, выраженные в Агде здесь.

Код.