Помощь в проверке завершения Агды

Question

Предположим, мы определили функцию

f : N \to N
f 0 = 0
f (s n) = f (n/2) -- this / operator is implemented as floored division.

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

Answer 1

Средство проверки завершения Agda проверяет только структурную рекурсию (то есть вызовы, которые происходят со структурно меньшими аргументами), и нет способа установить это определенное отношение (например, _<_) подразумевает, что один из аргументов структурно меньше.

---

Отступление: аналогичная проблема возникает с проверкой позитивности. Рассмотрим стандартный тип данных с фиксированной точкой:

data μ_ (F : Set → Set) : Set where
  fix : F (μ F) → μ F

Агда отвергает это, потому что F не может быть положительным в первом аргументе. Но мы не можем ограничивать μ принимать только функции положительного типа или показывать, что некоторая функция определенного типа является положительной.

---

Как мы обычно показываем, что рекурсивные функции завершаются? Для натуральных чисел это тот факт, что если рекурсивный вызов происходит на строго меньшее число, мы в конечном итоге должны достичь нуля, и рекурсия останавливается; для списков то же самое верно для его длины; для множеств мы можем использовать строгое отношение подмножества; и так далее. Обратите внимание, что "строго меньшее число" не работает для целых чисел.

Свойство, которое разделяют все эти отношения, называется обоснованностью. Неформально говоря, отношение является обоснованным, если оно не имеет бесконечных нисходящих цепочек. Например, < на натуральные числа обоснованны, потому что для любого числа n:

n > n - 1 > ... > 2 > 1 > 0

То есть длина такой цепочки ограничена n + 1,

≤ на натуральные числа, однако, не является обоснованным:

n ≥ n ≥ ... ≥ n ≥ ...

И ни один не < по целым числам:

n > n - 1 > ... > 1 > 0 > -1 > ...

---

Это помогает нам? Оказывается, мы можем закодировать, что означает, что отношение является обоснованным в Agda, а затем использовать его для реализации вашей функции.

Для простоты я собираюсь испечь _<_ отношение в тип данных. Прежде всего, мы должны определить, что означает доступность номера: n доступно, если все m такой, что m < n также доступны. Это, конечно, останавливается на n = 0потому что нет m чтобы m < 0 и это утверждение тривиально.

data Acc (n : ℕ) : Set where
  acc : (∀ m → m < n → Acc m) → Acc n

Теперь, если мы можем показать, что все натуральные числа доступны, то мы показали, что < обоснован. Почему это так? Там должно быть конечное число acc конструкторы (т.е. без бесконечной нисходящей цепочки), потому что Agda не позволит нам написать бесконечную рекурсию. Теперь может показаться, что мы просто отодвинули проблему на шаг вперед, но написание доказательства обоснованности на самом деле является структурно рекурсивным!

Итак, имея в виду, вот определение < быть обоснованным:

WF : Set
WF = ∀ n → Acc n

И доказательство обоснованности:

<-wf : WF
<-wf n = acc (go n)
  where
  go : ∀ n m → m < n → Acc m
  go zero    m       ()
  go (suc n) zero    _         = acc λ _ ()
  go (suc n) (suc m) (s≤s m<n) = acc λ o o<sm → go n o (trans o<sm m<n)

Заметить, что go красиво структурно рекурсивный trans можно импортировать так:

open import Data.Nat
open import Relation.Binary

open DecTotalOrder decTotalOrder
  using (trans)

Далее нам нужно доказательство того, что ⌊ n /2⌋ ≤ n:

/2-less : ∀ n → ⌊ n /2⌋ ≤ n
/2-less zero          = z≤n
/2-less (suc zero)    = z≤n
/2-less (suc (suc n)) = s≤s (trans (/2-less n) (right _))
  where
  right : ∀ n → n ≤ suc n
  right zero    = z≤n
  right (suc n) = s≤s (right n)

И, наконец, мы можем написать f функция. Обратите внимание, как это внезапно становится структурно рекурсивным благодаря Acc: рекурсивные вызовы происходят по аргументам с одним acc конструктор отклеился

