真的未定義?

December 15, 2021

在〈算術的編碼〉中實現了 $0$1$2$3addsub 等,這就可以用來改寫〈未定義是值嗎?〉的成果,像是 lensum,就可以改寫為:

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

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

其他的函式都可以進行這類的改寫,來整理一下目前已經完成的東西好了,以便之後討論:

let y = f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n)));

let undef = (_ => _)();
let is_undef = n => n === undef ? yes : no;

let yes = f => _ => f();
let no = _ => f => f(); 
let when = _ => _;

let not = b => b(_ => no)(_ => yes);

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;

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

let $0 = _ => x => x;
let $1 = f => x => f(x);
let $2 = f => x => f(f(x));
let $3 = f => x => f(f(f(x)));

let is_$0 = n => n(_ => no)(yes);

let succ = n => f => x => f(n(f)(x));
let add = m => n => n(succ)(m);

let pair_succ = p => pair(right(p))(succ(right(p)));
let prev = n => left(n(pair_succ)(pair($0)($0)));
let sub = m => n => n(prev)(m);

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

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

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 map = l => f => when(isEmpty(l))
						(_ => nil)
						(_ => con(f(head(l)))(map(tail(l))(f)));

let lt = list(elems($1)($2)($3));
let lt2 = map(list(elems($1)($2)($3)))(elem => sub(elem)($1));

console.log(natural(len(lt)));
console.log(natural(sum(lt)));
console.log(array(lt2));

function natural(n) {
	return n(i => i + 1)(0);
}

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

實際上不會用到的參數,在上面也都用 _ 來表示了,這樣會容易辨識一些。看起來除了 is_undef 這個黑箱中的 ===?: 之外,都使用箭號函式來表示了,沒有出現 123+- 這些 JavaScript 中的元素了!YA~~~~~!

定義 nil

YA~~~~?還是不太甘心啊!都已經將 ===?: 逼到 is_undef 了,就不能給它們一個痛快嗎?(咦?)…

換個角度來想好了,有沒有辦法不使用 is_undef,如果可以不使用到 is_undef,自然地,就不會有 ===?: 的問題,目前有兩個地方使用了 is_undef,也就是 isEmpty 以及 rcon

先來處理 isEmpty,它之所以要使用 is_undef,是要判斷傳進來的是否為 nil,而這是因為 nil 被定義為 pair(undef)(undef),實際上就是 pair(undefined)(undefined),如果能改變 nil 的定義,令其不使用 undefinedisEmpty 自然就可以不使用 is_undef

仔細想想,為什麼現在的 nil 會是 pair(undefined)(undefined)?這是在〈頭尾成對〉中開始定義的,目的只是為了與 [undefined, undefined] 對應,仔細想想,這樣的 nil 真的是值嗎?pair(undefined)(undefined) 真的是值嗎?pair(undefined)(undefined) 是個 lambda 表示式嗎?

你也許會想,不是可以用 pair((_ => _)())((_ => _)()) 來表示?不對!實際上,這只是 JavaScript 環境的蜜糖,其實真相是 pair((_ => _)(undefined))((_ => _)(undefined)),它並不是 lambda 表示式!

先不管左值、右值是什麼,姑且令 nilpair(a)(b),也就是 nilf => f(a)(b),而 isEmpty(nil) 希望是 yes,那麼簡單的想法是,a 如果是 yesleft(nil) 就可以當成是 isEmpty 的傳回值,或者是 byesright(nil) 就可以當成是 isEmpty 的傳回值。

那就試著將 nil 定義為 pair(yes)(yes) 呢?也就是 nilf => f(yes)(yes),然而仔細想想,無論 fleftright,結果不都傳回 yes,也就是 nil 直接是 f => yes 不就好了?

let nil = _ => yes;

f 是什麼都不重要,因此用 _ 來表示就可以了。現在解決了 isEmpty 一半的問題,只要遇到 nil 就可以傳回 yes,那麼其他的 List 呢?只有 nil 會直接忽略傳入的函式直接傳回 yes,既然如此,其他的 List 會呼叫傳入的函式,那麼傳入的函式一律傳回 no 就可以了:

let isEmpty = l => l(_ => _ => no);

或者定義個更明確的 is_nil 名稱也可以:

let is_nil = l => l(_ => _ => no);
let isEmpty = is_nil;

無數字

