Un programma orientato agli oggetti può essere visto come una macchina a stati finiti?

Qualsiasi programma a thread singolo in esecuzione su una macchina con una quantità limitata di memoria può essere modellato come una macchina a stati finiti. Uno stato particolare nella macchina a stati finiti rappresenterà i valori specifici di tutte le variabili locali di memoria rilevanti, le variabili globali, la memoria heap, i dati attualmente scambiati nella memoria virtuale, persino il contenuto dei file rilevanti. In altre parole, ci sarà un lotto di stati in quel modello a stati finiti, anche per programmi abbastanza banali.

Anche se l'unico stato del programma è una singola variabile globale di un tipo intero a 32 bit, ciò implica almeno 2 ^ 32 (più di 4 miliardi) stati. E questo non prende nemmeno in considerazione il contatore del programma e lo stack delle chiamate.

Un modello di automa push-down è più realistico per questo genere di cose. È come un automa finito, ma ha un concetto incorporato di pila. Però non è davvero uno stack di chiamate come nella maggior parte dei linguaggi di programmazione.

C'è una spiegazione di Wikipedia , ma non impantanarti nella sezione di definizione formale.

Gli automi push-down sono usati per modellare calcoli generali. Le macchine di Turing sono simili a , ma IIRC non è identico - sebbene le loro capacità di calcolo siano equivalenti .

Thankyou to kevin cline for pointing out the error above - as Wikipedia also points out, push-down automata are more powerful than finite state machines, but less powerful than Turing machines.

I honestly don't know where this brain fart came from - I do know that context sensitive grammars are more powerful than context free, and that context sensitive grammars can't be parsed using a simple push-down automaton. I even know that while it's possible to parse any unambiguous context-free grammar in linear time, it generally takes more than a (deterministic) push-down automaton to do that. So how I could end up believing a push-down automaton is equivalent to a Turing machine is bizarre.

Maybe I was thinking of a push-down automaton with some extra machinery added, but that would be like counting a finite automaton as equivalent to a push-down automaton (just add and exploit a stack).

Gli automi push-down sono importanti nell'analisi. Sono abbastanza familiare con loro in quel contesto, ma non li ho mai veramente studiati come modelli di calcolo di computer science, quindi non posso fornire molti più dettagli di quelli che ho già.

È possibile modellare un singolo oggetto OOP come macchina a stati finiti. Lo stato della macchina sarà determinato dagli stati di tutte le variabili membro. Normalmente, si contano solo gli stati validi tra (non durante) le chiamate di metodo. Di nuovo, avrai in genere molti stati di cui preoccuparti: è qualcosa che potresti usare come modello teorico, ma non vorrai enumerare tutti questi stati, tranne forse in un caso banale.

È abbastanza comune, tuttavia, modellare alcuni aspetto dello stato di un oggetto usando una macchina a stati finiti. Un caso comune è l'intelligenza artificiale per gli oggetti di gioco.

Questo è anche ciò che viene in genere fatto quando si definisce un parser usando un modello di automa push-down. Sebbene ci sia un insieme finito di stati in un modello di stato, questo modello solo parte dello stato del parser - informazioni aggiuntive sono memorizzate in variabili extra accanto a quello stato. Questo risolve ad es. il problema di 4 miliardi di stati per uno integer, non elencare tutti questi stati, basta includere la variabile intera. In un certo senso è ancora parte dello stato dell'automa push-down, ma è un approccio molto più gestibile che in effetti disegnando 4 miliardi di bolle di stato su un diagramma.

Il problema non è se qualcosa "è" o "non è" una macchina a stati finiti. Una macchina a stati finiti è un modello mentale che può essere utile per capire qualcosa se quella cosa può essere pensata come una sola.

Tipicamente il modello di macchina a stati finiti si applica a cose con un piccolo numero di stati, come una grammatica regolare o il sequenziatore di istruzioni di un computer.

Per rispondere direttamente alla tua domanda: quasi certamente no. Non sembra esserci una teoria matematica formale per OOP il modo in cui lambda calcolo e / o logica di programmazione combinatoria non funziona, o le macchine di Turing sono sottilmente ordinarie e vecchie programmazioni imperative.

