我们正在努力恢复Google Play商店上的Unionpedia应用程序
🌟我们简化了设计以优化导航!
Instagram Facebook X LinkedIn

依赖类型和直觉类型论

快捷方式: 差异相似杰卡德相似系数参考

依赖类型和直觉类型论之间的区别

依赖类型 vs. 直觉类型论

在计算机科学和逻辑中,依赖类型(或依存类型,dependent type)是指依赖于值的类型,其理论同时包含了数学基础中的类型论和计算机编程中用以减少程序错误的类型系统两方面。在 Per Martin-Löf 的直觉类型论中,依赖类型可对应于谓词逻辑中的全称量词和存在量词;在依赖类型函数式编程语言如 ATS、Agda、Dependent ML、Epigram、F* 和 Idris 中,依赖类型系统通过极其丰富的类型表达能力使得程序规范得以借助类型的形式被检查,从而有效减少程序错误。 依赖类型的两个常见实例是依赖函数类型(又称依赖乘积类型、Π-类型)和依赖值对类型(又称依赖总和类型、Σ-类型)。一个依赖类型函数的返回值类型可以依赖于某个参数的具体值,而非仅仅参数的类型,例如,一个输入参数为整型值n的函数可能返回一个长度为n的数组;一个依赖类型值对中的第二个值可以依赖于第一个值,例如,依赖类型可表示这样的类型:它由一对整数组成,其中的第二个数总是大于第一个数。 依赖类型增加了类型系统的复杂度。由于确定两个依赖于值的类型的等价性需要涉及具体的计算,若允许在依赖类型中使用任意值的话,其类型检查将会成为不可判定问题;换言之,无法确保程序的类型检查一定会停机。 由于Curry-Howard同构揭示了程序语言的类型论与证明论的直觉逻辑之间的紧密关联性,以依赖类型系统为基础的编程语言大多同时也作为构造证明与可验证程序的辅助工具而存在,如 Coq 和 Agda(但并非所有证明辅助工具都以类型论为基础);近年来,一些以通用和系统编程为目的的编程语言被设计出来,如 Idris。 一些以证明辅助为主要目的的编程语言采用强函数式编程(total functional programming),这消除了停机问题,同时也意味着通过它们自身的核心语言无法实现任意无限递归,不是图灵完全的,如 Coq 和 Agda;另外一些依赖类型编程语言则是图灵完全的,如 Idris、由 ML 衍生而来的 ATS 和 由 F# 衍生而来的 F*。. 觉类型论、或构造类型论、或Martin-Löf 类型论、或就叫类型论是基于数学构造主义的函数式编程语言、逻辑和集合论。直觉类型论由瑞典数学家和哲学家 Per Martin-Löf 在1972年介入。 Martin-Löf 已经多次修改了它的提议;先是非直谓性的而后是直谓性的,先是外延的而后是内涵的类型论变体。 直觉类型论基于的是命题和类型的同一: 一个命题同一于它的证明的类型。这种同一通常叫做Curry-Howard同构,它最初公式化了命题逻辑和简单类型 lambda 演算。类型论通过介入包含着值的依赖类型把这种同一扩展到谓词逻辑。类型论内在化了 Brouwer、Heyting 和 Kolmogorov 提议的叫做 BHK释义的直觉逻辑释义。类型论的类型扮演了类似于集合在集合论的角色,但是在类型论中的函数总是可计算的。.

之间依赖类型和直觉类型论相似

依赖类型和直觉类型论有(在联盟百科)19共同点: Agda存在量化实数不交并函數程式語言全称量化Coq笛卡儿积简单类型λ演算类型论类型检查直觉主义逻辑谓词逻辑自然数逻辑Per Martin-Löf柯里-霍华德同构构造演算有类型λ演算

Agda

