“One语言”的设计理念

By guenchi at 2018-02-06 • 0人收藏 • 188人看过

作者:王垠


上文提到我下一篇博客要讲静态分析的原理,但是睡了一晚上之后,觉得更有动力先讲一下我的语言的设计,以后再讲静态分析的事情。当然这篇文章里面也会涉及到静态分析的一些东西。以后我应该尽量避免谈到“下一篇博客”要讲什么,因为我总是喜欢改变主意。

其实我一直在设计一种语言。从进入 Cornell 之后,我就在搜集各种资料信息,想设计一种“终极语言”,它会使得编程变得极其简单。因为大家都用这同一种语言,所以不管是人还是程序间的信息交换都会变得非常容易。软件的构造效率会大幅度提高。

虽然离“终极”的目标还差一截,但是我还是把这种语言暂时称为 One。如果写一本书,就应该叫:The One Programming Language。THE ONE — 让我想起了骇客帝国的 Neo 哈哈…… 也许可以把用这个语言写出来的操作系统叫做 Neo。一种用于取代 Unix 的操作系统,就是我的下一个目标。实际上这个操作系统就是 One 语言的“运行时系统”(runtime)。

(现在发现 One 这个名字不好。Neo 可以考虑。不过只是个名字,以后换换就行。)

为什么我们只需要一种程序语言

有些人认为只用一种程序语言貌似天方夜谭的事情,然而我觉得这是有可能实现的。

很多人从自然语言的现状出发,觉得世界上需要多种程序语言。然而圣经的故事告诉我们,在最早的时候全世界只有一种语言。但是由于全部人都用这种语言,信息交互非常迅速,人类发展很快。上帝开始担心人会超越自己,所以就施了一个法术,让不同地方的人开始说不同的语言。这样人们由于信息交互不流畅,发展就减慢了。当然圣经只是一本故事书,但这貌似仍然说明了一些问题。

从认知科学的角度来看,人类其实根本不是用自然语言思考的,不管是中文还是英语,法语…… 不同国家的人在思考的时候,脑子里其实运行的是同一种没有名字的“人脑语言”。来自感官的信号,和神经元之间的电化学反应,在人脑里面形成了一种动态的“电路”和“模型”。人脑就是使用这些电路来推动这些模型,从而预测出将来会发生的事情。他们需要交流的时候,才会把这些模型转换为自然语言。程序语言其实就跟人脑里面的这种语言类似,它也是一种用于构造“模型”的材料,只不过这种模型不是由人脑,而是由电脑来运行。这就是为什么我们能用电脑来预报天气。

从物理的角度来看,我们生活的世界本来就是由非常简单的材料——基本粒子构成的。我们看到的千奇百怪的物体,不过都是这些基本粒子经过不同的方式组合在一起而已。所以有什么理由认为我们需要很多种程序语言呢?

从历史来看,已经有这样的系统存在过:Lisp Machine, Oberon

所以,我觉得世界上根本不需要那么多种程序语言。理想的情况是一种就够了。

One语言的基本要素

One语言的设计融合了很多种语言的因素和一些新的想法。它并不是简单的把它们放在一起,而是从哲学的角度出发,让这些要素无缝的组合在一起。需要描述的每一个模型,都有一个最直接,最高效的描述方式,而不需要转几道弯,绕过一堆语言设计的无端限制来完成。

我现在就介绍一下几个最主要的要素。偏向于某些语言的人也许会对我的选择比较吃惊,但是我会对这些选择做出简要的分析,说明我的理由,或者给出之前的一些博文的链接。

语法

One 语言使用与 Lisp/Scheme 类似的,基于“S表达式”的语法,但比它们的“语法”含量还要少,还要简单。比如,它不包含 #(...) 这样的东西。通常所谓的“S表达式”其实包含了不少的复杂性,这使得“reader”(也就是 Lisp 的 parser)的构造其实并不像传说中的那么简单。这样的选择的目的,在于让语法分析变得极其容易,速度极快。再加上编译器速度也快,“编译加运行”的过程里面,“编译”占的比重非常之小。所以开发程序的时候你可以专注于源程序,而不必担心“build”的过程。

这样的语法会在早期带来一定的“打字开销”,但是从长远角度来看是有益处的。因为我的设想中,Neo 系统会自带一种基于“结构化编辑”的 IDE,它能够帮助高效的编辑 One 语言的源文件,也可以让人可以选择更加美观,更加简洁的“渲染”方式。由于语言实现考虑到了这一点,所以编译器会给 IDE 提供相当大的支持,使得 IDE 的实现变得容易。

