Langage de programmation où chaque expression a du sens

23

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?

user1561358
la source
48
Étant donné un compilateur , créez un nouveau compilateur qui fonctionne comme suit: source donnée , passer à . Si est satisfait et produit un exécutable, alors c'est ça, mais si plaint, alors sortez un exécutable qui affiche Le compilateur accepte chaque chaîne comme un programme valide. C s C C C C 'CsCCCYou are a bimbo.C
Andrej Bauer
1
BF a besoin d'une [ ]commande correspondante (selon la page Wiki). Ma pensée était de regarder les opcodes CPU. Mais même dans ce cas, certains modèles peuvent générer un problème (par exemple, si un opcode est de 3 bits, mais que votre programme n'est que de 2 bits.) À l'exception de ce problème de remplissage éventuel avec des bits de 0 supplémentaires, on peut penser à n'importe quel processeur avec un ensemble complet d'opcode qui satisfera la revendication "chaque chaîne est un programme valide". Peut-être vide de sens, mais toujours valable.
Ran G.
1
Laissez votre matériel être un processeur Z-80 avec 64 Ko de RAM. Écrivez un compilateur qui copie simplement le code source codé ASCII dans la mémoire 64k (tronquant ou complétant zéro si nécessaire). Ce compilateur ne donne jamais d'erreur de syntaxe.
Ben Crowell
1
@A sonné. Un «compilateur» qui traite n'importe quel train de bits et le corrige pour être un bit de code objet valide pour le processeur donné, je pense, répondrait aux exigences des OP. Ce ne serait probablement pas terriblement difficile, même pour les systèmes avec des jeux d'instructions complexes comme x86. Il y a des années, j'ai lu un article sur la validité des octets aléatoires en tant que programmes x86 et il a constaté que x86 était en réalité beaucoup plus robuste que ce que les auteurs attendaient à l'origine.
otakucode
2
Sans autres conditions, cette question est ennuyeuse: le commentaire d'Andrej et la réponse de David donnent des réponses "triviales". Vous devez définir plus précisément ce que vous voulez.
Raphael

Réponses:

31

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.

Cort Ammon - Rétablir Monica
la source
1
La génétique ne semble pas être un bon exemple. En termes de validité ou d'invalidité, parlez-vous simplement de réplication? Parce que bien sûr, chaque chaîne sera un programme valide pour une langue dans laquelle la seule instruction possible est replicate this string. Ce n'est pas vraiment un langage de programmation significatif, car il est loin de Turing Complete.
tel
2
@tel: Cort parle probablement de synthèse de protéines via l'ARNm, plutôt que de réplication. À peu près n'importe quelle séquence génétique peut être transcrite et ensuite mise dans le mécanisme de synthèse des protéines: si la protéine qui en sort est suffisamment stable pour ne pas avoir déjà été dégradée au moment de sa construction, et si oui, si elle fait quelque chose d'utile pour l'organisme, c'est une autre affaire ...
Steve Jessop
3
Le code génétique n'est pas un code pour se reproduire. C'est (généralement) un code pour une protéine. L'utilité de la protéine est souvent une question différente. Bien sûr, cela devient plus intéressant. Certains morceaux de «code» dans une séquence génétique finissent par ressembler davantage à une instruction du type «qui codent quelques lignes plus loin - vous devez parfois simplement l'ignorer». Il y a toutes sortes de "programmes" sympas que les cellules et les virus ont écrit en se combattant.
Joel
TECO est un autre exemple concret.
cjm
1
@cjm wow. "Une API n'est pas terminée lorsque vous avez fini de tout ajouter, mais lorsque vous avez fini de tout retirer." À moins que vous ne soyez TECO, vous avez terminé lorsque vous manquez de caractères pour attribuer un sens à.
Cort Ammon - Rétablir Monica
16

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.

nn

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.

David Richerby
la source
13

É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.

Gilles 'SO- arrête d'être méchant'
la source
12

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.

