论编程语言的表现力 - Shriram Krishnamurthi [PWLConf 2019]
On the Expressive Power of Programming Languages by Shriram Krishnamurthi [PWLConf 2019]
频道:PapersWeLove · 时长:59:03 · 发布:2019-09-19 · 播放:27256
简介
Shriram Krishnamurthi 在 PWLConf 2019 的演讲,基于 Felleisen 的论文,讨论编程语言表现力的形式化概念。它解释了如何判断一个特性是否增加了表现力,即模拟它是否需要全局重写。
HN 为什么推荐
被推荐作为进入语言表现力精确定义的平易近人方式,用于语言设计论证。
Shriram Krishnamurthi 两年前关于这篇论文的演讲可能更容易理解。 — HN, 2021
中文字幕节选
[音乐] 大家好,我是 Shriram,我要展示的这项工作绝对不是我做的,我会尽力 不失误,不把它说成是我的,如果我这样做了,那也不是我的。我没戴 挂绳,因为显然它干扰了音频,而音频更重要。 我是绿色挂绳,如果有人在意的话。那么这篇论文是关于什么的呢? 它有一个看起来有点晦涩的标题,说的是,你知道,它是关于 编程语言表达能力的。实际作者的照片在上面。 那是Matthias Felleisen,所以从精神上讲,他现在正盘旋在我们上方。那么这篇 论文是关于什么的呢?嗯,你知道,关于在不同的计算模型中 能做什么和不能做什么,我们知道很多事情,对吧?所以我们有非常清晰的 数学区分。如果你曾经有幸或不幸——取决于 是谁教的——上过计算理论课,或者翻开过关于这个 主题的书,你就知道有这些非常精细的区分,我们知道如何做出 这些区分。然而不知何故,这些实际上对我们作为语言设计者很有用。这 对我来说在设计语言时是无价的。我想,如果我添加这个,我的 理论教科书告诉我可能会发生什么,这个后果我能接受吗?当我构建 验证工具时,我利用了我可以生活在计算能力有限的小语言中的事实, 这样我就能用这些语言做非常丰富的事情。 好吧,我靠这个谋生,一直不错。不幸的是,我们遇到了这一点, 这个所谓的图灵阈值,好吧,超过它之后,一切都平等了。 当一切都平等时,我们无法做出任何有意义的区分,真的 无法做出有意义的区分。我不能依赖这个工具包,它 作为语言设计者、验证工程师等真的很有用。好吧,这就是 这篇论文的内容。如果这些对你来说没什么意义,那完全没问题, 因为我们将用接下来的49分钟来揭开所有这些。好了,现在 我想,如果你们允许我一下,我想花点时间告诉你们 一点我与这篇论文的个人历史。我刚开始读研究生时,我是 计算生物学家,我不幸地早期就取得了成功。 早期成功真的很糟糕,因为你知道,我的冒名顶替综合征严重发作, 我想,人们会发现我不懂任何生物学,我真的 需要尽快离开这个领域,对吧?晚期成功,好吧,你可以 边做边学。早期成功真的很糟糕。所以我环顾四周, 我说,我能做什么计算机科学的事情呢?我甚至不知道我 怎么找到这篇论文的,它就像掉到我腿上一样。我没有向Mateus要它,我只是 不知怎么地就出现了。我记得我读它的那个下午,那就像是我 一生中最神奇的日子之一。好吧,我仍然对那个 下午坐在休斯顿的公寓里读这篇论文有着柔和的余晖。所以这就是为什么 当Xion联系我时,我说我知道我要展示哪篇论文了。完全 诚实地说,我已经有25年没有真正读过这篇论文了,所以我开始 几周前读它,说你知道我需要准备一个演讲,读读论文 不会有害。然后我卡在了一个证明上,在某个时候我妻子 走过来对我说,你知道它叫‘我们爱的论文’,不是‘我们曾经 爱的论文’。但一切都好,一切都好,我又爱它了,我重新爱上了它, 这个机会帮助我重新爱上了它。好吧,最后一件
HN 上的讨论
> 如果宏可以实现任意语言特性 不完全是你的问题——其他人已经提供了类型系统作为宏的例子——但它们不能,它们只能做局部重写。例如,如果你还没有可变性或非局部控制流,你就无法表达它们;《论编程语言的表达力》[0] 相当理论化,但确实划定了宏能做什么和不能做什么的边界。它们是局部的,这意味着如果你想让你的类型系统成为宏,每个人都必须接受它。 [0] [LINK] 不过 [VIDEO] 可能对所提出的想法进行了有用的讲解 — hayley-patton, 2026-08
在编程语言设计中,我们倾向于区分全局分析和局部分析。类型检查和展开是全局分析的一个例子,而脱糖本质上局限于某段代码。因此,“能力”或“表达力”通常意味着某些东西无法在语法上“展开”;例如,虽然类型类会展开为显式字典,但它们仍然需要类型检查器的信息,因此被认为是编程语言的“真正”特性。另一方面,嵌套模式匹配可以表述为局部语法转换,因此它不会给类型系统或动态语义带来任何根本性的新东西。如果有人对形式化感兴趣,还有一场关于此事的精彩演讲[1]。[1] [VIDEO] — Hirrolot, 2024-05
值得阅读 Felleisen 的论文“论编程语言的表达能力”(或观看这个演讲 [VIDEO]),该论文认为,如果语言 A 有一个特性在语言 B 中实现需要全局重构,那么 A 比 B 更具表达力。 — fanf2, 2023-05
当然,添加 call/cc 并不能让你用程序表示更多可计算函数。但是,我们对程序的许多内部特性感兴趣,这些特性让我们能够有意义地区分那些在其他方面具有完全相同可观察行为的程序。我喜欢用协程作为例子,因为我有非常直接的经验,在具有或不具有协程的系统中编写具有类似行为的程序。到目前为止,我发现基于协程的程序更容易理解和扩展。Mattias Felleisen 写了关于比较图灵完备语言表达能力的开创性论文。如果你还没看过,值得一读![LINK] 不过,Shriram Krishnamurthi 两年前关于这篇论文的演讲可能更容易理解。[VIDEO] — Twisol, 2021-08
关于这个概念,有一个非常好的演讲“论编程语言的表达能力”[1][2],它试图为区分图灵完备语言的表达能力提供形式化基础。[1] [VIDEO] [2] 它所基于的论文 [LINK] — opnitro, 2021-03
相关视频
- 拯救旅行者1号!- Bruce Waggoner 在 !!Con 2024 · !!Con · 35:25
- 可视化四维数:四元数 · 3Blue1Brown · 31:50
- 如何探测额外维度 · PBS Space Time · 15:48
- 在1000核上运行Java - 硬件/软件协同设计的故事 · Google TechTalks · 1:12:01
- 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