はじめに

この文章は配列指向プログラミング言語BQNの使い方をまとめたものです。筆者はそもそもAPLを使ったことがないような初心者ですが BQNはおろか現代的なAPLに関する日本語のページがほぼ見当たらない現状では、自分で色々とメモしたものを日本語でまとめた直しただけでも役に立ちそうなので、自分で作ることにしました。まあ、メモ付きリンク集程度のものになるでしょう。

用語について

monadic

この言葉は通常Haskellで有名なmonadに関することを意味するものだが、APLの文脈では「1引数」を意味する。この文章では1引数の意味で使用する。ちなみに「2引数」に対応する語句は dyadic である。

operator

通常は、関数と類似しているが構文的な差異を持つものを指すもの(sinは関数で+は演算子)だが、APLの文脈では関数を引数に取るもの、すなわち高階関数(の一部）を指す。 BQNではmodifierという語をoperatorの意味で使っている。

この文章ではいわゆる演算子を(も)関数と呼び、高階関数にはmodifierを当て、この語はできるだけ使わないようにする。

コードの見栄えに関して

color highlighten には highlight.js¹ with highlightjs-bqn² を、書体には BQN386³ を使用しているが、何かしらの不具合でグリフの文字化けが起こってしまうようだ。この問題はグリフ間にスペースを挟むことで回避できそうなので、そのようにコードを整形してある。

    ( 𝕨𝕊𝕩 ) 𝕊 ( 𝕨𝕊𝕩 )
    ((𝕨𝕊𝕩))𝕊((𝕨𝕊𝕩))          # 上の式から括弧まわりの空白文字を消しただけなのだが🤷

奇妙なところにスペースが空いているのはそういう理由なのでご理解いただきたい。

https://github.com/highlightjs/highlight.js

https://github.com/razetime/highlightjs-bqn

https://github.com/dzaima/BQN386

設問に関して

いくつかの設問には🧑‍🎓マークを付けている。これはその設問が出現するまでに説明した内容では解答はできないことを意味する。例えば関数グリフの章の問題で解答にmodifierが使われているなど。

最後に

どうも「はじめに」は作れても「おわりに」は作れないようなので、ここに書いておく。

Happy Array Programming!

1. 実行環境と情報源

オンラインREPL

https://mlochbaum.github.io/BQN/try.html - 構文木を表示する機能がある
https://bqnpad.mechanize.systems/ -- フォントが大きい
https://bqnpad.mechanize.systems/notebook -- セルに分かれているのでちょっとだけjupyter notebook的に使える

環境構築

インタプリタ

CBQN -- https://github.com/dzaima/CBQN

この文書ではインタプリタへの入力とその出力を多くのAPL関連の文書と同様に、

入力は4文字のインデント付き
出力はインデントなし

のcode blockで表示している。

ただし、

リスト構文では要素間は,で区切る事が必要なので入力では文法通りに
REPLの出力ではなぜか,は省略されているが、出力は出力された通りに

表示している。以下のように出力部をコピーして入力しようとすると構文エラーになるので注意のこと。

    ⟨1,2,3⟩
⟨ 1 2 3 ⟩
    ⟨ 1 2 3 ⟩        # 上の出力をコピーした
Error: Double subjects (missing ‿?)
at     ⟨ 1 2 3 ⟩
           ^

フォント

BQN386 -- https://github.com/dzaima/BQN386

編集環境

bqnlsp -- https://github.com/shnarazk/learn-bqn/blob/main/bqnlsp.md
tree-sitter-bqn -- https://github.com/shnarazk/tree-sitter-bqn

ライブラリ

bqn-libs -- https://github.com/mlochbaum/bqn-libs
BQNcrate -- https://mlochbaum.github.io/bqncrate/

情報源

community -- BQN/community/index.html
Matrix -- https://matrix.to/#/#bqn:matrix.org
Array Cast -- https://www.arraycast.com/

2. 言語の基礎要素

グリフ

グリフ(glyph)は1文字で関数やmodifierなどを表す、多くのプログラミング言語では出現しない表意文字を意味する¹。 BQNでは一連のグリフ列が1トークンを構成することはない(常に1文字が1トークンとなる)。そのためグリフ間には空白文字を置く必要はない。

    g ← "+-×÷⋆√⌊⌈∧∨¬|≤<>≥=≠≡≢⊣⊢⥊∾≍⋈↑↓↕«»⌽⍉/⍋⍒⊏⊑⊐⊒∊⍷⊔!˙˜∘○⊸⟜⌾⊘◶⎊⎉˘⚇¨⌜⍟⁼´˝`∞@π"
    t ← "array"‿"number"‿"char"‿"func"‿"1-mod"‿"2-mod"
    ⍉t≍(≠⊸⋈)¨•type∘•BQN∘⋈¨⊸⊔∧g
┌─
╵ "array"  ⟨ 0 ⟨⟩ ⟩
  "number" ⟨ 2 "π∞" ⟩
  "char"   ⟨ 1 "@" ⟩
  "func"   ⟨ 44 "!+-/<=>|«¬»×÷↑↓↕∊√∧∨∾≍≠≡≢≤≥⊏⊐⊑⊒⊔⊢⊣⋆⋈⌈⌊⌽⍉⍋⍒⍷⥊" ⟩
  "1-mod"  ⟨ 9 "`¨´˘˙˜˝⁼⌜" ⟩
  "2-mod"  ⟨ 11 "∘⊘⊸⌾⍟⎉⎊○◶⚇⟜" ⟩
                                                                 ┘

→ Try it online⌨️

定義を調べてないので，表意文字と言い切っていいのか自信はない。

型とatom

https://mlochbaum.github.io/BQN/doc/types.html

以下の型を持つ。他の配列指向言語と同様に enum や struct などのユーザ定義データ型は存在せず、配列のみで対象領域をモデル化することになる。ただし名前空間を class のように使うことでオブジェクト指向的なプログラミングスタイルを取ることもできる²。

#³	型	備考
0	配列	CBQNでは使える次元(rank)は0から100(間違っているかも)
1	数値	保持する値に応じた表現(CBQNではf64, i64, bool)を自動選択
2	文字	Unicode code pointを採用。UTF-8ではないそうだ。
3	関数
4	1-modifier
5	2-modifier
6	名前空間

配列以外の型を持つ値を atom と呼ぶ。

BQN/doc/oop.html

BQN/spec/system.html#operation-properties

リテラル

文字定数の記法はちょっと変わっているので原典を参照のこと。エスケープ文字がないのでそのようなものが必要な文字はnull文字を表す'@'への加算で作り出さないといけない。例えば、TAB = ctrl-I は @+'I'¬'A' または簡略化して @+9 となる。
数値リテラルとして以下の文字
- '¯' -- 負の数を表す。-は減算または符号を反転を意味する関数としてのみ使用される
- '∞'
- 'π'
が使えるので注意。この3文字は数字の一種なので識別子の2文字目以降としても使えるので注意。

識別子

識別子は大文字で始まると値のroleを持つ。
識別子が小文字で始まると関数のroleを持つ。
識別子がアンダースコア'_'列で始まり、アンダースコア'_'列で終わらないなら1-modifierのroleを持つ。
識別子がアンダースコア'_'列で始まり、アンダースコア'_'列で終わるなら2-modifierのroleを持つ。

roleは出現毎に選択できるのでfは文脈さえ適切であればFとして参照できる。つまり fとFは同じものを指す。さらに識別子中のアンダースコア '_' は無視される。つまり以下のようになる。

   a_b ← 1         # 変数 'a_b' の定義
1
   a_b             # これは当然
1
   ab              # 定義してないはずなのだが
1
   aB              # 定義してないはずなのだが
1
   A_b             # 関数のroleなのでは?? どう書くかよりも型が優先された??
1
   ab____          # modifierに見えるが後置アンダースコアはroleには影響しないし無視される
1
   _m2_ ← ○        # 2-modifier '_m2_' の定義
○
   + _m2_ +        # これは当然
+○+
   + __m2__ +      # 定義してないはずなのだが
+○+
   + ___m___2___ + # 定義してないはずなのだが
+○+

このことがわかってないと、名前空間を使う際に思いもかけないことになる。

ns_ ← {
  s___ ⇐ 0
  F___ ⇐ +
  __m1 ⇐ ´
  _m2_ ⇐ ⌾
}
{s‿f‿m1‿m2⇐}

関数適用

他の配列指向言語と同様に関数およびmodifierは1引数または2引数に限定される⁴。関数適用は右結合なので自分より右のものを簡約し終わった値が関数の右引数𝕩の値となる。

⁴

私見だがこの制約はpoint-free coding styleと相性がいい。

2.1 rank多相 -- rank polymorphism

全ての関数ではないが、rank多相を持つ関数は引数の型に対して以下のように振舞う。

両引数がatomの場合はそのまま関数適用をする
片方のみがatomである場合はatomデータを同じ形状の配列に持ち上げ、要素同士の関数適用を行う
形状が一致するprefixを持つ場合はそれ以降のshapeについてrank多相を再帰的に適用する
それ以外の場合は形状不一致で実行時エラー

最も簡単でよく知られたスカラー値と配列の場合に話を単純化する¹と上のルールは以下のように言い換えられる。

両引数がスカラーの場合はそのまま関数適用をする
両引数が配列でその形状が同じである場合は対応する要素同士の関数適用を行う(HaskellのFanctorみたいな感じ)
1引数が配列で他引数がスカラーである場合はスカラーデータを同じ形状の配列に持ち上げ、要素同士の関数適用を行う
それ以外の場合は形状不一致で実行時エラー

スカラーから配列への持ち上げは𝕨と𝕩のどちらでも同じように行われる。

   1+3           # atom-to-atom
4
   1‿2‿3+5‿0‿2   # array-to-array
⟨ 6 2 5 ⟩
   1+2‿3‿4       # atom-to-array
⟨ 3 4 5 ⟩
   0‿1‿2+5       # array-to-atom
⟨ 5 6 7 ⟩
   0‿1+2‿3‿4     # array-to-array
Error: Mapping: Expected equal shape prefix (⟨2⟩ ≡ ≢𝕨, ⟨3⟩ ≡ ≢𝕩)
at 0‿1 + 2‿3‿4
       ^

rank多相のdispatchが期待したものでない場合は、配列を「atom化」する（単位配列に入れる）enclose '<' で対処することが一般的である²。

    0=0‿2‿0‿1‿0‿2‿2         # この例では0と等しいかどうかの配列を作る
⟨ 1 0 1 0 1 0 0 ⟩
    1=0‿2‿0‿1‿0‿2‿2         # 同様に1と等しいかどうかを調べる
⟨ 0 0 0 1 0 0 0 ⟩
    0‿1=0‿2‿0‿1‿0‿2‿2       # 両方の処理をまとめて行いたいのだが
FIXME
    0‿1=¨<0‿2‿0‿1‿0‿2‿2     # 片方をatom化したのでエラーが解決
FIXME
    0‿1=<0‿2‿0‿1‿0‿2‿2      # rankの問題が解決したので明示的なmappingは不要
FIXME
    ∨´0‿1=<0‿2‿0‿1‿0‿2‿2    # 2つの結果をfoldして目的の結果を得た
⟨ 1 0 1 1 1 0 0 ⟩

FIXME

ちなみにこの目的を達成するなら別の関数を使った方が簡単になる。

    0‿2‿0‿1‿0‿2‿2∊0‿1
⟨ 1 0 1 1 1 0 0 ⟩

APLの説明で必ず出てくるスカラーとベクターの加算は一般化されたルールの説明としては不十分。配列間での持ち上げに触れておかねば。でなければbqncrateにある多次元に一般化された「行列」積が理解できないのではなかろうか。

実はこの方法は比較関数<, ≤, ⌊などで期待した通りに動かない。そのため、文字列の比較はやってみると意外に難しい。ということでここで 設問🧑‍🎓：文字列𝕨, 𝕩のうち辞書的順序で小さい方を返す関数を定義せよ。

2.2 roleと型

BQNの式は以下の4つのroleのどれかを構文的に与えられる¹。

subject
fuction
1-modifier
2-modifier

構文的というのは実際の型とは違うことがあることを意味している。例えば、関数適用の結果は常にsubjectである。従って関数適用の結果を変数に代入するならその変数は小文字で始まらなければならない。

    f ← {𝕤 ⋄ {𝕩+1}}@       # 関数を返す関数
*function*
    F ← {𝕤 ⋄ {𝕩+1}}@
Error: Role of the two sides in assignment must match

fはsubjectであるので、通常の関数に渡すことができ、その中で通常の関数として使うために関数を表すFとして参照することができる。

    {𝕏 10}f     # 𝕩はsubject, 𝕏は𝕩をfunctionのroleに変換したもの
11

高階関数はmodifierであると言ったが、型だけで考えるとこのように一般の関数でも関数を受け取ることができるように見えてしまう。 roleも考慮することが必要である。関数を引数に取るprimitive関数としてreshape '⥊'を挙げておく。

BQN/doc/syntax.html#expressions

設問🧑‍🎓

    AsFunction ← {𝕨 𝕊 𝕩 : 𝕎 𝕩}
    ({𝕊 x : {F y : x+y}} 1) AsFunction 2

上式はエラーを起こすか
AsFunctionはfunctionかmodifierか
上式を等価変換した下式はエラーを起こすか

    AsFunction ← {𝕨 𝕊 𝕩 : 𝕎𝕩}
    {F y : 1+y} AsFunction 2

逆にデータがfunctionのroleを持つ例も挙げておく。

   3 1
Error: Double subjects (missing ‿?)
at 3 1
     ^
   3¨ 1
┌·
· 3
    ┘

modifier'¨'の左引数の位置にあるので数値3はfunctionのroleを持ち、3を返す恒等関数となる。

2.3 基本関数群

関数は4章で、modifiersは5章で説明するつもりなのだが、それまでの説明に関数やmodifiersを全く使わないわけにはいかないので、それらの章までに出現するものを「基本」と称してここで紹介することにする。

なお、この節では𝔽/1は関数𝔽がmonadic functionであることを、𝔽/2は関数𝔽がdyadic functionであることを表す。そしてわかりやすさのためトークン間にはより空白を置いて記述する。

また、‿はリテラル構成子であり、関数ではなく、関数適用よりも高い優先度を持つので念のため。

関数

算術計算 `+-×÷⋆√`

乗算は×、除算は÷、冪乗は⋆、moduloは|で表される。これらの関数はそれぞれmonadic applicationでは違う意味を持つので注意。

floor関数は⌊/1、ceiling関数は⌈/1である。整数除算はグリフとしては存在しないので除算÷/2の結果を⌊/1で整数化することになる。

Join/1, Join To/2 '`∾`'

Join Toは'∾'のdyadic applicationで𝕨と𝕩とを結合する。𝕨が長さ\(l\)の配列、𝕩が長さ\(m\)の配列とすると𝕨∾𝕩は\(l+m\)の長さの配列になる。

    1‿2∾5‿6‿7
⟨ 1 2 5 6 7 ⟩
    "abc" ∾ "xyz"
"abcxyz"
    "abc" ∾ 1‿2‿3
⟨ 'a' 'b' 'c' 1 2 3 ⟩

Joinは'∾'のmonadic applicationである。𝕩はリストのリストであり、それらを結合する。

   ∾ ⟨⟨1⟩,⟨2,3⟩,⟨0,4⟩⟩
⟨ 1 2 3 0 4 ⟩

Pick '`⊑`'

    1 ⊑ 3‿2‿1
2
    ¯1 ⊑ 3‿2‿1
1
    0 ⊑ 3‿2‿1
3
    ⊑ 3‿2‿1
3

Range/1 '`↕`'

    ↕ 4
⟨ 0 1 2 3 ⟩
    ↕ 0
⟨⟩
    ↕ 2‿3    # 多次元配列も指定できる
┌─
╵ ⟨ 0 0 ⟩ ⟨ 0 1 ⟩ ⟨ 0 2 ⟩
  ⟨ 1 0 ⟩ ⟨ 1 1 ⟩ ⟨ 1 2 ⟩
                          ┘

Modifiers

modifierは

1つの関数を引数に取り修正を加えた関数を返す1-modifier
2つの関数を引数に取りそれらから構成された新たな関数を返す2-modifier からなる。高階関数である。

modifierの適用は関数適用よりも優先度が高い。

    ¯5 √○| ¯9
9
    ¯5 (⌈○|) ¯9    # 関数の合成後に適用
9
   # (¯5⌈) ○ (| ¯9)    # ではない。そもそも(¯5√)は正しい構文ではない
   # ¯5 (⌈○ (| ¯9))    # ではない。○の右引数が関数ではなくなっている

Each '`¨`'

関数型プログラミングでお馴染みのmap関数に相当する。

    {1+𝕩}¨ 3‿2‿1‿0    # リスト3‿2‿1‿0に対して{1+𝕩}という関数をmapする
⟨ 4 3 2 1 ⟩

Fold '`´`'

関数型プログラミングでお馴染みのfold関数に相当する。適用順序などの詳細は5.2 1-modifiersにて。

   +´ 1‿2‿4‿10    # リスト1‿2‿4‿10に対して+という関数でfoldする
17

∾/1は∾/2のfold版になる。

    ∾ ⟨⟨1⟩,⟨2,3⟩,⟨0,4⟩⟩
⟨ 1 2 3 0 4 ⟩
    ∾´ ⟨⟨1⟩,⟨2,3⟩,⟨0,4⟩⟩    # → ⟨1⟩∾⟨2,3⟩∾⟨0,4⟩
⟨ 1 2 3 0 4 ⟩

3. 配列

BQNの配列は多次元配列であり、リストをネストさせたものとは別である。両者は形状が違う。
一部のprimitive functionにとっては存在するデータ型は配列しかない

References

あまり関係ないのではあるが、配列とは何であろうか(自動翻訳字幕は全くのゴミなので見ないように)

3.1 配列の表示形式

空白行の数

https://mlochbaum.github.io/BQN/doc/array.html

要素の並びは以下のルールに従う。

最下位の軸は横に並ぶ。従ってリストは横に要素が並ぶ。
それ以外の軸は縦に並ぶ。下から\(n\)番目の軸のセル間には\(n-2\)行の空白行が置かれる。

例を以下に示す。

   4⥊∞            # 1次元なので横に並ぶ
⟨ ∞ ∞ ∞ ∞ ⟩
   2‿4⥊∞          # 下から2軸めは上下に並ぶ
┌─
╵ ∞ ∞ ∞ ∞
  ∞ ∞ ∞ ∞
          ┘
   2‿2‿4⥊∞
┌─
╎ ∞ ∞ ∞ ∞
  ∞ ∞ ∞ ∞         # 下から3軸めのセル間には1行の空白行が挟まれる

  ∞ ∞ ∞ ∞
  ∞ ∞ ∞ ∞
          ┘
   2‿2‿2‿4⥊∞
┌─
┆ ∞ ∞ ∞ ∞
  ∞ ∞ ∞ ∞

  ∞ ∞ ∞ ∞
  ∞ ∞ ∞ ∞         # 下から4軸めのセル間には2行の空白行が挟まれる


  ∞ ∞ ∞ ∞
  ∞ ∞ ∞ ∞

  ∞ ∞ ∞ ∞
  ∞ ∞ ∞ ∞
          ┘

rank表示

REPLで表示された配列は要素だけでなくrankが左上に置かれたギズモ(小さなシンボル)で表されている。

rank=0(単位配列)の場合は"┌"の直右・直下に"·"が置かれる。

   <∞
┌·
· ∞
    ┘

rank=1の場合はギズモは表示されない。

   4⥊∞            # 1次元なので横に並ぶ
⟨ ∞ ∞ ∞ ∞ ⟩

rank=2の場合は"┌"の直下に"╵"が置かれる。行間に空白をおいてないと単なる縦線に見えてしまうが、実は分離されているので縦に2つ積み重なっていることが表現されている。

   2‿4⥊∞
┌─
╵ ∞ ∞ ∞ ∞
  ∞ ∞ ∞ ∞
          ┘

rank=3の場合は"┌"の直下に"╎"が置かれる。

   2‿2‿4⥊∞
┌─
╎ ∞ ∞ ∞ ∞
  ∞ ∞ ∞ ∞

rank=4の場合は"┌"の直下に"┆"が置かれる。

   2‿2‿2‿4⥊∞
┌─
┆ ∞ ∞ ∞ ∞
  ∞ ∞ ∞ ∞

rank=5の場合は"┌"の直下に"┊"が置かれる。

   2‿2‿2‿2‿4⥊∞
┌─
┊ ∞ ∞ ∞ ∞
  ∞ ∞ ∞ ∞

rank≥6の場合は"┌"の直右にrank数が置かれる。

   2‿2‿2‿2‿2‿4⥊∞
┌6
┊ ∞ ∞ ∞ ∞
  ∞ ∞ ∞ ∞

3.3 配列の特徴量

https://mlochbaum.github.io/BQN/doc/shape.html

以下の3次元配列mについて考えよう。

   m ← 2‿3‿5⥊0
┌─
╎ 0 0 0 0 0
  0 0 0 0 0
  0 0 0 0 0

  0 0 0 0 0
  0 0 0 0 0
  0 0 0 0 0
            ┘

mには3つの軸があり、その全てを指定することで要素0にアクセスできる。言葉を補って、

3軸(その定義域は\([0,2), [0,3), [0,5)\))を添字として1回指定することで要素を得る。

と言い換え、このことから、

3軸あることからrank(=)を3
その定義域からshape(≢)を⟨2, 3, 5⟩
添字を1回指定することからdepth(≡)を1

と表現する。

   =m    # rank
3
   ≡m    # depth
1
   ≢m    # shape
⟨ 2 3 5 ⟩

depth

https://mlochbaum.github.io/BQN/doc/depth.html

要素がatomになってない以下の3次元配列nの形状について考える。

   n ← 2‿3‿5⥊<"abcdef"
┌─
╎ "abcdef" "abcdef" "abcdef" "abcdef" "abcdef"
  "abcdef" "abcdef" "abcdef" "abcdef" "abcdef"
  "abcdef" "abcdef" "abcdef" "abcdef" "abcdef"

  "abcdef" "abcdef" "abcdef" "abcdef" "abcdef"
  "abcdef" "abcdef" "abcdef" "abcdef" "abcdef"
  "abcdef" "abcdef" "abcdef" "abcdef" "abcdef"
                                               ┘

先ほどと同様にnに対して添字を1回指定することで要素"abcdef"にアクセスできるが。これは文字列すなわち文字型の1次元配列である。従って要素を得る過程は以下のように表現される。

3軸を1回指定することで配列の要素にアクセスできる。

   1‿1‿1⊑n
"abcdef"

さらに要素である文字列に対して1つの軸(その定義域は\([0,6)\))を1回指定することでatomである文字型データを得ることもできる。

   3⊑1‿1‿1⊑n
'd'
   1‿1‿1‿3⊑n           # 4次元配列ではない
Error: ⊑: Picking item at wrong rank (index 1‿1‿1‿3 in array of shape 2‿3‿5)
at 1‿1‿1‿3⊑n
          ^

そこで、配列の形状や添字は先のmと変わらないが、

添字を最大2回指定できる(この時得られるデータはatomである文字型)ことからdepthは2

となる。

   =n    # rank
3
   ≡n    # depth
2
   ≢n    # shape
⟨ 2 3 5 ⟩
   ≡m    # depth of m
1

配列と文字列の間に単位配列が入っていて、そのことを考慮しなければいけないように思うかもしれない。しかし、このnは文字列"abcdef"が入った単位配列をreshape(⥊)で2次元配列へ変換したものであり、nの中には単位配列は存在していない。 𝕨⥊<𝕩 は𝕩の入った単位配列を並べるためのideomではなく、(atomかどうかに関わらず)𝕩を並べるためのものである。

nが4次元配列にならない理由も𝕨⥊<𝕩という変換方法から来ている。そうしたい場合には明示的に文字列をshape2‿3‿5‿6へreshape(⥊)することが必要なようである。

例1

式	=	≠	≡	≢	注釈
`1`	0	1	0	`⟨⟩`	a base data type
`<1`	0	1	1	`⟨⟩`	a unit array
`7‿8‿9`	1	3	1	`⟨3⟩`	a list, 1D array
`<7‿8‿9`	0	1	2	`⟨⟩`	a unit array of list
`7‿8‿9≍7‿8‿9`	2	2	1	`⟨ 2 3 ⟩`	数値を要素に持つ2次元配列
`⟨0⟩‿⟨1⟩‿⟨2⟩)≍(⟨0⟩‿⟨1⟩‿⟨2⟩)`	2	2	2	`⟨ 2 3 ⟩`	2次元配列の中に配列

例2: 要素の参照

    l ← ⟨0⟩‿⟨1⟩‿⟨2⟩)≍(⟨3⟩‿⟨4⟩‿⟨5⟩)
