22

RDBMS 基于关系代数和 Codd 模型。我们是否有类似于编程语言或 OOP 的东西？

4

11 回答 11

41

我们有编程语言的[底层模型]吗？

天，是的。而且因为有这么多的编程语言，所以有多种模型可供选择。首先最重要：

  • Church 的无类型 lambda 演算是一种计算模型，它与图灵机一样强大（不多也不少）。著名的“Church-Turing 假设”是这两个等效模型代表了我们知道如何实现的最通用的计算模型。lambda演算非常简单；整个语言是

    e ::= x | e1 e2 | \x.e

    它们构成变量、函数应用程序和函数定义。lambda 演算还带有相当大的“简化规则”集合，用于简化表达式。如果你找到一个不能被归约的表达式，那称为“范式”并表示一个值。

    lambda 演算非常通用，您可以从多个方向进行学习。

    • 如果你想使用所有可用的规则，你可以编写专门的工具，比如部分评估器和编译器的一部分。

    • 如果你避免减少 lambda 下的任何子表达式，而是使用所有可用的规则，你最终会得到一个惰性函数语言的模型，比如Haskell或 Clean。在这个模型中，如果一个归约可以终止，那么它是有保证的，并且很容易表示无限的数据结构。很强大。

    • 如果您避免减少 lambda 下的任何子表达式，并且如果您还坚持在应用函数之前将每个参数减少为正常形式，那么您就有了一个像 F#、Lisp、Objective Caml、Scheme或标准机器学习。

  • 还有几种类型的lambda 演算，其中最著名的归类为System F，它们是由 Girard（逻辑学）和 Reynolds（计算机科学）独立发现的。System F 是 CLU、Haskell 和 ML 等语言的优秀模型，这些语言是多态的，但具有编译时类型检查。Hindley（逻辑学）和 Milner（计算机科学）发现了 System F 的一种受限形式（现在称为 Hindley-Milner 类型系统），这使得从无类型 lambda 演算的一些表达式中推断 System F 表达式成为可能。Damas 和 Milner 开发了一种算法来进行这种推理，该算法用于标准 ML 并已在其他语言中推广。

  • Lambda 演算只是在推动符号。Dana Scott 在指称语义方面的开创性工作表明，lambda 演算中的表达式实际上对应于数学函数——他确定了哪些函数。Scott 的工作在理解“递归定义”方面尤为重要，这在计算机科学中很常见，但从数学的角度来看却是荒谬的。Scott 和 Christopher Strachey 证明了递归定义等价于递归方程的最小定义解，并进一步说明了如何构造该解。任何允许递归的语言，尤其是允许以任意类型递归的语言（如 Haskell 和 Clean）都归功于 Scott 的模型。

  • 有一整套基于抽象机器的模型。在这里，与其说是一种单独的模型，不如说是一种技术。您可以通过使用状态机并在机器上定义转换来定义语言。这个定义涵盖了从图灵机到冯诺依曼机再到术语重写系统的所有内容，但通常抽象机被设计为“尽可能接近语言”。这种机器的设计，以及证明它们的定理的业务，都属于操作语义的范畴。

那么面向对象编程呢？

对于用于 OOP 的抽象模型，我没有受到应有的教育。我最熟悉的模型与实施策略密切相关。如果我想进一步研究这个领域，我会从 William Cook 的 Smalltalk 指称语义开始。（Smalltalk 作为一门语言非常简单，几乎和 lambda 演算一样简单，因此它为建模更复杂的面向对象语言提供了一个很好的案例研究。）

Wei Hu 提醒我，Martin Abadi 和 Luca Cardelli 在面向对象语言的基础演算（类似于 lambda 演算）方面开展了雄心勃勃的工作。我不太了解这项工作来总结它，但这里有一段来自他们书的序言，我觉得值得引用：

程序语言通常很好理解；到目前为止，它们的构造是标准的，并且它们的正式基础是坚实的。这些语言的基本特征已被提炼成形式，证明在识别和解释实现、静态分析、语义和验证问题方面很有用。

