Sous-typage implicite vs explicite

Cette page affirme que

de nombreux langages n'utilisent pas de sous-typage implicite (équivalence structurelle), préférant le sous-typage explicite / déclaré (équivalence de déclaration)

J'ai surtout utilisé des langages de programmation qui utilisent un sous-typage explicite . Quels sont les avantages du sous-typage implicite, comme décrit dans les notes ci-dessus.

pl.programming-languages type-theory Frankie Ribery
la source

D'après la FAQ, sur la portée de cet échange: "Le travail dans ce domaine se distingue souvent par son accent mis sur la technique mathématique et la rigueur." Je baisse les votes parce que je ne vois aucune marge de rigueur dans les réponses à cette question.

David Eppstein

Malheureusement, il y a beaucoup plus de place pour la rigueur dans la réponse à cette question que ce que vous pourriez initialement espérer. Beaucoup de personnes très éminentes ont brûlé une grande partie des années 90 aux prises avec des questions apparemment triviales sur le sous-typage. C'est un domaine avec un très faible rapport effort / récompense, malheureusement.

Neel Krishnaswami

oui, il y a beaucoup de place pour les mathématiques et la rigueur dans la réponse à cette question, ou du moins pour expliquer mathématiquement ce qu'est le sous - typage implicite . Je ne suis pas sûr du rapport effort / récompense.

Noam Zeilberger

J'aurais probablement dû dire que c'était "très dur", car après réflexion, je me rends compte que je suis très intéressé par les réponses.

Neel Krishnaswami

D'accord, je suis convaincu. Je supprimerais mon downvote mais le système ne me le permettra pas.

David Eppstein

Réponses:

La réponse courte est "pour vérifier les propriétés supplémentaires du code existant". Une réponse plus longue suit.

Je ne suis pas sûr que «implicite» vs «explicite» soit une bonne terminologie. Cette distinction est parfois appelée sous-typage "structurel" vs "nominal". Ensuite, il y a aussi une deuxième distinction dans les interprétations possibles du sous-typage structurel (décrites brièvement). Notez que les trois interprétations du sous-typage sont vraiment orthogonales, et qu'il n'est donc pas vraiment logique de les comparer les unes aux autres, plutôt que de comprendre les utilisations de chacune.

La principale distinction opérationnelle dans l'interprétation d'une relation structurelle de sous-typage A <: B est de savoir si elle est attestée par une contrainte réelle avec un contenu informatique (runtime / compiletime), ou si elle peut être attestée par la contrainte d'identité. Dans le premier cas, la propriété théorique importante qui doit être respectée est la "cohérence", c'est-à-dire s'il existe plusieurs façons de montrer que A est un sous-type sous-structurel de B, chacune des contraintes qui l'accompagnent doit avoir le même contenu informatique.

Le lien que vous avez donné semble avoir la deuxième interprétation du sous-typage structurel à l'esprit, où A <: B peut être observé par la contrainte d'identité. Ceci est parfois appelé une "interprétation de sous-ensemble" du sous-typage, prenant la vue naïve qu'un type représente un ensemble de valeurs, et donc A <: B juste au cas où chaque valeur de type A est également une valeur de type B. Elle est également parfois appelé "raffinement typage", et un bon article à lire pour la motivation originale est Freeman & Pfenning types de raffinement pour ML . Pour une incarnation plus récente en F #, vous pouvez lire Bengston et al, Refinement types for secure implementations. L'idée de base est de prendre un langage de programmation existant qui peut (ou non) avoir déjà des types mais dans lequel les types ne garantissent pas tant que ça (par exemple, seulement la sécurité de la mémoire), et envisager une deuxième couche de types sélectionnant des sous-ensembles de programmes avec propriétés supplémentaires et plus précises.

