“类型驱动的程序合成” by Nadia Polikarpova

"Type-Driven Program Synthesis" by Nadia Polikarpova

频道:Strange Loop Conference · 时长:39:40 · 发布:2018-10-16 · 播放:14723

在 YouTube 观看

简介

Nadia Polikarpova 在 Strange Loop 的演讲,关于由细化类型驱动的程序合成,如 Synquid。它展示了如何将丰富的类型规范转化为经过验证的可执行代码。

HN 为什么推荐

HN 指出它作为对程序合成是什么以及类型能为其做什么的激励性介绍。

对于程序合成是什么的激励性演讲和解释,试试这个 — HN, 2019

编程语言设计 · 逻辑与形式化方法

中文字幕节选

大家下午好,欢迎来到 Strange Loop,我叫 Nadia Polikarpova 我是加州大学圣地亚哥分校的助理教授,我 非常激动能来到这里,和大家分享一些我一直在 和我的学生及合作者所做的研究。我们研究的目标 是自动化编程,就像汽车工业那样, 通过多年来提高自动化程度,我们能够更快、更 可靠地生产汽车。在软件行业,通过提高我们 编程语言中的自动化水平,我们能够以更低的成本和更少的 错误来构建软件。在我们开始之前,先澄清一下,别对我发火,我并不是 想要取代程序员的工作,恰恰相反, 我希望程序员能够专注于工作中真正有趣的部分, 而不是被埋没在那些底层细节里。让我用一个 非常简单的例子来说明这个想法。假设我想写一个程序,将一个 值插入到已排序列表中的适当位置。更准确地说,我的程序 接收一个值,我们叫它 X,以及一个列表,我们叫它 XS,并返回一个列表 YS,该列表是有序的,并且包含 XS 的所有元素 以及 X。好的,我可以用函数式语言将这个程序实现为 一个简单的递归函数,我们叫它 insert,它接收两个参数 X 和 XS, 它做的第一件事是对输入列表 XS 进行模式匹配,以判断 它是空列表(我们称之为 nil),还是非空列表, 即是否有头部和尾部 在第一种情况下,我们可以简单地返回一个包含 X 的单元素列表, 在第二种情况下,我们必须将新元素 X 与列表的头部进行比较, 如果 X 小于等于头部,那么我们就找到了正确的位置, 可以直接将 X 放在 XS 前面;否则,我们就必须对 尾部递归调用 insert。好了,这并不太难,只是一个简单的 8 行 程序。但如果我想用 C 写同样的程序,我就必须做 更多的工作,对吧?为什么呢?因为与 C 不同, Haskell 为我自动化了很多东西。是的,我称它为 Haskell,尽管它 并不是真正的 Haskell。我整个演讲中将使用的语言是一种 简单、极简的函数式语言,具有类似 Haskell 的语法,但 有一些差异,希望这些差异是不言自明的。所以这种 函数式语言,我们叫它 Haskell,为我自动化了一堆东西,比如 指针操作和内存管理等等。所以如果我想 用汇编语言写这个程序,我就必须做更多的工作,因为即使是 C 也为我自动化了一堆东西,比如在函数之间传递参数和值、 访问内存等等。所以从这个 图表可以看出,在过去几十年里,编程语言已经取得了很大的 进步,现在的东西比以前自动化程度高得多。但 此时让我们问自己:这就是终点吗?Haskell 真的是创造的 巅峰吗?在本次演讲中,我 将和大家分享我对这个问号可能代表什么的愿景, 即编程语言中下一个很酷的东西可能是什么。 更详细地说,我将论证编程语言的新酷特性是 带规约的编程,而程序合成技术 是使其成为现实的关键。最后,在 我演讲的最后部分,我将讨论这种程序合成技术如何 与我们的编程语言集成,以提供这种我称之为

HN 上的讨论

哦是的,你让我想起了之前在Strange Loop看到的一个很酷的演讲。不是关于AI部分,而是关于Haskell中的程序合成:Nadia Polikarpova的“Type-Driven Program Synthesis”[VIDEO] Polikarpova教授更多项目和论文的链接:[LINK] 我认为这是她在演讲中讨论的主要项目之一:[LINK] 编辑:本来还想提这个,我觉得它存在的时间更长一些,不过我从未在生产中使用过:[LINK] — ddellacosta, 2024-03
关于TLA+的介绍和动机,我推荐Hillel Wayne的演讲《Everything About Distributed Systems is Terrible》[0],以及他在博客上写的关于TLA+的任何内容。我认为,一旦你决定要深入学习,跟着TLA+视频课程学习是非常全面且易于理解的[1]。当你开始为自己的系统编写规约时,你会发现TLA+ Hyperbook是一个有用的参考和指南[2]。它有许多示例和项目可供练习。最终,如果你决定值得深入,可以阅读《Specifying Systems》这本TLA+的教科书和圣经[3]。程序合成领域有很多研究,并且开始显示出有希望的结果。我想说,虽然研究已经进行了很长时间,但对于工业应用来说仍然相当新……关于程序合成是什么的激励性演讲和解释,可以试试这个:[VIDEO] [0] [LINK] [1] [LINK] [2] [LINK] [3] [LI… — agentultra, 2019-03
这是一个活跃的研究领域。搜索“程序合成”。我们正在进步,但当前的状态……还不算令人惊叹(尽管有点酷!)。参见[1]的交互式演示示例和[2]的相应演示。[1] [LINK] [2] [VIDEO] — kilburn, 2021-06
> 良好的规范通常是在这样一个层次上编写的:从中生成可执行代码往往是不可判定的,并且在实践中几乎总是难以处理。那么像 Idris 这样的现代依赖类型元语言,以及像 Nadia Polikarpova 在 Synquid 上的工作这样的程序合成器呢?类型驱动的程序合成,作者 Nadia Polikarpova(StrangeLoop 2018)[video] [VIDEO] MIT Comcom:Synquid 程序合成器,以及更多用于 Web 的命令行工具 [LINK] Idris 软件基础 [LINK] — espeed, 2018-10

相关视频