O 'sort` pode ser digitado na lógica afim elementar?

O seguinte termo-λ, aqui na forma normal:

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

Implementa um algoritmo de classificação para listas codificadas por igrejas. Ou seja, o resultado de:

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

Similarmente,

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

Também implementa a classificação para as mesmas listas acima, exceto que você deve fornecer um argumento adicional com um limite para os números que serão considerados:

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

Estou tentando determinar se esses termos são tipificáveis na lógica afetiva elementar. Como não conheço nenhum verificador de tipos EAL disponível publicamente, isso está se tornando uma tarefa mais difícil do que eu esperava. Existe um tipo para sortna lógica afetiva elementar?

lo.logic lambda-calculus type-systems MaiaVictor
fonte

Tem um tipo "comum"? O que acontece se você conectá-lo ao Haskell?

Andrej Bauer

Concordo com Andrej, os termos são ilegíveis como tais. Quais algoritmos eles implementam? Alguma ordenação inteira não baseada em comparação ? Qual sistema de digitação baseado em EAL você está considerando? O ingênuo (sem redução de assunto) ou o de Coppola, Dal Lago e Ronchi ? Eles podem ser digitados no Sistema F, por exemplo, , onde ? Caso contrário, não há esperança de que sejam tipificáveis em qualquer sistema baseado em 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

Sim, isso ocorre porque existe um functor esquecido do EAL para o Sistema F (ou para tipos simples, se você não usar polimorfismo), de modo que, se no EAL, então no Sistema F. O fato de o seu avaliador simplificado funcionar não é inconsistente com isso: o que faz o algoritmo de Lamping funcionar sem colchetes e croissants é uma propriedade de estratificação dos termos, que é puramente estrutural e independente dos tipos: existem termos não tipáveis (em System F, EAL, Haskell ou o que for) que são estratificados. Eu acho que seu termo deve estar nessa classe.

(\cdot)^{-}

$(\cdot)^-$

t : A

$t:A$

t^{-} : A^{-}

$t^-:A^-$

Damiano Mazza

Talvez esses comentários possam ser transformados em uma resposta?

Andrej Bauer

Ao ler as perguntas. :-)

Tayfun Pay

Respostas:

Eu acho que sort, como apresentado lá, não pode ser digitado no EAL. Não posso provar isso, mas não funciona no algoritmo abstrato de Lamping sem o oráculo. Além disso, embora o termo seja um pouco inteligente e breve, ele usa estratégias muito malucas que não são compatíveis com a EAL.

Mas por trás dessa pergunta, há uma mais interessante: "uma função de classificação nat pode ser implementada no EAL" ? Essa era uma pergunta muito difícil na época, mas agora parece bastante trivial. Sim, claro. Existem muitas maneiras mais simples de fazer isso. Por exemplo, pode-se preencher apenas um codificado em Scott NatSetcom Nats codificados pela Igreja e depois convertê-lo em uma lista. Aqui está uma demonstração completa:

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

Aqui está a forma normal indexada por bruijn de uma versão ligeiramente alterada da sortacima, que deve receber (x -> (x x))como o primeiro argumento para funcionar (caso contrário, ela não tem uma forma normal):

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

Muito simples em retrospecto.

MaiaVictor
fonte