Un programme orienté objet peut-il être considéré comme une machine à états finis?

C'est peut-être une question philosophique / fondamentale, mais je veux juste la clarifier.

À ma connaissance, une machine à états finis est un moyen de modéliser un système dans lequel la sortie du système dépendra non seulement des entrées actuelles, mais aussi de l'état actuel du système. De plus, comme son nom l'indique, une machine à états finis peut être segmentée en un nombre N fini d'états avec son état et son comportement respectifs.

Si cela est correct, chaque objet avec des données et des membres de fonction ne devrait-il pas être un état dans notre modèle orienté objet, faisant de toute conception orientée objet une machine à états finis?

Si ce n'est pas l'interprétation d'un FSM dans la conception d'objets, que veulent exactement dire les gens lorsqu'ils implémentent un FSM dans un logiciel? est-ce que je manque quelque chose?

Merci

Tout programme monothread s'exécutant sur une machine avec une quantité finie de stockage peut être modélisé comme une machine à états finis. Un état particulier dans la machine à états finis représentera les valeurs spécifiques de tous les stockages pertinents: variables locales, variables globales, stockage en tas, données actuellement échangées dans la mémoire virtuelle, même le contenu des fichiers pertinents. En d'autres termes, il y aura beaucoup d'états dans ce modèle à états finis, même pour des programmes assez triviaux.

Même si le seul état de votre programme est une seule variable globale d'un type entier 32 bits, cela implique au moins 2 ^ 32 (plus de 4 milliards) d'états. Et cela ne tient même pas compte du compteur de programme et de la pile d'appels.

Un modèle d'automate déroulant est plus réaliste pour ce genre de chose. C'est comme un automate fini, mais a un concept intégré de pile. Ce n'est pas vraiment une pile d'appels comme dans la plupart des langages de programmation.

Il y a une explication Wikipedia , mais ne vous enlisez pas dans la section de définition formelle.

Les automates déroulants sont utilisés pour modéliser des calculs généraux. Les machines de Turing sont similaires , mais l'IIRC n'est pas identique - bien que leurs capacités de calcul soient équivalentes .

Merci à Kevin Cline d'avoir signalé l'erreur ci-dessus - comme le souligne également Wikipedia , les automates déroulants sont plus puissants que les machines à états finis, mais moins puissants que les machines Turing.

Honnêtement , je ne sais pas où cela pète cerveau provenait - Je ne sais ce contexte sensibles sont plus grammaires puissants que dans un contexte libre, et que les grammaires sensibles au contexte ne peut pas être analysé à l' aide d' un simple automate push-down. Je sais même que s'il est possible d'analyser n'importe quelle grammaire sans contexte sans ambiguïté en temps linéaire, il faut généralement plus qu'un automate (déterministe) pour le faire. Donc, comment je pourrais finir par croire qu'un automate push-down est équivalent à une machine de Turing est bizarre.

Peut-être que je pensais à un automate push-down avec des machines supplémentaires ajoutées, mais ce serait comme compter un automate fini comme équivalent à un automate push-down (il suffit d'ajouter et d'exploiter une pile).

Les automates déroulants sont importants pour l'analyse. Je les connais assez bien dans ce contexte, mais je ne les ai jamais vraiment étudiés en tant que modèles informatiques de calcul, donc je ne peux pas donner beaucoup plus de détails que je n'en ai déjà.

Il est possible de modéliser un seul objet OOP comme machine à états finis. L'état de la machine sera déterminé par les états de toutes les variables membres. Normalement, vous ne comptez que les états valides entre (pas pendant) les appels de méthode. Encore une fois, vous aurez généralement beaucoup d'états à vous soucier - c'est quelque chose que vous pourriez utiliser comme modèle théorique, mais vous ne voudriez pas énumérer tous ces états, sauf peut-être dans un cas trivial.

Il est cependant assez courant de modéliser certains aspects de l'état d'un objet à l'aide d'une machine à états finis. Un cas courant est l'IA pour les objets de jeu.

C'est également ce qui est généralement fait lors de la définition d'un analyseur à l'aide d'un modèle d'automate déroulant. Bien qu'il existe un ensemble fini d'états dans un modèle d'état, cela ne modélise qu'une partie de l'état de l'analyseur - des informations supplémentaires sont stockées dans des variables supplémentaires à côté de cet état. Cela résout par exemple le problème des 4 milliards d'états pour un entier - n'énumérez pas tous ces états, incluez simplement la variable entière. Dans un sens, cela fait toujours partie de l'état de l'automate déroulant, mais c'est une approche beaucoup plus gérable que de dessiner en fait 4 milliards de bulles d'état sur un diagramme.

La question n'est pas de savoir si quelque chose «est» ou «n'est pas» une machine à états finis. Une machine à états finis est un modèle mental qui peut être utile pour comprendre quelque chose si cette chose peut être considérée comme une seule.

