ハクソク

世界を動かす技術を、日本語で。

何もないより少ないプログラミング

215日前原文(joshmoody.org)

概要

FizzBuzz の問題を、 ラムダ計算 や コンビネータ のみで解く奇抜な面接回答例。 JavaScript を使いながら、 S や K などの基本コンビネータから構築。 Church数 や リスト、 再帰 もすべて関数のみで表現。 面接官との 会話形式 で進行し、途中で Yコンビネータ や 遅延評価 の話題も登場。 最後は FizzBuzz の完全なラムダ式まで展開し、徹底的な抽象化を見せつける内容。

FizzBuzzをラムダ計算とコンビネータで解く

  • 面接官 Dana との会話形式で進行
  • FizzBuzz の説明を求められ、 JavaScript で記述開始
  • S、 K などの基本コンビネータを定義
    • 例：let S = (x) => (y) => (z) => x(z)(y(z));
  • I （恒等関数）、 B （合成）、 C （引数交換）、 W （自己適用）なども定義
  • TRUE / FALSE などのブール値を関数で表現
  • NOT、 IS_ZERO などの論理演算も関数のみで表現
  • Church数 の定義と、 SUCC （後者）、 PRED （前者）、 ADD （加算）などを実装
  • 再帰 実現のため、 Yコンビネータ を導入
    • JavaScriptの 正格評価 ではスタックオーバーフローになるため、 Skoobert という遅延評価環境に切り替え
  • extractNumber 関数でChurch数から通常の数値へ変換
  • SUBTRACT （減算）、 MULTIPLY （乗算）、 MOD （剰余）などの算術関数もすべて関数合成で記述
  • リスト構造 （CONS、FIRST、REST、EMPTY）や MAP、 FOLD、 RANGE なども関数で表現
  • Fizz や Buzz の文字列も、アルファベットを数値で表現し、リストとして構成
  • extractString でリストから文字列へ変換
  • 数値を各桁のリストに分解し、文字列化する関数も自作
  • 最後に FizzBuzz 判定ロジックを関数合成で実装
    • 3の倍数でFizz、5の倍数でBuzz、15の倍数でFizzBuzz、その他は数値を文字列化
  • 変数を一切使わず、すべて ラムダ式 の入れ子でFizzBuzzを実現

面接官とのやりとり・抽象化の極限

  • Dana は途中で「for文が見当たらない」と困惑
  • Church数 や Barendregt など、関数型プログラミングの用語が飛び交う
  • Yコンビネータ の使用に「JavaScriptなら普通に再帰できる」と指摘される
  • 文字列処理、数値変換もすべて関数で記述し、「抽象化の暴走」を体現
  • 最後はFizzBuzzのロジックを S や K のみの入れ子で完全展開
  • 面接官も「満足？」と問いかけるが、さらに変数を排除する徹底ぶり

まとめ・学び

  • FizzBuzz という単純な問題でも、 ラムダ計算 や コンビネータ のみで解くと極端に抽象的・複雑になる
  • 再帰 や リスト処理、 数値変換 もすべて関数だけで表現できることの証明
  • JavaScript の評価戦略の違い（正格／遅延）にも注意が必要
  • 「抽象化」「関数合成」「再帰」の極限を体験できる例
  • 実用性よりも 理論的な面白さ や 関数型プログラミングの奥深さ を味わえる内容

Hackerたちの意見

組合論理の説明がめっちゃ良かった！書き方がこの投稿シリーズを思い出させたよ（個人的にはいいことだと思う）: https://aphyr.com/posts/353-rewriting-the-technical-intervie...

└

明らかにあれからインスパイアされてるね。著者はクレジットを入れるべきだったと思う。

└

説明？あんまり説明がないよね。ほとんど見せびらかしだな。（それでもかなり印象的だけど。）

└

UKのオンライン安全法のせいで利用できないって、ため息。

最後のコードブロックはスクロールするよ。サイズは166 kB。SとKはカリー化された関数で、一度に一つの引数を取るからね。さらに読みたい人はこちら: https://stackoverflow.com/a/36321/

└

スクロールしてる時にシンタックスハイライトが諦めるのが、一番好きな部分だった。

let A = (x) => (y) => (z) => x(z)(y((w) => z)) これを何回か組み合わせるだけ。 let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A)); // (x) => (y) => x let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)((A(A)))))))(A)(A); // (x) => (y) => (z) => x(z)(y(z)) > 「ラムダ計算なんて絶対使わない。冗長な言語だ。」 実際、組合論理はラムダ計算よりも冗長で、同じプログラムを表現するのにもっとビットが必要なんだよね[1]。ラムダ計算は最も簡潔な言語の一つだって主張することもできるよ[2]。 > ダナがニヤリ。「そうだね。JavaScriptはイagerな言語だから、Yコンビネータは使えないよ。」 イagerな言語は、引数をダミー引数を使ったラムダでラップすることでレイジーにできるんだ。これはJavaScriptのBLCインタープリタでやってることだよ[3]。 [1] https://tromp.github.io/cl/LC.pdf [2] https://www.ioccc.org/2012/tromp/ [3] https://github.com/tromp/AIT/blob/master/uni.js#L56

