配列言語で考える

 (github.com/razetime)
2 ポイント 投稿者 GN⁺ 2024-01-15 | 1件のコメント | WhatsAppで共有

K言語で考える

  • KプログラミングはほとんどがREPLを通じて行われる。
  • ngn/kのrlwrapは矢印キーで履歴をたどることができ、大きなプログラムの開発に役立つ。
  • 関数はREPLでテストした後、実際のコードへ移される。
  • ngn/kの整形された出力は常に有効なKデータを返し、プログラムの高速化のために事前計算できる。
  • KスクリプトはREPLに入力したかのように実行され、各行の返り値はセミコロンで終わらない限り出力される。
  • スクリプトは複数行の定義を許可し、可読性の向上に役立つ。
  • 作業をスクリプトに保存してREPLで使うには、\lfile.kを使ってファイルを実行し、データを読み込める。
  • REPLではファイルを何度も読み込み、以前のデータを上書きできる。
  • \でアクセスするREPLヘルプには、さまざまな便利なコマンドがある。

配列プログラミングの単純化

  • 配列プログラミングは、複雑なパターンをより小さく宣言的で読みやすいパターンへと単純化していく継続的な過程である。
  • 複雑なパターンを単純化する方法は、「APLにおけるパターンとアンチパターン: 初学者の高原を脱出する - Aaron Hsu - Dyalog '17」で詳しく論じられている。

行列積のKへの変換

  • Wikipediaの記事から持ってきた行列積の反復アルゴリズムは、Kへ直接変換できる。
  • Kへ変換した最悪のコード例では、多くのグローバル変数への代入、ネストしたループ、多数の変更が必要になる。
  • コードを単純化することで、これらの問題を一つずつ解決できる。

内側のループの単純化

  • 内側のループでは、sumをfold(/)を使って単純化できる。
  • ' (each) は配列を返すため、Cグローバル変数を削除できる。
  • i、j、k変数を取り除いてループを単純化できる。

ループの除去とグローバル変数の最小化

  • kなしで行と列を直接対応付けることで、中間ループを除去できる。
  • jを除去するために、Bの各列をA[i]と組にできる。
  • iを除去するために、eachleftを使ってAの各行をBの各列と組にできる。
  • もはやグローバル変数は不要である。

行列積関数の最終形

  • + (転置) はコストが高いため、取り除くことができる。
  • xの各行をyの各列と掛け合わせる代わりに、Bの各行をA全体に合わせることで、暗黙的に同じ処理を行える。
  • 最終的に、簡潔で明示的な行列積関数が得られる。
  • コードを単純化する過程は、最初は多くの段階を経るが、Kに習熟するほど容易で直感的になる。
  • 行列積は、Kの配列サポートとよく噛み合う単純な手続きである。
  • Kとうまく噛み合わない、より多くのアルゴリズムとその扱い方は今後の章で扱う予定である。

GN⁺の見解

  • この記事は、K言語を使って行列積のようなアルゴリズムをどのように単純化し最適化できるかを示している。
  • REPLによる即時フィードバックとコードの反復的な改善はKプログラミングの中核的な特徴であり、初級ソフトウェアエンジニアにとっても有用な学習方法である。
  • コード単純化の過程はプログラミング能力を高めるうえで重要であり、この記事はその過程を具体例を通して分かりやすく説明している。

関連記事

1件のコメント

 
GN⁺ 2024-01-15
Hacker Newsの意見

  • 配列言語の有用性や理解しやすさについて、多くの人が疑問を呈している。

    • 配列言語はあらゆる問題に適しているわけではない。
    • 多くの種類の問題に対して驚くほど有能である。
    • 配列言語の利用者はたいてい非常に賢い。
    • 配列言語の動作原理を学ぶのは大きな挑戦である。
    • 配列言語で「手続き的」なコードを書くのは非常に悪いことだ。
    • tacit programming を理解することは、精神を拡張する素晴らしい体験である。
    • verb trains を内面化するときの体験。
    • 配列ベースの言語があらゆる次元の配列を扱う方法の理解。
    • under の動作方法の理解。
    • function exponents の動作方法の理解。

  • 配列言語には驚くべき側面が多くあり、上の一覧はその一部にすぎない。

    • Aaron Hsu が並列 APL コンパイラを開発する過程を見て、配列言語の現実的な潜在力を確信するようになった。
    • APL コードの「意味密度(semantic density)」についての議論。

  • 配列プログラミングを聞いたことがなく、入門を求めるなら "The Array Cast" がおすすめ。

  • 70年代に APL/APL2 を知って夢中になったが、関数を合成する能力のほうにより魅力を感じた。

    • Haskell は純粋かつ型付きなので、APL よりも面白く強力である。
    • APL の「思考の道具としての記法」は、過度な簡潔さを正当化する論理に見える。

  • 配列言語を使ううえで最も重要な気づき:

    • 動詞はアルゴリズムである。
    • 動詞(または副詞)の連続は、これまで使った中で最も直接的な合成方法である。
    • プログラムは文や式の集合ではなく、アルゴリズムの合成である。
    • 配列、マップ、関数にまたがって定義域と値域を一貫して扱うという考え方。
    • コードを読むとき、目が「あちこち飛び回る」必要のない左から右への評価。
    • データにコードを送ることが可能であり、むしろ好ましい。
    • K 言語の追加の利点: ビュー(つまり依存関係)を直接実装でき、インタープリタによるホットコードローディングが可能である。

  • 配列言語に対する質問: 「N より小さい数のうち、条件 P を満たすすべての数を見つける」のような作業はどう行うのか?

    • 配列言語では通常、1 から N までの配列を生成し、その配列に対して条件をテストしたうえで、条件が真の要素だけを得るためにマスクを適用する。
    • N が大きく、条件が頻繁には真にならない場合、不必要に多くの一時配列を生成するのはメモリや資源の浪費に見える。
    • 配列言語の実装は、このような問題を最適化したり、遅延評価(lazy evaluation)のような手法を使って解決したりできる。

  • J 言語についての経験: 配列言語のパラダイムには偏りがあり、あらゆる問題を配列の入れ子として考えることが本当に役立つのか確信が持てない。

    • 問題を単純化できるデータ構造を自由に作ることが、アルゴリズム部分を大きく単純化できる。
    • APL/J/K を使うには、この偏りのためにより賢くある必要がある。

  • K 言語の問題を解いて得た印象: K 言語は意図的に難解である。

    • パズルや巧妙な解法には向いているが、Python で numpy 配列を扱うことでも、配列言語を学び、配列で考える方法を身につけられる。

  • 配列言語 J の例: dot =: +/ . * を使って P と Q の内積(dot product)を計算する。

  • K 言語の文法はより短いが、K 言語がどう動くかについての多くの組み込みの文脈を頭の中に保持しておく必要がある.