现实世界中是否存在可证明的语言？（斯卡拉？）

StackOverflow https://stackoverflow.com/questions/4065001

题

我被教导关于 正式系统 在大学时，但我很失望它们似乎没有在现实世界中使用。

我喜欢这样的想法：能够知道某些代码（对象、函数等）是否有效，不是通过测试，而是通过 证明.

我确信我们都熟悉物理工程和软件工程之间不存在的相似之处（钢铁的行为是可预测的，软件可以做任何事情——谁知道呢！），我很想知道是否有任何语言可以可以在实际应用中使用（对 Web 框架的要求是否过高？）

我听说过关于像 scala 这样的函数式语言的可测试性的有趣事情。

作为软件 工程师 我们有什么选择？

有帮助吗？

解决方案

是的，有些语言是为编写可证明正确的软件而设计的。有些甚至用于工业。 火花阿达 可能是最突出的例子。我和 Praxis Critical Systems Limited 的一些人交谈过，他们使用它来在 Boings 上运行代码（用于引擎监控），它看起来相当不错。（这里有一个很棒的 语言的摘要/描述.) 该语言和随附的证明系统使用下面描述的第二种技术。它甚至不支持动态内存分配！

我的印象和经验是，编写正确的软件有两种技术：

  • 技巧一：使用您熟悉的语言（例如 C、C++ 或 Java）编写软件。采用这种语言的正式规范，并证明您的程序是正确的。

    如果您的目标是 100% 正确（这是汽车/航空航天行业最常见的要求），您将花费很少的时间进行编程，而花更多的时间进行证明。

  • 技巧2：使用稍微尴尬的语言（例如 Ada 的某些子集或 OCaml 的调整版本）编写软件，并一路编写正确性证明。在这里，编程和证明是齐头并进的。在 Coq 中编程甚至完全等同于它们！（参见 库里-霍华德通信)

    在这些情况下，您总是会得到正确的程序。（错误肯定会根植于规范中。）您可能会在编程上花费更多时间，但另一方面，您会一路证明它的正确性。

请注意，这两种方法都取决于您手头有一个正式的规范（否则您如何判断什么是正确/不正确的行为），以及语言的正式定义的语义（您如何才能判断实际行为）你的程序是）。

以下是正式方法的更多示例。它是否是“现实世界”，取决于你问的是谁:-)

我只知道一个“可证明是正确的” 网络应用程序语言: 尿道. 。“通过编译器”的 Ur 程序保证不会：

  • 遭受任何类型的代码注入攻击
  • 返回无效的 HTML
  • 包含无效的应用程序内部链接
  • HTML 表单与其处理程序期望的字段不匹配
  • 包含对远程 Web 服务器提供的“AJAX”式服务做出错误假设的客户端代码
  • 尝试无效的 SQL 查询
  • 在与 SQL 数据库或浏览器与 Web 服务器之间的通信中使用不正确的编组或解组

其他提示

为了回答这个问题，你真的需要定义你所说的“可证明的”的意思。正如里奇指出，与类型系统的任何语言与语言内置那里每编译程序的时间证明系统。这些证明系统几乎都是可悲的无能 - 回答类似的问题String VS Int，避免这样的问题“是列表排序？” - 但是它们证明系统没有最少

。

不幸的是，更复杂的证明目标，越难工作，它可以检查你的证据制度。此升级很快成为不可判定当你考虑到类的这些都对图灵机不可判定问题的庞大规模。当然，你可以做理论上证明一样的排序算法的正确性基本的东西，但任何更重要的是将要被踩在非常薄的冰。

即使证明一些简单的像一个排序算法的正确性需要相对复杂的证明系统。 （注：由于我们已经建立这种类型的系统是建立在语言证明系统，我要谈的事情型理论方面，而不是挥舞着我的手更有力）我相当肯定，一个名单上的排序将需要某种形式的依赖类型的完整正确性证明，否则，你有没有在类型级别引用相对值的方式。这立即开始闯入已被证明是不可判定的类型理论的领域。因此，尽管你可以证明你的列表排序算法，这样做将是使用一个系统，也将让你表达它无法验证证明的唯一途径正确性。就个人而言，我觉得这非常令人不安。

还有我先前提到的易用性的用途方面。更复杂的类型系统，在不太愉快的是使用。这不是一个硬性的规定，但我认为它持有的大部分事实。此外，与任何正式的系统，你会经常发现，表达证明是比创建摆在首位的实施更多的工作（和更容易出错）。