└

let A = (x) => (y) => (z) => x(z)(y((w) => z)) wって何？

└

ただ、面白いのは、ラムダ計算のための最速のインタープリター（例えば、あなたのuni.c）は、項をコンビネーター論理に翻訳して（S,Kよりも大きなベースで）、それを使って計算することで動くってことだね。

構造は確かに異なるプログラミングモデルを考えるのが好きな人には面白いけど、プログラミングインタビューのストーリーの枠組みは「間違ってる」と思う。プログラミングインタビューは2つの目的があるんだ: 1. 候補者がプログラミングに詳しいかどうか？ 2. プログラミングスタイルが会社が求めるものに（ある程度）合っているか？ 1は明確で、著者はこの部分はクリアしてるね。2について: 特にプログラミングは多くの「文化」に分かれていて、その多くは表面的な知識を超えるために深い努力が必要だから（だから「Javaショップ」や「Microsoft/C#ショップ」とか言うんだよね）、プログラミングインタビューでは、候補者がその会社の主流のプログラミング文化に合うかどうかも見たいんだ。もしJavaScriptのポジションを募集してるなら、組合論理にそんなに深く入っている人がそのポジションに合う可能性は低いから、そういう解決策を持ってきたら、たぶん（良い理由で）拒否されるだろうね。

└

SKIで正しいプログラムをホワイトボードに書ける人がいたら、ぜひ雇いたいな。同じく、手で正しいフォースを書ける人もね。頭の中でかなり大きな計算グラフを持っていて、それをペンでシリアライズするのが全然遅くならないってことだよ。でも、残念ながら、俺にはどっちもできないんだ。やっぱり高レベルの世界に留まるしかない。悲しいな。

└

これはこのシリーズへの明確な言及だと思ってたけど、参考文献には載ってないね。 https://aphyr.com/posts/340-reversing-the-technical-intervie... でも、TFAは少なくとも半ページの説明があるから、十分だよね？ ;)

みんな「これ何？」って感じだから、コンビネーターについて説明するね。コンビネーターってのは、グローバルステートを変えず、変数にも閉じ込めない関数のこと。ソフトウェアの基本形だよ。同じ引数を渡せば、同じ結果が返ってくるし、システムの他の部分には何も影響しない。これらのコンビネーターを組み合わせると、また別のコンビネーターができるんだ。だって、純粋な関数を組み合わせると、出てくるのは純粋な関数だから。これらはアセンブリ言語でも書きやすい関数でもある。Cでもね。あんまり複雑なことはしないから。だから、x64でSとKを書いて、次に一般的なリスプをコンビネーターにコンパイルして、SとKで書かれたコンビネーターを使うと、実際にはその2つの手書きのアセンブリ関数で動くリスプができるわけ。パフォーマンス的にはあんまり良くないけど、数百のよく使われるパターンをインラインで組み合わせて名前を付ければ、機能的なプログラムをコンパイルするための実用的な「マシン」ができる。これは、変異を恐れるフォースみたいな感じだね。あるいはバイトコードVMとか、コンビネーターが「命令」と呼ばれるCPUみたいな。要するに、コンビネーターは実装の詳細をできるだけ無視した応用コンピュータサイエンスの表現なんだ。これがラムダ計算よりもシンプルな理由だよ。同様に、少数のコンビネーターでラムダ計算を実装して、その上でリスプを実装して、そのリスプで何かを書くと、スタックの底で必要なマシン特有の作業がかなり減るんだ。

└

どこかで、ある関数が自分を呼び出して資金調達をしてる。

何もないよりはマシにするために、このプログラミング言語を使うことをお勧めするよ： https://en.wikipedia.org/wiki/Whitespace_(programming_langua...

なんて馬鹿げた、不純なナンセンスなんだ。まだ「実行」と「出力」なんて使ってるのか、現実の汚い偶発的な効果を。どうして3つもコンビネーターを使う必要があるんだ？ιx = xSKって定義すればよかったのに。情けない。真の純粋なプログラムは決して実行する必要がない。存在するだけで証明になって、その存在によってユーザーの意識をその明らかなマニ教的な純粋さに合わせて再構成するんだ。「プログラム」を「実行」するなんて、何なんだ、野蛮人か？

「それって… Yコンビネータのこと？」とダナが聞く。 「それがないと再帰できないよ。」 面白いことに、固定点コンビネータは無限にあって、だからYコンビネータなしでも再帰する方法は無限にあるんだ。

残念ながら、NodeJSでは実行できない :( Uncaught RangeError: 最大コールスタックサイズを超えました at REPL2:1:16 at REPL1:1:30 at REPL1:1:34 at REPL1:1:30 at REPL1:1:30 at REPL1:1:30 at REPL1:1:35 at REPL1:1:34 at REPL1:1:34

ブルーバード、カーディナル、ウォーブラー、スラッシュ。君がよく知ってる鳥の友達だね。 それに、新しいお気に入りの命名規則があるんだ。 「バレンドレフト。教会はちょっとメインストリームすぎる。」 「もうすぐJavaScriptじゃなくなるよ。」 ダグラス・アダムスがSICPを教えてる。

└

[遅延]