ECUG Con 2015｜许式伟《一周一语言》

1月22日，ECUG Con 2015在北京新疆大厦举行。七牛云CEO许式伟做了主题为《一周一语言》的演讲，他首次对于qnlang（内部已经改名qlang，即Q语言）进行详细的分析。作为与Go语言交互最便捷的语言，Q语言在很多场合都能够辅助完成对系统的灵活定制需求。以下是演讲实录。 许式伟：我今天的演讲话题叫一周一语言，这个议题坦白来说是标题党，其实我重点不是讲这个语言，而是讲这个语言的基础，也就是我在网上提过的一个叫TPL的东西。   qlang七天诞生记 今天要讲的语言叫qlang，也就是Q语言。是在没有依赖第三方，一步步根据Go标准库写出来的。事实上它的诞生真的是在七天内搞定的，这七天我每天的睡眠时间不超过三个小时。 第一天（11.27） 实现一个TPL的基础版本，实际上2007年我写过一个C++的版本，大家在网上可以看到。我曾经在多个场合说过，我个人从C++转到Go语言之后唯一不能割舍的是TPL。所以我在Go里面做这个非常有激情，这是一个长期以来积累的夙愿。 第二天（11.28） 我在TPL的基础上实现了解析器引擎，开始叫计算器引擎，其实我最后发现就是一个解析器引擎，好处是我可以做任何一个语言，让它由这个解析器解释执行。在这个基础上实现一个支持四则运算和函数调用的计算器的Demo。这是很基础的，但是这个计算器是很好的基础，因为我后面写的qlang，你可以认为它是从这个演化过来的。 第三天（11.29） Go语言标准库有理数、复数，所以我又写了三个不同的计算器，一个是有理数，就是说任意的两个数相加以后还是一个有理数，计算的精度特别高；还有一个是复数，最后一个是变体(variant)。所谓变体是指这个计算器支持多种类型的数据。前面几个计算器都只支持一种数据类型，到了变体计算器(vcalc)后我可以同时有整数、浮点、字符串等等。这样我们就有了四个计算器。然后我在支持变体的版本中加入了变量。有了变量以后看起来更像一个语言了。 第四天（11.30） 在变量的版本里引入了map、slice的支持。支持了对象成员的访问，支持模块，当然最重要的是支持函数定义。在这时我们就可以自己定义函数了。 第五天（12.1） 支持函数调用(function call)、闭包(closure，可以引用父函数的变元)，重构 vcalc为微内核设计，除语法结构外，所有功能都做成插件式(plugin)，将功能分解到 builtin、math、strings 三个模块，可随意组装。支持boolean 运算，支持 if、switch、for 控制语句，将 vcalc 改名 vlang (V 语言)。 第六天（12.2） 改名为qnlang语言，并明确该语言的优势为与 golang 的互操作性，表现在 golang 的社区资源可以全部为我所用，无需包装；潜在市场：如游戏领域可以取代lua、python、javascript，作为内建脚本。语言特性上，主要是增加了类的支持。支持定义一个类，new一个对象，调用成员方法或函数。 最后一天（12.3） 支持了构造函数、可变参数，支持多返回值。其实不是支持多返回值，因为返回值是Go语言的多个值，到了qlang变成了variantslice。但是variant slice可以赋值给多个变量，所以看起来像是支持了多返回值。最后我们也支持defer。   TPL(Text ProcessingLanguage)详解 以上这些东西的背后都和TPL有关系，所以我们今天重点讲一下TPL。 文本处理语言 什么是TPL呢？简单来讲它是文本处理语言，我将其定义为一个语言，原因是因为它有一个自己的文法。我在C++里是用C++的语法表达了TPL的文法，因为C++有这样的灵活性，我们可以重载各种操作符。但是在Go语言里面我们没法这么做。所以TPL确确实实定义了一个类BNF文法的语言。这么这样的文法是谁负责解释呢？是TPL本身。TPL首先解释自己的BNF文法，来理解用户表达的语义，把它编成一个TPL的内部表示，再以此来解释用户定义的语言，比如像qlang。 TPL本身的业务是负责把文本进行解析执行，它会有解析器，或者说文本进行一个抽取，这是它的基本功能。它是怎么工作的呢？和大部分的文本处理模型一模一样，分两个阶段，一个是Scanner（词法分析），另外一个是Parser（语法分析）。词法分析是把文本流变成Token流，变成一个一个语法的单元。语法分析是把Token变成DOM 或action 来执行。 我刚才说TPL其实是一个语言，看一看这个语言的文法是什么样的，如图1代码所示：

