Dlaczego behawioralne podtypowanie jest nierozstrzygalne?

Prace Liskova w tym obszarze koncentrowały się na podtypach behawioralnych, które oprócz bezpieczeństwa systemu typów omawianego w tym artykule wymagają również, aby podtypy zachowywały wszystkie niezmienniki gwarantowane przez nadtypy w niektórych kontraktach [3]. Ta definicja podtypu jest na ogół nierozstrzygalna, więc nie może być zweryfikowana przez moduł sprawdzania typu.

Od: http://www.wikiwand.com/en/Subtyping#/Function_types

type-systems subtypes

— q126y
źródło

Odpowiedzi:

Niech umowa działania otypu Tbędzie polegała na tym, że zatrzymuje się ona dla wszystkich danych wejściowych. Teraz zdecyduj, czy działanie opodtypu S <: Tspełnia tę umowę: właśnie rozwiązałeś problem zatrzymania .

Mówiąc bardziej ogólnie, S::omusi obliczyć tę samą funkcję, T::ojakby S <: T. Decyzja, czy dwa programy obliczają tę samą funkcję, nazywa się Problemem Funkcji i jest równoważna rozwiązaniu problemu Zatrzymania.

Ogólnie rzecz biorąc, statyczne podejmowanie decyzji o wszelkich nietrywialnych właściwościach środowiska wykonawczego jest prawie zawsze równoważne Problemowi Zatrzymania.

— Jörg W Mittag
źródło

Ta ostatnia linia to przybija. W chwili, gdy chcesz udowodnić właściwość dotyczącą tego, co program może zrobić w otoczeniu behawioralnym, wkraczasz w niemożliwe. Powodem działania systemów typów i narzędzi analizy statycznej jest to, że traktują one inny język (typów programu, zakresu zmiennych w programie itd.), A nie właściwości bezpośredniego działania programu .

— Benjamin Gruenbaum,

@BenjaminGruenbaum Jorg odpowiedź i twój komentarz są poprawne, ale jest w tym subtelność, którą chciałbym wyjaśnić. Często można udowodnić właściwość określonego programu. Po prostu nie ma algorytmu, którego można by ślepo przestrzegać, który działałby dla wszystkich programów. Rozważ tę metodę napisaną w Javie:

BigInteger sum(int[] arr) { BigInteger sum = BigInteger.ZERO; for (int x: arr) sum = sum.add(BigInteger.valueOf(x)); return sum; }

Nietrudno udowodnić, że konkretna metoda zawsze zwraca sumę elementów tablicy liczb całkowitych i nie robi nic więcej (pod warunkiem, że argument nie jest pusty).

— Doval,

A kiedy nie jest to równoważne z problemem zatrzymania, często jest jeszcze gorzej . Ponieważ niemożliwe nie było już wystarczająco trudne.

— user2357112 obsługuje Monica

Lub umieścić punkt Doval inny sposób (tępy), właśnie dlatego non kompletne języki -Turing są interesujące i użyteczne. Często nie potrzebujesz kompletności Turinga (z pewnością na poziomie modułu) do prawdziwej pracy.

— Leushenko,

@Doval: Bardzo dobra uwaga. Chociaż prawdą jest, że nie możesz mieć algorytmu potwierdzającego zakończenie i / lub poprawność losowego programu, możliwe jest pisanie programów w taki sposób, aby można było udowodnić ich poprawność.

— Giorgio,

Ponieważ prawie każde pytanie dotyczące zachowania programów jest nierozstrzygalne. Według twierdzenia Rice'a każdy problem decyzyjny formy:

Niektóre programy obliczają funkcje, które mają tę właściwość, inne programy obliczają funkcje, które nie mają tej właściwości. Biorąc pod uwagę program P, czy funkcja obliczona przez P ma wyżej wspomnianą właściwość, czy nie?

jest nierozstrzygalny. Na przykład nie zawsze można odróżnić kod, który oblicza kwadrat danych wejściowych od kodu, który tego nie robi. Chociaż w prostych przypadkach często można udowodnić, że funkcja to robi lub nie, nie ma ogólnej procedury, która działałaby dla wszystkich programów.

Prawie każdy interesujący niezmiennik behawioralny podlega twierdzeniu Rice'a, ponieważ te stwierdzenia rzadko (jeśli w ogóle) mówią o tym, jak ta metoda wygląda wewnętrznie, tylko o tym, co zwraca i jakie efekty uboczne wywołuje w odpowiedzi na pewne dane wejściowe.

Możesz wyjaśnić trochę: Nie chodzi o to, że pojedynczy program, bez względu na to, jak patologiczny, byłby w stanie oprzeć się wszelkim analizom, ale że dla każdej analizy istnieje przynajmniej jeden program, którego nie można odpowiednio skategoryzować.

— Nathan Tuggy,