在这种 IDE 实现以前,也可以用 Emacs 加 paredit-mode.el

关于语法,详细的思想可以参考之前一篇博文:《谈语法》。

函数式

One 语言具有 first-class function。函数可以作为值任意传递。跟 Scheme 一样,这是一种真正的 lambda。很多语言虽然有叫 lambda 的东西,但却不能正确的实现,比如 Python 和 C++11。

具有真正的 lambda 的语言都需要 closure optimization。这个优化如果不做,就会产生大量的内存访问。C++11 要求程序员自己写出 free variable 在 [...] 里,就是因为它的编译器不能做好这个优化。在 Chez Scheme 和 Kent 的课程里,这种优化都是做得很好的,做到了极点。

副作用

One 语言不是一种“纯函数式”语言,它允许自由的使用副作用。为什么不设计成像 Haskell 那样的纯函数式语言,不但是出于效率的需求,而且是因为“纯函数式”本身的问题。纯函数式语言所能表达的一切对于“安全性”的要求,其实都可以通过简单的静态分析来达到。实际上,静态分析系统的实现,里面就有很多类似 monads 的东西。纯函数式语言带来了程序员的各种麻烦,因为它相当于让程序员自己在实现一些简单的静态分析系统。关于这个问题,可以参考另一篇博文:《对函数式语言的误解》。

所以 One 语言允许使用各种副作用和赋值。当然,真的需要纯函数式数据结构的时候,你也可以实现它们,你只要不用赋值语句就可以。

没有 let (暂行)

跟 Lisp 和 Scheme 不同,对于变量的“绑定”不使用 let,而是采用像 C 和 Java 里的变量声明。在 Lisp 里的

(let ([x 1])  ...)

变成了变量声明(语法是暂时的设计,重用类型声明的语法,看是否能把它们“统一”起来):

(: x 1)...

去掉 let 的原因是,let 往往形成不必要的嵌套和缩进,然而从“模型”的角度,它跟变量声明是一样的效果:它们都是电路里的一个节点。另外 let 和 if 一起,经常产生一些复杂难读的结构,比如,

(let ([x (if y 0 1)]) ...)

你必须把 (if y 0 1) 嵌套在 let 之内才能让同一个变量依据不同的条件得到不同的值。可是如果你有变量声明和赋值语句,你就可以写:

(: x)(if y  (<- x 0)  (<- x 1))

这样其实清晰一些。这种变量多的时候,赋值的好处就更加明显。赋值语句只能对已经“绑定”的变量进行赋值,而不能构造新的绑定。声明和赋值都不需要类型标记,系统会很容易的自动推导出类型。

不区分stack和heap变量

跟 C++ 和 C# 不同,但是跟 Scheme 和 Java 类似, 所有的变量都只是一个名字,程序员没必要知道它被放在堆栈(stack)上还是堆(heap)上。做这样的选择是为了让“名字”这个概念更加有一致性。为什么程序员需要知道它在哪里呢?这种事情本来就应该是编译器来做的。程序员所要知道的只是“一个名字对应一个对象”。

编译器尽量把对象放在堆栈上,这样可以减少 heap 的碎片现象。

快速而高效的寄存器分配算法

几十年来,很多编译器都使用一种图着色的寄存器分配算法,这种算法的复杂度是 NP-Complete 的,就算近似解的复杂度也不能达到线性时间。

经过一个学期与 Kent Dybvig 的 independent study,我设计了一个与 Chez Scheme 类似,却又在某些地方应该更加高效的算法。这个算法极其简单,基本上是线性时间,但却可以达到超过图着色算法的效果。它其实自然的包含了 linear scan 和 live range splitting 两种技术的组合。原理是把寄存器作为堆栈的“cache”,这样寄存器的分配就变成了一个静态的“cache replacement”算法。

这个方法被记录与我写的(Kent挂名)的一篇 paper 稿(未发表)。你可以在这里看到它的全文。

http://arxiv.org/abs/1202.5539

其实寄存器分配现在已经几乎不是一个问题,因为现在的处理器一般都有足够多的寄存器,使得笨一点的算法也能分配好寄存器。

自动的,非 GC 实时内存管理

由于希望 One 语言能够被应用于实时系统,所以我现在不考虑使用垃圾回收(GC)。在目前来看,再好的垃圾回收算法也是不能完全保证实时回收内存的。引起程序的暂停情况,在很多情况下是不可接受的。这不只是在实时的控制系统(比如飞机,导弹,汽车等),而且在现在的高度发达的互联网上,GC 带来的停顿也会引起问题,这就是为什么我听说淘宝和 Twitter 都试图改进 JVM 的 GC。Chez Scheme 使用了 generational GC,总共有5个 generation。据说效率相当高,可是我仍然怀疑它是否能达到最高的实时系统标准,因为貌似没有实时系统在使用 Chez Scheme (天知道呢,Cisco 收购了 Chez Scheme 拿去做什么了)。

