非正式谬误导致堆栈溢出

本文关键字：堆栈 栈溢出 非正式 | 更新日期: 2023-09-27 18:06:01

  • 破损代码

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

上面的代码期望表达：

结论推断前提是因为前提隐含着结论。

前提意味着结论，因为结论推断了前提。

这将是循环推理，肯定会导致堆栈溢出。然后我重新设计如下：

  • 工作代码

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

但这意味着：

  1. 它在正确的逻辑上失败了，即它不能没有Paradox<T>，我最初将其命名为Predicate<T>，但与System.Predicate<T>冲突。

  2. 与代码前者不同，T必须实现IConvertable，这是有缺陷的。

需要明确的是，我试图使代码不仅能工作，而且能表示类似的逻辑公式，这样我就可以进一步重用它来推理逻辑，而不受T实现IConvertable的约束。有没有办法使逻辑正确并消除有缺陷的设计？

非正式谬误导致堆栈溢出

从你的问题中还不太清楚你想做什么。你想用C#表达一些逻辑谓词吗？您是否正在尝试编写能够推理逻辑的代码？你在试图表示逻辑公式吗？

悖论当谈到计算中的悖论时，最好读一读lambda演算和罗素悖论(这是一篇很好的文章(。Lambda演算本质上是一种简单的函数式编程语言(想象一下C#中有Lambda函数和应用程序，但没有其他功能(。

它最初是作为数学基础的系统开发的(在计算机发明之前(，但这并没有真正起作用，因为你可以编写没有意义的递归计算(详细信息请参阅文章(，但你可以编写如下计算(用C#表示法(：

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

由于没有x = r(r)和x = not(x)，该模型作为数学基础是没有意义的。但它作为编程语言的模型是有用的，在这里你可以编写递归计算——尽管它们可能永远不会终止。

表示逻辑如果要在程序中表示逻辑公式，则可能需要将公式的表示与推理分离。这最好用函数式语言(比如F#(来完成，但你也可以用C#来完成(只需要更多的打字(。公式的F#表示形式类似于：

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

其思想是，一个公式要么是变量(命名(，要么是对另一个公式的否定，要么是一个公式暗示另一个的暗示。在C#中，您可以将相同的东西表示为类层次结构(以Formula作为基类和三个派生类(

然后，您的推理可以实现为一种操纵公式的方法。在F#中，使用模式匹配可以很容易地做到这一点。在C#中，您可能需要使用类型测试来编写检查参数是否为Variable的代码(然后执行一些操作…(；如果参数是Negation(然后做点什么…(等。

丢弃IConvertable

让我们从"简单的部分"开始：放下IConvertible。您之所以需要它，是因为您希望此代码适用于所有类型，这意味着您不能总是影响它是否具有某个成员(Implies(。你想做的是他们在C++中所说的：模板专业化，但不幸的是，在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

解决这个问题最简单的方法是使用多方法。您可以为此使用"dynamic"关键字：

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

如果你有"第三种"方法，你可以简单地称之为

我已经看了几分钟这个奇怪的递归定义，它对我来说真的没有意义……如果你有第三个helper方法，为什么不直接调用它呢？：-(

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

not(not(T((问题

虽然上面的内容对我来说没有多大意义，但我发现使用类型系统和语言来帮助你是完全合理的。好吧，你肯定能做到，我就是这样做的…：-(

让我们介绍一个带有泛型的"Not"类：

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

如果我们在这里有一个Not>的情况，我们想给-否则，我们想直接使用。好吧，我们可以通过一些扩展很容易地做到这一点：

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

要测试它，你可以做类似的事情：

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

这是有效的，因为过载解析将选择正确的Optimize调用，这确保您将Not>>优化为T值，依此类推

它也起作用，因为我们将"Not"包装在包装器类中，然后使用类型系统来达到我们的优势。

返回原始问题

与其直接评估"暗示"answers"推断"，为什么不使用一个临时对象来做你的邪恶工作呢。可以使用运算符重载(确切地说是隐式转换(来指定Implies和Infers的关联方式。唯一的问题是它在扩展方法方面有其局限性。

C#运算符重载将选择最佳匹配方法。在第一种情况下这将是完全匹配，在第二种情况下，方法将被隐式转换，然后将调用Evaluate。换句话说，它不会堆栈溢出，只是因为它会延迟求值。准备好代码了吗？：-(

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();
    }
}
相关文章：