Informal fallacy causes stack overflow

Question

• Broken code

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

The code above is expecting to express:

The conclusion infers the premise because of the premise implies the conclusion.

The the premise implies the conclusion because of the conclusion infers the premise.

It would be circular reasoning, and definitely will cause stack overflow. I then redesign it as follows:

• Working code

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

But that means:

1. It fails on the correct logic that it cannot go without Paradox<T> which I initially named Predicate<T> but is conflict with System.Predicate<T>.

2. It's defective that T must implement IConvertable unlike the code former.

To be clear, I'm trying to make the code not only works but also represent like logical formulas that I can further reuse it to reason about logic without a constraint of T implements IConvertable. Is there a way make the logic correct and get rid of the defective design?

Answer 1

Dropping IConvertible

Let's start with the 'easy part': dropping the IConvertible. The reason you need it is because you want this code to work on all types, which means you cannot always influence that it has a certain member (Implies). What you would like to do is what they call in C++: template specialization, but unfortunately isn't available (yet?) in C#:

    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

The easiest way to solve this is by using multimethods. You can use the 'dynamic' keyword for this:

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

And if you have a 'third' method, you can simply call it

I've been looking a couple of minutes at the strange recursive definition and it doesn't really make sense to me... if you have a third helper method anyways, why not simply call it directly? :-)

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

The not(not(T)) problem

While the above didn't make much sense to me, I find it perfectly reasonable to use the type system and the language to help you out a bit. Well, surely you can do that and this is how I would do that... :-)

Let's introduce a 'Not' class with a generic:

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

If we have a Not> situation here, we want to give - otherwise, we want to use directly. Well, we can do that quite easy with some extensions:

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

To test it, you can do a similar thing:

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

This works, because overload resolution will pick the correct Optimize call, which ensures you will optimize the Not>>>> into the T value and so on.

It also works, because we wrap the 'Not' in a wrapper class and then use the type system to our advantage.

Going back to the original problem

Instead of directly evaluating 'Implies' and 'Infers', why not use a temporary object to do your evil work. You can use operator overloading (implicit conversion to be precise) to specify how Implies and Infers relate. The only catch is that it has its limits with extension methods.

C# operator overloading will then pick the best matching method. In the first case this will be the exact match, in the second case, the method will be implicitly converted and afterwards Evaluate will be called. In other words, it will not stack overflow, simply because it will do its evaluation lazy. Ready for the 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();
    }
}

Answer 2

It is not very clear from your question what are you trying to do. Are you trying to express some logical predicates in C#? Are you trying to write code that will reason about logic? Are you trying to represent logical formulas?

Paradoxes. When talking about paradoxes in computations, it might be good to read about lambda calculus and Russel's paradox (here is a nice article). Lambda calculus is essentially a simple functional programming language (imagine C# with lambda functions and application, but nothing else).

It was first developed as a system for the foundation of mathematics (before computers were invented), but this did not really work because you were able to write recursive computations that did not make sense (see the article for details), but you can write a computation that evaluates as follows (in C# notation):

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

... and since there is no x = r(r) such that x = not(x), the model does not make sense as foundation of mathematics. But it is useful as a model of programming languages where you can write recursive computations - though they may never terminate.

Representing logic. If you want to represent logical formulas in your program, then you probably want to separate the representation of formula from the reasoning. This is best done in functional languages (like F#), but you can do it in C# too (just with more typing). The F# representation of a formula would be something like:

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

The idea is that a formula is either a variable (named) or a negation of another formula or an implication where one formula implies another. In C#, you can represent the same thing as a class hierarchy (with Formula as a base class and three derived classes.)

Your reasoning can then be implemented as a method that manipulates formulas. In F#, this can be done quite easily using pattern matching. In C#, you'll probably need to use type tests to write code that checks if the argument is Variable (then do something...); if the argument is Negation (then do something...) etc.