┌─
╵ ⟨ 0 ⟩ ⟨ 1 ⟩ ⟨ 2 ⟩
  ⟨ 3 ⟩ ⟨ 4 ⟩ ⟨ 5 ⟩
                    ┘

式	=	≠	≡	≢	返値
`0⊏l`	1	3	2	`⟨3⟩`	`⟨ ⟨ 0 ⟩ ⟨ 1 ⟩ ⟨ 2 ⟩ ⟩`
`0‿1⊏l`	2	2	2	`⟨ 2 3 ⟩`	これはビックリその1
`1‿2⊑l`	1	1	1	`⟨ 1 ⟩`	`⟨5⟩`
`2⊏1⊏l`	0	1	2	`⟨⟩`	これはビックリその2
`⊑⊑2⊏1⊏l`	0	1	0	`⟨⟩`	`5`

これはビックリその1

1‿2は二つの軸を指定しているのではなく、範囲を指定している。

┌─
╵ ⟨ 0 ⟩ ⟨ 1 ⟩ ⟨ 2 ⟩
  ⟨ 3 ⟩ ⟨ 4 ⟩ ⟨ 5 ⟩
                      ┘

これはビックリその2

⊏は取り出さないのでunitになった

┌·
· ⟨ 5 ⟩
        ┘

