Czy środowisko wykonawcze może wykryć nieskończoną pętlę?

Czy środowisko wykonawcze może wykryć nieskończone pętle, a następnie zatrzymać powiązany proces, czy też wdrożenie takiej logiki byłoby równoznaczne z rozwiązaniem problemu zatrzymania?

Na potrzeby tego pytania definiuję „nieskończoną pętlę”, która oznacza serię instrukcji i powiązanych początkowych danych stosu / sterty, które po uruchomieniu zwracają proces do dokładnie tego samego stanu (w tym danych), w jakim był wcześniej inicjowanie nieskończonej pętli. (Innymi słowy, program generujący nieskończenie długie dziesiętne rozwinięcie liczby pi nie jest „utknięty” w „nieskończonej pętli”, ponieważ przy każdej iteracji ma więcej cyfr pi gdzieś w powiązanej pamięci.)

(Przeniesiony z /programming//q/16250472/1858225 )

To może być teoretycznie możliwe dla środowiska wykonawczego w celu sprawdzenia takich pętli stosując następującą procedurę:

Po każdym wykonaniu instrukcji środowisko wykonawcze wykona pełny obraz stanu uruchomionego procesu (tj. Całą związaną z nim pamięć, w tym rejestry, komputer, stos, stertę i globale), zapisze gdzieś ten obraz, a następnie sprawdzi sprawdź, czy pasuje do któregokolwiek z wcześniej zapisanych obrazów dla tego procesu. Jeśli istnieje dopasowanie, proces utknie w nieskończonej pętli. W przeciwnym razie wykonywana jest następna instrukcja i proces jest powtarzany.

W rzeczywistości, zamiast wykonywania tej kontroli po każdej instrukcji, środowisko wykonawcze może po prostu okresowo wstrzymywać proces i tworzyć stan zapisu. Jeśli proces utknie w nieskończonej pętli obejmującej n stanów, to po co najwyżej n sprawdzeniach zostanie zaobserwowany duplikat.

Należy oczywiście pamiętać, że nie jest to rozwiązanie problemu zatrzymania; rozróżnienie omówiono tutaj .

Ale taka cecha byłaby ogromnym marnotrawstwem zasobów ; ciągłe wstrzymywanie procesu w celu zapisania całej pamięci z nim związanej spowolniłoby go ogromnie i bardzo szybko zużyło ogromną ilość pamięci. (Chociaż po pewnym czasie stare obrazy mogłyby zostać usunięte, ryzykowne byłoby ograniczenie całkowitej liczby zdjęć, które można zapisać, ponieważ duża nieskończona pętla - tj. Jedna z wieloma stanami - może nie zostać złapana, jeśli jest ich za mało stanów przechowywanych w pamięci.) Ponadto funkcja ta nie przyniosłaby tak wiele korzyści, ponieważ jej zdolność do wychwytywania błędów byłaby bardzo ograniczona i ponieważ stosunkowo proste jest znalezienie nieskończonych pętli za pomocą innych metod debugowania (takich jak po prostu przejście przez kod i rozpoznawanie błędu logicznego).

Dlatego wątpię, aby takie środowisko wykonawcze istniało lub że kiedykolwiek będzie istnieć, chyba że ktoś zaprogramuje je tylko dla kopnięć. (Kusi mnie to teraz.)

Załóżmy, że program nie wchodzi w interakcje ze światem zewnętrznym, więc naprawdę jest możliwe podsumowanie całego stanu programu. (Oznacza to, że przynajmniej nie wprowadza żadnych danych wejściowych.) Ponadto załóżmy, że program działa w jakimś deterministycznym środowisku, dzięki czemu każdy stan ma unikatowego następcę, co oznacza, że ​​środowisko wykonawcze albo nie jest wątkowe, albo że wątki można deterministycznie zredukować do sekwencji.

Przy tych wysoce nieprawdopodobnych, ale teoretycznie nieograniczających założeniach, możemy powielić program i uruchomić go w dwóch osobnych środowiskach wykonawczych; każdy wykona dokładnie to samo obliczenie.

Zróbmy to. Uruchomimy go raz w środowisku uruchomieniowym Tortoise, a jednocześnie uruchomimy w środowisku uruchomieniowym Hare. Jednak zapewniamy, że środowisko uruchomieniowe Hare będzie działać dokładnie dwa razy szybciej; za każdym razem, gdy środowisko wykonawcze Tortoise wykonuje jeden krok, środowisko wykonawcze Hare wykonuje dwa kroki.

$n$$p$$kn$$k$$kn\ge p$

Całkowity koszt testu to jeden dodatkowy stan i jedno porównanie stanu na krok i zakończy się nie więcej niż trzykrotnie niż liczba kroków, jakie musi wykonać program, aby zakończyć swoją pierwszą pętlę. (Jeden raz w Żółwiu i dwa razy w Zającu, w sumie trzy razy.)

Jak sugerują używane przeze mnie terminy, jest to tylko słynny algorytm wykrywania cyklu Żółwia i Zająca Roberta Floyda .

Właśnie gdy miałem zasugerować algorytm wykrywania cyklu Floyda, post Rici mnie pobił. Jednak całość można uczynić bardziej praktyczną poprzez przyspieszenie porównań pełnych stanów.

Wąskim gardłem proponowanego algorytmu byłoby porównywanie stanu pełnego. Te porównania zwykle się nie kończą, ale kończą wcześnie - przy pierwszej różnicy. Jedną z optymalizacji jest zapamiętanie, gdzie wystąpiły różnice w przeszłości i sprawdzenie najpierw tych części stanu. Na przykład prowadź listę lokalizacji i przejrzyj ją przed wykonaniem pełnego porównania. Gdy lokalizacja z tej listy ujawnia różnicę, zatrzymaj porównanie (z błędem) i przenieś lokalizację na początek listy.

Innym (i potencjalnie bardziej skalowalnym) podejściem jest stosowanie przyrostowego mieszania. Wybierz funkcję pełnego stanu, aby wartości skrótu były łatwe do dostosowania w O (1), gdy zmieni się jakaś część stanu. Na przykład weź ważoną sumę słów stanu mod jakąś dużą liczbę pierwszą i połącz z nieważoną sumą mod inną dużą dużą liczbą pierwszą (możesz również wrzucić modułową sumę ważoną kwadratów słów o różnej wadze i module). W ten sposób aktualizacje skrótów zajmą czas O (1) na każdym etapie wykonania, a porównania potrwają czas O (1), aż do uzyskania trafienia. Prawdopodobieństwo fałszywie dodatniego (tzn. Skrótu dopasowania, podczas gdy stany się różnią) jest bardzo niskie, a nawet jeśli tak się stanie, amortyzuje się w stosunku do dużej liczby prawdziwych negatywów (fałszywe negatywy są niemożliwe).

Oczywiście w praktyce wydaje się, że bardziej prawdopodobne jest popadnięcie w takie sytuacje, jak generowanie cyfr liczby pi --- rzeczy ciągle się zmieniają, ale nigdy się nie kończą. Inną częstą możliwością jest to, że nieskończona pętla przydziela pamięć, w którym to przypadku szybko wyczerpuje całą dostępną pamięć.

W moim kursie na temat algorytmów i struktur danych nasz autograder musi zajmować się zgłoszeniami uczniów, które czasami wpadają w nieskończone pętle. Zajmuje się tym 30-sekundowy limit czasu i pewien limit pamięci. Oba są znacznie luźniejsze niż budżety czasu wykonywania i pamięci, które nakładamy w ramach oceniania. Nie jestem pewien, czy wdrożenie prawdziwego wykrywania pętli nieskończonej miałoby sens w tym kontekście, ponieważ takie programy będą działały nieco wolniej (w tym przypadku pomocna może być sprzętowa obsługa haszowania stanu, ale ponownie potrzebne będą dodatkowe zastosowania, aby uzasadnij to). Kiedy uczniowie wiedzą, że upłynął limit czasu ich programu, zwykle mogą znaleźć nieskończoną pętlę.

W aprove wykonuje narzędzie zakończenie analizy statycznej w systemach przepisywania (w tym podklasy programach Haskell), które mogą okazać się non-zakończenia, co daje rzeczywisty przykład non-zakończenia programu. Ta technika jest dość potężna i działa przy użyciu wariantu techniki zwanego zwężaniem .

O ile mi wiadomo, niewiele było pracy nad wykryciem faktycznego braku wypowiedzenia dla języków ogólnych.