(Maintenant, je dirais que la théorie mathématique derrière cette interprétation du sous-typage n'est toujours pas aussi bien comprise qu'elle devrait l'être, et peut-être parce que ses utilisations ne sont pas aussi largement appréciées qu'elles devraient l'être. Un problème est que le "set des valeurs ", l'interprétation des types est trop naïve, et donc parfois elle est abandonnée plutôt que raffinée. Pour un autre argument selon lequel cette interprétation du sous-typage mérite plus d'attention mathématique, lisez l'introduction aux sous- espaces de Paul Taylor dans la dualité de la pierre abstraite .)

Noam Zeilberger
la source

Salut Noam, belle réponse! J'ajouterai que le sous-typage nominal à la OO est fondamentalement un moyen de définir une classe de coercitions non identitaires qui sont néanmoins réalisées par des non-ops. Autrement dit, le sous-typage de la largeur des objets induit par l'héritage implique formellement une contrainte de non-identité (par exemple, une contrainte

signifie que vous jetez le

), mais en disposant séquentiellement les enregistrements en mémoire, vous peut utiliser le même code binaire pour projeter les composants

pour les deux types.

A \times B \times C <: A \times B

$A \times B \times C <: A \times B$

C

$C$

A

$A$

B

$B$

Neel Krishnaswami

C'est le travail de l'optimiseur de déterminer la disposition optimale de la mémoire, donc les contraintes qui sont des identités devraient vraiment être le résultat de l'optimisation.

Andrej Bauer

Donc, juste pour clarifier le commentaire d'Andrej par rapport à ma réponse, dans une interprétation de typage de raffinement, les relations de sous-typage sont toujours observées par la contrainte d'identité par définition , car les types de raffinement n'ont pas de contenu informatique supplémentaire. En d'autres termes, si A et B sont deux raffinements ("sous-ensembles" / "propriétés") d'un type de valeurs X, A <: B affirme que pour chaque valeur x dans X, si x: A alors aussi x: B. Une telle déclaration peut être vérifiée ou falsifiée, mais elle n'a aucun effet au moment de l'exécution, car les preuves que x: A et x: B n'existent pas au moment de l'exécution.

Noam Zeilberger

@Noam: Je suis d'accord, mais seulement lorsque nous parlons de la métathéorie d'une seule langue, et pas si nous parlons de compilation. Les contraintes d'identité peuvent être réalisées par des procédures qui font beaucoup de travail, et les contraintes de non-identité peuvent être réalisées par des procédures qui ne font rien. Concrètement, supposons que nous ayons un type

, et un raffinement

N

$\mathbb{N}$

. Ensuite, nous pourrions implémenter des éléments du raffinement avec un seul mot sans boîte, même si le type complet nécessite une allocation de mémoire pour représenter. Les contraintes d'identité ici doivent être réalisées par un calcul réel.

{x : N | x < 2^{32}}

$\{x:N\;\;|\;\;x < 2^{32}\}$

Neel Krishnaswami

N

$N$

{x : N | x < 2^{32}}

$\{x:N | x < 2^{32}\}$

N

$N$

{x : N | x < 2^{32}}

$\{x:N | x < 2^{32}\}$

Noam Zeilberger

Cette réponse est une sorte de complément minimal à l'excellente réponse de Noam. Un point d'intérêt des données est le sort des concepts C ++, qui a échoué dans une tentative d'unifier les notions nominales et structurelles de type.

Il y a un excellent résumé ici, avec des liens vers une grande partie de la discussion pertinente: http://bartoszmilewski.wordpress.com/2010/06/24/c-concepts-a-postmortem/

Cependant, le résumé ci-dessus ne discute pas en profondeur le problème nominal vs structurel. Il y a un autre écrit ici, qui fait: http://nerdland.net/2009/07/alas-concepts-we-hardly-knew-ye/

Le document clé que les deux pointent est «Simplifier l'utilisation des concepts» de Bjarne Stroustrup: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2906.pdf , qui va dans la pratique problèmes rencontrés en profondeur.

Dans l'ensemble, la discussion est plus pragmatique que rigoureuse. Cependant, il donne un bon aperçu des types de compromis impliqués dans ces questions, en particulier dans le contexte d'un grand langage existant.

sclv
la source