Можно ли ввести min в теории нормализации, такой как System-F или Исчисление конструкций?

Это min определение ниже работает с двумя церковными числами и возвращает наименьшее значение. Каждое число становится продолжением, которое отправляет свое предысторию другому, зигзагообразно и загадочно, до тех пор, пока не будет достигнут ноль. Более того, одно из чисел добавляет f к результату каждый раз, когда он вызывается, так что в итоге у вас будет (\ f x -> f (... (f (f x)) ...)), где число 'f справа - это количество раз, когда было вызвано первое продолжение.

min a b f x = (a_continuator b_continuator)
    a_continuator = (a (\ pred cont -> (cont pred)) (\ cont -> x))
    b_continuator = (b (\ pred cont -> (f (cont pred))) (\ cont -> x))

Похоже, что min нельзя набрать в System-F. Например, чтобы запустить его на GHC, мне пришлось дважды использовать unsafeCoerce:

import Unsafe.Coerce

(#)   = unsafeCoerce
min'  = (\ a b f x -> (a (\ p c -> (c # p)) (\ c -> x) (b (\ p c -> (f (c # p))) (\ c -> x))))
toInt = (\ n -> (n (+ 1) 0))
main  = print (toInt (min'
    (\ f x -> (f (f (f (f (f x))))))               -- 5
    (\ f x -> (f (f (f (f (f (f (f (f x))))))))))  -- 8
    :: Int)

Можно ли ввести min в System-F (или в исчислении конструкций)?


types haskell dependent-type agda type-theory
person MaiaVictor    schedule 18.11.2015    source источник
comment
Я не могу разобрать (cont -> x). Есть еще \ ?   -  person chi    schedule 18.11.2015
comment
У меня нет четкого представления, но я думаю, что церковные цифры имеют политип CN = forall a. (a->a)->a->a. Поскольку политипы не могут быть выведены, я бы начал с аннотирования числовых переменных с помощью CN - есть вероятность, что вы используете их в разных типах.   -  person chi    schedule 18.11.2015
comment
@chi На самом деле не должно быть `` на другой лямбде. Я понятия не имел, как он туда попал. Есть шанс, что я их использую в разных типах?   -  person MaiaVictor    schedule 18.11.2015
comment
В нетипизированном лямбда-исчислении вы можете применить церковную цифру к любой функции. В типизированном языке без политипов вы можете иметь числительное для каждого типа T (которое может применяться только к функциям T->T) - однако это ограничение очень неудобно. В языке с политипами вы можете присвоить тип CN числам, чтобы они могли работать с любой функцией типа T->T, независимо от типа T.   -  person chi    schedule 18.11.2015
comment
После некоторого эксперимента я чувствую, что подтерм a (\ p c -> c p) нельзя ввести в SystemF (даже после добавления некоторых параметров типа). Его тип, кажется, зависит от фактического значения a. Я предполагаю, что в CoC его можно ввести, но только после добавления не просто переменных типа / аргументов типа, но и других терминов, которые кодируют зависимость результирующего типа от a.   -  person chi    schedule 18.11.2015
comment
Кажется, это работает так же, как coroutining zip в предыдущем вопросе, поэтому я думаю, что его можно ввести аналогичным образом в Agda. Однако он также будет использовать зависимое исключение, на этот раз натуральных чисел, и нет никакого способа получить это исключительно из кодировок Чёрча. Нам нужно добавить правило исключения к базовому языку.   -  person András Kovács    schedule 18.11.2015
comment
На самом деле я об этом и спрашиваю. В вашем решении используются зависимые элиминаторы, которых нет в CoC (таким образом, в Morte). Так вы говорите, что это не печатается на CoC, верно?   -  person MaiaVictor    schedule 18.11.2015
comment
Правильно. Это несколько плохая новость для тех, кто хочет минимизировать базовые языки. Тем не менее, вы можете изучить теории типов с закрытыми (универсальными) вселенными типов, поскольку они могут быть намного более мощными, чем ванильный CoC, но все же имеют довольно простую спецификацию (и им также не нужны какие-либо типы данных, определяемые пользователем).   -  person András Kovács    schedule 18.11.2015
comment
Как вы сказали, это сложно погуглить. Не могли бы вы мне подсказать, @ AndrásKovács?   -  person MaiaVictor    schedule 18.11.2015
comment
К сожалению, материал, который я прочитал об этом, разбросан по множеству несамостоятельных статей, и я не припомню ничего, что подходило бы именно для ваших целей. Идея состоит в том, чтобы закодировать все типы с помощью небольшого набора конструкций, доступные основы вы можете найти в GHC.Generics и его использовании. Для более сложных универсальных юниверсов вы можете посмотреть this или это.   -  person András Kovács    schedule 19.11.2015
comment
В общем, я многому научился из статей Конора Макбрайда (свинарник на SO и Reddit) и по обобщениям, особенно из статей Андерса Лё (космикус на SO и Reddit). Найдите их материалы в Google Scholar. Я думаю, вам нужно будет глубоко погрузиться в теорию типов, чтобы понять это. Тем не менее, я от всей души рекомендую этот опыт.   -  person András Kovács    schedule 19.11.2015
comment
Я думаю, вам нужно будет глубоко погрузиться в теорию типов, чтобы понять это. - и как я могу это сделать эффективно? Когда я задумываюсь об этом, меня останавливает то, что я думаю, что потрачу больше времени на изучение поля и выяснение того, что мне следует прочитать, чем на само чтение.   -  person MaiaVictor    schedule 19.11.2015
comment
Позвольте нам продолжить это обсуждение в чате.   -  person András Kovács    schedule 19.11.2015

Ответы (1)


arrow_upward
4
arrow_downward

Функция (хорошо ли она известна? Она выглядит действительно умной) типизирована, она просто не работает с натсами, закодированными в церковной кодировке.

Вот тип, который выводит GHC:

(((t3 -> t2) -> t3 -> t2) -> (b0 -> a0) -> t1 -> t0)
                        -> (((t6 -> t5) -> t6 -> t4) -> (b1 -> a0) -> t1)
                        -> (t5 -> t4)
                        -> a0
                        -> t0))

