2013-03-27 2 views
9
  • Gebrochene CodeInformal Irrtum verursacht Stapelüberlauf

    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); 
        } 
    } 
    

Der obige Code erwartet auszudrücken:

Die Schlussfolgerung der Prämisse wegen der Prämisse folgert bedeutet den Abschluss.

Die Prämisse impliziert die Schlussfolgerung aufgrund der Schlussfolgerung die Prämisse.

Es wäre circular reasoning, und wird definitiv Stapelüberlauf verursachen. Ich Redesign es dann wie folgt:

  • Code Arbeiten

    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)); 
        } 
    } 
    

Aber das bedeutet:

  1. Es ist auf die richtige Logik nicht, dass es nicht ohne Paradox<T> gehen die Ich nannte ursprünglich Predicate<T>, aber ist Konflikt mit System.Predicate<T>.

  2. Es ist defekt, dass TIConvertable im Gegensatz zu dem Code-Former implementieren muss.

Um klar zu sein, ich versuche, den Code nicht nur funktioniert, sondern auch, wie logische Formeln darstellen zu machen, dass ich es weiter wiederverwenden kann über Logik ohne Einschränkung von TIConvertable Arbeitsgeräte zur Vernunft. Gibt es einen Weg, die Logik zu korrigieren und das fehlerhafte Design loszuwerden?

+11

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

+4

Es ist bei diesen Punkt würde ich wahrscheinlich zu Prolog wechseln. – spender

+0

@spender: Es ist lange her, ich habe einmal in Prolog geschrieben. Vielleicht eine Antwort von Prolog, um das Problem zu lösen? –

Antwort

9

Es ist nicht sehr klar aus Ihrer Frage, was Sie versuchen zu tun. Versuchen Sie einige logische Prädikate in C# auszudrücken? Versuchen Sie, Code zu schreiben, der logisch logisch ist? Versuchen Sie, logische Formeln darzustellen?

Paradoxe. Wenn über Paradoxien in Berechnungen gesprochen wird, könnte es gut sein, über Lambda-Kalkül und Russels Paradoxon zu lesen (here is a nice article). Lambda-Kalkül ist im Wesentlichen eine einfache funktionale Programmiersprache (stellen Sie sich C# mit Lambda-Funktionen und -Anwendung vor, aber sonst nichts).

Es wurde zuerst als ein System für das Fundament der Mathematik entwickelt (vor dem Computer erfunden wurde), aber dies nicht wirklich arbeiten, weil Sie in der Lage waren rekursive Berechnungen zu schreiben, die keinen Sinn ergeben (siehe die Artikel Details), aber Sie können eine Berechnung schreiben, bewertet als (in C# Schreibweise folgt):

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

... und da es keine x = r(r) so dass x = not(x) ist, gilt das Modell nicht Sinn als Fundament der Mathematik machen. Aber es ist nützlich als ein Modell von Programmiersprachen, wo Sie rekursive Berechnungen schreiben können - obwohl sie niemals enden.

Logik darstellen. Wenn Sie logische Formeln in Ihrem Programm darstellen möchten, dann möchten Sie wahrscheinlich die Darstellung der Formel aus der Argumentation trennen. Dies ist am besten in funktionalen Sprachen (wie F #), aber Sie können es auch in C# tun (nur mit mehr Eingabe). Die F # Darstellung einer Formel wäre so etwas wie:

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

Die Idee ist, dass eine Formel ist entweder eine Variable (genannt) oder eine Negation einer anderen Formel oder eine Implikation, wo eine Formel eines anderes impliziert. In C# können Sie dasselbe wie eine Klassenhierarchie (mit Formula als Basisklasse und drei abgeleiteten Klassen) darstellen.

Ihre Argumentation kann dann als eine Methode implementiert werden, die Formeln bearbeitet In F # kann dies recht einfach mithilfe von Musterabgleich durchgeführt werden. In C# müssen Sie wahrscheinlich Typprüfungen verwenden, um Code zu schreiben, der prüft, ob das Argument Variable ist (dann tun Sie etwas ...); wenn das Argument Negation ist (dann etwas ...) usw.

2

Dropping IConvertible

Beginnen wir mit dem 'easy Teil' starten: IConvertible fallen. Der Grund, warum Sie es brauchen, ist, dass Sie möchten, dass dieser Code auf allen Arten funktioniert, was bedeutet, dass Sie nicht immer beeinflussen können, dass er ein bestimmtes Mitglied hat (Implies). Was Sie möchten, dass tun, was sie in C++ rufen: Template-Spezialisierung, aber leider nicht verfügbar ist in C# (noch?):

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 

Der einfachste Weg, dies durch die Verwendung Multimethoden zu lösen ist.

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); 
    } 
} 

Und wenn Sie eine ‚dritte‘ Methode haben, können Sie einfach nennen es

Ich habe in der ein paar Minuten gesucht: Sie können das ‚dynamische‘ Schlüsselwort für diesen Einsatz seltsam rekursive Definition und es ergibt keinen Sinn für mich ... Wenn Sie eine dritte Hilfsmethode sowieso haben, warum nicht einfach direkt anrufen? :-)

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); 
    } 

Die nicht (nicht (T)) Problem

Während die oben nicht viel Sinn für mich habe, finde ich es durchaus sinnvoll, die Art System und die Sprache zu verwenden um dir ein bisschen zu helfen. Nun, sicher können Sie das tun und das ist, wie ich das tun würde ... :-)

Lassen Sie uns einen einführen ‚Nicht‘ Klasse mit einem generic:

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

Wenn wir eine Nicht> Situation haben hier wollen wir geben - sonst wollen wir direkt verwenden.Nun, wir können mit einigen Erweiterungen, die ganz einfach tun:

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; 
    } 

es zu testen, können Sie eine ähnliche Sache tun:

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

Dies funktioniert, weil die Überladungsauflösung den richtigen Optimize Anruf anzunehmen wird, was sicherstellt, dass Sie das Nicht >>>> in den T-Wert optimieren und so weiter.

Es funktioniert auch, weil wir das 'Not' in einer Wrapper-Klasse umhüllen und dann das Typsystem zu unserem Vorteil verwenden.

Gehen wir zurück zum ursprünglichen Problem

Statt direkt die Bewertung ‚Impliziert‘ und ‚folgert‘, warum nicht ein temporäres Objekt verwenden, um Ihre bösen Arbeit zu tun. Sie können das Überladen von Operatoren (implizite Konvertierung, um genau zu sein) verwenden, um anzugeben, wie sich Imples und Infers verhalten. Der einzige Haken ist, dass es mit Erweiterungsmethoden Grenzen hat.

C# -Operatorüberladung wählt dann die am besten passende Methode aus. Im ersten Fall ist dies die exakte Übereinstimmung, im zweiten Fall wird die Methode implizit konvertiert und anschließend wird Evaluate aufgerufen. Mit anderen Worten, es wird keinen Überlauf stacken, nur weil es seine Bewertung faul macht. Bereit für den Code? :-)

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

Ich habe gerade gelesen, und noch kein Test. Sieht gut aus, aber ähnlich wie ein Workaround, habe ich Recht? –

+1

@KenKin Nun ja und nein ... Ja in dem Sinne, dass generische Spezialisierung wird einfach nicht unterstützt, so dass Sie eine Workaround benötigen ... was ist ein Hilfstyp, der den Compiler ein wenig hilft. Nein in dem Sinne, dass ich Werte nicht direkt auswerte, sondern eine Hilfsklasse verwende, um Operationen zu verzögern. – atlaste