O que isso significa para um idioma ser estaticamente digitado?

Question

Meu entendimento é que isso significa que é possível escrever um programa para provar formalmente que um programa escrito em um idioma tipado estaticamente estará livre de um determinado (pequeno) subconjunto de defeitos.

Meu problema com isso é o seguinte:

Suponha que tenhamos dois idiomas completos de Turing, presume -se que A e B. Suponha que receba um programa para verificar a correção de qualquer programa escrito em A. O que é para me impedir de traduzir qualquer programa escrito em B para A, aplicando L. Se P traduzir de A a B, por que não Verificador de tipo válido para algum programa escrito em B?

Sou treinado em álgebra e estou apenas começando a estudar o CS, para que haja algum motivo óbvio de que isso não funcione, mas eu gostaria muito de saber. Todo essa coisa de 'tipo de segurança' cheirava a mim por um tempo.

Answer 1

Seja um idioma de preenchimento de Turing, que deve ser estaticamente digitado e deixe um idioma que você obtém de um quando remover a verificação do tipo (mas não as anotações de tipo porque também servem a outros propósitos). Os programas aceitos de A serão um subconjunto dos programas aceitos de A '. Portanto, em particular, um 'também será preenchido.

Dado o seu tradutor P de B a A (e vice -versa). O que deve fazer? Pode fazer uma de duas coisas:

1. Em primeiro lugar, poderia traduzir todos os programas de B para um programa de A. Nesse caso, o LPY sempre retornaria verdadeiro, pois os programas de A são, por definição, digitados corretamente.

2. Em segundo lugar, P poderia traduzir todos os programas de B para um programa de A '. Nesse caso, o LPY retornaria verdadeiro se o PY fosse um programa de A e Falso, se não.

Como o primeiro caso não produz nada de interessante, vamos nos ater ao segundo caso, o que é provavelmente o que você quer dizer. A função LP definida em programas de B nos diz algo interessante sobre os programas de B? Eu digo não, porque não é invariante sob uma mudança de P. como A é um complemento, mesmo no segundo caso P pode ser escolhido para que sua imagem esteja em A., então o LP seria constantemente verdadeiro. Por outro lado, P poderia ser escolhido para que alguns programas sejam mapeados para o complemento de A em A '. Nesse caso, o LP cuspiria falso para alguns (possivelmente todos) programas de B. Como você pode ver, você não recebe nada que dependa apenas de y.

Também posso colocá -lo mais matematicamente da seguinte maneira: existe uma categoria C das linguagens de programação cujos objetos são as linguagens de programação e cujos morfismos são tradutores de uma linguagem de programação para outra. Em particular, se houver um morfismo p: x -> y, y é pelo menos tão expressivo quanto X. Entre cada par de idiomas completos de Turing, existem morfismos em ambas as direções. Para cada objeto X de C (ou seja, para cada linguagem de programação), temos um conjunto associado, digamos {x} (notação ruim, eu sei) daquelas funções parcialmente definidas que podem ser calculadas por programas de X. Cada morfismo p: x - > Y então induz uma inclusão {x} -> {y} de conjuntos. Vamos inverter formalmente todos os morfismos p: x -> y que induzem a identidade {x} -> {y}. Chamarei a categoria resultante (que é, em termos matemáticos, uma localização de c) por C '. Agora a inclusão a -> a 'é um morfismo em c'. No entanto, não é preservado sob automorfismos de A ', que é o morfismo a -> a' não é um invariante de A 'em C'. Em outras palavras: deste ponto de vista abstrato, o atributo "tipado estaticamente" não é definível e pode ser arbitrariamente anexado a um idioma.

Para deixar meu ponto mais claro, você também pode pensar em c 'como a categoria de, digamos, formas geométricas no espaço tridimensional, juntamente com os movimentos euclidianos como morfismos. A 'e B são então duas formas geométricas e P e Q são movimentos euclidianos que trazem B para um' e vice -versa. Por exemplo, A 'e B podem ser duas esferas. Agora vamos consertar um ponto em um ', que representará o subconjunto a de A'. Vamos chamar esse ponto de "tiped estaticamente". Queremos saber se um ponto de B é estaticamente digitado. Então, levamos esse ponto Y, mapeamos via P para um 'e teste, seja nosso ponto marcado em A'. Como pode -se ver facilmente, isso depende do mapa escolhido P ou, para colocar em outras palavras: um ponto marcado em uma esfera não é preservado por automorfismos (que são movimentos euclidianos que mapeiam a esfera para si mesma) dessa esfera.