面向对象的语言还没有出现类似的理解。对于基本结构的集合及其属性没有广泛的共识……如果我们对面向对象语言的基础有更好的理解，这种情况可能会有所改善。

...我们将对象视为原始对象，并专注于对象应遵守的内在规则。我们引入对象演算并发展围绕它们的对象理论。这些对象演算与函数演算一样简单，但直接表示对象。

我希望这段引文能让你对作品的味道有所了解。

于 2010-03-18T22:10:10.630 回答
10

Lisp 基于 Lambda 演算，是我们今天在现代语言中看到的大部分内容的灵感来源。

冯诺依曼机器是现代计算机的基础，它首先用汇编语言编程，然后用 FORmula TRANslator 编程。然后应用了上下文无关语法的形式语言学理论，并成为所有现代语言句法的基础。

可计算性理论（形式自动机）具有与形式语法层次结构平行的机器类型层次结构，例如，regular-grammar = 有限状态机、上下文无关语法 = 下推自动机、上下文敏感语法 =图灵机。

还有两种类型的信息论，Shannon 和 Kolmogorov，可以应用于计算。

还有一些鲜为人知的计算模型，例如递归函数理论、寄存器机器和后机器。

不要忘记各种形式的谓词逻辑。

补充：我忘了提到离散数学——群论和格论。格尤其是（恕我直言）所有布尔逻辑和一些计算模型（例如指称语义）的一个特别漂亮的概念。

于 2010-03-18T12:59:25.863 回答
6

像 lisp 这样的函数式语言从 Church 的“lambda calculs”（此处的维基百科文章）继承了它们的基本概念。问候

于 2010-03-18T12:47:17.257 回答
5

一个概念可能是图灵机。

于 2010-03-18T12:41:56.830 回答
3

如果您学习编程语言（例如：在大学），则涉及很多理论，而不是涉及一点数学。

例子是：

于 2010-03-18T13:10:22.483 回答
2

维基百科的面向对象编程的历史部分可能很有启发性。

于 2010-03-18T12:48:48.113 回答
2

我能想到的最接近的类比是 Gurevich Evolving Algebras，如今，以“Gurevich 抽象状态机”（GASM）的名义更为人所知。

当 Gurevich 加入微软时，我一直希望看到该理论更多的实际应用，但似乎很少有人出来。您可以查看 Microsoft 站点上的 ASML 页面。

GASM 的优点是它们非常类似于伪代码，即使它们的语义是正式指定的。这意味着从业者可以很容易地掌握它们。

毕竟，我认为关系代数成功的部分原因在于它是易于掌握的概念的形式基础，即表、外键、连接等。

我认为对于软件系统的动态组件，我们需要类似的东西。

于 2010-03-18T12:56:29.440 回答
2

有许多维度可以解决您的问题，分散在答案中。

首先，为了描述一种语言的语法并指定解析器的工作方式，我们使用上下文无关文法。

然后，您需要为语法分配含义。形式语义派上用场；主要参与者是操作语义、指称语义和公理语义。

要排除不良程序，您需要使用类型系统。

最后，所有计算机程序都可以简化为（或编译为，如果你愿意的话）非常简单的计算模型。命令式程序更容易映射到图灵机，而函数式程序更容易映射到 lambda 演算。

如果你自己学习所有这些东西，我强烈推荐http://www.uni-koblenz.de/~laemmel/paradigms0910/，因为这些讲座被录像并放到网上。

于 2010-03-19T06:13:30.723 回答
2

很多人提到了数学在计算理论和语义中的应用。我喜欢提到类型理论，我很高兴有人提到格理论。这里还有一些。

没有人明确提到过范畴论，它在函数式语言中比在其他地方出现得更多，例如通过单子和函子的概念。然后是模型理论和实际出现在定理证明器或逻辑语言 Prolog 中的各种逻辑化身。并发语言的基础和问题也有数学应用。