4. 関数グリフ Function Glyphs

    3⊑•type∘•BQN∘⋈¨⊸⊔∧"+-×÷⋆√⌊⌈∧∨¬|≤<>≥=≠≡≢⊣⊢⥊∾≍⋈↑↓↕«»⌽⍉/⍋⍒⊏⊑⊐⊒∊⍷⊔!˙˜∘○⊸⟜⌾⊘◶⎊⎉˘⚇¨⌜⍟⁼´˝`"
"!+-/<=>|«¬»×÷↑↓↕∊√∧∨∾≍≠≡≢≤≥⊏⊐⊑⊒⊔⊢⊣⋆⋈⌈⌊⌽⍉⍋⍒⍷⥊"

→ Try it online⌨️

数多いし原典がそんなに説明が足りないわけでもないのでほぼ省略。

検索系関数

注: 以下の表では関数 𝔽 のmonadic applicationを𝔽/1, dyadic applicationを𝔽/2 と表す。

関数	適用例	返値	意味
`⊐/1`	`⊐"abacdc"`	`⟨0 1 0 2 3 2⟩`	最初の出現順位
`⊐/2`	`"ccz"⊐"abacdc"`	`⟨3 3 6⟩`	最初の添字
`⊒/1`	`⊒"abacdc"`	`⟨0 0 1 0 0 1⟩`	出現回数
`⊒/2`	`"ccz"⊒"abacdc"`	`⟨3 5 6⟩`	対応する添字
`∊/1`	`∊"abacdc"`	`⟨1 1 0 1 1 0⟩`	最初の出現か
`∊/2`	`"az"∊"abacdc"`	`⟨1 0⟩`	出現するか
`⍷/1`	`⍷"abacdc"`	`"abcd"`	ユニーク化
`⍷/2`	`"abc"⍷" abcd"`	`⟨0 1 0⟩`	列単位検索

4.1 配列操作関数

To Be Revised

生成

https://mlochbaum.github.io/BQN/doc/map.html#table

同じ形状の二つのリストから Couple '`≍`'で配列を構成する

   x ← 1‿2‿3≍3‿4‿5
┌─
╵ 1 2 3
  3 4 5
        ┘
   x ≍ x
┌─
╎ 1 2 3
  3 4 5

  1 2 3
  3 4 5
        ┘

ちゃんと配列になっているかどうかを確かめるにはShape '≢'の返値で軸が2つあることを見ればよい。ちなみにリストのリストは深さが2で次元が2なのではない。だからstrandをネストさせてもtableにはならない。

Table '`⌜`'を使って二つのリストの外積`𝔽⌜`として生成する

https://mlochbaum.github.io/BQN/doc/map.html#table

要素の追加

https://mlochbaum.github.io/BQN/doc/join.html

配列に要素を追加する、すなわちHaskellでのa -> [a] -> [a]がやりたいならJoin To '∾'を使う。これは要素が左引数なら先頭に追加し、右引数なら最後に追加する。

indexing

https://mlochbaum.github.io/BQN/doc/indices.html

Pick '⊑'やSelect '⊏'を使う。二つ組を処理したいなら

    {𝕗(0⊏𝕨) ⋄ 𝕘(1⊏𝕨)}

filtering

https://mlochbaum.github.io/BQN/doc/replicate.html

Indices '/'はそれぞれの要素の個数を指定するので要素の有無指定以上のことができる。

    0‿1‿1‿0‿3/"abcde"
"bceee"

配列に対するマッピング

https://mlochbaum.github.io/BQN/doc/map.html#mapping-modifiers
要素に対するマッピングにはリストと同じく𝔽¨が使える。
TODO: 要素に対するマッピングにはTable '⌜'が使える。
セルに対するマッピングにはCells '˘'が使える。

配列の更新

配列はimmutableなので変更できない。Under '⌾'を使ったopticsのようなことはできる。

The Under 2-modifier expresses the idea of modifying part of an array, or applying a function in a different domain, such as working in logarithmic space.

https://mlochbaum.github.io/BQN/doc/under.html

Deshape/Reshape '`⥊`'による変形

𝕨	意味
`∘`	要素数は正確に一致することが必要
`⌊`	多い分は切り捨て
`⌽`	不足分は循環追加
`↑`	不足分はfill(arrayなら最初の要素?)

4.2 配列変形系関数

Transpose '`⍉`'

𝕨⍉𝕩 はleading axisの軸とrank=𝕨の軸とを入れ替える。ここでrankはleading axisを基点0として数えるので注意。従って、leading axis のrankは常に0であり、最下位のrankは¯1+=𝕨となる。

monadic applicationでは𝕨=¯1+=𝕩と見做される。

Finally, it's worth noting that, as monadic Transpose moves the first axis to the end, it's equivalent to Reorder Axes with a "default" left argument: (=-1˙)⊸⍉.

→ BQN/doc/transpose.html#Reorder Axes

なお(=-1˙)は1を引く3-train。

   m ← ⥊⟜(↕×´)2‿3‿5
┌─
╎  0  1  2  3  4
   5  6  7  8  9
  10 11 12 13 14

  15 16 17 18 19
  20 21 22 23 24
  25 26 27 28 29
                 ┘
   =m
3
   ⍉m        # leading axitと最下位軸の交換
┌─
╎  0 15
   1 16
   2 17
   3 18
   4 19

   5 20
   6 21
   7 22
   8 23
   9 24

  10 25
  11 26
  12 27
  13 28
  14 29
        ┘
   0⍉m        # leading axis = 0なので何も起こらない
┌─
╎  0  1  2  3  4
   5  6  7  8  9
  10 11 12 13 14

  15 16 17 18 19
  20 21 22 23 24
  25 26 27 28 29
                 ┘
   1⍉m        # leading axisとその直下の軸の交換(最下位軸には影響なし)
┌─
╎  0  1  2  3  4
  15 16 17 18 19

   5  6  7  8  9
  20 21 22 23 24

  10 11 12 13 14
  25 26 27 28 29
                 ┘
   2⍉m        # leading axisと最下位軸の交換
┌─
╎  0 15
   1 16
   2 17
   3 18
   4 19

   5 20
   6 21
   7 22
   8 23
   9 24

  10 25
  11 26
  12 27
  13 28
  14 29
        ┘
   3⍉m        # rank = 3なので3軸はない
Error: ⍉: Axis 3 does not exist (3≡=𝕩)
at 3⍉m
    ^

設問1

Reshape '⥊'を使わずに⟨"ABC","DEFG","HIJ"⟩を以下のshapeに変換せよ。

┌─
╵ "ABC"
  "DEFG"
  "HIJ"
          ┘

設問2

Reshape '⥊'を使わずに"ABCD"を以下のshapeに変換せよ。

┌─
╵ "ABCD"
         ┘

設問🧑‍🎓

以下のrank=2の配列mから示した出力を得る関数Fを定義せよ。

    m ← [
      ⟨0,0,1⟩
      ⟨0,2,0⟩
      ⟨3,0,0⟩
      ⟨1,2,7⟩
    ]
    F m
⟨ ⟨0 0 1⟩ ⟨0 2 0⟩ ⟨3 0 0⟩ ⟨1 2 7⟩⟩    # これはdepth=2のリスト

    F ← ⥊<˘

5. Modifier Glyphs

leading axis theory¹絡みのものは押さえておきたい。

BQN/doc/leading.html

5.1. combinatorについて

Conor Hoekstra. 2022. Combinatory Logic and Combinators in Array Languages. In Proceedings of the 8th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming (ARRAY ’22), ACM, 2022. pdf

hxがぶっ飛んだので再び入力する気が戻って来るまでessenceだけ書いておく。

#define swap_int(x,y)    { int tmp = x; x = y; y = tmp;}

    mask ← (¯1=)𝕩
    mask/𝕩

    ❓ ← {𝔽 _𝕣_ 𝔾 𝕩 : y ← 𝔽 𝕩 ⋄ y 𝔾 𝕩}    # あるいは等価変換して {𝔽 _𝕣_ 𝔾 𝕩 : (𝔽 𝕩)𝔾 𝕩}

    (¯1⊸=)❓/𝕩

APLのプログラムが簡潔なのは関数が1文字で表されるからだと勘違いする人がいてもおかしくない。しかし実際にはグリフは40〜60個程度しかなくmonadic applicationとdiadic applicationの意味の違いを考えても実際に1文字で表されるデータ操作、アルゴリズムは100個程度しかないので、それではAPLの簡潔さは説明できない。

むしろ、

point-free coding style(あるいはIverson記法)から来る、引数・返値の明示的記述の省略
combinatorsの多用から来る、ローカル変数・制御構造の明示的記述の省略

が簡潔さの本質である。 💣言葉が汚くて申し訳ないが「同じ識別子が2回出現するなんてバカじゃねーの」である¹。

APLの人がそう言ったわけでもBQNの人がそう言ったわけでもないのでご注意。さらにプログラムが長くなれば理解しやすいようにステップごとに中間結果をローカル変数に反映させて行くことはどの言語でも当然の書き方なのでそれもご注意。

References

Combinatorを使ったプログラムの簡潔さの布教ビデオを見るべし

ちょっと違うがこれもぜひ

5.2. 1-modifiers

    4⊑•type∘•BQN∘⋈¨⊸⊔∧"+-×÷⋆√⌊⌈∧∨¬|≤<>≥=≠≡≢⊣⊢⥊∾≍⋈↑↓↕«»⌽⍉/⍋⍒⊏⊑⊐⊒∊⍷⊔!˙˜∘○⊸⟜⌾⊘◶⎊⎉˘⚇¨⌜⍟⁼´˝`"
"`¨´˘˙˜˝⁼⌜"

→ Try it online⌨️

Undo '⁼'の話は書いておきたい。

Fold '`´`'

Fold '´' は以下のように展開される。

    F´ a‿b‿c‿d‿e → a F b F c F d F e

BQNは右から関数評価を行うことを思い出せば、これは右からのscanである事がわかる。リストの先頭からのscanではないので、そうしたければF´⌽というフレーズが必要になる。

この延長で初期値𝕨が与えられた場合は以下のように展開される。

    𝕨 F´ a‿b‿c‿d‿e  → a F b F c F d F e F 𝕨
    𝕨 F´⌽ a‿b‿c‿d‿e → e F d F c F b F a F 𝕨

