Um programa orientado a objetos pode ser visto como uma máquina de estados finitos?

13

Essa pode ser uma pergunta filosófica / fundamental, mas eu só quero esclarecer.

No meu entendimento, uma máquina de estados finitos é uma maneira de modelar um sistema no qual a saída do sistema não depende apenas das entradas atuais, mas também do estado atual do sistema. Além disso, como o nome sugere, uma máquina de estados finitos pode ser segmentada em um número N finito de estados com seu respectivo estado e comportamento.

Se isso estiver correto, todos os objetos com dados e funções não deveriam ser um estado em nosso modelo orientado a objetos, tornando qualquer projeto orientado a objetos uma máquina de estados finitos?

Se essa não é a interpretação de um FSM no design de objetos, o que exatamente as pessoas querem dizer quando implementam um FSM no software? estou esquecendo de algo?

obrigado

Peretz
fonte
6
O software Computer + é uma máquina de estado, desde que você restrinja a memória, o espaço em disco e outros tipos de armazenamento (como a Internet). Assim que a interface com a Internet ou outro hardware externo é permitida (implica armazenamento ilimitado), isso se torna mais como uma máquina de Turing. Já ouviu falar de uma frase 'Turing complete'? De qualquer forma, os programas funcionais e os orientados a objetos terminam como código de montagem. Não conheço Haskel (uma linguagem funcional pura) / mônadas, mas deve haver uma relação interessante entre isso e uma máquina de Turing.
Job
Além do ponto de tarefas, qualquer forma de não-determinismo também excede os modelos de máquina de estado e de máquina de Turing. Na internet, você tem várias máquinas não sincronizadas, perda de dados por meio de conexões imperfeitas, etc. Mesmo com um computador simples de núcleo único, você recebe informações não determinísticas do usuário, mas normalmente ignora esse problema e finge todas as entrada era conhecida antecipadamente.
Steve314
@ Steve314: Formalmente, os autômatos determinísticos estão em um único estado. Cada entrada leva a um novo estado. Para autômatos não determinísticos, cada entrada pode levar a vários estados. Um autômato não determinístico com N estados pode ser emulado por um autômato determinístico com 2 ^ N estados.
precisa
@cline - Nesse caso, você está absolutamente certo, mas acho que o que eu tinha em mente era o tipo de simultaneidade e variação de tempo que acontecem em uma máquina do mundo real - coisas como um núcleo que fica um pouco mais lento porque está quente demais , o momento exato em que os dados estão sob a cabeça de leitura etc. Isso tudo se encaixa no modelo de autômatos finitos não determinísticos que você descreve, é claro, então você está absolutamente correto - mas o número de estados será incrivelmente grande. Eu acho que eu poderia ter tido medidas contínuas, como essas temperaturas, como parte do estado do sistema também (não apenas consequências).
Steve314

Respostas:

16

Qualquer programa de thread único em execução em uma máquina com uma quantidade finita de armazenamento pode ser modelado como uma máquina de estado finito. Um estado específico na máquina de estados finitos representará os valores específicos de todo o armazenamento relevante - variáveis ​​locais, variáveis ​​globais, armazenamento em heap, dados atualmente trocados na memória virtual, até o conteúdo dos arquivos relevantes. Em outras palavras, haverá muitos estados nesse modelo de estados finitos, mesmo para programas bastante triviais.

Mesmo que o único estado do seu programa seja uma única variável global de um tipo inteiro de 32 bits, isso implica pelo menos 2 ^ 32 (mais de 4 bilhões) de estados. E isso nem leva em consideração o contador do programa e a pilha de chamadas.

Um modelo de autômato push-down é mais realista para esse tipo de coisa. É como um autômato finito, mas tem um conceito embutido de pilha. Não é realmente uma pilha de chamadas, como na maioria das linguagens de programação.

Há uma explicação da Wikipedia , mas não fique atolado na seção de definição formal.

Autômatos push-down são usados ​​para modelar cálculos gerais. As máquinas de Turing são semelhantes , mas o IIRC não é idêntico - embora suas capacidades computacionais sejam equivalentes .

Agradecemos a Kevin Cline por apontar o erro acima - como a Wikipedia também aponta, os autômatos push-down são mais poderosos que as máquinas de estados finitos, mas menos poderosos que as máquinas de Turing.

