Czy program zorientowany obiektowo może być postrzegany jako skończona maszyna stanowa?

To może być pytanie filozoficzne / fundamentalne, ale chcę to wyjaśnić.

W moim rozumieniu Maszyna Skończonych Stanów jest sposobem modelowania systemu, w którym moc wyjściowa systemu będzie zależeć nie tylko od bieżących danych wejściowych, ale także od bieżącego stanu systemu. Ponadto, jak sugeruje nazwa, skończona maszyna stanów może być podzielona na segmenty w skończonej liczbie stanów N z odpowiednim stanem i zachowaniem.

Jeśli jest to poprawne, to czy każdy obiekt z danymi i elementami funkcji nie powinien być stanem w naszym modelu obiektowym, czyniąc jakikolwiek projekt obiektowy maszyną skończoną?

Jeśli nie jest to interpretacja FSM w projektowaniu obiektowym, co dokładnie ludzie mają na myśli, gdy wdrażają FSM w oprogramowaniu? czy coś mi brakuje?

Dzięki

Każdy jednowątkowy program działający na maszynie ze skończoną ilością pamięci może być modelowany jako skończona maszyna stanu. Określony stan w skończonej maszynie stanów będzie reprezentował określone wartości wszystkich odpowiednich pamięci - zmiennych lokalnych, zmiennych globalnych, pamięci sterty, danych obecnie zamienionych w pamięci wirtualnej, a nawet zawartości odpowiednich plików. Innymi słowy, w tym modelu stanów skończonych będzie wiele stanów, nawet dla dość trywialnych programów.

Nawet jeśli jedynym stanem, jaki ma Twój program, jest pojedyncza zmienna globalna 32-bitowej liczby całkowitej, co implikuje co najmniej 2 ^ 32 (ponad 4 miliardy) stanów. A to nawet nie bierze pod uwagę licznika programów i stosu wywołań.

Model automatyczny z opuszczaniem jest bardziej realistyczny dla tego rodzaju rzeczy. To jest jak automat skończony, ale ma wbudowaną koncepcję stosu. Jednak tak naprawdę nie jest to stos wywołań, jak w większości języków programowania.

Istnieje wyjaśnienie Wikipedii , ale nie daj się wciągnąć w część definicji formalnej.

Automaty przesuwane służą do modelowania obliczeń ogólnych. Maszyny Turinga są podobne , ale IIRC nie są identyczne - chociaż ich możliwości obliczeniowe są równoważne .

Dziękuję Kevinowi Cline za wskazanie powyższego błędu - jak wskazuje również Wikipedia , automaty do obniżania są silniejsze niż maszyny o skończonych stanach, ale słabsze niż maszyny Turinga.

Szczerze mówiąc, nie wiem, skąd to pochodzi z mózgu pierdnięcie - I zrobić wiedzieć, że gramatyka kontekstowa są bardziej skuteczne niż kontekście wolnego i że Gramatyki kontekstowe nie mogą być analizowane za pomocą prostego push-down automat. Wiem nawet, że chociaż możliwe jest parsowanie dowolnej jednoznacznej gramatyki bezkontekstowej w czasie liniowym, na ogół potrzeba więcej niż (deterministycznego) automatu push-down. Więc jak mogłem uwierzyć, że automat zwijający jest równoważny maszynie Turinga, jest dziwny.

Może myślałem o automacie push-down z dodanymi dodatkowymi maszynami, ale to byłoby jak liczenie automatu skończonego jako równoważnego automatowi push-down (wystarczy dodać i wykorzystać stos).

Automatyczne pchanie są ważne podczas analizowania. W tym kontekście znam je dość dobrze, ale tak naprawdę nigdy nie studiowałem ich jako komputerowych modeli obliczeniowych, więc nie mogę podać więcej szczegółów niż już mam.

Możliwe jest modelowanie pojedynczego obiektu OOP jako skończonej maszyny stanów. Stan maszyny zostanie określony przez stany wszystkich zmiennych składowych. Zwykle liczy się tylko poprawne stany między wywołaniami metod (nie podczas). Ponownie, ogólnie będziesz mieć wiele stanów do zmartwienia - możesz to wykorzystać jako model teoretyczny, ale nie chciałbyś wyliczać wszystkich tych stanów, z wyjątkiem może trywialnego przypadku.

Jednak dość powszechne jest modelowanie jakiegoś aspektu stanu obiektu za pomocą skończonej maszyny stanów. Częstym przypadkiem jest AI dla obiektów gry.

Jest to również zwykle wykonywane podczas definiowania analizatora składni za pomocą modelu automatu push-down. Chociaż w modelu stanu istnieje skończony zestaw stanów, modeluje tylko część stanu analizatora składni - dodatkowe informacje są przechowywane w dodatkowych zmiennych obok tego stanu. Rozwiązuje to np. Problem 4 miliardów stanów na jedną liczbę całkowitą - nie wyliczaj wszystkich tych stanów, po prostu dołącz zmienną całkowitą. W pewnym sensie jest to nadal część stanu automatyzującego push-down, ale jest to znacznie łatwiejsze do opanowania podejście niż w efekcie rysowanie 4 miliardów bąbelków stanu na diagramie.

