柯里化的前生今世(三):语言和同像性

  1. 云栖社区>
  2. 博客>
  3. 正文

柯里化的前生今世(三):语言和同像性

何幻 2016-10-28 13:47:54 浏览2008
展开阅读全文

按照故事情节的正常发展,我们这一篇该介绍Racket语言的语法了。
可是,在大局观上,我们还没有达成共识。
对于一个概念来说,我们不止要学会怎样描述它,还要学会理解它的内涵。
因此,这篇还是在打基础,俗称,引言。。

关于

在上一篇中,我们提到了Lisp语言家族,看到了关于Lisp最美丽的传说,我们提到了Racket,以及它的IDE,DrRacket。

本文将从目标语言和元语言,同像性(Homoiconicity),引用等这些角度来深入的讨论Lisp,
浅尝辄止,毕竟不是一个好习惯。

目标语言和元语言

当我们讨论一件事物时,我们所使用的语言被称为对象语言。
而当我们谈论一种语言时,我们所使用的语言被称为元语言。

在任何语言研究中,都有一种作为研究对象的语言,还有一种由研究者用来谈论对象语言的元语言。
对象语言与元语言是相对而言的。
任何语言,无论它多么简单或者多么复杂,当它作为被谈论的对象的时候,它就是对象语言;
当它用来讨论一种语言的时候,它就是元语言。

区分开目标语言和元语言,是学好Lisp的第一步,也是理解Lisp元编程的第一步。

形式语言

日常生活中,我们有了这样的认识。
我们所了解的汉字总是有限的,但是我们能说的话,却是无限的。
可以说出任意长度的汉字序列。

程序语言也是如此。
有人说编程,不就是输入A到Z吗,指的就是这个编程语言的“字母表”。
字母表所包含的字母,是有限的,但是可以写出无限多个“句子”。

“语言”,正是这些“句子”的集合。
所谓形式语言,指的是用精确的数学,或机器可处理的公式,定义的语言。
相应的数学和计算机科学分支叫做形式语言与自动机理论,
它只研究语言的语法而不讨论它的语义。

当初,为了研究语言的性质,人们从两个角度出发,
一个是从语言的识别角度来看,提出了自动机理论。
另一个是从语言的生成角度来看,有乔姆斯基开创的形式语言理论。
这两个理论之间,又是互相关联的。

文法

文法提供了一种方便的方法来定义“句子”的无限集。

为了描述语言的结构,John Backus和Peter Naur创造了一种语言的描述方法,
称为BNF(Backus-Naur Form)。

expr ::= term { "+" term | "-" term }.
term ::= factor { "*" factor | "/" factor }.
factor ::= "(" expr ")".

BNF表示中的每一行,称为一个“产生式”,::=表示左边的项可以由右边的项来产生。
其中,用引号括起来的项,称为“终结符”,相当于字面量。
不用引号括起来的项,称为“非终结符”,它们可以由其他项组成。

{…}是约定好了的符号,用来表示它包含的项可以出现0次或更多次。
常用的还有[…],用来表示,可以出现也可以不出现。

以上BNF描述了算术表达式的语法。
例如:1*(2+3),可以从expr开始生成出来,

expr
=> factor “*” factor
=> factor “*” “(” expr “)”
=> factor “*” “(” term “+” term “)”
=> 1 “*” “(” 2 “+” 3 “)”

expr称为“开始符号”。

综上,一个语言的所有终结符,非终结符,产生式,开始符号,
构成了这个语言的文法。

语言的分类

乔姆斯基,根据语言文法产生式的特点,把语言分为了4类。
不同的文法,能描述不能范围的语言集合,虽然它们都是无限集。

0型文法,能力最强,可以产生递归可枚举语言。
1型文法,能力稍弱,可以产生上下文有关语言。
2型文法,能力次之,可以产生上下文无关语言。
3型文法,能力最弱,可以产生正则语言。

这些文法,建立了一个从大到小,互相包含的,语言集合的层次关系。
例如:正则语言,一定是上下文无关语言,反之,则不成立。
其中,2型和3型文法用的最多,有特殊的名字,称为,上下文无关文法,正则文法。

我们似乎发现了,这里也出现了“正则”两个字,难道与正则表达式有关?
确实,正则表达式,是正则文法的便利写法。
正则表达式所描述的语言,就是正则语言。

S表达式

了解过Racket之后,我们发现Racket程序都用一种称为S表达式的语法写成。
S表达式,是Lisp语言的特色,它是二叉树的一种线性编码。

我们知道二叉树是很重要的数据结构,可以用来存储结构化的数据。例如:

     *
   /   \
  *     *
 / \   / \
a   b c   d

二叉树的每个节点,或者是叶节点,或者有2个子节点,叶节点可以用来存储数据。
可是,这样表示二叉树,太麻烦了,不容易书写。
于是,先哲们发明了“点对表示法”,((a . b) . (c . d))可以表示上面的二叉树,
其中“.”表示节点。

S表达式是点对表示法的形式定义:

Atom ::= Num | Symbol
S-exp ::= Atom | "(" S-exp "." S-exp ")"

所以,S表达式或者是原子(Atom),或者是递归的由其他S表达式构成的点对。

实际使用时,书写S表达式,还要同时写很多点号“.”,这也是一件麻烦的事情。
因此,Lisp语言定义了一套S表达式的化简规则。
(1)如果一个点号右邻一个左括号,那么就可以将这个点号,左括号以及匹配的右括号,一起去掉。
例如:(a . (b . c)) <=> (a b . c)

(2)如果一个点号右邻原子nil,那么就可以把这个点号和原子nil,一起去掉。
例如:(a . (b . nil)) <=> (a b . nil) <=> (a b)

同像性(Homoiconicity)

同像性,指的是程序和程序所操作的数据采用了统一编码。

Lisp语言使用了S表达式,例如,(fn x)
既可以看做是程序,用参数x调用函数fn,
也可以看做是数据,由符号fn和符号x构成的列表。

同像性使得我们,可以像处理数据一样处理代码。
做一些代码转换之类的工作,十分简单。

例如,
当遇到(fn x)时,
我们可以让它先转换成,

(begin
    (display x)
    (gn x))

然后再执行。

甚至也可以用来定义变量,

(define-with-display (f a)
    (g a))

转换成,

(define (f a)
    (display a)
    (g a))

这种代码层面的转换称为“宏”(macro)。

引用

在Lisp语言中,引用(quotation)是一个很独特的概念。
这与按引用传参(call by reference)完全是两码事。

在Lisp程序中,我们知道(+ 1 2)是一个加法调用,
但是它也可以表示由3个符号+12构成的列表。
列表是数据,加法调用是程序,它们虽然采用了相同的编码,可是我们没有办法区分。

首先想到的就是让它们采用不同的编码。例如:
我们把函数调用编码为+[1;2],而列表编码为(+ 1 2)
人们一开始也是这么做的,+[1;2]称为M表达式,(+ 1 2)称为S表达式。

可是,后来人们发现,如果用Lisp语言来处理Lisp程序文本时,
不同的编码,会增加难度,即,失去了同像性的种种优势。

另一方面,程序主要是由函数调用组成的,把程序看成数据是更少见的一种场景。
所以,人们进行了以下编码,
函数调用编码为(+ 1 2)
而列表编码为(quote (+ 1 2))

即,(+ 1 2)求值,会导致函数调用。
(quote (+ 1 2))求值,会得到一个列表。
于是,我们就统一的用S表达式,完成了对程序和数据的相同编码。

后文所需要的基础

下一篇文章,我们要回到高阶函数上来了,我们要写一个简易的解释器,
实现词法作用域,然后自然的得到闭包这种数据结构。
所以,Racket语法方面,大家还是抽空多了解下吧,需要介绍吗?

参考

元语言
形式语言
S表达式
同像性
程序设计语言:实践之路
LISP语言

网友评论

登录后评论
0/500
评论
何幻
+ 关注