近期规划

目前最终目的, 用 purescript 写 Cyberbrain, 写完之后, 后者成为前者的debugger, 而前者又是后者的静态检查器.

为了达到这个目的, 首先purescript要能codegen到Python. 目前遇到的问题是, Python是一个语句优先的语言, 而purescript给出的中间表示需要一些表达式优先的特性, 比如块表达式以及赋值表达式.

Purescript-Python

从表达式优先到语句优先: ANF变换

解决的办法有两种, 一种是利用ANF(Applicative Normal Form)的表示.

例如, 给出如下表达式优先的程序,

f({
    print(f(x))
    x = 2
    print(f(x))
    x = 3
    g(x)
})

我们可以将其转为如下语句优先的程序,

# print(f(x))
tmp1 = f(x)
tmp2 = print(tmp1)
# x = 2, 返回None
x = 2
tmp3 = None
# print(f(x))
tmp4 = f(x)
tmp5 = print(tmp4)
# x = 3
x = 3
tmp6  = None
# g(x)
tmp7 = g(x)  # tmp7: 块表达式的返回
# f({ ... })
tmp8 = f(tmp7)

其中tmp7是块表达式的返回值.

注意观察函数参数还是赋值的左右端，他们形式上总是一个常量或者变量, 都是一个非递归/简单的形式. 这是ANF的做法, 可以把表达式优先的语言转为语句优先的语言.

ANF变换的代价是引入一大堆没必要的中间变量, 通常来说, 可以引起性能的大幅下降, 尤其是对于Python这种本身建立在栈帧虚拟机上的语言. ANF变化可以进行一些优化, 比如通过寄存器分配优化的算法去尽可能减少ANF变换产生的冗余变量.

Python虚拟机上的First-class的表达式优先

ANF变换分配的变量, 即便经过寄存器分配优化, 也必然无法彻底消除, 因为他们代表着对栈上临时变量的模拟, 那么有一个临时计算结果必然至少对应一个临时变量.

并且, 无论经过何种寄存器分配优化, 临时变量的数量至少是大于等于栈的最大使用长度的.

所以可以直接用Python的虚拟机栈的话, 还是更好的.

上面那段函数调用的程序, 用虚拟机指令表示则是

load-fast print

# f(x)
load-fast f
load-fast x
call-function 1

# print(f(x))
call-function 1

# x = 2
load-const 2
store-fast x

# f(x)
load-fast f
load-fast x
call-function 1

# print(f(x))
call-function 1

# x = 2
load-const 2
store-fast x

# g(x)
load-fast g
load-fast x
call-function 1

是不需要引入任何新的临时变量的.

社区意见

Python因为语法设计问题, 而无法成为表达式优先的语言.

大概率正因如此, 它的ast也设计成了语句优先(实际上这是没必要的), 具有同样的表达力限制(无法支持块表达式和赋值表达式等).

目前, Python社区里造出的使用Python运行时的其他编程语言, 只要有一点流行度, 都是基于拼源代码或者拼ast的.

原因有

  1. ast好学, 而字节码虚拟机不好学
  2. ast跨实现, 可以支持PyPy或者Jython这些Python实现.

目前没有拿定注意选什么方法, 仅有的感觉是ANF是不太漂亮的.