Fの引数の一つをアキュムレーターだとすると直感に反してそれは右引数𝕩に対応するので注意すること。

    10{item F sum : item+10×sum}´⌽3‿5‿7   # 10を初期値とするアキュムレーターsumは左引数
10357
    10{𝕨+10×𝕩}´⌽3‿5‿7    # 簡略版：アキュムレーターは𝕩
10357

uncurryとの関係

右引数がlength=2のリストに対するFoldを改めて書き下すと以下のようになる。

    F´ a‿b → a F b

Fを二要素からなる1つの「タプル」を受け取る1引数関数だとすると F´は2引数関数である。従って´はuncurryの操作そのものである¹。

ちなみに逆変換curryは以下の通り∘⋈なのだろう。

    𝕨 F∘⋈ 𝕩 → F(𝕨⋈𝕩)

BQNのドキュメントにはこの関係について明記されてないのだが、興味を持った人が最初に見るであろうA quick start to BQNの最初の変数定義式(L5)にこの変換が出てくる。言われなくても気づけるものなのだろうか。

Cells '`˘`'

配列の要素に対するmapではなく配列のmajor cellに対してmapを行う。配列がrank=nの場合、major cellはrank=n-1の配列に相当し、配列はあたかもmajor cellのリストと見なされる。

返値は配列になるので同じshapeを持つ事が要求される。

The Cells modifier ˘ applies a function to major cells of its argument, much like Each applies to elements. Each result from 𝔽 becomes a major cell of the result, which means they must all have the same shape.

    m ← 3‿3⥊↕9
┌─
╵ 0 1 2
  3 4 5
  6 7 8
        ┘
    -∘¬¨m        # 各要素に対するdecrement
┌─
╵ ¯1 0 1
   2 3 4
   5 6 7
         ┘
    -∘¬˘m        # major cellに対するdecrementだがrank多相により各要素に対するdecrementに帰着
┌─
╵ ¯1 0 1
   2 3 4
   5 6 7
         ┘
    +´˘m         # mにおいてはmajor cellは数値のリストに対応するのでfold可能
⟨ 3 12 21 ⟩
   (↕+´)˘m       # しかし長さが違うリストを返そうとするとエラー
Error: ˘: Incompatible result shapes (encountered shapes ⟨3⟩ and ⟨12⟩)
at (↕+´)˘m
   ^^^^^^
   (¯3↑·↕+´)˘m    # shapeが同じなら問題ない
┌─
╵  0  1  2
   9 10 11
  18 19 20
           ┘

条件分岐

else節を持たない1方向分岐は引数𝕩に対して𝔽を𝕘回繰り返し適用するRepeat '⍟' で実装できる。

多方向分岐はリスト𝕘の𝕗番目の関数を𝕩に対して適用するChoose '◶' で実装できる。

他には条件分岐のblockが使える。

•_timed (CBQN)

実行時間を測るならこれか)profile。

BQN/spec/system.html#time

In BQN matrix, someone uses the F0 to compute the largest group of 1s.

    #!/usr/bin/env cbqn
    F0 ⇐ (0⌈´(-˜˝˘∘‿2⥊0⊸(/∾≠∾˜)))
    F1 ⇐ {F s: ⊑0‿0{((⊑𝕩)⊸⌈⋈𝕨⊸×)𝕨+1⊑𝕩}´s}
    F2 ⇐ {⌈´-˜´˘∘‿2⥊/≠´˘2↕0∾𝕩}
    # F2 ⇐ {⌈´-˜´˘∘‿2⥊/≠´˘2↕0∾𝕩∾⟨0⟩}
    seq ⇐ (100×1000×1000) •rand.Range 2
    •Show "F0"⊸⋈ 10 F0•_timed seq
    •Show "F1"⊸⋈ 2 F1•_timed seq
    •Show "F2"⊸⋈ 10 F2•_timed seq

function	time by `•_timed`
`F0`	0.0916479
`F1`	5.9444225
`F2`	0.3276033

1-modifier glyphの出現頻度

4.3での計算を基にした1-modifiersの出現頻度は以下の通り。

    •Show>>1⊏s4
┌─
╎ 3400 "¨"
  2481 "´"
  1527 "˜"
  793  "˘"
  549  "`"
  508  "⌜"
  263  "˝"
  258  "⁼"
  201  "˙"
           ┘

5.3. 2-modifiers

    5⊑•type∘•BQN∘⋈¨⊸⊔∧"+-×÷⋆√⌊⌈∧∨¬|≤<>≥=≠≡≢⊣⊢⥊∾≍⋈↑↓↕«»⌽⍉/⍋⍒⊏⊑⊐⊒∊⍷⊔!˙˜∘○⊸⟜⌾⊘◶⎊⎉˘⚇¨⌜⍟⁼´˝`"
"∘⊘⊸⌾⍟⎉⎊○◶⚇⟜"

→ Try it online⌨️

Rank '⎉'の話は書きたいと思う。

Under

Under '⌾'も面白い。というよりも習得必須項目である。

例えば、以下のような2要素からなるレコードのリストを第2項目で整列するにはどうしたらいいだろうか。

    l ← ⟨3‿"ee",2‿"zz",0‿"oh",5‿"co",1‿"st"⟩
    ∧l        # これは第1項目での整列
⟨ ⟨ 0 "oh" ⟩ ⟨ 1 "st" ⟩ ⟨ 2 "zz" ⟩ ⟨ 3 "ee" ⟩ ⟨ 5 "co" ⟩ ⟩

Underを使うならレコードのリストを'>'で配列化し、キーとなる要素が先頭に来るようにRotate '⌽'した上で '∧'で整列し、元に戻せばいいのでこのようになる。

    ∧⌾(1⌽˘>)l        # 1は左へのシフト回数(1なら省略可能)
⟨ ⟨ 5 "co" ⟩ ⟨ 3 "ee" ⟩ ⟨ 0 "oh" ⟩ ⟨ 1 "st" ⟩ ⟨ 2 "zz" ⟩ ⟩

→ Try it online⌨️

Underを使わないならGrade '⍋'を使ったこういうコードだろう。同じ文字数になる。

    (⍋1⊸⊑¨)⊸⊏l    # こちらの1は省略不可

注意このソートがうまくいくのは∧にキーが先頭に来るように並べ替えたレコード全体を渡しているからであって、

   ∧⌾(1⊸⊑¨)

ではキーフィールドのみが整列されてしまうので注意。 ∧は名前空間を含む配列のソートでエラーを起こすので、そのような場合はキーフィールドに対する⍋⍒を使うしかないだろう。

また、最近思いついた応用は、ヒープデータ構造でのparcolate_upを追加要素から根へのパス上の整列問題と捉えてUnderで実装するというものである。

   d ← ∞∾•rand.Deal 16
⟨ ∞ 12 2 16 5 13 3 9 1 7 8 4 11 14 15 0 6 ⟩
   1‿2‿4‿8‿16 ⊏ d              # 最終要素（追加要素）からの半減添字列
⟨ 12 2 5 1 6 ⟩
   ∧⌾(1‿2‿4‿8‿16⊸⊏) d          # 半減列のみを昇順で整列
⟨ ∞ 1 2 16 5 13 3 9 6 7 8 4 11 14 15 0 12 ⟩

∧を使うことで\(O(\log(n))\)の問題を\(O(\log(n)\log(\log(n)))\)にしてしまっているのだが、さて差は出るだろうか？

設問

二つの正整数を以下のように合成する関数Mergeを実装せよ。

    1 Merge 2
12
    33 Merge 1
331
   100 Merge 200
100200
   123 Merge 6789
1236789

→ Try it online⌨️

   Merge ← {𝕩+𝕨×⌈⌾(10⊸⋆⁼)𝕩}
   ⊢+×⟜(⌈⌾(10⊸⋆⁼))        # point-free version

`•_while_`

system valueの中に唯一含められている制御構造が•_while_である。再帰をするよりもメモリ効率がよいので是非。

    count ← 0
    result ← {𝕊 cnt : •Show cnt ⋄ 1+cnt}•_while_{𝕊 cnt : 5>cnt}count
    •Show result
0
1
2
3
4
5
5
    •Show(1+•Show)•_while_(5⊸>)0    # 上の3行から冗長な部分を全て削除
0
1
2
3
4
5
5

2-modifier glyphの出現頻度

4.3での計算を基にした2-modifiersの出現頻度は以下の通り。

    •Show>>2⊏s4
┌─
╎ 3046 "⊸"
  1554 "∘"
  1222 "⟜"
  535  "◶"
  525  "⍟"
  473  "⌾"
  367  "○"
  156  "⊘"
  120  "⎉"
  93   "⚇"
  17   "⎊"
           ┘

6. Fork and Train

💣 私見ですがこんな面白い話に触れてない(現代的)APLの紹介記事なんて読むだけ無駄です。

Tutorial: Combinators -- BQN/tutorial/combinator.html
Tacid programming -- BQN/doc/tacit.html
Conor Hoekstra. 2022. Combinatory Logic and Combinators in Array Languages¹. In Proceedings of the 8th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming (ARRAY ’22), ACM, 2022.

ここに BQN/doc で使われているmodifierの関数適用の図を全部並べたいのだが、あの図は全て埋め込みsvgで簡単じゃないのでとりあえず断念する。

6.1 3-train, the invisible combinator

combinatorは5. Modifier Glyphsにて紹介したが、実はあれだけでは記述できない構造がある。

    ( 𝕨𝔽𝕩 ) 𝕊 ( 𝕨𝔾𝕩 )

このなんということはない構造もcombinatorを一つ用意すればいいように思えるが、問題はAPLやBQNの大原則：関数の引数は高々2個という制約の下ではこの式に出現する3種類の関数𝔽,𝔾,𝕊をcombinatorに渡しようがないことである。もちろんuncurry化してしまえばいいのだが、このよく使うであろうパターンに対して直感的でない記述を強いてしまう。なんとかならないだろうか。

APLの開発者たちが考案した巧妙な方法はcombinatorを書くのをやめよう(だからthe invisible combinator)、3つの関数が項を構成していたら自動的にこの制御構造だとみなそうというものである¹²。

      ( 𝔽𝕊𝔾 ) 𝕩 → ( 𝔽𝕩 ) 𝕊 ( 𝔾𝕩 )     # monadic version
    𝕨 ( 𝔽𝕊𝔾 ) 𝕩 → ( 𝕨𝔽𝕩 ) 𝕊 ( 𝕨𝔾𝕩 )   # dyadic version

これで基本的な関数間の配線に困ることはなくなる(困るようならローカル変数やブロック構造を使おう)。この「3つの関数(だけ)から構成された項」を3-trainと呼ぶ (APLではforkとも呼ぶ)。逆に3つ(以上の)関数を括弧で囲む際には3-trainとして解釈されてもよいか気を付ける必要があるので注意が必要である。

また2-trainは「2つの関数(だけ)から構成された項」であり、単なる2関数の関数合成である。

      ( 𝔽𝔾 ) 𝕩 → 𝔽 ( 𝔾𝕩 )
    𝕨 ( 𝔽𝔾 ) 𝕩 → 𝔽 ( 𝕨𝔾𝕩 )

BQNでは2-train (𝔽𝔾)は明示的に2-modifier Atop'∘'を使って'𝔽∘𝔾とも書ける。Atopを使った方が1文字少なくて済む。

一般化してtrainは「複数の関数(だけ)からなる項」であり、 4つ以上の関数が項を構成している場合は右から3-trainとして合成関数に置き換えていくことで最終的には一つの合成関数になる。

設問2

以下はtrainか。

    # 1.
    (+⊸×⟜-)
    # 2.
    (×1-⌊)

https://aplwiki.com/wiki/Trainによれば Dyalog APLに導入されたのは2014年のことなのでAPLの古い説明には出てこない。ということで日本語ではほぼ読むことができない。

3-trainを「括弧で囲まれた〜」とする説明は間違いである。その定義では以下のF, Gが3-trainになる理由を説明できない。

    3+×-2    # 3 + (× (- 2)) という関数適用の連鎖であり3-trainではない
2
    F ← +×-
    3 F 2      # (3+2)×(3-2) → 5
5
    g ← 1⊑⟨+,+×-,-⟩
    3 G 2      # (3+2)×(3-2) → 5
