配列言語として考える

 (github.com/razetime)
2 ポイント 投稿者 GN⁺ 2024-01-15 | 1件のコメント | WhatsAppで共有
  • Kプログラミングでは、REPLで試したコードをスクリプトに移しながら、大きな命令型パターンをより小さな宣言的な配列パターンへと縮小し続けることに重点が置かれる
  • ngn/k スクリプトは REPL 入力のように行単位で実行され、\l file.k によって保存済みのデータや関数を REPL にロードできる
  • Wikipedia式の3重ループによる行列積をそのまま移植すると、グローバル変数・ネストしたループ・変更が多くなり、Kの長所に反する
  • 改善の過程では +/ fold、' each、/: eachright、\: eachleft、転置の除去、tacit 変換を経て、matmul: {x{+/x*y}\:y} から matmul: (+/*)\: へと凝縮される
  • 行列積の例は、Kの習熟とはコードを凝縮する過程を繰り返し、複雑な手続きをより読みやすい配列表現へ置き換えることにあると示している

REPL中心のK開発フロー

  • 完全なソースコードは GitHub の matmul.k で見られる
  • Kプログラミングの大半は REPL 上で行われ、既存コードの上で素早く実験し改善するのに向いている
  • ngn/k と rlfe の組み合わせは上下矢印のヒストリをサポートしており、より大きなKプログラムの開発にも十分対応できる
  • 関数はまず REPL でテストし、その後に実際のコードへ移す流れが自然である
  • ngn/k の prettyprinting は常に有効なKデータを返すため、一部の値を事前計算してプログラムを高速化できる

Kスクリプトの実行モデル

  • Kスクリプトは REPL に入力したものと同じように実行される
    • 各行が順番に実行される
    • 行がセミコロンで終わっていなければ戻り値が出力される
  • スクリプトでは 複数行定義 が許され、可読性を高められる
  • 保存されたデータや関数を REPL で使うには \l file.k を実行する
    • ファイルが実行される
    • ファイル内のデータがロードされる
    • 同じファイルを複数回ロードすると以前のデータは上書きされる
  • \ で利用できる REPL ヘルプから、さらに多くのコマンドを確認できる

配列言語でパターンを縮小する方法

  • Kと配列プログラミングは、パターンを継続的に単純化していく過程である
  • 大きく扱いづらいパターンでも、より小さく宣言的で読みやすい形に縮小する方法が1つ以上ある
  • 関連する議論は Patterns and Anti-patterns in APL: Escaping the Beginner's Plateau - Aaron Hsu - Dyalog '17 で詳しく見られる
  • よくある出発点は、GeeksforGeeks や Wikipedia のよく知られたアルゴリズムを K に翻訳しようとする場面である
  • 例として 行列積 を用いる

命令型の行列積をそのまま移した場合

  • Wikipedia の Matrix multiplication algorithm では、i、j、k の3重ループと sum の累積で行列 C を埋めていく
  • これを K に直接翻訳すると、A、B、n、m、p、C、i、j、k、sum のようなグローバル値を大量に割り当てることになる
  • このコードは K を命令型言語のように使う書き方であり、Kの設計思想とはあまり合わない
  • 問題は次の3点に絞られる
    • グローバル代入 が多い
    • 多段のネストしたループが残る
    • 変更が頻繁に発生する

内側のループから畳み込んで縮小する

  • 最も内側のループでは、sum を 0 に初期化し、k を回しながら A[i;k]*B[k;j] を累積する
  • 最初の改善は、fold である / を使って合計を +/ に置き換えることだ
    • sum のグローバルが消える
    • C[i;j]::+/... という形に整理される
  • 続いて ' each が配列を返すことを使えば、C を変更せず、ネストしたループの戻り値をそのまま使える
  • この段階では、変更のない3つのループだけが残り、中心となる変数は i、j、k になる

k、j、i を消していく過程

  • 3つの変数の役割は次の通り
    • i は A の各行をインデックスする
    • j は B の各列をインデックスする
    • k は A の各列と B の各行をインデックスする
  • k は A の各行と B の各列を組にして掛け合わせる役割なので、中間インデックスをなくして直接対応付けできる
    • この段階でループ1つと m が不要になる
  • j を取り除くには、B の各列を取り出して A[i] と組にする必要がある
    • B を転置し、eachright /: で各要素を組み合わせる
  • i も同じ方法で取り除ける
    • eachleft \: を使って A の各行と B の各列を組み合わせる
  • この過程を経ると、グローバルなしで次の形になる