于 2013-05-07T13:30:42.743 回答
2

OOP 没有数学模型。

SQL 数学模型中的关系代数。它是由 bt EF Codd 创建的。CJ Date 也是帮助这一理论的著名科学家。整个想法是您可以将每个操作作为一个集合操作来执行，同时影响很多值。这当然意味着必须告诉数据库引擎要输出什么，并且数据库能够优化您的查询。

Codd 和 Date 都批评了 SQL，因为他们参与了理论，但没有参与 SQL 的创建。

看这个视频：http ://player.oreilly.com/videos/9781491908853?toc_id=182164

Chris Date 提供了很多信息。我记得 Date 批评 SQL 编程语言是一种糟糕的语言，但我找不到那篇论文。

批评基本上是大多数语言允许编写表达式并将变量分配给这些表达式，但 SQL 不允许。

由于 SQL 是一种逻辑语言，我想你可以在 Prolog 中编写关系代数。至少你会有一种真正的语言。所以你可以在 Prolog 中编写查询。而且由于在 prolog 中有很多程序可以解释自然语言，因此您可以使用自然语言查询数据库。

根据鲍勃叔叔的说法，当每个人都有 SSD 时，就不需要数据库了，因为 SSD 的架构意味着访问速度和 RAM 一样快。因此，您可以将所有对象都放在 RAM 中。

https://www.youtube.com/watch?feature=player_detailpage&v=t86v3N4OshQ#t=3287

放弃 SQL 的唯一问题是您最终将没有数据库的查询语言。

所以是与否，关系代数被用作 SQL 的灵感来源，但 SQL 并不是关系代数的真正实现。

对于 Lisp，情况有所不同。主要思想是在 Lisp 中实现 eval 函数可以实现整个语言。这就是为什么第一个 Lisp 实现只有半页代码。

http://www.michaelnielsen.org/ddi/lisp-as-the-maxwells-equations-of-software/

稍微笑一下：https ://www.youtube.com/watch?v=hzf3hTUKk8U

函数式编程的重要性归结为柯里化函数和惰性调用。永远不要忘记环境和闭包。和地图减少。这一切都意味着我们将在 20 年内使用函数式语言进行编码。

现在回到 OOP，没有正式的 OOP。

有趣的是，曾经创建的第二种面向对象语言 Smalltalk 只有对象，它没有原语或类似的东西。并且创建者 Alan Kay 明确地创建了块来完全像 Lisp 函数一样工作。

有些人声称 OOP 可以使用范畴论来形式化，范畴论是一种集合论，但具有态射。态射是对象之间的结构保持映射。所以一般来说，你可以有 map( f, collection ) 并取回一个集合，所有元素都被 f 应用。

我很确定 Lisp 有这个，但是 Lisp 也有返回集合中的一个元素的函数，这会破坏结构，所以态射是一种特殊的函数，因此，你需要减少和限制函数在 Lisp 中，它们都是态射。

https://www.youtube.com/watch?feature=player_detailpage&v=o6L6XeNdd_k#t=250

这样做的主要问题是函数在 OOP 中并不独立于对象存在，但在范畴论中它们确实存在。因此它们是不相容的。你可以开发一种新的语言来表达范畴论。

为尝试形式化 OOP 而明确创建的实验性理论语言是 Z。Z 源自需求形式主义。

另一种尝试是 Luca Cardelli 的形式主义：

Javahttp://lucacardelli.name/Papers/PrimObjImp.pdf Javahttp://lucacardelli.name/Papers/PrimObj1stOrder.A4.pdf Javahttp://lucacardelli.name/Papers/PrimObjSemLICS.A4.pdf

我无法阅读和理解该符号。这似乎是一种无用的练习，因为据我所知，没有人像在 Lisp 中实现 Lamba 演算那样实现这一点。

于 2015-07-06T03:40:35.890 回答
0

据我所知，形式语法用于描述语法。

于 2010-03-18T12:45:08.040 回答