图1

和编译原理中的差不多，但是又有些细节的不同。编译原理喜欢把G*这样的写法，把星号放在后面，但是我们这里用*G，因为我们常规语言操作符喜欢用前缀。其中标红的部分，我把它叫做标记(mark)，是用来和Go语言打交道的，最后解析的时候这里会转为一个回调。这整个的代码非常短，但是真的很强大。 语法解释 我们解释一下这个文法，如果学过编译原理很容易理解，但是我们还是详细的讲一下。首先是基本Token。因为词法分析过程会把输入变成Token流，Token流中的这些Token，就是基本Token。基本Token一般是用大写开头的符号，比如说FLOAT、IDENT，或者用单引号或双引号括起来的常量，这两种都可以。比如这里例子中的加减乘除是用单引号括起来的常量表示。 除了基本Token以外，剩下的就是一些复合规则了。

• 第一个是*G，反复匹配规则G，直到无法成功匹配为止。匹配0次到N次都可以。
• 第二个是G1 G2 … GN，匹配的文本要求满足序列 G1 G2 … GN。注意这些规则中间没有操作符，当然你也可以认为空格就是操作符。
• 第三个是G1|G2|…|GN，要求匹配的文本满足规则 G1 G2 ... Gn 中的任意一个。
• 第四个是G1 % G2，这个大家可能会有点陌生，我把它叫列表运算。从规则来看它等价于G1 *(G2 G1)，也就是 G1 G2 G1 G2 … G1 这样的序列，G1和G2不停交替，G1始终比G2多一个。这个典型的例子就是函数的参数列表。这也是为什么我们把它叫做列表运算的来由。
• 第五个是G1 %= G2，它叫可选择列表运算，等价于 ?(G1 % G2)。规则上来讲是和列表运算类似，只是允许列表为空。
• 第六个是标记 G/mark，它用来和Go代码建立连接，让Go语言处理相应的标记。

这样解释完了以后，对着前面的例子，这个文法看起来就容易理解了。我们描述的这一系列规则就构成了类BNF文法。 解释器 有了这样的文法以后，我们就可以由解释器来解释执行。当遇到mark时做一些回调，在解释器中，这表现为执行某个动作。解释器要求要求使用方要有一个Fntable(函数表)，这样一道一个mark时去Fntable中查，如果有就去执行，没有就报错。解释器另外一个要求是要有一个Stack(堆栈)，但是它是可选的，如果这个解释器解释过程不需要堆栈就可以没有。有堆栈的好处是，如果fntable中的函数第一个参数不是interpreter实例，就基于stackmachine来执行动作。我们看一下计算器的实际代码。网上有开源的版本，是qlang写的版本，和Go版本的机理是一样的。前面是一系列的很普通的函数，我们跳过。再下面是Stack，这个实现也很常规，大家都知道Stack是怎么回事。再下面是Calculator类，也就是解释器。这个类实现了fntable和stack这两个方法，分别返回了函数表和堆栈。最后是fntable表。这一这个表里面的函数，可以是任意的普通数学函数，比如sin，cos都可以。这样一个计算器就出来了。 以上就是解释器。有了这个解释器引擎以后，形成任意一个新语言代码量都不会很大。包括我们后面的qlang，也只有1200行左右的代码。 抽取器 解释器并不是TPL的唯一用法。刚才我们介绍TPL的时候也提到了DOM抽取。完成这个事情的是抽取器。所谓抽取器，简单来讲就是从任意一个文本里抽取大家感兴趣的内容。刚才我们讲在解释器里面mark是一个个要执行的动作，在抽取器这里语义就不是了，它是DOM中的标签。我们根据DOM结点的特点，把mark分成这样四类：

