プログラミング：無より少ないものでプログラミングする

• この記事は、面接の場面で応募者が単純な FizzBuzz 問題をラムダ計算ベースの純粋関数コンビネータで実装しようとする、風刺的な物語を描いている
• 主人公は JavaScript から始めるが、次第に S, K, I コンビネータを定義しながら、言語の基本構造を自ら再構築していく
• 続いて ブール値、数、リスト、文字列をすべてコンビネータだけで表現し、Y コンビネータによって再帰を実装する
• 最終的に FizzBuzz を完全な ポイントフリー(point-free) スタイルで完成させるが、コードは人間が理解できないレベルにまで膨れ上がる
• この記事は、プログラミング言語の本質と抽象化の極限をユーモラスに探求し、開発者文化の自己風刺をあらわにする

---

面接の始まり：FizzBuzz とコンビネータ

• 物語の始まりは、面接官 Dana が応募者に FizzBuzz 問題を解いてみるよう求める場面から始まる
  • 応募者は一般的なループ文の代わりに S と K コンビネータを定義しながら問題を解き始める
  • Dana はいぶかしむが、応募者は「もう少しでできます」と言って続ける
• 応募者は I, B, C, W, T などさまざまなコンビネータを定義し、それらを新しい言語の基本構成要素として使う
  • 各コンビネータは、関数合成、引数の入れ替え、自己適用など、ラムダ計算の中核概念を実装する
  • コードコメントには “Bluebird, Cardinal, Warbler, Thrush” など、コンビネータ名の別名も登場する

ブール値と数の定義

• 応募者は TRUE, FALSE, NOT をコンビネータだけで定義し、ブール論理を構築する
  • Dana は「ラムダ計算なのか」と尋ねるが、応募者は「ラムダ計算は大げさすぎる」と答える
• 続いて ZERO, SUCC, PRED, IS_ZERO などを定義し、数体系(Church numeral) を構成する
  • SUCC は後者、PRED は前者、DECREMENT は 0 未満に下がらない減算演算を実装する
  • ONE から TEN までの数を順に定義する

再帰と Y コンビネータ

• 応募者は ADD 関数を定義し、徐々に ポイントフリー(point-free) 形式へと変換していく
  • ADD_MAKER を定義し、それを Y コンビネータで包んで再帰を可能にする
  • Dana は「JavaScript でも再帰はできる」と指摘するが、応募者は「もうすぐ JavaScript ではなくなる」と答える
• JavaScript の 正格評価(eager evaluation) によってスタックオーバーフローが発生すると、応募者は Skoobert という「遅延評価(lazy)」の JS インタプリタでコードを実行する
  • 結果は無事に 3 を出力する

算術、リスト、そして文字列

• 応募者は SUBTRACT, MULTIPLY, MOD, DIVIDE などの算術演算をすべてコンビネータベースで実装する
  • 各演算は IS_ZERO, PRED, SUCC などを再帰的に組み合わせて構成される
• 続いて CONS, FIRST, REST, EMPTY を定義し、リスト構造を構築する
  • MAP, FOLD, RANGE, CONCAT などの高階関数的演算もすべてコンビネータの形で実装する
• リストを文字列として出力するために renderList, showLines 関数を作成する
  • Dana はすでに諦めたようで、反応しなくなる

文字と文字列の構成

• 応募者は 文字コードを 1 から 9、さらに 10 単位でコンビネータを使って定義する
  • CHAR_A から CHAR_Z, CHAR_0 から CHAR_9 までをすべて数コンビネータの組み合わせで表現する
• ARRAY 関数を通じて文字列をリストに変換し、FIZZ, BUZZ, FIZZBUZZ を生成する
  • extractString 関数を通じてリストを実際の文字列に変換する
  • コンソール出力結果は "fizzbuzz"

数値から文字列への変換

• 数値を桁のリストに変える NUMBER_TO_DIGIT_LIST と、それを文字列に変える NUMBER_TO_STRING を定義する
  • DIVIDE, MOD, TEN などを使って各桁を分離する
  • DIGITS_NUMERAL リストを通じて数字文字へのマッピングを行う