5

→ Try it online⌨️

括弧で囲まれていることは条件ではなく、複数の関数が項を構成していることが必要であり、式の中ではそのような状況は括弧で囲まないと滅多に出現しないだけである。

3-trainとbefore+after bindsの違い

3-trainがよく似たbefore+after bindsとは違う構造を持っていることを確かめておこう。

    2(|⋈×)5    # 3-train
⟨1 10⟩
    2-⊸⋈⟜×5    # before+after binds
⟨2 1⟩

前者の3-trainは、

    𝕨 ( 𝔽 𝕊 𝔾 ) 𝕩 → ( 𝕨 𝔽 𝕩 ) 𝕊 ( 𝕨 𝔾 𝕩 )

と変換されるのに対して、後者のbefore+after bindsは、

    𝕨𝔽 ⊸ 𝕊 ⟜  𝔾 𝕩 → ( 𝔽 𝕨 ) 𝕊 ( 𝔾 𝕩 )

と変換されるのでどちらも必要になる。

なお、この話は "Combinatory Logic and Combinators in Array Languages"³の7.12でも触れられている。

https://github.com/codereport/Content/blob/main/Publications/Combinatory_Logic_and_Combinators_in_Array_Languages.pdf

設問

以下の構造を2-modifierや3-trainなどの組み合わせで実現せよ。

    𝕨 F ( 𝕨 G 𝕩 )

   (⊣FG)

6.2 Nothing '`·`'

どうしても括弧で囲むことが必要な関数の並びをtrainにするかどうかを制御する際に使われるのが Nothing '·'である。

The character · is called Nothing. While it can be easier to think of it as a value, it can't be passed around in variables, and so can also be interpreted as an element of syntax. The special name 𝕨 also functions as Nothing if the block that contains it is called with one argument (the uppercase spelling 𝕎 doesn't, but instead immediately causes an error). Both · and 𝕨 have a subject role.

以下はNothingの使用例である。

    1(+´--)⟨2,3⟩
⟨ 7 8 ⟩
    1(+´·--)⟨2,3⟩
3

前者ではdyadic function ー で値を生成する3-trainになっている。

𝕨=2, 𝕩=⟨2,3⟩としてdyadic function +´を実行して7
𝕨=2, 𝕩=⟨2,3⟩としてdyadic function -を実行して⟨0,¯1⟩
𝕨=7, 𝕩=⟨0,¯1⟩としてdyadic function -を実行して⟨7,8⟩

一方、後者は途中にNothingというsubjectが入っているので3-trainにはならない: 構文木

𝕨=1, 𝕩=⟨2,3⟩としてdyadic function -を実行して⟨¯1,¯2⟩
𝕨=·, 𝕩=⟨¯1,¯2⟩なのでmonadic function -を実行して⟨1,2⟩
𝕩=⟨1,2⟩としてmonadic function +´を実行して3

Nothingなしで後者を書きたいならこうなってしまう。

    1(+´(--))⟨2,3⟩
3

ということでNothingを使うことで括弧を増やさずにすむ。

3-trainとNothing

上の例は2-trainでの使用例だったが、括弧で囲むだけでできてしまう3-trainの制御としてNothingは使われる事が多い。

(A B C D E)は

A
B
3-train (C D E)

の3-trainだが、

(A B C · D E)は

B
C
2-train (DE)

の3-trainとAとの2-trainになる。

7. ブロック -- Blocks

Blocks -- BQN/doc/block.html

ブロックは以下の4種類に分類される。

複文¹
ヘッダーなし関数/modifier 定義²
ヘッダーあり関数/modifier 定義³
名前空間⁴

関数/modifier 定義かどうかは特殊名 𝔽𝔾w𝕎𝕩𝕏𝕣𝕤 またはヘッダーが出現するかどうかで決まり、ヘッダーのあるなしは':'が出現するかどうかで決まる。名前空間かどうかは'⇐'が出現するかどうかで決まる。

したがってBQNはCFGではあるもののLALR(\(n\))ではない。

BQN/doc/block.html#headerless-blocks

BQN/doc/block.html#arguments

BQN/doc/block.html#block-headers

⁴

BQN/doc/namespace.html

7.1 ヘッダーあり定義ブロック

以下は𝕩をdeconstructするだけのヘッダー(𝕊が含まれてない)だが、これも許されるので注意。

    F ← {a1‿a2‿a3 : a1+a2+a3}

紛らわしい例

    {•Show"ok" ⋄ 1}⍟10 0

Repeat '⍟'の左引数はヘッダーもなく特殊名も含まないので複文ブロックである。複文ブロックは関数Repeatの適用前に評価されるので"ok"が出力され1に簡約される。従って上記のコードは以下と等価である。

    •Show"ok" ⋄ 1⍟10 0

1はRepeatの左引数なのでfunction roleが与えられ、1を返す恒等関数とみなされる。結局、エラーなく恒等関数を10回繰り返し実行し1が返される。一方、画面への出力は1回のみとなる。

紛らわしい例2

ブロックは必ずしも関数名を踏まなくてもよい。ただし注意が必要になる。

   •Type¨{x‿y : 1}‿{x : 1}
⟨ 3 1 ⟩        # 両者の型は違う

このように{x‿y : 1}は関数であるが、{x : 1}は数だと言われる。何が起きているのだろうか。

まず、関数が右引数しか場合はない場合は関数名をブロックに含まなくてもよい。

If a header consists of 𝕊 with one argument, like 𝕊 a‿b: or 𝕊𝕩:, the 𝕊 can be left off. See case headers below for examples.

Special names in headers

    {x‿y : 1}@          # 1引数関数。引数を分解しているが参照はしてない定数関数
1
    {𝕊 x‿y : 1}@        # 上のと同じ関数の冗長表現
1
    {𝕊 𝕩 : 1}@          # 上のと同じ関数の冗長表現
1
    {x‿y : x|y}4‿10     # 引数を参照する1引数関数。
2

この仕様には例外がある。

The exception is if the argument is a plain name, as in 𝕊 arg:, because the header arg: is a label for an immediate block as described in the next section.

関数名を書かず、引数をパターンマッチングで分解しない場合はブロックは関数ではなく複文として処理される。

    {x : 1}      # このブロックは関数ではないので引数を必要とせず値が返される。
1

ここでヘッダーに現れているxは引数名ではなくこのブロックを自己参照するラベルである。といっても本体中で使うことはできない。なんというか変な所に置かれたtype annotation¹程度に考えるしかなさそうである。

For immediate blocks, this is the only type of header possible, and it must use an identifier as there's no applicable special name. However, the name can't be used in code: it doesn't make sense to refer to a value while it's still being computed!

ラベルが小文字で始まっていることからこのブロックにsubjectとしての型が与えられている。大文字だとどうなるだろうか。

   {F : 3}1         # 定数関数になっている
3
   {F : 3}          # 関数なので引数がなければ関数そのものが返される
(function block)
   {F : f}10        # Fはブロックそのものを自己参照しており、引数を指しているわけではない
(function block)    # なので引数を与えても関数そのものが返値になる

7.2 条件分岐のためのブロック

'?'を使うことで条件分岐をする複文ブロックを作ることができる。 a ∧ b は短絡しない(∧は関数なのでa, bとも常に評価される)が、?を使った複文ブロックは短絡可能である。

   {•Show "A" ⋄ 0}∧{•Show "B" ⋄ 0}    # 評価順序にも注目
"B"
"A"
0
   {{•Show "A" ⋄ 0} ? {•Show "B" ⋄ 0} ? 1 ; 0}
"A"
0
   {{•Show "A" ⋄ 1} ? {•Show "B" ⋄ 1} ? 1 ; 0}
"A"
"B"
1

7.3 特殊名を使用するブロック

特殊名による関数参照で作られる予期せぬ関数定義ブロック

以下は条件分岐をする関数を定義する例だがうまく動いていない。なぜだろうか。

    Solve ← {part 𝕊 d :
      {1=part ? d ;
       2=part ? ∞ ;
                d 𝕊 d    # 再帰呼び出し
      }
    }
    3 Solve 1       # 実行すると
⟨function block⟩    # 評価されていない

問題は条件分岐に使われているブロックの形式にある。

    part‿d ← 0‿1
⟨ 0 1 ⟩
    {1=part ? d ; 2=part ? ∞ ; d 𝕊 d}    # 複文のように見えるが
(function block)

条件分岐のブロックの中では𝕊が使われているが、これは最内ブロックを指す特殊名であり、その結果このブロックは条件分岐の複文ブロックではなく、ヘッダーなし関数定義ブロックと見做される。関数の最後の式が関数定義なのでSolveは関数を返す関数になってしまっている。これを複文ブロックとするためには特殊名の使用をやめなければならない。従ってSolveに𝕊以外の名前を付けるか、Solveそのものを指定するように書き換えなければならない。

   Solve ← {part Fn d : {1=part ? d ; 2=part ? ∞ ; d Fn d}}  # 内部名Fnを使用
(function block)
   0 Solve 1
1
   Solve ↩ {part 𝕊 d : {1=part ? d ; 2=part ? ∞ ; d Solve d}}  # 外部名を使用
(function block)
   0 Solve 1
1

条件分岐を{}で囲むことをやめてもよさそうに思えるが、そうすると今度は識別子のスコープの問題が生じるため実際的ではないことが多い。

   Solve ← {part 𝕊 d :
     1=part ? d ;
     2=part ? ∞ ;
              d 𝕊 d
   }
Error: Undefined identifiers
    2=part ? ∞;
      ^^^^

特殊名による引数参照で作られる予期せぬ関数定義ブロック

上の問題は関数の参照によって予期せぬ関数定義ブロックが作られた例だったが、 𝕩や𝕨を使った引数の参照でも同じことに起きる。

    F ← {𝕨 𝕊 𝕩 :
      {•Show 𝕨×𝕩 ⋄ 𝕨‿𝕩 (-¬) ↩}    # 何かしら複文のブロックが必要だったとする
    }
(function block)
    2 F 2               # 実行すると
(function block)        # 評価されていない

先と同じようにブロックの中で特殊名𝕩, 𝕨を使ったため関数定義になってしまったのが原因なので、同じ対策が必要である。

    F ← {w 𝕊 x :
      {•Show w×x ⋄ w‿x (-¬) ↩}      # 参照したい引数に固有の識別子を与える
    }
    F ← {𝕨 𝕊 𝕩 :
      𝕨{•Show 𝕨×𝕩 ⋄ 𝕨‿𝕩 (-¬) ↩}𝕩    # 必要な引数を与える
    }

自分のAoCのリポジトリ中に以下のメモを見つけたので貼っておきます。

;はブロックの途中でreturnするものではなく、そこでブロックが終っている。つまり;の前後で違うブロックが定義されていると思った方がよい。

     F ← {
       temp ← 0
       𝕩 = 1 ? temp+1;
       temp ↩ 0        # tempに再代入したのだが
       temp+2
     }
Error: Undefined identifier
at       temp ↩ 0
         ^^^^
     F ← {
       temp ← 0
       𝕩 = 1 ? temp+1;
       temp ← 0        # ということで、ここで必要なのは ↩ ではない!
       temp+2
     }
(function block)

7.4 配列変形演習2

設問1

以下のrank = 3の配列mがあるとする。

    m ← ⥊⟜(↕×´)5‿5‿5
┌─
╎   0   1   2   3   4
    5   6   7   8   9
   10  11  12  13  14
   15  16  17  18  19
   20  21  22  23  24

   25  26  27  28  29
   30  31  32  33  34
   35  36  37  38  39
   40  41  42  43  44
   45  46  47  48  49

   50  51  52  53  54
   55  56  57  58  59
   60  61  62  63  64
   65  66  67  68  69
   70  71  72  73  74

   75  76  77  78  79
   80  81  82  83  84
   85  86  87  88  89
   90  91  92  93  94
   95  96  97  98  99

  100 101 102 103 104
  105 106 107 108 109
  110 111 112 113 114
  115 116 117 118 119
  120 121 122 123 124
                      ┘

以下のように、配列𝕨の下から数えて⊑𝕨番目(1から数える)のrankで1⊑𝕨番目のセル(0から数える)に含まれる要素を全て0にした配列を返す関数Gを関数定義ブロックを使って実現せよ。

    1‿0 G m
