Langage de programmation où chaque expression a du sens

Par recommandation, je republie cela à partir de Stack Overflow .

Récemment, j'ai réfléchi au problème suivant.

Considérez le code pour un standard "Bonjour tout le monde!" programme:

main()
{
    printf("Hello World");

}

Maintenant, presque tout changement dans ce code le rendra complètement inutile, en fait presque chaque changement empêchera la compilation du code. Par exemple:

main(5
{
    printf("Hello World");

}

Passons maintenant à la vraie question. Existe-t-il un langage de programmation où chaque combinaison possible de symboles - c'est-à-dire chaque expression - a un sens? J'ai essayé de penser à une sorte de solution et j'en ai trouvé deux:

1. Postfixe avec un nombre limité de variables. Essentiellement, toutes les variables sont déjà définies avant d'écrire un code et vous devez travailler uniquement avec elles. Théoriquement, vous pouvez effectuer un nombre arbitraire d'opérations en formant une chaîne de nombreux programmes simples, chacun d'eux fournissant des résultats aux autres. Le code pourrait être écrit comme une série de caractères en notation postfixée;

2. "Postfix" avec une pile de variables. Les variables sont stockées sur une pile; chaque opération prend deux variables d'en haut et met le résultat à leur place. Le programme se termine lorsqu'il atteint la dernière opération ou variable.

Personnellement, je déteste les deux. Non seulement ils sont limités, ils sont inélégants. Ce ne sont même pas de vraies solutions, plutôt des solutions de contournement, qui «délocalisent» essentiellement du travail vers un processus externe.

Quelqu'un at-il une autre idée de la façon de résoudre ce problème?

Redcode, le langage d'assemblage derrière les guerres de code, a été explicitement écrit pour avoir très peu d'instructions d'arrêt, parce que le code est souvent altéré avant de finalement céder, et plus il a de possibilités d'interrompre, moins le jeu est intéressant.

Vous voyez très peu de ces langages dans la pratique parce que nous ne voulons pas seulement qu'un programme s'exécute, nous voulons qu'il s'exécute de la manière que nous attendons. Si vous pouvez faire une faute de frappe et changer la façon dont le programme a fonctionné, il doit être suffisamment proche du comportement attendu d'origine, ou les programmeurs se sentent frustrés.

Il y a une certaine priorité pour de telles choses en utilisant des langues naturelles plutôt que des langues formelles, mais ce n'est pas ce que j'appellerais un grand champ lorsque vous le comparez à l'utilisation de langues formelles. Si vous êtes intéressé par de tels langages de programmation, la communauté de traitement du langage naturel est l'endroit où je chercherais.

Un autre domaine que vous pourriez examiner est la génétique. Il existe remarquablement peu de séquences génétiques qui sont tout simplement invalides. Beaucoup d'entre eux qui ne sont pas très efficaces pour les reproductions, mais très peu de reproductions invalides.

L'idée d'une machine de Turing universelle utilise exactement un tel "langage de programmation": un codage des machines de Turing en nombres naturels, représentés par exemple en binaire, de sorte que chaque nombre naturel désigne une machine de Turing, c'est-à-dire un programme. Dans cette langue, chaque chaîne de zéros et de uns est un programme.

$n$$n$

Je suis sûr qu'il existe également des langages de programmation ésotériques où chaque chaîne est un programme; cependant, si vous demandez simplement une liste de ceux-ci, je pense que votre question est hors sujet ici.

Étendre un langage de programmation pour que chaque expression ait du sens est toujours possible, mais pas intéressant. Par exemple, vous pouvez simplement attribuer la signification «ne rien faire» à toute expression que la langue d'origine rejette.

Il n'est pas particulièrement utile de concevoir un langage de programmation où chaque expression a un sens «vous pouvez l'exécuter». Un bon langage de programmation n'est pas seulement celui où un singe peut taper sur un clavier et écrire un programme valide, mais celui où un programmeur peut facilement écrire le programme qu'il avait l'intention d'écrire. Écrire des programmes valides n'est pas la partie difficile de la programmation: la partie difficile est d'écrire un programme qui exécute ce que l'on attendait de lui. Le rejet de programmes manifestement incorrects est très utile à cet égard.

Une autre façon de résoudre ce problème consiste à définir complètement la sémantique de toutes les entrées possibles, y compris en spécifiant les erreurs de compilation, de chargement ou d'exécution qui doivent être générées pour chaque entrée, le cas échéant. Autrement dit, «abandonner le programme après l'impression Syntax error at line 42sur le flux d'erreurs standard» fait partie de la sémantique définie du langage. Chaque expression «a du sens» en ce sens qu'elle a une signification définie. Est-ce une signification utile? Peut-être - après tout, si le programme est manifestement faux, le rejeter est utile.

Découvrez Jot , un langage complet de Turing basé sur la logique combinatoire, où chaque séquence de 0 et de 1 (y compris une séquence vide) est un programme valide.

Un bel exemple est l' espace blanc . Dans la langue proprement dite, toute combinaison d'opérateurs est valide. Les opérateurs sont l'espace, la tabulation et la nouvelle ligne (spécifiquement "\ n"). Tous les autres personnages sont considérés comme des commentaires .

Cette réponse, et en effet votre question (ainsi que l'ensemble de cette page Web) sont des exemples de programmes d'espaces valides (bien qu'ils ne puissent rien faire de particulièrement intéressant).

Je voudrais aborder l'idée que de nombreuses affiches ont donnée, qu'une telle langue serait "inutile". Il serait peut-être inutile pour les humains d'écrire, manuellement, dans le but de résoudre une tâche particulière. Cependant, bien qu'il s'agisse d'un cas d'utilisation majoritaire pour les langages de programmation, ce n'est certainement pas le seul cas d'utilisation. Plusieurs cas d'utilisation viennent à l'esprit lorsqu'une telle langue est utile, et nous pouvons consulter ces champs pour des exemples de ces langues.

Tout d'abord, l'allusion de Cort Ammon à la génétique est parfaite: la transformation du programme dans la question (se substituant )à 5) peut être vue comme une mutation . Ce type de manipulation est courant dans le domaine du calcul évolutif ; en particulier, les algorithmes génétiques effectuent de telles transformations sur les chaînes , tandis que la programmation génétique transforme les programmes . Dans les deux cas, nous voulons généralement attribuer un sens à chaque possibilité, car cela produira l'espace de recherche le plus compact.

Les algorithmes génétiques s'appuient sur une sorte de fonction d'évaluation pour les chaînes; si nous utilisons un interpréteur de langage de programmation comme fonction d'évaluation, nous avons alors un scénario où un langage de programmation qui attribue un sens à toutes les chaînes possibles est utile. En programmation génétique, on suppose que notre fonction d'évaluation est un interpréteur de langage de programmation, mais nous pouvons choisir différentes représentations pour nos programmes; par exemple, de nombreux systèmes fonctionnent sur des arbres de syntaxe abstraite. Si nous choisissons des chaînes comme représentation, nous récupérons le même scénario qu'avec les algorithmes génétiques.

Une autre situation où nous pouvons souhaiter que chaque chaîne soit un programme valide est lors de l' énumération des programmes. Ceci est lié à la bijection mentionnée par CodesInChaos, mais nous pouvons préférer opérer sur des chaînes plutôt que sur des nombres naturels pour plusieurs raisons:

• S'il y a une certaine structure dans la langue, par exemple. nous pouvons attribuer un sens aux sous-chaînes, cela peut être perdu lors de la traduction en nombres naturels. Dans ce cas, nous pouvons préférer utiliser des chaînes, afin de raisonner et de transformer les sous-chaînes localement, plutôt que de représenter l'ensemble du programme sous forme de nombre. Ceci est analogue à la façon dont nous pourrions préférer utiliser des opérations au niveau du bit sur un int plutôt que des expressions arithmétiques, lorsque chaque bit a une signification individuelle. Il s'agit essentiellement d'une généralisation du scénario évolutif.
• Nous pouvons vouloir générer les programmes sur demande; par exemple, nous pourrions commencer à exécuter un programme qui est complètement indéterminé, et générer uniquement (par exemple de manière aléatoire) les instructions individuelles (par exemple, des caractères) lorsque / si le pointeur d'instruction les atteint. Ceci est courant dans la théorie algorithmique de l'information, où le programme est une bande de machine de Turing, et le but est de caractériser le comportement des programmes générés aléatoirement. Par exemple, nous pouvons formuler le Solomonoff prior sur des chaînes arbitraires comme la probabilité qu'une machine de Turing universelle avec une bande aléatoire produise cette chaîne.

En termes d'exemples de langages, de nombreux systèmes de calcul évolutifs sont basés sur des langages de pile comme la famille Push . Ceux-ci ont tendance à autoriser des flux de jetons arbitraires (que nous pourrions représenter comme des caractères individuels). Parfois (comme avec l'exemple Brainfuck de BrainSlugs83) il y a des restrictions sur l'équilibrage des parenthèses; cependant, nous pouvons relier ce à des programmes d'auto-délimitant , en ce qu'une chaîne comme [peut ne pas être valide programme , mais il est valide préfixe de programme . Si nous imaginons un compilateur / interprète lisant le code source de stdin, alors il ne rejettera pas une chaîne comme [, il attendra simplement plus d'entrée avant de continuer.

Des langages comme la logique combinatoire binaire et le calcul lambda binaire sont nés directement du travail sur la théorie algorithmique de l'information, par exemple. depuis http://tromp.github.io/cl/cl.html

Cette conception d'un ordinateur universel minimaliste a été motivée par mon désir de proposer une définition concrète de la complexité de Kolmogorov, qui étudie le caractère aléatoire d'objets individuels.

Les vrais langages de programmation doivent transmettre du sens aux gens , pas aux ordinateurs. Comme beaucoup de textes amusants avec des lettres presque aléatoires flottant autour du spectacle 'ńet, les gens peuvent lire du charabia et donner un sens à cela, même sans remarquer ouvertement les mutilations. Il suffit de penser à quel point il est difficile de trouver des fautes de frappe et d'autres erreurs de ce type dans les textes.

Un langage de programmation comme ce que vous demandez ferait comprendre aux gens ce qu'ils veulent lire, pas ce qui est écrit. Le débogage dans les langues où il y a un ensemble limité de déclarations juridiques, où il n'y a pas beaucoup d'ambiguïté possible, est déjà assez difficile. De bonnes langues réduisent les interprétations possibles dues par exemple aux symboles transposés ou aux fautes de frappe. Les langues naturelles sont également connues pour leur redondance, pour le même genre de raison.

Dans le langage de programmation Brainfuck , presque toutes les expressions binaires possibles peuvent être interprétées comme un programme. - C'est-à-dire que vous pourriez prendre un programme complètement bon, taper un tas de déchets, et il serait toujours compilable / interprétable sans aucun problème.

( Modifier: Il s'avère que vous devez faire correspondre les crochets d'ouverture et de fermeture, mais sinon, ce qui précède est vrai.)

Il y parvient via ces deux méthodes simples:

1. Toutes les commandes qu'il comprend sont un seul octet (en BF, ce sont tous des caractères ASCII uniques par exemple *).

2. Tous les personnages qu'il ne comprend pas, il les rejette comme commentaires.

Le langage de programmation est Turing complet (ce qui signifie qu'il peut faire tout ce que n'importe quel autre langage peut faire).

*: Il s'avère que toutes les commandes BF ne sont pas un seul octet ASCII - c'est-à-dire que les crochets DOIVENT être mis en correspondance - de la sorte, ce langage ne répond pas aux premiers critères. - Mais toute langue qui répond aux deux critères répondrait à ce que le PO demande.