Pourquoi certains langages de programmation sont-ils complets mais manquent-ils de capacités d'autres langages?

42

J'ai rencontré un problème étrange lors de l'écriture d'un interpréteur qui (devrait) être raccordé à des programmes / fonctions externes: les fonctions en 'C' et 'C ++' ne peuvent pas accrocher les fonctions variadiques , par exemple, je ne peux pas créer de fonction qui appelle 'printf' avec exactement les mêmes arguments que ceux obtenus, et doit plutôt appeler une version alternative prenant un objet variadique. Ceci est très problématique car je veux pouvoir créer un objet contenant un crochet anonyme.

Donc, je pensais que c'était étrange depuis Forth , JavaScript , et peut-être une pléthore d'autres langages peuvent le faire très facilement sans avoir à recourir au code assembleur / code machine. Etant donné que d’autres langues peuvent le faire si facilement, cela signifie-t-il que la classe de problèmes que chaque langage de programmation peut résoudre varie en fait d’une langue à l’autre, même si ces langues sont toutes terminées ?

M. Menthe Frais
la source
33
Vous devriez regarder dans les tentes . C'est un type de langage de programmation fascinant qui a intentionnellement le moins d'opérations possibles tout en restant complet. La plupart d'entre eux manquent de types de données de base, de fonctions et même de choses simples comme la déclaration de variables. Personnellement, je pense que coder en eux est très amusant, car cela vous oblige à sortir de votre zone de confort pour essayer quelque chose de incroyablement difficile.
DJMcMayhem
8
Regardez ce que fait une machine de Turing et vous verrez que "Turing-complete" est un très faible obstacle à franchir. Fondamentalement, tout ce qui peut «lire», «écrire» et «sauter» tout en prenant en charge l'arithmétique de base est Turing-complete. C'est bien en dessous du niveau des fonctionnalités linguistiques que vous examinez.
aroth
2
Pour être encore plus ridicule: l’instruction MOV sur un processeur x86 est complète. Voir cl.cam.ac.uk/~sd601/papers/mov.pdf pour plus de détails.
Gareth McCaughan
3
Même le jeu de cartes Magic: The Gathering est complet. La complétude n'a rien à voir avec les caractéristiques d'une langue.
Mât
2
En outre, il existe également des langages de programmation très compliqués qui ne sont pas complets, tels que les vérificateurs de preuves.
盛安安

Réponses:

68

Turing langages complets peuvent calculer le même ensemble de fonctions , qui est l'ensemble des fonctions partielles récursives générales. C'est ça.NkN

Cela ne dit rien sur les fonctionnalités de la langue. Une machine de Turing a des caractéristiques de composition très limitées. Le calcul non typé est beaucoup plus compositionnel, mais il manque de nombreuses fonctionnalités couramment trouvées dans les langues modernes.λ

Cette exhaustivité ne dit rien sur les types, les tableaux / entiers / dictionnaires intégrés, les capacités d'entrée / sortie, l'accès réseau, le multithreading, l'allocation dynamique, ...

Tout simplement parce que Java n’a pas de fonctionnalité X (disons, macros, types de rang supérieur ou types dépendants), elle n’arrête pas subitement de devenir Turing complète.

La complétude et l'expressivité linguistique sont deux notions différentes.

