用1024字节实现Python解释器

欢迎前往 Hacker News、r/programming 和 Lobste.rs 参与本文讨论。

为了找回「人之为人」的实感，我周末会手写代码。

最近的挑战是什么？用约~~512~~1024字节的标准C代码实现一个Python解释器。哦对了，不准用宏技巧，也不许耍库函数花招。

def buzz():
for n in range(101):
if n % 15 == 0:
print("FizzBuzz")
else:
if n % 3 == 0:
print("Fizz")
else:
if n % 5 == 0:
print("Buzz")
else:
print(n)
buzz()

显然，1024字节的代码不可能塞下完整的Python语言。那我能实现多少「形似Python」的特性呢？

上面这段FizzBuzz代码就很有Python味儿：有def定义、冒号、缩进，if语句也不用加括号。在我看来，这就够像Python了！当然，除了语法子集，我还得加一些额外限制。

不过我的第一次尝试彻底失败了。

我写过不少递归下降解析器，本以为这次也大同小异——毕竟Python子集和我之前实现过的语言（比如我的Teeny Tiny编译器）应该差不多。

我从最基础的代码开始：1 + 2

接着升级复杂度：x = 1 + 2 * 3

后来又加入了语句：if x > y: z = 3

不错，我做了个计算器……但这根本不是我想要的挑战！而且代码量已经超了。这时我才退一步思考，列出那些「看起来像Python」的特性，同时意识到自己的代码高尔夫水平还不够，根本没法塞进512字节。

那1024字节行不行？先实现功能，再压缩体积。

真正的CPython会先对Python源码做分词，解析成抽象语法树，再做分析优化，生成字节码，最后解释执行字节码。

而我的小解释器完全不走这套流程。

它用几个全局变量保存状态：一个固定长度的数组（目前是999位）存储原始Python代码，变量和函数名则全部存在另一个数组里。

char src[999]; /* 去除大部分空格后的完整程序 */
int vars[256]; /* 符号表 */
int pos; /* src中的下一个字符位置 */
int ch; /* src中的当前字符 */
int line_start; /* 当前行的起始位置 */

表达式处理和其他递归下降解析器一样，边解析边执行。比如：

int parse_sum(void) {
int value = parse_term();
while (ch == '+' || ch == '-') {
if (ch == '+')
value = value + parse_term();
else
value = value - parse_term();
}
return value;
}

目前来看还算简单直接。

这个解释器完全没有错误处理！它极度依赖输入代码的正确性，比如默认所有关键字都拼写正确：