┌─
╎ 0   1   2   3   4
  0   6   7   8   9
  0  11  12  13  14
  0  16  17  18  19
  0  21  22  23  24

  0  26  27  28  29
  0  31  32  33  34
  0  36  37  38  39
  0  41  42  43  44
  0  46  47  48  49

  0  51  52  53  54
  0  56  57  58  59
  0  61  62  63  64
  0  66  67  68  69
  0  71  72  73  74

  0  76  77  78  79
  0  81  82  83  84
  0  86  87  88  89
  0  91  92  93  94
  0  96  97  98  99

  0 101 102 103 104
  0 106 107 108 109
  0 111 112 113 114
  0 116 117 118 119
  0 121 122 123 124
                    ┘
    1‿2 G m
┌─
╎   0   1 0   3   4
    5   6 0   8   9
   10  11 0  13  14
   15  16 0  18  19
   20  21 0  23  24

   25  26 0  28  29
   30  31 0  33  34
   35  36 0  38  39
   40  41 0  43  44
   45  46 0  48  49

   50  51 0  53  54
   55  56 0  58  59
   60  61 0  63  64
   65  66 0  68  69
   70  71 0  73  74

   75  76 0  78  79
   80  81 0  83  84
   85  86 0  88  89
   90  91 0  93  94
   95  96 0  98  99

  100 101 0 103 104
  105 106 0 108 109
  110 111 0 113 114
  115 116 0 118 119
  120 121 0 123 124
                    ┘
    2‿3 G m
┌─
╎   0   1   2   3   4
    5   6   7   8   9
   10  11  12  13  14
    0   0   0   0   0
   20  21  22  23  24

   25  26  27  28  29
   30  31  32  33  34
   35  36  37  38  39
    0   0   0   0   0
   45  46  47  48  49

   50  51  52  53  54
   55  56  57  58  59
   60  61  62  63  64
    0   0   0   0   0
   70  71  72  73  74

   75  76  77  78  79
   80  81  82  83  84
   85  86  87  88  89
    0   0   0   0   0
   95  96  97  98  99

  100 101 102 103 104
  105 106 107 108 109
  110 111 112 113 114
    0   0   0   0   0
  120 121 122 123 124
                      ┘
    3‿¯1 G m
┌─
╎  0  1  2  3  4
   5  6  7  8  9
  10 11 12 13 14
  15 16 17 18 19
  20 21 22 23 24

  25 26 27 28 29
  30 31 32 33 34
  35 36 37 38 39
  40 41 42 43 44
  45 46 47 48 49

  50 51 52 53 54
  55 56 57 58 59
  60 61 62 63 64
  65 66 67 68 69
  70 71 72 73 74

  75 76 77 78 79
  80 81 82 83 84
  85 86 87 88 89
  90 91 92 93 94
  95 96 97 98 99

   0  0  0  0  0
   0  0  0  0  0
   0  0  0  0  0
   0  0  0  0  0
   0  0  0  0  0
                 ┘

→ Try it online⌨️

解答

     G ← {r‿c 𝕊 m : 0¨⌾(c⊸⊏⎉r)m}
     G ← {r‿c𝕊m:0¨⌾(c⊸⊏⎉r)m}     # code golf版
     G ← {0¨⌾((1⊑𝕨)⊸⊏⎉(⊑𝕨))𝕩}    # another code golf

名前空間

名前空間はフィールド名によるデータアクセスを可能にするので構造体のようにも使える。特に名前空間の中の関数は環境内の変数に対する代入をサポートしているので状態をもつオブジェクトとして使うことが可能である。

mutabilityとブロック

名前空間を使ってmutableなオブジェクトを作ったとしよう。 mutableなフィールドデータを参照するメソッドはクロージャすなわち定義ブロックでなければならない。ブロック内での識別子アクセスは正しくenviroment chainをたどるが、そうでない関数はデータの更新を追いかけないからである。

    d ← {
      table ← [0‿1,"A"‿"B"]
      Set ⇐ {table 𝕩⌾(𝕨⊸⊑1⊸⊏) ↩}
      GetB ⇐ {((⊏table)⊐𝕩)⊏1⊏table}    # closure版
      GetT ⇐ (⊏table)⊸⊐⊸⊏⟜(1⊏table)    # train版
    }
    •Show [⟨"GetB",d.GetB⌾⋈1⟩,⟨"GetT",d.GetT⌾⋈1⟩]
┌─
╵ "GetB" "B"
  "GetT" "B"
             ┘
    1 d.Set "b"
    •Show [⟨"GetB",d.GetB⌾⋈1⟩,⟨"GetT",d.GetT⌾⋈1⟩]
┌─
╵ "GetB" "b"
  "GetT" "B"        # 更新されていない
             ┘

→ Try it online⌨️

使用例

稼働第1バージョン

環境変数群をenv経由で読み取り、いつでもどの環境変数でもアクセスできる名前空間envを作ろう。

外部プログラムはsystem value•SHを使って呼び出せる。

    •SH<"cal"      # 文字列のリストを要求する
⟨ 0 "     July 2023
Su Mo Tu We Th Fr Sa
                   1
 2  3  4  5  6  7  8
 9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
" ⟨⟩ ⟩
    1⊑•SH<"env"    # 大事な1要素の標準出力の結果のみ必要
"COLORTERM=truecolor
LC_CTYPE=UTF-8
TERM=alacritty
EDITOR=hx
CXX=clang++
CC=clang
LD_DYLD_PATH=/usr/lib/dyld
NIX_STORE=/nix/store
...

この出力をkey-value形式のrank=2の配列に変形すると以下のようになる。

    vars ← >{(⊑'='⊸(⊐˜))⊸(↑⋈(1⊸↓↓))𝕩}¨1↓((¬×(1++`))(@+10)⊸=)⊸⊔1⊑•SH<"env"
┌─
╵ "COLORTERM"           "truecolor"
  "COMMAND_MODE"        "unix2003"
  "LC_CTYPE"            "UTF-8"
  "LaunchInstanceID"    "D27E85ED-4FA3-4DAD-8FAA-FCD3D8F35D96"
...
   {1⊑⊏((𝕩⊸≡)¨((<⊑)˘))⊸/vars}"LC_CTYPE"
"UTF-8"

⟨"LC_CTYPE","UTF-8"⟩とマッチするセルを探すなら

    ⟨"LC_CTYPE","UTF-8"⟩⊸≡⊸/m

となり、このセルから値を取り出すために、

     1⊑⊏⟨"LC_CTYPE","UTF-8"⟩⊸≡⊸/m

となる。検索キーを𝕩とし関数名をVarとすると以下のようになる。

    vars ← >{(⊑'='⊸(⊐˜))⊸(↑⋈(1⊸↓↓))𝕩}¨1↓((¬×(1++`))(@+10)⊸=)⊸⊔1⊑•SH<"env"
    Var ⇐ {1⊑⊏(𝕩⊸≡¨(<∘⊑˘))⊸/vars}

これらを名前空間envにバインドすると以下のようになる。

    env ← {
        vars ← >{(⊑'='⊸(⊐˜))⊸(↑⋈(1⊸↓↓))𝕩}¨1↓((¬×(1++`))(@+10)⊸=)⊸⊔1⊑•SH<"env"
        Var ⇐ {1⊑⊏(𝕩⊸≡¨(<∘⊑˘))⊸/vars}
    }
    env.Var "COLORTERM"
"truecolor"

エラー対応

値を持たない環境変数を与えるとenv.Varがエラーを起こす。

そこでCatch '⎉'を使って不適切な添字による要素のアクセスでのエラーを捉えることにしよう。

    env ← {
        vars ← >{(⊑'='⊸(⊐˜))⊸(↑⋈(1⊸↓↓))𝕩}¨1↓((¬×(1++`))(@+10)⊸=)⊸⊔1⊑•SH<"env"
        Var ⇐ {1⊸⊑∘⊏⎉"" (𝕩⊸≡¨(<∘⊑˘))⊸/vars}
    }
    env.Var "COLORTER"
""