f : ℕ → ℕ
f n = go _ (<-wf n)
  where
  go : ∀ n → Acc n → ℕ
  go zero    _       = 0
  go (suc n) (acc a) = go ⌊ n /2⌋ (a _ (s≤s (/2-less _)))

---

Теперь приходится работать напрямую с Acc не очень приятно И вот тут-то и приходит ответ Доминика. Все, что я здесь написал, уже сделано в стандартной библиотеке. Это более общий Acc тип данных на самом деле параметризован через отношение), и это позволяет просто использовать <-rec не беспокоясь о Acc,

---

Если присмотреться поближе, мы на самом деле довольно близки к общему решению. Давайте посмотрим, что мы получим, когда мы параметризуем отношение. Для простоты я не имею дело с полиморфизмом вселенной.

Отношение на A это просто функция, принимающая два Aи возвращение Set (мы могли бы назвать это двоичным предикатом):

Rel : Set → Set₁
Rel A = A → A → Set

Мы можем легко обобщить Acc изменяя жестко закодированный _<_ : ℕ → ℕ → Set к произвольному отношению по некоторому типу A:

data Acc {A} (_<_ : Rel A) (x : A) : Set where
  acc : (∀ y → y < x → Acc _<_ y) → Acc _<_ x

Определение обоснованности меняется соответственно:

WellFounded : ∀ {A} → Rel A → Set
WellFounded _<_ = ∀ x → Acc _<_ x

Теперь, так как Acc является индуктивным типом данных, как и любой другой, мы должны быть в состоянии написать его элиминатор. Для индуктивных типов это складка (очень похоже на foldr является списывателем для списков) - мы сообщаем исключителю, что делать с каждым случаем конструктора, и устранитель применяет это ко всей структуре.

В этом случае у нас все будет хорошо с простым вариантом:

foldAccSimple : ∀ {A} {_<_ : Rel A} {R : Set} →
                (∀ x → (∀ y → y < x → R) → R) →
                ∀ z → Acc _<_ z → R
foldAccSimple {R = R} acc′ = go
  where
  go : ∀ z → Acc _ z → R
  go z (acc a) = acc′ z λ y y<z → go y (a y y<z)

Если мы знаем, что _<_ обоснованно, мы можем пропустить Acc _<_ z аргумент полностью, поэтому давайте напишем небольшую вспомогательную оболочку:

recSimple : ∀ {A} {_<_ : Rel A} → WellFounded _<_ → {R : Set} →
            (∀ x → (∀ y → y < x → R) → R) →
            A → R
recSimple wf acc′ z = foldAccSimple acc′ z (wf z)

И наконец:

<-wf : WellFounded _<_
<-wf = {- same definition -}

<-rec = recSimple <-wf

f : ℕ → ℕ
f = <-rec go
  where
  go : ∀ n → (∀ m → m < n → ℕ) → ℕ
  go zero    _ = 0
  go (suc n) r = r ⌊ n /2⌋ (s≤s (/2-less _))

И действительно, это выглядит (и работает) почти так же, как в стандартной библиотеке!

---

Вот полностью зависимая версия на случай, если вам интересно:

foldAcc : ∀ {A} {_<_ : Rel A} (P : A → Set) →
          (∀ x → (∀ y → y < x → P y) → P x) →
          ∀ z → Acc _<_ z → P z
foldAcc P acc′ = go
  where
  go : ∀ z → Acc _ z → P z
  go _ (acc a) = acc′ _ λ _ y<z → go _ (a _ y<z)

rec : ∀ {A} {_<_ : Rel A} → WellFounded _<_ →
      (P : A → Set) → (∀ x → (∀ y → y < x → P y) → P x) →
      ∀ z → P z
rec wf P acc′ z = foldAcc P acc′ _ (wf z)

Answer 2

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

Идея в том, что проблема заключается в том, что мы не можем n / 2 как-то "часть" n, Структурная рекурсия хочет разбить вещь на ее непосредственные части, но так, чтобы n / 2 является "частью" n это то, что мы бросаем друг друга suc, Но заранее не ясно, сколько бросить, мы должны осмотреться и попытаться выстроить все в ряд. Что было бы хорошо, если бы у нас был какой-то тип, у которого были конструкторы для "множественного числа" suc s.