chi
la source
43
Edwin Brady, le concepteur d’Idris, (seulement la moitié) utilise en plaisantant (je ne sais pas s’il l’a inventé) le terme "Tetris-complete" pour exprimer cette différence entre "peut calculer toute fonction calculable sur des nombres naturels" et "peut être utilisé pour écrire des programmes non-triviaux qui interagissent avec l'environnement ".
Jörg W Mittag
12
Vous pouvez également mentionner que vous pourriez avoir ces choses en C / C ++. Il vous suffirait d'écrire du code qui fait office de compilateur en C / C ++ pour un autre langage les contenant, dans lequel votre code compile une chaîne dans votre code C / C ++. Ensuite, vous pouvez simplement programmer quelque chose comme Java dans votre fichier C. Cela représenterait beaucoup de travail, mais c'est possible (certainement parce que C / C ++ est Turing Complete).
Shufflepants
4
@ Shufflepants Je me demande cependant s'il est vraiment utile de dire "je peux le faire en C ++ puisque je peux interpréter un autre langage". Par ce jeton, Java, ML, C ++ sont équivalents. Les TM avec un oracle pour les appels système (E / S) sont également équivalents. Je crains que, par ce raisonnement, pratiquement toutes les langues soient également expressives. Si c'est le cas, ce n'est pas une notion utile de comparer des langues.
chi
9
@chi Vous avez raison, ils sont équivalents. C'est ce que cela signifie d'être Turing Complete. Tout ce qui peut être fait avec un système Turing Complete peut être fait dans un autre système Turing Complete. Ce n'est peut-être pas pratique de le faire dans un système particulier. Et la commodité de faire diverses choses est la principale façon de comparer différents langages de programmation. Mais ce n'est pas ce que la question demandait.
Shufflepants
5
@Rhymoid Si C n'est pas Turing Complete pour des raisons d'accès à la mémoire ou parce qu'il est impossible d'envoyer des signaux arbitraires à un périphérique connecté dont la capacité de stockage est arbitrairement grande, on peut alors affirmer qu'aucune langue ni aucun périphérique du monde réel n'est Turing Complete. . Mais je ne pense pas que ce soit un raisonnement très productif.
Shufflepants
47

Cette complétude est un concept abstrait de calculabilité. Si un langage est complet de Turing, alors il est capable de faire n'importe quel calcul qu'un autre langage complet de Turing peut faire.

Cela ne dit cependant pas à quel point il est pratique de le faire. Certaines fonctionnalités faciles dans certaines langues peuvent être très difficiles dans d’autres, en raison des choix de conception. La complétude dit simplement que vous pouvez faire le calcul. Comme exemple extrême, il peut être difficile d’attacher des fonctions varadiques en C ++, mais il est possible d’écrire un interpréteur JavaScript en C ++ pouvant accrocher des fonctions variadiques.

Le design du langage est un art assez intéressant. L'une des principales étapes à entreprendre consiste à identifier les comportements sur lesquels vous souhaitez former l'épine dorsale de votre langage. Ces comportements sont des choses faciles à faire dans votre langue car ils sont intégrés au rez-de-chaussée. Nous prenons des décisions de conception sur les fonctionnalités à inclure dans toutes les langues.

En ce qui concerne votre exemple particulier, lorsque C a été développé, il était conçu pour fonctionner de manière très proche de celle des langages d’assemblage du jour. Les fonctions variadiques ont simplement poussé des arguments sur la pile, avec très peu de sécurité de types. La mise en œuvre de ces fonctions variadiques a été laissée au compilateur afin d’assurer une portabilité maximale. En conséquence, très peu d'hypothèses ont été formulées sur les capacités du matériel. Au moment où JavaScript est arrivé, la scène avait changé. Il fonctionne déjà dans une machine virtuelle en tant que langage interprété, de sorte que la balance évolue vers la commodité. Autoriser l'accrochage de fonctions variadiques devient raisonnable. Même dans le cas de JavaScript compilé Just In Time, nos compilateurs sont disposés à stocker beaucoup plus d'informations supplémentaires sur les arguments que les compilateurs C de jadis.

