Ist "sort" für elementare affine Logik typisierbar?

Der folgende λ-Term, hier in normaler Form:

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))

Implementiert einen Sortieralgorithmus für kirchenkodierte Listen. Das heißt, das Ergebnis von:

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

Ähnlich,

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))))

Implementiert auch die Sortierung für dieselben Listen wie oben, außer dass Sie ein zusätzliches Argument mit einer Begrenzung für die berücksichtigten Zahlen angeben müssen:

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

Ich versuche festzustellen, ob diese Begriffe auf elementarer affiner Logik typisierbar sind. Da ich keinen öffentlich verfügbaren EAL-Typprüfer kenne, ist dies eine schwierigere Aufgabe als erwartet. Gibt es einen Typ für sortin der elementaren affinen Logik?

Ich denke sort, wie dort dargestellt, ist auf EAL nicht typisierbar. Ich kann das nicht beweisen, aber es funktioniert nicht mit Lampings abstraktem Algorithmus ohne das Orakel. Obwohl der Begriff etwas klug und kurz ist, verwendet er sehr verrückte Strategien, die nicht EAL-freundlich sind.

Hinter dieser Frage steht jedoch eine interessantere: "Kann eine Nat-Sortierfunktion in EAL implementiert werden ? " Das war damals eine sehr schwierige Frage, aber jetzt sieht es ziemlich trivial aus. Ja natürlich. Es gibt viele einfachere Möglichkeiten, dies zu tun. Zum Beispiel kann man einfach ein Scott-codiertes NatSetmit Church-codiertem Nats füllen und es dann in eine Liste konvertieren. Hier ist eine vollständige Demonstration:

-- 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])

Hier ist die bruijn-indizierte Normalform einer leicht veränderten Version des sortoben genannten, die (x -> (x x))als erstes Argument empfangen werden muss, um zu funktionieren (ansonsten hat sie keine Normalform):

λλ(((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)

Rückblickend ziemlich einfach.