解決 isEmpty 了,現在來看 rcon,它之所以需要用到 is_undef,其實是為了代表不再輸入數字,可以將目前收集數字用的 List 傳回了,若有個數字 $$ 代表著不再輸入數字,而且有個 is_$$ 只在看到 $$ 就傳回 yes,那就可以不使用 is_undef 了。

實際上,這樣的數字早就有了,那就是 $0,而 is_$0 只會在看到 $0 時傳回 yes,然而,如果用 $0 來代表數字輸入結束了,那 List 中的元素,就不能有 $0 了。

還是來定義一個新的 $$ 好了,它要是什麼表示式呢?先看看 is_$0 的定義,n => n(_ => no)(yes) 只在 $0 時傳回 yes,那麼 n => n(_ => no)(no) 就表示全部的自然數都會傳回 no 了,就先寫下來吧!

let is_$$ = n => n(_ => no)(no);

還有什麼數可以令 is_$$ 傳回 yes?顯然地,必須是 x => y => ? 形式,這樣才能套用 _ => nono,然後,必須忽略傳入的 _ => no,這樣就不可能呼叫它而傳回 no,也必須忽略傳入的 no,這樣就不會傳回 no,因此會是 _ => _ => ? 形式,呼叫結果必須是 yes,這樣 is_$$ 才會傳回 yes,因此會是 _ => _ => yes

let $$ = _ => _ => yes;

好了!現在 is_$$($$) 會是 yes,至於 is_$$($0)is_$$($1)is_$$($2) 等都會是 no 了!只是 $$ 這怪數字到底是什麼?這麼想會合理一些,它是數字沒錯,然而不是自然數,由於目前的程式只考量自然數,暫時將 $$ 如上定義就夠了。

於是 rcon 可以改為:

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

YA!終於連 rcon 都沒使用 is_undef 了,別忘了 list 也要做個修改,最後必須傳入 $$

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

這倒提醒了一件事,只要呼叫函式 f 時是 f() 形式,其實都相當於 f(undefined),就修改到目前來說,還有兩個地方有這種呼叫形式,那就是 yesno 的定義,怎麼辦?

無用

目前的程式,f() 形式的呼叫,實際上都忽略了傳入的值,這表示傳入什麼都沒關係,反正會被忽略,它是個無用的引數,什麼都不用做,那就來定義個 useless

let unit = _ => _;
let no_use = unit;

let yes = f => _ => f(no_use);
let no = _ => f => f(no_use); 
let when = unit;

既然無用,no_use 定義為什麼都可以,只要它是個 lambda 表示式就好了,在上頭也定義了一個 unit,給什麼就傳回什麼,然後 no_use 單純就掛個 unit,仔細檢視程式,when 其實也是 unit,就也一併修改了。

這次就真的去掉「未定義」這東西了,仔細想想,很多時候會用上「未定義」這概念,其實只是懶得想定義,然後隨便搪塞個「未定義」,就像 nil 之前會用上 undefined,其實是想判斷「是否處於某邊界值」,$$ 出現之前會用上 undefined,也是想判斷「是否處於邊界值」,既然如此,分別明確地定義出可判斷是否的邊界值,就可以避免同時使用模糊的 undefined

lambda expression

底下是整個修改後的成果:

let y = f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n)));

let unit = _ => _;
let no_use = unit;

let yes = f => _ => f(no_use);
let no = _ => f => f(no_use); 
let when = unit;

let not = b => b(_ => no)(_ => yes);

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

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

let is_nil = l => l(_ => _ => no);
let isEmpty = is_nil;

let $0 = _ => x => x;
let $1 = f => x => f(x);
let $2 = f => x => f(f(x));
let $3 = f => x => f(f(f(x)));
let is_$0 = n => n(_ => no)(yes);

let $$ = _ => _ => yes;
let is_$$ = n => n(_ => no)(no);

let succ = n => f => x => f(n(f)(x));
let add = m => n => n(succ)(m);

let pair_succ = p => pair(right(p))(succ(right(p)));
let prev = n => left(n(pair_succ)(pair($0)($0)));
let sub = m => n => n(prev)(m);

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

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