Agda是一个依赖类型的函数式编程语言,同时亦可作为一个用于构建构造性证明的证明辅助工具。Agda最早由瑞典查尔摩斯工学院的 Ulf Norell 设计并开发,作为他的博士论文课题。目前的版本,Agda 2,则在第一版的基础上完全重写。 Agda体现了柯里-霍华德同构(Curry-Howard correspondence)。它的理论根基是 Zhaohui Luo 的UTT,该理论与 Per Martin-Löf 的直觉类型论相类似。 Agda与Coq的几点显著不同之处在于:它本身并不支持tactics;所有的证明均以函数式编程的方式书写;语言本身吸收了许多常规的程序语言元素,诸如:数据类型、模式匹配(pattern matching)、记录类型(records)、let表达式和模块(modules)等,而其语法则非常类似Haskell。 Agda系统一般通过其提供的Emacs界面进行交互,亦可藉由命令行方式单独执行。.

Agda和依赖类型 · Agda和直觉类型论 · 查看更多 »

存在量化

在谓词逻辑中,存在量化是对一个域的至少一个成员的性质或关系的论断。使用叫做存在量词逻辑算子符号∃来指示存在量化。 它相对于声称某些事物对所有事物都为真的全称量化。.

依赖类型和存在量化 · 存在量化和直觉类型论 · 查看更多 »

实数

实数,是有理數和無理數的总称,前者如0、-4、81/7;后者如\sqrt、\pi等。实数可以直观地看作小數(有限或無限的),它們能把数轴「填滿」。但僅僅以枚舉的方式不能描述實數的全體。实数和虚数共同构成复数。 根据日常经验,有理數集在數軸上似乎是「稠密」的,于是古人一直认为用有理數即能滿足測量上的實際需要。以邊長為1公分的正方形為例,其對角線有多長?在規定的精度下(比如誤差小於0.001公分),總可以用有理數來表示足夠精確的測量結果(比如1.414公分)。但是,古希臘畢達哥拉斯學派的數學家發現,只使用有理數無法完全精確地表示這條對角線的長度,這徹底地打擊了他們的數學理念;他們原以為:.

依赖类型和实数 · 实数和直觉类型论 · 查看更多 »

不交并

在集合論,一組集合的不交并指的是一種修改過的并集運算,除了普通的并集,還標記了元素的來源。不交并還有另一個意義,指的是兩兩不交的集合的并集。.

不交并和依赖类型 · 不交并和直觉类型论 · 查看更多 »

函數程式語言

函數式編程(functional programming)或称函数程序设计,又稱泛函編程,是一種編程典範,它將電腦運算視為數學上的函數計算,並且避免使用程序状态以及易变物件。函數程式語言最重要的基礎是λ演算(lambda calculus)。而且λ演算的函數可以接受函數當作輸入(引數)和輸出(傳出值)。 比起指令式編程,函數式編程更加強調程序执行的结果而非执行的过程,倡导利用若干简单的执行单元让计算结果不断渐进,逐层推导复杂的运算,而不是设计一个复杂的执行过程。.

依赖类型和函數程式語言 · 函數程式語言和直觉类型论 · 查看更多 »

全称量化

在谓词逻辑中,全称量化是尝试形式化某个事物(逻辑谓词)对于所有事物或所有有关的事物都为真的概念。结果的陈述是全称量化后的陈述,我们在谓词上有了全称量化。在符号逻辑中,全称量词(典型的"∀")是用来指示全称量化的符号。.

依赖类型和全称量化 · 全称量化和直觉类型论 · 查看更多 »

Coq

Coq 是一个交互式的定理证明辅助工具。它允许用户输入包含数学断言的表达式、机械化地对这些断言执行检查、帮助构造形式化的证明、并从其形式化描述的构造性证明中提取出可验证的(certified)程序。Coq 的理论基础是归纳构造演算(calculus of inductive constructions)、一种构造演算(calculus of constructions)的衍生理论。Coq 并非一个自动化定理机器证明语言;然而,它提供了自动化定理证明的策略(tactics)和不同的决策过程。 Coq 同时还是一个依赖类型的函数式编程语言。它由法国PPS实验室的PI.R2团队研究开发,该团队由INRIA、巴黎综合理工学院、巴黎第十一大学、巴黎第七大学和法国国家科学研究中心组成。此前里昂高等师范学校亦曾参与开发。Coq 项目当前由 Gérard Huet、Christine Paulin 和 Hugo Herbelin领导。Coq 使用 OCaml 以及少部分 C 实现。 单词 coq 在法语中意为“公鸡”,此命名体现了法国在研究活动中使用动物名称命名工具的传统。 最初,它被简单地称作 Coc,意即构造演算(calculus of constructions)的缩写,同时也暗含了 Thierry Coquand(与 Gérard Huet 共同提出了前述的构造演算)的姓氏。 Coq 自身提供了一套规范语言 Gallina (gallina 在西班牙语中意为“母鸡”)。使用 Gallina 书写的程序具有规范化性质——它们总是会终止。此性质使之避开了停机问题 。同时,这也使得 Coq 语言本身并非图灵完全。.