• この過程によって、数値 → 文字 → 文字列 の変換が完全なコンビネータ体系の中で可能になる

FizzBuzz の完成

• FIFTEEN, ONE_HUNDRED を定義し、MAP と RANGE を使って 1 から 100 までのリストを生成する
  • 各数について 3、5、15 の倍数を判定し、"Fizz", "Buzz", "FizzBuzz" または数値文字列を出力する
  • showLines(extractString)(FIZZBUZZ_RESULT) で最終結果を出力する
• Dana は「これで満足か」と尋ねるが、応募者は すべての変数定義を取り除き、純粋なコンビネータだけでコードを書き直す
  • 結果は数千行に及ぶ、S と K だけで構成された巨大な式になる

結末と意味

• この記事は、プログラミング言語の根本的な構成要素を探求すると同時に、開発者が単純な問題を過剰に複雑化してしまう傾向を風刺している
  • 「無より少ないものでプログラミングする」という題名は、言語の最小単位から世界を再構成しようとする試みを象徴している
• この作品は、関数型プログラミング、ラムダ計算、コンビネータ論理への深い理解を、ユーモアと物語で描いた技術文学である
  • 同時に、「FizzBuzz すら哲学的実験に変えてしまう開発者精神」を風刺的に示している

[GN⁺]

Hacker Newsの意見

• みんな「これはいったい何なんだ？」という感じになっているようなので、combinator の要点を説明してみる
  combinator とは、グローバル状態を変更せず、外部変数をキャプチャしない関数のこと。同じ引数を与えれば常に同じ結果を返し、システムの他の部分には何の影響も与えない
  こうした純粋関数を組み合わせると、別の combinator が作られる。つまり、純粋関数の合成はやはり純粋関数だということ
  こうした関数はアセンブリや C でも簡単に書ける。たとえば x64 で S と K を直接実装し、その上で combinator ベースで Common Lisp をコンパイルすれば、結局 2 つのアセンブリ関数の上で Lisp が動くことになる
  性能はあまり良くないだろうが、数百個ほどのよく使うパターンを インライン combinator として作って名前を付ければ、かなり実用的な「機械」になる
  この構造は、mutation を恐れる Forth や、bytecode VM、あるいは combinator を「命令」と呼ぶ CPU にも似ている
  結局のところ combinator は、実装の詳細をできる限り無視した 応用計算機科学の表現 と言える。だからラムダ計算より単純だとも言える
  もしラムダ計算をいくつかの combinator で実装し、その上に Lisp を載せるなら、スタックの最下層で必要になる機械依存の作業は極端に減る

  • どこかで関数の 1 つが自分自身を呼び出して seed round を受け取ったような気がする
  • 学生のころに似たようなことをやったことがあるが（Lisp ではなく、ラムダ計算へマクロ展開される単純な言語だった）、S と K だけですべて実装できるというのは本当に 衝撃的 だった。ただ同時に、どれほど非効率かにも驚かされた。とはいえ、命令セットが大きくなるほど状況はずっと良くなる
  • 理論上は全部可能だが、実際にはグラフ書き換えよりずっと 実用的な計算基盤 を選ぶべきだ。計算可能性の限界を実験したいのでなければ、これはほとんどパーティートリックの域だ。しかも数の表現も問題になる。少なくとも 2 の補数整数と効率的なデストラクタを使ってこそ感心できる
  • こういう形で combinator の上に実装された Lisp が実在するのか気になる。あるなら移植してみるのはかなり面白そう