matmul: {x{+/x*y}/:\:+y}

転置の除去と最終的な tacit 形式

  • + による転置はコストが高いため、除去できる
  • 従来の方法は、x の各行と y の各列を掛ける素朴な方法である
  • 代わりに、B の各行を A 全体に適用すれば、同じ処理を暗黙的に実行できる
matmul: {x{+/x*y}\:y}
  • この関数は Chapter 3 の規則を適用して tacit 形式に変換できる
  • 最終結果は次の通り
matmul: (+/*)\:

練習によって身につく配列言語の直感

  • matmul: (+/*)\: は Kらしい行列積関数として整理されている
  • 凝縮の過程は、最初は手順が多く見えるかもしれない
  • Kを練習するほど、コードの凝縮はより容易で直感的な作業へと変わっていく
  • 行列積は K の配列サポートと相性の良い単純な手続きである
  • 以後の章では、K と相性の悪いアルゴリズムと、その扱い方を取り上げる予定である

関連記事

1件のコメント

 
GN⁺ 2024-01-15
Hacker News のコメント

  • 実際に配列言語の可能性を最も説得力をもって示していたのは、Aaron Hsu が 並列 APL コンパイラ Co-dfns を開発する様子を説明した動画だった: https://www.youtube.com/watch?v=gcUWTa16Jc0&t=860s
    彼は HN で arcfide という名前で 意味密度 についても何度か書いており、APL のコードは、動作の仕方、周辺の文脈、依存関係を、ほとんど移動せずに1つの画面内で見られるように設計するものだと説明している: https://news.ycombinator.com/item?id=13571159
    アルゴリズム名がアルゴリズムそのものを展開して書いた長さと同じくらいになるほど簡潔になれば、英語の句を読むようにイディオム単位でコードを読むようになり、再利用可能な抽象化を作るよりも、画面に見えているすべての使用箇所を直接変更するほうが速い場合がある、という見方

    • 有限のコンテキストウィンドウを持つ LLM が、他の言語よりも APL をうまく扱えるのかも気になる
    • ああいう長い説明を書かなければならないのは、コードの見た目がひどいからだと思う。記号同士がくっついたときにもう少し見苦しく見えないものを選んでいれば、その言語が駄目ではないと人々を説得するのに 18時間 も費やさなくて済んだのではないか

  • 配列プログラミングに詳しくないなら、入門資料として The Array Cast を勧める: https://www.arraycast.com/episodes/
    RSS の URL は https://www.arraycast.com/episodes?format=rss

    • 納得しようと思って The Array Cast の最初の5話ほどを聞いたが、結局納得できなかった。司会者たちは、配列言語の 短い記法 や非 ASCII 記号は慣れれば問題なく、利点があるので受け入れる価値があると言っていたが、その利点の大半は、今の主流言語の高階関数ですでにおなじみのものだった
      map/filter/reduce はすでにほとんどどこにでもあり、表語文字のような記法体系を新たに学ばなくても使える、という点を見落としているように感じた
    • これを通じて BQN を知ったが、実際の本番環境で使うかはまだ分からない。好きではあるものの、R、NumPy、Julia あたりでなければ、ほとんどの配列言語はなじみが薄いし、APL、J、BQN に深く入り込むと、後で助けを求められる人たちから自分で距離を置くことになりそうだ

  • 70年代に紙端末で実際に重ね打ちを使っていた APL/APL2 に触れてすぐ夢中になったが、その後 ML と Haskell で関数型プログラミングを知ってから、自分が APL で本当に好きだったのは配列よりも 関数合成 の能力だったのだと気づいた
    Haskell は完全に純粋で、型が全体に適用されるため、この点でははるかに優れており、APL よりも楽しく強力だった。小規模・中規模のプロジェクトをたくさん作り、LLVM Flang のパーサを parser combinator で実装できることを示すプロトタイプも作ったし、毎年 Advent of Code も全体で数百行程度で解いている。APL が好きなら Haskell も試してみる価値がある
    今では、APL の「思考の道具としての記法」という側面は、過度な簡潔さを正当化する言葉のように見える。合成の力を示すにはよいが、明確さを損なうこともある

    • この話題ではずっと同じことを言ってしまうが、point-free Haskell をある程度うまく使えるようになってから、J と K はほとんど触らなくなった。ファンクタまで混ぜると動詞列車よりも強力になり、<=< はすでにあるし、fmap に相当するものを使えば本当にうまく回る
      |||、+++、&&&、*** も良いし、UTF-8 演算子を自分で作って、もっと短くきれいにすることもできる。ただし実際の仕事や公開されている本格的な Haskell コードは、このように縦方向の画面スペースに優しいことが少ないのが残念
    • Advent of Code のソースリンクを見られるとありがたい

  • 配列言語で「Nより小さい数のうち述語Pが真になるすべての数を見つける」のような問題を、一般にはどう扱うのか気になっている。たとえば1000未満の素数を見つける、あるいは z が1,000,000未満のピタゴラス数の三つ組を見つける、といった形だ。
    命令型言語ならループで述語を検査し、関数型言語なら再帰や遅延リストに map/filter を使うだろうが、配列言語では普通 1..N の配列を作り、述語を適用してマスク配列を作ったうえで、そのマスクで元の配列を絞り込む、というふうに理解している。
    N が10億のように大きく、述語がほとんど真にならないなら、1..N 配列とマスクという巨大な一時配列を2つ作るのは、メモリとリソースの面で非常に無駄に見える。配列言語はこうした一時配列を作り続けて遅くなるのか、それとも実装が遅延評価のような方式で最適化するのか気になる。

    • その通りで、メモリを大量に無駄にする。ただしメモリは安いし、必要なら計算をブロック単位に分けられる。実際にメモリが尽きることはまれだが、より低いキャッシュ階層にとどまるためにブロッキングは有用だ。
      スカラー言語は逆に、1回に1つの値を処理するのが基本なので、配列言語が SIMD アルゴリズムとして活用する潜在的な並列性を無駄にしている。これも現状に慣れているため大きな問題に見えにくいだけで、解決策はやはりブロッキングだ。
      実際に配列言語が良いかどうかは問題による。大多数の実用的な用途では性能はまったく重要ではなく、k の評判も、k の実装自体が速い言語だからというより、kdb がデータベースとして速いことに由来しているように思う。それでも、マシンごとの細かな最適化よりも優雅な配列アルゴリズムに集中するだけで、驚くほど速くなり得る: https://mlochbaum.github.io/BQN/implementation/versusc.html
    • 回避策はいくつかある。遅延評価もその1つで、Kap はこれを使っている: https://aplwiki.com/wiki/KAP
      もう1つの明確な方法は、本体全体をループ融合して一時配列が生じないようにすることだ。より単純な選択肢は、入力・出力配列を数十KB程度のチャンクに分けて不要な一時メモリ使用量を抑える方法だが、知る限りこれを自動で行う配列言語はなく、いつか CBQN で試してみたい。ユーザーが手動で行うこともでき、性能を最大化するには実際によく必要になる。
    • 直感はおおむね正しいが、実戦ではまれな問題だ。k 系、たとえば ngn/k には、!10000000 のように0から1000万までの iota を、実際に1000万個の整数配列として作らず、単純な範囲として扱う遅延構造がある。
      もちろん、どの演算子を使うかによっては最終的にそうした配列が生じることもある。また +|x のように、x を反転して最初の要素を取るパターンを、単に最後の要素を取る処理に置き換える最適化もある。
    • 配列生成が文字通り起きると考えているように見える。配列言語が内部的にチャンク単位で処理できない理由はない。100億個の整数配列を要求しても、素朴にそのまま作らないことはあり得る。
    • 多くの配列言語には実際にこの問題がある。正確には、単純で直感的なやり方が、必要以上にはるかに多く計算してしまいがちなのが問題だ。
      もちろん別の書き方をして避けることはできるが、そうした解法はより長く、あまり美しくなくなり得る。私が取り組んでいる APL 方言 Kap は、結果が必要になるまで計算を遅らせ、直感的な書き方のまま、捨てられる結果を計算しないようにする多くのケースを扱う。

  • 配列言語、特に k を使って最も大きく気づいた点は次の通り。動詞はアルゴリズムであり、命令型・オブジェクト指向言語では find、sort、group のような共通アルゴリズムを自分で実装しなければならないことが多い。
    動詞や副詞の連なりは、私が使った中で最も直接的な合成の形で、合成が簡単で自然だ。プログラムは文や式の集まりではなく、アルゴリズムの合成として見えるようになる。
    配列、マップ、関数で定義域と値域の概念を一貫して扱うと設計上の選択が単純になり、右から左へ評価されると、コードを読むときに視線をあちこちに飛ばさずに済む。
    データをコードへ持ってくるのではなく、コードをデータへ送る方式が可能であり、好まれる。大きな k プロジェクトのほとんどは、コメントを除けばネットワーク MTU、つまり1540バイト以内に収まる。k のおまけとして、ビューは関数的関係を直接実装でき、インタプリタを介したホットコードローディングにより、「永遠に」動くアプリケーションも可能になる。

  • 就職面接の準備として K 言語の問題を解いてみた、個人的で偏った限られた印象では、この言語は意図的に難解だというものだった。パズルや賢い解法には向いている言語だ。
    ただし、配列言語と配列で考える方法を教えてくれるのは、Python で NumPy 配列を扱う経験だと思う。

    • どこの面接だったのか気になる。

  • J を50時間ほど使ってみた経験では、このパラダイムは正直かなり一方向に偏りすぎていると感じた。
    あらゆる問題を配列の入れ子として考えることが、思考の道具として役立つのか分からない。問題をうまく捉えるデータ構造を自由に作れるなら、アルゴリズム部分は大きく単純化できることがある。
    APL/J/K を使うには、より頭が良くなければならないと思う。より柔軟な言語ではすぐ可能なアプローチがしばしば不可能で、問題を変換しなければならず、その過程ではるかに多くの思考が必要になることがある。

  • この例は K ベースだが、別の配列言語として J もある: http://jsoftware.com
    J では dot =: +/ . *、P =: 2 3 4、Q =: 1 0 2、P dot Q のように書くと、P と Q の内積 10 を返す。

    • もともとの配列言語は APL で、内積は dot←+.× と書ける。ただし、展開した表記が適度に短い名前と同じくらい短いなら、あえて名前を付ける必要はなく、名前の周囲に空白まで入れなければならない場合もある。
    • Haskell よりこれにどんな利点があるのか、まだよく分からない。dot = (sum.) . zipWith (*)、p = [2, 3, 4]、q = [1, 0, 2]、p `dot` q のように書けばよい。
      私の目には、sum と zipWith に名前を使い、リフティングや構造変換が「魔法のように」起きない、という違いしかないように見える。
    • KlongPy で内積は dot::{+/x*y} と書く。P::[2 3 4]、Q::[1 0 2]、dot(P;Q) という形だ。

  • 例を見ると、これにどんな意味があるのか分からない。何らかの形で性能が良いのか？
    行列乗算の構文はより短いが、それは K 言語がどう動くかについて多くの組み込みの文脈を頭の中に持っていなければならないからに見える

    • より簡潔であること自体に価値がある。特に、数学がますます多くの概念をより高いレベルの定義へ圧縮していく過程だと考えると似ている。より高いレベルの概念がプリミティブになると、より速く考え、より複雑な対象を作れる
    • 性能が良くなることはあり得る。コンピュータは配列を走査する処理が非常に速く、特に SIMD を活用できるならそうだが、それがすべてではない
      配列言語を使ってみて、パラダイムが理解できるまでいじってみる価値はある。命令型コードが配列スタイルでよりうまく表現できる場合はよくあり、長く細かな関数が配列演算だけで、あるいは他のスタイルと併用することで大きく単純化されることもある
    • 冗長さにもコストがあり、本当に複雑な関数だけに冗長である特権があると信じるなら、その意味はすぐに分かる
      Haskell で (+) <$> Just 1 <*> Just 2 と do x <- Just 1; y <- Just 2; Just (x + y) を比べると、この程度の複雑さなら常に前者を好む。後者はより多くのスペースを取り、何かもっと複雑なことが起きているように感じられる
      より複雑な処理なら、後者の形を使うよりも、前者の変形が意味をなすように小さな関数へ分解したい。これは「一部の初心者がすばやく読める」を「初心者以上が読める」に変えるトレードオフだ
      「一部の初心者が読める」ことを最適化対象にすると収穫逓減が非常に大きいと考えており、代わりに「初心者以上」、場合によっては「中級者以上」が読めるようにすることを目標にしている

  • どんな言語にも、使う理由も使わない理由もたくさんある。しかし核心は、短い記法、相対的な明確さ、高速なコードへコンパイルできる能力ではなく、後から来たプログラマーがそのコードを実際の利用のために修正し、保守できるかどうかだ
    プログラマーはあまりにも頻繁に自分の leet スキルを見せたがり、その後にやって来てそのコードを引き受けなければならない哀れな人たちのことを考えない。現実には、多くの leet コードは長期的にサポート可能なものを得るために捨てられるか、完全に書き直されなければならない
    これを理解するのに時間がかかったが、その後は他の人が保守できるように、きれいで単純で理解しやすいコードを書くようにしてきた。捨てるつもりのコードが組織の基盤インフラとして固着し、次の世代にとって理解不能なものになることがあまりにも多い