Coq和依赖类型 · Coq和直觉类型论 · 查看更多 »

笛卡儿积

在数学中,两个集合X和Y的笛卡儿积(Cartesian product),又称直积,在集合论中表示为X × Y,是所有可能的有序对組成的集合,其中有序對的第一个对象是X的成员,第二个对象是Y的成员。 舉個實例,如果集合X是13个元素的点数集合,而集合Y是4个元素的花色集合,则这两个集合的笛卡儿积是有52个元素的标准扑克牌的集合。 笛卡儿积得名于笛卡儿,因為這概念是由他建立的解析几何引申出來.

依赖类型和笛卡儿积 · 直觉类型论和笛卡儿积 · 查看更多 »

简单类型λ演算

单类型 lambda 演算(\lambda^\to)是连接词只有 \to (函数类型)的有类型 lambda 演算。这使它成为规范的、在很多方面是最简单的有类型 lambda 演算的例子。 简单类型也被用来称呼对简单类型 lambda 演算的扩展比如积、陪积或自然数(系统 T)甚至完全的递归(如PCF)。相反的,介入了多态类型(如系统F)或依赖类型(如逻辑框架)的系统不被当作是简单类型。简单类型 lambda 演算最初由阿隆佐·邱奇在 1940 年介入来尝试避免无类型 lambda 演算的悖论性使用。.

依赖类型和简单类型λ演算 · 直觉类型论和简单类型λ演算 · 查看更多 »

类型论

在最广泛的层面上,类型论是关注把实体分类到叫做类型的搜集中的数学和逻辑分支。在这种意义上,它与类型的形而上学概念有关。现代类型论在部分上是响应罗素悖论而发明的,并在伯特兰·罗素和阿弗烈·诺夫·怀海德的《数学原理》中起到重要作用。 在计算机科学分支中的编程语言理论中,类型论提供了设计分析和研究类型系统的形式基础。实际上,很多计算机科学家使用术语“类型论”来称呼对编程语言的类型语言的形式研究,尽管有些人把它限制于对更加抽象的形式化如有类型lambda演算的研究。.

依赖类型和类型论 · 直觉类型论和类型论 · 查看更多 »

类型检查

#重定向 類型系統.

依赖类型和类型检查 · 直觉类型论和类型检查 · 查看更多 »

直觉主义逻辑

觉主义逻辑或构造性逻辑是最初由阿蘭德·海廷开发的为鲁伊兹·布劳威尔的数学直觉主义计划提供形式基础的符号逻辑。这个系统保持跨越生成导出命题的变换的证实性而不是真理性。从实用的观点,也有使用直觉逻辑的强烈动机,因为它有存在性质,这使它还适合其他形式的数学构造主义。.

依赖类型和直觉主义逻辑 · 直觉主义逻辑和直觉类型论 · 查看更多 »

谓词逻辑

在数理逻辑中,谓词逻辑(Predicate logic)是符号形式系统的通用术语,比如一阶逻辑,二阶逻辑,多类逻辑或无穷逻辑等等。.

依赖类型和谓词逻辑 · 直觉类型论和谓词逻辑 · 查看更多 »

自然数

数学中,自然数指用于计数(如「桌子上有三个苹果」)和定序(如「国内第三大城市」)的数字。用于计数时称之为基数,用于定序时称之为序数。 自然数的定义不一,可以指正整数 (1, 2, 3, 4, \ldots),亦可以指非负整数 (0, 1, 2, 3, 4, \ldots)。前者多在数论中使用,后者多在集合论和计算机科学中使用,也是 标准中所采用的定义。 数学家一般以\mathbb代表以自然数组成的集合。自然数集是一個可數的,無上界的無窮集合。.

