# ScalaMatsuri 2024 立案

## 冒頭の branching 紹介

冒頭で branching について話すときには、
- javac
- 分岐判断に必要な情報をスタックから取る (例: `if_icmpeq $label`)
- x86
- 分岐判断に必要な情報をフラグから取る (例: `JE $rel16_offset`)
- JMP 命令族は Jcc 命令族 (condition code に基づいたジャンプ命令族) とは全く別の命令族である。JMP 命令族は様々な指定ができ、computed jump (実行時に決まるジャンプ先) を実現できるが (例: `JMP r/m16`)、Jcc 命令族には rel8/rel16/rel32 の相対オフセットしかジャンプ先に指定できない。
- https://www.felixcloutier.com/x86/jmp
- https://www.felixcloutier.com/x86/jcc
- ~~MIPS~~ RISC-V
- 分岐判断に必要な情報をレジスタから取る (例: `beq $s1, $s2, $label`)

の 3 例で挙げるのがよさそう。

このきれいな 3 対比によって、そこを abstract out させ、共通である "the branching operation is an act of extracting some information out of the machine's state and choosing whether to jump" というコンセプトに聴衆を集中させることができるからである。

## たたき台となるコード

https://scastie.scala-lang.org/8f6Qq7k8TxSVCefUjPeFqg

## 想定する聴衆の前提知識は？

- (Goal - 40 minutes) で定めるというズルもある

1. do 構文 (for 式) で monadic な値を合成したことがある \[MUST\]
2. do 構文 (for 式) がどう desugar されるかを想像できる \[WANT\]
3. 典型的な「アセンブリ言語・機械語・CPUの三つ組み」について噂レベルで聞いたことがある \[強いWANT\]
- ~~javap でも可~~
- ~~"For those who've never x86'ed, don't worry: *javap* can satisfy the requirement for this course."~~
- javap のみを使うから javap の出力を見たことがあるとベター　無くても良い
4. データ型による概念のモデリング（まあこれは ScalaMatsuri に来ている人なら仮定できる）
- 結構強い仮定ではあるが、これを仮定せずにこの発表はできない
6. 型クラスへの理解
- 関連型まで soft に仮定する必要がありそう (説明はする)
- Rust の trait を知っていればもうそれでいい
7. callback API を呼び出したことがある

## 持っててほしい空気

- そもそもこの分野を探索するモチベーションとして、次のようなことを把握してほしい (別にモチベーションとか知らんから Eff の作り方を教えてくれという人にはちょっとだけ我慢してもらおう)
- 「プログラムとは、実行によって発生する作用に対する期待を書き下したものだ」
- 「『作用への期待』を合成するというプログラミングスタイルには様々なメリットがある」
- 「『作用への期待』を合成する非常に強力な下地として extensible effects というプログラムのモデルがある」
- 「extensible effects という仕組みを学ぶことで、小さなプログラムを値として扱って合成するというテンプレパターンへの理解度が高まる」
- 「これが高まっていると、『メタプログラミングのおかげでできる操作』についての直観が生えて、そういうプログラミングをするときに活きる」

## prerequisite かと思いきや実は要求しなくていい

- Control Flow Graph を前提にしたくない → 実際要らない
- CPS を仮定できないので教えなきゃいけない？
- ~~→ CPS の直観だけ分かってればいい~~
- CPS 変換可能性みたいなことは説明しないで良い
- そもそも CPS 自体前面には出てこない (アセンブリ上の branching 構造に全てが帰着されて自然に出てくる)
- 「機械語を実行する機械の仕組み」→「目の前の命令とその後すべてという二分法」でプログラムのモデルを正当化できる

## 達成したい「柱」

- 表向きには…
- ~~Eff の背景にある概念をなぞり、それらを「原理」として据えることで、Eff のデザインを理解し、自分で簡単な Eff の実装を作るための知識を身に着けてほしい~~
- Eff を捉えるためのかなり斬新な道筋を紹介し、それをともに辿ることで、**Eff のデザインを理解し、自分で簡単な Eff の実装を作るための知識を身に着けてほしい**。
- 裏テーマとして…
- Eff (のよくあるエンコード) の裏に隠れているプログラミング言語理論的な背景、および (「純粋関数型命令型メタプログラミング」と言って差し支えない) 関数型プログラミングパラダイム内での Eff の立ち位置を理解し、Eff を利用したプログラムを書く時の支えにしてほしい
- また、この理論的な理解を道具立てとすることで、Eff のナイーブな実装が抱える本質的な問題 (特に、higher-order effect、スタックトレース、handler探索等による計算量的問題の三つ) を理解し、これらを克服するにはどのような手段を取り得るのかという active area of research に立ち向かえるようになって欲しい
- これをスコープに入れるのは普通に厳しい説が出てきた
- 一方、この講演で語られた理論的な Eff の構成の解釈はこういった active area of research に立ち向かうにあたって普通に有用なんで、単に道具として受け取ってほしいな、という想いは残り続ける
- 最後にサラッと触れて参考文献を挙げておいてあげるくらいが落としどころかな～ (論文で言う related work)
- 「この拡張性によって失われたものもある (e.g. stack trace, fibre [e.g. atomic reference], higher-order effects [e.g. try-catch, fork]) から、cats.effect.IO や fs2.Stream などより真に優位であるというわけでは無いことに注意してほしい、詳細はうんたらかんたら」

