Dive into the programming language. 在编程语言中计算过程是如何求值的?

前言

最近准备啃一本书<<计算机程序的构造与解释>>(国内简称sicp)。仅仅看了第一章前面两节，对计算过程又有了深刻的理解。书中用的语言是lisp，当我还在抱怨为什么不用当时流行的c时，读了几页就领悟了作者的用意: 人们常说”c生万物”， 没错，不过那仅仅是在语言的实现层面上说的，但在计算过程中, 我敢肯定: lisp生万物!

那么什么是计算过程呢? 在数学的角度，也许是一个证明的过程。但是在编程的角度，其实就是在研究一个程序求值的过程。

一个程序本质上就是在求值，在求值过程中，本质上就是将所有东西转化为两种最基本的东西–数据和运算符(实际上编译器的实现就是这个过程)。

代换模型

举个非常简单的例子：我们要编写个函数计算x^2 + y^2, c语言可以这样写:

1
2
3
4
5
#define square(x) x * x

int square_sum(x, y) {
  return square(x) + square(y);
}

假如我们调用square_sum(3, 4)会发生什么? 作者在书中抽象出了代换模型这种概念: 将square_sum的参数x和y代换为3和4，接着向下求值, 最后就会变为 3 ^ 3 + 4 ^ 4了.

用lisp更能容易发现这一过程:

1
2
(define (square x) (* x x))
(define (square_sum x y) (+ (square x) (square y))

调用后lisp后转化为:

1
(+ (* x x) (* y y))

非常简单吧，但是这里提出一个问题了:

在调用函数时函数是先展开后求值(正则序)还是先求值后展开(应用序)呢? 首先，数学角度证明了这两种方法都能得出同样的结果。

求值也有顺序之分

在lisp中， 我们先用过程抽象的方法自己定义一个if语句:

1
2
3
(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

我们来测试一下lisp是正则序求值还是应用序求值:

1
2
(new-if #t (display "good") (display "bad")))
> badgood

上面的结果是 badgood, 也就是说明 lisp 会先求出函数参数中的值，在应用代换模型向下展开运算了，那么试下正常的 if 语句:

1
2
(if #t (display "good") (display "bad"))
> good

那么就说明 if 不是用函数实现的吧(当然了，if 的底层只是个指令，函数却是一个堆栈结构)!

最后得出结论: lisp 求值过程是应用序的!!!

心血来潮，测试一下 c语言是不是也是应用序求值:

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>

int p() {return p();}

int test(int x, int y) {
  if (x == 0) return 0;
  else return y;
}

int main() {
  printf("%d", test(0, p()));
  return 0;
}

我们先分析一下，如果 c 语言是应用序求值，那么在调用test的时候会先对参数求值, 注意到第二个参数是个死递归(没有出口的递归), 那么这个程序会一直运行没有结果。

测试了一下，果然没看到0输出!!! 看来c语言也是应用序求值! 最后再来看一下生成的汇编代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
p:
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$32, %rsp
	call	p
	addq	$32, %rsp
	popq	%rbp
	ret

test:
	pushq	%rbp
	movq	%rsp, %rbp
	movl	%ecx, 16(%rbp)
	movl	%edx, 24(%rbp)
	cmpl	$0, 16(%rbp)
	jne	.L4
	movl	$0, %eax
	jmp	.L5
.L4:
	movl	24(%rbp), %eax
.L5:
	popq	%rbp
	ret

.LC0:
	.ascii "%d\0"
	.text
	.globl	main
	.def	main;	.scl	2;	.type	32;	.endef
	.seh_proc	main
main:
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$32, %rsp
	call	__main
	call	p   ; 注意这里调用test先调用了参数中的 p
	movl	%eax, %edx
	movl	$0, %ecx
	call	test
	movl	%eax, %edx
	leaq	.LC0(%rip), %rcx
	call	printf
	movl	$0, %eax
	addq	$32, %rsp
	popq	%rbp
	ret

总结一下吧，我们先讨论了代换模型，最后又对求值顺序进行了探究。发现lisp和c都是应用序的。

那么有没有编程语言求值过程是正则序的呢? 我测试了几种常用的语言暂时还没发现。。。或许使用应用序隐藏着某种优点?