Problemem nie jest to, czy coś „jest”, czy „nie jest” maszyną skończoną. Maszyna stanów skończonych jest modelem mentalnym, który może być przydatny do zrozumienia czegoś, jeśli można uznać to za jedno.

Zazwyczaj model skończonej maszyny stanów stosuje się do rzeczy z małą liczbą stanów, takich jak gramatyka regularna lub sekwencer instrukcji komputera.

Aby odpowiedzieć bezpośrednio na twoje pytanie: prawie na pewno nie. Wydaje się, że nie ma formalnej teorii matematycznej dla OOP w taki sposób, że rachunek lambda i / lub logika kombinacyjna leżą u podstaw programowania funkcjonalnego, a Maszyny Turinga prawie zwykłym starym programowaniem imperatywnym.

Zobacz to pytanie dotyczące przepełnienia stosu, aby uzyskać więcej.

Domyślam się, że brak podstawowej teorii matematycznej powoduje, że każdy wie, czym jest „przedmiot”, gdy go widzi, ale nikt nie widzi „przedmiotów” tak samo jak wszyscy inni.

Nie, praktycznie nie. Maszyna stanów skończonych zwykle zapamiętuje tylko jeden element danych: jego aktualny stan.

Typowym zastosowaniem FSM jest leksykowanie lub parsowanie. Na przykład, gdy wykonujemy leksykację, (normalnie) dość łatwo jest zakodować akcje dla każdego możliwego wejścia pod względem stanu bieżącego i wartości wejścia.

Na przykład możemy mieć stan NUMER, w którym czytamy cyfry liczby. Jeśli następnym znakiem, który czytamy, jest cyfra, pozostajemy w stanie NUMERYCZNYM. Jeśli jest to spacja lub tabulator, zwracamy cyfry, a następnie przechodzimy do stanu WHITE_SPACE lub czegoś w tej kolejności.

Teraz z pewnością jest prawdą, że w typowym FSM (szczególnie takim, który jest zaimplementowany w oprogramowaniu) otrzymujemy bity, które technicznie nie pasują do FSM zmieszanego z samym FSM. Na przykład, gdy czytamy cyfry liczby, często zapisujesz pozycję pierwszej cyfry, więc kiedy dojdziesz do końca, możesz łatwo obliczyć wartość liczby.

Sam FSM ma pewne ograniczenia - nie ma mechanizmu liczenia. Rozważmy na przykład język, w którym „/ ” zaczyna się od komentarza, a „ /”, aby zakończyć komentarz. Lexer prawdopodobnie miałby stan KOMENTARZA, do którego wszedł, gdy zobaczył token „/ ”. W tym momencie nie ma możliwości (poza dodaniem kolejnego stanu, takiego jak COMMENT2) wykrycia kolejnego „/ ” i uświadomienia sobie, że zajmuje się zagnieżdżonym komentarzem. Zamiast tego w stanie komentarza rozpozna, */że nakazuje mu pozostawienie komentarza, a wszystko inne pozostawia go w stanie komentarza.

Jak już wspomniano, na pewno mógłby obejmować stan comment2 dla zagnieżdżonego komentarz - i tym, że stan COMMENT3, i tak dalej. W pewnym momencie będziesz jednak miał dość dodawania kolejnych stanów, a to określi maksymalną głębokość zagnieżdżania, na jaką zezwalasz na komentarze. W przypadku innej formy parsera (tj. Nie jest to maszyna stanu czystego, ale coś, co ma trochę pamięci, aby mogła się liczyć), możesz po prostu bezpośrednio śledzić swoją głębokość zagnieżdżania, dzięki czemu pozostajesz w stanie KOMENTARZ, aż dojdziesz do tokena komentarza, który równoważy pierwszy, więc licznik wraca do 0 i wychodzisz ze stanu KOMENTARZ.

Jednak, jak powiedziałem, po dodaniu takiego licznika nie ma już naprawdę FSM. Jednocześnie jest on dość blisko - a konkretnie wystarczająco blisko, aby można było zasymulować licznik, dodając więcej stanów.

Jednak w typowym przypadku, gdy ktoś mówi o implementacji FSM w oprogramowaniu, utrzyma go w miarę „czystym”. W szczególności oprogramowanie zareaguje na bieżący sygnał wejściowy wyłącznie na podstawie aktualnego stanu i wartości samego wejścia. Jeśli reakcja zależy od wielu innych czynników, zwykle nie nazywają tego maszyną stanu (przynajmniej jeśli wiedzą, o czym mówią).

Nie sądzę, aby zaakceptowana odpowiedź była całkowicie poprawna.

Nie można modelować dowolnego programu napisanego w języku Turing Complete, niezależnie od tego, czy jest on zorientowany obiektowo, czy też nie, jako skończona maszyna stanowa. Prawie wszystkie współczesne języki komputerowe, takie jak Java, C ++ lub Smalltalk, są Turing Complete.

Na przykład nie można utworzyć maszyny stanów skończonych do rozpoznawania sekwencji obiektów, w których występuje n wystąpień jednego obiektu, a następnie n wystąpień innego obiektu, ponieważ maszyny stanów skończonych nie są w stanie zapisać n zmiennej. Mogą tylko odczytać dane wejściowe i przejść do stanu.