• 第一类是叶结点（leaf mark）。它的名字必须是 xxx_Int，xxx_Float，xxx_String，xxx_Text，xxx_Char这样的。
• 第二类是叶数组结点（leaf array mark）。它的名字必须是xxx_IntArray，xxx_FloatArray，...，xxx_CharArray这样的。
• 第三类是非叶结点（node mark），它的名字必须是xxx_Node这样的。
• 第四类是非叶数组结点（node array mark），它的名字必须是xxx_NodeArray 这样的。

这里 mark 的名字有些特别，前面 xxx 是结点名字，后面Int, FloatArray 这些其实是类型，类型是用来协助抽取器如何从文本里面抽取信息的。 我们来看一个例子，用TPL的抽取器如何抽取一个浮点数组。如图2代码所示：

图2

我们先看抽取的类BNF文法。和前面解释器用的类BNF文法是一模一样的，只是mark的命名不太一样。doc是整个语法的根，FLOAT代表浮点数，列表运算然后紧跟一个逗号，这个要匹配的东西很清晰，就是一个浮点数列表，中间以逗号作为分隔符。拿这个抽取器文法去抽取后面的文本`1.2, 3,4, 5.6`，抽取出来的DOM是{“items”: [1.2, 3,4, 5.6]}。 理解了这个简单的抽取器样例后，我们看看图3，这是一个相对复杂的例子：

图3

前面我们介绍了计算器的实现。但实际上计算器的实现其实有两种方法。一种是我们刚才用的解析器，第二种是基于抽取器。也就是先用抽取器把文本解析成DOM，然后再依据这个DOM再去解析执行。 tplconv 工具 在抽取器基础上我还实现了一个tplconv工具。这是一种万能的工具，是它能实现任意两个文本格式之间的变换。如何做到的呢？下面是一些例子： –       tplconv class.cpp •   C++ => DOM => Json –        tplconv -ojson.htm test.ints •  IntArray=> DOM => Html –       tplconv class.cpp | jspt class.php •  C++ =>DOM => Json => Text tplconv 工具原理 首先是输入文件经过TPL的抽取器，转为一个DOM树。然后对DOM进行格式化输出，有以下这些可能性：一种是内建的，比如json(默认是这个)。第二种是用html/template这个Go标准库来生成Html。第三种是对接jspt。jspt是我在2007年发明的词，全称是 Json PHP Transformation，它的名字其实是对应 XSLT 的。这样的好处是可以用PHP这样拥有强大的格式化能力的语言来做输出。实际上这个格式化输出可以有更多，后面还可以不断地添加。 有了tplconv，我们看到这个时候，TPL可以对接任意输入，而且它是插件式的，任意的文件格式都可以用TPL的抽取器文法来抽取信息，然后在格式化输出的时候也是插件式的，最终达到可以做到任意的文本格式输入，任意的文本格式输出。其实这个tplconv在C++版本的TPL里面也有，但是问题是C++TPL抽取器是编译执行而不是动态解析，所以输入没有办法做到插件式。现在因为TPL抽取器是真正的在运行时解析执行，所以tplconv可以做得很强大。 TPL总结 首先，TPL用类BNF文法来描述要处理的文本格式。描述完了以后可以有两个选择，这两个都是属于TPL的扩展模块：第一个是解析器，基于它我们可以轻松实现一门语言；第二个是抽取器，可以实现从文本中抽取感兴趣的信息构成DOM树。最后，我们实现了tplconv工具，可以完成任意的文本格式转换。   qlang 介绍完TPL以后，我们把话题回到qlang的这个事情上，一开始它确实只是一个demo，做着做着我把它做成了一个语言，因为我觉得它有很大的魅力。为什么这样讲呢？首先是它真的和Go的交互特别好，任何Go的代码在qlang里面基本上可以无缝执行的。这让qlang和Go语言有非常好的交互基础，你可以非常容易基于qlang来完成对Go语言程序的定制化。其次是它的语法和Go很像，非常精简。从现代语言的层面来讲，它的表达力也很强大。所以我个人认为它是有前途的，这也是我不是把它当demo，而是往语言角度去做的原因。 实现思路 大概讲一下qlang的实现思路，实际上和前面看到的计算器没有本质上的区别，唯一的差别是我们对mark进行了扩展，内建了两个mark：_mute和_unmute。原来所有的mark都会对应执行一些动作，但是一旦执行了_mute以后这些mark就不再执行动作了，被忽略了。当然前提是所有非下划线(_)开头的mark指令都被忽略，下划线开始的还是照常执行。这样的好处是有些代码是不需要一上来就执行的，比如说函数的body，if语句的body，所以这种情况下我们可以用_mute把代码禁止执行，然后把代码先记录到一个变量里面压入堆栈。 有了这两个以后，本质上理解了calc的实现，那么qlang的实现其实也没有什么大的区别。无论多复杂的语法，像if，像函数，所有的信息你都可以理解为参数，这些参数收到以后压入堆栈，整个语句结束的时候再执行一个总控的动作，由它来判断整个执行逻辑应该怎样。 后续优化思路 第一个优化思路是，我们将qlang从纯解释执行转换成基于字节码执行。这个已经完成了。这个实现也不费事，只要定义好指令，无非是把代码解析执行改为翻译成相应的指令而已。第二个是优化变量的访问速度。在编译执行的情况下，我们就可以算出每个变量的地址，变量的地址可以事先安排，而不是通过map查询来做。第三个是上下文的优化，比如说常量表达式的编译期计算、精简冗余指令。第四个是TPLParser本身的优化，但是它不是非常关键，原因是编译过程通常只发生一次，但是执行器会反复执行代码。所以前面三个的优化更加重要一些。 选择器 我们很快的过了一下qlang是如何去做的，我没有非常详细的展开讲，因为它和计算器没有什么本质的区别。qlang的使用场景我觉得可以作为Go语言的嵌入式脚本，对go程序进行定制。比如说这是我在七牛内部实现的一个使用场景：它通过qlang把DOM变成另外一个DOM，也就是信息抽取。 我们看一下实际的案例，大家都可能听过XPath，但是我个人认为XPath不足以满足信息抽取的需求。我把这个东西叫做选择器，因为本质上来讲我在上面做的是选择节点，然后重构节点位置，变成另外一种DOM的形式。 一个常见的信息抽取工具是XSLT，曾经在XML比较流行的时候大家会听到。它最初可能没有想着成为一门语言，但是后面的功能越来越强大，最后变成了语言，拥有语言所有需要的元素。所以我认为XPath不满足信息抽取，所有的选择器最终会变成一门语言。 图4是qlang中的选择器的一个样例。这个样例是抽取github用户的repo列表。它输入是doc，也就是整个htmlDOM。输出是repo列表，每个repo会有用什么语言，repo地址、标题、从哪里fork过来的、最后一次更新的时间是多少等等。它的语法还是比较接近于常规选择器像XPath。