Vedi questa domanda di stackoverflow per ulteriori informazioni.

La mia ipotesi è che la mancanza di una teoria matematica sottostante è la ragione per cui tutti sanno cos'è un "oggetto" quando ne vedono uno, ma nessuno vede "oggetti" esattamente come chiunque altro.

No, non praticamente comunque. Una macchina a stati finiti normalmente ricorda solo un pezzo di dati: il suo stato attuale.

Una tipica applicazione di un FSM è il lexing o l'analisi. Ad esempio, quando stiamo facendo lexing, è (normalmente) abbastanza facile codificare le azioni per ogni possibile input in termini di uno stato corrente e il valore dell'input.

Ad esempio, potremmo avere uno stato NUMBER in cui stiamo leggendo le cifre di un numero. Se il prossimo carattere che leggiamo è una cifra, restiamo nello stato NUMBER. Se si tratta di uno spazio o di una scheda, restituiremo le cifre e quindi passeremo a qualche stato di WHITE_SPACE o qualcosa del genere.

Ora, è certamente vero che in un tipico FSM (specialmente uno che è implementato nel software) ci ritroviamo con frammenti che tecnicamente non si adattano perfettamente ad un FSM mescolato con lo stesso FSM. Ad esempio, quando stiamo leggendo cifre di un numero, salvi frequentemente la posizione della prima cifra, quindi quando arrivi alla fine puoi facilmente calcolare il valore del numero.

Lo stesso FSM ha alcune limitazioni: non ha un meccanismo di conteggio. Si consideri, ad esempio, un linguaggio che utilizza "/ " per iniziare un commento e " /" per terminare un commento. Il suo lexer avrebbe probabilmente uno stato COMMENTO che è entrato quando ha visto un token '/ '. A questo punto non ha alcun modo (a parte aggiungere un altro stato come COMMENT2) per rilevare un altro "/ " e rendersi conto che si tratta di un commento annidato. Piuttosto, nello stato dei commenti, riconoscerà */ come dicendo di lasciare lo stato dei commenti e qualsiasi altra cosa lo lascia nello stato dei commenti.

Come già detto, potresti certamente includere uno stato COMMENT2 per un commento nidificato, e in quello, uno stato COMMENT3 e così via. Ad un certo punto, tuttavia, ti stancherai di aggiungere altri stati e questo determinerà la profondità massima di annidamento che ammetti per i commenti. Con qualche altra forma di parser (vale a dire, non una macchina a stati puri, ma qualcosa che ha un po 'di memoria per lasciarla contare) puoi semplicemente tenere traccia direttamente della profondità di annidamento, così rimani nello stato COMMENT fino a raggiungere un token commento vicino che bilancia il primo, quindi il tuo contatore torna a 0 e lasci lo stato COMMENT.

Come ho detto, tuttavia, quando aggiungi un segnalino come quello, ciò che hai non è più un vero FSM. Allo stesso tempo, è in realtà piuttosto vicino - in particolare, abbastanza vicino da poter simulare il contatore semplicemente aggiungendo altri stati.

In un caso tipico, tuttavia, quando qualcuno parla dell'implementazione di un FSM nel software, lo manterrà ragionevolmente "puro". In particolare, il software reagirà all'ingresso corrente in base solo allo stato corrente e al valore dell'input stesso. Se la reazione dipende da molto altro, di solito non la chiameranno una macchina a stati (almeno se sanno di cosa stanno parlando).

Non credo che la risposta accettata sia completamente corretta.

Non è possibile modellare un programma arbitrario scritto in una lingua Turing Complete, indipendentemente dal fatto che sia orientato agli oggetti o meno, come una macchina a stati finiti. Quasi tutti i linguaggi informatici moderni, come Java, C ++ o Smalltalk, sono completati da Turing.

Ad esempio, non è possibile creare una macchina a stati finiti per riconoscere una sequenza di oggetti in cui sono presenti n istanze di un oggetto seguite da n istanze di un altro oggetto perché le macchine a stati finiti non sono in grado di scrivere n in una variabile. Possono solo leggere l'input e passare a uno stato.