2013-03-27 4 views
9
  • codice rottofallacia informale provoca overflow dello stack

    public static partial class LogicExtensions { 
        public static bool Implies<T>(this T premise, T conclusion) { 
         return conclusion.Infers(premise); 
        } 
    
        public static bool Infers<T>(this T premise, T conclusion) { 
         return premise.Implies(conclusion); 
        } 
    } 
    

Il codice di cui sopra è in attesa di esprimere:

La conclusione deduce la premessa a causa della premessa implica la conclusione.

La premessa implica la conclusione a causa della conclusione ne deduce la premessa.

Sarebbe circular reasoning e sicuramente causerà l'overflow dello stack. Ho poi riprogettare come segue:

  • codice di lavoro

    public delegate bool Paradox<T>(T premise, T conclusion, Paradox<T> predicate=null); 
    
    public static partial class LogicExtensions { 
        public static bool Implies<T>(this T premise, T conclusion, Paradox<T> predicate=null) { 
         if(null==predicate) 
          return conclusion.Infers(premise, Implies); 
    
         if(Infers!=predicate) 
          return predicate(premise, conclusion); 
    
         return LogicExtensions.Implies(conclusion as IConvertible, premise as IConvertible); 
        } 
    
        public static bool Infers<T>(this T premise, T conclusion, Paradox<T> predicate=null) { 
         if(null==predicate) 
          return premise.Implies(conclusion, Infers); 
    
         if(Implies!=predicate) 
          return predicate(premise, conclusion); 
    
         return LogicExtensions.Implies(conclusion as IConvertible, premise as IConvertible); 
        } 
    
        static bool Implies<T>(T premise, T conclusion) where T: IConvertible { 
         var x=premise.ToUInt64(null); 
         return x==(x&conclusion.ToUInt64(null)); 
        } 
    } 
    

Ma questo significa:

  1. Fallisce sulla logica corretta che non si può andare senza Paradox<T> che Inizialmente ho chiamato Predicate<T> ma è in conflitto con System.Predicate<T>.

  2. È difettoso che T deve implementare IConvertable a differenza del codice precedente.

Per essere chiari, io sto cercando di rendere il codice non solo funziona, ma rappresentano anche come formule logiche che posso ulteriormente riutilizzarla per ragionare su logica, senza un vincolo di T attrezzi IConvertable. C'è un modo per correggere la logica e liberarsi del design difettoso?

+11