Чтобы сделать проблему немного более интересной, давайте вместо этого попробуем определить функцию, которая ведет себя как

f : ℕ → ℕ
f 0 = 0
f (suc n) = 1 + (f (n / 2))

то есть, это должно быть так, что

f n = ⌈ log₂ (n + 1) ⌉

Теперь, естественно, приведенное выше определение не будет работать, по тем же причинам f не будет. Но давайте притворимся, что это так, и давайте исследуем, так сказать, "путь", что аргумент будет проходить через натуральные числа. Предположим, мы смотрим на n = 8:

f 8 = 1 + f 4 = 1 + 1 + f 2 = 1 + 1 + 1 + f 1 = 1 + 1 + 1 + 1 + f 0 = 1 + 1 + 1 + 1 + 0 = 4

так что "путь" 8 -> 4 -> 2 -> 1 -> 0, Как насчет, скажем, 11?

f 11 = 1 + f 5 = 1 + 1 + f 2 = ... = 4

так что "путь" 11 -> 5 -> 2 -> 1 -> 0,

Естественно, что здесь происходит, так это то, что на каждом шаге мы либо делим на 2, либо вычитаем один и делим на 2. Каждое естественное число, большее 0, может быть разложено таким образом уникальным образом. Если он четный, разделите на два и продолжите, если он нечетный, вычтите один, разделите на два и продолжите.

Итак, теперь мы можем точно видеть, как должен выглядеть наш тип данных. Нам нужен тип, который имеет конструктор, который означает "вдвое больше suc "и еще что значит" вдвое больше suc "плюс один", а также конструктор, который означает "ноль" suc s":

data Decomp : ℕ → Set where
  zero : Decomp zero
  2*_ : ∀ {n} → Decomp n → Decomp (n * 2)
  2*_+1 : ∀ {n} → Decomp n → Decomp (suc (n * 2))

Теперь мы можем определить функцию, которая разбивает натуральное число на Decomp что соответствует этому:

decomp : (n : ℕ) → Decomp n
decomp zero = zero
decomp (suc n) = decomp n +1

Это помогает определить +1 за Decomp s:

_+1 : {n : ℕ} → Decomp n → Decomp (suc n)
zero +1 = 2* zero +1
(2* d) +1 = 2* d +1
(2* d +1) +1 = 2* (d +1)

Учитывая Decomp мы можем сгладить его в натуральное число, которое игнорирует различия между 2*_ а также 2*_+1:

