Categoria teoria e analisadores - referências desejadas

Como estou interessado em analisadores (principalmente em gramáticas de expressão do analisador), estou me perguntando se há algum trabalho que forneça um tratamento categórico para a análise. Qualquer referência sobre aplicações da teoria de categorias à análise é altamente apreciada.

melhor,

Uma das primeiras aplicações da teoria das categorias a um assunto fora da geometria algébrica foi a análise! As palavras-chave que você deseja orientar sua pesquisa são "cálculo Lambek" e "gramática categorial".

Em termos modernos, Joachim Lambek inventou a lógica linear não comutativa para modelar a estrutura das sentenças. A idéia básica é que você pode fornecer partes básicas da fala como tendo tipos e, em seguida, (digamos) atribuir adjetivos em inglês a um tipo de função que use frases substantivas em frases substantivas. (por exemplo, "verde" é visto como uma função que leva substantivos a substantivos, o que significa que "ovos verdes" é bem digitado, já que "ovos" é um substantivo).

$A\setminus{}B$$B$$A$$B/A$$B$$A$$A \ast B$$A$$B$

Acontece que as gramáticas Lambek são equivalentes às linguagens livres de contexto, embora aparentemente este seja um resultado bastante difícil - é fácil mostrar que os CFGs são um subconjunto de gramáticas Lambek, mas a outra direção só foi estabelecida em 1991 pelo Pentus.

Um bom exercício ^ H ^ H ^ A publicação para o leitor (ou seja, eu não tentei, mas acho que seria legal tentar) é usar o cálculo de Lambek para reformular a apresentação de Valiant da análise de CYK via multiplicação de matriz booleana , em categorias termos. Como motivação, cito o artigo de Lambek de 1958, The Mathematics of Structure Structure :

O cálculo apresentado aqui é formalmente idêntico ao cálculo construído por GD Findlay e o presente autor para uma discussão de mapeamentos canônicos em álgebra linear e multilinear.

Parece que (sem contexto) a análise de um Parsec é naturalmente expressa em termos da classe de tipo Aplicative . Por sua vez, essa classe é bem descrita pelos chamados funcionais monoidais fortes e frouxos , mencionados nesta muito boa pergunta sobre a história e nesta agradável pergunta sobre o fluxo de pilha .

De maneira mais geral, os analisadores Parsec são mônadas , tão conhecidas tanto na teoria de CS quanto na teoria de categorias que não darei referências a menos que solicitado.