if (ch == 'w' || ch == 'i' || ch == 'f') {
int keyword = ch;
int loop_var = 0;
if (keyword == 'f') { /* "for K in range(N):" */
pos += 2; /* 跳过"or" */
loop_var = next();
pos += 8; /* 跳过"inrange(" */
vars[loop_var] = 0;
} else if (keyword == 'w')
pos += 4; /* 跳过"hile" */
else
pos += 1; /* 跳过"if"中的"f" */

它还默认 token 边界正确，会去除大部分空白，只保留缩进和字符串字面量中的空格。

变量名被限制为单个小写字母，这样就能直接通过字符做符号表查找：

if (ch > 96) {
value = vars[ch];
next();
}

代码块执行函数会一直运行，直到缩进级别降低——此时函数返回，由调用者处理下一行。也就是说，它是用C程序的调用栈来处理递归的：

void run_block(int min_indent) {
for (;;) {
int indent = read_indent();
if (ch == '\n')
continue;
if (indent < min_indent || ch == 0) {
pos = line_start;
return;
}

那循环功能怎么实现？

由于没有编译步骤，循环靠反向跳转、每次迭代重新解析源码实现。while和for循环都会记录条件表达式的位置，执行完循环体后，就跳回该位置继续解析。

函数的实现逻辑类似：解析函数定义时，符号表会记下函数在源码中的位置；解析函数调用时，先保存调用位置，再跳转到函数体执行，执行完毕后恢复调用位置。

不用中间表示居然也能做到这些，实在太巧妙了！而且解释器需要维护的状态极少。

我之前没怎么玩过代码高尔夫。缩短变量名、删空白这种操作很直观，但怎么大幅压缩代码量呢？

有个古老到快被遗忘的网站叫Stack Overflow，上面曾有一群代码魔法师分享经验。我从《C语言代码高尔夫技巧》Tips for golfing in C里学到了很多思路。

规则都是用来打破的，所以我不得不另辟蹊径。有些技巧依赖GNU C89的专属「特性」——这可不是耍花招！这是常规的小变通。以下是我从可读版代码中压缩字节的方法：

比如之前展示的parse_sum(void)函数，被精简成了e(){for(z=t();c-43u<3;)y=44-c,z+=y*t();return z;}。这里用ASCII值来节省字节。

再比如一个跳转到行尾的辅助函数：

void skip_to_eol(void) {
if (ch != 0 && ch != '\n') {
next();
skip_to_eol();
}
}

我把它改成了：Y(){c&&c-10&&Y(G());}。它先判断是否为0，再用减10的方式判断是否为换行符，用&&替代if语句；还通过Y(G());代替G();Y();省了一个字节。太聪明了！再次感谢那篇Stack Overflow帖子。

一番操作后，最终的高尔夫版本刚好1024字节！

完整的可读版代码超过4800字节。我原本加了不少特性，为了压缩体积不得不忍痛删减。比较表达式是下一个被砍掉的功能——它占了太多字节，而且就算没有它，真值判断依然能工作，比如写成if n%15:就行。

如果只需要让FizzBuzz跑起来，我估计代码能压到800字节以下！肯定还有其他高尔夫技巧可以用。

下面就是最终的高尔夫版本源码：

char s[999];v[256],p,c,x,y,z,w,u;G(){return c=s[p++];}I(){for(u=p;G()==32;);return p-u;}Y(){c&&c-10&&Y(G());}f(){x=0;if(G()>96)x=v[c],G();for(;c-48u<10;G())x=x*10+c-48;return x;}t(g,h){for(g=f();c==42|c==37;)h=c,g=h-42?g%f():g*f();return g;}e(){for(z=t();c-43u<3;)y=44-c,z+=y*t();return z;}E(a,q){a=e();if(c-60u>2)return a;w=c-61;q=G()==61;p-=!q;x=e();return w?(a-x)*w>-q:a==x;}S(i){for(;I()>i|c==10;)Y();p=u;}Q(){for(G();G()-34;)putchar(c);G();}B(i,q,j,k,a,m,n){for(;;){j=I();if(c==10)continue;if(j<i|!c){p=u;return;}if(c==119|c==105|c==102){k=c;k-102?p+=k/4-25:(p+=2,m=G(),p+=8,v[m]=0);q=p;for(;;){a=k-102?E():v[m]<E();p+=k==102;G();if(!a){S(j);break;}B(j+1);if(k==105)break;k-102||v[m]++;p=q;}I()-j|c-101?p=u:(p+=4,G(),a?S(j):B(j+1));}else if(c==100){p+=2;k=G();Y();v[k]=p;S(j);}else{if(c>96){k=c;while(G()>96);c==40?k-112?(G(),n=p,p=v[k],B(2),p=n,G()):(s[p]-34?printf("%d",E()):Q(),puts(""),G()):(v[k]=E());}Y();}}}main(q,m,h){for(h=m=q=0;~(c=getchar());){c=c-9?c:32;h^=c==34;s[q]=c;q+=c-32?1:!m|h;m=c>32|m&&c-10;}B(0);}

最终我实现了以下特性：

近期我应该不会再碰代码高尔夫挑战了。整个过程太折磨人——我得在正在压缩的版本和原始版本之间反复切换，才能搞清楚两分钟前自己改了什么。两个版本都放在GitHub上了。

现在轮到你了：你心中1024字节的Python会是什么样子？