Representação formal de uma hierarquia de abstração

9

Introdução

Estou escrevendo minha tese de doutorado em Abstract Delta Modeling (ADM), uma descrição algébrica abstrata de modificações (conhecidas como deltas ) capazes de atuar em produtos (como em 'produtos de software'). Isso pode ser usado para organizar um conjunto de produtos relacionados (uma 'linha de produtos') como um produto básico simples e um conjunto de deltas aplicados condicionalmente e, assim, permitir maior reutilização dos artefatos subjacentes.

Os detalhes da modelagem delta não são realmente importantes para minha pergunta, mas o ADM serve como um bom exemplo para explicar o problema; portanto, apresentarei os conceitos mais importantes.

fundo

A principal estrutura de interesse é o deltóide . Os produtos vêm de um conjunto universal . Deltas vêm de um monóide com operador composição e elemento neutro . O operador de avaliação semântica transforma um delta 'sintático' em uma relaçãoP ( D , , ε ) : D × DD ε D [(P,D,,ϵ,[[]])P(D,,ϵ):D×DDϵD d D [[[]]:D2P×PdD d[[d]]P×Pque decide como pode modificar um produto.d

Questão

Como o ADM é uma álgebra abstrata, a maioria do meu trabalho abstrai da natureza concreta de produtos e deltas, e vários resultados são comprovados sem descer a um nível mais concreto. Espera-se que esses resultados sejam transferidos para um domínio mais concreto, mas ainda não o formalizei.

Existem exemplos e estudos de caso que funcionam em um domínio concreto: código-fonte orientado a objetos, código , números naturais, perfis de telefones celulares, etc. Há também alguns estágios intermediários de abstração, como aninhados pares chave-valor. Para cada redefinir (ou 'refinar') . ( P , D ,,ϵ, [LATEX(P,D,,ϵ,[[]])

Eu gostaria de deixar essa hierarquia explícita: (1) para fornecer maior clareza ao leitor e (2) para justificar formalmente o uso de resultados de níveis mais abstratos.

Minha pergunta: como devo organizar formalmente esses níveis de abstração?

Espero poder argumentar com uma simples relação de refinamento em deltoids. E eu sinto que poderia ser definido simplesmente apelando para a relação subconjunto de e . Mas ainda não tenho certeza. Existem abordagens existentes para o tipo de problema que estou descrevendo? Publicações que devo ler?P DPD

A hierarquia deltóide

Para ter uma idéia melhor do que quero dizer, aqui está a hierarquia de abstração deltóide que tenho em mente:

  • Resumo Deltóide : Este é o deltóide básico no qual produtos e deltas ainda podem ser qualquer coisa. A maior parte da teoria é baseada nessa e a maioria dos resultados é comprovada nesse nível.
    • Deltóide relacional : Aqui, deltas são relações em e é a função de identidade. P[[]]
      • Deltóide Funcional : Aqui, os deltas são funcionais (ou 'determinísticos').
    • Número natural deltóide : este é o deltóide concreto mais simples, criado apenas para ilustrar o refinamento deltóide. Aqui, produtos são números naturais e deltas são sequências numéricas simples que representam operações polinomiais.P=ND=N+
    • Deltoide de par de valor-chave aninhado : um nível intermediário de abstração para qualquer hierarquia na qual as chaves são mapeadas para valores ou sub-hierarquias. O Deltas pode realizar modificações nesta 'árvore' a qualquer profundidade.
      • OOP Deltoid : Para representações abstratas de programas orientados a objetos. Eles são basicamente pares de valores-chave aninhados, porque os programas mapeiam nomes de módulos para conjuntos de classes, que mapeiam nomes de classes para conjuntos de métodos, que mapeiam nomes de métodos para implementações de métodos.
        • ABS Deltoid : O ABS é uma linguagem de programação real orientada a objetos.
      • Deltoid de perfil de telefone : aqui, um produto é um mapeamento simples de configurações (como volume, brilho da tela etc.) para valores de um domínio correspondente.
    • LATEX Deltoid : os produtos são documentos e os deltas os modificam redefinindo as macros.LATEX

Bem, isso deve lhe dar uma boa idéia do que tenho em mente. Note, a propósito, que para qualquer deltóide, é um homomorfismo monóide de ao pertencente ao deltóide relacional correspondente.[[]]DD

A hierarquia real pode ser maior. Também pode ser organizado de maneira diferente, com base em que tipo de teoria de refinamento vou usar. Por exemplo, se eu optar por uma relação de subconjunto simples em e o ABS Deltoid não se encaixaria no Deltoid Nested Key-Value Pair, pois seus produtos e deltas são na verdade texto simples (código-fonte). Mas a hierarquia dada ainda pode funcionar se eu usar homomorfismos.DPD

mhelvens
fonte
3
Você pode tornar mais explícito qual é a hierarquia de abstração? Que coisas são abstrações de que outras coisas?
21813 Dave
Oi Dave! Eu atualizei minha pergunta. Espero que isso esclareça um pouco as coisas.
Mhelvens 12/04
4
Que tal construir categorias para cada tipo de deltóide e depois estudar os functores adjacentes esquerdo e direito (se houver) entre eles?
22813 Martin Berger
Receio não ser bem versado em teoria de categorias. :-(
mhelvens 12/04/2013

Respostas:

8

Acredito que seria benéfico para você procurar a teoria da interpretação abstrata, que fornece respostas muito completas para perguntas semelhantes na área ligeiramente diferente da análise de programas baseados em treliça.

Parece-me que você está usando uma estrutura baseada em álgebras. Estou usando a palavra álgebra aqui no sentido de álgebra universal, onde suponho que as restrições na estrutura da álgebra sejam dadas por igualdades entre os termos. Existem dois sentidos diferentes nos quais abstrações (ou hierarquias) entram na imagem.

  1. Abstração como uma relação entre duas álgebras específicas. Você pode dizer que uma álgebra tem uma estrutura mais rica que outra álgebra ou que todo problema que você pode resolver com uma álgebra pode ser resolvido com a outra. Esse tipo de relacionamento é o que seria formalizado em homomorfismos de compra ou algum outro mapeamento entre álgebras.
  2. Hierarquias de abstração como famílias de álgebras. No seu caso, seriam famílias de deltóides com certas propriedades. Como um exemplo mais geral, considere todos os conjuntos parcialmente pedidos. Podemos pensar em redes, redes distributivas e redes booleanas como uma sequência de subfamílias que possuem propriedades mais ricas.

As duas noções estão intimamente relacionadas, mas diferentes.

Abstração entre duas estruturas

O insight da interpretação abstrata é que é útil dotar as estruturas que você considera com uma noção de ordem. Considere duas estruturas

(M,fM) e , com e como operações de interesse.(N,fN)fM:MMfN:NN

Um homomorfismo no sentido universal de álgebra seria algo assim:

h:MN é uma função que satisfaz a igualdade .h(fM(a))=fN(h(a))

Podemos ver as duas estruturas que aparecem acima como estruturas pré-ordenadas

(M,=,fM) e(N,=,fN)

e o homomorfismo que podemos reescrever para ser uma função que satisfaça

  1. que se então , ea=bh(a)=h(b)
  2. para todos em , .aMh(fM(a))=fN(h(a))

Agora, suponha que você tenha alguma outra noção de aproximação disponível que faça sentido. Por exemplo, quando lidamos com conjuntos de estados na verificação de programas, a inclusão de subconjuntos faz sentido para certos aplicativos ou quando lidamos com fórmulas na dedução automática, a implicação faz sentido. De maneira mais geral, podemos considerar

(M,,fM) e , em que e são pré-encomendas.(N,,fN)

Agora, em vez de homomorfismo, podemos ter uma função de abstração

α:MN que é

  1. monótono, o que significa que sempre que temos eabα(a)α(b)
  2. semi-comuta com as operações de: para todos em .α(fM(a))fN(α(a))aM

A função abstração torna explícita a ideia de que se a estrutura sobre é uma abstração da estrutura sobre , a avaliação de um termo em não pode produzir resultados mais precisos (com relação à noção de aproximação em ) do que a avaliação do mesmo termo em e, em seguida, o mapeamento para .NMNNMN

Agora podemos perguntar se é necessário abordar o problema em termos de abstração em oposição ao refinamento. Ou seja, não podemos dizer que é um refinamento de e formular condições em termos de termos. É exatamente isso que uma função de concretização faz.MN

Uma função de concretização é monótona e satisfaz a desigualdade .γ:NMfM(γ(b))γ(fN(b))

As condições de abstração e concretização são chamadas condições de solidez na interpretação abstrata. No caso especial que e formam uma conexão de Galois, as condições de abstração e concretização são equivalentes. Em geral, eles não são equivalentes.αγ

Tudo o que fizemos até agora apenas formaliza a noção de abstração entre um par de estruturas. As coisas que eu disse podem ser resumidas de maneira muito mais sucinta na linguagem da teoria das categorias. Evitei categorias por causa do seu comentário acima.

Hierarquias de abstração

Suponha que tenhamos uma estrutura dotada de uma pré-encomenda e de algumas operações. Podemos considerar todas as estruturas modo que seja uma abstração de no sentido acima. Se tivermos que é uma abstração de e ambos sejam abstrações de , teremos três elementos da hierarquia. A relação 'é uma abstração de' permite definir uma pré-ordem entre estruturas. Vamos chamar uma família de estruturas ordenadas por abstração como uma hierarquia .N N M N 1 N 2 MMNNMN1N2M

Se eu considerar o seu exemplo, parece que seu deltóide abstrato pode ser um candidato ao elemento máximo em alguma hierarquia. Não tenho muita certeza porque o deltóide abstrato parece ser uma família de deltóides, e não um deltóide específico.

O que você pode fazer agora é considerar diferentes hierarquias. A hierarquia de todos os deltóides. Uma sub-hierarquia baseada em várias considerações acima. Um exemplo específico no contexto de interpretação abstrata é uma hierarquia de redes completas que estão em uma conexão Galois com uma dada rede de conjuntos de potências e sub-hierarquias que consistem apenas em redes distributivas ou apenas booleanas.

Como Martin Berger aponta nos comentários, essa noção de abstração entre hierarquias é capturada pela de adjuntos entre categorias.

Uma perspectiva categórica

Houve um comentário solicitando mais comentários sobre categorias. Esse comentário não está mais lá, mas eu responderei de qualquer maneira.

Vamos voltar e ver o que você está fazendo no design de deltóides e o que descrevi acima de uma perspectiva mais geral. Estamos interessados ​​em entender a estrutura essencial das entidades que manipulamos em um contexto de software e o relacionamento entre essas entidades.

A primeira percepção importante é que não estamos interessados ​​apenas em um conjunto de elementos, mas nas operações que podemos executar nesses elementos e nas propriedades dessas operações. Essa intuição direciona o design de classes na programação orientada a objetos e a definição de estruturas algébricas. Você já fez essa intuição explícita na definição de um deltóide que identificou algumas operações de interesse. De maneira mais geral, esse é o processo de pensamento subjacente às descrições algébricas. Precisamos identificar quais são nossas operações e quais propriedades elas possuem. Esta etapa nos diz a estrutura de tipos com a qual estamos trabalhando.

A segunda percepção é que não estamos interessados ​​apenas em um conjunto de elementos, mas em relacionamentos de abstração. A formalização mais simples que posso imaginar da abstração é considerar um conjunto pré-ordenado. Podemos pensar em um conjunto pré-ordenado como uma generalização estrita de um conjunto para algo que vem com uma noção de aproximação inserida.

Idealmente, queremos trabalhar em um ambiente em que os dois pontos de vista acima sejam cidadãos de primeira classe. Ou seja, queremos uma configuração digitada como a de uma álgebra, mas também a configuração com reconhecimento de aproximação de uma pré-encomenda. Um primeiro passo nessa direção é considerar uma treliça. Uma treliça é uma estrutura conceitualmente interessante porque podemos defini-la de duas maneiras equivalentes.

  1. Podemos definir uma estrutura como um conjunto equipado com uma operação meet e join. Podemos então derivar a ordem parcial definindo para reter sempre que .um b um b = um(L,,)abab=a
  2. Uma alternativa é definir uma rede como um conjunto parcialmente ordenado satisfazendo que cada par de elementos em tenha um maior limite inferior e um limite superior únicos. Podemos então derivar as operações meet e join da ordem parcial.L(L,)L

Uma rede é, portanto, uma estrutura matemática que pode ser abordada da perspectiva algébrica ou de aproximação. A desvantagem aqui é que os próprios elementos de uma treliça não possuem uma estrutura de tipos que é fatorada no relacionamento de aproximação. Ou seja, não podemos comparar elementos com base na noção de ter mais ou menos estrutura.

No contexto do seu problema, você pode pensar em categorias como uma generalização natural de pré-ordens que capturam tanto a noção de aproximação (nos morfismos) quanto a estrutura de tipos em um cenário algébrico. A definição da teoria das categorias nos permite dispensar várias distinções desnecessárias e focar na estrutura das entidades de que você gosta e na aproximação dessa estrutura. As propriedades e complementos universais fornecem um vocabulário e ferramentas muito poderosos para entender a paisagem das estruturas nas quais você está interessado e permitem um tratamento matemático rigoroso de até noções intuitivas, como diferentes níveis de abstração.

Com relação ao meu comentário sobre deltóides abstratos, parece que o que você quer é uma categoria. O deltóide abstrato é uma categoria específica análoga à categoria de conjuntos. Existem outras categorias que você está considerando. Inicialmente, pensei que você estivesse definindo um deltóide que, no sentido da teoria das categorias, seria um objeto terminal (ou final).

Você está estudando o tipo de perguntas para as quais a teoria das categorias fornece respostas muito satisfatórias. Espero que você seja capaz de chegar a essa conclusão.

Referências

  1. Interpretação abstrata e aplicação a programas lógicos , Patrick Cousot e Radhia Cousot. A primeira metade deste artigo é uma introdução geral do estilo tutorial ao tópico de interpretação abstrata.
  2. Quadros de interpretação abstrata , Patrick Cousot e Radhia Cousot. Este artigo discute todas as possibilidades esboçadas acima com relação às funções de abstração e concretização em grande detalhe.
  3. Projeto sistemático de estruturas de análise de programas , Patrick Cousot e Radhia Cousot. Este foi o artigo que introduziu a noção de hierarquias de abstrações no contexto da análise do programa.
  4. Preservação Forte Generalizada por Interpretação Abstrata , Francesco Ranzato e Francesco Tapparo. Este artigo aplica essas idéias em um contexto diferente de abstrações que preservam fórmulas lógicas temporais. Você encontrará exemplos trabalhados de abstrações booleanas e distributivas aqui.
  5. Resumo Interpretação, Relações Lógicas e Extensões Kan , Samson Abramsky. Apresenta uma perspectiva da teoria da categoria no material teórico da ordem acima.
Vijay D
fonte
Obrigado pela sua resposta completa! E a falta de categorias é muito apreciada. ;-) (vou ter que estudar alguma teoria de categoria intermediária no futuro.) Vou dar uma olhada nas suas referências. - = # = - Nesse meio tempo, tenho uma pergunta sobre sua afirmação "o deltóide abstrato parece ser uma família de deltóides em vez de um deltóide específico". Você poderia explicar como o deltóide abstrato é diferente nesse aspecto dos outros? Nenhuma estrutura algébrica não pode ser vista como a família de todos os seus refinamentos?
Mhelvens #
@VijayD Obrigado pela atualização no CT. Sou o culpado de fazer o comentário e depois o apaguei. Eu acredito profundamente que a TC é mais adequada para a questão do OP. Estou ainda mais convencido depois de ver sua atualização. Acho que se o OP não quiser fazer isso usando CT, alguém o fará.
Scaaahu
Parece muito provável que a teoria das categorias forneça as melhores respostas para minhas perguntas. E estou ansioso para estudá-lo e entender melhor essas respostas. E, de fato, minha falta de tempo para estudar e aplicar a teoria das categorias não deve ser uma desculpa para dar uma resposta 'inferior' neste site. - = # = - No entanto, aprecio muito a consideração de Vijay. Sua resposta no nível monóide foi bastante útil. - = # = - Portanto, não posso usar categorias no momento. Mas definitivamente explorarei a opção em trabalhos futuros. Obrigado a todos!
Mhelvens 18/04
Você está em uma excelente posição para abordar o assunto porque tem diante de si um problema que entende bem e pode analisar diretamente da perspectiva categórica. Acho essa a melhor maneira de aprender alguma coisa e exortaria você a não se atrasar porque os textos sobre a teoria das categorias parecem intimidadores. Tenho certeza de que há porções pequenas para estudar. Boa sorte para a defesa.
Vijay D
9

Você está trabalhando no seu doutorado. Dizer "eu não sou bem versado em " não é uma desculpa. E se você é bom, dizer "meu orientador não conhece " também não é desculpa.XXX

Você está usando monoides onde deveria estar usando categorias. Suas operações monóides pressupõem que você possa combinar qualquer . Mas isso realmente faz sentido, por exemplo, como você comporia "adicionar revestimento de plástico" e "adicionar revestimento de metal"? Suponho que parte do seu resulta em relações vazias porque elas não fazem sentido. Você deve suspeitar desse tipo de coisa.δδδ

Como observador interessado, parece que o monóide deve ser uma categoria, para que possamos compor dois apenas se fizer sentido que sejam compostos. Então sua avaliação semântica é apenas um functor na categoria de conjuntos e relações. E então você vê que existem muitas outras categorias que você poderia usar. Os deltas funcionais corresponderão a um functor que mapeia para a categoria de conjuntos e funções, os números naturais deltoid são um functor para o monóide de polinômios em números naturais (vistos como uma categoria), etc.δ

Não sei se você deseja formalizar os telefones celulares LaTeX e Nokia com muita seriedade na teoria geral. Mas é claro que sua teoria deve ser aplicável a esses exemplos (simplesmente não se desligue quando descobrir que os telefones celulares não têm uma semântica bem definida).

Você está realmente se enganando ao insistir em uma tecnologia predeterminada (pelo seu orientador?), Pela aparência.

Andrej Bauer
fonte
2
Em geral, eu concordo com você. E nunca usei isso como desculpa. :-) Mas, neste caso, a maior parte da minha tese já está escrita e o monóide foi usado em todas as minhas publicações. - = # = - Dito isto, você faz um excelente argumento. No exemplo de revestimento de plástico / metal, agora eu manuseio isso permitindo a composição, mas tendo o delta resultante avaliado para a relação vazia (como você adivinhou). Está tudo bem definido, por isso é suficiente por enquanto. Mas posso ver que sua sugestão é mais elegante. Você me deu outro bom motivo para estudar a teoria das categorias. Obrigado!
Mhelvens 15/04
@mhelvens Sou engenheiro de software aposentado que mora na indústria há muito tempo. Veio de volta a TCS após a aposentadoria. Vou fazer uma pergunta da vida real. Suponha que você formalize com sucesso os produtos de telefone Nokia usando monóide em sua tese, o que você dirá na defesa oral se a Apple anunciar que adquire a Nokia? Esse anúncio quebrará seu modelo? Parece-me que quanto mais geral é a teoria, melhor seria o modelo.
Scaaahu
@scaaahu Pergunta interessante. :-) Deixe-me começar por responder: "Não, de jeito nenhum." A teoria é independente do 'tipo' de dispositivo. - = # = - Garanto que não há necessidade de me convencer dos benefícios da generalização. (De fato, acho que às vezes exagerei.) Acontece que não encontrei a teoria das categorias a tempo de ser útil para o meu trabalho de doutorado. Como disse, concordo que pode ser uma abordagem valiosa. Mas dois meses após o prazo de minha tese não é o momento de mudar fundamentalmente minha abordagem.
Mhelvens 15/04
Claramente, você está pronto para um pós-doc ;-)
Andrej Bauer
Pedido de concessão já enviado. :-) Espero poder continuar neste campo.
Mhelvens 18/04