柯里化的前生今世（三）：語言和同像性

03-04

按照故事情節的正常發展，我們這一篇該介紹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 | SymbolS-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個符號+，1和2構成的列表。

列表是數據，加法調用是程序，它們雖然採用了相同的編碼，可是我們沒有辦法區分。

首先想到的就是讓它們採用不同的編碼。例如：

我們把函數調用編碼為+[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語言