GC 的问题大概就是为什么 C++ 继续流行的原因。我觉得与其解决这个问题,带来 runtime 的复杂性,不如使用另外的方式。其实我早就设计出了一种自动的引用计数的方式,但是我一直有点怀疑它的效率会受到引用计数变化的影响。利用一定的静态分析,编译器可以降低一部分这种开销。比如通过 escape analysis,自动把没法“逃脱”(escape)堆栈作用域的数据都作为堆栈数据处理,剩下的才放在 heap 上。只有放在 heap 上的对象才需要被引用计数。放在堆栈上的对象会在函数结束时被回收。

对于引用计数里面的 cycle 问题,一般的做法是与偶尔的 GC 结合,但是一旦有了 GC,似乎又会不可避免的出现停顿的问题,所以我决定依靠程序员自己做记号来实现。如果他需要指出“我现在的赋值语句会在数据结构中构造一个环”,他就使用一种特殊的赋值语句 (语法是临时设计),比如:

(<= node.next ls.head)

这样的赋值语句虽然会降低 node.next 的引用计数,但却不会对 ls.head 的引用计数产生影响,所以产生一个 weak pointer。如果他不小心写成了普通的赋值语句怎么办呢?那就在系统里留下一些垃圾。所以恐怕也需要结合一下基于 arena 的方式,就像 Unix 一样,把结束之后的进程占用的内存完全释放掉。

根据我跟一个编译器工程师的讨论,Objective-C 的自动引用计数(ARC)是相当高效的,然而这种自动引用计数方法是否能满足实时系统要求,还有待实践考验(因为没有人在实时系统里用 Objective-C)。也许有一天我会再次考虑使用 GC 或者其他方式,但它应该只需要程序员做非常少的工作。

使用 Partial Evaluation 来统一整个编译器的设计

Partial Evaluation 是 Neil Jones 在 80 年代提出的一种自动生成编译器的方法。在 Chez Scheme 里面有一个优化过程叫做 CP0,是一个 online partial evaluation。在 Kent 的另一个课程,我们实现了 CP0 的算法。

这种 online partial evaluation,可以一步就完成其它编译器里面的很多种优化,比如 constant folding, copy propagation 等。它也可以被作为很多要素的实现方式,比如用于优化掉多余的动态类型检查。这样我就从中得到了一种可以实现动静态类型检查“自动划分”的方法。

再加上从静态分析领域得到的启发,我就得到了以下的类型系统。这个类型系统,也就是 One 语言不同于所有其他语言的特色。

强大,灵活而简单的类型系统

One 语言采用一种我正在设计的非常强大的类型系统。它合并了多种类型系统的最好的部分(Hindley-Milner, intersection type, dependent types ……),但却又不是简单的把它们堆放在一起。这种类型系统给程序员一种“连续性”的强度选择,从完全的动态检查,简单的类型,一直到最严格的定理证明方式(完全确保算法的正确性)。程序员可以完全不写类型,也可以选择只写某些类型。这给编程带来很大的灵活性,实现起来却又很简单。

程序员可以写完全不带类型的函数:

(def id (x) x)

他没有给参数 x 类型标记,所以类型系统自动的认为 x 可以是“任何对象”。由于函数直接返回了参数 x,而没有针对它的类型进行“操作”,所以这个函数可以通过类型检查。这样就构造出完全“多态”(polymorphic)的函数,可以接受任何对象作为参数。

进一小步,程序员也可以声明参数的“简单类型”,这就像普通的语言比如 C 或者 Java 一样。然而跟很多语言不同的是,类型的标记不是放在参数列表上,而是放在函数内部,就像一个普通的 assertion。比如:

(def id-int (x)  (assert (: x int))  x)

这里的 ":" 表示一种“子类型关系”。(assert (: x int)) 表示:x 必须是整数,或者是整数的“子类型”,也就是说它必须是一种“可以被当成是整数的对象”。

把类型声明放在函数体内,不是为了显得酷,而是为了取得语义的“一致性”。这个类型声明可以是一个很复杂的表达式,比如 (assert (or (: x int) (: x bool))),它可以表示 x 或者是 int,或者是 bool。这样,我就可以简单的实现 dependent type 的功能,因为我的“类型声明”里面可以含有任意的代码(不过返回值必须是 bool)。

