Можно ли сортировать `sort` по элементарной аффинной логике?

Следующий λ-член здесь в нормальной форме:

sort = (λabc.(a(λdefg.(f(d(λhij.(j(λkl.(k(λmn.(mhi))l))
       (h(λkl.l)i)))(λhi.(i(λjk.(bd(jhk)))(bd(h(λjk.(j
       (λlm.m)k))c)))))e))(λde.e)(λde.(d(λfg.g)e))c))

Реализует алгоритм сортировки для церковно-закодированных списков. То есть результат:

sort (λ c n . (c 3 (c 1 (c 2 n)))) β→ (λ c n . (c 1 (c 2 (c 3 n))))

По аналогии,

sort_below = λabcd.a(λef.f(λghi.g(λj.h(λkl.kj(ikl)))(hi))e(λgh.h))
            (λe.d)(λe.b(λf.e(f(λghi.hg)(λgh.cfh))))

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

sort_below 4 [5,1,3,2,4] → [1,2,3]

Я пытаюсь определить, поддаются ли эти термины элементарной аффинной логике. Поскольку я не знаю общедоступных средств проверки типов EAL, это оказалось сложнее, чем я ожидал. Есть ли тип для sortэлементарной аффинной логики?

lo.logic lambda-calculus type-systems MaiaVictor
источник

Есть ли у него "обычный" тип? Что произойдет, если вы подключите его к Haskell?

Андрей Бауэр

Я согласен с Андреем, условия не читаются как таковые. Какие алгоритмы они реализуют? Какая-то целочисленная сортировка, не основанная на сравнении ? Какую систему печати на основе EAL вы рассматриваете? Наивный (без сокращения предмета) или Коппола, Даль Лаго и Рончи ? Они могут быть напечатаны в Системе F, например, , где ? Если нет, то нет надежды, что они будут типизированы в любой системе на основе EAL.

s o r t : N a t L i s t \to N a t L i s t

$sort:\mathsf{NatList}\to\mathsf{NatList}$

N a t L i s t := \forall X . (N a t \to X \to X) \to X \to X

$\mathsf{NatList}:=\forall X.(\mathsf{Nat}\to X\to X)\to X\to X$

Дамиано Мазза

Да, это потому, что существует забывчивый функтор из EAL в System F (или в простые типы, если вы не используете полиморфизм) такой, что если в EAL, то в Системе F. Тот факт, что ваш упрощенный оценщик работает, не противоречит следующему: то, что заставляет алгоритм Лампинга работать без скобок и круассанов, является стратификационным свойством терминов, которое является чисто структурным и независимым от типов: в нем есть нетипизированные термины (в Системе F, EAL, Haskell или любой другой), которые стратифицированы. Я думаю, ваш термин должен попасть в этот класс.

(\cdot)^{-}

$(\cdot)^-$

t : A

$t:A$

t^{-} : A^{-}

$t^-:A^-$

Дамиано Мазза

Может быть, эти комментарии можно превратить в ответ?

Андрей Бауэр

Читая вопросы. :-)

Тайфун

Ответы:

Я думаю sort, как представлено там, не может быть напечатано на EAL. Я не могу доказать это, но он не работает на абстрактном алгоритме Лампинга без оракула. Более того, хотя этот термин несколько умный и краткий, он использует очень дурацкие стратегии, которые не подходят для EAL.

Но за этим вопросом стоит более интересный: «можно ли реализовать функцию сортировки nat в EAL» ? Тогда это был очень сложный вопрос, но теперь он выглядит довольно тривиально. Ну конечно; естественно. Есть много простых способов сделать это. Например, можно просто заполнить кодировкой Скотта s -кодированными NatSetЦерковью Nat, а затем преобразовать ее в список. Вот полная демонстрация:

-- sort_example.mel
-- Sorting a list of Church-encoded numbers on the untyped lambda calculus
-- with terms that can be executed by Lamping's Abstract Algorithm without
-- using the Oracle. Test by calling `mel sort_example.mel`, using Caramel,
-- from https://github.com/maiavictor/caramel

-- Constructors for Church-encoded Lists 
-- Haskell: `data List = Cons a (List a) | Nil`
Cons head tail = (cons nil -> (cons head (tail cons nil)))
Nil            = (cons nil -> nil)

-- Constructors for Church-encoded Nats
-- Haskell: `data Nat = Succ Nat | Zero`
Succ pred = (succ zero -> (succ (pred succ zero)))
Zero      = (succ zero -> zero)

---- Constructors for Scott-encoded NatMaps
---- Those work like lists, where `Yep` constructors mean
---- there is a number on that index, `Nah` constructors
---- mean there isn't, and `End` ends the list.
---- Haskell: `data NatMap = Yep NatMap | Nah NatMap | End`
Yep natMap = (yep nah end -> (yep natMap))
Nah natMap = (yep nah end -> (nah natMap))
End        = (yep nah end -> end)

---- insert :: Nat (Church) -> NatMap (Scott) -> NatMap (Scott)
---- Inserts a Church-encoded Nat into a Scott-encoded NatMap.
insert nat natMap    = (nat succ zero natMap)
    succ pred natMap = (natMap yep? nah? end?)
        yep? natMap  = (Yep (pred natMap))
        nah? natMap  = (Nah (pred natMap))
        end?         = (Nah (pred natMap))
    zero natMap      = (natMap Yep Yep (Yep End))

---- toList :: NatMap (Scott) -> List Nat (Church)
---- Converts a Scott-Encoded NatMap to a Church-encoded List
toList natMap        = (go go natMap 0)
    go go natMap nat = (natMap yep? nah? end?)
        yep? natMap  = (Cons nat (go go natMap (Succ nat)))
        nah? natMap  = (go go natMap (Succ nat))
        end?         = Nil

---- sort :: List Nat (Church) -> List Nat (Church)
---- Sorts a Church-encoded list of Nats in ascending order.
sort nats = (toList (nats insert End))

-- Test
main = (sort [1,4,5,2,3])

Вот индекс bruijn с нормальной формой слегка измененной версии sortвышеупомянутого, который должен получить (x -> (x x))в качестве первого аргумента для работы (в противном случае он не имеет нормальной формы):

λλ(((1 λλλ(((1 λλλ((1 3) (((((5 5) 2) λλ(1 ((5 1) 0))) 1) 0))) 
λ(((3 3) 0) λλ(1 ((3 1) 0)))) λλ0)) ((0 λλ(((1 λλ(((0 λλλλ(2 (
5 3))) λλλλ(1 (5 3))) λλλ(1 (4 3)))) λ(((0 λλλλ(2 3)) λλλλ(2 3
)) λλλ(2 λλλ0))) 0)) λλλ0)) λλ0)

Довольно просто в ретроспективе.

MaiaVictor
источник