I compilatori possono controllare se certi assiomi sono validi per un tipo definito dall'utente?

3

Supponiamo che il seguente tipo sia definito (la sintassi C ++, può essere concettualmente applicata a qualsiasi linguaggio tipizzato staticamente.)

class T {
   int val;
   friend bool operator<(const T& lhs, const T& rhs) {
      return lhs.val < rhs.val;
   }
   // Ideally, if we should make them "friends"
   // Also, this doesn't make them belong to the type itself as they're not member functions
   friend bool operator>=(const T& lhs, const T& rhs) {
      return !(lhs < rhs);
   }
   // Also the following implementation is interesting
   friend bool operator>=(const T& lhs, const T& rhs) {
      return lsh.val >= rhs.val;
   }
};

Quindi, il compilatore può sicuramente verificare se T supporta l'operatore < oppure operator > =, può solo cercare la dichiarazione.
Questo diventa più complicato se questi fossero definiti come "amici" invece di funzioni membro, ma può essere fatto per quanto mi riguarda.

Tuttavia, il compilatore può controllare se l'"assioma comune di ordinamento" è valido? (Come in è possibile verificarlo in tutti gli scenari? Non importa se questo sarebbe conforme allo standard.) Dire:
non (a < b) == a > = b

Dovremmo definirne uno in termini di altro, è sicuramente possibile in questo particolare scenario, ma questo non è naturalmente l'unico assioma da controllare, per quanto riguarda:
(a > b) = > (b < a)
e inoltre non è necessario (sfortunatamente) definire il nostro comportamento in termini di qualcosa che è già stato definito. E a volte non sarebbe nemmeno possibile.

Quindi, se il compilatore può controllare se certi assiomi valgono, come? Generare valori casuali da determinati intervalli? È possibile ideare e verificare la correttezza di tali intervalli?

Questo è principalmente legato ai concetti C ++ che, a differenza dei concetti C ++, dovrebbe anche essere in grado di "supportare gli assiomi", qualunque cosa significhi, non riesco a vedere un modo chiaro su come possono essere applicati. O il creatore del tipo deve dichiarare quali assiomi obbedisce alla sua classe? C ++ ha abbandonato le "mappe concettuali" per quanto ne so.

    
posta ScarletAmaranth 27.09.2013 - 13:31
fonte

3 risposte

5

However, can the compiler check whether the "common axiom of sorts" hold?

No. Quello sarebbe un compilatore non conforme. Non c'è nulla nello standard che dice che, ad esempio, operator>= deve essere l'inversa booleano di operator< . Va perfettamente allo standard se un programmatore vuole definire tutti gli operatori di confronto come return 42; . Che questa non è una buona idea è una domanda diversa.

Il compilatore ha già abbastanza tempo per la complessità di C ++. Non è una buona idea aggiungere un task Sysiphean a quel carico. Il tuo 'testing of axioms' è in generale un problema indecidibile.

    
risposta data 27.09.2013 - 14:32
fonte
0

No. Dal momento che gli operatori possono detenere codice arbitrario, è impossibile persino determinare se termineranno in tutti i casi. Per maggiori informazioni su questo, cerca il problema della fermata.

    
risposta data 28.09.2013 - 13:05
fonte
0

(Nota Questa risposta è basata sull'esperienza in c #. Non l'ho mai provato in c / c ++)

Non penso che le pre- o postcodizioni (come l'ordinamento) possano essere controllate a tutti i costi.

Ma un compilatore (o un compilatore-postelaboratore) può inserire automaticamente il codice per eseguire runtimechecks per pre- e post-condizioni. (Questo è il modo in cui è fatto in contratti di codice c # che fanno sì che i contratti vengano applicati anche in anche funzioni virtuali sovrascritte.

Elenchi di Wikipedia sotto Design_by_contract alcune librerie c / c ++ per supportare i contratti.

UML usa OCL = Object_Constraint_Language per questo.

    
risposta data 28.09.2013 - 18:25
fonte

Leggi altre domande sui tag