Answer 2

Se Você pode traduzir todo B '(um programa escrito em b) em um equivalente A' (que está correto se b '), então o idioma B desfruta tanto de "segurança do tipo" quanto a linguagem A (em um sentido teórico, é claro ;-) - Basicamente, isso significaria que B é tal que você pode fazer um tipo perfeito. Mas isso é extremamente limitado para uma linguagem dinâmica - por exemplo, considere:

if userinput() = 'bah':
    thefun(23)
else:
    thefun('gotcha')

Onde thefun (Vamos supor) é TypeSafe para o argumento int, mas não para o argumento da STR. Agora - como você traduz isso para a linguagem A em primeiro lugar...?

Answer 3

Outra maneira de fazer o mesmo ponto que foi feito é que sua pergunta constitui uma prova por contradição de que também:

• A não pode ser mapeado para B
• A segurança do tipo não é uma propriedade lexical de um idioma

ou ambos. Minha intuição diz que o último é provavelmente o ponto de discórdia: esse tipo de segurança é uma propriedade meta-linguística.

Answer 4

Não há nada "suspeito" nisso. ;)

O conjunto de idiomas de Turing-complete que são seguros de tipo em relação a qualquer não trivial [1] Sistema de tipo T é um rigoroso subconjunto dos idiomas Turing-complete. Como tal, no caso geral, nenhum tradutor P^-1 a partir de B para UMA existe; Portanto, nenhum tradutor tambémporra-Type-checker Lp^-1.

Uma reação instintiva a esse tipo de reivindicação pode ser: Absurdo! Ambos UMA e B são turing-complete, para que eu possa expressar algum função computável em qualquer Língua! E, de fato, isso está correto-você posso expressar qualquer função computável em qualquer idioma; No entanto, muitas vezes, você também pode expressar um pouco mais. Em particular, você pode construir expressões cuja semântica denotacional não é bem definida, como aquelas que podem felizmente tentar pegar a soma aritmética das cordas do personagem "Foo" e "bar" (esta é a essência de Chubsdad Alex Martelliresposta). Esses tipos de expressões podem estar "em" o idioma B, mas pode simplesmente não ser expresso no idioma UMA, porque a semântica denotacional é indefinida, portanto, não há uma maneira sensata de traduzi -las.

Esse é um dos grandes pontos fortes da digitação estática: se o seu sistema de tipos não conseguir provar, no momento da compilação, que a função mencionada receberá quaisquer parâmetros, mas aqueles para os quais o resultado do operador de adição aritmética é bem definido, ele pode ser rejeitado como mal-tado.

Observe que, embora o acima seja o tipo usual de exemplo dado para explicar os méritos de um sistema de tipo estático, talvez seja muito modesto. Em geral, um sistema de tipo estático não precisa se limitar a apenas cumprir a correção de tipo de tipo de parâmetros, mas de fato pode expressar algum propriedade desejada de um programa que pode ser comprovado no momento da compilação. Por exemplo, é possível construir sistemas de tipo que imponham a restrição de que se libere um identificador de sistema de arquivos (por exemplo para um banco de dados, arquivo, soquete de rede, etc.) dentro do mesmo escopo em que foi adquirido. Obviamente, isso é tremendamente valioso em domínios como sistemas de apoio à vida, entre outros, onde demonstrável A correção do maior número possível de parâmetros do sistema é absolutamente essencial. Se você satisfazer o sistema do tipo estático, poderá obter esses tipos de provas gratuitamente.

[1] Por não trivial, quero dizer de tal forma que nem todas as expressões possíveis são bem tocadas.

Answer 5

Meu entendimento é que isso tem a ver com tempo de compilação versus tempo de execução. Em um idioma tipado estaticamente, a maioria da verificação do tipo é realizada durante o tempo de compilação. Em um idioma dinamicamente digitado, a maioria de sua verificação de tipo é realizada em tempo de execução.

Answer 6

Deixe -me responder o contrário:

Existem dois tipos diferentes de programação "dinâmica".

Um é "dinamicamente digitado", o que significa que você tem algum tipo de shell onde pode programar digitando definições nesse shell, pense nisso como o shell ocioso do Python.

O outro tipo de programação dinâmica é mais teórica. Um programa dinâmico, é aquele que pode alterar sua própria fonte. Ele precisa de algum nível de introdução e é frequentemente usado para alterar a memória do programa nos microcontroladores. Às vezes, gerar tabelas de pesquisa para trituração de números é chamado de programação dinâmica.