[* Paradox *] (http://www.veterangamers.co.uk/blog/wp-content/uploads/2011/04/paradox.jpg) ... –

+4

è al questo punto probabilmente passerei a Prolog. – spender

+0

@spender: È tanto tempo fa, che ho scritto una volta in Prolog. Forse una risposta porting da Prolog per risolvere questo? –

risposta

9

Non è molto chiaro dalla domanda che cosa stai cercando di fare. Stai cercando di esprimere alcuni predicati logici in C#? Stai cercando di scrivere un codice che ragionerà sulla logica? Stai cercando di rappresentare formule logiche?

Paradossi. Quando si parla di paradossi nei calcoli, potrebbe essere utile leggere sul calcolo lambda e sul paradosso di Russel (here is a nice article). Il Lambda Calculus è essenzialmente un semplice linguaggio di programmazione funzionale (immagina C# con funzioni e applicazioni lambda, ma nient'altro).

E 'stato sviluppato come un sistema per la fondamenti della matematica (prima che i computer sono stati inventati), ma questo non ha davvero funzionato perché sono stati in grado di scrivere i calcoli ricorsive che non aveva senso (si veda l'articolo per i dettagli), ma è possibile scrivere un calcolo che valuta come segue (in C# notazione):

r(r) = not(r(r)) = not(not(r(r))) 

... e dal momento che non v'è alcuna x = r(r) tale che x = not(x), il modello non ha senso come fondamento della matematica. Ma è utile come modello di linguaggi di programmazione in cui è possibile scrivere calcoli ricorsivi, sebbene non possano mai terminare.

Rappresentare la logica. Se si desidera rappresentare le formule logiche nel proprio programma, è probabile che si desideri separare la rappresentazione della formula dal ragionamento . Questo è meglio fatto in linguaggi funzionali (come F #), ma puoi farlo anche in C# (solo con una maggiore digitazione). Il # Rappresentazione F di una formula sarebbe qualcosa di simile:

type Formula = 
    | Variable of string 
    | Negation of Formula 
    | Implies of Formula * Formula 

L'idea è che una formula o è una variabile (denominata), o una negazione di un'altra formula o un'implicazione in cui si formula implica l'altro. In C#, puoi rappresentare la stessa cosa di una gerarchia di classi (con Formula come classe base e tre classi derivate.)

Il tuo ragionamento può quindi essere implementato come un metodo che manipola le formule. In F #, questo può essere fatto abbastanza facilmente usando la corrispondenza del modello. In C#, probabilmente dovrai usare test di tipo per scrivere codice che controlli se l'argomento è Variable (poi fai qualcosa ...); se l'argomento è Negation (poi fare qualcosa ...), ecc

2

Dropping IConvertible

Cominciamo con la 'parte facile': far cadere il IConvertible. Il motivo per cui ne hai bisogno è perché vuoi che questo codice funzioni su tutti i tipi, il che significa che non puoi sempre influenzare il fatto che abbia un determinato membro (Implies). Ciò che si vorrebbe fare è quello che chiamano in C++: modello di specializzazione, ma purtroppo non è disponibile in C# (ancora?):

static bool Implies<T>(T premise, T conclusion) where T : IConvertible 
    { 
     var x = premise.ToUInt64(null); 
     return x == (x & conclusion.ToUInt64(null)); 
    } 

    static bool Implies<T>(T premise, T conclusion) where T : Foobar 
    { 
    // other fancy logic 
    } 

// and so on 

Il modo più semplice per risolvere questo è quello di utilizzare multimethods. È possibile utilizzare la parola 'dinamica' per questo:

public partial class Implications 
{ 
    internal static bool CheckImplies<T>(T lhs, T rhs) 
    { 
     return Implies((dynamic)lhs, (dynamic)rhs); 
    } 

    public static bool Implies(int lhs, int rhs) 
    { 
     return lhs == (lhs & rhs); 
    } 
    // your other implies thingies implement this same partial class 
} 

public static partial class LogicExtensions 
{ 
    public static bool Implies<T>(this T premise, T conclusion, Paradox<T> predicate = null) 
    { 
     if (null == predicate) 
      return conclusion.Infers(premise, Implies); 

     if (Infers != predicate) 
      return predicate(premise, conclusion); 

     return Implications.CheckImplies(premise, conclusion); 
    } 

    public static bool Infers<T>(this T premise, T conclusion, Paradox<T> predicate = null) 
    { 
     if (null == predicate) 
      return premise.Implies(conclusion, Infers); 

     if (Implies != predicate) 
      return predicate(premise, conclusion); 

     return Implications.CheckImplies(premise, conclusion); 
    } 
} 

E se si dispone di un metodo di 'terza', si può semplicemente chiamare

Sono stato alla ricerca di un paio di minuti al strana definizione ricorsiva e per me non ha senso ... se hai comunque un terzo metodo di aiuto, perché non chiamarlo direttamente? :-)

public static bool Implies<T>(this T premise, T conclusion) 
    { 
     return Implications.CheckImplies(premise, conclusion); 
    } 

    public static bool Infers<T>(this T premise, T conclusion) 
    { 
     return Implications.CheckImplies(conclusion, premise); 
    } 

Il non (non (T)) problema

Mentre quanto sopra non ha molto senso per me, trovo perfettamente ragionevole usare il sistema di tipi e la lingua per aiutarti un po '. Beh, sicuramente si può fare questo e questo è come l'avrei fatto ... :-)

Diamo introdurre un 'non' classe con un generico:

public class Not<T> 
{ 
    public Not(T val) 
    { 
     this.not = val; 
    } 
    internal T not; 
} 

Se abbiamo un non> situazione qui, vogliamo dare - altrimenti, vogliamo usare direttamente.Beh, possiamo farlo abbastanza facile con alcune estensioni:

public static T Optimize<T>(this Not<Not<T>> var) 
    { 
     return Optimize(var.not.not); 
    } 

    public static T Optimize<T>(this T var) 
    { 
     return var; 
    } 

Per provarlo, si può fare una cosa simile:

var val = new Not<Not<int>>(new Not<int>(2)); 
var result = val.Optimize(); 

Questo funziona, perché la risoluzione di sovraccarico prenderà la chiamata Optimize corretta, che garantisce l'ottimizzazione di Non >>>> nel valore T e così via.

Funziona anche, perché avvolgiamo il "Not" in una classe wrapper e quindi usiamo il sistema di tipi a nostro vantaggio.

Tornando al problema originale

Invece di valutare direttamente 'Implica' e 'Inferi', perché non utilizzare un oggetto temporaneo per fare il vostro lavoro il male. È possibile utilizzare l'overloading dell'operatore (conversione implicita per la precisione) per specificare il modo in cui Implies e Infers sono correlati. L'unico problema è che ha i suoi limiti con i metodi di estensione.

L'overloading dell'operatore C# seleziona quindi il metodo di corrispondenza migliore. Nel primo caso questa sarà la corrispondenza esatta, nel secondo caso il metodo verrà convertito implicitamente e in seguito verrà chiamato Evaluate. In altre parole, non impilerà l'overflow, semplicemente perché farà la sua valutazione pigra. Pronto per il codice? :-)

public class Implies<T> 
{ 
    public Implies(T premise, T conclusion) 
    { 
     this.premise = premise; 
     this.conclusion = conclusion; 
    } 

    public T premise; 
    public T conclusion; 

    public static implicit operator Infers<T>(Implies<T> src) 
    { 
     return new Infers<T>(src.conclusion, src.premise); 
    } 
} 

public class Infers<T> 
{ 
    public Infers(T premise, T conclusion) 
    { 
     this.premise = premise; 
     this.conclusion = conclusion; 
    } 

    public T premise; 
    public T conclusion; 

    public static implicit operator Implies<T>(Infers<T> src) 
    { 
     return new Implies<T>(src.conclusion, src.premise); 
    } 
} 

public static partial class LogicExtensions 
{ 
    public static Implies<T> Implies<T>(this T premise, T conclusion) 
    { 
     return new Implies<T>(premise, conclusion); 
    } 

    public static Infers<T> Infers<T>(this T premise, T conclusion) 
    { 
     return new Infers<T>(premise, conclusion); 
    } 
} 

public class Foo 
{ 
    // The things you wish to implement :-) 
    public static bool Evaluate(Implies<int> impl) 
    { 
     return impl.premise == (impl.conclusion & impl.premise); 
    } 

    static void Main(string[] args) 
    { 
     Implies<int> impl= 0.Implies(2); // will be called directly 
     Infers<int> impl2 = 0.Infers(2); // will be converted 

     Console.WriteLine("Res: {0} {1}", Evaluate(impl), Evaluate(impl2)); 

     Console.ReadLine(); 
    } 
} 
+0

Ho appena letto, e non ancora un test. Sembra buono, ma molto simile a una soluzione alternativa, ho ragione? –

+1

@KenKin Beh sì e no ... Sì, nel senso che la specializzazione generica non è semplicemente supportata, quindi è necessario qualche soluzione ... che è un tipo di aiuto che aiuta un po 'il compilatore ad uscire. No, nel senso che non valuto direttamente i valori, ma uso una classe helper per posticipare le operazioni. – atlaste