0
0

JavaScript 原理,其五

Typeof 发表于 1970年01月01日 08:00 | Hits: 754

利用程序语言我们可以教会机器它们的任务。语法规定哪些句子是合法的,而机器应该做什么,就是形式语义规定的内容了。但是语义其实是个挺玄的东西,玄在两处,一是——能作为「语义」的东西真太 TM 多了。考虑下如下的「十进制数」语法:

  • Decimal → Digit
  • Decimal → DecimalDigit
  • Digit → 0|1|2|3|4|5|6|7|8|9

对于「十进制数」的「语义」是什么,我们可以说是它表达的整数值(这是各位最熟悉的语义)。一旦语义确定是如此,那么语法制导定义——那个从字符串到「语义」的函数——就可以这么写就:

def (numVal (Digit -> `'0`)) = 0
def (numVal (Digit -> `'1`)) = 1
...
def (numVal (Digit -> `'9`)) = 9
def (numVal (Decimal -> (Digit *))) =
numVal (Digit *)
def (numVal (Decimal -> (Decimal *) (Digit *))) =
return [10 times (numVal (Decimal *)) + (numVal (Digit *))]

(我已经预感到你们在吐槽为什么这「语法制导定义」长得那么像 Lisp——具体原因之后再谈)

不过呢,如过我把「十进制数」的语义,硬说是那个整数的位数,那么这就好玩了;此时,语法制导定义就不同了:

def (dlen (Digit -> `'0`)) = 1
def (dlen (Digit -> `'1`)) = 1
...
def (dlen (Digit -> `'9`)) = 1
def (dlen (Decimal -> (Digit *))) =
dlen (Digit *)
def (dlen (Decimal -> (Decimal *) (Digit *))) =
return [(dlen (Decimal *)) + (dlen (Digit *))]

也就是说,语义本身就是设计师自己想要什么就能定成什么的(只要精确和递归 就行)。不过,对绝大多数程序而言,它的语义就是——它要做的事情,对不?于是,形式语义第二个玄点就来了:如何描述一件程序「做的事」?用其他程序描述吗?

程序语言的形式语义大概分为三个流派。第一个也是最正经的叫做指称语义 ,它将「程序」定义成一个函数。第二个叫操作语义 ,它将语义定义为某个抽象机器上的指令序列。还有一个是公理语义 ,它主要用于程序证明。在这些定义中操作语义可能是各位最容易接受的:我们写再多的程序最后还是要转换成 CPU 上的指令,因而用抽象机器里的指令来表示语义,显然没有什么大问题——没问题到许多语言(比如 Java)就是这么定义语义的。而指称语义则适合函数式语言:许多函数式语言的语义甚至不需要复杂的转换,源码就是定义,最明显的例子就是 Lisp,它的语义简单到任何智力正常的程序员都能在一天写出一个简单的后端,简单到用它自己写一个eval不需要 100 行:(以下源码来自 Paul Graham 的文章)