Eu honestamente não sei onde esse peido de cérebro veio - I fazer saber que contexto gramáticas sensíveis são mais poderosos do contexto livre, e que gramática sensível ao contexto não pode ser analisado usando um autômato push-down simples. Eu até sei que, embora seja possível analisar qualquer gramática sem contexto inequívoca em tempo linear, geralmente é necessário mais do que um autômato push-down (determinístico) para fazer isso. Então, como eu poderia acabar acreditando que um autômato push-down é equivalente a uma máquina de Turing é bizarro.

Talvez eu estivesse pensando em um autômato push-down com algumas máquinas extras adicionadas, mas isso seria como contar um autômato finito como equivalente a um autômato push-down (basta adicionar e explorar uma pilha).

Autômatos push-down são importantes na análise. Estou familiarizado o suficiente com eles nesse contexto, mas nunca os estudei como modelos de computação da ciência da computação, por isso não posso dar muito mais detalhes do que já tenho.

É possível modelar um único objeto OOP como máquina de estados finitos. O estado da máquina será determinado pelos estados de todas as variáveis ​​de membro. Normalmente, você contaria apenas os estados válidos entre (não durante) as chamadas de método. Novamente, você geralmente tem muitos estados para se preocupar - é algo que você pode usar como modelo teórico, mas não gostaria de enumerar todos esses estados, exceto talvez em um caso trivial.

No entanto, é bastante comum modelar algum aspecto do estado de um objeto usando uma máquina de estados finitos. Um caso comum é a IA para objetos de jogo.

Isso também é feito tipicamente ao definir um analisador usando um modelo de autômato push-down. Embora exista um conjunto finito de estados em um modelo de estado, isso apenas modela parte do estado do analisador - informações adicionais são armazenadas em variáveis ​​extras ao lado desse estado. Isso resolve, por exemplo, a questão de 4 bilhões de estados por um número inteiro - não enumere todos esses estados, apenas inclua a variável número inteiro. Em certo sentido, ainda faz parte do estado de autômato push-down, mas é uma abordagem muito mais gerenciável do que, na verdade, desenhar 4 bilhões de bolhas de estado em um diagrama.

Steve314
fonte
1
"É possível modelar um único objeto OOP como máquina de estados finitos". Verdadeiro, mas fraco. Não é possível". É uma questão de definição. O trabalho de uma linguagem de programação é expressar um FSM em uma notação organizada. OOP é uma implementação de um FSM com notação mais simples para todos os vários estados.
S.Lott 22/07
1
@ S.Lott - Sim, mas a maioria das pessoas não pensa em um objeto OOP como expressando um FSM, pelo menos na maioria das vezes. O uso do nome "máquina de estado" tende a sugerir que você está usando alguma implementação específica, como o padrão de design do estado ou uma variável de membro de ID do estado. "Modelar como uma máquina de estado" geralmente também implica algo na documentação de especificação ou design, diferente da implementação dessa classe. Portanto, modelar uma classe como um modelo de estado finito subjetivamente significa algo diferente de apenas fornecer o código-fonte para a classe.
21311 Steve114
"as pessoas não pensam". Verdade. E um problema profundo. Todos os programas são máquinas de estado. Eles têm muitos estados. É isso que o teste "Turing Complete" para uma linguagem de programação exige. É uma regra muito, muito forte (e absoluta). Em vez de sugerir que é "possível", é mais como "necessário" e "suficiente".
S.Lott 22/07
1
-1: autômatos push-down NÃO são tão poderosos quanto as máquinas de Turing.
kevin Cline
1
@ Kevin Cline - obrigado - e o que eu estava pensando !!! Editado para eliminar esse detalhe. Apesar do que eu disse sobre o estudo formal, eu sei melhor do que isso e deveria ter sabido melhor naquela época.
Steve314
5

A questão não é se algo "é" ou "não é" uma máquina de estados finitos. Uma máquina de estados finitos é um modelo mental que pode ser útil para entender algo, se isso puder ser pensado como um.

Normalmente, o modelo de máquina de estados finitos se aplica a itens com um pequeno número de estados, como uma gramática regular ou o seqüenciador de instruções de um computador.

Mike Dunlavey
fonte
1

Para responder sua pergunta diretamente: quase certamente não. Não parece haver uma teoria matemática formal para OOP da maneira que o cálculo lambda e / ou a programação combinada da lógica combinatória são subestimados, ou a programação imperativa imperativa comumente antiga da Turing Machines.

Veja esta pergunta sobre o stackoverflow para mais.

