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

13

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

Perec
źródło
6
Komputer + oprogramowanie jest maszyną stanową, o ile ogranicza się pamięć, miejsce na dysku i inne rodzaje pamięci (takie jak Internet). Gdy tylko dozwolona jest komunikacja z Internetem lub innym sprzętem zewnętrznym (implikuje nieograniczone miejsce na dane), staje się to bardziej jak maszyna Turinga. Czy słyszałeś kiedyś o wyrażeniu „Turing zakończony”? W każdym razie programy funkcjonalne i programy zorientowane obiektowo kończą jako kod asemblera. Nie znam Haskela (czysto funkcjonalnego języka) / monad, ale musi istnieć ciekawy związek między tym a maszyną Turinga.
Job
Dodając do punktu Jobsa, każda forma niedeterminizmu również przewyższa zarówno modele maszyny stanu, jak i modele maszyny Turinga. W Internecie masz wiele niezsynchronizowanych maszyn, utratę danych przez niedoskonałe połączenia itp. Nawet z prostym jednordzeniowym komputerem masz niedeterministyczne dane wejściowe od użytkownika, ale zwykle ignorujesz ten problem i udajesz, że wszystkie wkład był znany z góry.
Steve314,
@ Steve314: Formalnie deterministyczne automaty są w jednym stanie. Każde wejście prowadzi do nowego stanu. W przypadku niedeterministycznych automatów każde wejście może prowadzić do wielu stanów. Automat niedeterministyczny ze stanami N może być emulowany przez automat deterministyczny ze stanami 2 ^ N.
kevin cline
@cline - W tym przypadku masz całkowitą rację, ale myślę, że miałem na myśli rodzaj współbieżności i zmienność czasową, które występują w maszynie w świecie rzeczywistym - rzeczy takie jak rdzeń działający nieco wolniej, ponieważ jest zbyt gorący , dokładny czas, kiedy dane znajdują się pod głowicą odczytu itp. To wszystko pasuje do niedeterministycznego modelu automatów skończonych, który opisujesz, oczywiście, więc masz absolutną rację - ale liczba stanów będzie niesamowicie duża. Myślę, że mogłem mieć na uwadze ciągłe pomiary, takie jak te temperatury, jako część stanu systemu (nie tylko konsekwencje).
Steve314

Odpowiedzi:

16

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.

Steve314
źródło
1
„Możliwe jest modelowanie pojedynczego obiektu OOP jako skończonej maszyny stanów”. Prawda, ale słaba. To nie jest możliwe". To kwestia definicji. Zadaniem języka programowania jest wyrażenie FSM w uporządkowanym zapisie. OOP jest implementacją FSM z prostszą notacją dla wszystkich różnych stanów.
S.Lott
1
@ S.Lott - Tak, ale większość ludzi nie myśli o obiekcie OOP jako wyrażającym FSM, przynajmniej nie przez większość czasu. Używanie nazwy „automat stanowy” sugeruje, że używasz określonej implementacji, takiej jak wzorzec projektu stanu lub zmienna członkowska state-ID. „Modelowanie jako maszyna stanowa” często implikuje coś o specyfikacji lub dokumentacji projektowej, która różni się od implementacji tej klasy. Dlatego modelowanie klasy jako modelu stanu skończonego subiektywnie oznacza coś innego niż tylko zapewnienie kodu źródłowego dla klasy.
Steve314,
„ludzie nie myślą”. Prawdziwe. I głęboki problem. Wszystkie programy są automatami państwowymi. Mają wiele stanów. Właśnie tego wymaga test „Turing Complete” dla języka programowania. To bardzo, bardzo silna (i absolutna) zasada. Zamiast sugerować, że jest to „możliwe”, bardziej przypomina „konieczne” i „wystarczające”.
S.Lott
1
-1: Automaty zsuwane NIE są tak potężne jak maszyny Turinga.
kevin cline
1
@kevin cline - dzięki - i co ja sobie myślałem !!! Edytowane, aby to skreślić. Pomimo tego, co powiedziałem o formalnych studiach, wiem o tym lepiej i powinienem był wtedy wiedzieć lepiej.
Steve314
5

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.

Mike Dunlavey
źródło
1

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.

Bruce Ediger
źródło
0

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ą).

Jerry Coffin
źródło
„jego obecny stan” może zawierać wiele informacji. FSM może w prosty sposób liczyć, mając stany dla każdej liczby, którą będzie liczyć. Jest skończony (w przeciwieństwie do maszyny Turinga), ale nadal doskonale się liczy. Myślę, że możesz potrzebować lepszego przykładu.
S.Lott
oprogramowanie w twoim telefonie komórkowym to zbiór ohydnie skomplikowanych automatów stanów, które zapamiętują wiele danych i interpretują je zgodnie z aktualnym stanem.
Mawg mówi o przywróceniu Moniki
-2

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.

James Fremen
źródło
to tylko powtarza uwagi przedstawione i wyjaśnione w odpowiedziach opublikowanych 3 lata temu, np. w tym
komara