Motivation: J'aimerais pouvoir utiliser la programmation fonctionnelle de jouet dans des langues sans fonctions de première commande, en utilisant des numéros naturels au lieu de fonctions.
Une fonction universelle est une fonction F: N -> (N -> N), équivalent F: N * N -> N qui énumère toutes les fonctions calculables possibles. En d'autres termes, il y a un nombre k tel que f (k) est la fonction de quinquage, il y a un numéro J tel que f (j) est la nième fonction principale, etc.
Pour écrire une telle fonction, on peut prendre n'importe quelle langue Turing-Complete (Compilateur de langage de programmation, Calculus Lambda, Turing Machines ...) et énumérer tous les programmes. J'aimerais permettre non seulement une évaluation, mais également des opérations sur des fonctions telles que l'ajout, la composition, le currying. Par exemple, des indices de deux fonctions F, G Envie de savoir quel est l'indice de la fonction F + G, ou F composé avec g. Cela permettrait "programmation fonctionnelle de jouet".
Quel est un bon moyen d'écrire une telle bibliothèque de code? Je ne cherche pas un tarpit de Turing minimaliste qui luttera pour calculer la facture de 10, ni je ne veux pas écrire un compilateur avancé. Il devrait avoir des fonctions de base telles que l'ajout et la possibilité d'écrire une boucle, mais pas beaucoup plus.
Solutions dans toutes les langues de haut niveau sont les bienvenues. Pseudocode, Haskell et Python sont préférés. Vous pouvez assumer des arithmétiques de précision arbitraire. En utilisant Clarification: Les fonctions énumérées se composent de tout partiel récursif (calculable) - cela inclut des fonctions cela ne mettomte pas sur des intrants. La fonction universelle sera suspendue dans ce cas; Bien sûr que c'est inévitable. Voir aussi: Fonctions M-Rursive - http://fr.wikipedia.org/wiki/ Μ-récursive_function . eval ou similaire n'est pas autorisé.
7 Réponses :
Pas une question facile. Je suppose que vous devez commencer par un générateur de fonction qui peut générer toutes les fonctions une par une. Cela entraînera une énumération.
Depuis que vous devez traiter plusieurs dimensions sans fin ... pensons-y.
Réduisons le problème pour fonctionner avec n paramètres et les opérations de base +, -, *, /.
Construisons toutes les fonctions avec une seule opération:
a + a
A + B
a - un
A - B
A * un
A * B
A / A
A / B
Je suppose qu'il est facile de voir que certaines de ces fonctions ont plus de sens que d'autres et certaines d'entre elles pourraient être égales, mais au moins, c'est un mappage qui peut être généré à travers une boucle.
Maintenant, dans la prochaine itération, on pourrait facilement ajouter à chacune de ces fonctions
Ensuite, vous avez une énorme liste de fonctions pour lesquelles vous pouvez répéter l'étape deux.
Étant donné que la fonction est une fonction qui estime toutes les fonctions plus complexes telles que le péché et le journal (série Taylor), celles-ci doivent également être couvertes dans cet espace de fonctions.
Est-ce que cela aide? N'hésitez pas à éditer ce post!
Il suffit de relire votre message. Si vous souhaitez énumérer toutes les fonctions programmatiques et non seulement numériques une fois, je suppose que ce sera plus complexe. Je suppose que cela aurait alors un sens de travailler avec une cartographie "Fonction <-> Number" en zippant la source de votre fonction et en traçage du fichier zip comme un grand nombre. L'inverse, vous pouvez essayer de décompresser n'importe quel nombre et de voir si cela crée une fonction utile :-) Mais je suppose que vous aurez beaucoup de chiffres qui ne sont même pas des fichiers zip.
Mais il remplirait votre exigence que, pour chaque fonction, il y a un numéro qui le représente: -)
Ce que vous voulez s'appelle un interprète.
Premièrement, toute énumération avec les propriétés que vous souhaitez ne pas correspondre aux fonctions intéressantes que vous souhaitez manipuler dans les 2 premiers 22, voire les 2 premiers 2 ^ 64, entiers. Vous aurez donc besoin de plus gros entiers, alloués quelque part en mémoire et référencés à travers un pointeur.
Pourquoi ne pas utiliser de tableaux de caractères (chaînes) représentant un programme dans une syntaxe existante alors?
Considérez une telle chaîne comme un entier si cela vous rend heureux. Le numéro de la fonction pour calculer Qu'est-ce que cette approche n'a pas d'unicité de la représentation d'une fonction, c'était peut-être impliqué dans votre question (je ne suis pas sûr). Ce que je suis sûr, c'est que l'unicité de la représentation est incompatible avec des opérations de composition simples, voire calculables, sur les représentations de la fonction - par exemple, il y aurait une solution facile au problème d'arrêt si ce n'était pas le cas. F1 () + F2 () est la chaîne faite de (représentation de F1), "+" et (représentation de F2). Vous obtenez l'idée ...
Convenu - Unicity of Représentation est impossible. Au lieu d'utiliser des cordes, des arbres peuvent être utilisés pour représenter des cordes analysées; Le stockage interne n'est pas si important. La question est de savoir quel ensemble de fonctions dois-je permettre à l'interprète d'avoir?
Droit sur. Il y a plus de 2 ^ 64 fonctions de la forme (x -> 1501 * x + 67) seul, et vous ne savez jamais lequel se passera pour être utile.
SDCVVC, maintenant, vous semblez poser une question de conception de langues de programmation sans fournir d'exigences.
Non seulement y a-t-il plus de 2 ^ 64 fonctions du formulaire (x -> 1501 * x +67), mais il existe des fonctions de manière importable de la forme (x-> n). Vous devez vraiment passer des limitations sur les fonctions que vous souhaitez décrire.
@Jason Orendorff: Les seules exigences que j'aiées sont les suivantes: (1) étant Turing-complète (2) aussi facile que possible possible, en utilisant des nombres naturels; Il suffira que le niveau d'expressivité soit comparable à la base ou floue (en.wikipedia.org/wiki/bloop_and_floop). N'importe quel design fera. @Liberalkid: tous les ordinables; Jusqu'à l'isomorphisme récursif, il n'y a qu'une solution possible, par le théorème de Myhill Isomorphism.
Vous pouvez prendre tout langage de programmation tel que vous pouvez déterminer si quelque chose est un programme ou non, et répertoriez tous les programmes de l'ordre lexicographique. Pour éviter au moins un peu l'explosion combinatoire, vous pouvez attribuer des noms définis par l'utilisateur (variables, fonctions, etc.) sur une forme normalisée. De toute évidence, cela entraînera un nombre immense de fonctions, et il ne sera pas facile de choisir lesquels sont faciles à choisir. Toute méthode automatique de coupe exclura certaines fonctions que vous allez réellement vouloir ou ne parviennent pas à couper l'explosion combinatoire suffisamment utile, ou les deux.
L'autre inconvénient de cela est qu'il sera très difficile de passer du nombre à la fonction: il est difficile de trouver un meilleur moyen de trouver la fonction 433 457 175.432 187.463 que d'énumérer environ quatre cents fonctions quadrillions.
L'autre sens consiste à coder une fonction dans un numéro en mappant les symboles aux nombres et en les concaténant efficacement.
suppose que les symboles sont +, -,: =, ==, <, si, puis, endif, do, fin_do_condition, enddo et un délimiteur d'instruction. C'est 11 symboles là-bas, sans variables, pour un ensemble assez minimal qui n'inclut rien comme un appel de fonction et nécessite que vous vous multipliez et divisez-vous. (Je ne suis pas vraiment sûr que cela fonctionnerait sans opérateur logique ou deux.) Ajoutez cinq noms de variables et vous avez un langage de programmation avec des caractères 4 bits. Cela signifie qu'un maximum de seize caractères s'intègrent dans un entier non signé de 64 bits.
Une fois que vous avez ceci, toutes les relations possibles entre les fonctions vont être représentées comme une relation arithmétique, mais une relation immensément compliquée qui sera loin d'être complexe pour se mettre en pratique.
En bref, alors que cela est théoriquement possible, il va être beaucoup trop maladroit dans la pratique. Il serait probablement plus facile d'écrire un interprète pour une langue fonctionnelle dans votre langue non fonctionnelle de choix.
Votre définition n'est-elle pas une "langue de programmation avec des caractères de 4 bits".
écrire une telle fonction, on peut prendre Toute langue complète (Compilateur de langue de programmation, Lambda calcul, machines de Turing ...) et énumérer tous les programmes
Je ne suis pas très sûr que cela puisse être fait du tout ... Ça ressemble à la thèse de Turing-Church. Afin d'énumérer tous les programmes, vous avez d'abord besoin d'un algorithme qui détermine quels programmes sont valides et que ceux-ci ne sont pas, et c'est impossible ... à moins que vous ne vous en souciez pas de cela et que vous n'en tenez pas de programmes incorrects dans votre langue.
Mais peut-être le Goodélisation d'un système formel pourrait vous aider ... j'essayerais avec LISP, avoir le code comme données pourrait aider beaucoup.
Oui, c'est impossible, mais toutes les langues de programmation gérent de la même manière (droite?) En permettant des programmes «invalides» (par exemple, des programmes qui ne se terminent pas) tout en rejetant ceux avec des erreurs évidentes. L'ensemble de programmes qui conviennent à une grammaire donnée est toujours dénombrable ... non?
Il n'est pas impossible de déterminer quels programmes sont valides et qui ne sont pas (Eh bien, peut-être en C ++, mais pas dans une simple langue de la machine à tanguer). Il est impossible de décider quels programmes s'arrêtent et qui ne le font pas. Mais vous n'avez pas besoin de savoir que pour diriger tous les programmes qui font obstacle - ce que vous faites est exécuté la première étape du programme 1, puis la première étape du programme 2, puis étape 2 sur 1, puis 1 sur 3, puis 1 sur 3, 2 sur 2, 3 sur 1, et ainsi de suite. Si un programme s'arrête lorsqu'il est exécuté seul, il s'arrêtera lorsqu'il sera exécuté de cette façon. Évidemment, vous avez besoin de beaucoup de mémoire, cependant ...
... Donc, une alternative serait de gérer les premiers millions de étapes de chacun des premiers millions de programmes à son tour, puis de recommencer et d'exécuter les deux premiers millions de étapes des deux premiers millions de programmes à son tour, etc. Vous n'avez pas à stocker l'état de chaque programme, juste pour les programmes qui vous intéressent, le drapeau qui se sont arrêtés. Bien sûr, cela nécessite beaucoup de temps, car vous réactivez le travail. Mais cela devrait être attendu si vous exécutez chaque programme qui existe :-)
Quoi qu'il en soit, le point est que vous pouvez énumérer des programmes valides, assurez-vous simplement de choisir une langue dans laquelle il est facile de déterminer si un programme est valide ou non. Avec une machine virtuelle de sandboxe appropriée; un ensemble d'instructions où tout ce qui n'est pas explicitement défini comme une opération est un non-op; et sauter des limites signifie «HALT», chaque séquence d'octets est un programme valide. Facile :-) Ce n'est tout simplement pas la même chose que d'évaluer toutes les fonctions calculables, puisque a) "Tous les programmes" inclut les non-halins, et (b) si un programme doit être utilisé comme fonction, alors qu'il arrête de s'arrêter dépend de l'entrée.
@Jason: Non, pas à moins que votre langue ait une limite de taille. Théoriquement au moins, vous pouvez créer un programme avec n'importe quel nombre de caractères jusqu'à l'infini et donc un nombre infini de programmes. Soustrayer une infini d'un autre est toujours l'infini (dans ce cas, l'infini du poing est un surset de la seconde). (Pas un mec mathématique alors dis-moi si quelqu'un est faux)
@RCIX Comptable est "une sorte d'infini", exactement ces infinités pouvant être mappées au nombre naturel (sa cardinalité est Aleph_0). Aleph_0 + -K est toujours Aleph_0 (par exemple, si vous soustrayez "un" de l'infini, vous obtenez toujours la même infini, pas un sous-ensemble). Mais aussi multiplier Aleph_0 par un rendement constant toujours à Aleph_0 (vous pouvez cartographier les numéros entier au naturel). Et encore plus, Aleph_0 est toujours Aleph_0! (Vous pouvez toujours cartographier les nombres rationnels aux entiers) ...
Le commentaire précédent n'était qu'une introduction mathématique du concept de dénombrable, revenons aux bases ... un moyen simple de cartographier les programmes vers des nombres naturels est simplement interpréter son code source comme un grand nombre binaire. Mon objection initiale était de pouvoir distinguer les programmes valides des celles invalides, pour avoir une cartographie sans lacunes.
Et crucialement pour ce que dit Fortran, l'ensemble des séquences finies d'un alphabet dénombrable est comptable. Les programmes sont des séquences finies d'un alphabet fini (ASCII, par exemple ou unicode), donc encore mieux. Si les programmes pourraient être infiniment longs, il y aurait alors nombre d'entre eux (c'est-à-dire, plus que Aleph_0), comme les chiffres réels. Mais ils ne peuvent pas, alors il n'y en a pas.
Je ne sais pas que je comprends. Une chose si - vous ne pouvez pas énumérer toutes les fonctions calculables possibles. Réponse courte: Par exemple, il y aura un antivirus universel. Réponse longue: car s'il y avait une telle énumération, vous auriez dans cet ensemble la fonction qui calcule l'énumération elle-même. Comme le paradoxe de Russel.
Une réponse différente à votre question serait - vous voulez `` liste '' toutes les fonctions calculables possibles; Pour ce faire, vous voudrez peut-être les représenter en tant que nombres premiers et utiliser leur composition comme multiplication. Cela garantirait l'unicité. La factorisation vous donnera la fonction inverse.
Pour les définitions habituelles de "énuméré" et "calculables", vous pouvez énumérer toutes les fonctions calculables. Fixer une machine de Turning universelle, commencez par ces fonctions calculées avec un ruban de longueur initial, puis passez à ceux calculés avec un ruban initial de longueur deux, ... Qu'est-ce qui compte que la fonction qui calcule l'énumération est quelque part Dans l'énumération?
Malheureusement, la composition de fonction n'est pas également commutative et la multiplication est.
Il est impossible d'énumérer toutes les fonctions récursives. Il est possible d'énumérer toutes les personnes récursives partielles.
-1: Répondre toujours mal. Une énumération de toutes les fonctions récursives partielles comprend toutes les fonctions récursives, y compris la fonction (calculable) qui énumère les fonctions récursives partielles. Tscheidungsproblem de Turing nous dit qu'il n'y a pas de test récursif pour quelles fonctions dans cette séquence sont calculables.
Bien qu'il ne soit pas trop difficile d'énumérer tous les expressions dans certaines langues, vous ne serez pas en mesure de les limiter à ces expressions qui dénotent fonctions de terminaison . < / p>
Mais si vous n'êtes pas intéressé par la résiliation, vous utilisez des combinaisons (avec des primitives arithmétiques levées pour l'utilité) pourraient être le meilleur moyen, puisque vous évitez d'introduire des noms variables de cette façon.
Comme le dit Pascal, ce que vous voulez est un interprète, mais on peut faire encore mieux: utilisez le processeur comme interprète directement.
Alimez le nombre N (disons, comme un grand réseau Int) directement sur un tampon et exécutez ce tampon en tant que machinecode.
Pour chaque fonction possible, votre ordinateur est capable d'exécuter qu'il existe une N. malheureusement. Tous les n sont un programme valide (ce n'était pas demandé) ou le programme de terminaison (ce qui n'est pas possible).
D'autre part, cette fonction produira des pierres précieuses telles que World of Warcraft, Microsoft Office 17, y compris Service Pack 6 et Windows 9.
Pas sûr que MS Office 17 est un gemme, mais vous êtes pardonné pour cela une fois. +1
Depuis que vous semblez avoir besoin d'aide et de drainer pour accepter une réponse. Le meilleur est Stackoverflow.com/questions/1797457/... par Pascal Cuoq. Le dernier de Hirschhornsalz n'est pas mauvais non plus. Je peux comprendre que c'est difficile pour vous de l'accepter.