Philip Wadler - 命题即类型(Lambda Days 2016)
Philip Wadler - Propositions as Types (Lambda Days 2016)
频道:Erlang Solutions · 时长:56:58 · 发布:2016-03-02 · 播放:20211
简介
Philip Wadler 在 Lambda Days 上的演讲,讲述命题即类型,以及逻辑与计算之间的联系,这一联系是定理证明器和编程语言设计的基础。
HN 为什么推荐
被推荐为对计算机科学基础的一次精彩绝伦的快速巡览。
这是一个非常好的系列讲座[4]。 — HN, 2021
中文字幕节选
让我先做件重要的事 首先 微笑,我想这么做,因为这绝对是一群 很棒的观众,来到克拉科夫看到满屋子笑容满面、热切的面孔真好,所以嗯 我想请大家给自己鼓个掌,这真是 太棒了,所以感谢组织者邀请我,也感谢你们 到场,你们准备好了解这个极其有趣的 可计算性理论了吗?看,我说过它很 有趣吧。那么让我们开始吧。算法是一系列 由计算机执行的指令。如今我们想到 计算机时,会认为它是一种机器,但计算机曾经是一个人的名字,那个执行算法的 男人或女人。算法可以在欧几里得的《几何原本》中找到, 在古典希腊,以及9世纪波斯的花拉子米的著作中, 但直到20世纪,我们才得到 算法的形式化定义,当时阿隆佐·邱奇、库尔特·哥德尔 和艾伦·图灵的提议都在一年之内相继出现 就像公交车一样,你等了2000年才等到可计算性的形式化定义, 然后三个同时 到来。为什么会这样?所以在20世纪初, 形式逻辑最重要的倡导者之一是哥廷根的David Hilbert,他有一个 目标,他的目标是让所有数学家失业。他想要的是 一种算法,如果你输入一个数学形式陈述, 你就能计算并确定这个陈述是真还是假,这样你就不需要 数学家了,你可以用计算机取代他们,当时计算机还是人, 这被称为Entscheidungsproblem(判定问题),因为用 德语 听起来更好。现在他认为判定问题 是可解的,这基本上预设了逻辑 是完备的。济慈有句名言说美 即是真,真即是美,好吧,所以济慈告诉我们美当且仅当 真,而完备性非常相似,对吧?如果你有一个逻辑是可靠 且完备的,那就意味着可证明当且仅当为真,可证明的就是真的, 真的就是可证明的,好吧,这基本上就是为什么人们认为 判定问题一定有解。但在1930年,库尔特· 哥德尔提出了他的逻辑不完备性 证明,这意味着,请原谅我在这里使用一个技术术语,但Hilbert 完蛋了。所以哥德尔所做的是,他找到了一种方法 将逻辑中的陈述编码为数字, 并将逻辑中的证明也编码为数字,然后他可以写下一个数值陈述,意思是 这个陈述不可证明。哦, 他们说得对,一旦你能写下这个,你就陷入了严重的麻烦,对吧? 因为这个陈述要么是假的,要么是真的,所以如果它是 假的,那么它就是可证明的,而你就证明了一个 假的陈述,这有点破坏了做证明的整个意义,对吧?你想 做证明是为了知道它是真的,所以你真的很不希望出现 你能证明假的事情的情况,所以剩下的是什么?一旦你能写下 这个陈述,唯一剩下的可能性就是这个陈述是真的, 这意味着它不可证明,所以存在一个真的陈述但不可证明, 所以这没那么糟糕,但仍然很烦人,尤其是 如果你是Hilbert。现在,只要人们认为判定 问题是可解的,他们就不需要算法的形式化定义,这就像 斯图尔特大法官对色情作品的定义:我看到就知道 了,对吧?你可以直接看着它,看看你是否有算法,但如果你 想证明没有算法能解决判定问题,那么你
HN 上的讨论
我建议理论和实践相结合。对于实践,我强烈推荐学习 Haskell。如果你是函数式编程新手,那么学习 Haskell 会既困难又令人沮丧,但和任何新主题一样,关键是不放弃,持续探索。最近一个好的发展是很多主流语言开始包含函数式范式,比如 lambda、闭包等。例如 Java 引入了 lambda 表达式,JavaScript 早就有了。但从第一性原理的角度看,Haskell 已经是最好的了,所以请学习并用 Haskell 写代码,即使不是在工作中,至少也在副项目里。对于理论,我发现以下材料非常有用。0. 这个[0]是一场极其精彩的讲座,Phil Wadler 带我们快速巡览计算机科学。他讲解了计算机科学中几乎所有东西(硬件和软件)所建立于其上的不同基础结构。我每隔几个月就会看一次这场讲座 :-)。它帮助你建立上下文,并把各种主题落到实处。1. 独一无二的 SICP。书[1]和讲座[2]。2… — vishnugupta, 2021-05
> 静态类型也不是。它是一层保护,很像测试。 不对。Curry-Howard对应展示了类型化程序与证明之间的关系。我建议你看看Phillip Wadler关于这个的演讲:[VIDEO] 注意:这并不意味着类型系统能证明关于程序的_所有断言_,但类型系统确实可以作为证明器。 > 我不认为那一定正确。无论有没有静态类型,你仍然需要写测试。那些你无论如何都需要写的测试,会捕获动态类型语言中的类型错误,而静态类型语言在编译时就能发现这些错误。 这不一定正确,除非你测试所有输入(这在大多数情况下往往不可行)。类型系统可以通过输入不符合类型来拒绝它们,从而消除测试它们的需要。 > 问题在于你是否需要写更多测试,以及更多测试是否抵消了为静态类型化代码而需要写的更多代码。 我没有证据支持这一点(如果有人有,或者有相反的证据,我很想在这里看到引用),但我相信带有类型推断的静态类型系统几乎不会带来额外开销。… — knucklesandwich, 2016-05
只是提一下,这个演讲简要提到了另一个主题,Curry–Howard同构,Philip Wadler曾在Lambda Days(2016)上做过类似的演讲,题为“Propositions as Types”[1](幻灯片[2]和视频录像[3])。 [1]: [LINK] [2]: [LINK] [3]: [VIDEO] — irfansharif, 2017-04
相关视频
- 为《Crafting Interpreters》绘制插图 · Bob Nystrom · 9:23
- Noam Chomsky:《自由市场?》 · Santarchy · 2:01:00
- Michael Stonebraker | 大数据(至少)是四个不同的问题 · Michigan Engineering · 55:53
- 范畴论 1.1:动机与哲学 · Bartosz Milewski · 46:46
- Ruby Conf 12 - Y Not- 函数式编程历险记 by Jim Weirich · Confreaks · 53:21
- Python如何被泄漏的内部机制塑造,Armin Ronacher,Flask框架 · Видео с мероприятий {speach! · 49:55
- Erlang和Elixir的灵魂 • Sasa Juric • GOTO 2019 · GOTO Conferences · 42:02
- “简单造就易用” - Rich Hickey (2011) · Strange Loop Conference · 1:01:38
- Richard Feldman 谈“让不可能的状态不可能” · elm-conf · 25:06
- William Byrd 谈“有史以来最美丽的程序” [PWL NYC] · PapersWeLove · 1:31:05
- Rich Hickey 谈价值的价值 · InfoQ · 31:43
- 为什么函数式编程没有成为主流?—— Richard Feldman · Metosin · 46:09
- 也许不 - Rich Hickey · ClojureTV · 1:03:28
- 用 Clojure 的方式解决问题 - Rafal Dittwald · Clojure/north · 1:02:26
- 第一讲A:Lisp概述与简介 · MIT OpenCourseWare · 1:12:55
- APL中的康威生命游戏 · Dyalog · 7:47