• let A = (x) => (y) => (z) => x(z)(y((w) => z))
  

  これを何回か組み合わせるだけでよい

  let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A);
  let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)((A(A)))))))(A)(A);
  

  「ラムダ計算なんて絶対に使わない。あんなものは 肥大化した言語 だ」
  だが実際には combinatory logic のほうがもっと肥大化している。同じプログラムを表現するのに、より多くのビットが必要になる
  ラムダ計算はむしろ最も 簡潔な言語 の 1 つだ
  JavaScript のような eager な言語でも、引数をダミーのラムダで包めば lazy にできる。例は この JS BLC インタプリタ を参照
  関連論文は この PDF と IOCCC の例 を参照

  • 興味深いのは、最速クラスのラムダ計算インタプリタ（たとえば uni.c）が、結局はラムダ式を combinatory logic に変換して計算している点だ。ただし S、K より大きい基本集合を使っている
  • 「bloated language」とは不要な機能が多い言語を指す。たとえば C++ は C よりコードが短くなることがあっても、はるかに 複雑な言語 だ
  • あのコードブロックを見ていると、口から出る音がほとんど引数リストと一致してくる
  • K と S の定義には括弧の誤りがあるようだ。修正版は次のとおり

    let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A));
    let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)(A(A)))))))(A)(A);
    

    そして eager な言語を lazy にするには、こんなふうにできる

    let A = x => y => z => () => x()(z())(y()(w => z()));
    

  • 「w って何？」という疑問が湧く

• 「FizzBuzz は知ってる？」
  「もちろん。10 文字のコードゴルフ版、ジュニアでも理解できる 12 行版、それとも 奇怪な知識自慢用 の完全にぶっ飛んだ版？」

  • これを見て C64 BASIC で 最速の FizzBuzz を実装してみた。朝の時間を楽しく無駄にできた
    結果リンク

• combinator logic の説明が本当に見事だった。文体は このシリーズ を思い出させる

  • 説明というより 見せるためのパフォーマンス に近い。それでもかなり印象的だった
  • たしかにあのシリーズから着想を得た感じがある。著者名に触れていたらもっと良かったかもしれない
  • イギリスでは Online Safety Act のせいでアクセスが遮断されていて残念だ

• 以前読んだ「FizzBuzz in TensorFlow」という記事を思い出した
  リンク

  • 今回の記事はまだ追いかけられたので良かった

• こういう プログラミング面接の枠組み は少しおかしい気がする
  面接の目的は、(1) 応募者のプログラミング知識を確認すること、(2) 会社の プログラミング文化との適合性 を見ることだ
  たとえば JavaScript のポジションを採るのに combinatory logic に深くのめり込んでいるなら、文化的に合わない可能性が高い。だから不採用でも不思議ではない

  • おそらく このシリーズ を参照しているのだろう。ただし原文では明示されていない
  • ときどき HN のコメント欄には 楽しむことを忘れた人たち がいるように感じる
  • プログラミングの多様性を強調したのは確かだが、それも特定のエコシステムの専門性を選ぶ 1 つの形にすぎない。多くは レガシーコード や既存エコシステム活用のための選択だ
  • 「IQ が低ければ不採用」みたいな話は笑えるが、結局お金さえ十分に積めば、どんな OOP/FP/FRP スタイル にでも合わせられる
  • 現実には、こういう理想的な面接はほとんどない。大半は フラストレーションを抱えた面接官 が自分の世界観を押し付けている。実際の仕事は面接内容とほとんど無関係だ

• Moses Schönfinkel を思い出すべきときだ
  彼は 1920 年、Hilbert の弟子だった時代に combinatory logic を発明した。ロシアに戻った後は精神疾患を患い、貧困のなかモスクワで亡くなった。Wikipedia によれば、彼の論文は近所の人たちに暖房用として燃やされてしまったという

• 最後のコードブロックはスクロールが出るほど大きい（166KB）
  S と K は カリー化された関数 で、一度に 1 つの引数しか取らない
  詳しくは この StackOverflow の回答 を参照

  • スクロールしていくと シンタックスハイライトが諦める瞬間 がいちばん面白かった

• 「Bluebird、cardinal、warbler、thrush」みたいな鳥の名前がすごく気に入った。新しい 命名規則 にしたいくらいだ
  「Barendregt。Church はメジャーすぎるからね」
  「そのうち JavaScript ですらなくなる」
  Douglas Adams が SICP を教えている感じだ

  • 鳥の名前は Smullyan の『To Mock a Mockingbird』から来ている。そこにはもっとたくさんの鳥が出てくる

• 「それって……Y combinator？」
  「そう。再帰するには必要だからね」
  面白いことに、不動点コンビネータ（fixed-point combinator） は無限に存在する。つまり、Y combinator がなくても無限に多くのやり方で再帰を実装できる