Mesure de puissance autre que l'exhaustivité de Turing

J'ai d'abord essayé de poser cette question sur StackOverflow, mais c'était trop subjectif :-(. Je m'intéresse aux méthodes de définition de la puissance des langages de programmation. La complétude de Turing en est une, mais elle est presque universellement satisfaite. Ce qui serait bien, c'est de définir un mesure de la puissance qui fait la distinction entre les langages de programmation qui sont réellement utilisés. Par exemple, quelqu'un peut-il proposer une méthode non subjective qui ferait la distinction entre l'assemblage et Java?

L'exhaustivité de Turing signifie qu'un langage est au maximum puissant dans ce qu'il peut produire (ce qui signifie à peu près qu'il peut faire n'importe quoi sans temps dans le monde réel). Donc, si nous voulons définir une mesure de puissance plus forte, nous devons adopter une autre approche. La brièveté a été suggérée dans la question initiale, mais ce n'est pas du tout facile à définir. Quelqu'un a-t-il d'autres suggestions?

La notion que vous recherchez s'appelle expressivité et Matthias Felleisen a une définition mathématiquement rigoureuse:

" Sur la puissance expressive des langages de programmation "

www.ccs.neu.edu/scheme/pubs/scp91-felleisen.ps.gz (version Postscript)

L'intuition derrière l'idée est que si vous avez deux programmes équivalents dans deux langues différentes - disons, programme A en langue X et programme B en langue Y - et si vous effectuez un changement local vers A qui nécessite un changement global vers B , alors X est plus expressif que Y.

Un exemple fourni par Felleisen est l'affectation: dans les langages de programmation Scheme, vous pouvez supprimer l'opérateur d'affectation et avoir toujours un langage complet de Turing. Cependant, dans une langue aussi restreinte, l'ajout d'une fonctionnalité qui serait localisée si l'affectation était autorisée nécessiterait une modification globale du programme sans affectation.

Ma discussion a simplifié certains détails, et vous devriez lire le document lui-même pour le compte rendu complet.

Pour répondre à votre autre question: vous pouvez dire que Java est plus expressif que l'assembly car vous pouvez ajouter une nouvelle classe à votre programme Java, puis bénéficier des avantages du polymorphisme en faisant en sorte que d'autres parties de votre programme appellent ses méthodes sans modification globale. La gestion des exceptions est un autre exemple où Java est plus expressif que l'assemblage: il vous suffit d'écrire une seule throwinstruction pour transférer le contrôle vers le haut de la pile. À un niveau plus élémentaire, vous pouvez également ajouter une nouvelle caseinstruction vers le début d'un switchet vous n'aurez pas à vous soucier de recalculer les sauts à la main.

Si je comprends bien votre question, vous recherchez néanmoins quelque chose qui est relativement mesurable et pas seulement un appel de jugement subjectif. Si c'est le cas, je préférerais personnellement le temps nécessaire pour résoudre un problème particulier (en moyenne sur tous les problèmes et tous les programmeurs). Dans cette mesure, vous devrez peut-être prendre en compte non seulement le langage lui-même, mais également le cadre / l'API utilisé avec lui. La syntaxe succincte est un très petit facteur: un facteur beaucoup plus important est que la fonctionnalité la plus souvent requise est facilement accessible.

Si vous cherchez quelque chose de plus subjectif, je dirais à quel point c'est amusant . Les programmeurs ont tendance à être des gens qui veulent résoudre les problèmes, donc un langage de programmation amusant pour les programmeurs sera inévitablement celui qui résoudra le plus de problèmes. Cette mesure tient compte du fait que différentes personnes ont des préférences différentes sur la façon d'utiliser les choses, donc le «meilleur» langage de programmation sera celui qui séduira le plus de programmeurs. Cependant, vous devrez peut-être considérer non seulement le langage de programmation et l'API ici, mais également l'environnement (IDE), qui est bien sûr ce avec quoi le programmeur interagit réellement.

Je définirais la puissance d'une langue en fonction de sa productivité. Beaucoup de gens ont tendance à parler de productivité en termes d'écriture rapide de code, mais comme la majorité du cycle de vie d'un programme est la maintenance, pas le développement, une meilleure mesure est la facilité avec laquelle vous pouvez lire et déboguer le code, surtout quand il est écrit par quelqu'un autre. Les langues les plus puissantes sont celles qui sont les plus faciles à lire et à entretenir.

Vous devez mieux définir votre terminologie.

Turing l'exhaustivité ne concerne pas le «pouvoir» dans le sens que vous entendez probablement. Il s'agit plutôt de calculabilité; c'est-à-dire si une langue donnée peut exprimer n'importe quel programme qui peut être implémenté à l'aide d'une machine de Turing. Il s'avère que presque tous les langages de programmation sont Turing complets.

Ce que vous recherchez probablement, c'est une mesure de ce que l'on appelle «l'expressivité» du langage de programmation. Je ne sais pas si une telle mesure existe, ou si elle existe, si elle est utile. Fondamentalement, différents langages de programmation expriment mieux des solutions à différents types de problèmes.

ÉDITER

Juste pour le préciser, les langages de programmation n'ont pas de propriété connue sous le nom de "puissance". Il existe un concept communément appelé «expressivité» ou «pouvoir expressif» d'un langage de programmation. L'expressivité dépend en partie de la facilité d'écriture de programmes succincts pour résoudre des problèmes particuliers. Mais il existe également une mesure considérable de la facilité de lecture et d'écriture des programmes. C'est un peu comme la «beauté». Je le saurai quand je le verrai, mais ne me demandez pas de le définir.

La simple comparaison du nombre de caractères ne vous donne pas une mesure adéquate de l'expressivité. Sinon, vous pourriez rendre un langage plus expressif en compressant le code source ... et c'est absurde. En fait, je ne connais aucune mesure objective de l'expressivité et je soupçonne fortement qu'il n'en existe pas. Ce qui rend effectivement la caractéristique inutile et assez inintéressante.