【求教】我最近在写一个解释器。请道友们谈谈看有哪些优秀的语言特性。

我最近在写一个解释器,准备把几个常见语言的主要特性都加上,组成一个"弗兰肯斯坦"。目前已实现常用数据类型(整数、字符串、list)和语句表达式(变量/if/函数(lambda)/loop/四则运算),准备加上的有:

1.OCaml的sum type,或者rust的enum;

2.C/Go语言的struct;

3.zig的switch case;

4.Go语言的array;

5.Go/Java的interface;

6.Python的dict;

7.rust的loop;

8.JavaScript/OCaml的可科里化函数;

9.match;

10.GC;

11.C语言指针或Go中的指针;

12.宏语法暂时有点不想弄;

13.rust 的内存管理方式(借用、ownership、lifetime)很酷,但是太复杂,目前也不考虑。

求教:还有哪些值得推荐的特性?哪些是糟粕,哪些是精华?

一点背景知识:我不懂 PL 理论,所以先“蛮干”。做个项目的第一目的是学习解释器/编译器,至于最终会做出什么东西来,目前完全没有概念。

1 个赞

elisp 的 dynamic binding

2 个赞

NO!(紫薯布丁)

2 个赞

go 的 goroutine 和 channel!

2 个赞

scheme 的 call/cc

1 个赞

Python的函数默认值,拒绝缩进;Golang的goroutine,拒绝Go式错误处理

1 个赞

先写一点这里列出来我相对熟悉的特性:

11、10、13 我觉得不太适合放一起,要 GC 就 GC,别混手动管理 。要么就全手动管理,提供一个 GC 库,让用户来管理哪些要 GC 管理的。要混一起至少得定义一种来显式区分的方案,不然你怎么决定是否处理呢?最后感觉反而把事情变复杂了。

1 和 9 其实可以算一条,因为这些特性是配套的,单有一条意义不大。

8 条其实会涉及到不少东西,比如说,你怎么去管理你的函数定义,这个 currying 过程是运行时动态变换还是解析时就一步生成好。函数与变量是同一的,还是不同的,lambda 呢?不同的话,处理的时候是运行时区分还是解析时就区分。 这一条下来也直接关系到了 1、2、5、6、9 要怎么做。你是要像 python 那种全部是 object?还是有类型约束?几个东西叠起来后就和你最开始想要的可能不一样了。如果没有类型约束,那么也不太存在手动管理内存了,至少会很麻烦。

第 4 条和第 6 条不太理解想说什么东西。难道是 slice、定义方式那些?这个的话,其实可以当成糖,在做完最基本的文法后再向上加。第一阶段可以跳过。

我理解里的 3 和 9 也基本是同一个特性。

12 条其实不急,方案有很多种,等基础定型了再定这个比较好。

然后,这里还只考虑了特性本身,没考虑怎么设计文法。这么多特性,你要用 LL、LR、LALR 还是 PEG?别最后都设计好了,然后发现解析器不工作。既然你是解释器,你是要以什么样的单元了解释?比如说,函数定义是整个结束了才开始执行函数定义,还是第一行就先把函数名加进环境里了,后面每行往向里注入,如果失败再回退操作。不同方式也会影响到文法设计。最后可能导致你开始想的这些特性实现起来很困难。

==================================================

然后我个人比较喜欢的特性的话:

涉及到绑定的地方都能用 pattern match,比如 rust 里的 if let, while let,haskell 里函数参数也能 pattern matching,或者像 common lisp 里 defgeneric 那样的。

糖!我喜欢糖,语言里同样的一种行为能让我有几种选择来用,比如 perl 里 <>$_""qw。还有像 rust 里有 match 也有 if-let,还有 let else。 像 haskell monad 那样存在上下文行为的调用。

依值类型,GADT

Agda 那样的自定义符号表达式

根据自己理解帮楼主把这些特性分个类。

类型系统,抽象数据:

1)sum type

2)struct (product type)(可以和1组合设计成 algebraic datatype)

5)interface (这个有点tricky,因为是偏OOP的设计,需要楼主多考虑一下最终想要的效果)

13)ownership type system (蛮复杂的设计,同意楼主的concern)

语法(糖):

3)switch case (既然有了1和2,那么楼主理应有一个从1和2抽象的数据拿数据的手段,可以直接实现pattern matching)

参考资料有SPJ的The Implementation of Functional Programming Languages的第四章

7)rust的loop(我理解为ruby类似的loop block,本质上是while True的语法糖)如果楼主设计好control flow相关(while),那么这个会比较trivial。

Infrastructure 语言基础设施相关:(可以之后做)

9)match (同1,2,3,可以用pattern matching代替)

4)array(go,也有可能楼主是想要它的语法)

6)python’s dict

其他

8) JavaScript/OCaml的可科里化函数; 不太清楚楼主的想要,有两个options:

  • 拥有一个primitive将uncurried的函数转成curried,如果语言支持高阶函数(higher-order function)的话将非常trivial。

  • 像haskell一样默认都currying(那么楼主需要一个函数类型)

10)11)GC和pointer,是否将memory的控制权限交给programmer需要楼主想好。

写完发现楼上已经做了类似的工作😄