- Eff (Freer Monad) の「物質界的」な直観へ至る道筋を紹介し、Extensible Effect が abstract nonsense であるという幻想を破壊する
- さらに、その直観を用いたプログラミングができるようになってほしい

## 関連

- GADTs によって「命令を表す ADT にその命令の戻り値型をタグ付けできる」ことを理解してもらう
- GADT 一般の話を理解してもらう必要は (そんなに) ない
- 実のところ、言語機能の話をしたいわけではないので、「GADTs」という名前を出す必要もそんなにない
- コンパイラ屋さんが頑張っているので GADTs というのが Scala では普通に書けますが、何か？くらいの顔をして良い
- 小さい文字で「ちなみにコンストラクタが型変数の一部を決め打ちで具体化するような直積の直和で書かれたデータ型のことを GADTs と言います☆」くらいに書くのはアリ (後で検索したい人向け)

## 達成しなければいけないマイルストーン
- movfuscator と万能命令（オペランドが異常にリッチでありそちらに押し付ける、という発想）

## 雑メモ

### 冒頭で使えそうなネタ
- Let me start with a *very* simple question:
- "Why did the chicken cross the road?"　→ "To get to the other side."
- Okay, that was an easy one.
- Now, onto the next question:
- "Why did you write code?" → "To cause effects."
- …という話が「effects とは何であろう？」という疑問の切り口として使える

### スケルトンに名前がほしい
- hsjoihs「Program マイナス OpCode に名前がほしい。OpCode によって populate されるべきスケルトンに名前がほしいのだ」
- Kory「あー、『木構造』みたいなレイヤの名前が」
- hsjoihs「知り合いに古典ギリシャ語ができるやつがいるから、ちょっと名前考えてもらうよう頼むか」
- Kory「TreeWithTypedBranching とかは思いつく」
- みとみとみっとんから納品されたもの：
- ***ephictozon*** ("having accessible branches") < *ephict-* ("easy to reach, accessible, attainable") + *ozos* ("branch, twig")
- ***ephorozon*** ("overseeing branches") < *ephor-* ("to oversee") + *ozos* ("branch, twig")

### CPU アーキテクチャの直和分解周りの話
- RISC-V standard extensions
- https://gist.github.com/dominiksalvet/2a982235957012c51453139668e21fce
- FPU emulation 周り
- https://qiita.com/hnw/items/8703a0e776f8b6a60b45#%E3%82%AB%E3%83%BC%E3%83%8D%E3%83%ABfpu%E3%82%A8%E3%83%9F%E3%83%A5%E3%83%AC%E3%83%BC%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%A8soft-float
- https://zenn.dev/tetsu_koba/articles/c29e18f6d2eeb2

## 構成検討

1. モチベーションの説明・オリエンテーション
1. JVM バイトコードの軽いおさらい (?)
1. アセンブリのモデル化から始めて、「終了コード付き実行可能形式」のモデルにまで行きつく
- ここまでのクリティカルパスはこんな感じ 
- これを Scala のコードに落とすとこんな感じ

      // 命令セットの例
      enum Instruction1[BranchIndex]:
        case JmpNat() extends Instruction1[Int]
        case PushStack(value: Int) extends Instruction1[Unit]

      enum ExecutableWithInstr1[ExitCode]:
        case Exit(code: ExitCode)
        case NonEmpty[BranchIndex, ExitCode](
            headInstr: Instruction1[BranchIndex],
            branches: BranchIndex => ExecutableWithInstr1[ExitCode]
        ) extends ExecutableWithInstr1[ExitCode]

1. 命令セットを動かせるように一般化する

   enum Executable[Instruction[_], ExitCode]:
     case Exit[I[_], EC](code: EC) extends Executable[I, EC]
     case NonEmpty[I[_], BranchIndex, EC](
         headInstr: I[BranchIndex],
         branches: BranchIndex => Executable[I, EC]
     ) extends Executable[I, EC]

1. `injectAtExits` と `transpile` という、`Executable` 自体に対する操作を紹介・定義する

   def injectAtExits[I[_], A, B](
       program: Executable[I, A],
       selectNext: A => Executable[I, B]
   ): Executable[I, B] =
     program match {
       case Exit(exitCode) =>
         selectNext(exitCode)
       case NonEmpty(headInstr, branches) =>
         NonEmpty(
           headInstr,
           branchIndex => injectAtExits(branches(branchIndex), selectNext)
         )
     }
   
   def transpile[I1[_], I2[_], ExitCode](
       program: Executable[I1, ExitCode],
       expand: [A] /* "forall type A", */ => I1[A] => Executable[I2, A]
   ): Executable[I2, ExitCode] =
     program match {
       case Exit(exitCode) => Exit(exitCode)
       case NonEmpty(headInstr, branches) =>
         injectAtExits(
           expand(headInstr),
           branchIndex => transpile(branches(branchIndex), expand)
         )
     }

1. 命令セットの直和分解と、それを利用した staged transpilation, 及び、最終ステップに現れる `compactify` という操作
- compactify といえども実際に情報を圧縮しているのではなく、プログラム全体を単一の可変長命令に押し込むような操作をしている。`repackage` に近い。
- staged transpilation で単一の、他の命令をすべてエミュレートできる命令にすべてをトランスパイルするという状況は、movfuscator とやっていることが似ている
- ところで、`Executable[I, EC]` は間接アドレッシング（実行時にジャンプ先が決まる goto）入りの `I[_]` をモデリング出来ないので、movfuscator はその抽象から若干外れそう
- 伝えたいことは次の図みたいな感じ
- まず、次の型クラスを定義する

      trait Decompose[SubInstruction[_], Instruction[_]] {
        type Complement[_]
        def split[A](instr: Instruction[A]): Either[SubInstruction[A], Complement[A]]
      }


- `Decompose` は、命令を表すデータ型を decompose するためのものだった。**双対的に**、命令を表すデータ型を compose するものとして `mix` (`EitherK`) を定義する。

      case class EitherK[F[_], G[_], A](value: Either[F[A], G[A]])
      infix type mix[F[_], G[_]] = [A] =>> EitherK[F, G, A]

- これが如何なる意味で「命令を表すデータ型を compose しているのか」というと、普通に、`enum F[_]` の定義と `enum G[_]` の定義を連接した (i.e. 二つの `enum` の `case` を愚直にかき集めてベタっと書き直した)ような `enum FG[_]` と等価になっている。これを例を通して納得してもらうのが良さそう。

- 「compose した命令を decompose するような」`mix` への `Decompose` インスタンス導出を書く　実装は省略 (`Executable.single` は後でも使う)

      object Executable {
        // ...

        def single[I[_], A](instruction: I[A]): Executable[I, A] =
          Executable.NonEmpty(
            instruction,
            branchIndex => Executable.Exit(branchIndex)
          )
      }

      object Decompose {
        given leftLeaf[Instr[_], RightI[_]]
          : Decompose[Instr, Instr mix RightI] with {
          type Complement[X] = RightI[X]
          def split[A](instr: (Instr mix RightI)[A]): Either[Instr[A], RightI[A]] = instr.value
        }
      
        given rightLeaf[Instr[_], LeftI[_]]
          : Decompose[Instr, LeftI mix Instr] with { ... }
      
        given composeLeft[Instr[_], LeftI[_], RightI[_]](
          using m: Decompose[Instr, LeftI]
        ): Decompose[Instr, LeftI mix RightI] with {
          type Complement[A] = (m.Complement mix RightI)[A]
          // ...
        }
      
        given composeRight[Instr[_], LeftI[_], RightI[_]](
            using m: Decompose[Instr, RightI]
        ): Decompose[Instr, LeftI mix RightI] with { ... }
      }

- 二つの重要な関数を紹介する

      def eliminateSubinstruction[Eliminatee[_], Source[_], ExitCode, Target[_]](
          program: Executable[Source, ExitCode],
          expand: [A] => Eliminatee[A] => Executable[Target, A]
      )(using
          decomposition: Decompose[Eliminatee, Source] { type Complement[A] = Target[A] }
      ): Executable[Target, ExitCode] =
        transpile(
          program,
          [A] =>
            instr =>
              decomposition.split(instr) match {
                case Left(subInstr)    => expand(subInstr)
                case Right(complement) => Executable.single(complement)
            }
        )
      
      import cats.Monad
      import cats.syntax.all.*
      
      def compactify[Instruction[_]: Monad, ExitCode](
          program: Executable[Instruction, ExitCode]
      ): Instruction[ExitCode] =
        program match {
          case Exit(exitCode) => Monad[Instruction].pure(exitCode)
          case NonEmpty(headInstr, branches) =>
            headInstr.flatMap(branchIndex => compactify(branches(branchIndex)))
        }

1. TODO: 実際のプログラミングにこのモデルを応用するにはどうするのが良いか？というのを話す (`MemberIn` 型クラスを利用した、`Instruction[_]` を抽象化したプログラミング)
- 「君のどこが Extensible なの？？？」の説明に不可欠
- ここで、次のような話を (もちろん、適切に希釈して) しても良いかもしれない… 「ここまでの我々は、アセンブリの命令がアセンブリの静的なプログラムの文法上持つであろう制約をあぶり出すことのみで `Executable[I, EC]` というモデルにたどり着いている。命令とは、文法上は単なる終端記号に過ぎない。しかし、命令を「単なる終端記号」として取り扱うのは勿体ない。命令には、「命令」という語から読み取れるように、プログラマと機械の間の一種の契約であるという意味が込められている (尤も、機械はプログラマが放り込んできた命令列を粛々と実行しないといけないから、極めて不公平な契約ではあるが…)。この立場から考えれば、「命令セット」とは、機械が如何なる命令を受け付けられるのかを事前に教えてくれているものでもある。
- なので、「アプリケーションロジックがプログラムの文法上特定の命令を実行することができると仮定すること」(not explained clearly yet)は、「そのプログラムを実行する機械に一定の能力を期待していること」に他ならない。この、「アプリケーション内に記述される命令」が持つ役割の言い換えが、`Executable[I, EC]` をどう扱うと良いかについて非常に良い指針を与えてくれる。」
- 特に、実際には `Member` から `include` のみを抜き出した `MemberIn` クラスによって命令セットに制約を加えることでアプリケーションロジックを書くことができる。命令セットに `MemberIn` 制約を加えることは、プログラムという文法構造を通して、それを実行する機械に capability を (極めて間接的な形で) 要求することに相当する。
- ちょうど、この間読んでいた「圏論による論理学」の§1.5†には、「記号は本来的にその意味 (i.e. 被指示者) を伴っている．そしてこのことは，どのような場合にもいえることであり，記号自身以外に特に何も見当たらない場合でも成立する．ではそのような場合，その記号が指示する被指示者はいかなるものであろうか．答は，当の記号自体である，といえる．(p. 51)」という一節があり、我々がここまで取ってきた「文法上は単なる終端記号に過ぎない」という立場は、まさにこの終端記号の「記号自身を指示する」という最も (literally) literal な形での記号の意味に注目したものであると言えるだろう(?)。
- TODO: ↑の話をここでしようと考えていたが、実は `eliminateSubinstruction` の時点で「意味」についての話を一定している。「今までは命令の文法的機能についてのみ考えていましたが、機械がこれをどのように解釈すればよいのかという「意味」について考えつつ、次の手を考えましょう」という話をしたいのであれば、`eliminateSubinstruction` よりも前にするべきかもしれない。

## dump 置き場

### `MemberIn` (`Include` に改名予定) 型クラスをなぜ導入しないといけないか？

- Extensible Effects を実際のアプリケーションで使うときにすることは、
- アプリケーション内で起こる、アプリケーション固有のプリミティブな操作に対応するインストラクションを作ります
- e.g. 掲示板で request と DB の橋渡しをするサーバーにおいては、
- まず、Eff のプログラムがどのようなライフサイクルで実行されるかを、アーキテクトは考える必要がある。
- アプリケーションと同じライフサイクルで走り続けるのか、
- リクエストに返答しきるまでのライフサイクルなのか、
- デコードが完了してエンコード対象のレスポンスオブジェクトを作るためのところまでのライフサイクルなのか、
- これを決めないと話が始まらない。
- 一番最後のケースを考えよう。するとまず何をするかというと、「リクエスト内容」というのを、プログラムへの入力（環境値）として参照する必要があります。リクエストを一発で取ってくる（取ってこない場合もあり、そこにはデザインスペースがある。リクエストオブジェクトを取ってくるでもいいし、「ヘッダを取ってくる」と「\[⌛]を取ってくる」があってもいい。）結局は、どんなのが飛んできたのかを知らないとプログラムはなにもできないので、それに関する命令は必要です。
- 現在時刻を読む必要があるので、「いま何時？」を一発で返してくれる命令が必要です。
- この必要はないかも。というのも、persistence backend に書き込むタイミングで時刻データを取得してそれも送ればいいだけだから、「現在時刻を読む命令」は、「この板のところに、【いま】この書き込みがあった」という命令に subsume される
- これ以上のバリデーションが要らない場合を考えると、あとは 【DB というか persistence backend に「この板のところに、この時間に、この内容の書き込みがあった」という出力を書き込む】という命令が必要。
- 命令セットが、以上の 2 つの命令をサポートすることさえできれば、その命令セットの上の Executable においては、今回の案件は
- 「来たリクエストから書き込み内容を抜き取って」
- 「persistence backend に送る」
- という 2 つの命令のみを持つ Executable で済む。
- これが Initial design
- 少なくとも、`eliminateSubInstruction` and `compactify` に載せるためには、単一の非常に強力な命令が必要なのであった。先ほど考案した 2 つの命令は、全然強力ではない。Functor ですらない。そもそも直交している。全く無関係な 2 命令であるため。そもそも eliminateSubinstruction で片方を片方につぶすことなどできるはずがない
- つまり、仮に eSI & compactify の上にこのプログラムを載せるのであれば、一番最初に eSI の前のもともとの命令セットの時点で「この 2 つとは異なる万能命令」が入っていなければならないことを示唆しています
- 「いなければならない」というのは、「万能命令が最初から入っていないと、【そこにすべてを transpile して帰着させる】ということができない」という意味
- eSI の受け皿である万能命令を一番最初に用意しておかねばならない
- 仮に、staged transpilation で「persistence backend に送る」という命令を
- α「現在時刻を読む」という命令と
- β「現在時刻とメッセージと板の情報を triple として p ba に送る」という命令
- に分解することにした場合、この 2 つの命令 (α, β)も初期命令セットに含んであげないといけない
- この問題を総括すると、初期命令セットが、それをどう transpile するかという後続の事情に引っ張られてしまうことになる。【一切の transpile をするよりも前の Executable】にはたった 2 つの命令しか現れないというのに。
- このモデルの上で application logic として命令セットを 1 回固定してしまうと、後続のその executable をどう transpile するかという無関係な都合によって命令セットがコロコロ変わることになってしまう。
- 一般に、application 内部のコードは、「そのコードがどう実行されるか」という外部事情に引きずられて変更を強いられるべきではない。
- 以上が、problem statement

- 理想形がどのような形であるかを考える
- アプリケーションの内部、コアロジックでは、コアロジックの関数のシグネチャに、その関数が使う subinstruction しか現れない

- その理想と現状にはどういうギャップがあって、どう解決できるのか
- ギャップは前述の problem statement のとおり
- （todo）

- 解決策は 2 つ
- 1 つは、今回の講演の内容に関しては、上手く行きます
- その先のところで詰むことを僕は知っています
- もしかして：暗黙知
- どういう選択肢があるか？
- 後で詰むやつの話をまずする。

#### 選択肢1

- 選択肢1としては、
- アプリケーション内部では、application code 内で必要な subinstruction だけをシグネチャに書いて、executable を実行するときに、その小さな subinstruction を「実行に必要な全部の instruction set に埋め込む」ような include 操作をする。それをして、
- 「app 内部では小さな subinstruction で書けている」
- 「edge of the world で、実行に必要な命令セットをガサっと持ってきてドメイン固有の命令を埋め込んだうえで、eliminateSubInstruction & compactify をする」

を両立させる
- なお、eSI + compactify は使わなくてもいい。application 内部で固定して、なんなら application のそれぞれの部分でバラバラの固定の仕方をして、edge of the world でいい感じに統合するという方法もある

##### 選択肢1の問題点①（簡単なほう）

application-core logic から edge of the world の間には、基本的に複数のレイヤがあって、最後に edge of the world に繋がっているという構造をしているはずである (cf. The clean architecture)。「ここがひっくり返ると外側も必然的にひっくり返る」という形に整理しておくと、必然的にそういう多段構造が生まれる。
- 強い主張だが、ある程度の system architect なら同意してくれるだろう

この構造を踏まえたとき、edge of the world と application-core logic の真ん中ぐらいにいる、core logic 群を協調動作させるような抽象層は、より小さな subinstruction をちょっとずつ合成する (複数の core logics が使っている subinstruction たちを cover するような最小の instruction set を新たに作る) 必要がある。

ところで、`EitherK` を使った formulation は instruction set を subinstruction の木に分解していた。一方で、「subinstruction たちを cover する最小の instruction を作る」という操作は、まさに集合論的和 (union) である。木という余分な情報が入ったまま sub instruction たちを扱っていると、union を取るときの組み替え方が非自明になる (特に、subinstruction 達に順序が入っていないから、OrderedSet のように扱うこともできない)。理想としては、instruction set = set of subinstructions というモデルでやっていきたい。ところで、subinstruction の enum variant に実行時タグがついているというのは (transpilation をするにあたって) 重要な性質であるのだが、instruction set = set of subinstruction のモデルではそのような実行時タグが (少なくとも naive には) 得られず、困る。

1 個めの問題点をまとめると、「subinstruction の合成という操作を行うために、本来 instruction set = subinstruction の set として扱っていきたいのだが、subinstruction の実行時 tag を残さないといけないという都合と両立させようと思うと、bookkeeping が大変になる。（大変であるだけであり、不可能ではない。本質的な問題ではない）」

##### 選択肢1の問題点②（難しいほう）

\[こりーさんから【cats.effects.IO と実行時タグと uncancelable、および https://github.com/kory33/recursive-eff-experiments 】に関する 1 時間の講習を受けた後でお読みください]

\[要点としては、cats.effects.IO は「ASTノード」がリッチだが、Eff には 1 つしかなく、それをかいくぐろうと【プログラム自体を引数として持つ instruction】(HOE) でこなそうとすると、再帰型が発生し、Scala では書けないはずだが、こりーさんはコンパイラの既知の秘孔を突いてそれを実装した (参考: [Scala 3 で一般の再帰型を作る](https://qiita.com/Kory__3/items/278505527d530545be5e))\]

- 先ほどのような、operand に Executable 自体を取るような opcode のことを、 higher-order effect (HOE) と呼びます。
- application 内部で、【小さな命令セットを固定する】というモデルと、HOE の相性が、致命的に悪い。
- なぜかというと、
- operand に入っているプログラムの instruction というのは、【ParBoth という instruction を含む、最終的に edge of the world に渡される大きな命令セット】である必要がある
- ゆえに、application 内部で HOE を利用しようとすると、必然的に【最終的に edge of the world に渡される大きな命令セット】に言及する必要が発生する。
- よって、【application 内部で小さな命令セットだけに言及すればよい】というのは、HOE がない状況では「bookkeeping が大変」、で済んだが、HOE が入った瞬間、完全に崩壊する

##### 問題点のまとめ

選択肢 1 は、今回のトークの範囲では上手く行くが、それを拡張して、例えば Promise.all だったり uncancelable だったりがほしくなったときに致命的に破綻する。

これはここ 7 年ぐらいの active area of research で、この問題はそのころから認知されている。

#### 選択肢 2

「アプリケーションの内部、コアロジックでは、コアロジックの関数のシグネチャに、その関数が使う subinstruction しか現れない」という理想と、problem statement で述べた状況とのギャップを埋める方法は、もう一つある。

アイデアは比較的簡単で、
- プログラム全体を通して、使う命令セットというのは固定します
- しかし、アプリケーション内部では、この命令セットを型変数にしておく
- そして、「この命令は要る！」という型クラス制約をつける

これにより、先ほど述べた問題が全て解決する。なんと HOE もこれで解決する。

具体的には、次のような `Include` 型クラスを定義する

trait Include[SubInstruction[_], Instruction[_]] {
  def include[A](instr: SubInstruction[A]): Instruction[A]
}


メンバ関数という形で、「include できる」という条件だけを指定する

これを用いて、アプリケーション内部の core logic を、例えば次のように記述する。

def acceptRequest[Instr[_]](
  using inclAskRCtx: Include[AskRequestContext, Instr],
        inclPersist: Include[PersistNewPost, Instr]
): Executable[Instr, Unit] =
  for {
    reqCtx <- inclAskRCtx.include(AskRequestContext.Ask())
    (target, message) = extractPostContent(reqCtx)
    _ <- inclPersist.include(PersistNewPost.Persist(target, message))
  } yield ()

すると、例えば `RealTimeClock[_]` という subinstruction を含むような `Instr` でも、その `Instr` が `AskRequestContext` と `PersistNewPost` の命令さえ subinstruction として持っていれば、その `Instr` を
`acceptRequest` の型引数に渡すことでメソッドコール (`Executable` の構築) が通る。

これで、内部で使う instruction への要求を edge of the world での都合から切り離すことができる。

（このメリットを「こっちの方が合成可能性が高い」とはしょることもできる）

これのほうが総合的に上手く行く。本質的には、「型クラス制約って有限集合 like であり、コンパイラが順序の情報をちゃんと捨ててつぶしてくれる」という事実に依存している。なので、「集合がほしいなあ :thinking_face:」「そうだ！　型クラス制約を使おう」という方法の motivate で(説明|正当化)すること**も**できる」

正当性は明らかだが、「これをあなたも使うといいですよ」を説得するための妥当性は相当非自明、という状況。

これは非常に重要な抽象であり、説明したいなぁ。

ここまでの説明を理解しきったら、Eff の実装を作り切れるといっていい

### Eff の本質、そして Eff のライブラリを作るということ

- 間接アドレッシングがないアセンブリから導出されたモデルを基盤として、これに直和分解された命令セットを載せ、直和分解により transpile & compactify するという実行モデルのもと、アプリケーション内部では `Include` 型クラスによって命令セットの中の概念への依存を最小化する、という一連の機構こそが Eff の本質だと**僕は**考えています。（これだけが Eff のエンコーディングではないが、conceptual essence ではあると思う。）
- 実質的に、Eff のライブラリのデザインは、この 5 つの概念の上にどれほどフレンドリーなコンビネータを置くかに掛かっていると思う
- もちろん、実行時効率を上げるために考えるべきことは山ほどある。それらの都合には今回の講演では一切触れていないが…

- ひとつ忠告しておきたいのは、Eff はプログラムのモデルとして万能であるということではないということ。
- 「AST の構造を制限して、終端記号に関する制約を (直和分解されているという、extensibility の根幹に必要な制約以外) 取っ払ったもの」が Extensible effect であるが、AST 自体がリッチである既存の cats.effects.IO などで容易に達成できることが、Eff でもできるとは限らない。(e.g. スタックトレース。cats.effects.IO は AST ノードにその情報を埋めこんでいたからできたのであって、Eff には a priori にそんなものを差し込む方法は【少なくともナイーブには】なく、スタックトレースを実現できない) (別の例として、HOE がある (HOE 前提の Eff の定義 (sayo-hs/heftia 参照) か、命令セットを再帰型により定義する必要がある))
- だからこそ、限界を探ることに意味がある。
- この講演が、あなたが命令型メタプログラミングのパラダイムの基盤を理解する手助けになってくれた、もしくはくれるのなら、それほど嬉しいことはない。

- ↑ これを言いたいがための発表

## 発表実験

### 2024-04-03

#### yanorei32

- プログラムのモデルとして木構造でモデル化されたアセンブリを紹介した。
- feedback
- アセンブリを木構造として見られることは分かったが、そう見ることのメリットが全然わからない。
- 木構造にされたアセンブリと (例えば JavaScript で書かれた) コールバック付き非同期関数呼び出しの類似性が初見では全然わからなかった。
- 具体的な CPU アーキテクチャを初手で、特に、そこから抽象的なモデルを捻り出すために出すのは悪手かも。例えば x86-64 一つをとっても、パイプラインがストールする条件や out-of-order 実行の都合などの意味論的なノイズが非常に多くなってしまい、そこから抽象的な構文論を抜き出す操作に納得してもらえるかが怪しい。抽象化自体は通りそうなので、最初にものすごく簡単なアーキテクチャもしくは架空の単純なアーキテクチャで抽象化の説明を通したうえで、「同じ議論がより複雑な x86-64、もしくは、事実上世の中のほとんどの CPU アーキテクチャに適用できると思います」と最後に一文添えるくらいの方が説明が通りやすそう。
- Kory 補足: 間接アドレスジャンプがあるアーキテクチャではプログラムの構造が動的なので、この抽象化で拾えない…
- もしかすると、セクションごとに抽象と具体的な実装例をバチバチ切り替えながら話すでもいいかもしれない
- 最初に抽象について一気に話し、その具体例を挙げていくという手
- 「アセンブリをこう見ることもできる」というのはだいぶマズくて、アセンブリの具体例から抽象的な木モデルを抜き出しているんだという話をしないと、具体から抽象への移行についていけない

#### Kory 職場の K さん

- 2時間かけて、話した
- 話した内容をまとめ損ねたが、こりーさんの糧にはなっているので記録せず放置

### 4/13

#### @chencmd

- 途中の hsjoihs & てるるゆとの話し合いを含めて 3 時間ほど掛けて `transpile` まで (かなり丁寧に) 説明した
- 一番最初に詰まったポイントが「`transpile` で branching index と exit code が貼り合わせられているのが非自明」というところであった
- これは確かにある
- exit code を executor に communicate するためのステータスコードとして導入しているので、それを branching index と貼り合わせる用に「流用」するのはだいぶ発想の飛躍が要る
- なんとかならないかなぁ
- hsjoihs & てるるゆからの major improvements の指摘がいくつか
- まず、JVM のスタックマシンというモデルに時間を掛け過ぎ。結局伝えたいことは「プログラムとは命令が有向グラフとして繋がっているもので、out-degree が >1 のところは分岐命令に相当する」というただその一点であるから、JVM bytecode & x86-64 & RISC-V でこの現象が共通して起こっていることを矢継ぎ早に語る方が話が進めやすいのではないか。
- list of instructions から graph of instructions に移行するときに付けた文句は「offset address で書かれたジャンプ命令は index of instruction に変換するのが手間」であったが、これは訴求力が弱い。そこで、「`injectAtExits` の操作を先にやりたいけれど list of instructions だと index を全部ずらす必要があり大変めんどくさい。list は合成可能性に欠ける。これをグラフだと思い直すことで、二次元的かつ空間的なデータ構造になり、injectAtExits が exit 命令のところに別のプログラムをそのまま貼り付けるだけという極めて物質界的な操作だと捉え直すことができ、便利」という方向性で話をする、つまり、exit code & inject at exits の話をリストモデルの直後、比較的最初の方にすることでグラフモデルへの移行をスムーズに正当化できるのではないか。
- あと、"You might have been thinking of functions as mechanical devices to transform a value of the input type to a value of the output type. Yet another way to perceive a (pure) function `A => B` is to see it as a `A`-indexed collection of values of `B`" というのも明示的に言っていい可能性がある
- これを空で伝えるのは結構時間かかった
- 「inject at exits の操作は CRISPR によるゲノム編集と似たような操作だ」というと面白いかもしれない
- Kory: ちょっと CRISPR を勉強してきたが、 `transpile` は言うほど CRISPR でもなさそうだった…
- 4/29 追記: Macro-ops fusion と呼ばれる Intel の Core プロセッサなどで使われている技術はまさに CRISPR っぽい (実行時パターンマッチを行って複数の x86 命令を fuse する)
- https://pc.watch.impress.co.jp/docs/2006/0306/kaigai247.htm
- https://en.wikichip.org/wiki/macro-operation_fusion
- https://ascii.jp/elem/000/000/558/558788/4/

### 4/15

#### @yuchiki1000yen

- 指摘: 「unfold したデータ構造を callback で書ける」は一般には成り立たない (無限木が有限のプログラムコードで書けるとは限らない)
- 結局、無限木的な表現を **参考にして** グラフ構造を callback 形式で書いている、という説明をするほかなさそう

### 5/9

#### @Lugendre

- 「今までずっとアセンブリの話をしていたけどいきなり `HttpGet` が出てきてビビる」
- 「AESENC 命令があるんだから Http GET する命令があってもいいだろ」の一文を挟むことで解決しそう
- @kory: Branch instructions: The Destroyer of ... で「ジャンプ命令がどれ？」をハイライトしてほしい
- @kory: 話してわかった行間として、次のようなものがありそう
- "BranchIndex need not be limited to Unit or Boolean" の部分の補足 (Int のような「大きい」型や、`Array[Byte]` のような無限型も入れられる & この構造が「普通の、変数束縛のある命令型プログラミング」をサポートしている) というのは補足として非常に重い。本文無しでは誰もついていけなさそう
- `Executable` の定義の "paths to what follows" / "後続部分" が何であるかがすぐに分からない。図で補足したい (図を描くのが難しくはある)
- 「関数をコレクションだと見做す」考えは実は普通に非自明

### 5/10

#### 前半 (45/80 スライド) を 20 分で走り切る会 @ アルプ社

- 20 分で 45/80 スライドを走り切れた
- feedback:
- 各セクションスライドで「今どの辺に居ます」という案内があると先が見えない不安が解消されそう
- 読み込みたいところはあるが、前半で突っかかるところは無く、整理されているように感じた
- exit-code / injectAtExit を導入するモチベーションは結構行間があるかも
- さらっと言うくらいでもいいかも

### 5/17

#### sanada さん

分岐数というのは Algebraic Effects における arity のこと？

スローガンがどうこのWorld-Machine-Program の発想に繋がるかが非自明。このスローガンの裏に主張がいくつか隠れていて、まず premature optimization と言っているのは、ここに掲載している動画が詳しく言っているのだが、

実際に結果を取り出すときには浮動小数点数を使うが、たとえば代数的数を使って途中を扱った方がいいこともあるし、たとえばピタゴラスを使って平方根で誤差が入りこむのがよろしくない、という。低レイヤな表現で扱うのではなく、作業中は抽象化しておいて、一番最後に具体的な表現に落とす方が、合成可能性が保たれる。というアナロジーが

Extensible というのは mix で追加できるという話？→　実際は、話していないところにある。

- 最後に "premature concretization" についての言及 (回収) があってもいいかも

## 参考にできそうな資料

- Kory が見た/読んだ
- L. Ina, *仮想関数テーブルと型クラスを見比べる p.7*, https://speakerdeck.com/tarao/comparing-vtables-and-type-classes?slide=7
- D. Spiewak, *The Case for Effect Systems*, https://www.youtube.com/watch?v=_OsM7bqY4-g
- E. Torreborre, *atnos-org/eff*, https://github.com/atnos-org/eff
- E. Torreborre, *The Eff monad, one monad to rule them all*, https://vimeo.com/channels/flatmap2016/165927840
- R. Bjarnason, *Constraints Liberate, Liberties Constrain*, https://www.youtube.com/watch?v=GqmsQeSzMdw

- 見たい
- H. Ishii, *Freer Monads, More Extensible Effects*, https://www.slideshare.net/konn/freer-monads-more-extensible-effects-59411772
- R. Ueyama, *低レイヤを知りたい人のためのCコンパイラ作成入門*, https://www.sigbus.info/compilerbook
- C. Domas, *movfuscator*, https://github.com/xoreaxeaxeax/movfuscator