Pad*_*rag 22 oop math programming-languages model algebra
RDBMS基于关系代数以及Codd的模型.我们有类似于编程语言或OOP的东西吗？
Nor*_*sey 41
我们有编程语言的[基础模型]吗？
天啊,是的.因为有很多编程语言,所以有多种模型可供选择.最重要的是:
Church的无类型lambda演算是一种计算模型,它与图灵机一样强大(不多也不少).着名的"Church-Turing假设"是这两个等价模型代表了我们知道如何实现的最通用的计算模型.lambda演算非常简单; 完整的语言是
e ::= x | e1 e2 | \x.e
它构成变量,函数应用程序和函数定义.lambda演算还附带了相当大的"缩减规则"集合,用于简化表达式.如果找到无法缩小的表达式,则称为"正常形式"并表示值.
lambda演算非常普遍,你可以在几个方向上进行演算.
如果要使用所有可用规则,可以编写专用工具,如部分计算器和部分编译器.
如果你避免在lambda下减少任何子表达式,但是否则使用所有可用的规则,你最终会得到一个惰性函数语言的模型,比如Haskell或Clean.在这个模型中,如果减少可以终止,则可以保证,并且很容易表示无限的数据结构.很强大.
如果你避免减少lambda下的任何子表达式,并且你还坚持在应用函数之前将每个参数减少为普通形式,那么你就拥有了一个急切的函数式语言模型,如F#,Lisp,Objective Caml,Scheme,或者标准ML.
还有几种类型的 lambda calcul,其中最着名的是以System F为名,它们由Girard(逻辑学)和Reynolds(计算机科学)独立发现.System F是CLU,Haskell和ML等语言的优秀模型,它们是多态的,但具有编译时类型检查功能.Hindley(逻辑学)和Milner(计算机科学)发现了一种限制形式的系统F(现在称为Hindley-Milner型系统),它可以从无类型 lambda演算的某些表达式推断出系统F表达式.Damas和Milner开发了一种算法做这种推理,它在标准ML中使用,并已在其他语言中推广.
Lambda演算只是推动符号.Dana Scott在指称语义学方面的开创性工作表明,lambda演算中的表达式实际上与数学函数相对应 - 他确定了哪些表达式.斯科特的工作对于理解"递归定义"尤为重要,这种定义在计算机科学中很常见,但从数学的角度来看却是荒谬的.Scott和Christopher Strachey表明,递归定义等价于递归方程的最小定义解,并进一步说明了如何构造该解.任何允许递归的语言,特别是允许以任意类型递归的语言(如Haskell和Clean)都归功于Scott的模型.
有一整套基于抽象机器的模型.这里没有一个单独的模型作为技术.您可以使用状态机定义语言并在计算机上定义转换.这个定义包括从图灵机到冯诺依曼机器到术语重写系统的所有内容,但通常抽象机器被设计为"尽可能接近语言".这些机器的设计以及关于它们的证明定理的业务都属于操作语义的标题.
面向对象编程怎么样？
对于OOP使用的抽象模型,我没有受过良好的教育.我最熟悉的模型与实施策略密切相关.如果我想进一步研究这个领域,我将从William Cook的Smalltalk的指称语义开始.(Smalltalk作为一种语言非常简单,几乎和lambda演算一样简单,因此它为建模更复杂的面向对象语言提供了一个很好的案例研究.)
Wei Hu提醒我,Martin Abadi和Luca Cardelli已经为面向对象语言组建了一个雄心勃勃的基础结构(类似于lambda演算).我不能很好地理解这项工作总结它,但这是他们书中序言的一段,我觉得值得引用:
程序语言通常很容易理解; 他们的构造现在是标准的,他们的正式基础是坚实的.这些语言的基本特征已被提炼为形式主义,这些形式主义在确定和解释实现,静态分析,语义和验证等问题时非常有用.
面向对象语言尚未出现类似的理解.对基本结构及其属性的集合没有广泛的一致意见......如果我们更好地理解面向对象语言的基础,这种情况可能会有所改善.
......我们将对象视为原始对象,并专注于对象应遵循的内在规则.我们介绍对象演算并围绕它们开发对象理论.这些对象计算与函数计算一样简单,但直接表示对象.
我希望这个引文能让你了解作品的风格.
Mik*_*vey 10
Lisp基于Lambda微积分,是我们今天在现代语言中看到的大部分内容的灵感来源.
Von-Neumann机器是现代计算机的基础,它们首先用汇编语言编程,然后用FORmula TRANslator编程.然后应用了无语境语法的形式语言学理论,并将其作为所有现代语言语法的基础.
可计算性理论(形式自动机)具有与正式语法的层次结构相似的机器类型的层次结构,例如,常规语法=有限状态机,无上下文语法=下推自动机,上下文敏感 - 语法=图灵机.
还有信息理论,有两种类型,Shannon和Kolmogorov,可以应用于计算.
有一些鲜为人知的计算模型,如递归函数理论,寄存器机器和后机器.
并且不要忘记各种形式的谓词逻辑.
补充:我忘了提到离散数学 - 群论和格理论.格子特别是(恕我直言)一个特别漂亮的概念,它基于所有布尔逻辑,以及一些计算模型,如指称语义.