依赖types可以certificate你的代码是正确的,直到规范。 但是,你如何certificate规范是正确的?

相关types通常被广告作为一种方式,使您能够断言程序是否符合规范是正确的。 所以,例如,你被要求编写一个sorting列表的代码 – 你可以通过将“sort”的概念编码为一个types来certificate代码是正确的,并且编写一个函数,比如List a -> SortedList a 。 但是,如何certificate规范SortedList是正确的呢? 难道不是这种情况:你的规格越复杂,这个规格的types编码就越可能是不正确的?

这是静态的types系统版本, 你怎么知道你的testing是正确的?

我可以诚实地给出的唯一答案是,你的规格越复杂和笨重,越有可能犯了一个错误。 你可以用types理论的forms来写一些东西,就像你可以把程序的描述forms化为一个可执行的函数一样。

希望是你的规格简单小巧,可以通过检查来判断,而你的实现可能会更大。 这有助于,一旦你有一些“种子”的想法forms化,你可以表明,从这些派生的想法是正确的。 从这个angular度来看,你可以更容易地机械地和可证实地从简单的部分中得到你的规范的一部分,并最终从你的规范中得到你的实现,就越有可能得到一个正确的实现。

但是,如何forms化某些东西可能并不清楚,这可能会导致将你的想法转化为forms主义的错误 – 你可能会认为你certificate了一件事,而事实上你certificate了另一件事 – 或者你会发现自己正在做types理论研究以forms化一个想法。

这是任何规范语言(甚至是英语)的问题,而不仅仅是依赖types。 你自己的post就是一个很好的例子:它包含了一个“sorting函数”的非forms规范,它只需要对结果进行sorting,而不是你想要的( \xs -> []会限定的)。 请参阅Twan van Laarhoven的博客文章。

我认为这是相反的:一个良好的types的程序不能certificate无稽之谈(假设系统是固定的),而规范可能是不一致的或只是愚蠢的。 所以,不是“如何确定这段代码反映我的柏拉图式的想法?”,而是“如何确保我的想法有意义地投射到一个纯粹的句法规则的有根据的平面?”。 如何确保你看到的鸟是一只嘲鸟(为某些提供的嘲讽鸟的概念)? 那么,研究鸟类,提高你的机会是正确的。 但是一如既往的人类 ,你不可能 100%确定。

types理论是通过引入forms规则, 机器检查certificate (这是一个非常相关的论文)和其他东西来缓解人类心智不完善的一种方法,它可以集中并因此简化问题(Brouwer说:“math只不过是我们思想的确切部分“),但是你不能指望任何工具使你的思想”正确“,因为没有统一的正确的概念。 IOW,没有办法正式连接非正式的和正式的:非正式的就像在IO monad里面 – 这是无法逃避的。

所以不是“这个语法是否反映了我的非常精确的语义?”,而是“我可以将我的原始语义附加到这个强结构化的语法吗?”。 程序是适当的物质对象,而想法是繁琐的近似,只能按惯例才能成为适当的物质对象。 所以我们使用惯例来形成一些基础,然后我们就相信它,因为相信所有众多想法中的一小部分,而不是所有这些想法都更合理。

你如何certificatemath是正确的? 也就是说,你如何certificate整数加法是计数苹果的正确方法,或者你如何certificate实际加法是增加权重的正确方法? forms/math与非正式/真实之间总是有一个界面。 它需要技巧和math/物理的味道才能find解决特定问题的适当forms。 正式的方法不会消除这一点。

forms方法的价值是双重的:

  1. 你不会知道你的程序是否正确,除非你知道它实际上满足什么属性。 在你知道你的sorting例程是否“正确”之前,你首先必须知道它的实际function。 任何发现这个问题的过程都将是一个正式的方法(甚至是unit testing!),所以拒绝“forms化方法”的人实际上只是将自己限制在一小部分可用的方法中。

  2. 即使你知道如何find一个程序实际上做了什么,人们在math推理中犯了错误(我们不是理性的生物,不pipe某些意识形态可能声称的)。 所以有一台机器检查我们是有帮助的。 这与我们使用unit testing的原因是一样的 – 运行桌面检查并确保程序做我们想要的是很好的; 但让电脑做检查,并告诉我们结果是否正确有助于防止错误。 让计算机检查我们有关程序行为的certificate是有帮助的,完全相同的原因。

正式的方法可以做的一件事情,我认为别人没有触及的是帮助简单的事情与更复杂的事情联系起来。 你可能不知道如何确切地指定一个Set数据结构应该如何performance,但是如果你可以根据sorting列表编写一个简单的版本,那么你可以certificate你基于平衡search树的花式版本通过toList函数。 也就是说,您可以使用forms化的方法将您对sorting列表的信心转移到平衡的search树上。

假设你的函数不是顶级的,而是被别人用作某个模块的一部分,这也是正确的certificate。 后者必须使用你函数的正确性certificate,如果不好,模块将不能编译。 模块本身仍然可能有错误,但这不是你的问题了。

在晚会来临之前,AFAICT还没有提到另一个重要的方面:在程序validation的背景下,在规范中有一个bug并不总是太可怕,因为你可以使用代码来检查spec

IOW,certificate不是说“代码是正确的”,而是“代码和规范是相互一致的”。 所以,为了使规范中的一个bug不被注意,它必须是以下之一:

  • 一个不规范的规范。
  • 该规范中的一个错误与代码中的相应错误相匹配。

正如其他人指出的那样:testing的问题是一样的。