Cort Ammon
la source
1
@Wildcard Je considérerais (virtuellement) tous les compilateurs comme malsains. La plupart des langages sont complets en Turing, mais doivent éventuellement être interprétés par / compilés pour assembler, ce qui n'est pas le cas. Mais c’est une limitation physique nécessaire: le matériel n’est jamais puissant. Néanmoins, la calculabilité offre de nombreux concepts utiles qui "s’appliquent", dans un sens pratique, aux ordinateurs du monde réel.
chi
3
@Wildcard Dans ce sens trivial. Assembly (et C) a des pointeurs de taille fixe, qui ne peuvent traiter qu’une quantité limitée de mémoire. En théorie, nous pourrions définir un assemblage où les pointeurs sont des éléments naturels illimités, mais je n’appellerais plus cela "assemblée" - j’appellerais URM ou quelque chose du genre. En pratique, nous prétendons simplement que les limites physiques sont suffisamment grandes pour permettre l’exécution de nos programmes. Ainsi, même si un ordinateur n’est qu’une machine à états finis (ce qui implique qu’il ne peut par exemple pas effectuer d’addition), nous le considérons plus comme une machine de Turing ( donc l'addition est faisable).
chi
4
@chi Ce n'est pas tout à fait exact. Tout d’abord, pratiquement tout le monde considère C comme étant complet de Turing parce que nous attribuons généralement cette formulation en partant de l’hypothèse «vous avez assez de mémoire». Pour le très petit nombre de personnes qui doivent s'inquiéter de la formulation plus stricte où de telles hypothèses sont invalides, C ne spécifie pas la taille d'un pointeur ni une limite sur la quantité de mémoire pouvant être adressée. Ainsi, même dans le sens le plus strict et absolu de «Turing complete», C est effectivement Turing complet.
Cort Ammon
3
@CortAmmon, je ne suis pas d'accord. Si nous formalisions la sémantique de C, en essayant d'intégrer l'hypothèse "assez de mémoire", nous échouerions car il sizeof(void *)est tenu d'évaluer la norme ISO C. Cela nous oblige à limiter la quantité de mémoire pour un programme donné, à quelque chose de grand - mais toujours limité. Par exemple, je ne peux pas écrire un programme dont la sémantique ajoute deux éléments naturels arbitraires. C peut toujours être rendu Turing puissant via les E / S, en utilisant des fichiers tels que des bandes TM (comme le fait remarquer @Hurkyl ci-dessus). Je suis d'accord pour dire qu'il ne s'agit pas d'un problème en pratique.
chi
7
Je suggère le nouveau langage C-inf, qui est exactement le même que C, sauf que trop de mémoire est allouée via la récursivité ou l'allocation de tas, le programme est abandonné, recompilé avec une valeur plus grande pour sizeof (void *) et sizeof (size_t), et recommence à courir depuis le début.
gnasher729
26

Pensez aux langages de programmation comme à différents véhicules terrestres: vélos, voitures, aéroglisseurs, trains.

Turing Completeness indique que "ce véhicule peut aller où n'importe quel autre véhicule peut aller." C'est-à-dire que vous pouvez calculer toutes les mêmes fonctions. Entrée à sortie, début à la fin.

Mais, cette déclaration ne dit rien sur la façon dont vous y parvenez. Ce peut être sur des rails, sur des routes, dans les airs. De la même manière, Turing Completeness ne dit rien sur la façon dont vous calculez une fonction. Vous pouvez utiliser la récursivité, ou l'itération, ou des automates cellulaires étranges. Vous pouvez utiliser des types ou non, vous pouvez utiliser des techniques dynamiques ou statiques. Mais si vous ne tenez compte que des fonctions (ou des ensembles / langages formels) que vous pouvez calculer, à condition que vous soyez Turing Complete, ces fonctionnalités vous donnent le même pouvoir.

jmite
la source
4
C'est une excellente analogie. Cela s'étend également à la question que j'ai vue ailleurs sur ce site, à savoir s'il pourrait y avoir d'autres modèles de calcul qui surpassent une machine de Turing: dans cette analogie, les avions et les vaisseaux spatiaux sont plus que Turing Complete, et les bateaux à moteur sont un autre type de machine entièrement. :)
Wildcard
2
Un déplacement plus rapide que la lumière est probablement une meilleure analogie pour le calcul super-Turing. C'est peut- être possible, mais la plupart des gens pensent que non.
Jmite
@jmite Bien sûr, il n'y a toujours pas de preuves solides qui suggèrent que nos cerveaux sont des ordinateurs super-durs. Notre (apparente) incapacité à envisager des machines non durables peut provenir de cela, bien que ce ne soit pas nécessairement une barrière insurmontable. Les avions sont en fait une bonne analogie - ils vont juste "en ligne droite" entre deux points, ignorant le terrain. Si nous pouvions ignorer la topologie de l'espace-temps lui-même, nous pourrions également voler plus vite que la lumière. Non pas que je dise qu'il est possible d'ignorer la topologie de l'espace-temps,
remarquez bien
1
@Luaan C'est vrai, mais notre cerveau n'a pas nécessairement besoin d'être super-Turing pour comprendre un ordinateur super-Turing. Je peux décrire la sémantique d'une machine de Turing en utilisant un langage de terminaison plus faible, tel que Simply Typed Lambda Calculus, en écrivant une fonction qui prend une MT et son état et la passe à l'état suivant. Je ne peux pas réellement utiliser la machine dans cette langue (car cela peut prendre des étapes infinies), mais je peux écrire à quoi ressemble chaque étape.
Jmite
@Luaan, "il n'y a toujours pas de bonne preuve pour suggérer que notre cerveau est un ordinateur super- dur " - peut-être, mais il n'y a aucune preuve pour suggérer que l'esprit humain n'est qu'une machine de Turing. Puisqu'aucune machine de Turing ne peut être dirigée vers un endroit quelconque qui ne puisse être attribuée à des idées nées de l'esprit - il reste la distinction que la vie peut créer des idées et que les dispositifs mécaniques ne le peuvent pas. Mais en ce qui concerne les modèles de calcul, je pense que les machines de Turing englobent avec succès tout ce que l’on peut raisonnablement appeler «calcul», idées et rêves et ainsi de suite.
Wildcard
17

Ce que vous demandez essentiellement, c’est la différence entre le pouvoir de calcul et ce que l’on appelle communément le pouvoir d’expression (ou simplement l’ expression ) d’un langage (ou d’un système de calcul).

Puissance de calcul

Le pouvoir de calcul fait référence aux types de problèmes que le langage peut traiter. La classe de puissance de calcul la plus connue est celle qui équivaut à une machine de Turing universelle . Il existe de nombreux autres systèmes de calcul, tels que les machines à accès aléatoire , le λ-calcul , le calculateur combinatoire SK , les fonctions µ-récursives , les WHILEprogrammes et bien d'autres. Et il s'avère que tous peuvent se simuler, ce qui signifie qu'ils ont tous la même puissance de calcul.

Cela donne lieu à la thèse de Church-Turing (nommée d'après Alonzo Church qui a créé le λ-calcul et Alan Turing qui a créé la machine de Turing universelle). The Church-Turing-Thesis est une hypothèse sur la calculabilité à deux aspects:

  1. tous les systèmes informatiques capables de calcul général sont également puissants, et
  2. Un être humain qui suit un algorithme peut calculer exactement les fonctions qu'une machine de Turing (et donc n'importe lequel des autres systèmes) peut calculer.

La seconde est plus importante dans le domaine de la philosophie de l’esprit que dans la science informatique.

Cependant, la thèse de l'Église de Turing ne dit pas deux choses qui sont très pertinentes pour votre question:

  1. quelle est l' efficacité des différentes simulations et
  2. comment pratique le codage d'un problème.

Un exemple simple pour (1): sur un ordinateur à accès aléatoire, la copie d'un tableau prend du temps proportionnellement à sa longueur. Sur une machine Turing, cependant, cela prend du temps proportionnellement au carré de la longueur de la matrice, car la machine Turing n’a pas d’accès mémoire aléatoire, elle ne peut se déplacer sur la bande, cellule par cellule. Par conséquent, il doit se déplacer n fois sur les n éléments du tableau pour les copier. Ainsi, différents modèles de calcul peuvent avoir différentes caractéristiques de performance, même dans le cas asymptotique, où nous essayons d’abstraire les détails de la mise en oeuvre.

Les exemples pour (2) abondent: λ-calcul et Python sont tous deux Turing-complete. Mais préférez-vous écrire un programme en Python ou en λ-calcul?

J'ai également contourné une troisième ride jusqu'à présent: tous ces systèmes originaux ont été conçus par des logiciens, des philosophes ou des mathématiciens, et non par des informaticiens… simplement parce que les ordinateurs et donc l'informatique n'existaient pas. Tout cela remonte au début des années 1930, avant même les toutes premières expériences de Konrad Zuse (qui n'étaient de toute façon pas programmables et / ou Turing complètes). Ils ne parlent que de "fonctions calculables sur les nombres naturels".

Il se trouve qu’il ya beaucoup de choses que vous pouvez exprimer comme fonctions sur les nombres naturels - après tout, nos ordinateurs modernes se débrouillent même avec beaucoup moins que cela (essentiellement 3-4 fonctions sur les nombres 0 et 1, et c’est tout ), mais par exemple, quelle fonction un système d’exploitation calcule-t-il?

Cette notion d'E / S, d'effets secondaires, en interaction avec l'environnement, n'est pas capturée par l'idée de "fonctions sur des nombres naturels". Et pourtant, il est assez important, puisque, comme Simon Peyton Jones a dit une fois « Toute une fonction pure, sans effets secondaires ne, est de rendre votre CPU chaud » , auquel un membre du public a répondu « En fait, c'est un côté -Effet aussi! "

Edwin Brady , le concepteur d’ Idris , (seulement la moitié) utilise en plaisantant (je ne sais pas s’il l’a inventé) le terme "Tetris-complete" pour exprimer cette différence entre "peut calculer toute fonction calculable sur des nombres naturels" et "peut être utilisé pour écrire des programmes non-triviaux qui interagissent avec l'environnement ". Encore plus ironiquement, il le démontre en mettant en œuvre un clone de Space Invaders dans Idris , mais il se dit confiant que Tetris se réduit à Space Invaders.

Une autre chose à souligner est que non seulement l'équivalence de Turing n'est pas nécessairement suffisante pour parler d'écriture de programmes "utiles", elle peut aussi ne pas être nécessaire . Par exemple, SQL n'est devenu équivalent à Turing qu'avec ANSI SQL: 1999 , mais il était encore utile auparavant. En fait, certains pourraient dire que le fait de rendre l'équivalent de Turing n'a pas du tout augmenté son utilité. Il existe de nombreux langages spécifiques à un domaine qui ne sont pas équivalents à Turing. Le langage de description de données n'est généralement pas (et ne devrait pas l'être). Total Languages ​​ne peut évidemment pas être équivalent à Turing, mais vous pouvez toujours y écrire des boucles d’événements, des serveurs Web ou des systèmes d’exploitation. Il existe également des langues équivalentes à Turing, mais considérées comme une erreur.

Donc, dans l’ensemble, l’équivalence de Turing n’est pas très intéressante, à moins que vous ne souhaitiez analyser statiquement des programmes.

Expressivité

En supposant que notre système de calcul soit assez puissant pour résoudre même notre problème, nous devons ensuite exprimer notre algorithme de résolution du problème dans une sorte de notation formelle pour ce système. En d'autres termes: nous devons écrire un programme dans un langage informatique. C'est là qu'intervient la notion d' expressivité .

Il s'agit essentiellement de la "facilité" ou du "plaisir" d'écrire notre programme dans notre langage de programmation particulier. Comme vous pouvez le constater, la notion est assez vague, subjective et plus psychologique que technique.

Cependant, il existe des tentatives de définitions plus précises. Le plus célèbre (et le plus rigoureux que je connaisse) est de Matthias Felleisen dans son article Sur le pouvoir expressif des langages de programmation (les deux premières pages contiennent une introduction douce, le reste du document est plus charnu).

L’intuition principale est la suivante: lors de la traduction d’un programme d’une langue à une autre, certains des changements que vous devez faire sont localisés (par exemple, la conversion de FORboucles en WHILEboucles ou de boucles en conditionnelles GOTO), et certaines nécessitent un changement de structure du programme.

Lorsque vous pouvez remplacer une caractéristique d'une langue par une autre, d'une transformation différente, par des transformations locales uniquement, ces fonctionnalités sont réputées n'avoir aucun effet sur le pouvoir d'expression. C'est ce qu'on appelle le sucre syntaxique .

D'autre part, si cela nécessite un changement de la structure globale du programme, la langue dans laquelle vous traduisez est dite incapable d'exprimer la fonctionnalité. Et la langue à partir de laquelle vous traduisez est dite plus expressive (en ce qui concerne cette fonctionnalité).

Notez que cela donne une définition de l'expressivité objectivement mesurable. Notez également que la notion dépend du contexte de la fonctionnalité et qu'elle est comparative. Ainsi, si chaque programme de la langue A peut être traduit en langue B avec uniquement des modifications locales et s'il existe au moins un programme en langue B qui ne peut pas être traduit en A avec des modifications locales uniquement, la langue B est strictement plus expressive que la langue. UNE. Cependant, le scénario le plus probable est que de nombreux programmes dans les deux langues peuvent être traduits, mais il existe certains programmes dans les deux langues qui ne peuvent pas être traduits dans une autre. Cela signifie qu’aucun langage n’est strictement plus expressif que l’autre, ils ont juste des caractéristiques différentes qui permettent à différents programmes de s’exprimer de différentes manières.

Cela donne une définition formelle de ce que signifie être "plus expressif", mais ne capture toujours pas les notions psychologiques à la base du phénomène. Par exemple, le sucre syntaxique, selon ce modèle, n'augmente pas le pouvoir d'expression d'une langue, car il peut être traduit en utilisant uniquement des modifications locales. Cependant, nous savons par expérience que ayant FOR, WHILEet IFdisponibles, même si elles ne sont que du sucre syntaxique pour conditionnel GOTOmarques exprimant notre intention plus facile .

Le fait est que différentes langues ont des caractéristiques différentes qui permettent d’exprimer différentes façons de penser à un problème plus facilement ou plus difficilement. Et certaines personnes trouveront peut-être un moyen d’exprimer leur intention plus facilement et d’autres, d’une manière différente.

Un exemple que j’ai trouvé dans la balise Ruby sur StackOverflow: de nombreux utilisateurs qui suivent la balise Ruby affirment que les boucles sont plus faciles à comprendre que la récursion et que la récursivité n’est que pour les programmeurs fonctionnels avancés et que les boucles sont plus intuitives pour les nouveaux arrivants, mais j’ai vu plusieurs cas de les nouveaux venus qui écrivent intuitivement un code comme celui-ci:

def rock_paper_scissors
  get_user_input
  determine_outcome
  print_winner
  rock_paper_scissors # start from the top
end

Ce qui conduit généralement plusieurs personnes à commenter que "cela ne fonctionne pas" et "elles le font mal" et que la "manière correcte" est la suivante:

def rock_paper_scissors
  loop do
    get_user_input
    determine_outcome
    print_winner
  end
end

Il est donc clair que, pour certaines personnes, la récursion de la queue est un moyen plus naturel d’exprimer le concept de "bouclage" que les constructions en boucle.

Sommaire

Le fait que deux langues soient équivalentes à Turing en dit long sur le fait qu’elles peuvent calculer le même ensemble de fonctions sur des nombres naturels qu’une machine de Turing. C'est ça.

Cela ne dit rien sur la rapidité avec laquelle ils calculent ces fonctions. Cela ne dit rien sur la facilité à exprimer ces fonctions. Et cela ne dit rien sur ce qu’ils peuvent faire en plus des fonctions de calcul sur les nombres naturels (par exemple, la liaison à des bibliothèques C, la lecture des entrées de l’utilisateur, l’écriture de la sortie sur l’écran).

Cela signifie-t-il que la classe de problèmes pouvant être résolus par chaque langage de programmation varie d’un langage à l’autre, même si ces langages sont tous terminés?

Oui.

  1. Il existe des problèmes qui ne sont pas couverts par le terme "Turing-complete" (qui ne concerne que les fonctions de calcul sur des nombres naturels), tels que l'impression à l'écran. Deux langues peuvent être complètes, mais l’une peut permettre l’impression à l’écran et l’autre pas.
  2. Même si les deux langues peuvent résoudre les mêmes problèmes, cela n’indique en rien la complexité de l’encodage et la facilité avec laquelle il peut être exprimé. Par exemple, C peut résoudre tous les problèmes que Haskell peut résoudre, simplement en écrivant un interprète Haskell en C… mais vous devez écrire d'abord l'interprète Haskell pour résoudre un problème de cette façon!
Jörg W Mittag
la source
7

Tous les langages de programmation complets de Turing peuvent implémenter le même ensemble d'algorithmes. Donc, si vous voyez qu'un algorithme est très difficile à implémenter dans un langage particulier, cela ne veut pas dire que c'est impossible.

Rappelez-vous qu'un langage est constitué de syntaxe et de sémantique. Parfois, l’ensemble des mots appartenant à une langue donnée n’est pas minimal pour être considéré comme complet, il existe des fonctionnalités qui facilitent les choses (c’est pourquoi elles sont appelées fonctionnalités ). Si vous supprimez ces fonctionnalités, le langage est toujours complet.

Certains d'entre eux pourraient être d'intérêt:

Euge
la source
5

Tous les langages complets de Turing peuvent calculer les mêmes choses.

Si vous essayez de mettre en œuvre une langue moderne, vous remarquerez que la plupart de ses caractéristiques n'ajouter des capacités de calcul. Beaucoup de ces fonctionnalités peuvent être réduites à des fonctionnalités plus simples qui existent déjà dans le même langage.

Voici quelques exemples:

  • Si vous n'avez pas d'énums, vous pouvez utiliser des entiers.
  • Si vous ne disposez pas de tampons connaissant leur taille, vous pouvez créer un type contenant une taille et un tampon ne connaissant pas sa taille.
  • Si vous n'avez pas de vérification des limites des tampons, vous pouvez simplement vérifier l'index chaque fois que vous les utilisez.
  • Si vous n'avez pas de fonctions variadiques, vous pouvez créer une fonction qui utilise un tampon connaissant sa taille et lisant à partir de ce tampon les mêmes informations que celles que vous obtiendriez à partir d'arguments formels.
  • Si vous n'avez pas d'opérateur, vous pouvez utiliser des fonctions.
  • Si vous n'avez pas de types pouvant hériter l'un de l'autre, vous pouvez créer des types qui se contiennent et y accéder par un niveau supplémentaire d'indirection, le sous-type étant simplement une transformation du type handle-to-the-complet en un handle-to-the-contient-type.
  • Si vous n'avez pas de délégués mais que vous avez des pointeurs de fonction, vous pouvez créer un type contenant l'objet référent et un pointeur de fonction.
  • Si vous n'avez pas de délégués mais que vous avez des interfaces, vous pouvez déclarer une interface contenant une seule méthode avec la signature souhaitée.
  • Si vous n'avez pas de types génériques, vous pouvez utiliser des types non génériques qui supposent uniquement les limites supérieure ou inférieure qui vous intéressent (et peut-être effectuer les conversions appropriées aux emplacements d'utilisation, pour que le compilateur reste heureux).
  • Si vous n'avez pas de système de type linéaire / affine, vous pouvez simplement éviter d'utiliser une variable plus d'une fois.
  • ...etc.

La conception linguistique standard se concentre sur des fonctionnalités qui facilitent et facilitent le calcul, l’identification précoce des erreurs, la programmation contre des composants inconnus, la sécurisation du parallélisme, etc.

Les éléments purement informatiques ont été cloués il y a longtemps.

Theodoros Chatzigiannakis
la source
4

Les réponses existantes indiquent à juste titre que l’exhaustivité de Turing n’est pas un bon moyen de comparer des langues. En effet, presque toutes les langues sont complètes. ("Si tout le monde est spécial, personne n'est spécial", disait The Incredibles.)

Cependant, il est possible de comparer l'expressivité des langues avec la précision mathématique. Jetez un coup d'œil sur le pouvoir expressif des langages de programmation de Felleisen . En gros, l’idée est de poser la question suivante: Puis-je convertir n’importe quel programme de la langue A en un programme de la langue B en n’effectuant que des modifications locales ? En d'autres termes, Felleisen donne une forme mathématiquement précise à votre intuition.

grog
la source
2

En plus des réponses de tous les autres, voici une autre analogie.

Pour laver les vêtements, vous avez besoin de trois choses: un réservoir contenant de l’eau, un détergent quelconque et un mécanisme d’agitation. Cela pourrait être réalisé à bien des égards. Le réservoir d'eau est tout ce qui contient suffisamment d'eau (par exemple une baignoire, un lac, une rivière). Le mécanisme d'agitation pourrait être un dispositif mécanique, une planche à laver ou même un rocher contre lequel les vêtements sont frappés. Et les détergents se présentent également sous différentes formes.

Alors, quelle est la différence entre une machine à laver moderne informatisée et un rocher au bord d'une rivière?

Cela se résume à trois choses: efficacité, sécurité et commodité. Certaines méthodes de lavage consomment moins d'énergie, polluent moins l'environnement, consomment moins d'eau, etc. Certaines méthodes de lavage nécessitent des activités manuelles moins répétitives (qui entraînent des blessures) ou d'être à l'extérieur par mauvais temps. Et certaines méthodes de lavage n'exigent pas qu'un humain surveille le processus.

Les langages de programmation Turing-complete ont une utilité générale et sont donc soumis à plusieurs tâches. Néanmoins, pour une tâche donnée, certains langages de programmation sont plus efficaces, plus pratiques et plus sûrs (en ce sens que moins de problèmes peuvent survenir lorsque le programme est réellement utilisé) que d’autres.

Pseudonyme
la source
2

D'autres ont fourni beaucoup de bonnes réponses, mais ils ne mentionnent pas explicitement une mise en garde qui m'avait beaucoup déroutée une fois: le fait d'être complet ne signifie pas qu'un langage peut exprimer des fonctions calculables arbitraires à partir de ses entrées vers ses sorties. Il est plus faible: il doit exister un moyen de représenter le domaine et la plage de l’ensemble des fonctions calculables en tant qu’entrées et sorties de sorte que chacune de ces fonctions mappe à un programme qui prend une représentation de ses entrées en sorties correspondantes.

Prenons, par exemple, un langage qui exprime les machines de Turing. Chaque programme dans la langue est une machine de Turing.

Maintenant, considérons la sous-langue de toutes les machines Turing qui lisent et écrivent uniquement les caractères a, b et les blancs. Il est complet, mais il ne peut exprimer aucun programme produisant, par exemple, c sur toutes les entrées, car il ne peut écrire aucun cs. Il ne peut exprimer que toutes les fonctions calculables sur les entrées et les sorties codées sous forme de chaînes de caractères as et bs.

Il n'est donc pas vrai que tous les langages complets de Turing peuvent calculer les mêmes choses, pas même lorsque nous limitons ces choses aux fonctions calculables de leurs entrées potentielles à leurs sorties potentielles. Le langage peut nécessiter que les entrées et les sorties soient codées de certaines manières.

Reinierpost
la source