1(defun null. (x)
	2  (eq x '()))
	3(defun and. (x y)
	4  (cond (x (cond (y 't) ('t '())))
	5		('t '())))
	6(defun not. (x)
	7  (cond (x '())
	8		('t 't)))
	
	9; 连接表 x 和 y
	10(defun append. (x y)
	11   (cond ((null. x) y)
	12		 ('t (cons (car x) (append. (cdr x) y)))))
	
	13; 转换 (a b c) (x y z) 形式的表为 ((a x) (b y) (c z))
	14(defun pair. (x y)
	15  (cond ((and. (null. x) (null. y)) '())
	16		((and. (not. (atom x)) (not. (atom y)))
	17		 (cons (list (car x) (car y))
	18			   (pair. (cdr) (cdr y))))))
	
	19; Hash 查找
	20(defun assoc. (x y)
	21  (cond ((eq (caar y) x) (cadar y))
	22		('t (assoc. x (cdr y)))))
	
	23(defun eval. (e a)
	24  (cond 
	25	((atom e) (assoc. e a))
	26	((atom (car e))
	27	 (cond 
	28	   ((eq (car e) 'quote) (cadr e))
	29	   ((eq (car e) 'atom)  (atom   (eval. (cadr e) a)))
	30	   ((eq (car e) 'eq)    (eq     (eval. (cadr e) a)
	31									(eval. (caddr e) a)))
	32	   ((eq (car e) 'car)   (car    (eval. (cadr e) a)))
	33	   ((eq (car e) 'cdr)   (cdr    (eval. (cadr e) a)))
	34	   ((eq (car e) 'cons)  (cons   (eval. (cadr e) a)
	35									(eval. (caddr e) a)))
	36	   ((eq (car e) 'cond)  (evcon. (cdr e) a))
	37	   ('t (eval. (cons (assoc. (car e) a)
	38						(cdr e))
	39				  a))))
	40	; label 函数,绑定符号
	41	((eq (caar e) 'label)
	42	 (eval. (cons (caddar e) (cdr e))
	43			(cons (list (cadar e) (car e)) a)))
	44	; Lambda 表达式,按值传递
	45	((eq (caar e) 'lambda)
	46	 (eval. (caddar e)
	47			(append. (pair. (cadar e) (evlis. (cdr e) a))
	48					 a)))))
	
	49(defun evcon. (c a)
	50  (cond ((eval. (caar c) a)
	51		 (eval. (cadar c) a))
	52		('t (evcon. (cdr c) a))))
	
	53(defun evlis. (m a)
	54  (cond ((null. m) '())
	55		('t (cons (eval.  (car m) a)
	56				  (evlis. (cdr m) a)))))
	
	57(eval. '(cons x '(b c))
	58	'((x a) (y b)))
	59; (a b c)
	

当然其他语言就没有这么简单了。尽管如此,指称语义仍然是描述程序语言语义最精确的手段。不过话说回来,指称语义把程序定义成一个函数,这对 Lisp 这种纯函数式语言还好说,JavaScript 并不是纯函数语言,它有变量,有流程,有副作用,这又该如何定义呢?

解决的方法是使用程序状态 ,把程序看成状态到状态的函数。程序状态的实际形态可以有很多,从直接的内存转储到抽象一些都可以,只要方便表述就行,而顺序的流程,就对应函数复合。程序状态的具体形制要随着语言走。对于 C 这种「低级」语言往往就需要用完整的内存数据表示程序状态。不过 JavaScript 在语义上相对高级,所以表达程序状态可以用更抽象一些的东西。

这里使用的东西是字典,或者说是字符串到「对象」的映射。不仅是程序状态,许多东西——比如对象和对象中的属性——都可以用字典表达。因为字典本质上仍然是「函数」,所以取字典中的用一项就可以用函数调用表达。而向其中写入数据,实际上是返回新函数的过程。

为了保持严谨,在本文中形式语义和语法制导定义将采用一种类似 Lisp 的东西定义,并辅以自然语言描述。我本是想用更加贴近数学符号的系统来表达语义,只是那些符号毫无章法,相反,类 Lisp 的表述则没有类似的问题。传统的数学符号问题真的不少,大家常见的微积分符号就有无数的坑,例如常见的偏微分:

{part f(x, y)} over {part x}

上面的记法称为莱布尼兹符号,它整体的意思是「f(x, y)对x的偏微分」,但是part f(x, y)是啥?形式语义有一个要求,就是它必须是构造性的 ,「3+4」的语义就要由「3」、「4」和「+」的语义组合而成。但是在这些微积分符号里却没法很好定义part f(x, y)是什么。当然,微积分也算是历史悠久的学问,里面有太多遗留问题,况且历史上也有许多设计不错的符号,比如欧拉符号就使用类似算子的记法,把偏微分记做

part_x ~ f(x, y)

这个符号显然要比莱布尼兹符号清晰。

在本文的形式语义里,所有的函数调用都用圆括弧围起来,里面挨个写出函数名和参数。因此,作为「函数」的字典,从中取值就可以写成:

(dictionary key)

字典的行为可以递归定义。首先我们有一个空字典D_omega,它对于所有键都返回「未找到」值omega:

def (D_omega key) = omega

「关键字」(其实也是函数)def 用来定义函数或者其他东西,其形式为def bf ~ pattern ~ = ~ value。上面D_omega的定义应该是最简单的了。其实def 可以拥有复杂的模式匹配功能。比如,向字典中「写入」项目的函数,rojoin,可以定义成:

def [dict rojoin [key -> value]] =
lambda take .
if [value = take]
then value
else (dict take)

方括弧里的是传统些的运算符优先级系统。它们会被转换为圆括弧形式:运算符作为函数,之后跟着两个参数。使用它们的原因是可以减少括弧数量。缩进和换行用来给上一行增加参数,因而上面那个语义定义完全等价于:

def (rojoin dict (-> key value)) = (lambda take . (if [value = take] (then value) (else (dict take))))

除开字典最基本的操作rojoin,还有其他许多重要的操作,比如(keys)函数可以获取一个字典里,所有不映射到omega的键,组成一个列表(老实说下面那个其实已经不是程序了:字符串集可是无穷无尽的):

def (keys dict) =
asList (select Strings (lambda s . [(dict s) ne omega]))

一些复杂的语义里会使用顺序的流程,它用do 加缩进表示。下文是 JavaScript 里加号「+」的语法制导定义,其中还用了let 定义局部「变量」。我没有把异常处理的部分明确写出来,它们和绝大多数语言相似,一旦抛出就沿着堆栈向上抛。

def ((evaluate (AddictiveExpression -> (AddictiveExpression *) `'+` (MultiplicativeExpression *))) sigma ket) = do
let sigma_1 ket = ((evaluate (AdditiveExpression *)) sigma ket)
let sigma_2 ket = ((evaluate (MultiplicativeExpression *)) sigma_1 ket)
let lprim = (ToPrimitive (GetValue (sigma_1 ket EV)))
let rprim = (ToPrimitive (GetValue (sigma_2 ket EV)))
if (or (isin String lprim) (isin String rprim))
then [sigma_2 ket rojoin [E rm -> (strcat (ToString lprim) (ToString rprim))]]
else [sigma_2 ket rojoin [E rm -> [(ToNumber lprim) + (ToNumber rprim)]]]

语法树节点的形状就如上文里模式所写的那样,写成产生式的样子,不过字母前面打个'来和符号区分。引用这些符号所代表的节点,直接写它们的模式即可,必要的时候会有下标。程序状态会围在~ ket符号里,用来和其他东西区分。(老实说在我写到这里的时候我非常想把这套语义系统弄成个程序语言,但是我挖的坑已经够多了,所以……)

def (evaluate (Decimal *) sigma ket) =
return [sigma ket rojoin [EV -> (numVal (Decimal *))]]

原文链接: http://typeof.net/s/jsmech/05.html

0     0

评价列表(0)