可以不要 let 嗎?

December 15, 2021

在〈真的未定義?〉中,已經可以將 map(list(elems($1)($2)($3)))(elem => sub(elem)($1)) 全部替換,完全使用箭號函式表示,這是這一系列文件想要達成的目標,不過,替換過程其實很無趣,替換的結果也如同密宗文字般難解。

IIFE

為了便於理解,在之前的文件中,都會借助 JavaScript 語法提供的 let,給予匿名函式一個名稱,從 lambda 演算的角度來看,像是放寬了限制,然而,也可以用另一個角度來看 let,將之當成是語法蜜糖。例如,如果有個程式是這麼撰寫:

let addOne = n => n + 1;
console.log(addOne(1));

可以將之視為底下程式的語法糖:

console.log(
	(addOne => 
		addOne(1)
	)(n => n + 1)
);

若是 let 宣告了兩個以上的名稱:

let addOne = n => n + 1;
let addTwo = n => addOne(addOne(n));
console.log(addTwo(1));

可以轉換為底下而得到相同的結果:

console.log(
	(addOne => 
		(addTwo =>
			addTwo(1)
		)(n => addOne(addOne(n)))
	)(n => n + 1)
);

結合 Y Combinator

那麼遞迴呢?例如:

let fact = n => n < 2 ? 1 : n * fact(n - 1);
console.log(fact(5));

你不能直接這麼撰寫:

console.log(
	(fact =>
		fact(5)
	)(n => n < 2 ? 1 : n * fact(n - 1));
);

n => n < 2 ? 1 : n * fact(n - 1) 來說,其中的 fact 在變數作用範圍中不存在,為了能解決這個問題,需要〈Y Combinator〉:

console.log(
	(y =>
		(fact =>
			fact(5)
		)(y(fact =>n => n < 2 ? 1 : n * fact(n - 1)))
	)(f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))
);

對 lambda 演算來說,實際上換行為縮排是不需要的,然而,這有助於閱讀,若想知道某個參數對應的函式是什麼,只要對照下側同一層的定義就可以了,當然,缺點就是巢狀的深度,let越多的名稱,巢狀就越深,不過,相對於完全展開的寫法,可讀性還是算好一些…XD

縮排地獄

可以試著將〈真的未定義?〉中最後使用 let 的版本改為底下,為了不要縮排地太誇張,縮排時只用了一個空白:

console.log(array(

 (y =>
  (unit =>
   (no_use =>
    (yes => 
     (no => 
      (when =>
       (not =>
        (pair =>
         (left => 
          (right =>
           (nil => 
            (con =>
             (head =>
              (tail =>
               (is_nil =>
                (isEmpty =>
                 ($0 => 
                  ($1 => 
                   ($2 =>
                    ($3 =>
                     (is_$0 => 
                      ($$ => 
                       (is_$$ =>
                        (succ => 
                         (add =>
                          (pair_succ =>
                           (prev => 
                            (sub => 
                             (len => 
                              (sum => 
                               (rcon => 
                                (rev => 
                                 (reverse =>
                                  (elems =>
                                   (list =>
                                    (map =>
                                    
                                     map(list(elems($1)($2)($3)))(elem => sub(elem)($1))
                                     
                                    )(y(map => l => f => when(isEmpty(l))(_ => nil)(_ => con(f(head(l)))(map(tail(l))(f)))))
                                   )(es => reverse(es($$)))
                                  )(rcon(nil))
                                 )(l => rev(nil)(l))
                                )(y(rev => r => l => when(isEmpty(l))(_ => r)(_ => rev(con(head(l))(r))(tail(l)))))
                               )(y(rcon => t => h => when(is_$$(h))(_ => t)(_ => rcon(con(h)(t)))))
                              )(y(sum => l => when(isEmpty(l))(_ => $0)(_ => add(head(l))(sum(tail(l))))))
                             )(y(len => l => when(isEmpty(l))(_ => $0)(_ => add($1)(len(tail(l))))))
                            )(m => n => n(prev)(m))
                           )(n => left(n(pair_succ)(pair($0)($0))))
                          )(p => pair(right(p))(succ(right(p))))
                         )(m => n => n(succ)(m))
                        )(n => f => x => f(n(f)(x)))
                       )(n => n(_ => no)(no))
                      )(_ => _ => yes)
                     )(n => n(_ => no)(yes))
                    )(f => x => f(f(f(x))))
                   )(f => x => f(f(x)))
                  )(f => x => f(x))
                 )(_ => x => x)
                )(is_nil)
               )(l => l(_ => _ => no))
              )(right)
             )(left)
            )(h => t => pair(h)(t))
           )(_ => yes)
          )(p => p(_ => r => r))
         )(p => p(l => _ => l))
        )(l => r => f => f(l)(r))
       )(b => b(_ => no)(_ => yes))
      )(unit)
     )(_ => f => f(no_use))
    )(f => _ => f(no_use))
   )(unit) 
  )(_ => _) 
 )(f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n))))

));

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

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

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

	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;

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