Langages de programmation non déterministes
je sais en Prolog vous pouvez faire quelque chose comme
someFunction(List) :-
someOtherFunction(X, List)
doSomethingWith(X)
% and so on
ce ne sera pas itérer sur chaque élément dans la liste; au lieu de cela, il se ramifiera dans différentes" machines " (en utilisant des fils multiples, le retraçage sur un seul fil, la création d'univers parallèles ou whathave you) , avec une exécution séparée pour chaque valeur possible de X qui fait someOtherFunction(X, List) pour retourner vrai!
(Je n'ai pas idée de comment il le fait, mais ce n'est pas important de la question)
ma question Est: Quels sont les autres langages de programmation non-determistes? il semble que le non-déterminisme est le moyen le plus simple et le plus logique d'implémenter le multi-threading dans un langage avec des variables immuables, mais je n'ai jamais vu Cela fait avant - pourquoi cette technique n'est-elle pas plus populaire?
8 réponses
Prologue est en fait déterministe-l'ordre d'évaluation est prescrit, et l'ordre des questions.
pourquoi le non-déterminisme n'est-il pas plus populaire?
le non-déterminisme est impopulaire parce qu'il rend plus difficile de raisonner au sujet des résultats de vos programmes, et vraiment non-déterministe les exécutions (par opposition à la sémantique) sont difficiles à mettre en œuvre.
le seul non-déterministe langues que je connais sont
-
calcul de Dijkstra de commandes gardées, qu'il ne voulait jamais être mis en œuvre
-
ml simultané, dans lequel les communications peuvent être synchronisées de façon non déterministe
-
la langue Promela de Gerard Holzmann, qui est la langue du modèle checker SPIN
SPIN does en fait, utilisez le non-déterminisme et explore tout l'espace de l'état quand il le peut.
et bien sûr tout langage multithread se comporte de manière non-déterministe si les threads ne sont pas synchronisés, mais c'est exactement le genre de chose qui est difficile à raisonner-et pourquoi il est si difficile de mettre en œuvre des structures de données efficaces et correctes.
D'ailleurs, si vous cherchez à obtenir le parallélisme, vous pouvez obtenir la même chose par un simple map dans un langage purement fonctionnel comme Haskell. Il ya une raison Google MapReduce est basé sur les langues fonctionnelles.
le article Wikipedia pointe vers Amb qui est un dérivé Scheme avec des capacités pour la programmation non déterministe.
pour autant que je comprenne, la principale raison pour laquelle les langages de programmation ne font pas cela est que l'exécution d'un programme non déterministe sur une machine déterministe (comme le sont tous les ordinateurs existants) est intrinsèquement coûteuse. Fondamentalement, une machine de Turing non déterministe peut résoudre des problèmes complexes dans temps polynomial, pour lequel aucun algorithme polynomial pour une machine de Turing déterministe n'est connu. En d'autres termes, la programmation non déterministe ne parvient pas à saisir l'essence de l'algorithmique dans le contexte des ordinateurs existants.
Le même problème impacts Prolog. Toute application Prolog efficace, ou du moins peu inefficace, doit utiliser l'opérateur "cut" pour éviter d'explorer un nombre exponentiel de chemins. L'opérateur ne fonctionne que tant que le programmeur a une bonne vue mentale de la façon dont L'interprète Prolog explorera les chemins possibles, d'une manière déterministe et très procédurale. Les choses qui sont très procédurales ne se marient pas bien avec la programmation fonctionnelle, puisque cette dernière est principalement un effort de ne pas penser procéduralement du tout.
entre les machines de Turing déterministes et non déterministes, il y a le modèle de" calcul quantique". Un ordinateur quantique, en supposant qu'un Existe, ne fait pas tout ce qu'un la machine de Turing non déterministe peut faire, mais elle peut faire plus qu'une machine de Turing déterministe. Il y a des gens qui conçoivent actuellement des langages de programmation pour l'ordinateur quantique (en supposant qu'un ordinateur quantique sera finalement construit). Certains de ces nouvelles langues sont fonctionnels. Vous pouvez trouver un hôte de liens utiles sur cette page Wikipedia . Apparemment, concevoir un langage de programmation quantique, fonctionnel ou non, et l'utiliser, n'est pas facile et certainement pas "simple."
dans Prolog vous pouvez avoir à la fois le non-déterminisme et la simultanéité. Le non-déterminisme est ce que vous avez décrit dans votre question concernant le code de l'exemple. Vous pouvez imaginer qu'une clause Prolog est pleine de déclarations implicites amb . Il est moins connu que la simultanéité est également soutenue par la programmation logique.
L'histoire dit:
le premier langage de programmation logique concurrent a été le relationnel La langue de Clark et Gregory, qui était une émanation de IC-Prolog. Les versions suivantes de la programmation logique concurrente incluent Shapiro Prolog et Ueda's Guarded Horn Clause langage GHC. https://en.wikipedia.org/wiki/Concurrent_logic_programming
mais aujourd'hui nous pourrions juste aller avec les traces à l'intérieur de la programmation logique. ici est un exemple pour implémenter un findall via des threads. Cela peut également être modulé pour effectuer toutes sortes de tâches sur la collection, ou peut-être même produire des réseaux d'agents vers l'intelligence artificielle distribuée.
un exemple de langage non déterministe est Occam , basé sur CSP théorie. La combinaison des constructions PAR et ALT peut donner lieu à un comportement non déterministe dans les systèmes multiprocesseurs, mettant en œuvre les programmes fine grain parallel .
lors de l'utilisation de canaux doux, c.-à-d. canaux entre processus sur le même processeur, la mise en œuvre de ALT sera faites le comportement près de déterministe † , mais dès que vous commencez à utiliser des canaux durs (liens de communication physique hors processeur) toute illusion de déterminisme disparaît. Les différents processeurs distants ne sont pas censés être synchronisés de quelque manière que ce soit et ils peuvent même ne pas avoir la même vitesse de base ou d'horloge.
† la construction ALT est souvent implémentée avec un PRI ALT , donc vous devez indiquez explicitement l'équité si vous voulez qu'elle soit équitable.
le non-déterminisme est considéré comme un désavantage quand il s'agit de raisonner et de prouver que les programmes sont corrects, mais à bien des égards, une fois que vous l'avez accepté, Vous êtes libéré de bon nombre des contraintes que le déterminisme force votre raisonnement.
aussi longtemps que le séquençage de la communication ne conduit pas à deadlock , qui peut être fait en appliquant des techniques CSP, puis l'ordre précis dans lequel les choses sont faites devrait importe beaucoup moins que si vous obtenez les résultats que vous voulez dans le temps.
c'est sans doute ce manque de déterminisme qui a été un facteur majeur dans la prévention de L'adoption de L'Occam et Transputer systèmes dans les projets militaires, dominé par Ada à l'époque, où savoir précisément ce qu'un CPU faisait à chaque cycle d'horloge a été considéré comme essentiel pour prouver un système correct. Sans cette contrainte, L'Occam et les systèmes de transport sur lesquels elle fonctionnait (les seuls CPU à l'époque avec une implémentation de point flottant IEEE formellement prouvée) auraient été parfaitement adaptés aux systèmes militaires durs en temps réel nécessitant des niveaux élevés de fonctionnalité de traitement dans un petit espace.
je crois que Haskell a la capacité de construire et la machine non-déterministe. Haskell à première vue peut sembler trop difficile et abstrait pour une utilisation pratique, mais il est en fait très puissant.
il existe un langage de programmation pour les problèmes non déterministes qui est appelé"programmation réseau de contrôle". Si vous voulez plus d'informations allez à http://controlnetworkprogramming.com . Ce site est toujours en cours, mais vous pouvez lire quelques infos à ce sujet.
Note: Avant de cliquer sur le lien et d'être déçu: il s'agit d'une langue ésotérique et n'a rien à voir avec le parallélisme.
le Sly langage de programmation en cours de développement chez IBM Research est une tentative d'inclure le non-déterminisme inhérent à l'exécution multi-threadé dans l'exécution de certains types d'algorithmes. Semble être très bien un travail en cours.