未定義是值嗎?

December 14, 2021

來看看〈是的!不是!〉中到底定義了什麼?

let yes = f => y => f();
let no = x => f => f(); 
let when = c => c;

三個函式?不!三個「值」!函式也是值!因此 yes 是個值,no 也是個值,既然如此,可以用來替代仍借助於 JavaScript 的 truefalse 嗎?可以的!

lambda 表示式就是值

這也給個機會,重新思考什麼是值?在多數程式語言中,值就是個定義好的符號,像是 truefalse123 等,在 lambda 演算的世界中,lambda 表示式就是值,可以用 lambda 表示式來定義 truefalse,這邊的 yesno 就是實際的例子,進一步地 123 也可以用 lambda 表示式來定義(這在後面的篇幅會談到)。

來試著不使用 ?:truefalse 來完成 map(list(elems(1)(2)(3)))(elem => elem - 1) 如何?首先,List 的結構不用修改:

let pair = l => r => f => f(l)(r);
let left = p => p(l => _ => l);
let right = p => p(_ => r => r);

let nil = pair(undefined)(undefined);
let con = h => t => pair(h)(t);
let head = left;
let tail = right;

接下來,看看 let isEmpty = lt => head(lt) === undefined;,若有個 lt 代表著 List,isEmpty 現在希望必須傳回 yesno 而不是 truefalseisEmpty 主要是看看首元素有沒有定義,雖然可以寫 let isEmpty = lt => head(lt) === undefined ? yes : no;,不過來想想看 undefined,它該算是個值嗎?

定義 undef

undefined 是值嗎?或者只是個唯一的符號?undefined 表示沒有東西、也不是容器、沒有對應的操作,什麼也沒有?

若就 JavaScript 來說,將 undefined 當成一個值,因此,就目前來說可以利用這點,在目前的箭號函式表示中,將 undefined 當成是符號,讓 JavaScript 代為判斷 undefinedyes 還是 no

let is_undefined = n => n === undefined ? yes : no; 

從 lambda 演算的角度來看,is_undefined 會是個黑箱,是運算機器(這邊就是 JavaScript 環境)的一部份,因此使用 ===?: 就不是問題,這黑箱只要看看是不是 undefined 符號,寫下 yesno 的 lambda 表示式就是了。

實際上在目前的箭號符號表示方式中,有些地方雖然沒有寫出 undefined,然而隱含著使用了 undefined 這個符號,例如,有個函式 f = x => x + 1,若以 f() 執行,就 JavaScript 環境來說,x 就會是 undefined,也就是就 lambda 表示式來說,可以看成是 f(undefined),隱含地傳入了 undefined 符號。

如果直接使用 undefined 真的讓你感到不舒服,那就來定義一個 undef 好了:

let undef = (_ => _)();

就 lambda 演算角度來看,(_ => _)() 像是個 lambda 表示式,如果以人力來運算,就是看看是不是 (_ => _)(),確定是不是未定值的表示式;如果使用 JavaScript 執行環境來運算,undef 也還是 undefined,最終,還是依然有個黑箱:

let is_undef = n => n === undef ? yes : no;

重構

雖然黑箱依然存在,然而就目前來說,這可以讓事情簡單一些,最終的運算表示式中,也可以不出現 undefined 這個 JavaScript 中的元素,爽度應該會高一些。例如 List 的相關定義現在可以是:

let pair = l => r => f => f(l)(r);
let left = p => p(l => _ => l);
let right = p => p(_ => r => r);

let nil = pair(undef)(undef);
let con = h => t => pair(h)(t);
let head = left;
let tail = right;

於是,isEmpty 現在可以傳回 yesno 了:

let isEmpty = l => is_undef(head(l));

接下來,可以實現幾個簡單的函式,像是 lensum 之類的:

let len = l => when(isEmpty(l))
					(_ => 0)
					(_ => 1 + len(tail(l)));

let sum = l => when(isEmpty(l))
					(_ => 0)
					(_ => head(l) + sum(tail(l)));

別忘了,由於 whenyesno 實現了惰性,when 接下來的兩個值,必須是個函式,在這邊略為排版了一下,看起來像是有了新的語言了。

在〈是的!不是!〉也談過,when 只是增加一層語義,實際上什麼也不做,也就是說,上例中的 when(isEmpty(l)) 直接寫為 isEmpty(l),函式也可以正常運作,就上面兩個函式來說,由於 isEmpty 名稱上還算清楚,是可以這麼做,然而若不是這類的名稱,加上 when 還是比較好的方式。

接下來重構一下 list 等函式:

let rcon = t => h => when(is_undef(h))
							(_ => t)
							(_ => rcon(con(h)(t)));

let rev = r => l => when(isEmpty(l))
						(_ => r)
						(_ => rev(con(head(l))(r))(tail(l)));

let reverse = l => rev(nil)(l);

let elems = rcon(nil);

let list = es => reverse(es());

來試試看:

let lt = list(elems(1)(2)(3)(4));
console.log(len(lt));    // 4
console.log(sum(lt));    // 10

實現一下 map 函式:

let map = l => f => when(isEmpty(l))
						(_ => nil)
						(_ => con(f(head(l)))(map(tail(l))(f)));

如果有個輔助函式為 array,可以將 List 轉為 JavaScript 陣列,那麼底下會顯示 [0, 1, 2]:

let lt2 = map(list(elems(1)(2)(3)))(elem => elem - 1);
console.log(array(lt2));

輔助用的函式與 lambda 演算沒直接關係,程式碼如下:

function array(lt) {
	function arr(acc, l) {
		if(isEmpty(l) === yes) {
			return acc;
		} else {
			return arr(acc.concat([head(l)]), tail(l));
		}
	}
	return arr([], lt);
}

來試著像之前那樣,將 map(list(elems(1)(2)(3)))(elem => elem - 1) 全部使用箭號函式表示:

(f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(map => l => f => (l => is_undef((p => p(l => _ => l))(l)))(l)(_ => ((l => r => f => f(l)(r))((_ => _)())((_ => _)())))(_ => (h => t => (l => r => f => f(l)(r))(h)(t))(f((p => p(l => _ => l))(l)))(map((p => p(_ => r => r))(l))(f))))((es => (l => ((f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(rev => r => l => (l => is_undef((p => p(l => _ => l))(l)))(l)(_ => r)(_ => rev((h => t => (l => r => f => f(l)(r))(h)(t))((p => p(l => _ => l))(l))(r))((p => p(_ => r => r))(l)))))((l => r => f => f(l)(r))((_ => _)())((_ => _)()))(l))(es()))((f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(rcon => t => h => is_undef(h)(_ => t)(_ => rcon((h => t => (l => r => f => f(l)(r))(h)(t))(h)(t))))((l => r => f => f(l)(r))((_ => _)())((_ => _)()))(1)(2)(3)))(elem => elem - 1)

想要在 JavaScript 環境中執行上面的箭號函式的話,只需要有 is_undef 的定義,也就是這個黑箱作為環境邊界。

如果不打算將環境邊界定得那麼嚴格,可以將 is_undef 替換為以下,就可以直接運算得到結果了:

n => n === (_ => _)() ? (f => y => f()) : (x => f => f())`,成為 `(f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(map => l => f => (l => (n => n === (_ => _)() ? (f => y => f()) : (x => f => f()))((p => p(l => _ => l))(l)))(l)(_ => ((l => r => f => f(l)(r))((_ => _)())((_ => _)())))(_ => (h => t => (l => r => f => f(l)(r))(h)(t))(f((p => p(l => _ => l))(l)))(map((p => p(_ => r => r))(l))(f))))((es => (l => ((f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(rev => r => l => (l => (n => n === (_ => _)() ? (f => y => f()) : (x => f => f()))((p => p(l => _ => l))(l)))(l)(_ => r)(_ => rev((h => t => (l => r => f => f(l)(r))(h)(t))((p => p(l => _ => l))(l))(r))((p => p(_ => r => r))(l)))))((l => r => f => f(l)(r))((_ => _)())((_ => _)()))(l))(es()))((f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(rcon => t => h => (n => n === (_ => _)() ? (f => y => f()) : (x => f => f()))(h)(_ => t)(_ => rcon((h => t => (l => r => f => f(l)(r))(h)(t))(h)(t))))((l => r => f => f(l)(r))((_ => _)())((_ => _)()))(1)(2)(3)))(elem => elem - 1)

還有可能再進一步嗎?例如,map(list(elems(1)(2)(3)))(elem => elem - 1) 中,連 1、2、3 甚至 - 都用箭號函式來表示?似乎是可以挑戰看看的對象…