En règle générale, le modèle de machine à états finis s'applique aux choses avec un petit nombre d'états, comme une grammaire régulière ou le séquenceur d'instructions d'un ordinateur.

Pour répondre directement à votre question: certainement pas. Il ne semble pas y avoir de théorie mathématique formelle pour la POO de la même manière que le calcul lambda et / ou la logique combinatoire sous-tendent la programmation fonctionnelle, ou les machines de Turing sous la vieille programmation impérative ordinaire.

Consultez cette question de stackoverflow pour en savoir plus.

Je suppose que l'absence d'une théorie mathématique sous-jacente est la raison pour laquelle tout le monde sait ce qu'est un «objet» quand il en voit un, mais personne ne voit des «objets» tout à fait comme les autres.

Non, pas pratiquement de toute façon. Une machine à états finis ne se souvient normalement que d'une seule donnée: son état actuel.

Une application typique d'un FSM est lexing ou l'analyse. Par exemple, lorsque nous faisons de la lexing, il est (normalement) assez facile de coder les actions pour chaque entrée possible en termes d'état actuel et la valeur de l'entrée.

Par exemple, nous pourrions avoir un état NUMBER dans lequel nous lisons les chiffres d'un nombre. Si le caractère suivant que nous lisons est un chiffre, nous restons dans l'état NUMBER. S'il s'agit d'un espace ou d'une tabulation, nous renvoyons les chiffres, puis passons à un état WHITE_SPACE, ou quelque chose dans cet ordre.

Maintenant, il est certainement vrai que dans un FSM typique (en particulier celui qui est implémenté dans un logiciel), nous nous retrouvons avec des morceaux qui, techniquement, ne correspondent pas tout à fait à un FSM mélangé au FSM lui-même. Par exemple, lorsque nous lisons des chiffres d'un nombre, vous allez souvent enregistrer la position du premier chiffre, donc lorsque vous arrivez à la fin, vous pouvez facilement calculer la valeur du nombre.

Le FSM lui-même a certaines limites - il n'a pas de mécanisme de comptage. Considérons, par exemple, une langue qui utilise "/ " pour commencer un commentaire et " /" pour terminer un commentaire. Son lexer aurait probablement un état COMMENTAIRE qu'il est entré lorsqu'il a vu un jeton «/ ». Il n'a aucun moyen à ce stade (à moins d'ajouter un autre état comme COMMENT2) de détecter un autre "/ " et de réaliser qu'il s'agit d'un commentaire imbriqué. Au contraire, dans l'état de commentaire, il reconnaîtra */comme lui disant de quitter l'état de commentaire, et toute autre chose le laisse dans l'état de commentaire.

Comme mentionné précédemment, vous avez certainement pu inclure un état comment2 pour un commentaire imbriqué - et en ce que l'état de comment3, et ainsi de suite. À un moment donné, cependant, vous allez en avoir assez d'ajouter d'autres états, ce qui déterminera la profondeur d'imbrication maximale que vous autorisez pour les commentaires. Avec une autre forme d'analyseur (c'est-à-dire pas une machine à états purs, mais quelque chose qui a de la mémoire pour la laisser compter), vous pouvez simplement suivre directement votre profondeur d'imbrication, de sorte que vous restez dans l'état COMMENT jusqu'à ce que vous atteigniez un jeton de commentaire proche qui équilibre le premier, donc votre compteur revient à 0 et vous quittez l'état COMMENT.

Comme je l'ai dit, cependant, lorsque vous ajoutez un compteur comme celui-ci, ce que vous avez n'est plus vraiment un FSM. En même temps, il est en fait assez proche - spécifiquement, suffisamment proche pour que vous puissiez simuler le compteur en ajoutant simplement plus d'états.

Dans un cas typique, cependant, lorsque quelqu'un parle d'implémenter un FSM dans un logiciel, il le gardera raisonnablement "pur". En particulier, le logiciel réagira à l'entrée actuelle uniquement en fonction de l'état actuel et de la valeur de l'entrée elle-même. Si la réaction dépend de beaucoup d'autre chose, ils ne l'appelleront généralement pas une machine d'état (du moins s'ils savent de quoi ils parlent).

Je ne crois pas que la réponse acceptée soit complètement correcte.

Vous ne pouvez pas modéliser un programme arbitraire écrit dans un langage Turing Complete, qu'il soit orienté objet ou non, comme une machine à états finis. Presque tous les langages informatiques modernes, tels que Java, C ++ ou Smalltalk, sont Turing Complete.

Par exemple, vous ne pouvez pas créer une machine à états finis pour reconnaître une séquence d'objets où vous avez n instances d'un objet suivies de n instances d'un autre objet car les machines à états finis sont incapables d'écrire n dans une variable. Ils peuvent uniquement lire l'entrée et passer à un état.