使用所有的出路，值得一提的是Scala的类型系统（如Haskell的）是图灵完备，这意味着你可以的理论上的使用它来证明你的代码的任何可判定的财产，前提是你写这样的代码，它是接受这种证据。 Haskell是几乎可以肯定这是一个更好的语言比Java（因为Haskell的类型级编程类似于Prolog的，而在斯卡拉类型级编程更类似于SML）。我不建议您使用这种方式Scala的或Haskell的类型系统（算法正确性的形式证明），但选择在理论上可用的。

总之，我想你没有见过的“真实世界”的正式制度的原因的事实，正式证明系统已经取得了实用主义的无情的暴政造成的。正如我所说，有参与各具特色的正确性证明，它几乎从来不值得这么多的努力。业内人士决定在很久以前，这是更容易地创建即席测试比它要经过任何形式的正式分析推理过程的。

类型语言证明不存在特定类别的故障的。更先进的类型的系统，所述多个故障它们可以证明不存在的。

有关证明整个计划的运作方式，是的，你是普通的语言，其中数学和编程彼此相遇，握手，然后边界之外步进继续使用有关程序员如何无法处理希腊符号谈符号。关于它的Σ这是无论如何。

你问的是我们很多人多年来都问过的问题。我不知道我有一个好的答案，但这里有一些：

  • 有些语言易于理解，并且有可能在今天被证明可以使用；Lisp via ACL2 就是其中之一，当然，Scheme 也有一个易于理解的正式定义。

  • 许多系统尝试使用纯函数式语言，或接近纯的语言，例如 Haskell。Haskell 中有相当多的正式方法。

  • 回溯 20 多年前，使用正式语言的手工校样，然后严格翻译成编译语言的做法是短暂的。一些例子包括 IBM 的 Software Cleanroom、ACL、Gypsy 和计算逻辑中的 Rose，John McHugh 和我在 C 的可信编译方面的工作，以及我自己在 C 系统编程的手工验证方面的工作。这些都引起了一些关注，但没有一个付诸实践。

我认为一个有趣的问题是将正式方法付诸实践的充分条件是什么？我很想听听一些建议。

您可以调查的纯功能性的语言的比如Haskell，这是用来当你的需求之一是可证的。

这是一个有趣的阅读，如果你有兴趣了解函数式编程语言和纯功能编程语言。

这样可证明语言的现实世界的应用将是极其困难的编写和理解afterwoods。 商业世界需要运行的软件，速度快。

/“可证明的”语言只是不大规模写入读取大项目的代码库，并似乎只是工作，小型和孤立的用例。

我参与了两个证明的语言。第一种是通过完美开发，用于指定sotfware，提炼，并生成代码的系统所支持的语言。它被用于一些大型的系统，包括PD本身，它教多所大学。第二语言可证明我参与是MISRA-C的可证明子集，请参见 C / C ++验证博客为更多。

查核欧米茄。

此引入包含具有相对无痛实施AVL树的包括正确性的证明。

斯卡拉，就是要“真实世界”，所以没有已作出努力，以使其可证明。你可以在Scala中做的是生产功能代码。功能代码测试容易得多，这是恕我直言“现实世界”和可证明性之间的良好平衡。

EDIT ===== 去除约ML是我的不正确的思想“可证明的”。

在可证明正确的代码的背景下，我对“现实世界”的（有争议的）定义是：

  • 它必须涉及某种程度的 自动化, ，否则你将花费太多的时间来证明和处理杂乱的小细节，并且这将是完全不切实际的（除了航天器控制软件之类的东西，你可能实际上想为此花费巨额资金）细致检查）。
  • 它必须支持某种程度的 函数式编程, ，它可以帮助您编写非常模块化、可重用且更易于推理的代码。显然，编写或证明 Hello World 或各种简单程序不需要函数式编程，但在某种程度上，函数式编程确实变得非常有用。
  • 虽然您不一定必须能够用主流编程语言编写代码，但作为替代方案，您至少应该能够以可靠的方式将代码机器翻译成用主流编程语言编写的相当高效的代码。方式。

以上是相对比较普遍的要求。其他的，例如对命令式代码进行建模的能力，或者证明高阶函数正确的能力，对于某些任务可能很重要或必不可少，但不是全部。

鉴于这些点，列出的许多工具 我的这篇博文 可能有用 - 尽管它们几乎都是新的和实验性的，或者对绝大多数行业程序员来说是不熟悉的。不过，其中涵盖了一些非常成熟的工具。

怎么样 伊德里斯 和 阿格达？现实世界够了吗？

作为现实生活中一个很好的例子，有一个项目旨在提供一个用 Agda 编写的经过验证的 HTTP REST 库，名为 Lemmachine： https://github.com/larrytheliquid/Lemmachine

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top