|
会议之眼A类、CCF A类顶会，年度编程语言原理专题讨论会POPL 2020（Principles of Programming Languages）今日召开。大会收录的68篇论文已收集整理，作为合集推送，详情请阅读 软件工程顶会POPL 2020合集共68篇paper！ 大会录用率27.5%。 国内做编程语言研究的课题组没多少，前两天还闹出了中科院造假事件： 木兰编程当事人最新回应！ 谁为国产换皮透支信用买单！ 为了让大家更加了解这个领域和POPL这个A类顶会。我们转载了来自知乎用户啥玩意啊的一篇文章：浅谈编程语言研究与程序分析。谢谢支持！ 前言 在上一篇文章《浅谈国内高校编程语言教育》（简称《浅教》）中，我提到了国外顶尖大学的编程语言课程大都是由从事编程语言（Programming Languages，PL）研究的专门人才来讲授的。PL作为软件的核心技术，在软件开发效率、软件可靠性、安全性、性能等方面都提供了根本性的支持。PL是一个已经活跃了50余年的研究领域，作为软件创新的核心动力，如今仍是一个极有生命力且非常活跃的学科。 如《浅教》所述，在排名领先的世界名校中，但凡有点规模的计算机院系，几乎都会有PL方向的全职教授和研究人员，且越顶尖的大学，PL的研究越受重视。然而我国的情况并非如此，PL这样历史悠久且庞大复杂的学科在中国计算机学会并没有相应的专委（Again，形式化方法专委和软件工程专委无法取代编程语言专委，反之亦然），高校和科研院所也极少有专门注明PL为研究方向的教授和科研人员。因此，我想通过这篇文章向感兴趣的知友们简单介绍一下当前PL研究的整体概况和我所在的研究领域——PL方向下程序分析的研究现状。 A类会议 国际上编程语言有公认的四大顶会：PLDI、POPL、OOPSLA、ECOOP。（有点像Security里面的四大顶会Oakland、CCS、Usenix Security、NDSS）。 如果非要细分，PLDI和POPL要比OOPSLA和ECOOP好。这么多年，我通过博士、博后导师们的灌输+开会聊天了解到，欧洲人一般认为ECOOP稍好于OOPSLA（欧洲的PL研究人员特别多，很多知名编程语言的创始人也都来自欧洲如C++, C#, Python, Scala, PHP, ML, Haskell等），而北美人一般认为OOPSLA稍好于ECOOP。说ECOOP稍好的人一般持“OOPSLA由美国ACM主导，有钱有颜（资金和宣传力），且ECOOP（由欧洲AITO主导）被毙掉的文章一般会流向OOPSLA（ECOOP和OOPSLA作为姊妹会议同一年创办且deadline一前一后），所以OOPSLA有更多的submission和随之而来更低的录取率”。 我刚开始读博士时不太懂，单纯地认为录取率低的会议好于录取率高的，后来随着在research上逐渐成熟慢慢了解到一个会议的好坏要看一个领域自己的人对它的认可情况，这个会议的program committee比它的排名、会议规模和录取率更重要（后面也懂得顶会论文数量和citation并不能评价一个人的真正学术水平和影响，这个就不在此展开了）。打一个比方，超级女声和青歌赛，前者报名人数众多1000人（因为名气大能出名，能吼两句的都想试试）且录取率很低（进100，10%），而后者报名人数很少200人（起码都是稍微专业一些的）随之录取率也相对较高（进50，25%），但你不能因为说前者人数更多且竞争更激烈，就觉得进超女决赛的人比进青歌赛决赛的人唱歌更好吧。 近些年，OOPSLA和ECOOP为了扩大PL在应用方面的影响力，也鼓励录取一些偏软件工程（SE）等方面的文章，个人认为在录取的文章中，还是那些偏PL的文章的整体水平更高，因为PL人审PL类文章会更专业且更严格（当然凡事也都有例外，偏PL的文章也有差的而偏SE的文章也有好的）。 实际上还有一个非常好的PL会议，虽然不像ECOOP和OOPSLA那样general，但其名声和质量并不比它们差。这个会议就是ICFP，是functional programming领域的ECOOP和OOPSLA。 B类会议 继PLDI/POPL/OOPSLA/ECOOP后下一个档次的PL会议是ESOP（欧洲编程语言会议），这个是“纯”PL的会议（搞纯PL的人认为这个会议相当的好）。在我个人所在的研究领域program analysis（注：它是偏PL的基础分析技术即传统的静态分析，例如pointer/points-to/alias analysis等，而并不是利用这些基础分析技术开发的偏SE应用的software analysis）也有一些和ESOP一个档次的“类”PL会议。 这个档次的“类”PL会议包括静态分析会议SAS（VMCAI和SAS一个级别，但搞抽象解释的朋友，他们很多都投VMCAI，告诉我他们认为SAS稍好于VMCAI），软件工程会议ISSTA（还有一个稍偏PL的SE会议是FSE，但FSE比ISSTA更好些，一般认为非同一级别），编译会议CGO（CGO和CC一个级别，但近几年CGO要稍好于CC），再有就是更小众的（在分析领域一般认为虽属同一档次但比前面的会议稍差那么一点的）内存管理会议ISMM，还有偏嵌入式的LCTES和EMSOFT等。 C类会议 再下一个档次的“纯”PL会议是APLAS，它被认为明显好于同属一个档次的其他“类”PL会议，如SOAP（是个非常好的workshop有很多不错的分析文章）、SCAM、SAC的PL track（SAC的老牌高质track）等。 最后提一下PL的期刊TOPLAS，公认为PL最好的期刊，挺难投的（一年貌似就十几篇），它的submission来源主要集中在PL的四大顶会（一般是把会议文章内容扩展30%左右）。 内容 PL学科庞大，结构复杂，让我这么个搞PL分析的说清楚整个PL都在研究什么是不可能的（估计这辈子都说不清楚）。但是简介一下概貌还是可以的。我觉得按照如下三个方面对PL的研究进行分类是相对容易理解。 1. 纯PL，即关于PL本身的设计。例如，
2. PL支持环境，即支撑PL的编译和运行系统。例如，
3. PL应用，即利用PL的语法语义等知识对PL编写的程序展开的一系列应用。例如，
上述分类只是一个框架，实际上并没有展开，因为它很难展开，太庞杂了。例如，纯PL中的第一条“语言设计和拓展”，就这一点就有各种编程范式，比如，object-oriented, functional, logic, constraint, domain-specific, asynchronized programming等等。因此针对PL的研究内容我就止步于此，大家有一个大致了解就好。 下面我针对上述各PL分类方向的研究现状做一个简单的总结。 1. 纯PL的研究相比于十年前已经安静很多了，但是大家也不要低估研究纯PL的这些人的数量，他们大多分布在世界顶级大学和软件公司，如今各种纯PL技术仍活跃在各大PL舞台，主要是POPL，ECOOP，ICFP和ESOP，PLDI和OOPSLA也有一些。我个人认为纯PL圈子的人有如当年占据计算机领域金字塔尖的那些搞算法、逻辑、复杂性的研究者们，虽然如今力量日渐消退，但我依然认为他们是引领PL乃至软件领域发展的一股中坚力量，值得尊敬。 2. PL支持环境实际上和编译领域、系统领域甚至体系结构都有一些关系。由于上层编程语言本身就是各种类型，那么支持它们的编译和运行时技术更是种类繁多，层出不穷。就凭当今主流的那些编程语言，也可以让这个方向的研究一直持续下去，毕竟使用它们的金主们（各大软件公司）为了它们编写的程序有更好的可靠性和性能也会给这股研究力量多多支持的。此外还有各种编译和系统方面交叉人才的加持，我相信这个方向还会有很多实用的技术被创造出来。 3. PL应用举的这三个例子，如今在PL的热度是一年比一年高，主要原因是如今的软件越来越复杂了，对于可靠性、安全性、性能和编写效率都有新的要求，提出了新的挑战，有很多实际且有趣的问题亟待解决，甚至这些技术的展开和探讨对于编程语言的设计也会有很大的影响。如果你是一个research新人，对PL有点兴趣但不知道研究什么好，我建议你入PL应用的坑，因为我认为它至少在未来五年依然会是一个很活跃的研究方向（原因如上所述）。 接下来，我们来聊聊PL应用中最庞大、最火热的分支之一，程序分析。 程序 程序分析在学术界的重要性！ 程序分析可以看成是一个交叉的研究方向，因为你会在PL以外的其它不同计算机领域的会议上看到程序分析的topic。例如，软件工程如FSE, ICSE, ISSTA, ASE等；系统领域如 OSDI, SOSP, ASPLOS, EuroSys, ATC等；安全领域如Oakland, CCS, NDSS, Usenix Security等等。造成这种交叉性质的原因不难理解：程序分析是一种方法技术，目的是分析出程序在可靠性、安全性、性能等各种方面的表现和问题，而各领域的程序都是用编程语言写的，且都或多或少地有上述方面的分析需求，因此不同领域对于程序分析的广泛兴趣便不足为奇。尤其是近些年，程序分析在上述很多会议的Call For Papers里都会被单独列为一项愿意接收的topic，比较火热。 程序分析在企业界的重要性 程序分析不只在学术界占有重要席位，近些年来也越来越受到企业界的青睐，原因我在之前简单提到过，因为当今的软件越来越复杂，在可靠性、安全性、性能等方面提出了新的要求和挑战，这些都是传统技术（如软件测试等）很难驾驭的。据我所知，国际知名的大公司都有专门的程序分析研究或开发组，例如Microsoft，Google，Oracle，Apple，IBM，Facebook、Uber、华为等等。随着人们逐渐意识到程序分析的重要性，专门研发程序分析技术的公司也越来越多，例如Coverity（被收购），GrammaTech，Semmle，SourceBrella（源伞）等。 如上所述，程序分析无论在学术界还是工业界都扮演着重要的角色。程序分析如此重要，它到底是个啥呢？接下来，我们来简单看看什么是程序分析。 什么是程序分析 程序分析虽有静态动态之分，但从PL的角度我们一般关注的是静态分析（static analysis）。简单说来，静态分析要回答的问题是 我想知道在任何输入下，整个程序或程序的某一点是否能满足某种条件或特性？ 但是，程序的输入可以无穷无尽，程序到达某一点的路径可以根据输入变化莫测、不胜枚举，如何将所有情况都考虑周全最后得出一个正确的（sound）结论呢？为此，我觉得静态分析技术的核心可以围绕两个关键字展开：Abstraction和Over-approximation。
程序在动态执行时，有各种不同类型的动态值，例如int类型的 1, -2, 350，String类型的 “a”, '007', 'Hello' 还有各种referenced的concrete object（比如你在一个死循环里放一句new A()你想想运行时会有无数个A类型的concrete object被生成直到吃满你的内存），如果你想用有限的内存资源来分析这些无限的动态值，你首先需要把它们抽象起来，即Abstraction。例如只有一个int类型的抽象值（或一个整数int、一个负数int、一个0，共三个抽象值），一个类型的String值，一个new A()语句只生成一个抽象的对象，即（和上面concrete object对应的）abstract object。怎么抽象是可以调节的，抽象方式不同，静态分析的精度和速度便会不同。
程序在动态执行时，根据输入的不同，可能会走各种不同的路径，随着程序规模和复杂度的增加，这些路径也会无穷无尽，最终不能用有限的空间来枚举每条可能的动态路径下的不同值（路径爆炸），进而也无法知道程序的某一点的值是否还满足某些条件。为了用有限的空间和时间来“枚举”无限路径下的各种可能值，我们需要保守近似over-approximation。如下所示 if (e) x = 1else x = 0@Label A假设我们想知道程序Label A这一点x的值是什么？想象一下如果我们可以枚举路径，我们可以得到很精确的答案，即在e == true时x = 1 （路径1）；在 e == false时x = 0 （路径2）。然而如果程序很大且复杂，我们没法枚举每一条路径（路径爆炸）下的值。over-approximation是在某些程序位置或区域保守地近似不同执行路径（executions）下的值。如在Label A，我们可以说无论走哪条路，x要么是1要么是0。这是sound（safe）的结论，尽管不精确，但是如果x只要不是负数就可以做某种优化，那么这样的结论就是有用的。对不同路径抽象的粒度是可以调节的，粒度不同（如context, flow, path-sensitivity），静态分析的精度和速度也会不同。 实际上真正的静态分析要复杂的多，因为它要针对不同编程语言不同语法下的不同语义来合理的抽象近似程序在每一个语句下的动态运行结果（可以想象成静态地抽象一个解释器）。因此静态分析是和编程语言紧密相关的（需要深入准确地了解语言的语法和语义）。如此，我再说程序分析（静态分析）实际上是偏PL的研究方向你就更容易理解了。 如今，软件工程、系统和安全方向的很多程序分析都是利用基础的静态分析技术和结果，结合程序和问题的特点，进行更high-level的分析，比如查到更有趣的bug和安全漏洞，或更好的帮助优化或理解程序等等。既然基础静态分析和PL联系的这么紧密且如此重要，我觉得有必要再深入地了解一下它。接下来，我要介绍基础静态分析中最核心、最重要的一个分支（之一），也是大家经常在各种程序分析论文和程序分析工具的代码、文档和注释中看到的指针分析（pointer analysis），又名指向分析（points-to analysis）或别名分析（alias analysis）。 指针 提到静态分析，都应该听说过指针分析，这个奇葩研究方向居然延续了近40年而且长盛不衰，至今仍活跃在各大PL相关会议当中。原因很简单，它太重要了。 指针分析并不是“分析指针”，如果不好理解，你可以用它的另一个名字“指向分析”来记，顾名思义，给定程序的任何变量或引用p，指向分析在compile-time（静态）回答p都可能指向哪些值（实际上也是回答静态分析的问题）。既然知道了p1和p2都指向什么，如果p1和p2的指向有交集，就说p1和p2互相alias（alias对很多sound的分析是必须的），因此指向分析也叫别名分析即alisas analysis。 1.指针分析的重要性 为什么指针分析如此重要？就像几乎所有指针分析论文中描述的那样，指针分析可以认为几乎是所有静态分析的基础，因为它可以被用来构建全局的程序控制流（Interprocedural control flow graph, ICFG）和方法调用图（call graph），且所有全局的程序静态分析都需要这些基本结构，与指针分析提供的指向信息和别名信息来构建自己更high-level的静态分析。 我上面提到的那些大的软件公司尤其是IBM、Oracle等都有自己专门的指针分析的团队（ @TwoFrogs的源伞公司也是研发指针分析的，国内首屈一指），很多程序分析的开源或商业框架也都是用指针分析搭建起来的。40年来各种PL相关会议上的指针分析论文层出不穷。近十多年来，指针分析的重点也逐渐从以前的C语言侧重到面向对象语言（这个不难理解，毕竟如今的应用软件的主流语言是面向对象），占据了近些年来各大PL相关top会议指针分析topic的更多席位。既然面向对象（OO）指针分析（主要是Java）在近些年相对更受关注，接下来我们就简单聊聊它的发展进程，我觉得下面的梳理对想入坑或感兴趣的同学会有所帮助。 2.OO指针分析的过去和现在 OO的指针分析一般以Java为主，现在的很多Android的静态分析技术和工具也都是基于Java指针分析的。接下来，我通过几个关键人物和他们开发的关键技术或工具来帮助梳理Java指针分析的研究进程。故事从枫叶国说起： 加拿大麦吉尔大学的Laurie Hendren教授（早期指针分析领军人物之一）的研究组在1999年以论文的形式发表了Soot，Soot直到今天仍是最流行的针对Java的静态分析器。 在2009年之前，还有几个人需要提及。 首先是Ana Milonova（现美国伦斯勒理工学院副教授）。Ana是Barbara G. Ryder（早期指针分析的领军人物之一，现弗吉尼亚理工教授）的学生。Ana在2002年提出了object-sensitivity并验证用它作为Java的context会带来更好的分析精度甚至速度。这就打破了一直以来从C语言静态分析那里继承而来的基于callsite的context-sensitivity的局面。这个工作在业内影响力很大，四大Java指针分析框架Doop，Wala，Soot，Chord都有object-sensitivity的实现，因为它是Java指针分析精度提升的必备技术。 2009年后Java的指针分析主要有以下几个国际团队在做， 希腊雅典大学的Yannis Smaragdakis教授， 注：值得一提的是，以上除了Bodden和Naik教授的团队，其余几个团队也做过或正在做C/C++的指针分析。实际上在我们国内也有做过C/C++的指针分析团队，那就是中科院计算所的冯晓兵教授和李炼研究员。关于C/C++的指针分析如果大家感兴趣可以访问以上几个团队的主页，外加UCSB的Ben Hardekopf教授和印度理工的Uday Khedker教授。 2009年后，Java（或OO）指针分析领域的最核心人物当属雅典大学的Yannis Smaragdakis教授，接下来我们简单了解一下他的工作。 Yannis Smaragdakis教授原来是美国佐治亚理工和马萨诸塞大学的教授，后来在2011年左右回到了希腊的雅典大学任教。他2009年在OOPSLA发表了当今最先进的Java指针分析器Doop，然后持续地在各PL顶级会议POPL，PLDI，OOPSLA，ECOOP发表大量的指针分析文章。我个人认为目前为止Yannis对指针分析最大的贡献有两个，一个就是Doop这个指针分析器本身，另一个是于2011年在POPL发表的一篇文章。这篇文章从新精确地解释了Ana Milanova在2002年提出的object-sensitivity的定义，以消除从02年到11年期间关于object-sensitivity的有分歧的理解：即当context层数大于一层时应该用哪些object来做context。此外这篇文章又提出了一种新的context技术叫type-sensitivity（精度比object-sensitivity稍差但是速度快很多），这对于大程序分析不scalable的问题起到了很好的缓解作用。 2016年以后到今天，Java指针分析的关键人物是我们的一位知友Tian Tan @甜品专家（现在是丹麦Aarhus大学Anders Møller教授的博士后）。 Tian在2016发表于SAS的工作改变了20多年来context-sensitivity一直使用连续context元素的局面，巧妙地避开了对分析精度没有用却又影响分析速度的context元素。据我所知，上面提到的Ondřej Lhoták，Yannis Smaragdakis还有Mayur Naik教授在不同场合都对这项工作有很高的评价，此外，上面提到的Hakjoo Oh教授团队在今年的OOPSLA，就是用机器学习的方法尝试了Tian的这个工作。Tian从2017年开始又陆续在PLDI、OOPSLA和FSE等顶会发表了针对Java的一系列指针分析工作，感兴趣的同学可以去他主页看看。 关于Java的指针分析我就说这么多，接下来简单提及一下另一个OO语言JavaScript的指针分析研究团队。值得注意的是，国际上有很多团队做JavaScript的程序分析，但是做JS指针分析这种很基础的并不多。主要有以下几个团队： 丹麦Aarhus大学的Anders Møller教授 在这里我就不对JS的指针分析展开了（它主要的一些技术还是来源于Java的指针分析，但是JS的一些神烦的特性还是让搞JS指针分析的人吃了不少苦），有兴趣的同学可以访问上述团队的主页。 总结 这篇文章从介绍PL会议入手，简单描述了哪些人是从事PL研究的，他们都研究些什么，这些研究的现状怎样。接着，介绍了PL研究的一个重要分支——（基础）程序分析，包括什么是程序分析（主要是静态分析）以及为什么程序分析在今天越来越重要。最后，介绍了程序分析中最核心、最重要的技术（之一）—— 指针分析，包括指针分析的概念、重要性以及它发展的过去和现在。希望这篇科普性的文章让你对PL的研究和程序分析技术都能有所了解。 过去的50多年里，针对PL的research从来没有间断过，也一直保持着生命力，它成就了如今软件的琳琅满目，也影响着未来软件的生产力和创新力。作为信息时代崛起的大国，不应该在如此重要的研究领域掉队，衷心期待我国编程语言领域科研的进步。 |
|
|