Вот самый близкий к желаемому типу, который я смог получить:

postulate t1 t2 : Set

A = ((t2 -> t1) -> t1) -> (((t2 -> t1) -> t1) -> t1) -> t1
B = (t2 -> t1) -> ((t2 -> t1) -> t1) -> t1
C = t1 -> t1

min : (A -> A) -> (B -> B) -> (C -> C)
min a b = \ f x -> a (\ p c -> c p) (\ c -> x) (b (\ p c -> f (c p)) (\ c -> x))

Для работы с натсами в кодировке Чёрча min должен принимать два аргумента типа (a -> a) -> a -> a, т.е. A должен иметь тип a -> a, т. Е.

a ~ (t2                 -> t1) -> t1
a ~ (((t2 -> t1) -> t1) -> t1) -> t1

то есть t2 ~ (t2 -> t1) -> t1, который представляет собой цикл. В Системе F или CoC нет рекурсивных типов, и, следовательно, термин не может быть типизирован как есть.

Однако я проигнорировал Rank2Types материал. Так или иначе,

newtype Church = Church { runChurch :: forall a. (a -> a) -> a -> a }

min' a b = Church $ \f x -> runChurch a (\p c -> c p) (\c -> x) (runChurch b (\p c -> f (c p)) (\c -> x))

также является ошибкой бесконечного типа.