Meu palpite é que a falta de uma teoria matemática subjacente é por que todo mundo sabe o que é um "objeto" quando vê um, mas ninguém vê "objetos" da mesma forma que qualquer outra pessoa.

Bruce Ediger
fonte
0

Não, praticamente não mesmo. Uma máquina de estados finitos normalmente lembra apenas um dado: seu estado atual.

Uma aplicação típica de um FSM é lexing ou análise. Por exemplo, quando estamos fazendo lexing, é (normalmente) bastante fácil codificar as ações para todas as entradas possíveis em termos de um estado atual e o valor da entrada.

Por exemplo, podemos ter um estado NUMBER no qual estamos lendo os dígitos de um número. Se o próximo caractere que lemos for um dígito, permaneceremos no estado NUMBER. Se for um espaço ou uma guia, retornaremos os dígitos e avançaremos para algum estado WHITE_SPACE, ou algo nesse pedido.

Agora, certamente é verdade que em um FSM típico (especialmente um implementado em software) acabamos com pedaços que tecnicamente não se encaixam perfeitamente em um FSM misturado com o próprio FSM. Por exemplo, quando estamos lendo dígitos de um número, você frequentemente salva a posição do primeiro dígito; assim, ao chegar ao final, pode calcular facilmente o valor do número.

O FSM em si tem algumas limitações - não possui mecanismo de contagem. Considere, por exemplo, um idioma que use "/ " para iniciar um comentário e " /" para finalizar um comentário. Seu lexer provavelmente teria um estado COMMENT em que entrou quando viu um token ' / '. Não há como, neste momento (além de adicionar outro estado como COMMENT2), detectar outro "/ " e perceber que está lidando com um comentário aninhado. Em vez disso, no estado de comentário, ele reconhecerá*/ como dizendo para deixar o estado de comentário e qualquer outra coisa o deixará no estado de comentário.

Como mencionado, você certamente poderia incluir um estado COMMENT2 para um comentário aninhado - e, nesse estado, um estado COMMENT3 e assim por diante. Em algum momento, no entanto, você ficará cansado de adicionar mais estados, e isso determinará a profundidade máxima de aninhamento permitida para comentários. Com alguma outra forma de analisador (ou seja, não é uma máquina de estado puro, mas algo que possui memória para permitir a contagem), você pode rastrear diretamente a profundidade do aninhamento, permanecendo no estado COMMENT até chegar a um token de comentário próximo que equilibra o primeiro, então seu contador volta para 0 e você sai do estado COMMENT.

Como eu disse, no entanto, quando você adiciona um contador como esse, o que você tem não é mais um FSM. Ao mesmo tempo, é realmente muito próximo - especificamente, próximo o suficiente para que você possa simular o contador apenas adicionando mais estados.

No entanto, em um caso típico, quando alguém fala sobre a implementação de um FSM em software, ele o mantém razoavelmente "puro". Em particular, o software reagirá à entrada atual com base apenas no estado atual e no valor da própria entrada. Se a reação depender de quase tudo, eles geralmente não a chamarão de máquina de estado (pelo menos se souberem do que estão falando).

Jerry Coffin
fonte
"seu estado atual" pode incluir uma grande quantidade de informações. Um FSM pode contar trivialmente tendo estados para cada número que contará. É finito (ao contrário de uma máquina de Turing), mas ainda é perfeitamente capaz de contar. Eu acho que você pode precisar de um exemplo melhor.
S.Lott 22/07
o software do seu telefone celular é uma coleção de máquinas de estado terrivelmente complexas que lembram muitos dados e os interpretam de acordo com o estado atual.
Mawg diz que restabelece Monica
-2

Não acredito que a resposta aceita esteja completamente correta.

Você não pode modelar um programa arbitrário escrito em uma linguagem Turing Complete, orientada ou não a objetos, como uma Máquina de Estado Finito. Quase todas as linguagens de computador modernas, como Java, C ++ ou Smalltalk, são Turing Complete.

Por exemplo, você não pode criar uma máquina de estados finitos para reconhecer uma sequência de objetos em que você possui n instâncias de um objeto seguidas por n instâncias de outro objeto porque as máquinas de estados finitos são incapazes de gravar n em uma variável. Eles podem apenas ler entrada e alternar para um estado.

James Fremen
fonte
esta apenas repete pontos feitos e explicado em respostas Colocado há 3 anos atrás, por exemplo, em um presente
mosquito