Liskov's work in this area focused on behavioral subtyping, which besides the type system safety discussed in this article also requires that subtypes preserve all invariants guaranteed by the supertypes in some contract.[3] This definition of subtyping is generally undecidable, so it cannot be verified by a type checker.
Da: link
Consenti al contratto di esecuzione o di Type T di essere fermo per tutti gli input. Ora decidi se l'operazione o del sottotipo S <: T soddisfa quel contratto: hai appena risolto il problema di interruzione .
Più in generale, S::o deve calcolare la stessa funzione di T::o se S <: T . Decidere se due programmi calcolano la stessa funzione è chiamato il Problema di funzione ed equivale a risolvere il problema di interruzione.
In generale, decidere staticamente qualsiasi proprietà runtime non banale è quasi sempre equivalente al problema di interruzione.
Perché quasi ogni domanda sul comportamento dei programmi è indecidibile. Per teorema di Rice , qualsiasi problema decisionale del modulo:
Some programs compute functions that have this property, other programs compute functions that don't have this property. Given a program P, does the function computed by P have the aforementioned property or not?
è indecidibile. Ad esempio, non è sempre possibile distinguere il codice che calcola il quadrato di un input dal codice che non lo fa. Sebbene in casi semplici, è spesso possibile dimostrare che una funzione lo fa o non lo fa, non esiste una procedura generale che funzioni per tutti i programmi.
Quasi ogni invariante comportamentale interessante cade sotto il teorema di Rice, dal momento che quelle dichiarazioni raramente (se mai) parlano di come il metodo appare internamente, solo ciò che ritorna e quali effetti collaterali provoca in risposta a determinati input.
Leggi altre domande sui tag type-systems subtypes