Qu'est-ce que cela signifie pour un langage statiquement typé?

https://stackoverflow.com/questions/3623323

26-09-2019
|

Question

Si je comprends bien que cela signifie que l'on peut éventuellement écrire un programme pour prouver formellement qu'un programme écrit dans un langage typé statiquement sera libre d'un certain (petit) sous-ensemble de défauts.

Mon problème est que suit:

Supposons que nous avons deux langues Türing complètes, A et B. A est supposé être « type sûr » et « B » est présumé ne pas être. Supposons que je me donne un programme L pour vérifier l'exactitude de tout programme écrit en A. Qu'est-ce que pour me empêcher de traduire un programme écrit en B à A, l'application de L. Si P traduit de A à B, alors pourquoi n'est pas PL une vérificateur de type valable pour tout programme écrit en B?

Je suis une formation en algèbre et je suis ne fait que commencer à étudier CS donc il pourrait y avoir une raison évidente que cela ne fonctionne pas, mais je aime beaucoup savoir. Toute cette affaire « de sécurité de type » a éperlan fishy me pendant un certain temps.

La solution

Soit A votre langue Turing-complet qui est censé être statiquement typé et laisser A » la langue que vous obtenez de A lorsque vous retirez la vérification de type (mais pas les annotations de type, car ils servent aussi à d'autres fins). Les programmes acceptés de A seront un sous-ensemble des programmes acceptés de A ». Ainsi, en particulier, A » sera également Turing-complet.

Compte tenu de votre traducteur P de B à A (et vice versa). Qu'est-il censé faire? Il pourrait faire l'une des deux choses:

Tout d'abord, il pourrait se traduire par tous les programmes y de B à un programme de A. Dans ce cas, LPY serait toujours retourner vrai que les programmes de A sont par définition correctement tapé.
En second lieu, P pourrait se traduire par tous les programmes y de B à un programme de A ». Dans ce cas, LPY retournerait Vrai si Py se trouve être un programme de A et False sinon.

Comme le premier cas, ne donne pas quelque chose d'intéressant, laissez-nous en tenir au second cas, ce qui est probablement ce que vous voulez dire. La fonction LP définie sur les programmes de B nous dire quelque chose d'intéressant au sujet des programmes de B? Je dis non, parce que ce n'est pas invariant par un changement de P. Comme A est Turing-complet, même dans le second cas P pourrait être choisie de telle sorte que son image se résiderait dans A. Alors LP serait toujours vrai. D'autre part, P pourrait être choisi de telle sorte que certains programmes sont mis en correspondance avec le complément de A dans A ». Dans ce cas, LP crachait Faux pour certains programmes (peut-être tous) de B. Comme vous pouvez le voir, vous ne recevez rien qui ne dépend que de y.

Je peux aussi dire plus mathématiquement de la manière suivante: Il existe une catégorie C de langages de programmation dont les objets sont les langages de programmation et dont les morphismes sont les traducteurs d'un langage de programmation à l'autre. En particulier, s'il existe un morphisme P: X -> Y, Y est au moins aussi expressif que X. Entre chaque paire de langues de Turing-complet, il y a morphisms dans les deux sens. Pour chaque objet X de C (ie pour chaque langage de programmation), nous avons un ensemble associé, disons {X} (mauvaise notation, je sais) de ces fonctions partiellement définies qui peuvent être calculées par des programmes de X. Chaque morphisme P: X - > Y induit alors une inclusion {X} -> {Y} des ensembles. Laissez-nous formellement inverser tous les morphismes P: X -> Y qui induisent l'identité {X} -> {Y}. Je vais appeler la catégorie résultante (qui est, en termes mathématiques, une localisation de C) par C ». Maintenant, l'inclusion A -> A 'est un morphisme dans C'. Cependant, il ne se conserve pas sous automorphismes de A «qui est le morphisme A -> A » est pas un invariant de A « C ». En d'autres termes: de ce point de vue abstrait l'attribut « statiquement typé » ne peut être défini et peut être arbitrairement fixé à une langue

Pour faire mon point plus clair, vous pouvez aussi penser à C » comme la catégorie, par exemple, des formes géométriques dans l'espace en trois dimensions ainsi que les mouvements euclidiens comme morphismes. A « et B sont alors deux formes géométriques et P et Q sont des mouvements euclidiens apportant B à A » et vice versa. Par exemple, A » et B pourrait être deux sphères. Maintenant, fixons un point A «qui doit se tenir pour le sous-ensemble A de A ». Appelons ce point « statiquement typé ». Nous voulons savoir si un point B est statiquement typé. Donc, nous prenons un tel point y, la carte via P à A « et le test, que ce soit notre point marqué sur A ». Comme on peut facilement voir, cela dépend de la carte P choisie ou, en d'autres mots: Un point marqué sur une sphère n'est pas préservée par automorphismes (qui sont des mouvements euclidiens qui tracent la sphère sur lui-même) de cette sphère

Autres conseils

Si vous pouvez traduire tous B '(un programme écrit en B) en un équivalent A' (ce qui est correct si B » est), puis la langue B bénéficie tout autant « type de sécurité » comme langue a (dans un sens théorique, bien sûr ;-) - en gros, cela voudrait dire que B est telle que vous pouvez faire de type parfait inférences. Mais qui est extrêmement limitée pour un langage dynamique - par exemple, pensez à:

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

où thefun (Assumons) est typesafe pour argument int, mais pas pour l'argument str. Maintenant - comment traduisez-vous cela A linguistique en premier lieu ...

Une autre façon de faire le même point comme cela a été fait est que votre question constitue une preuve par contradiction que ce soit:

A ne peut pas être mis en correspondance avec B
sécurité de type n'est pas une propriété lexical d'une langue

ou les deux. Mon intuition dit que ce dernier est sans doute le point le collage. Que la sécurité-type est une propriété de méta-linguistique

Il n'y a rien « fishy » à ce sujet. ;)

L'ensemble de Turing-complet langues qui sont le type de sécurité par rapport à une non négligeable [ 1 ] système de type T est un strict sous-ensemble des langues Turing-complet. En tant que tel, dans le cas général, aucun traducteur P ^-1 de B A existe; Par conséquent, ni ne traducteur- aucune cum de type-checker LP ^-1 .

Une réaction réflexe du genou à ce genre de réclamation pourrait être: Non-sens! Les deux et B sont Turing-complet, donc je peux exprimer any fonction calculable en soit langue! Et, en effet, cela est exact - vous peut exprimer toute fonction calculable dans les deux langues; Cependant, bien souvent, vous pouvez également exprimer un peu plus . En particulier, vous pouvez construire des expressions dont la sémantique dénotationnelle ne sont pas bien définis, tels que ceux qui pourraient essayer avec plaisir de prendre la somme arithmétique des chaînes de caractères « foo » et « bar » (ce qui est l'essentiel de ~~Chubsdad~~ Alex Martelli La réponse de). Ces sortes d'expressions peuvent être « dans » la langue B , mais peut tout simplement pas exprimable dans la langue A , parce que la sémantique dénotationnelle ne sont pas définies, donc il n'y a pas raisonnable façon de les traduire.

Ceci est l'une des grandes forces de typage statique: Si votre système de type ne peut pas prouver, au moment de la compilation, que la fonction mentionnée ci-dessus recevra tous les paramètres, mais ceux pour lesquels les résultats de l'opérateur d'addition arithmétique est bien définie , il peut être rejeté comme mal typ.

Notez que si ce qui précède est le genre d'exemple usuel d'expliquer le bien-fondé d'un système de type statique, il est peut-être trop modeste. En général, un système de type statique nécessité de ne pas se limiter à l'application de type simple correction des paramètres, mais peut en effet exprimer tout propriété souhaitée d'un programme qui peut être prouvé au moment de la compilation. Par exemple, il est possible de construire des systèmes de type qui mettent en application la contrainte que l'on libérer une poignée de système de fichiers ( par exemple à une base de données, fichier, socket réseau, etc. ) dans le même portée dans laquelle elle a été acquise. De toute évidence, c'est extrêmement utile dans des domaines tels que les systèmes d'aide à la vie, entre autres, où démontrable de justesse autant de paramètres du système possible est absolument essentiel. Si vous remplissez le système de type statique, vous pouvez obtenir ces sortes de preuves gratuitement.

[ 1 ] Par nonbanal, je veux dire de telle sorte que pas

toutes les expressions possibles sont bien typés.

Je crois comprendre que cela a à voir avec la compilation par rapport à l'exécution. Dans un langage typé statiquement la majorité des contrôles de type est effectuée lors de la compilation. Dans un langage typé dynamiquement, la majorité de sa vérification de type est effectuée lors de l'exécution.

Permettez-moi de répondre à cette l'autre sens:

Il existe deux types de programmation "dynamique" différents.

est « typé dynamiquement », ce qui signifie que vous avez une sorte de coquille où vous pouvez programmer en tapant les définitions dans cette coquille, pensez comme la coquille de IDLE Python.

L'autre type de programmation dynamique, est un plus théorique. Un programme dynamique, est celui qui peut changer sa propre source. Il a besoin d'un certain niveau de introjection, et est souvent utilisé pour changer la mémoire du programme sur les microcontrôleurs. Parfois, la génération des tables recherche pour crissement numéro est appelé programmation dynamique.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow