O que é um exemplo não artificial de verificação de tipo estática sendo muito conservadora?

9

Em Conceitos em linguagens de programação , John Mitchell escreve que a verificação de tipo estático é necessariamente conservadora (excessivamente rigorosa) por causa do problema de parada. Ele dá como exemplo:

if (complicated-expression-that-could-run-forever)
   then (expression-with-type-error)
   else (expression-with-type-error)

Alguém pode fornecer uma resposta não artificial que realmente seria uma preocupação prática?

Entendo que o Java permite conversões dinamicamente verificadas para casos como este:

if (foo instanceof Person) {
    Person p = (Person) foo;
    :
}

mas considero a necessidade disso mais uma deficiência de linguagem / compilador Java do que uma questão de linguagem cruzada.

programming-languages compilers type-checking Ellen Spertus
fonte
2
O exemplo de Java que você deu é um exemplo não inventado de verificação de tipo estática sendo muito conservadora. Em outras palavras: a resposta depende do tipo de sistema que você tem em mente. Para qualquer exemplo que surgirmos, sempre haverá um sistema de tipos que pode lidar com esse exemplo (o sistema de tipos não é muito conservador nesse exemplo). Para qualquer sistema de tipos, sempre podemos encontrar um exemplo em que é muito conservador. Então, acho que você precisa especificar o sistema de tipos. Se o sistema do tipo Java não é o que você tinha em mente, há algo mais específico em que você estava pensando? Inferência de tipo de estilo ML?
DW
pode-se argumentar que o exemplo é de análise de código estática sendo "conservadora", não de verificação de tipo. seria útil definir "conservador" . indiscutivelmente, todos os sistemas do tipo estático serão "conservadores" em comparação com os sistemas dinâmicos, porque os primeiros são mais rigorosos em tempo de compilação, por definição. no entanto, pode-se argumentar que nenhum dos dois é mais rigoroso no tempo de execução porque a verificação dinâmica também pode retornar erros semelhantes (baseados em tipo). e, a propósito, as conversões dinâmicas verificadas em tempo de execução nos idiomas não são uma deficiência , elas estão na maioria dos idiomas verificados estaticamente, possivelmente provavelmente nec.
vzn

Respostas:

7

Eu sempre o vi mais por uma questão de conveniência, do que se um algoritmo pode ou não ser expresso. Se eu realmente quisesse executar programas como o inventado por Mitchell, escreveria o simulador de máquina de Turing apropriado na minha linguagem estaticamente tipada.

O truque com um sistema de tipo estático é oferecer os tipos certos de flexibilidade apenas para os casos em que a flexibilidade permite que você escreva códigos que sejam mais facilmente mantidos.

Aqui estão alguns exemplos de técnicas de estruturação de programas que, às vezes, são mais fáceis de gerenciar dinamicamente do que em linguagens de tipo estaticamente.

Genéricos e Containers

Em linguagens estaticamente datadas antes de ML (c. 1973) e CLU (c. 1974), não era difícil criar uma árvore de strings vermelho-preto, uma árvore de números vermelho-preto, uma árvore de números flutuantes vermelho-preto ou um vermelho-preto árvore de elementos de tipo específico Foo. No entanto, foi difícil (talvez impossível) criar uma única implementação de uma árvore vermelho-preta que fosse estaticamente verificada e que pudesse lidar com qualquer um desses tipos de dados. As formas de contornar o problema foram (1) interromper completamente o sistema de tipos (por exemplo: usandovoid * em C), (2) para escrever para si mesmo algum tipo de pré-processador de macro e, em seguida, escreva macros que produzem o código para cada tipo específico que você deseja ou (3) use a abordagem Lisp / Smalltalk (e Java) para verificar o tipo de extração extraída. objeto dinamicamente.

ML e CLU introduziram a noção de, respectivamente, tipos parametrizados inferidos e declarados explicitamente (estáticos), que permitem escrever tipos de contêiner genéricos, tipicamente estaticamente.

Polimorfismo do subtipo

Nas linguagens estaticamente datadas antes de Simula67 (c. 1967) e Hope (c. 1977), não era possível realizar expedições dinâmicas e verificar estaticamente se você havia coberto o caso para todos os subtipos. Muitas línguas tiveram algum tipo de uniões marcadas , mas foi a responsabilidade do programador para se certificar de que seus caseou switchdeclarações, ou as suas tabelas de salto, cobriu cada tag possível.

Os idiomas que seguem o modelo Simula (C ++, Java, C #, Eiffel) fornecem subclasses de classes abstratas, nas quais o compilador pode verificar se cada subclasse implementou todos os métodos declarados pela classe pai. Os idiomas que seguem o modelo Hope (todas as variantes de ML, de SML / NJ a Haskell) possuem subtipos algébricos, nos quais o compilador pode verificar se todas as typecasedeclarações abrangem todos os subtipos.

Patches de Macacos e Programação Orientada a Aspectos

Os sistemas dinâmicos facilitam muito uma variedade de técnicas de prototipagem. Nas linguagens em que os tipos são representados por mapas de hash de strings para funções (por exemplo, Python, Javascript, Ruby), é muito fácil alterar globalmente o comportamento de cada módulo que depende de um tipo específico, simplesmente modificando dinamicamente o mapa de hash que representa esse tipo.

Embora existam maneiras óbvias pelas quais o patch para macacos pode ser usado para dificultar a manutenção de programas, também existem maneiras pelas quais ele pode realmente ser usado para "bem", em vez de "mal". Em particular, com a programação orientada a aspectos, pode-se usar técnicas semelhantes a patches de macaco para fazer coisas como modificar o tipo de arquivo para apontar para um sistema de arquivos virtualizado, permitindo a construção de infra-estruturas de teste de unidade como "gratuitas" ou modificar tipos de exceção simples para que eles imprima mensagens de log sempre que forem capturadas para melhor depuração.

Ao contrário do Generics and Subtype Polymorphism, onde as principais idéias de verificação estática estavam disponíveis na década de 1970, a verificação estática para programação orientada a aspectos é (eu acho) uma área de pesquisa ativa. Eu não sei muito sobre isso, exceto que existe uma linguagem chamada AspectJ desde 2001.

Lógica Errante
fonte