Comment vérifier / prouver l'orthogonalité d'un langage de programmation?

Je connais le concept d'orthogonalité, mais du point de vue du langage de programmation, existe-t-il un moyen de le vérifier / le prouver?

Par exemple en C #, on peut utiliser publicou staticpour une signature de méthode. Vous pouvez utiliser l'un ou les deux et ils n'interfèrent pas les uns avec les autres, ils sont donc orthogonaux entre eux, non?

Ma question est, comment dois-je faire pour le reste des fonctionnalités, en particulier les fonctionnalités qui ne sont pas liées les unes aux autres?

Toutes les fonctionnalités doivent-elles coexister / s'empiler ensemble?

Existe-t-il un langage de programmation 100% orthogonal?

Je ne suis pas sûr que l'orthogonalité puisse servir de métrique utile ou valide dans le cas de langages d'ordre général comme C #, car elle nécessite la distinction des "opérations" et des "opérandes" - les petites parties du langage qui ne sont pas facilement se distingue dans des langages de haut niveau comme C #.

Ma compréhension de l'orthogonalité est basée sur le langage Assembleur où l' orthogonalité du jeu d'instructions d'un certain CPU ou microcontrôleur particulier a indiqué s'il y a des contraintes sur les opérations effectuées par ce CPU ou contrôleur en fonction des types de données. Au début, cela était important car toutes les opérations du processeur ne prenaient pas en charge des nombres fractionnaires ou des nombres de longueur différente, etc.

À cet égard, je préfère vérifier l'orthogonalité du langage intermédiaire commun utilisant le langage Stack Machine comme cible pour le compilateur C #, pas C # lui-même.

Si vous êtes vraiment intéressé par l'orthogonalité de C # et que je ne me trompe pas ici (pour quelque raison que ce soit), je suggérerais de regarder vers certains algorithmes de programmation génétique . Vous pouvez les utiliser pour générer différents programmes à partir de l'ensemble de mots-clés donné (même ceux sans signification) et vous pouvez simplement vérifier automatiquement si ceux-ci sont compilables. Cela vous aiderait à voir automatiquement quels éléments du langage peuvent être combinés et à dériver certains aspects de votre métrique d'orthogonalité.

Le terme «orthogonalité» est un terme profane pour une notion mathématique précise: les termes du langage forment une algèbre initiale (recherchez-la dans Wikipedia).

Cela signifie essentiellement "il y a une correspondance 1-1 entre la syntaxe et le sens". Cela signifie: il y a exactement une façon d'exprimer les choses, et, si vous pouvez mettre une expression à un endroit particulier, vous pouvez également y mettre n'importe quelle autre expression.

Une autre façon de penser «orthogonale» est que la syntaxe obéit au principe de substitution. Par exemple, si vous avez une instruction avec un emplacement pour une expression, n'importe quelle expression peut y être placée et le résultat est toujours un programme syntaxiquement valide. De plus, si vous remplacez

Je tiens à souligner que le «sens» n'implique pas un résultat de calcul. Clairement, 1 + 2 et 2 + 1 sont tous les deux égaux à 3. Cependant, les termes sont distincts et impliquent un calcul différent même s'il a le même résultat. La signification est différente, tout comme deux algorithmes de tri sont différents.

Vous avez peut-être entendu parler de «arbre de syntaxe abstraite» (AST). Le mot «abstrait» signifie ici précisément «orthogonal». Techniquement, la plupart des AST ne sont pas en fait abstraits!

Peut-être avez-vous entendu parler du langage de programmation "C"? La notation de type C n'est pas abstraite. Considérer:

int f(int);

Voici donc une déclaration de fonction retournant un type int. Le type de pointeur vers cette fonction est donné par:

int (*)(int)

Remarque, vous ne pouvez pas écrire le type de la fonction! La notation de type C suce bigtime! Ce n'est pas abstrait. Ce n'est pas orthogonal. Supposons maintenant que nous voulons créer une fonction qui accepte le type ci-dessus au lieu de int:

int (*) ( int (*)(int) )