Petr Pudlák
la source
2
Ce n'est pas un ordinateur la science réponse.
Raphael
2
@Abdulrhman Il est simple de définir une bijection entre les chaînes binaires et les nombres naturels. Vous pouvez donc encoder n'importe quel programme en nombre naturel si vous le souhaitez.
CodesInChaos
7
@Raphael Veuillez développer ou suggérer une amélioration de la réponse, je serai heureux de l'améliorer si vous fournissez des motifs pour votre critique.
Petr Pudlák
+1, j'étais sur le point de donner une réponse similaire pour un langage de programmation fictif basé sur des nombres naturels, mais c'est similaire. AFAIK il n'y a pas de programmation (en utilisation pratique) qui a cette fonctionnalité, mais on peut en construire une en utilisant seulement des nombres, disons, où chaque combinaison a un sens (agir comme des opérateurs ainsi que des opérandes) C'est la clé
Nikos M.
8

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).

Slebetman
la source
J'y pensais juste après avoir posté ma réponse de brainfuck (la vôtre est meilleure car elle est correcte), mais je me demande - un programme vide est-il toujours un programme? (c'est-à-dire si ces trois caractères manquent dans le flux de fichiers entier). - Comme si ma voiture manquait de tout ce qui en faisait une voiture, serait-ce toujours une voiture?
BrainSlugs83
Ce n'est pas un ordinateur la science réponse. (Aussi, "chaque chaîne d'espaces"! = "Chaque chaîne".)
Raphael
2
@Raphael: Mais toutes les chaînes possibles (y compris celles qui ne contiennent aucun espace) sont des programmes d'espaces valides - notez que tout caractère qui n'est pas un espace est simplement des commentaires dans le langage de programmation des espaces
slebetman
2
@slebetman Vous interprétiez trop littéralement le commentaire de mes crochets. Je parlais de jetons de boucle non appariés. Certains problèmes similaires dans les espaces blancs pourraient être: Est-ce que le retour sans appel précédent fonctionne? (codé comme [LF][Tab][LF]) Que se passe-t-il si vous éclatez une pile vide? Que se passe-t-il si vous passez à une étiquette non définie? Que se passe-t-il si vous définissez des étiquettes en double?
CodesInChaos
7

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.

Warbo
la source
2

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.

vonbrand
la source
0

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.

BrainSlugs83
la source
2
Non seulement cela répond pas à la question, il est pas un ordinateur la science réponse.
Raphael
1
Vous pouvez redéfinir le langage pour les gérer de manière sensée. par exemple en insérant suffisamment de parenthèses ouvrantes au début du programme et fermant les parenthèses à la fin du programme pour le rendre équilibré. Il est simple d'écrire un interpréteur qui gère les programmes comme si ces crochets existaient sans réellement réécrire le programme. Bien sûr, démarrer un programme brainfuck avec un support d'ouverture est plutôt inutile, car il ignorera tout jusqu'au support de fermeture correspondant.
CodesInChaos
1
@Raphael, la question de l'OP était "Existe-t-il un langage de programmation où chaque combinaison possible de symboles - c'est-à-dire chaque expression - a du sens?" - ma réponse est "oui, voici un exemple de celui qui se rapproche, et voici la théorie derrière." - à part établir des règles exactes pour une classe de langues qui répondraient aux exigences du PO, je ne sais pas combien de place pour la science il y a ici. Pouvez-vous donner un exemple ou un lien vers une ressource de ce que vous espérez voir exactement ici? -- Je vous remercie.
BrainSlugs83
2
David et Gilles donnent des réponses en informatique. Ils explorent les principes et ne se contentent pas de dire: "le langage X fait (presque) cela". Si vous lisez leurs réponses, vous apprendrez que les réponses de cette dernière forme sont également assez ennuyeuses. Ce n'est pas de votre faute, mais les PO - la question (en tant que question informatique) est ennuyeuse; il y a un faux sentiment de complexité.
Raphael
On pourrait facilement "corriger" BF pour que n'importe quelle chaîne soit acceptée: vous prétendez simplement qu'il y a suffisamment de ]caractères à la fin de la source pour correspondre à tous les [s sans correspondance , et suffisamment [au début pour correspondre à tous les sans correspondance ]. La sémantique de [et ]peut facilement être modifiée pour les rendre équivalentes à cela. (par exemple , s'il n'y a pas correspondance ]alors [arrête juste exécution si l'octet au niveau du pointeur de données est nul. ]juste saute au début du programme dans une situation similaire.) Le langage résultant serait complet et Turing accepterait toute chaîne.
Nathaniel