let rcon = t => h => when(is_$$(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 map = l => f => when(isEmpty(l))
						(_ => nil)
						(_ => con(f(head(l)))(map(tail(l))(f)));

let lt = list(elems($1)($2)($3));
let lt2 = map(list(elems($1)($2)($3)))(elem => sub(elem)($1));

console.log(natural(len(lt)));
console.log(natural(sum(lt)));
console.log(array(lt2));

function natural(n) {
	return n(i => i + 1)(0);
}

function array(lt) {
	function arr(acc, l) {
		return when(isEmpty(l))
					(() => acc)
					(() => arr(acc.concat([natural(head(l))]), tail(l)));
	}
	return arr([], lt);
}

想要試著將 map(list(elems($1)($2)($3)))(elem => sub(elem)($1)) 全部替換,完全使用箭號函式表示,不需要用到 let 嗎?結果會是…

(f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(m => l => f => (_ => _)((l => l(_ => _ => (_ => f => f(_ => _))))(l))(_ => (_ => (f => _ => f(_ => _))))(_ => (h => t => (l => r => f => f(l)(r))(h)(t))(f((p => p(l => _ => l))(l)))(m((p => p(_ => r => r))(l))(f))))((e => (l => (f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(v => r => l => (_ => _)((l => l(_ => _ => (_ => f => f(_ => _))))(l))(_ => r)(_ => v((h => t => (l => r => f => f(l)(r))(h)(t))((p => p(l => _ => l))(l))(r))((p => p(_ => r => r))(l))))(_ => (f => _ => f(_ => _)))(l))(e(_ => _ => (f => _ => f(_ => _)))))((f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(r => t => h => (_ => _)((n => n(_ => (_ => f => f(_ => _)))(_ => f => f(_ => _)))(h))(_ => t)(_ => r((h => t => (l => r => f => f(l)(r))(h)(t))(h)(t))))(_ => (f => _ => f(_ => _)))(f => x => f(x))(f => x => f(f(x)))(f => x => f(f(f(x))))))(e => (m => n => n(n => (p => p(l => _ => l))(n(p => (l => r => f => f(l)(r))((p => p(_ => r => r))(p))((n => f => x => f(n(f)(x)))((p => p(_ => r => r))(p))))((l => r => f => f(l)(r))(_ => _)(_ => x => x))))(m))(e)(f => x => f(x)))

這一串東西真的可以運算嗎?可以喔!如果配合以下的輔助函式,可以轉換為 JavaScript 陣列:

function array(lt) {
    let unit = _ => _;
    let no_use = unit;

    let no = _ => f => f(no_use); 
    let when = unit;

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

    let head = left;
    let tail = right;

    let is_nil = l => l(_ => _ => no);
    let isEmpty = is_nil;
        
    function natural(n) {
        return n(i => i + 1)(0);
    }

    function arr(acc, l) {
        return when(isEmpty(l))
                   (() => acc)
                   (() => arr(acc.concat([natural(head(l))]), tail(l)));
    }
    return arr([], lt);
}

那麼底下就會顯示 [0, 1, 2]:

console.log(
	array(

(f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(m => l => f => (_ => _)((l => l(_ => _ => (_ => f => f(_ => _))))(l))(_ => (_ => (f => _ => f(_ => _))))(_ => (h => t => (l => r => f => f(l)(r))(h)(t))(f((p => p(l => _ => l))(l)))(m((p => p(_ => r => r))(l))(f))))((e => (l => (f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(v => r => l => (_ => _)((l => l(_ => _ => (_ => f => f(_ => _))))(l))(_ => r)(_ => v((h => t => (l => r => f => f(l)(r))(h)(t))((p => p(l => _ => l))(l))(r))((p => p(_ => r => r))(l))))(_ => (f => _ => f(_ => _)))(l))(e(_ => _ => (f => _ => f(_ => _)))))((f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))(r => t => h => (_ => _)((n => n(_ => (_ => f => f(_ => _)))(_ => f => f(_ => _)))(h))(_ => t)(_ => r((h => t => (l => r => f => f(l)(r))(h)(t))(h)(t))))(_ => (f => _ => f(_ => _)))(f => x => f(x))(f => x => f(f(x)))(f => x => f(f(f(x))))))(e => (m => n => n(n => (p => p(l => _ => l))(n(p => (l => r => f => f(l)(r))((p => p(_ => r => r))(p))((n => f => x => f(n(f)(x)))((p => p(_ => r => r))(p))))((l => r => f => f(l)(r))(_ => _)(_ => x => x))))(m))(e)(f => x => f(x)))

	)
);

不過,還有另一個方式可以完全用箭號函式表示,然後可讀性稍微高一些…