Est-il réellement possible d'avoir un langage de programmation «utile» qui ne soit pas complet?

37

Là où il est accepté qu'un langage doit être complet pour être réussi, est-il réellement possible d'avoir un langage de programmation «utile» qui n'est pas complet?

Je devrais préciser qu'il s'agit tout particulièrement de la "programmation" des langages au sens traditionnel, et non des langages de balisage ou de requête.

PhonicUK
la source
3
@PhonicUK Au début, SQL n'était pas complet
Ryathal
4
@Ryathal SQL n'est pas un langage de programmation, c'est un langage de requête.
Yannis
2
@PhonicUK votre question dans le commentaire en vaut vraiment la peine, changez la question affichée pour qu'elle soit ou elle va se fermer car elle n'est pas constructive. Il existe en fait des langages complets utiles et non parlants, et je serais intéressé d’en connaître les détails.
Jimmy Hoffa
5
regex n'est pas complet mais il est largement utilisé
Ratchet Freak
3
@DavidHammen Les implémentations réelles sont limitées, oui, à cause des limites de notre univers physique (ne peut construire que de la mémoire finie, ne peut faire fonctionner la machine que pendant un temps limité avant qu'elle ne fonctionne mal). Mais cela ne signifie pas que les langues sont limitées. Les spécifications d' un langage complet IOW ne nécessitent pas d' implémentation pour imposer de telles limites à un programme, alors qu'un langage non-TC requiert, par exemple, une preuve de terminaison.

Réponses:

48

Coq , Agda , HOL et ACL2 sont des langages très utiles et extrêmement puissants, bien qu'ils ne soient pas complets.

Une caractéristique commune qui les rend non-Turing-complete est le fait qu'il est toujours possible de prouver la résiliation. Une limitation très simple suffit: les appels récursifs ne sont autorisés que selon des conditions plus simples et plus structurelles. Par conséquent, bien qu’il ne soit pas possible de mettre en œuvre un interprète pour un langage complet de Turing ou même pour le langage lui-même, de nombreuses autres choses utiles sont toujours possibles, comme un compilateur C certifié .

SK-logic
la source
2
Pour ceux qui ne connaissent pas ces langages, pourriez-vous donner plus de détails sur ce qui leur manque, ce qui les rend incomplets, et quelques exemples d'éléments construits avec ces langages?
PhonicUK
8
@PhonicUK: un compilateur C est pas une implémentation en C . C'est un outil qui transforme le code d'une langue (C) en une autre (généralement du code machine). Cela ne signifie pas que le compilateur C est équivalent à un programme C aléatoire.
Joachim Sauer
9
@PhonicUK, vous ne pouvez pas implémenter d'interprète pour un langage complet de Turing dans un langage non complet de Turing. Mais vous pouvez bien sûr implémenter un compilateur (puisqu'un processeur complet de Turing fera une évaluation réelle).
SK-logic
11
@ SK-logic: "Bien sûr?" Ce n'est possible que pour C parce que c'est un langage assez simple. Ce n'est pas possible pour C ++ car un compilateur doit interpréter le code du template (qui est Turing-complete au moment de la compilation).
MSalters
11
@MSalters Oui, si la compilation du langage est complète, son compilateur doit être écrit dans un langage complet. Ce qui est aussi un peu évident (pour ne pas dire tautologique). Toutefois, notez que la norme C ++ autorise des limites sur les programmes d'entrée, telles qu'une profondeur d'évaluation maximale pour les instanciations de modèles (et les implémentations existantes prennent cette liberté). Si je ne me trompe pas, cela signifie qu'un compilateur C ++ complet non permanent sera peut-être possible (à moins de problèmes non liés, bien sûr).
12

Je pense que le terme "mini-langage" de Yegge fait référence au fait qu'il est souvent utile d'utiliser un langage pour des problèmes spécifiques où le langage n'exige pas une complétude pour accomplir la tâche, ce qui va au coeur de la non-complétude. -turing langues complètes peuvent être utiles. https://sites.google.com/site/steveyegge2/language-grubbing

Wikipedia y répond très bien, en ligne avec ce que mon instinct a dit. Je pensais d’abord aux mathématiques pures, puis je me suis souvenu de l’expression rationnelle, et Wikipedia répertorie Epigram qui, je pense, serait dans la veine des «mathématiques pures».

