问题背景:
1 AST可以反映程序的深层结构,或许可以大大简化程序编写和阅读
2 二进制化的AST或许可以解决用字符串通信的诸多弊端,实现用数据结构传递绝大部分信息,以此实现互用性(interoperability)的突破。

参考:

https://docs.python-guide.org/scenarios/serialization/
https://docs.python.org/2/library/pickle.html

https://softwareengineering.stackexchange.com/questions/119095/why-dont-we-store-the-syntax-tree-instead-of-the-source-code

Limitations of the Unix philosophy and the ultimate solution to parsing: https://yinwang0.wordpress.com/2011/04/14/unix/

The BinAST diaries - Compression, part 1: https://yoric.github.io/post/binary-ast-compression-1/

https://en.wikipedia.org/wiki/Intentional_programming

Watt, D. A., Brown, D. F., & Brown, D. (2000). Programming language processors in Java: compilers and interpreters. Pearson Education.

简单记录我的一些思考;
1 树形结构确实在多数情况下非常直观,减少了纯文本的格式问题。
2 AST只是表现句法(syntax)层面的东西,语义层面则勉为其难,不同语言甚至相同语言的某些情况存在同样句法树语义不同的情况。
3 AST解读本身需要额外规则,如深度优先还是广度优先,子树/节点(node)的含义。递归/自我引用(self-referential)的程序如递归函数(以阶乘为例)会导致很多简单序列化方法失效,此时需要额外规则。
4 目前已有产品(如js的那款)是主要针对语法解析(parsing)速度、减少重复而言的,不是提供通用的程序接口和互用性方案。
5 像COM、Oberon这些实现用数据结构通信的产品,全是同质化平台,而且底层开发语言只有一种(C*/Oberon)。

3 个月 后

说一下我自己的一点想法吧:

我觉得有一定道理的是 Limitations of the Unix philosophy and the ultimate solution to parsing 里提到的 “universal binary format” 的想法。确实如文中所提到的,现在的大多数文本的数据,其实都只是不同数据类型(interger、boolean)的一种低效率表示。

但同时我也认为我们现在不应该切换到一个 universal binary format 上去。因为对于现在的计算机来说,计算速度足够快,一个文本的 parse 和一个二进制格式的 parse 在性能上并不能拉开很大的差距。而且即使是 universal binary format,也依然少不了 parse 的步骤, 依然存在文中提到的 “前一个程序编码,传到后一个程序马上又要解码” 的问题,只是解码的数据从文本变成了二进制,收获了一点点性能提升罢了(again,我们真的需要这些性能提升吗?)。

我觉得本质上是找错了问题。

interoperability 的突破,需要的是一个良好定义,并广泛接受的数据交换格式,重点在于这种格式需要「良好定义并且广泛接受」,而与这种交换格式的本质是二进制还是文本无关。

拿 web 界来说,以前的互联网数据交换有很多协议,基本上每一个应用都有自己的不同的协议,而今天,大多数事情都可以通过 http 来完成。大量的前后端交互和跨应用 api 采用 http + json 的形式,假设你开发一个新的应用,可以通过 http api 调用到很多现成的基础服务,从而实现灵活的交互组合。这就是一个「良好定义并且广泛接受」的数据传输格式的例子。

而 「http + json 是文本格式」这一点,并不影响它的广泛应用,也丝毫不降低它提供互用性的能力。

二进制比起文本的优点,可能是 parser 的实现会相对简单,但是对于大多数应用来说都会使用现成的 parser 库,而不会自己重新造轮子。而二进制格式的设计大概率也会需要通过 parser 库来解析,所以这个优点就显得不是特别明显(特别是考虑到现在的计算机)。

更好的问题应该是,“能不能找到一个抽象,使得应用之间交换的信息都能用这个抽象来描述”。举 SMTP 的例子,一封邮件需要知道送信人、收信人、标题、正文。这个就是一次信息传递(一封邮件)所含的信息的抽象描述。而具体传输是如何分行,如何存储标题,是文本还是二进制,使用什么编码,这些都是具体实现的细节,不会影响它携带的信息这个本质。

找到这个抽象的过程,其实也就是协议规范制定的一部分。“要传什么” 比 “怎么传” 更重要。

总之观点就是,将文本格式切换到二进制格式,不会带来很显著的好处,也并没有改变传递的信息的本质,也就没有提升程序交互性

对于存储 AST 这一方面,大体的在参考资料里也都谈到了,例如语言之间的差异性之类。

我自己想到的一个没提到过的弊处是,“AST 阅读器” 的设计。如何设计这一 AST 格式,使得无论我在什么平台,无论我用什么阅读器,我都能够正确解析这个源码文件?如何使阅读器兼容比它出现得晚的,它从来没见过的语言?

如果说 AST 的节点里存储其所代表的文本来实现兼容,那么你发明了世界上最复杂的文本代码格式。
如果说在头部预先记录如何解读某些特别的 AST 节点,那么你发明了世界上最复杂的代码压缩格式。

本质上还是,这个通用二进制 AST 代码格式,不可能有足够的前瞻性去做出一个能描述未来所有可能出现的编程语言的语法,因为它连现在已有的编程语言都无法找到一个很好的方式进行统一描述。

尝试对 “代码” 这一信息去提出 “能不能找到一个抽象,使得应用之间交换的信息都能用这个抽象来描述” 这一问题的话,至少对于 “代码” 这一具体领域,很难。

2 年 后

楼主了解过 Zero-Copy Serializaion 么?当内存中的数据结构和持久化的二进制串是一样的表示时,那么数据交换是不是就算0开销了呢?Cap'n Proto 序列化框架主打的就是这个。不知道yinwang是这个意思吗?(没看yinwang博客,就是几年后恰好翻到楼主的贴子加上最近刚了解这个概念而已)

    1 年 后

    Ekstasis 没了解过,很抱歉现在自己转行了,但很高兴当年的记录能为你带来思考!

    © 2018-2025 0xFFFF