flatten : {n : ℕ} → Decomp n → ℕ
flatten zero = zero
flatten (2* p) = suc (flatten p)
flatten (2* p +1 = suc (flatten p)

И теперь это тривиально определить f:

f : ℕ → ℕ
f n = flatten (decomp n)

Это успешно проходит проверку завершения без проблем, потому что мы никогда не возвращаемся к проблемным n / 2, Вместо этого мы конвертируем число в формат, который напрямую представляет его путь через пространство номеров структурно рекурсивным способом.

Только недавно мне пришло в голову, что Decomp является порядковым представлением двоичных чисел. 2*_ "добавить 0 в конец / сдвиг влево на 1 бит" и 2*_+1 это "добавить 1 в конец / сдвиг влево на 1 бит и добавить один". Таким образом, приведенный выше код на самом деле показывает, что двоичные числа являются структурно рекурсивными по отношению к делению на 2, как и должно быть! Я думаю, это облегчает понимание, но я не хочу менять то, что уже написал, поэтому мы могли бы вместо этого сделать некоторое переименование: Decomp ~> Binary, 2*_ ~> _,zero, 2*_+1 ~> _,one, decomp ~> natToBin, flatten ~> countBits,

Answer 3

Приняв ответ Витуса, я обнаружил другой способ достижения цели доказательства завершения функции в Agda, а именно использование "размерных типов". Я даю свой ответ здесь, потому что он кажется приемлемым, а также для критики любых слабых мест этого ответа.

Размерные типы описаны: http://arxiv.org/pdf/1012.4896.pdf

Они реализованы в Agda, а не только в MiniAgda; см. здесь: http://www2.tcs.ifi.lmu.de/~abel/talkAIM2008Sendai.pdf.

Идея состоит в том, чтобы дополнить тип данных размером, позволяющим контролеру типов легче доказать завершение. Размер определяется в стандартной библиотеке.

open import Size

Мы определяем размерные натуральные числа:

data Nat : {i : Size} \to Set where
    zero : {i : Size} \to Nat {\up i} 
    succ : {i : Size} \to Nat {i} \to Nat {\up i}

Далее мы определяем предшественник и вычитание (monus):

pred : {i : Size} → Nat {i} → Nat {i}
pred .{↑ i} (zero {i}) = zero {i}
pred .{↑ i} (succ {i} n) = n 

sub : {i : Size} → Nat {i} → Nat {∞} → Nat {i}
sub .{↑ i} (zero {i}) n = zero {i}
sub .{↑ i} (succ {i} m) zero = succ {i} m
sub .{↑ i} (succ {i} m) (succ n) = sub {i} m n

Теперь мы можем определить деление с помощью алгоритма Евклида:

div : {i : Size} → Nat {i} → Nat → Nat {i}
div .{↑ i} (zero {i}) n = zero {i}
div .{↑ i} (succ {i} m) n = succ {i} (div {i} (sub {i} m n) n)

data ⊥ : Set where
record ⊤ : Set where
notZero :  Nat → Set
notZero zero = ⊥
notZero _ = ⊤

Мы даем деление на ненулевые знаменатели. Если знаменатель ненулевой, то он имеет вид b+1. Затем мы делаем divPos a (b+1) = div a b, так как div ab возвращает потолок (a/(b+1)).

divPos : {i : Size} → Nat {i} → (m : Nat) → (notZero m) → Nat {i}
divPos a (succ b) p = div a b
divPos a zero ()

В качестве вспомогательного:

div2 : {i : Size} → Nat {i} → Nat {i}
div2 n = divPos n (succ (succ zero)) (record {})

Теперь мы можем определить метод "разделяй и властвуй" для вычисления n-го числа Фибоначчи.

fibd : {i : Size} → Nat {i} → Nat
fibd zero = zero
fibd (succ zero) = succ zero
fibd (succ (succ zero)) = succ zero
fibd (succ n) with even (succ n)
fibd .{↑ i}  (succ {i} n) | true = 
  let
    -- When m=n+1, the input, is even, we set k = m/2
    -- Note, ceil(m/2) = ceil(n/2)
    k = div2 {i} n
    fib[k-1] = fibd {i} (pred {i} k)
    fib[k] = fibd {i} k
    fib[k+1] =  fib[k-1] + fib[k]
  in
    (fib[k+1] * fib[k]) + (fib[k] * fib[k-1])
fibd .{↑ i} (succ {i} n) | false = 
  let
    -- When m=n+1, the input, is odd, we set k = n/2 = (m-1)/2.
    k = div2 {i} n
    fib[k-1] = fibd {i} (pred {i} k)
    fib[k] = fibd {i} k
    fib[k+1] = fib[k-1] + fib[k]
  in
    (fib[k+1] * fib[k+1]) + (fib[k] * fib[k])

Answer 4

Вы не можете сделать это напрямую: проверка завершения Agda считает рекурсию приемлемой только для аргументов, синтаксически меньших. Однако стандартная библиотека Agda предоставляет несколько модулей для подтверждения завершения, используя обоснованный порядок между аргументами функций. Стандартный порядок на натуральных числах такой порядок и может быть использован здесь.

Используя код в Induction.*, Вы можете написать свою функцию следующим образом:

open import Data.Nat
open import Induction.WellFounded
open import Induction.Nat

s≤′s : ∀ {n m} → n ≤′ m → suc n ≤′ suc m
s≤′s ≤′-refl = ≤′-refl
s≤′s (≤′-step lt) = ≤′-step (s≤′s lt)

proof : ∀ n → ⌊ n /2⌋ ≤′ n
proof 0 = ≤′-refl
proof 1 = ≤′-step (proof zero)
proof (suc (suc n)) = ≤′-step (s≤′s (proof n))

f : ℕ → ℕ
f = <-rec (λ _ → ℕ) helper
  where
    helper : (n : ℕ) → (∀ y → y <′ n → ℕ) → ℕ
    helper 0 rec = 0
    helper (suc n) rec = rec ⌊ n /2⌋ (s≤′s (proof n))

Я нашел статью с некоторыми объяснениями здесь. Но там могут быть лучшие ссылки там.

Answer 5

Подобный вопрос появился в списке рассылки Agda несколько недель назад, и консенсус, похоже, заключался в том, чтобы Data.Nat элемент в Data.Bin а затем использовать структурную рекурсию для этого представления, которая хорошо подходит для работы под рукой.

Вы можете найти всю ветку здесь: http://comments.gmane.org/gmane.comp.lang.agda/5690

Answer 6

Вы можете избежать использования обоснованной рекурсии. Допустим, вы хотите функцию, которая применяется ⌊_/2⌋ на номер, пока не достигнет 0и собирает результаты. С {-# TERMINATING #-} Прагму это можно определить так:

{-# TERMINATING #-}
⌊_/2⌋s : ℕ -> List ℕ
⌊_/2⌋s 0 = []
⌊_/2⌋s n = n ∷ ⌊ ⌊ n /2⌋ /2⌋s

Второй пункт эквивалентен

⌊_/2⌋s n = n ∷ ⌊ n ∸ (n ∸ ⌊ n /2⌋) /2⌋s

Можно сделать ⌊_/2⌋s структурно рекурсивный, вставляя это вычитание:

⌊_/2⌋s : ℕ -> List ℕ
⌊_/2⌋s = go 0 where
  go : ℕ -> ℕ -> List ℕ
  go  _       0      = []
  go  0      (suc n) = suc n ∷ go (n ∸ ⌈ n /2⌉) n
  go (suc i) (suc n) = go i n

go (n ∸ ⌈ n /2⌉) n это упрощенная версия go (suc n ∸ ⌊ suc n /2⌋ ∸ 1) n

Некоторые тесты:

test-5 : ⌊ 5 /2⌋s ≡ 5 ∷ 2 ∷ 1 ∷ []
test-5 = refl

test-25 : ⌊ 25 /2⌋s ≡ 25 ∷ 12 ∷ 6 ∷ 3 ∷ 1 ∷ []
test-25 = refl

Теперь предположим, что вы хотите функцию, которая применяется ⌊_/2⌋ на номер, пока не достигнет 0и суммирует результаты. Это просто

⌊_/2⌋sum : ℕ -> ℕ
⌊ n /2⌋sum = go ⌊ n /2⌋s where
  go : List ℕ -> ℕ
  go  []      = 0
  go (n ∷ ns) = n + go ns

Таким образом, мы можем просто запустить нашу рекурсию в списке, который содержит значения, созданные ⌊_/2⌋s функция.

Более краткая версия

⌊ n /2⌋sum = foldr _+_ 0 ⌊ n /2⌋s

И вернемся к основательности.

open import Function
open import Relation.Nullary
open import Relation.Binary
open import Induction.WellFounded
open import Induction.Nat

calls : ∀ {a b ℓ} {A : Set a} {_<_ : Rel A ℓ} {guarded : A -> Set b}
      -> (f : A -> A)
      -> Well-founded _<_
      -> (∀ {x} -> guarded x -> f x < x)
      -> (∀ x -> Dec (guarded x))
      -> A
      -> List A
calls {A = A} {_<_} f wf smaller dec-guarded x = go (wf x) where
  go : ∀ {x} -> Acc _<_ x -> List A
  go {x} (acc r) with dec-guarded x
  ... | no  _ = []
  ... | yes g = x ∷ go (r (f x) (smaller g))

Эта функция делает то же самое, что и ⌊_/2⌋s функция, то есть создает значения для рекурсивных вызовов, но для любой функции, которая удовлетворяет определенным условиям.

Посмотрите на определение go, Если x не является guardedзатем вернитесь [], В противном случае готовый x и позвонить go на f x (мы могли бы написать go {x = f x} ...), что конструктивно меньше.

Мы можем переопределить ⌊_/2⌋s с точки зрения calls:

⌊_/2⌋s : ℕ -> List ℕ
⌊_/2⌋s = calls {guarded = ?} ⌊_/2⌋ ? ? ?

⌊ n /2⌋s возвращается [], только когда n является 0, так guarded = λ n -> n > 0,

Наше обоснованное отношение основано на _<′_ и определено в Induction.Nat модуль как <-well-founded,

Итак, мы имеем

⌊_/2⌋s = calls {guarded = λ n -> n > 0} ⌊_/2⌋ <-well-founded {!!} {!!}

Тип следующего отверстия {x : ℕ} → x > 0 → ⌊ x /2⌋ <′ x

Мы можем легко доказать это утверждение:

open import Data.Nat.Properties

suc-⌊/2⌋-≤′ : ∀ n -> ⌊ suc n /2⌋ ≤′ n
suc-⌊/2⌋-≤′  0      = ≤′-refl
suc-⌊/2⌋-≤′ (suc n) = s≤′s (⌊n/2⌋≤′n n)

>0-⌊/2⌋-<′ : ∀ {n} -> n > 0 -> ⌊ n /2⌋ <′ n
>0-⌊/2⌋-<′ {suc n} (s≤s z≤n) = s≤′s (suc-⌊/2⌋-≤′ n)

Тип последней лунки (x : ℕ) → Dec (x > 0)мы можем заполнить его _≤?_ 1,

И окончательное определение

⌊_/2⌋s : ℕ -> List ℕ
⌊_/2⌋s = calls ⌊_/2⌋ <-well-founded >0-⌊/2⌋-<′ (_≤?_ 1)

Теперь вы можете записаться на список, составленный ⌊_/2⌋s, без каких-либо вопросов прекращения.

Answer 7

---

Я столкнулся с такой проблемой при попытке написать функцию быстрой сортировки в Agda.

В то время как другие ответы, кажется, объясняют проблему и решения в более общем плане, исходя из фона CS, я думаю, что следующая формулировка будет более доступной для определенных читателей:

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

Предположим, мы хотим определить функцию

      func : Some-Recursively-Defined-Type → A 
func non-recursive-case = some-a 
func (recursive-case n) = some-other-func (func (f n)) (func (g n)) ...

Во многих случаях мы, писатели, знаем,f nиg nбудут меньше , чемrecursive-case n. Кроме того, доказательства того, что они меньше , не так уж и сложны. Проблема больше в том, как мы можем передать это знание Агде.

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

      Timer : Type
Timer = Nat

measure : Some-Recursively-Defined-Type → Timer
-- this function returns an upper-bound of how many steps left to terminate
-- the estimate should be tight enough for the non-recursive cases that
--    given those estimates, 
--    pattern matching on recursive cases is obviously impossible
measure = {! !}

func-aux : 
  (timer : Timer)        -- the timer, 
  (actual-arguments : Some-Recursively-Defined-Type)
  (timer-bounding : measure actual-arguments ≤ timer)
  → A
func-aux zero non-recursive-case prf = a  
  -- the prf should force args to only pattern match to the non-recursive cases
func-aux (succ t) non-recursive-case prf = a
func-aux (succ t) (recursive-case n) prf = 
  some-other-func (func-aux t (f n) prf') (func-aux t (g n) prf'') ... where 

    prf' : measure (f n) ≤ t
    prf' = {! !}

    prf'' : measure (g n) ≤ t
    prf'' = {! !}

Имея это под рукой, мы можем определить нужную функцию примерно так:

      func : Some-Recursively-Defined-Type → A
func x with measure x
func x | n = func-aux n x (≤-is-reflexive n)

Предостережение

1. Я не принял во внимание ничего о том, будет ли вычисление эффективным.
2. ПокаTimerтип не ограничен бытьNat(но для всех типов, с которыми у нас достаточно сильное отношение порядка для работы), я думаю, можно с уверенностью сказать, что мы не много выиграем, даже если принять во внимание такую ​​общность.