http://en.wikipedia.org/wiki/Turing_completeness#Non-Turing-complete_languages

Langues complètes non-Turing

Il existe de nombreux langages informatiques qui ne sont pas complets. Un tel exemple est l'ensemble des langages réguliers, le plus souvent des expressions régulières, générés par des automates finis. Une extension plus puissante mais toujours pas complète de Turing des automates finis est la catégorie des automates à pile et des grammaires sans contexte, qui sont couramment utilisées pour générer des arbres d'analyse dans une phase initiale de compilation du programme. D'autres exemples incluent certaines des premières versions des langages de pixel shader incorporés dans les extensions Direct3D et OpenGL, ou une série de formules mathématiques dans un tableur sans cycles. [Citation requise] Dans tous les langages de programmation fonctionnels, toutes les fonctions sont totales et doivent se terminer, tels que Charity et Epigram. La charité utilise un système de types et des constructions de contrôle basés sur la théorie des catégories,

Langages de données

La notion de complétude de Turing ne s'applique pas aux langages tels que XML, JSON, YAML et S-expressions, car ils sont généralement utilisés pour représenter des données structurées, et non pour décrire des calculs. Ceux-ci sont parfois appelés langages de balisage, ou plus exactement "langages de description de données".

Il mentionne également que les représentations de structure de données ne sont pas des langages, mais je pense que XSLT devrait être considéré comme une représentation du calcul, XPath n'étant peut-être pas basé sur ce que Yannis a dit plus haut, SQL est un langage de requête et non un langage de calcul. Peut-être que T-SQL ou PL / SQL sont considérés comme des langages de calcul, car vous pouvez effectuer beaucoup de calculs en utilisant leurs agrégats, où la forme généralisée de SQL ne spécifie peut-être pas d'agrégats.

Jimmy Hoffa
la source
8

Je comprends que le langage SQL est très populaire parmi les entreprises

Martin Beckett
la source
3
SQL est un langage de requête, pas un langage de programmation.
PhonicUK
4
@PhonicUK: et quelle est exactement la différence entre un langage de requête et un langage de programmation?
Joachim Sauer
8
@PhonicUK - Tex est un langage de balisage de texte complet, écrit par Turing
Martin Beckett
3
les implémentations modernes de sql, pour autant que je sache, sont complètes.
shabunc
6
@shabunc IIRC uniquement avec des procédures stockées. L'argument devient un peu circulaire, si ce n'est pas complet, alors ce n'est pas un langage de programmation - donc tous les langages de "programmation" sont TC
Martin Beckett
5

La complétude est essentielle pour qu’une langue soit apte à être utilisée comme langage à usage général. Mais cela ne suffit pas , c’est-à-dire que Turing est complet, il ne convient pas à tous les problèmes:

  • Il est prouvé que l’espace blanc est complet, mais il est évidemment inadapté à tout problème en dehors du divertissement programmé.
  • Les modèles C ++ ont été prouvés complets, mais vous n’écririez jamais de programmes complets avec eux.