跟大部分基于 HM 系统的函数式语言(ML,Haskell)不同,One 语言只有一种类型间的关系:子类型。子类型关系表示了类型间的“兼容性”(compatibility)。子类型关系是一种更加灵活的关系,就像“子集合”关系。如果 (: A B),那么 A 和 B 可以是“等价”的,也有可能 B “真包含”A,也就是说“有某些 B 的成员不是 A”。所以 (: A B) 就是说,所有的 A 都是 B。

更近一步,程序员可以声明更加细节的“需求”,比如:

(def bar (x)  (assert (and (: x int) (< x 5)))  x)

这就是说,x 是整数,而且必须小于5。这样 bar 的调用者就有“责任”证明这个事实。它的代码也许像这个样子:

(def call-bar (y)  (assert (: y int))  (cond    [(< y 4)     (bar y)]     ...))

注意,call-bar 其实什么事也没做,然而系统能够自动从条件 (< y 4) 推断出 (< y 5) 肯定也成立,从而知道 (bar y) 是可以安全调用的。也就是说,系统通过 call-bar 的定义,自动证明了这个定理。

这种类型的工作方式是几乎所有语言都还没有的。它来自于我对静态分析和机器定理证明的理解。它可以让程序员对函数的调用者提出比较复杂的需求。但是过于复杂的定理可能就需要人工帮助了。为了实现的简单,我目前并不打算把它设计为可以证明很复杂的定理,否则有可能变成 Agda 和 ACL2 那样很少有人会用的东西。

类型标记间的依赖关系

可以选择不写类型,并不是说如果程序员的疏忽没写类型,就会导致运行时错误。类型系统在类型标记的“数据流”中,存在一种严格的逻辑依赖关系。比如,如果你写这样一个函数:

(def foo (y)  (id-int y))

编译器会拒绝这个程序,因为 id-int 被声明为只接受 int 类型,而它的调用者 foo 却没能在调用它之前“证明”y是一个 int。

注意这里我使用了“证明”这个词。这是因为每一个像 (assert (: x int)) 这样的“类型声明”,其实是一个“证明请求”。它的意思是“调用我的人必须事先向我证明,x 的值肯定是一个整数”。

然而 foo 却不能保证 y 是一个整数,因为 y 从外面进来,不知道它是什么!这时候,foo 的作者可以加一个证明请求:

(def foo (y)  (assert (: y int))  (id-int y))

这样程序就能通过编译,因为“证明请求”使得证明的责任“转嫁”到了 foo 的调用者,不管它是谁。这样就形成了一种逻辑的“依赖关系链”。

这些逻辑有可能叠加组合起来,形成比较复杂的逻辑表达式。这样调用函数的人,就有责任做两件事情之一:1)直接证明这个“定理” 2)写一个“证明请求”,转嫁证明的责任给自己的调用者。

显然对于复杂的定理,有可能目前还没有人把它证明出来(如哥德巴赫猜想),或者证明它需要很长的时间。这时候程序员为了短期的目标,可以使用 assume“显式”的声明:我没法证明这个定理。比如:

(def gold (x)  (assert (goldbach-conjecture x))  x)(def bar (z)  (assume (goldbach-conjecture z))  (gold z))

这个 (assume (goldbach-conjecture)) 告诉编译器:“我没法证明哥德巴赫猜想,我暂时假设它成立”。这样编译生成的代码会自动在 (assume (goldbach-conjecture z)) 处插入动态检查,判断 z 是否符合哥德巴赫猜想。这样如果运行时输入的参数 z 不满足哥德巴赫猜想,程序就会发生运行时错误当掉。当然,你也许能因此拿到 Fields Medal(因为你碰巧证明了哥德巴赫猜想不成立),也有可能因此而丧生(因为这代码位于你坐的宇宙飞船的自动着陆系统)。

这种类型系统有点像 dependent type,但是它更加实用,也容易使用和实现。只要把所有的 assert 和 assume 进行一个 Partial Evaluation 就行。实际上,Partial Evaluation 就是 dependent type 的本质。

这就是这个类型系统里面比较有特色的地方。另外它还包括了我的 PySonar 和 Typed Racket 里面具有的 union type。这种 union type 可以很好的解决 null pointer 的问题。关于 null pointer,可以参考我的一篇英文博文

静态分析工具一般都有友好的“bug路径显示”,在这种具有 union type 的类型系统里面,我也想实现类似的报错功能。比如:

(def baz (x) : int  (: x int)  (cond   [(< x 1) 2]   [else "bad"]))

