Est-ce que `sort` peut être typé en logique affine élémentaire?

Le terme λ suivant, ici sous forme normale:

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

Implémente un algorithme de tri pour les listes codées par église. Autrement dit, le résultat de:

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

De même,

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

Implémente également le tri pour les mêmes listes que ci-dessus, sauf que vous devez fournir un argument supplémentaire avec une limite pour les nombres qu'il considérera:

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

J'essaie de déterminer si ces termes sont typables sur la logique affine élémentaire. Étant donné que je ne connais aucun vérificateur de type EAL accessible au public, cela s'avère une tâche plus difficile que ce à quoi je m'attendais. Existe-t-il un type de sortlogique affine élémentaire?

lo.logic lambda-calculus type-systems MaiaVictor
la source

At-il un type "ordinaire"? Que se passe-t-il si vous le branchez sur Haskell?

Andrej Bauer

Je suis d'accord avec Andrej, les termes sont illisibles en tant que tels. Quels algorithmes implémentent-ils? Un tri entier n'est pas basé sur une comparaison ? Quel système de saisie basé sur EAL envisagez-vous? La naïve (pas de réduction de sujet) ou celle de Coppola, Dal Lago et Ronchi ? Sont-ils typables dans le système F, par exemple, , où ? Sinon, il n'y a aucun espoir qu'ils soient typables dans un système basé sur 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$

Damiano Mazza

Oui, c'est parce qu'il y a un foncteur oublieux de EAL au système F (ou aux types simples, si vous n'utilisez pas le polymorphisme) tel que si dans EAL, alors dans le système F. Le fait que votre évaluateur simplifié fonctionne n'est pas incompatible avec cela: ce qui fait que l'algorithme de Lamping fonctionne sans crochets et croissants est une propriété de stratification des termes, qui est purement structurelle et indépendante des types: il existe des termes non typables (dans System F, EAL, Haskell ou autre) qui sont stratifiés. Je suppose que votre terme doit tomber dans cette classe.

(\cdot)^{-}

$(\cdot)^-$

t : A

$t:A$

t^{-} : A^{-}

$t^-:A^-$

Damiano Mazza

Peut-être que ces commentaires peuvent être transformés en réponse?

Andrej Bauer

En lisant les questions. :-)

Tayfun Payez le

Réponses:

Je pense sort, comme présenté ici, n'est pas typable sur EAL. Je ne peux pas le prouver, mais cela ne fonctionne pas sur l'algorithme abstrait de Lamping sans l'oracle. De plus, bien que le terme soit quelque peu intelligent et bref, il utilise des stratégies très farfelues qui ne sont pas adaptées à l'EAL.

Mais derrière cette question, il y en a une plus intéressante: "une fonction de tri nat peut-elle être implémentée en EAL" ? C'était une question très difficile à l'époque, mais maintenant cela semble assez trivial. Oui bien sûr. Il existe de nombreuses façons plus simples de le faire. Par exemple, on peut simplement remplir un Scott encodé NatSetavec des Church encodés Nat, puis le convertir en une liste. Voici une démonstration complète:

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

Voici la forme normale indexée par bruijn d'une version légèrement modifiée de ce qui sortprécède, qui doit recevoir (x -> (x x))comme premier argument pour fonctionner (sinon elle n'a pas de forme normale):

λλ(((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étrospectivement assez simple.

MaiaVictor
la source