Inversement, un DSL est adapté au domaine de problèmes pour lequel il a été conçu (à supposer qu'il ait été conçu de manière décente), même sans la complétude de Turing:

  • HTML * fournit un moyen concis de décrire une arborescence DOM. Bien que JavaScript soit complet et puisse être utilisé de la même manière, il est beaucoup plus bruyant et moins clair.
  • XPath et d’autres langages de requête, PCRE sans code incorporé et autres sont tous des outils puissants pour le seul travail pour lequel ils ont été conçus

* IIRC a prouvé que HTML avec les animations CSS était complet en utilisant celles-ci pour implémenter Game of Life de Conway sur un éventail de cases à cocher. Mais l'utilité du HTML est valable même dans les navigateurs qui ne supportent pas les animations CSS.

back2dos
la source
2
Avez-vous un lien vers Conway's Life implémenté dans CSS?
RBerteig
Je ne connais pas d'implémentation CGOL dans CSS, mais je sais que la règle 110 a été implémentée. Je n'arrive pas à le trouver, il semble avoir été déplacé.
Christian Mann
2
@ ChristianMann, celui-ci? raw.github.com/elitheeli/stupid-machines/master/rule110/…
SK-logic
-1 Très intéressant mais ne répond pas à la question posée
mattnz
2
@mattnz: Faux. Je donne des exemples concrets de langages complets non-Turing qui sont utiles, que je pense est une réponse appropriée à « Est - il réellement possible d'avoir un langage de programmation « utile » qui ne sont pas Turing complet? », Un peu comme une autre réponse ici
back2dos
3

Il existe en réalité des langages de programmation, où vous ne pouvez écrire que des programmes "efficaces". Efficace dans ce sens signifie que chaque programme écrit dans une telle langue représente une langue en P. Bellantoni, Niggl et Schwichtenberg décrivent un tel langage ici .

SpaceTrucker
la source
1

Le préprocesseur C est pas Turing-complet (par la conception), mais il peut encore mettre en œuvre un interprète pour une langue qui est Turing complet (commande de la langue, comme décrit dans la documentation, est fondamentalement juste une course-of-the moulin purement fonctionnel type ML / Scheme chose, et serait relativement banal - probablement assez agréable à utiliser - si ce n'était pour la mise en œuvre inhabituelle).

L'astuce qui se cache derrière est similaire aux arguments ci-dessus concernant la mise en œuvre d'une machine Turing dans un univers physique fini: le préprocesseur C ne peut pas fournir un nombre infini d'étapes ou de cellules de données au langage, mais il peut:

  1. fournir un déraisonnablement grand nombre de dynamiques (2 ^ 64 ou si par défaut), assez grand pour résoudre la plupart des problèmes réalistes à l' aide d' un processus d'expansion exponentielle ( mumble mumble à vie de l'univers Mumble ).

  2. utilisez une limite statique arbitraire pour le nombre ci-dessus, c'est-à-dire que, si le nombre d'étapes doit être un nombre fini, vous pouvez modifier la limite spécifique à la "compilation" en modifiant les paramètres statiques du moteur d'interprétation. Puisqu'il n'y a pas de limite (théorique) à la valeur réelle de ce plafond, il peut (théoriquement) être étendu pour s'adapter à l'espace requis pour tout programme de terminaison.

Sans vouloir prétendre que Order est nécessairement "utile" en soi, ou qu'un moteur implémenté par le RPC le serait, mais c'est une preuve de concept intéressante. Il est également censé être dynamiquement typé , ce qui est inhabituel pour cette région.

Leushenko
la source
Upvote pour marmonner au milieu de la conférence.
Jpaugh
-1

Oui, en effet, il est possible d’avoir un langage utile qui n’est pas complet. Voir ici: http://tkatchev.bitbucket.org/tab/examples.html

SQL est un autre exemple de langage incomplet utile à Turing. (Et un autre exemple est celui des feuilles de calcul comme Gnumeric ou Excel, bien qu'elles ne soient pas vraiment des langages de programmation.)

Pour ce qui est de la raison pour laquelle vous voudriez un langage qui ne soit pas complet à Turing: parce que cela vous permet de donner de fortes garanties quant au comportement à l'exécution.

Bien entendu, être complet signifie avoir une capacité de récursion. Avoir une récursion signifie avoir des structures potentiellement illimitées en mémoire. Étant donné que dans le monde réel, la mémoire n’est pas infinie, la complétude de Turing nécessite une gestion de la mémoire et / ou un garbage collection.

Interdire la récursion est un excellent moyen d’éviter le problème très complexe de la gestion des ressources.

Nota bene! Être incomplet ne signifie pas nécessairement que tout programme se terminera nécessairement. Un langage incomplet de Turing pourrait permettre d’évaluer une liste infinie de paresseux.

tkatchev
la source
-1

Un "langage de programmation sous-Turing" intéressant n'a pas été mentionné jusqu'à présent, je vais donc l'ajouter.

Ça s'appelle "Crema" . Il se décrit comme:

Crema est un front-end de LLVM qui vise à exécuter spécifiquement dans un espace complet sub-Turing. Conçu pour être simple à apprendre et pratique pour la majorité des tâches de programmation requises, Crema peut limiter au maximum la complexité de calcul du programme afin d’améliorer la sécurité.

C'est assez minimaliste et plutôt bas.

Cela devrait sembler familier aux développeurs C.

Il a été initialement financé par la DARPA (Defense Advanced Research Projects Agency), mais il semble ne pas être maintenu au moment d'écrire ces lignes. Mais peut-être que quelqu'un est intéressé quand même.

Mateusz Kowalewski
la source