Transformações naturais e parametridade

11

Em Teoremas de graça! , Wadler diz que a caracterização da parametricidade pode ser re-expressa em termos de transformações naturais frouxas e isso será objeto de outro artigo. A que papel ele está se referindo?

A abordagem categórica da parametericidade que conheço utiliza transformações dinaturais, como no polimorfismo funcional de Bainbridge, Freyd, Scedrov e PJ Scott. Qual é a conexão entre as formulações de parametridade de transformação natural frouxa e transformação dinatural?

reference-request ct.category-theory parametricity sonat
fonte
2
Estou quase com medo de fazer este comentário, mas confessarei que não entendi nenhuma palavra técnica nesta pergunta. Seria possível adicionar alguns links às definições para esse (terrivelmente) especialista em não?
Suresh Venkat
1
Parece um emprego para @UdayReddy.
21814 Dave Clarke
5
Até onde eu sei, o artigo mencionado nos Teoremas de graça! (infelizmente) nunca foi escrito. Tenho certeza de que o entendimento atual da parametridade em termos de teoria de categorias é melhor capturado pelas categorias Scones e vírgula . Veja, por exemplo, Mitchell & Scedrov e esta publicação do Café da categoria n.
Cody
Suresh, desculpe por não fornecer os links relevantes. Cody, obrigado por editar a postagem e mencionar categorias de scones e vírgulas.
sonat

Respostas:

8

Infelizmente, a observação de Wadler é muito enigmática para eu dizer que uso ele queria fazer das "transformações naturais relaxadas". Aqui está um palpite. Os quadrados de relação-preservação geralmente podem ser reformulados como quadrados comutativos frouxos. É assim que costumavam ser escritos em documentos / livros antigos sobre teoria de autômatos. Veja o parágrafo 1.2 em minhas notas sobre semigrupos . Para fazer esse tipo de coisa, você precisa misturar relações e morfismos e fingir que são os mesmos. Também não tenho certeza de que ele compra algo novo. É apenas uma notação mais feia por dizer a mesma coisa que preservação de relações.

Fique à vontade para explorar a conexão, mas não tenho certeza de que você encontrará algo novo fazendo isso.

Uday Reddy
fonte
Muito obrigado pelo link. A formulação no parágrafo 1.2 ainda é definida como teórica para mim. Como você fala sobre inclusão? Você supõe que a categoria é uma alegoria ou tem propriedades semelhantes a tópicos? Se esta é uma reforma das transformações naturais relaxadas, qual é a categoria 2 subjacente? Eu também li a parte "Categorização", mas não consegui encontrar nada sobre transformações naturais relaxadas.
sonat 17/03/14
x→yx≤yf→gf≤gR⊆S:Rel(A,B)
Ah, então a categoria é fixa! Eu pensei que Wadler estava se referindo a uma formulação mais geral e abstrata que faz sentido em uma certa classe de categorias que contêm Rel como um caso especial (e um tanto trivial). Se estamos trabalhando apenas em Rel, não faz sentido introduzir uma estrutura superior, ainda que degenerada. Agora eu entendo sua resposta original.
sonat 17/03/14
@ SonatSüer: Se você está interessado em generalizações, a maneira padrão de generalizar as relações com outras categorias além de Set é tratá-las como "extensões monônicas conjuntas". Você pode obter uma categoria enriquecida com pré-encomenda em vez de enriquecida com poset, mas a estrutura 2-categórica ainda é a mesma.
Uday Reddy
@ SonatSüer: E, se você estiver realmente interessado em uma teoria axiomática adequada que cubra tudo o que sabemos, posso encaminhá-lo ao nosso artigo recente Relações lógicas e Parametricidade - Um programa de Reynolds .
Uday Reddy