person user3237465    schedule 19.11.2015
comment
См. this для обсуждения min-подобных конструкций. - person András Kovács; 19.11.2015
comment
@ András Kovács, спасибо, это необычно читаемый документ, в котором есть продолжения. Итак, нам нужно решить t2 = (t2 -> t1) -> t1 и, следовательно, нам нужны рекурсивные типы. - person user3237465; 19.11.2015
comment
@ AndrásKovács, что вы думаете о Самотипах? Решает ли это проблему без других проблем? - person MaiaVictor; 21.11.2015
comment
@Viclib Я думаю, что min можно было бы ввести в него после того, как мы сделаем некоторое расширение системы в статье, в частности, нам нужно вычислить типы из Nat-s, что требует индукционного мотива Nat -> ☐, но в статье есть только Nat -> *. Это не должно быть слишком сложно, мы могли бы использовать иерархию вселенных, как в Agda / Coq, или * : *, если мы ленивы. Газета - отличная находка. - person András Kovács; 22.11.2015
comment
@ András Kovács, в системе уже есть * : *. Но тогда мы можем просто использовать данные в кодировке Скотта. Я не думаю, что возможно типизировать self k = k self (это самая простая вещь, которую мы можем делать с гиперфункциями) в любой системе типов звука: self self - это непосредственный цикл. - person user3237465; 22.11.2015
comment
@ user3237465: Я вижу * : ☐ только в бумага. Что касается набора min, нам просто нужно предоставить дополнительное доказательство того, что типы сверток сопрограмм всегда совпадают. См. код Agda. На первый взгляд кажется, что это возможно и с самотипами, если мы добавим большое исключение. - person András Kovács; 22.11.2015
comment
@ András Kovács, я полагаю, что * : ☐ в статье только из-за стирания материала System F-omega. Слайды содержат * : *. Код поучительный, спасибо. Невозможно определить self k = k self, но не self : ∀ n -> Min ⊤ n -> ℕ; self 0 k = k _; self (suc n) k = k (self n). - person user3237465; 22.11.2015
comment
@Viclib, Андраш Ковач, я написал более или менее прямой перевод сверток сопрограмм в Agda. - person user3237465; 23.11.2015
comment
@ user3237465, я не уверен, что понимаю, о чем вы, ребята. Какой именно вывод? Чтобы min был напечатан в звуковой системе, все, что нам нужно, это self и бесконечная иерархия вселенных - это то, что вы сказали? Я (очень) поверхностно понимаю, что делает ваш код, но я не вижу там никакого ссылочного типа, поэтому я не уверен, что это должно делать. - person MaiaVictor; 24.11.2015
comment
@Viclib, self-types дают вам принцип индукции, который необходим для определения foldK. Но по принципу индукции вы можете писать min, используя прямое сопоставление с образцом. Так что да, self-типы дают вам возможность сделать min типизированным, но они также дают вам возможность написать обычное трехстрочное определение min. Но я не знаю, действительно ли самотипы беспроблемны. - person user3237465; 24.11.2015
comment
@ user3237465 ты про обычную рекурсивную функцию? min (S a) (S b) = min a b; min Z b = b; min a Z = a? Это не имеет смысла, потому что им нужен Y-комбинатор (даже на нетипизированном лямбда-исчислении), который нельзя ввести, верно? - person MaiaVictor; 24.11.2015
comment
@Viclib, если a кодируется по Черчу, а b - по Скотту, тогда вам не нужен Y-комбинатор. Элиминаторы дают вам обоим как кодировку Parigot. (Мы обсудили это, и я согласился, что min определение таким образом слишком строго, но это было неправильно: здесь программа, которая завершается немедленно. С кодировкой Чёрча вы застряли с tail, но не с head). Здесь zipWith определены термины каплеуловителей. - person user3237465; 24.11.2015
comment
Ах я вижу. Что ж, я попробую расширить Morte с помощью self и написать там свой foldK, это может быть отличным упражнением. Но что происходит в строке 7 после знака =? Почему при чередовании аргументов используется {} вместо ()? Кроме того, я не уверен, где используется self TBH, тип foldK не относится к самому себе, он относится к _8 _... - person MaiaVictor; 25.11.2015
comment
@Viclib, мне было бы удобно работать с зависимыми типами, прежде чем пытаться реализовать проверку типов, особенно с малоизвестными правилами, не ориентированными на синтаксис. FoldK является продолжением числа. Неявные аргументы заключены в {} - это просто для удобства, вы можете сделать все явным. Дело в foldK в том, что его тип зависит от n. С закодированными Чёрчем натами невозможно выразить эту зависимость - они дают вам силу предикативной Системы F (по модулю большого исключения). self дает вам элиминаторы, которые являются краеугольным камнем теорий зависимых типов. - person user3237465; 25.11.2015