在時間上分離的可計算函數(shù)的遞歸性質(zhì)具有元語言的抽象能力

在上一篇文章中愕乎，我用lambda實現(xiàn)了一個快速排序的算法炼邀，這個算法的實現(xiàn)和大部分利用索引來實現(xiàn)的算法不同槽片，它沒有使用變量的賦值和修改，相反的是普筹，它只有純函數(shù)式的邏輯流程，而且從本質(zhì)上來說隘马，我們的語言構(gòu)建塊，已經(jīng)改變了妻顶，加號有了一個新的含義酸员，它可以在時間上完全分離讳嘱，生成一個全新的版本幔嗦，而不會對現(xiàn)有的系統(tǒng)產(chǎn)生破壞性的作用，由于我們的語言是基于消息和中綴式的數(shù)學(xué)定義沥潭，那么它的使用邀泉，看起來和本身系統(tǒng)內(nèi)部的原生函數(shù)，并沒有太大的不同钝鸽，我們的系統(tǒng)的可分解性汇恤，達到了語言級別，每一個消息的參數(shù)響應(yīng)對象拔恰，都是在上下文中約定的因谎，我們可以再添加無窮多個遞歸的消息棧，它們都可以利用同一個符號來表達不同的含義颜懊。

在smalltalk中财岔，這個語法被實現(xiàn)為左結(jié)合，實際上還有更初始的方法河爹，就是使用數(shù)學(xué)符號的運算符結(jié)合匠璧，這個思想大致可以在sasl,miranda,erlang,prolog和haskell中找到，由于alan kay受到lisp的影響比較大咸这，所以采用了這樣的定義夷恍，我們的新函數(shù)式語言，希望通過重新給數(shù)學(xué)符號添加定義炊苫，從而給這個新的邏輯工具帶來不一樣的樣子裁厅，我們?nèi)怂伎紗栴}，也是具有上下文的侨艾，這些上下文执虹，最終把動態(tài)的規(guī)則構(gòu)成了一個靜態(tài)的形象，比如說直角坐標(biāo)系唠梨，函數(shù)圖像來表現(xiàn)一個物體的狀態(tài)袋励，等等等等，一個函數(shù)就是一個全局的狀態(tài)參量，它精確描述了一個系統(tǒng)每一個瞬間的狀態(tài)茬故，使用它們之間復(fù)雜的遞歸關(guān)系來對整個世界進行建模盖灸。

我們的系統(tǒng)就是在lambda函數(shù)的基礎(chǔ)上，添加這樣一個分離式的時態(tài)邏輯的語法糖磺芭，它每一個新的表達式赁炎，就是給系統(tǒng)增加新的規(guī)則，一個規(guī)則定義了一個概念在某個上下文的特定含義钾腺，這個形式我們使用三種方法來描述徙垫，第一種是scheme版本，(lambda (X) E),第二種是miranda版本放棒，f(X) = E姻报，第三種是smalltalk版本，f X1 = E1, f X2 = E2...间螟，需要注意的是吴旋，smalltalk版本雖然很好，但是它可能在某些地方不太簡單厢破，所以我們使用miranda版本來作為一個替代荣瑟，miranda版本看起來更像我們普通人寫一個函數(shù)該有的樣式，然后我們的基礎(chǔ)庫的表現(xiàn)形式也是smalltalk樣式溉奕，但是這些基礎(chǔ)操作符和對象褂傀，它們都是純函數(shù)式的，也就是說加勤，它們用起來雖然是smalltalk的語法仙辟，但是它不具備可修改性，它們可以在遞歸過程中返回一個新的自身對象鳄梅，也就是self這個對象叠国，它是在時間上解耦了的，所以不會出現(xiàn)持續(xù)遞歸的現(xiàn)象戴尸，這種對系統(tǒng)的抽象導(dǎo)致它看起來也具有狀態(tài)粟焊，然而它自己已經(jīng)在時間中消失了，取代它的是它的一個新的對象孙蒙，這個對象也不具備狀態(tài)项棠，但是它可以被用來生成新的對象。

我們先來看第一個程序挎峦，平方的寫法：

//定義
square := f(x) = (x * x);
//使用
square 5;
= 25

第二個程序香追，階乘:

//第一種寫法
fac := f 1 = 1, f(n) = n * (fac (n - 1));
//第二種寫法
fac := f(n) = n == 1
 true: 1
 false: n * (fac (n-1));
//第三種寫法
fac 1 = 1;
fac (n) = n * (fac (n - 1));

因為f(x) = E的形式可以寫為一個匿名函數(shù)，所以我們可以這樣：

(f(x) =  (x * x)) 5
= 25

因為列表實際上是一種閉包對象坦胶，但是我們專門用一個符號來代表列表透典，這個符號就是[]晴楔，[1 2 3] = [1. 2. 3. [] ]，這是一個鏈表的結(jié)構(gòu)峭咒。
然后我們可以支持模式匹配和列表解析税弃，也就是說，列表可以提前解析

h.t = [1.2.3.[]];
h
=1
t
=[2.3.[]]

然后我們可以給列表的第一個元素添加標(biāo)簽凑队，從而給系統(tǒng)添加新的匹配規(guī)則：

vec.h1.t1 * vec.h2.t2 = (h1 * h2) + (t1 * t2) ;
vec.h1.[] * vec.h2.t2 = 'err' ;
vec.h1.t1 * vec.h2.[] = string.[$e $r $r];
vec.[] * vec.[] = 0 ;

我們把第二個err提示寫為string.[$e $r $r]则果，那么大家大概能理解內(nèi)部的一些實現(xiàn)，上面這幾條規(guī)則漩氨，定義了向量的乘法短条。
然后我們可以寫一個新的大于規(guī)則，列表的大于規(guī)則才菠。

h.t > x = h > x true: [h] false: [] + t > x;
[] > x = [];

這個規(guī)則匹配起來會是這樣

[1 2 3 4 5 6] > 2 ;
= [3 4 5 6]

然后我們可以使用宏定義，實際上宏定義并不特殊贡定，它就是一個規(guī)則生成模板赋访。

gen-compare compare := 
h.t compare x = h compare x true: [h] false: [] + t compare x,
[] compare x = [];

這樣我們就可以定義其他的運算符

gen-compare <=;
gen-compare <;
gen-compare >=;

有了這些之后，我們還想要什么呢缓待，我們可能想知道蚓耽，list + list這個是什么意思，也就是說

[1 2 3 4] + [2 3 4 5]
= 旋炒？

也許我們的List可能是集合步悠，也可能是向量，還有可能是字符瘫镇，還可能是矩陣元素鼎兽，這些都無所謂，我們只需要加標(biāo)簽就可以铣除，但是我們現(xiàn)在可以定義哪些運算呢谚咬，我們可以有集合，有向量尚粘，有這個列表择卦。

//列表的加法
[h.t] + [x] = [h] + (t + [x])
[h] + [x] = [h x]
//向量的加法
vec.[h1.t1] + vec.[h2.t2] = vec.([(h1 + h2)] + (t1 + t2))
vec.[] + vec.[] = vec.[]

有了這些構(gòu)建工具之后，我們可以寫一些程序了郎嫁，比如說快速排序

h.t qst = (h <= t qst) + [h] + (h > t qst)
[]  qst = []

矩陣乘法

//定義一個矩陣秉继，它的行是r,列是c,數(shù)據(jù)是d
mk-mx r c d :=
  f r = r ,
  f c = c ,
  f(r: c:) = (d ((r: * c) + c:));
//這里之所以可以這么寫是因為list的實現(xiàn)內(nèi)部可以利用索引直接作為參數(shù)獲取它的值
//list本身是一個函數(shù)，具體實現(xiàn)可以參考上一篇文章的my-list對象泽铛。

//定義一個方法尚辑，取得矩陣的某列
c-r mx c-i =
  (c-l i = i == mx r
    true: []
    false: [(mx r:i c:c-i)] + (c-l (i + 1)))
  c-l 0;
//定義一個方法，取得某行
r-f mx r-i =
  (r-l i = c-i == mx c
    true: []
    false: [(mx r:r-i col:i)] + (r-l (i + 1)))
  r-l 0;
//這是乘法厚宰，它從A腌巾，B矩陣中得到另一個新的矩陣
mx.A * mx.B = (A c) == (B r)
   (true: 
       f r = A r ,
       f c = B r ,
       f(r: c:) = vec.(r-f A r:) * vec.(c-f B c:))
   false: 'err';

可以看出來遂填，這個時間分離的遞歸方法完全用函數(shù)的思維去對數(shù)據(jù)進行建模，因為所有數(shù)據(jù)都是函數(shù)澈蝙，那么它的上下文可以無限的精簡吓坚，以至于寫出來的每一個程序就是一門語言，它的意義是上下文相關(guān)的灯荧，所以具有極端的伸縮性礁击。