楼主的学习方式很好,learn by coding,但是还是建议跟着一门课/一本书学,我能想到的书有EOPL(Essentials of Programming Languages)或者 plai.org

2 个赞

楼主以前写过解释器吗?

这两本书对比有什么特点啊

感谢反馈。里面提到的特性,能否实现我心里还没有底,走一步看一步吧。目前我的疑惑是,哪些特性比较好(公认的,非特定场景下的)。如果有相关的、比较实用的书籍,欢迎推荐,感谢感谢!

zig 的 switch 和 scheme 的 match 有点像,但弱很多。自动内存管理和指针并不矛盾。我列举的几条是我目前想到的,比较细、比较散,所以里面有交叉和重复。

parser 目前用的是比较简单的普拉特递归下降法,对某些复杂的语法能否解释,我心里也没有底。目前能解析C语言语法够用。

没有。第一次,从零开始。

感谢哥!!!

那建议你先写一个支持完整表达式计算的解释器。

能支持不同的数据类型,例如,整数,浮点数,布尔类型,字符串等等,支持括号,单目,双目,三目运算符,正确的处理运算符优先级等等。

除了浮点数、三目运算符,其他的都实现了。目前整数、负整数的四则运算、括号都没有问题。还有return语句也实现了。

我通读过EOPL,没有通读过PLAI,我能讲的大概是

EOPL的作者是Friedman(印第安纳大学的PL老前辈,The Little系列作者),用scheme + 自己写的一个datatype宏做教学,书很经典。 PLAI的作者是Krishnamurthi(布朗大学的PL学者),书籍是供教学使用,书里代码之前使用类scheme语言,现在大概是用pyret(自己写的一个语言)?

两本书的作者都是PL学界比较致力于education的教授,并且都是教写interpreter,他们的书都十分有价值。

2 个赞

嗯,准备看。感谢推荐!

说几点抽象的。

优秀的语言特性,在我看来需要有泛用性,即你作为第三方作者写的库是否也能用上这个功能。C++做得比较好,甚至可以说矫枉过正了,大量新的模板特性就是为库作者准备的。反面例子是某些语言的链式调用符号 ?. 只有自带的Optional类型可用。当然了,追求泛用性难免和语言的简洁程度相冲突,要看怎么在动态/静态、脚本/编译这对矛盾间做取舍。

元编程也是个热门话题。C的元编程排除编译器魔法,基本就是基于词法结构的替换。C++的模板做了三件事:把常量融入类型中、可以对类型做运算、以类型为参数复用代码,在普通的泛型场合很够用,但若要生成代码,不能说做不到,就是难免晦涩。更新一些的语言如Rust,从Lisp那拿来了卫生宏的理念,编译期生成代码方便多了。

通常而言,动态/解释型语言并不需要这些严谨的代码生成特性,毕竟有什么需要的话,运行时修改对象模型就好了。Ruby里面有不少这种惯用法(毕竟是不带括号的Lisp),比如在类定义里调用某个方法就可以对类的继承体系作修改,而Ruby社区也习惯把这些用法称作宏(虽然Ruby语法中并没有宏这个概念)。

把动态语言和静态语言的宏做下对比,可以发现Rust宏的实质就是一个语法特殊的模式匹配,执行者是编译器。胆子更大一点,其实编译型语言一样可以把对象体系、语法树,甚至整个编译器的上下文暴露出来,提供适当的接口给宏去注入,惟一的要求不过是这些宏必须是编译期可被求值的常量表达式(纯函数)。

也就是说,我写一个函数 UpdateTree<T>(node: T): T,如果传给它的参数是一个普通运行时对象,那它会作为一个普通函数被实例化再编译。但如果参数是编译期的常量对象(比如AST节点),那这个函数会在编译期被执行,形成类似「编译期的编译器其实是个解释器」的效果。C++的 constexpr 有这种效果,但只限于模板部分。倘若真的有语言能做到这点,那威力就太大了,以至于语言设计者要做出额外限制以防滥用。

我们还可以进一步模糊动态/静态、编译/解释的界限。常见的一种需求是,开发者用动态语言快速实现原型,逐渐解决性能和安全问题,而后打磨成真正的产品。一个例子是TypeScript的any,开发者可以一步步把any换成更严格的类型约束。这种渐进式的语言设计思路非常有意义:

  • 语言可以支持动态类型any,甚至可以把any编译成可执行文件,而从any改成具体类型之后,编译器真的会做对应优化,而不是像TypeScript一样只是简单擦除
  • 一开始可以无脑GC一把梭,后面有需要时能给具体对象/类型加上nogc标识。难点是这样相当于给对象染色了(染色的概念参考async函数和非async函数),要仔细处理两种对象的依赖关系
  • 原型阶段可以解释着跑,要性能了再编译。这点倒是很常见,比如OCaml
  • 这个语言能否「丝滑地」同其他语言互操作。这点很重要,苹果早年选中Objective-C这门奇怪的语言,就是因为它能和C/C++源码级互操作,等于海量的C/C++库都天然地为它所用

说一个实现层面的: 避免手写 GC.

最近花了十天时间写了一个简单的解释器, 长这样

用的是 Go, 直接白嫖了 Go 的 GC, 代码复杂度小很多, 而且怎么优化 GC 那都是 Google 的事情, 与我无关

1 个赞

gc 是这样的