图4

图5

我想证明一下选择器最终会变成语言，所以我要讲一下图5这个例子。前面的例子是比较简单的，它的语法看起来对语言特性的需求不大，只要有选择节点的文法就可以了。但是图5这个例子里面有非常多的运算，还涉及了字符串的处理。为什么呢？因为我们在比较复杂的网站里面抽取东西的时候，往往会要解析文本，在某个非常小的单元里面。这个代码是投融资信息的网站，上面会有很多投资信息，哪家公司被什么机构投资了，投了多少钱之类的。里面复杂的地方是第几轮和投了多少钱在网页展示的时候被放到了同一个字符串里面。这里我们就需要把它分解开。最后我们抽取出来的是这个项目的公司名字、网站地址和公司被投资的时间、第几轮、多少钱、投资机构是谁这些信息。这样的实际业务场景就导致了选择器最后不得不成为语言。 qlang应用场景 qlang的第一个应用场景是网络爬虫。我们今天假设我们要做去哪儿网，我们要抽取不同航空公司网站的航班信息，不同网站的结构信息肯定是不同的，航空公司非常多，这些逻辑我们可以做在爬虫的脚本里面实现，而不是直接在爬虫Go程序里面写死。而且同一个网站的不同时期的页面结构也会不同，考虑到这些内容，我们需要用一个脚本去描述网站的页面信息，qlang是非常适合这样的场景。 第二个场景是网游，网游里面游戏的策划是不太稳定的，尤其是生命期比较长的网游。网游通常需要不停的调整故事的策划，或者快速上线一个新的故事，这样我们就要经常去改游戏服务器的代码。如果我们能够用外置的脚本来写游戏故事，这会是一个比较好的选择。   提问环节 提问：我问一下为什么是类BNF，为什么不是BNF？有什么差别？ 许式伟：我不太好去定义什么叫做BNF，因为有的人喜欢用冒号。网上用的比较多的是冒号，我是用等于，其实这是一个非常小的差别，所以我叫类BNF，其实就是BNF，主要的差别是有一些扩展，比如我们扩展的mark。只是这些小细节不太一样。 提问：qlang现在做抽取器是不是特别方便？这是它最主要的使用价值么？ 许式伟：既然它是一个语言，用途只受限于使用者的想象，我自己目前用在爬虫这个地方。 提问：如果和八爪鱼和火车头这种爬虫工具相比怎么样？因为普通人用的比较简便，这个至少还得熟悉编程。 许式伟：它是用什么方式来抽取文本呢？肯定要用某一种文法描述你要抽取的内容，比如正则表达式。我个人觉得正则的表达能力是有限的。抽象一下，正则表达式你可以认为也是一种类XPath的东西，一种定位的方法，它没有程序逻辑，所以像刚才我展示的那种复杂案例，它是不能实现的。 提问：做爬虫的需求会不会出现编码问题？因为我们国内很多语言是按照中文的。 许式伟：这个东西我认为和qlang没有关系，其实我用的是标准库里面的html包，由它再额外改造成支持选择器的东西。如果那个html包支持gbk这些字符编码的话qlang就支持，这个具体我需要回去确认一下。 谢孟军：补充一下，Go多语言支持的应该会很好，明年Gopher China会有Go作者过来讲这一块。 提问：比较qlang兼容go的语法，我想问一下兼容到什么程度？会不会都支持呢？ 许式伟：大家可以看一下这里调TPL的演示，创建一个TPL的抽取器，这是在go里面的函数，只是在go里面是大写开头，我们qlang是小写字母开头。我这里调的时候会把函数名改为大写开头然后直接调过去，所以说Go里的代码在qlang里面是直接可以调的，这是qlang的最重要的优势，可以无缝交互。我给大家看一下这个代码的实现。这是我在qlang里面引用TPL抽取器的代码，可以看到就只有一行代码，就引出了一个new函数，其他什么都不用做。 提问：我想问一下关于想实现特别小型的，只有变量，执行顺序循环，还有函数，怎么实现和表达我想要的DOM呢？ 许式伟：有两种做法，一种是非常正规的表达方式。以我前面演示的1+2*3为例，这个DOM最顶层的是+，左边是1，右边是乘，下面是2和3，这就是最正规的DOM表达。我刚才展示的是DOM不是这样的，它更接近于解释器的执行次序，不是正规的DOM结构。这两种DOM用TPL都是能够做到的，只是你用TPL描述文法的时候是不这样的。 提问：我们公司做爬虫业务，qlang是不是支持超时的机制或者脚本执行完了，占用的资源所有都释放了吗？ 许式伟：这个是你可以自己控制的，把脚本对象删除了就可以释放。 提问：我们在qlang里面是否支持JIT技术？qlang用在爬虫方面，还有没有其他的适合的应用场景？ 许式伟：我们的字节码首先和其他的JVM平台语言不太一样，它是更偏和go交互的支持。我们字节码可优化的余地很大，为什么这样坦白来讲和第二个问题也有关系。第二个问题是qlang还能干什么，我自己做qlang的时候，其实是没有非常强烈的想它的商业目的是什么。因为大家看它的演化过程，最初它的目的只是实现TPL的一个demo，因为我觉得TPL的用途比qlang广很多。很多场景下都需要TPL。比如说我们同事自定义了一种SQL查询的语法，自己用TPL去解析。类似的这种场景的需求需要的是TPL，不是qlang。但是为什么我们要花一些精力在qlang上呢？因为我觉得这个语言有它很大的独特性，我认为它在后面的发展有机会成长。我今天讲qlang不多，重点讲TPL，它才是我一周能实现一个语言的原因，没有TPL是没有办法做到这一点的。有了这个基础以后，做任何新的语言其实不需要一周。大家都知道Go语言的语法很死板，不会允许出现某个语法只给小众的人来用，其他领域的人不用它。所以我们没办法用Go的语法来实现DSL。所以Go很需要TPL这样的库来快速实现DSL。