Tout va bien .. mais .. si nous voulons le retourner à la place:

int (*)(int) (*) (int)

Woops! Invalide. Ajoutons des parens:

(int (*)(int)) (*) (int)

Woops! Ça ne marche pas non plus. Nous devons le faire (c'est le seul moyen!):

typedef int (intintfunc*) (int);
intintfunc (*)(int)

Maintenant c'est OK, mais devoir utiliser un typedef ici est mauvais. C est nul. Ce n'est pas abstrait. Ce n'est pas orthogonal. Voici comment procéder en ML, qui est:

 int -> (int -> int)

Nous condamnons C au niveau de la syntaxe.

Ok, laisse maintenant floguer C ++. Nous pouvons corriger la stupidité ci-dessus avec des modèles et obtenir une notation de type ML (plus ou moins):

fun<int, int>
fun< fun<int,int>, int>

mais le système de type réel est fondamentalement vicié par les références: si Tc'est un type, alors est-ce T&un type? La réponse est waffly: au niveau de la syntaxe, si vous avez un type U = T &, alors U & est autorisé mais cela signifie simplement T &: une référence à une référence est la référence d'origine. Ça craint! Il casse sémantiquement l'exigence d'unicité. Pire: T & & n'est pas autorisé syntaxiquement: cela rompt le principe de substitution. Les références C ++ cassent donc l'orthogonalité de deux manières différentes, en fonction du temps de liaison (analyse syntaxique ou analyse de type). Si vous voulez comprendre comment faire cela correctement ... il n'y a aucun problème avec les pointeurs!

Presque aucune langue réelle n'est orthogonale. Même Scheme, qui prétend une grande clarté d'expression, ne l'est pas. Cependant, de nombreux bons langages peuvent être considérés comme ayant une «base de caractéristiques orthogonales raisonnablement proche» et c'est une bonne recommandation pour un langage, appliqué à la fois à la syntaxe et à la sémantique sous-jacente.

Prouver l'orthogonalité se révèle négatif. Cela signifie que vous n'avez pas de constructions non orthogonales, ce qui signifie qu'il est beaucoup plus facile de prouver que quelque chose n'est pas orthogonal.

Dans la pratique, la plupart des gens parlent d'orthogonalité des langages de programmation en termes de degrés plutôt que d'être complètement orthogonaux ou non. Lorsque la connaissance de faire quelque chose dans un contexte se traduit par un autre contexte et «fait ce que vous attendez», cette langue est dite plus orthogonale. LISP est considéré comme hautement orthogonal car tout est une liste, mais je ne pense pas qu'on puisse dire qu'il est 100% orthogonal en raison de certaines redondances qui le rendent plus facile à utiliser. Le C ++ est considéré comme peu orthogonal car il y a beaucoup de petits "pièges" où il ne fonctionne pas tout à fait comme vous le pensez.

Attention, je ne connais rien à ce sujet.

Un rapide coup d'œil sur Wikipedia semble indiquer que l'orthogonalité est principalement dirigée vers les modèles de conception et la conception de systèmes. En termes de langages de programmation, l'entrée indique que les jeux d'instructions sont orthogonaux s'il existe une et une seule instruction pour chaque action possible, ou plutôt qu'aucune instruction ne chevauche une autre.

Pour C #, j'imagine qu'il est orthogonal, dans la mesure où la plupart des astuces de syntaxe ( foreachvient à l'esprit) ne sont que des front-ends vers des versions spécialement formées de la construction de base ( foreachdeviennent des forboucles). Dans l'ensemble, le langage ne prend vraiment en charge que les choses d'une seule manière, même si le sucre syntaxique fournit des moyens supplémentaires de les faire. Et enfin, tout se compile jusqu'à MSIL(ou comme on l'appelle de nos jours) et MSILest probablement orthogonal.

Si vous faites la mise en garde que le sucre syntaxique est essentiellement un "wrapper" pour le faire à la "dure", vous pouvez analyser les différentes fonctionnalités du langage, en omettant le sucre, et voir s'il y a des constructions qui se chevauchent vraiment. Sinon, j'imagine que vous pourriez déclarer la langue orthogonale.

Mes deux centimes.

Ma question est, comment dois-je faire pour le reste des fonctionnalités, en particulier les fonctionnalités qui ne sont pas liées les unes aux autres?

Vous continuez à faire ce que vous faites, en énumérant toutes les combinaisons qui fonctionnent ou qui sont interdites.

C'est tout. C'est assez pénible à faire.

Toutes les fonctionnalités doivent-elles coexister / s'empiler ensemble?

Si toutes les fonctionnalités peuvent être partitionnées en sous-ensembles disjoints qui n'interfèrent pas entre eux, alors bien sûr, tout serait raisonnable.

Toutes les structures de données fonctionnent avec tous les types primitifs. Tous les opérateurs d'expression fonctionnent avec tous les types. Ce sont des définitions courantes de l'orthogonalité. Mais vous voudrez peut-être plus (ou moins)

Parfois, cependant, il existe des cas particuliers en raison de systèmes d'exploitation ou de bibliothèques héritées qui ne sont pas orthogonaux.

De plus, certains types ne sont pas vraiment très conformes du tout. Par exemple, Python vous permet de comparer deux objets de dictionnaire pour le "classement". Mais il n'y a presque pas de définition sensée du "classement" parmi les dictionnaires. Python en définit un, mais c'est assez discutable. Ce cas particulier fait-il échouer les dictionnaires à un test d'orthogonalité?

Dans quelle mesure orthogonale est «assez orthogonale»? Que devez - vous voir pour être satisfait du degré d'orthogonalité dans votre langue.

La liste des fonctionnalités non orthogonales est en effet longue dans la plupart des langages de programmation, par exemple

• les classes anonymes entrent en conflit avec la réflexion java
• conflit d'effacement générique et de type avec réflexion java
• les tableaux sont quelque peu différents des autres objets, en raison de leur type spécial, même s'ils sont des objets.
• les méthodes statiques et les méthodes d'instance ne sont pas les mêmes, par exemple, vous ne pouvez pas remplacer une méthode statique
• classe imbriquée est une réflexion après coup
• impact du typage dynamique vs statique sur la stratégie d'envoi des messages (voir par exemple ce cas périphérique en C #)
• etc.

Ces quelques-uns qui me viennent à l'esprit, mais il y en a beaucoup d'autres, et aussi dans d'autres langues.

Il est difficile de s'assurer qu'il n'y a pas d'interférence subtile entre les fonctionnalités linguistiques. Comme CAR Hoare l'indique dans son article "Hints on Programming Language Design":

Une partie de la conception du langage consiste en l'innovation. Cette activité conduit à de nouvelles fonctionnalités de langage isolément. La partie la plus difficile de la conception du langage réside dans l' intégration : la sélection d'un ensemble limité de fonctionnalités du langage et leur polissage jusqu'à ce que le résultat soit un cadre simple cohérent qui n'a plus de bords rugueux.

Probablement, une bonne chose pour augmenter l'orthogonalité est d'unifier les concepts (cela va dans le sens de la réponse @ karl-bielfeld). Si tout est, disons une liste ou un objet, les chances sont qu'il y aura moins de conflits. Ou au lieu d'avoir une classe imbriquée après coup, faites-en une fonctionnalité de base.

La plupart des articles sur les langages de programmation prouvent certaines propriétés du langage (par exemple la solidité du type) sur un sous-ensemble (un «noyau») du langage qui est formalisé. Ici, nous devons faire le contraire, prouver que toutes les fonctionnalités se composent en toute sécurité. En outre, cela signifie que l'on doit définir ce que signifie «composer». Cela signifie-t-il «courir»? (Dans ce cas, le lien ci-dessus sur le cas de bord avec le typage dynamique et statique est sûr). Cela signifie-t-il être «sûr»? Est-ce que cela signifie être prévisible du point de vue du développeur?

Tout cela est très intéressant - mais aussi très difficile.