由于 cond 表达式是一个分支语句,所以这个函数的返回类型被推导为 {int, string}。然而类型标记却说它的类型应该是 int。所以编译器报错,说“{int, string} 不能与 int 兼容。”我觉得出错信息应该更加详细一些,它应该指出,这个多余的 string 是从哪里来的,比如指明 "bad" 以及它的行号(在结构化编辑器里,直接标记出它的 AST 节点位置)。

并行和分布式计算

One 语言可以比较简单的实现并行计算,这与 C# 的 async/wait 有点类似,但是它的设计目标是让这种原语成为系统里唯一的并行操作原语,从而让并行计算变得极其容易实现。我们提供一个关键字叫 par,用于指定某段代码可以并行执行。比如你可以说:

(: x (par (long-computation)))(: y x)(do-other-things)(foo (wait y))

这里的 par 表示:(long-computation) 应该被自动安排为异步执行。

第二行的 y 能够直接得到 x 的“可能还没计算的值”(在 C# 里面叫做 Task)。由于还没有人使用 y 的值,我们并不需要检查 (long-computation) 是否已经执行完毕。所以 (: y x) 和 (do-other-things) 可以毫无停顿的进行。这样 (long-computation) 就和 (: y x) ... (do-other-things) 成为了两个独立的“线程”。

直到必须使用 y 的值,我们才用 wait 去检查“y 计算出来了吗?”,因为 y 其实就是 x,所以这其实是在问:“x 计算出来了吗?”如果 x 还没计算完毕,那么就会等待它计算完才会调用 foo。这样两个线程就汇合在了一起。

为什么 par 和 wait 需要显式声明,而不能对程序员透明呢?这是来源于现实系统的限制。我们不能让编译器自动的插入 par 来并行执行某段代码,因为我们不知道 (long-computation) 到底会计算多久。也许它只是一个简单的加法呢?如果我们把这么微小的操作分配给另一个处理器,我们就增加了处理器间通信的开销。然而要想知道一段代码的运行时间,却是一个不可计算的问题。所以我们不得以,必须要求程序员来指定哪段代码运行时间足够长,值得进行并行计算。

那么为什么要使用 wait,而不能直接调用 (foo y) 呢?因为问像“x 执行完了吗”这样的问题是需要时间的。虽然时间很短,但是反复的问就积少成多了。任何地方的 par 语句都可能产生“还没计算完的值”,它们可能会随着“数据流”到达代码的任意位置。如果我们不能准确的定位它们可能出现的位置,我们就必须在使用每个变量之前问这个问题:“你计算出来了吗?”这样就带来了程序效率的大幅度降低。这与我之前谈到的“惰性求值”的缺点类似。然而,想要定位这些确实需要 wait 的位置,就需要全局的数据流分析。这在要求速度很快,或者需要模块化的编译器里是不大可行的。

由于 One 语言写出来的所有函数和表达式都有可能成为 Neo 操作系统的一个“线程”,当已有的线程仍然在运行的时候,我们有可能写出新的代码,编译然后执行。所以模块化的编译似乎是一个必须的东西。也就是说,进行全局数据流分析貌似开销太大,因为这种流分析可能需要分析系统里正在运行的所有进程的所有代码。

以上就是我能想到的 One 语言里比较有特色的地方。具体的设计和实现,还有待多方面的调查和讨论才能最后决定。关于 Neo 操作系统的设计,可以参考我以前的一篇博文。当然,虽然我搞定语言的类型系统和编译器没问题,运行时系统(操作系统)的设计,我肯定需要更有经验的人帮忙。所以欢迎大家跟我切磋。


登录后方可回帖

登 录
信息栏

Scheme中文社区

推荐实现 ChezScheme / r6rs / r7rs large
theschemer.org
Q群: 724577239

精华导览

社区项目

包管理器:Raven
HTTP服务器:Igropyr (希腊火)
官方插件:vscode-chez

社区目标:

完善足以使Scheme工程化和商业化的库,特别是开发极致速度的Web服务器和ANN模块。

一直以来Scheme缺少一个活跃的中文社区,同时中文资料的稀少,导致大多数因为黑客与画家和SICP而接触Scheme的朋友,在学完SICP后无事可做,不能将Scheme转换为实际的生产力。最后渐渐的放弃。
同时Chicken等实现,却因效率问题无法与其他语言竞争。本社区只有一个目的,传播Scheme的文明之火,在最快的编译器实现上,集众人之力发展出足够与其他语言竞争的社区和库。


友情链接:

Clojure 中文论坛
函数式·China


Loading...