さらに見つからなかった場合の既定値を与えられるようにする。 dyadic applicationによって規定値は与えてもよいし, monadic applicationとして与えなくてもよい。

    env ← {
        vars ← >{(⊑'='⊸(⊐˜))⊸(↑⋈(1⊸↓↓))𝕩}¨1↓((¬×(1++`))(@+10)⊸=)⊸⊔1⊑•SH<"env"
        Var ⇐ {𝕊 𝕩 : ""𝕊𝕩 ; 𝕨 𝕊 𝕩 : 1⊸⊑∘⊏⎉𝕨 (𝕩⊸≡¨(<∘⊑˘))⊸/vars}
    }
    env.Var "COLORTER"
""
    "FullColor" env.Var "COLORTER"
"FullColoro"

並列検索

この方法は配列varの変形と検索を検索キーの個数回実行しており関数プログラミング的ではあるが処理を並列に行う余地がない。実は検索系の関数は複数の検索キーを渡す事ができるので、そのようなグリフを使うだけで並列化される可能性が高い。そこで/を使ったフィルタリングで目的要素を見つける関数型プログラミングから、検索キーの添字を全部返す⊐を使った配列志向のプログラムに変更しよう。

TBC

配列指向プログラミング

この章では言語の特徴を使った配列指向プログラミングの例を紹介する。

2020年に公開されたBQN言語を私は2021年には使い始めていたようなのですでに2年は使っている。そして、その頃に書いたプログラムを今見返すとかなりひどい。大体、以下のような特徴がある。

関数型プログラミングの機能でプログラムを構成しているがrank多相がうまく使えてない
depth≥2の配列(文字列のリストなど)は多用するがrank≥2の配列がほとんど出てこない
trainがうまく使えていない
Underを滅多に使わない
self search系関数を滅多に使わない
空白文字入れすぎ(空白で区切ることを前提とした単語ベースの言語の慣習を考えなしに持ち込んでいる)

関数型プログラミングは前提として、その上に配列指向プログラミングの考え方に慣れる事が必要だと思う。

9.1 Game of Life

配列指向プログラミングの例として、各点を順に計算するのではなく、対象となる2次元空間をそのまま配列で表現し、配列操作のみで全点を計算する手法を紹介する。

最初の例として、APL版の解説ビデオもある ConwayのGame of Lifeを使ってみる。

ソースコード

⟨term⟩ ← •Import"lib/lib.bqn"
LifeInit ← •rand.Range⟜2˜∘⋈
LifeNext ← (3⊸=∨4⊸=∘×)⟜(+´(⥊⋈⌜˜1-↕3)⌽¨<)
LifeShow ← {term.Print⊑⟜"·⚇"˜¨𝕩 ⋄ 𝕩}

# demo
•MakeRand•UnixTime
{•Delay÷50 ⋄ term.Up 2+k ⋄ LifeShow LifeNext 𝕩}⍟500 LifeShow LifeInit⟜(2⊸×)k ← 40

この中で使っているlib.bqnはhttps://github.com/shnarazk/learn-bqn/blob/main/lib/lib.bqnから入手できる。

プログラムの説明

TODO

実行例

9.2 Sudoku ソルバ

Game of lifeで使った、状態点を順にたどるのではなく状態集合を表す配列上の操作で一気に次状態集合を計算するという考え方が全く同じように使える別の例としてSudoku(数独)ソルバを考える。

幅優先探索版プログラム

まず参考にするのはAPLのオンラインREPL https://tryapl.org/ → 'LEARN'タブ → 'Sudoku Solver'である¹。手取り足取り説明してくれるのでそれを見ながら、BQNに直訳すると以下のようになる。

Box  ← {>𝕩/<˘𝕩‿∘⥊𝕩/1+↕𝕩⋆2}     # 盤面にブロック分割番号を割り当てる
RCB  ← {(1+↕𝕩)∾¨Box⊑√𝕩}        # row, column, blockの頭文字
Cmap ← {<˘˘1⊑∘∊¨=⌜˜𝕩}

Sudoku ← {
  map  ← Cmap RCB ≢𝕩
  Avl  ← {(1+↕⊑≢𝕩)(¬∘∊/⊣)0⊸≠⊸/⥊𝕩×𝕨⊑map}
  Nxt  ← {w 𝕊 x : (𝕨Avl𝕩){𝕨⌾(w⊸⊑)𝕩}¨<𝕩}
  Nxtv ← {∾𝕨⊸Nxt¨𝕩}                      # (<s44)Nxtv´⟨0‿0,0‿1,1‿0⟩ のように呼び出す
  >(<(Nxtv´)((0⊸=𝕩⊸(⊑˜))⊸/·⥊·↕≢))𝕩
}

→ Try it online⌨️

説明

最初の3行はセル間の関係を作り出すための関数である。

4×4の盤面（従って出現する数字は1から4となる）に対するRCB 4‿4の計算結果を以下に示す。

    RCB 4‿4
┌─
╵ ⟨ 1 1 1 ⟩ ⟨ 1 2 1 ⟩ ⟨ 1 3 2 ⟩ ⟨ 1 4 2 ⟩
  ⟨ 2 1 1 ⟩ ⟨ 2 2 1 ⟩ ⟨ 2 3 2 ⟩ ⟨ 2 4 2 ⟩
  ⟨ 3 1 3 ⟩ ⟨ 3 2 3 ⟩ ⟨ 3 3 4 ⟩ ⟨ 3 4 4 ⟩
  ⟨ 4 1 3 ⟩ ⟨ 4 2 3 ⟩ ⟨ 4 3 4 ⟩ ⟨ 4 4 4 ⟩
                                          ┘

各リストは順に横方向のグループ番号、縦方向のグループ番号、ブロック分割番号を要素として持つ。

次に4×4の盤面に対するmapを以下に示す。 map はセルが縦、横、ブロックのいずれかの観点から関係を持つかどうか(bool)を全てのセルに対して求めた配列である。 LifeNextでの全セルの近傍存在数の求め方と同じように配列の操作のみで全セルの関係セルを求めている。

    Cmap Rcb ⟨4,4⟩
┌─
╵ ┌─          ┌─          ┌─          ┌─
  ╵ 1 1 1 1   ╵ 1 1 1 1   ╵ 1 1 1 1   ╵ 1 1 1 1
    1 1 0 0     1 1 0 0     0 0 1 1     0 0 1 1
    1 0 0 0     0 1 0 0     0 0 1 0     0 0 0 1
    1 0 0 0     0 1 0 0     0 0 1 0     0 0 0 1
            ┘           ┘           ┘           ┘
  ┌─          ┌─          ┌─          ┌─
  ╵ 1 1 0 0   ╵ 1 1 0 0   ╵ 0 0 1 1   ╵ 0 0 1 1
    1 1 1 1     1 1 1 1     1 1 1 1     1 1 1 1
    1 0 0 0     0 1 0 0     0 0 1 0     0 0 0 1
    1 0 0 0     0 1 0 0     0 0 1 0     0 0 0 1
            ┘           ┘           ┘           ┘
  ┌─          ┌─          ┌─          ┌─
  ╵ 1 0 0 0   ╵ 0 1 0 0   ╵ 0 0 1 0   ╵ 0 0 0 1
    1 0 0 0     0 1 0 0     0 0 1 0     0 0 0 1
    1 1 1 1     1 1 1 1     1 1 1 1     1 1 1 1
    1 1 0 0     1 1 0 0     0 0 1 1     0 0 1 1
            ┘           ┘           ┘           ┘
  ┌─          ┌─          ┌─          ┌─
  ╵ 1 0 0 0   ╵ 0 1 0 0   ╵ 0 0 1 0   ╵ 0 0 0 1
    1 0 0 0     0 1 0 0     0 0 1 0     0 0 0 1
    1 1 0 0     1 1 0 0     0 0 1 1     0 0 1 1
    1 1 1 1     1 1 1 1     1 1 1 1     1 1 1 1
            ┘           ┘           ┘           ┘
                                                  ┘

例えば0‿0⊑mapの配列において値が1となっている添字のセルの集合中に同じ数が2回以上出現するなら添字0‿0のセルにおいてSudokuのルールが守られてないことを意味する。

逆にその中に出現していない数があれば(未割り当てならば)0‿0セルに割り当てることができる。ということでこの操作を実行しているのがmap以降の4行になる。

実行例

    s44 ← 4‿4⥊0‿0‿0‿0‿0‿0‿2‿1‿3‿0‿0‿4‿0‿0‿0‿0
    s99 ← 9‿9⥊∾⟨
      0‿0‿1‿6‿9‿0‿5‿0‿0
      4‿0‿0‿2‿7‿0‿0‿0‿1
      0‿7‿0‿0‿0‿0‿0‿9‿0
      0‿0‿0‿0‿0‿0‿0‿3‿0
      0‿0‿0‿4‿3‿0‿0‿0‿7
      0‿0‿0‿7‿8‿0‿6‿0‿0
      0‿0‿6‿0‿0‿0‿8‿0‿5
      0‿2‿0‿1‿4‿0‿0‿6‿0
      0‿1‿0‿3‿5‿0‿0‿4‿0
    ⟩
    •Show Sudoku s44
┌─
╎ 2 1 4 3
  4 3 2 1
  3 2 1 4
  1 4 3 2
          ┘
    •Show Sudoku s99
┌─
╎ 2 8 1 6 9 3 5 7 4
  4 6 9 2 7 5 3 8 1
  5 7 3 8 1 4 2 9 6
  7 9 2 5 6 1 4 3 8
  6 5 8 4 3 9 1 2 7
  1 3 4 7 8 2 6 5 9
  3 4 6 9 2 7 8 1 5
  9 2 5 1 4 8 7 6 3
  8 1 7 3 5 6 9 4 2
                    ┘

YouTubeにビデオも上がっているけど使い勝手が悪いのでは。

深さ優先探索版

次に、このプログラムをYouTubeのビデオを参考に深さ優先探索アルゴリズムに作り直したものが以下のプログラムである。

Box  ← {>𝕩/<˘𝕩‿∘⥊𝕩/1+↕𝕩⋆2}
RCB  ← {(1+↕𝕩)∾¨Box⊑√𝕩}
Cmap ← {<˘˘1⊑∘∊¨=⌜˜𝕩}

SudokuD ← {
  map ← Cmap RCB ≢𝕩
  Avl ← {(1+↕⊑≢𝕩)(¬∘∊/⊣)0⊸≠⊸/⥊𝕩×𝕨⊑map}
  Nxt ← {w 𝕊 x : (𝕨Avl𝕩){𝕨⌾(w⊸⊑)𝕩}¨<𝕩}
  ans ← ⟨⟩
  {𝕊¨{0<≠p ← (0⊸=𝕩⊸(⊑˜))⊸/·⥊·↕≢𝕩 ? (⊑p)Nxt 𝕩 ; ans ↩ 𝕩 ⋄ !0}𝕩}⎊{𝕤 ⋄ ans}𝕩
}

→ Try it online⌨️

説明

TODO

なお最初の解が見つかった時点でmapを強制に打ち切りたいので、Catch '⎊'を使っている。元々は以下のように終了時の返値用のローカル変数を持たせていたが、関数終了時にローカル定数mapが壊れても問題なかろうということで簡略化した。

  ans ← ⟨⟩
  {𝕊¨{0<≠p ← (0⊸=𝕩⊸(⊑˜))⊸/·⥊·↕≢𝕩 ? (⊑p)Nxt 𝕩 ; ans ↩ 𝕩 ⋄ !0}𝕩}⎊{𝕤 ⋄ ans}𝕩

BQNプログラムに見る深さ優先探索と幅優先探索の対比

TODO: 以下への導出

2つの解法を得ることができたので両者がどれくらい似ているのか比較しよう。編集距離をできるだけ近づけると以下のようになる。

Box  ← {>𝕩/<˘𝕩‿∘⥊𝕩/1+↕𝕩⋆2}
RCB  ← {(1+↕𝕩)∾¨Box⊑√𝕩}
Cmap ← {<˘˘1⊑∘∊¨=⌜˜𝕩}
Avl  ← {map 𝕊 w‿x : (1+↕⊑≢x)(¬∘∊/⊣)0⊸≠⊸/⥊x×w⊑map}
Nxt  ← {map 𝕊 w‿x : (𝕨 Avl 𝕩){𝕨⌾(w⊸⊑)𝕩}¨<x}

SudokuW ← {
  map ← Cmap RCB ≢𝕩
  {𝕊∾{0<≠p ← (0⊸=⊑⟜𝕩)⊸/⥊↕≢𝕩 ? map Nxt(⊑p)‿𝕩 ; map ↩ 𝕩 ⋄ !0}¨𝕩}⎊{𝕤 ⋄ map}<𝕩
}

SudokuD ← {
  map ← Cmap RCB ≢𝕩
  {𝕊¨{0<≠p ← (0⊸=⊑⟜𝕩)⊸/⥊↕≢𝕩 ? map Nxt(⊑p)‿𝕩 ; map ↩ 𝕩 ⋄ !0}¨𝕩}⎊{𝕤 ⋄ map}<𝕩
}

→ Try it online⌨️

ということで、2つの探索アルゴリズムを並べるとご覧の通り。

手法	表現
幅優先	`𝕊∾N¨`
深さ優先	`𝕊¨N¨`

くそ美しいな！ BQNプログラマにとって幅優先はニョロ、深さ優先はチョンチョンなのだ²！

ただし、次に埋めるべきセルの位置は、最初の幅優先探索では状態集合ごとに1回のみの計算で済んでいたものがこのバージョンでは状態毎に（同じ）計算を繰り返すことになってしまっている。ちょっとここは目を瞑って欲しい。

golfの余地

最終版はそれぞれ本体が2行と大変短くなったが全く同じコード片を持つのでなんとかしたい。同じ識別子が2回出現するなんてバカじゃねーの教徒的には。しかし関数の中で親環境の変数に対する代入を行っているので

親を大域変数に格上げするか、
関数閉包生成式をTBC

9.3 SIMD化π計算

Gregory-Leibniz seriesと呼ばれる以下の数列を用いて円周率¹を計算しよう。

\[ \frac{\pi}{4} = \frac{1}{1} - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \frac{1}{9} - \frac{1}{11} + \cdots \]

1回の除算を1回の乗算に置き換えると

\[ \frac{\pi}{4} = \frac{2}{1\times 3} + \frac{2}{5\times 7} + \frac{2}{9\times 11} + \cdots \]

あるいは、monadic ÷の使用による1文字削減を期待して、 \[ \frac{\pi}{8} = \frac{1}{1\times 3} + \frac{1}{5\times 7} + \frac{1}{9\times 11} + \cdots \]

となる。

なお、2行めの変換で項数は半分になる。以下ではこの式に基づいて項を数えることにする。

https://en.wikipedia.org/wiki/Pi, https://ja.wikipedia.org/wiki/円周率

Iverson記法への書き換え

↕n	0項目	1項目	2項目	3項目	一般化
各項の添字	0	4	8	12	`4×↕n`
分母	`×´1‿3`	`×´5‿7`	`×´9‿11`	`×´13‿15`	`{×´1‿3+𝕩}`
項	`÷×´1‿3`	`÷×´5‿7`	`÷×´9‿11`	`÷×´13‿15`	`{÷×´1‿3+𝕩}`

この項列を8×+´すればいいのだから、nを繰り返し上限として、以下のようになる。

pi ← 8×+´{÷×´1‿3+𝕩}¨↕n

ただしこのプログラム化には↕nが大変大きな配列となり実行不能になってしまうという空間計算量の問題がある。そこでリスト上で計算を行い最後にFold '´'するという方法はやめて、（それまでの部分和を更新する）次状態計算関数を繰り返し実行するRepeat '⍟'を使った方法に切り替えることにする。

n ← 1000×1000×1000
pq ← ¯3‿¯1              # 行は引数として渡すのではなく、親環境中に保持
Term ← {𝕩+÷×´pq 4⊸+ ↩}  # 引数として部分和をとり更新された部分和を返す
pi ← 8×Term⍟n 0

→ Try it online⌨️

SIMD命令を使った高速化

完成したプログラムはnに関わらず実行できるがリストを使ってないためSIMD命令を使った高速化の余地がない。そこで妥当な長さのリストを使って空間計算量の問題を起こすことなく高速化しよう。

n‿chunk ← ⟨1000×1000×1000,1000⟩
seed‿span ← ⟨3+4×↕chunk,4×chunk⟩
sum ← 0
Term ← {
  diff ← +´{÷×⟜(¯2⊸+)}¨𝕩+seed
  sum diff⊸+ ↩
  𝕩+span
}
Term⍟(n÷chunk)0
pi ← 8×sum

→ Try it online⌨️

BQNでは配列はimmutableなので計算結果は毎回割り当てられることになるが、その計算の基となるリストseedは再利用したいので親環境で定義している。

これでおよそ5倍の高速化になる。しかし、実はこれはまだ十分に並列化できていない。5行目の明示的なEachをやめて以下のように変更する。

--- pi-simd0.bqn        2023-06-21 21:40:58
+++ pi-simd.bqn 2023-06-21 21:40:51
@@ -2,7 +2,7 @@
 seed‿span ← ⟨3+4×↕chunk,4×chunk⟩
 sum ← 0
 Term ← {
-  diff ← +´{÷×⟜(¯2⊸+)}¨𝕩+seed
+  diff ← +´÷×⟜(¯2⊸+)𝕩+seed
   sum diff⊸+ ↩
   𝕩+span
 }

すると更に8倍速くなる。下のプログラムから40倍以上の高速化を実現できたということでrayonを使ったrustプログラム²にわずか2倍程度しか遅くないという速度を得ることができた。 Foldはどうしても逐次処理になってしまうのでできるだけ避けるべきであるというのはわかるが、なぜだかrank多相を使ってEachも避ける方がよいという結論になってしまった。

$ time cbqn pi-simple.bqn
Error: Out of memory
pi-simple.bqn:2:
  •Show pi ← 8×+´{÷×´1‿3+𝕩}¨↕n
                            ^
cbqn pi-simple.bqn  0.01s user 0.00s system 87% cpu 0.015 total
$ time cbqn pi-repeat.bqn
3.1415926445762157
cbqn pi-repeat.bqn  92.21s user 0.06s system 99% cpu 1:32.43 total
$ time cbqn pi-simd0.bqn
3.1415926530824487
cbqn pi-simd0.bqn  17.73s user 0.01s system 99% cpu 17.750 total
$ time cbqn pi-simd.bqn
3.1415926530824487
cbqn pi-simd.bqn  2.58s user 0.01s system 99% cpu 2.587 total

当然--release付き

golf

上記のプログラムを短くしよう。元々の実行可能なプログラムが4行だったので対比しやすいようそれに合わせて書き換えると以下のようになる。

n‿chunk ← ⟨1000×1000×1000,1000⟩
span‿seeds ← ⟨chunk×4,3+4×↕chunk⟩
Term ← {⟨𝕨++´÷×⟜(¯2⊸+)𝕩+seeds,𝕩+span⟩}     # 添字と部分和のペアに対する繰り返し実行
pi ← 8×⊑Term´⍟(n÷chunk)0‿0

→ Try it online⌨️

これでプレゼンテーションの1枚のシートに上下並べて2つのバージョンを載せることができるようになった。 APL（語族）を使うならこうでなければ。

9.4 最短経路探索問題

Dijkstraのアルゴリズムやその改良版である\(A^{*}\)アルゴリズムはヒープが必要であり、道具立てが大変なので、 APL界隈ではBellman-Fordアルゴリズムが好まれるようだ。 Advent of Codeに限れば、毎年のように最短経路探索問題に帰着する問題は出ているものの、これまで負の重みが与えられたことはないので、非負の重みのみに簡単化した Bellman-Fordのアルゴリズムを実装すればよい。この場合、アルゴリズムは辺を追加しながら全てのノード対に対する総コスト表を繰り返し更新するという極めて見通しのよいものになる。

ここで、始点終点対\((a, b)\)が点\(c\)を経由する際のコストの最小値は

  {𝕊 a‿b : ⌊´{𝕊 c : (a‿c⊑w)+(c‿b⊑w)}¨nodes}

と表せるが、これを従来の記法で書けば \[ \min_{i} w(a,c_i) + w(c_i, b) \] であり、行列積\(W \times W\) \[ \Sigma_{i} w(a,c_i) \times w(c_i, b) \] との類似が見て取れる¹。従ってBQNcrateにある配列積のコードm +˝∘×⎉1‿∞ nを利用して以下のようになる。

    # 以下はwikipediaでのDijkstraアルゴリズムの項で使われている問題例
    edges ← [
      ⟨0,1,7⟩,⟨0,2,9⟩,⟨0,5,14⟩
      ⟨1,2,10⟩,⟨1,3,15⟩
      ⟨2,3,11⟩,⟨2,5,2⟩,⟨2,5,14⟩
      ⟨3,4,6⟩
      ⟨4,5,9⟩
    ]
    d ← ([0,∞]⊸(⊑˜)∘¬=)⌜˜↕ n ← 1+0(1⊸⊑⊸⌈)˝edges
    •Show d ↩ d {i‿j‿w 𝕊 𝕩 : w˙⌾(j‿i⊸⊑)w˙⌾(i‿j⊸⊑)𝕩}˝edges

    SmallestCost ← (⌊˝∘+⎉1‿∞)˜
    •Show SmallestCost⍟(⌈2⋆⁼n)d    # 再帰的に経路を追加するので log n 回で不動点

→ Try it online⌨️

ただし、これではコストのみしかわからない。実際の経路も必要なら以下のようになる(これは少し苦労した)。

    Shortest ← {𝕊 m‿p :
      q ← (m⋈¨p)⋈¨∾¨˝⍉m(+⎉1‿∞)m
      ⟨(⌊´1⊸⊑)¨q,{(1⊑⊑𝕩)>⌊´1⊑𝕩 ? ⊑⍋1⊑𝕩 ; 1⊑⊑𝕩}¨q⟩
    }
    route ← 1+1⊑Shortest⍟(⌈⋆⁼2)d‿(∞¨d)
    # startからendに行くには以下が最小コスト列
    Traverse ← {r T start‿end :
      m ← ((-¬)¨start‿end)⊑r    # 次に選ぶべきノード
      {⊑m∊⟨start,end⟩ ?         # 始点または終点なら直接遷移可能
        ⟨start,end⟩
       ;
        (r T start‿m)∾1↓(r T m‿end)
      }
    }

→ Try it online⌨️

Bellman-Fordという名前を知らなくてもこの形の計算には見覚えないだろうか。到達可能性とかEigenTrustだとかの、よくあるグラフの特徴量算出式そのものだ。

9.5 配列指向プログラミングの限界

空間計算量がなんともならん！という話を何か実例を使って。

あるいはどうやれば高速なプログラムが書けるかと言う話

in-place updateは必須
しかし引数をin-place updateできるか?
場合によっては対応手法を使う事が必要

と言う話を以下の数値を使っていつか書く予定。

in-place update必須

    l ↩ l∾π

    l ∾⟜π ↩

in-place updateになってない場合

    l ∾⟜(⊑l) ↩

引数として使われるsubjectのin-place update問題

    F ← {l‿k : l ∾⟜(k⊑l) ↩ ⋄ ⟨l,k+1⟩}

`•_while_`が絡んだ引数問題

    x ← 1⊑{k‿l : l ∾⟜(k⊑l) ↩ ⋄ ⟨k+1, l⟩}•_while_(100>⊑)0‿⟨⟩

パターンマッチングが絡んだ引数問題

名前空間によるカプセル化(singleton化?)

!⟜(start_length⊸≡) ≠l ← start_length↑π
"update lst" util.Debug {{c‿m : l ↩ l∾π ⋄ ⟨c+1,m⟩}•_while_(𝕩>⊑)0‿⟨⟩}•_timed updates
!⟜((start_length+updates)⊸≡) ≠l
l ↩ start_length↑π
"in-place -" util.Debug {{c‿m : l ∾⟜π ↩ ⋄ ⟨c+1,m⟩}•_while_(𝕩>⊑)0‿⟨⟩}•_timed updates
!⟜((start_length+updates)⊸≡) ≠l
l ↩ start_length↑π
"update arg" util.Debug {l ↩ 1⊑{c‿l : l ↩ l∾π ⋄ ⟨c+1,l⟩}•_while_(𝕩>⊑)0‿l} •_timed updates
!⟜((start_length+updates)⊸≡) ≠l
l ↩ start_length↑π
"in-place -" util.Debug {l ↩ 1⊑{c‿l : l ∾⟜π ↩ ⋄ ⟨c+1,l⟩}•_while_(𝕩>⊑)0‿l} •_timed updates
!⟜((start_length+updates)⊸≡) ≠l
l ↩ start_length↑π
"in-place 2" util.Debug {l ↩ 1⊑{c‿l : ⟨c+1,l∾π⟩}•_while_(𝕩>⊑)0‿l} •_timed updates
!⟜((start_length+updates)⊸≡) ≠l
l ↩ start_length↑π
"wrap in ns" util.Debug {l ↩ {𝕩.vec}1⊑{c‿w : w.Add π ⋄ ⟨c+1,w⟩}•_while_(𝕩>⊑)0‿(List l)} •_timed updates
!⟜((start_length+updates)⊸≡) ≠l

m ← Longlist 100000
{m.Add π ⋄ 𝕩+1}•_while_(start_length⊸>)0
!⟜(start_length⊸≡) m.Size@
"indirect -" util.Debug {m ↩ 1⊑{c‿m : m.Add π ⋄ ⟨c+1,m⟩}•_while_(𝕩>⊑)0‿m} •_timed updates
!⟜((start_length+updates)⊸≡) m.Size@

#  - update lst: 6.697469000000001
#  - in-place -: 0.0014390000000000002
#  - update arg: 6.643209000000001
#  - in-place -: 6.647899000000001
#  - in-place 2: 6.660026
#  - wrap in ns: 0.0029370000000000004
#  - indirect -: 0.002893

init size/iteration/samples: ⟨ 1 200000 10 ⟩

#	code	time (sec.)
1	`{c‿m : l ↩ l∾π ⋄ ⟨c+1,m⟩}•_while_ (𝕩>⊑) 0‿⟨⟩`	3.3718565
2	`{c‿m : l ∾⟜π ↩ ⋄ ⟨c+1,m⟩}•_while_ (𝕩>⊑) 0‿⟨⟩`	0.0122643
3	`l ↩ l{𝕩 ↩ 𝕩∾π ⋄ 𝕩}´↕𝕩`	3.2780491
4	`l ↩ l{𝕩 ∾⟜π ↩ ⋄ 𝕩}´↕𝕩`	0.0053715
5	`l ↩ 1⊑{𝕩 ↩ 𝕩∾π ⋄ ⟨𝕨+1,𝕩⟩}´•_while_ (𝕩>⊑) 0‿l`	3.4005579
6	`l ↩ 1⊑{𝕩 ∾⟜π ↩ ⋄ ⟨𝕨+1,𝕩⟩}´•_while_ (𝕩>⊑) 0‿l`	0.0091961
7	`l ↩ 1⊑{w‿x : x ∾⟜π ↩ ⋄ ⟨w+1,x⟩}•_while_(𝕩>⊑) 0‿l`	3.3545225
8	`l ↩ 1⊑{⟨𝕨+1,∾𝕩._modify π⟩}´•_while_(𝕩>⊑) ⟨0,Ref l⟩`	0.0139621
9	`l ↩ 1⊑{⟨𝕨+1,∾𝕩._modify π⟩}´•_while_(𝕩>⊑) ⟨0,Ref l⟩`	0.0176845
10	`l ↩ (Ref l){∾𝕩._modify π}´↕𝕩`	0.0102602

substitute list object
in-place update object
subst. arg in fold loop
in-place arg in fold loop
subst. arg in •while
in-place arg in •while
in-place args in •while
Ref._modify arg in while
Ref._modify args in while
Ref._modify arg in fold

BQNの始め方 -- How to start BQN in Japanese

同じ形状の二つのリストからCouple '≍'で配列を構成する

Table '⌜'を使って二つのリストの外積𝔽⌜として生成する

Deshape/Reshape '⥊'による変形

同じ形状の二つのリストから Couple '`≍`'で配列を構成する

Table '`⌜`'を使って二つのリストの外積`𝔽⌜`として生成する

Deshape/Reshape '`⥊`'による変形