等價匿名函式?

December 15, 2021

有一件事必須得承認,就如同 Y Combinator 從來不肯面對 x 從何而來這個問題,這一系列的文件也從來不面對 undefined 這個問題。

從〈未定義是值嗎?〉到〈真的未定義?〉,不是已經解決 undefined 了嗎?不!並沒有,只是沒有使用 undefined 而已,就算是 no_use,那也不是 undefined 的匿名函式定義,只是函式中不會去理 no_use 而已。

匿名函式是否等價?

到底有沒有辦法使用匿名函式來定義 undefined 呢?如果針對特定需求,將 undefined 可適用的場合加以限制,應該是可以,不過,如果想要定義一個通用的匿名函式 s 來表示 undefined,這就得面對一個問題,勢必要有個通用的 eq(x)(s),能夠決定 xs 這兩個匿名函式是否等價。

也許有人會說,x === s 不行嗎?不行!=== 是 JavaScript 的東西,而且它比較的其實是 xs 的記憶體位址,不是比較匿名函式是否等價,而且,如果函式物件不是全域的存在,單純像是 (x => x) === (x => x) 的結果會是 false,實際上兩者是等價的。

試著呼叫匿名函式,看看它們是不是傳回相同的值呢?唔!因為是 eq 必須是通用的,你沒辦法預期會傳入什麼匿名函式,也就無法確定呼叫匿名函式時該傳入什麼引數,而且別忘了,值全部都使用匿名函式編碼了,傳回值也會是匿名函式,問題回到原點,如何確認傳回的兩個匿名函式等價?

也許野心先別太大,來看看數字是怎麼比較相等性好了,在〈算術的編碼〉中看過 is_$0

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

實際上它沒有直接比較 $0$0,只是呼叫傳入的值,看看傳回 yesno,那麼可以比較兩個數字是否相等嗎?來試試看:

let naturalEq = m => n => when(is_$0(sub(m)(n)))
                                (_ => is_$0(sub(n)(m)))
                                (_ => no)(no_use);

如果兩個數字相等,那麼相減結果必然是 $0,目前僅定義自然數,相減結果最小是 $0,因而除了 m 減去 n 必須為 $0 之外,也要檢查 n 減去 m 要是為 $0

naturalEq 可以比較任意兩個數字並傳回 yesno,最終是透過 is_$0 來確認等價性,在對匿名函式加以限制的情況下(例如限制在數字),這類的等價性確認是可以達成的,naturalEq 不是通用的 eq,不過可以解決數字等價的問題。

那麼,若參數與傳回值是數字的函式,基於數字來確定函式的等價性是有可能的了,例如:

let f = n => $1;
let g = n => $1;

可以判定 fg 等價,因為對任意的數字 n,執行後一定傳回 $1,令 fg 更複雜一些的話呢?

let x = (某個數字);
let f = n => $1;
let g = n => when(naturalEq(x)(n))
                    (_ => $1)
                    (_ => f(n))(no_use);

可以判定 fg 等價,因為對任意的數字 n,執行後一定傳回 $1,如果是底下的 fg 呢?

let some = (某個箭號函式);
let x = (某個數字);
let f = n => (_ => $1)(some(x));
let g = n => when(naturalEq(x)(n))
                    (_ => $1)
                    (_ => f(n))(no_use);

不管 some 是什麼,some(n) 執行完畢之後,當成是引數傳入,引數會被忽略直接傳回 $1,沒問題,fg 可以判定為等價。

等一下!some(n) 一定會執行完畢嗎?如果 somey(some => x => some(x)) 呢?那會發生無限遞迴,如果真有個通用的 eq 存在,可以在 eq(f)(g) 時列舉 n,用以判定 fg 的等價性,既然是通用的 eq,那表示也可以用 eq(x)(n) 來取代 naturalEq(x)(n),而且 eq 可以在發現無限遞迴時,直接傳回 no(因為無限遞迴時一定不會傳回 $1),而 some(x) 可以執行完畢的情況下,結果就是 yes(因為 fg 等價)。

停還是不停?

也就是說,eq(f)(g) 等於是在判斷 some(x) 可否執行完畢,那就來寫個 is_halt 函式:

let is_halt = some => x => 
    (f => 
        (g =>
            
            eq(f)(g)

        )(n => when(eq(x)(n))(_ => $1)(_ => f(n))(no_use))
    )(n => (_ => $1)(some(x)));

這個 is_halt,可以接受任意函式 somex,如果 some(x) 可執行完畢就傳回 yes,不然就是 no

如果有個函式 f,可以接受自身作為輸入,像是 Y Combinator 中 x[x] 的情況,因而關心的是 f(f) 能不能執行完畢,若可以執行完畢的話,希望可以進入另一個永不停止的流程:

let forever = y(f => x => f(x));
let foreverIfHalt = f => when(is_halt(f)(f))
                                (_ => forever($0))
                                (_ => $0)(no_use);

這需求在直覺上或許會認為不奇怪且可能(若指定 f 回呼會執行完畢,那就執行另一個預設的、不會停止的函式),如果被指定的回呼函式就是 foreverIfHalt 呢?

foreverIfHalt(foreverIfHalt);

如果上式能執行完畢,表示 is_halt(foreverIfHalt)(foreverIfHalt) 必須是 no,也就是表示 someforeverIfHalt,而 x 也是 foreverIfHalt 時,eq(f)(g) 的行為會是「some(x) 可以執行完畢的情況下,傳回 no」,可是剛才說「some(x) 可以執行完畢的情況下,結果就是 yes」。

如果上式不能執行完畢,表示 is_halt(foreverIfHalt)(foreverIfHalt) 必須是 yes,也就是表示 someforeverIfHalt,而 x 也是 foreverIfHalt 時,eq(f)(g) 的行為會是「some(x) 不能執行完畢的情況下,傳回 yes」,可是剛才說「eq 可以在發現無限遞迴時,直接傳回 no」。

之前說應該 yes 的情況,現在卻變成 no,之前說應該 no 的情況,現在卻變成 yes,這是政治上流行的髮夾彎嗎?這樣的政治人物…嗯…咳…這樣的 eq 根本就不該存在!

也就是說,可以判斷任意兩個匿名函式是否等價的運算不存在!