依赖类型和自然数 · 直觉类型论和自然数 · 查看更多 »

逻辑

邏輯(λογική;Logik;logique;logic;意大利语、西班牙语、葡萄牙语: logica),又稱理則、論理、推理、推論,是对有效推論的哲學研究。邏輯被使用在大部份的智能活動中,但主要在哲學、心理、学习、推论统计学、脑科学、數學、語義學、 法律和電腦科學等領域內被視為一門學科。邏輯討論邏輯論證會呈現的一般形式,哪種形式是有效的,以及其中的謬論。 邏輯通常可分為三個部份:歸納推理、溯因推理和演繹推理。 在哲學裡,邏輯被應用在大多數的主要領域之中:形上學/宇宙論、本體論、知識論及倫理學。 在數學裡,邏輯是指形式逻辑和数理邏輯,形式逻辑是研究某個形式語言的有效推論。主要是演繹推理。 在辯證法中也會學習到邏輯。数理邏輯是研究抽象邏輯关系和数学基本的问题。 在心理、脑科学、語義學、 法律裡,是研究人类思想推理的处理。 在学习、推论统计学裡,是研究最大可能的结论。主要是歸納推理、溯因推理。 在電腦科學裡, 是研究各种方法的性质,可能性,和实现在机器上。主要是歸納推理、溯因推理,也有在歸納推理的研究。 从古文明开始(如古印度、中國和古希臘)都有對邏輯進行研究。在西方,亞里斯多德將邏輯建立成一門正式的學科,並在哲學中給予它一個基本的位置。.

依赖类型和逻辑 · 直觉类型论和逻辑 · 查看更多 »

Per Martin-Löf

#重定向 佩尔·马丁-洛夫.

Per Martin-Löf和依赖类型 · Per Martin-Löf和直觉类型论 · 查看更多 »

柯里-霍华德同构

柯里-霍華德对应是在计算机程序和数学证明之间的紧密联系;这种对应也叫做柯里-霍華德同构、公式为类型对应或命题为类型对应。这是对形式逻辑系统和公式计算(computational calculus)之间符号的相似性的推广。它被认为是由美国数学家哈斯凯尔·加里和逻辑学家William Alvin Howard独立发现的。.

依赖类型和柯里-霍华德同构 · 柯里-霍华德同构和直觉类型论 · 查看更多 »

构造演算

构造演算(CoC)是高阶有类型 lambda 演算,这里的类型是一级值。因此在 CoC 内有可能定义从整数到类型、从类型到类型的函数,同从整数到整数的函数一样。CoC 是强规范化的。 CoC 最初由 Thierry Coquand 开发。 CoC 是 Coq 定理证明器早期版本的基础;它后来的版本建造在归纳构造演算之上,这是带有对归纳数据类型的天然支持的 CoC 扩展。在最初的 CoC 中,归纳数据类型必须模拟为它们的多态解构函数。.

依赖类型和构造演算 · 构造演算和直觉类型论 · 查看更多 »

有类型λ演算

有类型 lambda 演算是使用 lambda 符号(\lambda)指示匿名函数抽象的一种有类型的形式化。有类型 lambda 演算是基础编程语言并且是有类型的函数式编程语言如 ML 和 Haskell 和更间接的指令式编程语言的基础。它们通过 Curry-Howard同构密切关联于直觉逻辑并可以被认为是范畴的类的内部语言,比如简单类型 lambda 演算是笛卡尔闭范畴(CCC)的语言。 传统上,有类型 lambda 演算被看作无类型lambda演算的精细化。更现代的观点把有类型 lambda 演算看做更基础的理论,而把无类型 lambda 演算看作它的只有一个类型的特殊情况。.

依赖类型和有类型λ演算 · 有类型λ演算和直觉类型论 · 查看更多 »

上面的列表回答下列问题

依赖类型和直觉类型论之间的比较

依赖类型有41个关系,而直觉类型论有51个。由于它们的共同之处19,杰卡德指数为20.65% = 19 / (41 + 51)。

参考

本文介绍依赖类型和直觉类型论之间的关系。要访问该信息提取每篇文章,请访问: