微信群分享 第四期《趣味的 DSL Semantics 之旅》 by 丁辉

公开课 · joseph · 于 发布 · 最后由 abbey回复 · 1616 次阅读
12

简介

日期:2016-03-09 21:30 ~ 23:00
主题:《趣味的 DSL Semantics 之旅》
简介:设计一门完备的语言涉及语法、词法、解释器、编译器、虚拟机等一系列的复杂的问题,工作量庞大而繁琐,往往令人望而却步;但实际上我们所需要解决的问题都是一个特定问题,往往都是复杂问题的一个方面,是 DSL 的一个 narrow 应用,如果掌握 DSL 的设计思路,往往能否把问题做较彻底的解决。本次分享通过一个趣味 DSL 语义抽取设计练习,带领大家体验 DSLSemanticSyntax,让大家看到 DSL 解决问题的神奇之处;同时也让大家看到 DSL 不是那么的高不可攀,通过一定的思维训练是很容易掌握的。

讲师

丁辉,中兴通讯敏捷管理和技术教练,12年软件开发经验,8年项目管理和流程改进经验,指导并参多个团队由传统研发模式向敏捷研发模式转型,同时对如何提升员工代码设计能力和提升代码内在质量等方面较多解决思路。

《趣味的 DSL Semantics 之旅》——分享实录

感谢大家,这么晚还一起参加交流和分享。自我介绍下,我叫丁辉,来自中兴通讯,一名中兴通讯的敏捷技术教练。

我们今天分享的话题是《趣味的 DSL Semantics 之旅》。DSL 也是目前业界比较流行的软件设计思想、方法。

DSL 的发展

DSL 的全称是 Domain-Specific Language,即领域专用语言,在讲 DSL 之前,先看一下计算机语言的发展趋势和背景。

现在的计算机,无论是小型机、服务器、PC,还是大家用的平板电脑或者手机,这些主流的计算机都是基于图灵模型设计的。我们讲 DSL 之前,我们从最简单最原始的图灵机开始讲起。

最经典的图灵模型,也就是我们说的图灵机,是由一条可以无限扩展的纸带,加上一个可以在纸带上左右移动的读写头构成,这是一款最经典、最简单的图灵模型。大家不要看它非常简单、质朴,实际上,现在所有的计算机模型都是基于它工作的。

图灵模型的功能非常完备,我们所有的计算机的功能都可以通过图灵模型来实现,但是它的问题也非常突出,就是语义层次过低,举一个简单的例子:假设我们的图灵模型中纸带的左边是高位,右边是低位,我们把读写头移动最右端,也就是最低位,然后从右往左开始移动,碰到1就改写为0,直到碰到一个0改写为1,操作结束。

刚刚这个复杂的操作,其实是一个具有明确语义的计算,大家猜一猜这个计算是什么?其实这就是一个二进制的+1的运算,语义非常简单明确。但是问题也非常突出——语义层次非常低导致很难乍一看就别这些操作和+1对应起来。尽管完成如此简单的计算,也要经过如此繁多的步骤,而且每一步都很难看出与+1这个语义有什么直接关联,也就是说+1的层次比较高,执行时操作语义过低,操作的过程丢失了语义。这也是我们现在很多系统在设计模块时被广为诟病的问题——功能很容易实现,但在过程中往往把语义丢失了,造成代码难以理解。造成代码难以理解的原因非常多,语义层次的丢失是其中一个非常重要的原因。

随着计算机的发展,人们为了提高图灵模型的语义层次,汇编语言就被设计出来了。汇编语言有寄存器等于有了变量的概念,这样完成+1有对应的 add 操作,相对于机器语言来说,语义层次提升了很多。

在人们使用汇编的过程中,又希望继续提升汇编语言语义曾经。在1971年时设计出了B语言,1972年则基于B语言设计出了C语言,C语言进一步提升了汇编语言的语义层次。比如C语言的while循环,对应了汇编语言的cmp => mov => jmp操作,大家可以体会下其中的语义层次差别。这要求我们在使用语言时,一定要在语言层次上的语义思考问题。比如看到C的while循环,你不能降一层,把它视为汇编中的cmp => mov => jmp,这就弄混了语义层次。

语言发展的过程其实是一个语义层次不断被提升的过程,其实都是为了解决某一类问题,在问题域中抽取语义和实现,从而得到问题的特定解。其实C语言也是一个DSL,精通C语言的同学会很容易理解它是硬件资源的DSL。

随着问题的演进,我们设计出了各种语言,比如C++、Python、Ruby、Go、Scala、Java等各种语言,它们都是在相关问题域中进一步抽取提升语义层次而成的。

顺着这个思路,对于每个特定问题,都可以设计一门领域专用语言,合理恰当而优雅地解决问题,而不使用通用语言简单粗暴的去应对。

因为代码不易理解的另一个重要原因是,是代码语义层次上下跳动,即波动,致使高层语义和低层语义交织,难以理解,平滑而优雅的降低和组织语义层次可以很好的提升架构和代码的可理解性。这样要求我们使用通用语言解决特殊问题的时候,注意使用DSL来平滑降解语义层次。

所以呢,DSL解决问题的思路就是:抽取语义、映射语法、计算执行。首先进行一个问题域的语义识别,把问题域中的概念、计算、操作都抽取出来;然后用一种合适的语法表示出来。语法可以用宿主语言(如C语言)来表示语义,也可以用语义映射的方式,映射到数学领域,如几何运算、逻辑运算、布尔运算,来表示语义。还可以采用外DSL方式,用文本语言或自然语言来描述语义,行成一套语法。最后再实现语法的解释器或编译器,把外DSL转换为宿主语言。

小结下,语义到语法转换一般可以分为三类:第一,通过宿主语言表示语义;第二,通过宿主语言映射;第三,通过外DSL方式来描述语法。

接下来通过一种自定义的计算,即自定义解释器或编译期加上我们自定义的虚拟机,把语法转换成通用语言(C++、Java、Erlang、Python)从而隔离开语义层次。一个好的设计能够分离关注点,分离不仅是纵向的,功能不同(增删改查),还可以横向(基于语言层面而不是简单的function call),根据语义层次高低的不同来分离关注点。高层次语义可以用上述的三种方式来表示,低层次语义可以通过解释器、编译期、虚拟机来实现。

DSL实战

上面讲了很多DSL设计上的语义层次的理论,比较枯燥,为了讲清问题,我们通过一个小例子,来看看如何抽取语义、映射语法、实现计算。

小例子叫 Semantics of How Many。

可能很多人都玩过这个题。数一数有多少个三角形,我们通过解这个题,来展示如何识别抽取语义,如何映射成语法,以及如何通过计算(Computation)来得到解。

解题前,我们思考下通过人肉方式怎么数呢?为我们抽取语义抽取提供借鉴。可以有很多种方法,我们觉得比较实用的方法是:先数一数有多少个点,再任取三个点,看看能不能组成三角形,能则加一,不能就放弃,再另选三个点,直到把所有组合遍历一遍。这是一种比较容易理解,也比较严谨的方式。

我们怎么把这种方式转换计算机可以识别的方式呢?转换成语义、语法、计算,让计算机来数三角形。

这是我们语义抽取中的常见问题,对于复杂问题,最常见的方法是分而治之。通常分解开来,语义就自然浮现出,就像水里面的气泡一样。

对于我们这个问题,我们可以分两个部分:动作“数”和三角形。先看看右边部分,什么是三角形呢?我们要从语义上给出准确定义,即在一个平面上(不考虑球面等):
第一、如果任取三个点,这三个点两两相连,此为第一个条件。
第二,如果三个点不在一条直线上,则认为是一个三角形。
至此,我们为三角形给出了精确的形式化的定义。

下面就是用语法表达这个语义了。

语义1 三角形

包含1.1三个点中两两相连、1.2三个点不在同一条直线上

语义1.1 表达两个点相连,即两个点属于一条线。

包含1.1.1线和1.1.2属于

语义1.1.1表达线

这里我们可以通过语法映射表示,假设有一条线,已知线上有A、B、C点,我们用一条线上所有已知点(离散化)的集合来表示一条线

语义1.1.2表达属于

现在我们就得出了「属于」这个操作的语义语法:如果A属于ABC上,B也属于ABC,那我们就可以认为AB两点同属于这条线,即点的属于线的集合(已知点构成)。“属于”其实就是一个集合子集运算

语义1.1.3表达连接


判断两个点是不是相连,可以看这两个点是不是集合的子集,两个点相连的语法表示即为集合子集运算。

判断三个点是在不在集合中,就可以知它们是否在一条线上,根据语法一,即可得出三个点组成集合是否属于一条线的集合。

有同学问,为什么不用几何方法表示点、线以及判断点是否相连呢?例如二维坐标。因为DSL的定位是Domain,从领域中抽取语义。而我们的领域是:判断点在不在线上。这是归属关系,不属于图形运算领域,所以我们只要通过集合映射即可简单实现,没必要引入二维坐标、笛卡尔坐标。

用宿主语言表达来展示下三角形的第一个属性:连接。假设有一条线上所有点的集合,给定两个点的集合1,如果集合1是集合2的子集,我们就认为集合1的两个点是连接的。

宿主语言是Erlang,其他语言都可以,这里只是一个展示。


语义1.2 不在一条线上

我们再来看下三角形定义中的第二段:不在一条线上。那什么叫在一条线上?那就是说三个点都属于一条线的一个集合,即是在一条线上。

这样我们就通过宿主语言的集合映射关系,使用集合的语法,来把两个点是不是一条线,三个点是不是在一条线上,这两种语义表现了出来。

我们把如何表示点和线,如何表示属于和连接的语法表达后,我们就很容易定义三角形的概念(同一平面内点找三个点,两两相连且三个点不在一条直线

简单介绍下代码:lines表示一个函数。Line1表示一条线,这条线由 $a、$c、$b三个点组成。Line2也是条线,由 $c、$d组成。Lines是一个线的集合,有多条线。看最后两行中的on_a_line函数,只要P1、P2、P3三个点,通过判断它们是不是lines这个线的集合中任意一条线的子集,就可以判断这三个点是不是在一条线上。再次强调一遍,这便是通过映射集合的语法来表示「在一条线」上的语义。

完成了三角形定义的语法描述,我们再来看下另一个计算元素——「数」。它也由两部分组成,先挑一个三角形判断,把所有的点都遍历一遍。

语义2 数三角形,包括:

2.1数单个三角形、2.2找出所有可能三角形、2.3数多个三角形

语义2.1数单个三角形

那如何数一个三角形呢?可以任取三个点,再套用我们上面抽取出的算法即可。
大家看,我们用DSL的思想,在语义抽取的过程中,会发现所有代码中的运算,都是业务领域里的概念、计算和行为。然后用业务领域的方式组合。代码中都是业务领域层次中的元素,这样就可以大幅提升代码的可理解性。

看上图。我们把「数一个三角形」的过程形式化出来,判断P1、P2、P3组成的集合是不是三角形。

这就是语义2.1 数三角形的语法表达

语义2.2 找出所有可能三角形

那好,数一个三角形好数,那数多个三角形,大家看,比如说我们有abcd四个点,能组成多少个三角形呢?有 $a$b$c、$a$b$d、$a$c$d、$b$c$d,也就是说把任意三个组合起来,形成集合,即可数多个。

有的同学看到这呢,就会心一笑:这不就是一个排列组合C N 3吗?非常不错,你人肉数一遍就很容易发现,我这里又做了一个语法映射,从一堆点中任取三个拼成一个三角形,这个过程其实可以映射到代数上的排列组合运算。

我们实现comb函数,只要你把点的集合给它,告诉它任取几个,它就帮你生成一个大集合。实现起来不复杂。

语义2.3 数多个三角形

那有了这些充足的准备,我们就把数三角形这个过程形式化出来。而且完全使用业务领域的概念、关系、计算把它形式化出来。整个过程中,基本没有丢失任何的业务语义,从而使代码尽可能地保留可理解性。

那首先看,lines返回了多少线。$a$c、$a$d、$a$b、$c$d,线的集合有了,$a、$b、$c、$d四个点,然后调用comb得出所有可能的三角形的集合,最后判断。

下面呢,我们来看「数」这个词。所有三个点的集合都有了,三角形的判断算法也有了,怎么数呢?很容易想到,我在这个三个点的集合任取一个,如果是三角形,那我们把计数器变量加1,如果不是就略过,继续再数,这样把所有三个点的集合遍历完,「数」就结束了。我们现在把这个过程形式化出来。

大家看,就是这样做。首先通过comb,即排列组合运算得到所有可能是三角形的点Triples(这就是Erlang的特点,它用了一个递归算法,实际上,用其它语言就没必要这样写),然后呢,有一个计数器N,如果是三角形,N就加1,如果不是,就取下一个(List前面有一个H(head)跟T(tail),就是取list里第一个元素,这是一种match pattern,大家不必太多关注,思路有了就行)。所有三角形的集合有了,取一个,看看是不是三角形,是就把计数器加1,不是就取下一个,直到把三角形的集合遍历完。

这就是语义2.3的语法表示

通过我们这种思路,先进行「分」,把其中的语义识别出来,然后用语义映射的方式实现语法,把所有的分最后再组合起来,就得到了结果。

大家也可以试着数一下,到底有多少个。首先把题目中所有的点编号,编号后,所有的点和线都可以表示出来。

所有的线,1、2、3、4、5、6、7总共七条,所有的点,abcd…总共11个。

调用刚才「数」的算法,得出 24 个三角形。

这里大家也看到,计算机解题的思路更追求形式化的逻辑,然后按一点的规则去穷举或递归,得到正确的算法之后,再进行一些算法的优化,提升性能,而不是人脑的逻辑。人脑的逻辑,解题的时候,往往希望找到一个好的算法,或者是其它的思维方式,希望巧妙的解决问题;计算机则是进行遍历穷举+算法优化,这是它俩的差别。人脑的思维在找捷径的过程往往会有一些隐含的逻辑错误,所以我们在解决复杂问题的时候,尽量用计算机的思维模式去思考。

稍微总结下,在DSL设计中,我们要不停地问同一个问题 what does it mean?——它的语义是什么?只有对语义得到一个一个清晰、精确、无二意的描述之后,

我们才能想到一个很合理的语法表示。所以,弄清语义一定是第一位。

这样也得到了一个我们用DSL解决问题的通用思路。首先我们看左边是一个问题,也就是领域——Domain,我们能针对领域里的问题进行分解,得到其中的语义,也就我们说的Domain Model,就是领域模型,然后我可以针对这个领域模型设计出一套DSL也好,哪怕API也要,甚至一套DataType也好,来表示这种语义。表示的过程中,可以用外DSL,文本的方式,也可以用内DSL,映射的方式。

然后呢,我的应用层(App),就可以基于这一套语法,来进行编程、二次开发。它编程过程中,完全使用领域里的概念、计算、行为,所以它编出的代码就非常容易理解。

那从下面看呢,我们从计算(computation)层面,我们可以对设计出来的这套语法提供一套解释器,或编译器,或虚拟机,把它编译成通用语言,比如说C、C++、Java、Python、Ruby、Erlang、Go、Scala去执行。这样整个问题解的思路非常清晰,语义的层次也非常清晰,高层次的语义放在上面,那具体的,低层次的语义,怎么实现的,就在下面。而且呢,它功能点非常内聚,因为针对语法层面的实现都是一个小的功能集,非常容易维护。从而避免我们从「红叉」位置,直接把问题一下降解到最低(通用语言)层次,使问题域的语义降低太快,从而在整个代码实现过程中,以至于都看不清问题域的概念、行为,导致代码变得很难理解,很难维护。

那通过DSL这种方式,可以最大地保留领域内的骨架、整个形体,我还能在后期维护代码的时候看清楚领域的姿势,保证足够高的领域层次,而不像把骨架全部打散了,我们都看不出这个人的形状,这种语义层次高低跳跃的代码是非常难以维护的。

整个DSL的语义、语法和计算,三者之间的关系,我们通过这个小例子的展示已经基本结束,给大家稍微进行总结下。

碰到问题之后,我们首先要进行语义层次的拆解,拆解的过程就是「分」的过程,分的过程中尽最大努力保留业务领域内的概念、计算和行为,然后通过一种外DSL的自然语言,或者是内DSL宿主语言,或者通过一种领域之间的映射,行成一种语法,把语义表达出来,然后在二次编程中,使用我们刚才抽取出的具有原子性的语义,来进行组合,组合后还具有原子性,能继续组合(这是我们后续要分享的内容:语法的设计首先要有原子性,代表语义,然后原子之间能组合,不能组合就不叫语言。组合完后还能具有原子性,组合完的东西还能跟别的原子组合,这是我们下节课内容,再进行分享)。

那我们留一个小思考题。

请大家思考下。

互动提问

问题1:最后一个思考题,是不是几何学上的语义比数组的语义更高级,也意味着更难降解,难以让计算机理解?
丁老师:理解的不错,DSL 关键是领域,解决思路和领域要契合,这题里面只要求判断点线的包含关系,所有集合运算刚刚好。如果用坐标系,就过度实现了。

问题2:感觉 DSL 和函数式编程是不是更适合微观算法层面的设计与实现?软件整体架构的构建还需要面向对象的设计思路?一个大型软件可以全 DSL 的方式去实现吗?
丁老师:这个问题要具体问题具体分析,一般来说大型软件包含若干领域,需要将领域划分出来后,在领域中应用 DSL,划分领域的方法可以采用 DDD。

问题3:领域是不是有层次的问题?比如操作系统这种大型软件,是不是在不同层面都有DSL?
丁老师:大型软件可以划分为若干领域,领域中又可以划分子领域。对于某一个子领域的某个方面,满足计算规则比较一致且明确的场景。

问题4:DSL 哪里应用比较好 比如大型软件的什么具体方面。dsl是不是和面向对象相反的是都是方法组成的?
丁老师:DSL 对于计算规则比较统一明确的场景;面向对象可以作为 DSL 的实现方式之一。

问题5:如果要继续深入学习理解DSL, 丁老师有没有推荐的书籍?
丁老师:《Struture and Interpreation of Computer programs》和《Essentials of Programming lauguages》

其它

如果讲师的分享对你有帮助,欢迎酌情打赏鼓励讲师。

这是一个什么样的社区
查看往期线上活动


「软件匠艺社区」旨在传播匠艺精神,通过分享好的「工作方式」和「习惯」以帮助程序员更加快乐高效地编程。
共收到 3 条回复
351

关于DSL,我是在学习DDD过程中,从各种渠道接触到的零碎信息开始的,并且目前为止我只读过Martin Fowler所著的《领域特定语言》。由于该书比较晦涩,所以我对DSL的理解仍停留在『一套以DDD中的统一语言为其实现基础的”类编程语言“』上。所以在具体的实践中,我把DSL理解为配置信息或者业务规则的一种文本表达,然后再辅以一个语法解释器,在运行时由这个解释器去解析DSL文本,实现运行时的动态配置或者规则判断等等。

比如我曾在一个工资管理软件中尝试着这样去表达『当年满60周岁,或者工龄届满30年时,应退休。』的意思:retire = (Age >= 60) || (ServiceLength >= 30)。然后在运行的时候,加载这段文本,由一个内置的解释器把这些转化为领域里的Specification,再交给Aggregate去使用。期间,编写这个解释器的过程非常磨人。为了尽可能减少DSL的语法漏洞,我几乎把《编译原理》从头又来了一遍。

以上就是我的个人理解,也不知道这样是不是正确。另一方面,作为一个C#程序员,我感觉这方面的资料也比较少。我知道有一个Java的《DSL in Action》,但还没有读过,不知道有没有价值。最后,花费如此的代价去实现一套DSL,相比 一个简单的XML(当然,XML其实也是一种简单的DSL),会不会有得不尝失的疑虑?

谢谢!

1
hkliya · #2 ·

#1楼 @abbey 不好意思,没料到会同故障。看来还是得加到群里保持沟通。

12
joseph · #3 ·

#1楼 @abbey 抱歉,由于技术问题,原定的 Live Coding 分享形式临时变更为群内的语音分享。目前分享已结束,内容整理中,:)

需要 登录 后回复方可回复, 如果你还没有账号你可以 注册 一个帐号。