Don't Repeat Yourself

Don't Repeat Yourself (DRY) is a principle of software development aimed at reducing repetition of all kinds. -- wikipedia

【競プロノート】グラフを Rust で実装してみる

先日の Rust LT 会でグラフを実装してみる話がありました。そこではおそらく隣接リストを説明していたと思うのですが、そういえば Rust で実装してみたことはなかったなと思ったので、実装してみました。

『みんなのデータ構造』という本を参考にして実装しています。12章にグラフの章があります。何言語かで書かれたサンプルコードも存在します。

今回は、本書に掲載されていた下記のような「典型的な操作」を実装しました。今回はグラフ G = (V, E) を考えるものとします。一般的な話通りで、V は頂点で、E は辺です。

  • addEdge(i, j): 辺 (i, j) を E に加える
  • removeEdge(i, j): 辺 (i, j) を E から除く
  • hasEdge(i, j): (i, j) ∈ E かどうかを調べる
  • outEdges(i): (i, j) ∈ E を満たす整数整数 j のリストを返す
  • inEdges(i): (j, i) ∈ E を満たす整数整数 j のリストを返す

隣接行列

いきなりですが、隣接行列の実装は意外と大変です。Rust は、ポインタを使った操作 (参照先を書き換えてゴニョゴニョする操作) をしようとすると少々めんどくさくなるように言語が設計されています。隣接行列は行列 (2次元の配列) をもったデータ構造なのですが、その行列を状態とみなして書き換えていく操作を発生させるため、Rust 的にはとても面倒な実装になります。

今回実装した隣接行列は、(i, j) ∈ E のときに true となり、そうでない場合は false となる要素が含まれている行列です。

速度面などの細かい話を気にせず、RefCell を使用して実装してみました。ちなみに、std::mem::replace でも実装できると思いますし、実際 RefCell#replace はそれを使用して実装されているため、もしかすると RefCell を使用するのは大げさだったかもしれません。

use std::cell::RefCell;

pub struct AdjacencyMatrix {
    dimension: usize,
    matrix: Vec<Vec<RefCell<bool>>>,
}

impl AdjacencyMatrix {
    pub fn new(dimension: usize) -> AdjacencyMatrix {
        let mut matrix = vec![];
        for _ in 0..dimension {
            let mut tmp = vec![];
            for _ in 0..dimension {
                tmp.push(RefCell::new(false));
            }
            matrix.push(tmp);
        }

        AdjacencyMatrix { dimension, matrix }
    }

    pub fn dimension(&self) -> usize {
        self.dimension
    }

    fn get(&self, i: usize, j: usize) -> &RefCell<bool> {
        self.matrix.get(i).unwrap().get(j).unwrap()
    }

    pub fn add_edge(&self, i: usize, j: usize) {
        self.get(i, j).replace(true);
    }

    pub fn remove_edge(&self, i: usize, j: usize) {
        self.get(i, j).replace(false);
    }

    pub fn has_edge(&self, i: usize, j: usize) -> bool {
        *self.get(i, j).borrow()
    }

    pub fn in_edges(&self, i: usize) -> Vec<usize> {
        let mut edges = vec![];
        for j in 0..self.dimension {
            if *self.get(j, i).borrow() {
                edges.push(j);
            }
        }
        edges
    }

    pub fn out_edges(&self, i: usize) -> Vec<usize> {
        let mut edges = vec![];
        for j in 0..self.dimension {
            if *self.get(i, j).borrow() {
                edges.push(j);
            }
        }
        edges
    }
}

隣接リスト

逆に、隣接リストはスムーズに実装できます。これは、単純にエッジを追加する際にリストの末尾に値を入れていけばよいためです。

pub struct AdjacencyList {
    dimension: usize,
    list: Vec<Vec<usize>>,
}

impl AdjacencyList {
    pub fn new(dimension: usize) -> AdjacencyList {
        AdjacencyList {
            dimension,
            list: vec![vec![]],
        }
    }

    pub fn dimension(&self) -> usize {
        self.dimension
    }

    pub fn add_edge(&mut self, i: usize, j: usize) {
        if i > self.dimension() {
            panic!("add: greater than dimension");
        }

        match self.list.get_mut(i) {
            Some(v) => v.push(j),
            None => self.list.insert(i, vec![j]),
        }
    }

    pub fn remove_edge(&mut self, i: usize, j: usize) {
        match self.list.get_mut(i) {
            Some(v) => v.retain(|v0| *v0 != j),
            None => (),
        }
    }

    pub fn has_edge(&self, i: usize, j: usize) -> bool {
        match self.list.get(i) {
            Some(v) => v.contains(&j),
            None => false,
        }
    }

    pub fn in_edges(&self, i: usize) -> Vec<usize> {
        let mut edges = vec![];
        for j in 0..self.dimension() {
            if let Some(list) = self.list.get(j) {
                if list.contains(&i) {
                    edges.push(j);
                }
            }
        }
        edges
    }

    pub fn out_edges(&self, i: usize) -> Vec<usize> {
        match self.list.get(i) {
            Some(v) => v.to_vec(),
            None => vec![],
        }
    }
}

ポイントは、隣接リストの場合は初期状態の Vec<Vec<usize>> で、たとえば行を取得したい場合に、行が None として返ってきてしまうパターンが考えられるため、その点について留意しなが実装する必要があったという点です。Vector 関連でもっといい操作があれば知りたいところですが、思いつく限りでは None がどうしても発生してしまうため、都度パターンマッチして慎重に取り出す操作を行っています。

もっとも単純なグラフの実装がこれでわかりました。

2020年の Rust

2020年、Rust をどうしていくかというロードマップが例年通り策定されているようです。まだ草案なようなので変わる可能性がありそうですが、現時点での情報をまとめておこうかなと思います。

github.com

まとめると

  • Rust 2021 Edition への準備の年。
  • 現在進行中の作業をやりきる。
  • プロジェクトのガバナンスや可視性を改善する。

Rust 2021 Edition への準備

Rust では3年単位で「Edition」を変えることにしています。2018年に行われた Rust 2018 Edition が記憶に新しいかもしれません。2020年はその前年に当たるため、10月くらいに 2021 Edition で何をやるかについては決めきっておきたいようです。

2021 Edition ではどういった機能の変更が想定されているのでしょうか?草案に書いてある限りでは、

  • エラーハンドリング: 実は、Rust のエラーハンドリングにはデファクトに近い存在はあるものの、ユーザーは何を使うべきかを決めかねている状態が続いています。標準ライブラリでおそらくよいエラーハンドリングを選定し、実装することになるはずです。
  • 詳細は未定ですが trait に関する修正も入れたいようです: 個人的には async trait を有効にしていただけると大変幅が広がります。
  • &raw をはじめとする unsafe 周りの機能の改善: &raw&mut <place> as *mut&<place> as *const の対極に位置する予定の文法で、これが導入されると生ポインタを直接生成することができるようになります。

現在進行中の作業をやりきる

Rust のチーム的には、「ほとんど終わっているけれど完了ではない」作業が長く放置されていることを問題視しており、それを今年は、1つ1つ確実に完了させていきたいと思っているようです。たしかに、何年か前にステータスが変わらなくなり放置されている Issue などをたまに見かける気がします…。今年で多く片付くと嬉しいですね。

プロジェクトのガバナンスや可視性を改善する

3つくらいやりたいことがあげられていました。

  • 設計作業の状態の可視性とイニシアチブの取り方を改善したい。
  • メンタリングやリーダーシップ、それらに対する組織的な手助けの幅を広げたい。
  • 設計に関するディスカッションをより生産的にし、その作業によって消耗することのないようにしたい。

現在進行中の作業について、「どれが自分は手伝えそうか」といった話や、「X という機能の現在の進捗状態を知りたい」というのがとても把握しにくいといった問題があるようです。これは新規参画者だけでなく、結構コントリビュートしている人にとっても難しいらしく、そのあたりをまずは改善していきたいと考えているようです。ステータスを文章化してまとめたり、あるいは更新をもっと投稿するように作業時間を増やしていこうと考えているようです。

あとは単純にプロジェクトをリードする人や、新規のコントリビュータをメンタリングする人が足りていないようで、そのあたりの補充をしたいと考えているようです。

Rust は、RFC がユーザーに開かれています。誰でも議論に参加可能です。この形式は他言語にもだんだん浸透していっています。すばらしいものです。ただ、たとえば大規模で議論の余地がたくさんある設計に関する議論の際には、この仕組みがうまく機能しなくなりはじめているのではないかと見ているようです。今年は、RFC の議論周りの仕組みを改善していけるように、重きをおいて取り組んでいくことにしたようです。

直近の例だと async/await 導入あたりでの RFC の議論は、結構カオスになっていたように見えました。Rust のオープンな RFC システムはすばらしいとは思いますが、たしかにこのあたりは改善が必要かもしれませんね。期待。

余談: 2020年での日本の Rust コミュニティ

今年も Rust.Tokyo をやります。準備がんばります。今年も多くの人にお越しいただけますと嬉しいです。

感想

2018 年は 2018 Edition で忙しく、2019 年は async/await の導入でとても忙しかったようで、たしかに大量の「やりかけ RFC」が残っているようにも思います (しかも終わったのかステータスがわかりにくいのはたしかにそう…)。今年はそのあたりの機能がいくつか消化されるたり、あるいは RFC 管理が直感的にステータスを把握できるように改善されると期待できそうですね!

もし、英語の解釈が間違っているようでしたら教えていただけますと幸いです🙏🏻

作って学ぶ、cats.effect.IO モナドのしくみ

今回は cats.effect.IO (以下、 IO ) を理解する上で最低限必要となる*1実装を選定して、cats を参考に IO を実装してみました。具体的には、下記の機能を実装してみます。

  • IO#pure
  • IO#delay or IO#apply
  • IO#raiseError
  • IO#map
  • IO#flatMap
  • IO#unsafeRunSync

この記事のサンプルを実装し切ると、最終的にはたとえば次のようなコードが動きます。

object Main extends App {

  val io = for {
    num <- IO.pure(123)
    numStr <- IO.pure(num.toString)
    withHello <- IO.pure(s"${numStr}, Hello!")
    _ <- IO(println(withHello))
  } yield ()

    // "123, Hello!"
  io.unsafeRunSync()
}

逆に、紹介するにとどめて終わりそうな機能は下記です。

  • IO#async: 非同期処理を開始することができます。
  • IO#start: これを使用するとグリーンスレッドを扱うことができるようになります。実装的には、上記の async と、ExecutionContext の切り替え機能 (IO#contextShift) と、Fiber を実装すれば実現できます。

もちろん、IO では、ポーリング時に保有することになるスタックの大きさと深さの細かい管理が必要です。今回は、パフォーマンス面はまったく追求せず、単に IO の中身のコンセプトを理解するという点に主眼を置いています。

IO とは

遅延評価つき Future

IO は、もともとは Haskell にある概念です。IO[A] は、評価されるときに、A 型の値を返す前に副作用のある振る舞いをする計算であることを表現する型です。IO の値は純粋でイミュータブルであり、そのため参照透過です。

IO を使うことで、同期計算あるいは非同期計算を記述できます。for-yield でつないで書いていくことができますし、また内部処理をキャンセル可能にすることもできます。

もし、一般的に Scala で使用される概念である Future をご存知でしたら、IO は遅延評価つき Future といった対応関係にあります*2

ステートマシンである

実は、IO ( Future も) は、ステートマシンなのです*3。IO は、中のステート = 状態が受理になるまで遷移していき、受理になった時点で unsafeRunSync などの値を取り出す動作を行うと、値を取り出せるという仕組みになっています。

事実、cats の IO は下記のようなデータ構造をもっています。実際の IO.scalahttps://github.com/typelevel/cats-effect/blob/master/core/shared/src/main/scala/cats/effect/IO.scala#L1483

  private[effect] final case class Pure[+A](a: A)
    extends IO[A]

  private[effect] final case class Delay[+A](thunk: () => A)
    extends IO[A]

  private[effect] final case class RaiseError(e: Throwable)
    extends IO[Nothing]

  private[effect] final case class Suspend[+A](thunk: () => IO[A])
    extends IO[A]

  private[effect] final case class Bind[E, +A](source: IO[E], f: E => IO[A])
    extends IO[A]

  private[effect] final case class Map[E, +A](source: IO[E], f: E => A, index: Int)
    extends IO[A] with (E => IO[A]) {

    override def apply(value: E): IO[A] =
      new Pure(f(value))
  }

  private[effect] final case class Async[+A](
    k: (IOConnection, Either[Throwable, A]  => Unit) => Unit,
    trampolineAfter: Boolean = false)
    extends IO[A]

  private[effect] final case class ContextSwitch[A](
    source: IO[A],
    modify: IOConnection => IOConnection,
    restore: (A, Throwable, IOConnection, IOConnection) => IOConnection)
    extends IO[A]

多くの代数データがあります。cats では、同期処理であれば IORunLoop#step、非同期処理であれば IORunLoop#loop を使って、これらの代数データを遷移させていきます。これが、IO がステートマシンである所以なのです。

実装してみる

実装していきます。この IO は並行性を獲得できてはいませんが、IO の挙動の学習用には同期処理側を学ぶのが複雑性が少なく最適だと思うので、あえて実装していません。

用意した代数データ

今回は Pure, Delay, FlatMap, Map, そして RaiseError を切り出して用意しました。

object IO {
  final case class Pure[+A](a: A) extends IO[A]
  final case class Delay[+A](thunk: () => A) extends IO[A]
  final case class RaiseError(err: Throwable) extends IO[Nothing]
  final case class FlatMap[E, +A](original: IO[E], f: E => IO[A]) extends IO[A]
  final case class Map[E, +A](original: IO[E], f: E => A, index: Int)
      extends IO[A]
      with (E => IO[A]) {
    override def apply(value: E): IO[A] = Pure(f(value))
  }
}

https://github.com/yuk1ty/scratch-io-monad/blob/master/src/main/scala/effect/IO.scala

状態遷移を見てみる

今回は cats の IO を参考に、IOExecutor というクラスを実装してみました。というか、まるっと切り出しただけです。このクラスは、IO の状態遷移をかけつつ、状態に応じた関数適用や値の取り出しを逐次行っていくクラスです。

実装はこちらにあります→ https://github.com/yuk1ty/scratch-io-monad/blob/master/src/main/scala/effect/internal/IOExecutor.scala

IOExecutor#step と代数データを見比べながら、処理を少し理解してみましょう*4

登場人物を整理する

step 関数内の登場人物を少し整理します。

object IOExecutor {

  private[this] type Current = IO[Any]

  private[this] type Bind = Any => IO[Any]

  private[this] type CallBack = Either[Throwable, Any] => Unit

  private[this] type CallStack = mutable.ArrayStack[Bind]

  def step[A](source: Current): IO[A] = {
    var currentIO = source
    var bindFirst: Bind = null
    var bindRest: CallStack = null
    var hasUnboxed = false
    var unboxed: AnyRef = null
(...)
  • currentIO: 現在処理中の IO を指し示します。
  • bindFirst: 次にやってくる予定の処理を一時的に保管しておくための変数です。
  • bindRest: 2個、3個と bindFirst が積み上がることは容易に想像されます。それを保管するためのスタックを用意しています。
  • hasUnboxed: 中身が評価されたかどうかを制御しています。Delay か Pure に到達すると true になります。後続の処理で使用するためのフラグ。
  • unboxed: 評価された値を一時保存しておきます。

Pure に到達すると受理状態になる

IO は、状態遷移した後に Pure あるいは RaiseError に到達すると受理状態になります。つまり、この step 関数のなかで行っている処理は、再帰的に代数データの中身をたどっていき、Pure 状態 (例外時は RaiseError に寄せられます) に到達するまで状態遷移を繰り返していく処理です。

たとえば次のような IO の処理を組み立てたとしましょう。

for {
    num <- IO.pure(123)
    plusOne <- IO.pure(num + 1)
    plusThree <- IO.pure(plusOne + 3)
} yield plusThree

生成される代数データは次のようになっています。

FlatMap(Pure(123),Main$$$Lambda$2/892529689@6b9651f3)

中身について少し見ていきましょう。FlatMap と Delay で囲まれていることがわかります。FlatMap の代数データは、先ほどの代数データ一覧であったように、元のデータが左側に入っていて、これから連結したい対象の処理が右側に入っているという構図です。Main$$Lambda... については、左は「num + 1」、右は「plusOne + 3」が入っています。for-yield は flatMap のシンタックスシュガーなためです。flatMap の中身は Function ですよね。

この代数データに対して step 関数を適用して処理を実行していくと、次のような遷移をします。

// IO.pure(123) と IO.pure(num + 1) が入っている。
FlatMap(Pure(123),Main$$$Lambda$2/892529689@6b9651f3) 
// IO.pure(123) をたどっている。
Pure(123)
 // num + 1 適用後値と、IO.pure(plusOne + 3) が入っている。
FlatMap(Pure(124),Main$$$Lambda$6/1728790703@12f41634)
// IO.pure(123) をたどっている。
Pure(124) 
// plusOne + 3 をたどっている。
<function1>
// ↑が適用された 
Pure(127)
// 受理状態になった
Pure(127) 

Delay の挙動

公式ドキュメントに習って、IO は、遅延評価つきの IO であると先ほど紹介しました。その根幹を担うのがこの Delay という代数データです。IO#apply をすると基本的に Delay に状態遷移するようにできています。

すこしわかりにくいですが、Delay と Pure を織り交ぜて見ると、下記のような動きをします。

for {
    num <- IO.pure(123)
    plusOne <- IO(num + 1)
    plus3 <- IO(plusOne + 3)
} yield plus3
FlatMap(Pure(123),Main$$$Lambda$2/892529689@6b9651f3)
Pure(123)
FlatMap(Delay(Main$$$Lambda$6/1415157681@16f7c8c1),Main$$$Lambda$7/641853239@2f0a87b3)
Delay(Main$$$Lambda$6/1415157681@16f7c8c1)
<function1>
Delay(Main$$$Lambda$9/1338841523@b3d7190)
Pure(127)

Delay は、保持する値 (thunk) を評価せずに、一度遅延状態で保持する状態です。Delay は、step 関数に入れられてはじめて thunk の評価がかけられ、値が評価されていきます。

case Delay(thunk) => {
    Try {
       unboxed = thunk().asInstanceOf[AnyRef]
       hasUnboxed = true
       currentIO = null
    }.recover {
        case NonFatal(err) =>
          currentIO = RaiseError(err)
    }.get
}

unboxed に標準出力関数を噛ませて、中身の状態を見ていきましょう。

FlatMap(Pure(123),Main$$$Lambda$2/892529689@6b9651f3)
Pure(123)
FlatMap(Delay(Main$$$Lambda$6/1415157681@16f7c8c1),Main$$$Lambda$7/641853239@2f0a87b3)
Delay(Main$$$Lambda$6/1415157681@16f7c8c1)
delay unboxed: 124
<function1>
Delay(Main$$$Lambda$9/1338841523@b3d7190)
delay unboxed: 127
Pure(127)

きちんと関数適用が行われていたことがわかりました。

つなげる FlatMap

IO#flatMap をすると、FlatMap 状態に遷移します。この代数データの step 関数側の処理を見てみると、次のようなことをしています。

    do {
      currentIO match {
        case FlatMap(fa, bindNext) => {
          if (bindFirst != null) {
            if (bindRest == null) {
              bindRest = new mutable.ArrayStack()
            }
            bindRest.push(bindFirst)
          }

          bindFirst = bindNext.asInstanceOf[Bind]
          currentIO = fa
        }
(...)

FlatMap は一度パターンマッチに入ってくると、まず次に評価予定の内容をスタックの一番上に詰め込んでおきます。その後、現在の評価中 IO を自身のもともと評価予定だった IO に変え、次のループでその中身を処理していきます。これが、flatMap によって IO モナドがまるでひとつであるかのように連結されていくように見える所以です*5

flatMap を二重に重ねてしまう→「発火しない!」

実際にプロダクションで IO を使っていて、不意に実装中に flatMap が2回重なってしまって、IO が発火されずに困っているケースが散見されました。なぜこれが起きるかも、ステートマシンの動きを見ていくとわかります。

for {
    num <- IO.pure(123)
    plusOne <- IO(num + 1)
    plus3 <- IO(IO(plusOne + 3)) // 2回重ねてみた
} yield plus3

さて、ステートマシンの動きはどうなっているかというと…

FlatMap(Pure(123),Main$$$Lambda$2/892529689@6b9651f3)
Pure(123)
FlatMap(Delay(Main$$$Lambda$6/1415157681@16f7c8c1),Main$$$Lambda$7/641853239@2f0a87b3)
Delay(Main$$$Lambda$6/1415157681@16f7c8c1)
<function1>
Delay(Main$$$Lambda$9/1338841523@5d11346a)
Delay(Main$$$Lambda$11/2050404090@17211155)
Pure(Delay(Main$$$Lambda$11/2050404090@17211155))

Pure(Delay(...)) となってしまっていることがわかります。内側の Delay は関数適用が行われていないために評価されておらず、結果値を取り出せていません。

「そんなケースあるのか?」という話なのですが、プロダクションで見たケースとしては、たとえば IO(num + 1) の間に KVS への保存処理などを含んでいたとします。下記のように書いたとしましょう。

// num は外で定義されているものとします

// KvsRepository.scala
object KvsRepository {
    def insert(i: Int): IO[Unit] = IO(kvs.set(i)) // kvs への保存処理
}

// Main.scala
IO {
    KvsRepository.insert(num)
    num + 1
}.unsafeRunSync()

この場合は発火しませんね。なぜなら、KvsRepository 内の処理は Delay になっているからです。したがって、この insert は発火されず、num + 1 の結果だけが返ります。

IO の使い所の注意としては、きちんと最終的に Pure 状態になるようにコンビネータをつなげ続ける必要があるという点です。先ほどの KVS への保存の例のコードを修正するとしたら、次のようになるでしょう。

// num は外で定義されているものとします
val task = for {
    _ <- KVSRepository.insert(num)
    n <- num + 1
} yield n

task.unsafeRunSync()

発火しない問題には注意が必要です。が、かといって、副作用を含む処理を IO#pure に入れるのは、たしかに即時評価を起こせますが IO の本来の使い方や目的とは違っています。なので、面倒臭がらずに、きちんとコンビネータをつなげることを私はおすすめします。発火しない問題が起きた際には、一度 IO モナドを print するなどして、現在の代数データの状況がどうなっているかを確認するとよいです。

まとめ

  • IO はステートマシンである。
  • このステートマシンは、Pure か RaiseError になると受理状態になる。

リポジトリ

今回記事の長さの都合 (とわたしの気力の都合) でこの記事では解説しきれなかった、例外処理側や step 関数の実装全体もこのリポジトリに置いてあります。本当は RaiseError 時に復旧手段として用意されている IOFrame も解説するべきだったかもしれません…。

実装そのものはそこまでハードでもないですし、IO モナドを深く理解したい方には一度フルスクラッチしてみるのはとてもおすすめだと私は思いました。もともとは会社のチームメンバーのみなさんに使ってもらえるようにリポジトリを用意しましたが、2020年のチャレンジにどうぞ。

github.com

参考

*1:というか、私がよく使っているだけとも言うけれど

*2:ちなみに Future パターンに関する解説はこちらに詳しく載っています。

*3:この話については、この記事がとてもわかりやすいです→ステートマシン抽象化としてのFuture | κeenのHappy Hacκing Blog

*4:実装を見ると、再代入をかなり繰り返しますし、かつ Any や AnyRef などを多用していて型安全性も少し低めです。再代入を繰り返しているのは、パフォーマンス面を考慮してのことではないかと思いました。また、Any や AnyRef を全廃しようとすると、多くの型に対して個別実装を生やす必要が出てきて、実装の手間が膨大になりそうだなと思いました。それに加えて、Any(Ref) の範囲はこの IO 内に限られていて外には露出していませんので、問題ではないのかもしれませんね。

*5:このスタックの深さは、効率よく制御しないとパフォーマンスネックになる可能性があると想像できます。今回の実装では Scala の標準でついている ArrayStack を使用しましたが、cats では独自に Stack 実装を用意してありました。

async/await 時代の新しい HTTP サーバーフレームワーク tide を試す

Rust Advent Calendar 2019 25日目の記事です。

tide は現在開発途中の、 Rust の async/await に対応した HTTP サーバーを構築するフレームワークです。not ready for production yet なので本番にこれを使用するのは難しいかもしれませんが、いろいろな例を見てみた感じとても使いやすそうで、注目に値するフレームワークの一つです。

記事を少し読んでみたのですが、どうやら 2018 年に Rust の Network Service Working Group が開発に着手したフレームワークのようですね。現在のステータスを追いかけていないので詳しくはわかりませんが、Rust チームの方々が何かしら関わっているフレームワークということで、少し安心感がもてるかなと私は思っています。async/await が今年無事安定化されたので、一層開発が進んでくれると嬉しい…そんなフレームワークです。

GitHubリポジトリはこちら。

github.com

また、開発者の方の Twitter はこちら。時々 tide に関する最新情報が流れてくるので、tide がどういう状況かを逐次キャッチアップしたい方はフォローしておくとよいと思います🙂

twitter.com

今回はそんな tide を少し触ってみたので、解説記事を書いておきたいと思います*1

実行 OS は macOS version 10.14 です。また、テンプレ用のリポジトリも用意しました→GitHub - yuk1ty/tide-example: A build template for tide

Hello, World してみる

まずは GitHub のサンプルを写したらいけるだろうということで、README.md のものをそのままローカルに落としてきて Hello, World してくれる API を用意してみましょう。Cargo.toml に tide の依存を追加します。その後、下記のように書きます。

#[async_std::main]
async fn main() -> Result<(), std::io::Error> {
    let mut app = tide::new();
    app.at("/").get(|_| async move { "Hello, World!" });
    app.listen("127.0.0.1:8080").await?;
    Ok(())
}

ただ…このまま実行すると、次のようなコンパイルエラーに見舞われました。

$ cargo build
   Compiling tide-example v0.1.0 (/Users/xxx/dev/rust/tide-example)
error[E0433]: failed to resolve: use of undeclared type or module `async_std`
 --> src/main.rs:1:3
  |
1 | #[async_std::main]
  |   ^^^^^^^^^ use of undeclared type or module `async_std`

error[E0277]: `main` has invalid return type `impl std::future::Future`
 --> src/main.rs:2:20
  |
2 | async fn main() -> Result<(), std::io::Error> {
  |                    ^^^^^^^^^^^^^^^^^^^^^^^^^^ `main` can only return types that implement `std::process::Termination`
  |
  = help: consider using `()`, or a `Result`

error: aborting due to 2 previous errors

どうやら、#[async_std::main] が存在しないと怒られてしまっています。それに伴って、async fn main() が返す結果が impl std::future::Future となってしまっており、エラーがもうひとつ発生しています。しかし、おそらく #[async_std::main] が存在しないために起きている事象なはずですので、そちらを解決することに専念しましょう。

async-std とは?

#[async_std::main] ですが、 Rust チームが鋭意開発中の非同期処理基盤 async-std に入っています。

async-std は、Go のランタイムのタスクスケジューリングアルゴリズムやブロッキング戦略を Rust に導入したライブラリです。非同期処理のランタイムには tokio をはじめいくつか種類がありますが、そのうちのひとつが async-std です*2。余談ですが Rust.Tokyo でキーノートをしてくれた Florian が開発に携わっていますね!

この crate に含まれる #[async_std::main] アトリビュートを追加すると、async fn main() -> Result<...> と宣言できるようになり、アプリケーションを非同期処理のランタイムに乗せられます。つまり、tide は async-std 上に乗って動いているということでもあります。

github.com

Cargo.toml に設定を追加する

なお、この #[async_std::main] ですが、async-std の attribute feature を有効にしてライブラリとして追加する必要があるようです。したがって、使用したい場合には自身で下記の記述を追加する必要があります。

[dependencies.async-std]
version = "1.4.0"
features = ["attributes"]

HTTP サーバーが起動する

この状態で走らせると…

$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.33s
     Running `target/debug/tide-example`
Server is listening on: http://127.0.0.1:8080

無事にサーバーが起動しました!curl で GET リクエストを送ってみましょう。すると…

$ curl localhost:8080
Hello, World!

Hello, World! と返ってきます。これでようやく動作確認が完了しました。

ルーティングをちょこっと紹介

私が気になった機能をピックアップして試していきます。

/hc に GET を投げると 200 OK を返す

よく実装するヘルスチェック機構を実装しましょう。/hc に対して GET リクエストを送ると 200 OK を返させます。これには tide::Response を利用します。

use tide::Response;

#[async_std::main]
async fn main() -> Result<(), std::io::Error> {
    let mut app = tide::new();
    app.at("/hc").get(|_| async move {
        Response::new(200)
    });
    app.listen("127.0.0.1:8080").await?;
    Ok(())
}

curl を投げて確認してみましょう。

$ curl --dump-header - localhost:8080/hc
HTTP/1.1 200 OK
transfer-encoding: chunked
date: Tue, 24 Dec 2019 08:01:19 GMT

想定通り、200 OK が返ってきていますね。Response の実装を少し読んでみましたが、Web アプリを作る際に欲しい機能は一通り用意されているようでした。

複数エンドポイントを作ってみる――罠。

後ほど使用するために、/json というエンドポイントを用意してみましょう。

use tide::Response;

#[async_std::main]
async fn main() -> Result<(), std::io::Error> {
    let mut app = tide::new();
    app.at("/hc").get(|_| async move { Response::new(200) });
    app.at("json").get(|_| async move { "OK" });
    app.listen("127.0.0.1:8080").await?;
    Ok(())
}

これで、curl を叩いてみます。

$ curl localhost:8080/json
OK

大丈夫ですね!👏 ただ、ちょっとハマったポイントがありました。普通はやらないのかもしれませんが、app.at(...).get(...).at(...).get(...) といった形で、実はメソッドチェーンが可能です。

use tide::Response;

#[async_std::main]
async fn main() -> Result<(), std::io::Error> {
    let mut app = tide::new();
    app.at("/hc")
        .get(|_| async move { Response::new(200) })
        .at("/json")
        .get(|_| async move { "OK" });
    app.listen("127.0.0.1:8080").await?;
    Ok(())
}

よさそうに見えます。コンパイルも通りました。/hc というエンドポイントと、/json というエンドポイントが作られるだろうと期待しています。curl を叩いてみます。

$ curl --dump-header - localhost:8080/json
HTTP/1.1 404 Not Found
transfer-encoding: chunked
date: Tue, 24 Dec 2019 09:04:21 GMT

えっ…消えました…。もしかして、と思って次のような curl を叩いてみました。

$ curl --dump-header - localhost:8080/hc/json
HTTP/1.1 200 OK
content-type: text/plain; charset=utf-8
transfer-encoding: chunked
date: Tue, 24 Dec 2019 09:04:55 GMT

OK

なるほど、つまりメソッドチェーンをすると、チェーンした分だけ配下にどんどんパスが切られていってしまうのでしょう。これはちょっと微妙なデザインだと思いました。メソッドチェーンをしたとしても、第一階層にパスが追加され続けるというデザインが直感的なように私には思えました。あるいは、メソッドチェーン自体を禁止される形式がよいのかもしれません。

nest

ちなみに、もしルートをグループ化して使用したい場合には nest という関数が使えます。RubySinatra や Go の echo などのご存知の方は、ああいった namespaceGroup 関数のようなものが使えるイメージです。たとえば、/api/v1 という親ルートの中に、/hc/endpoint という子ルートを用意したい場合には、次のように記述できます。

use tide::Response;

#[async_std::main]
async fn main() -> Result<(), std::io::Error> {
    let mut app = tide::new();
    app.at("/api/v1").nest(|router| {
        router.at("/hc").get(|_| async move { Response::new(200) });
        router
            .at("/endpoint")
            .get(|_| async move { "nested endpoint" });
    });
    app.listen("127.0.0.1:8080").await?;
    Ok(())
}

curl で確認してみると、しっかり指定したルートで登録されていました!

curl -i localhost:8080/api/v1/hc
HTTP/1.1 200 OK
transfer-encoding: chunked
date: Tue, 24 Dec 2019 09:21:56 GMT
curl -i localhost:8080/api/v1/endpoint
HTTP/1.1 200 OK
content-type: text/plain; charset=utf-8
transfer-encoding: chunked
date: Tue, 24 Dec 2019 09:23:25 GMT

nested endpoint

JSON を含むリクエストを投げる

公式ドキュメントに載っているコードを拝借して、JSON をボディに含むリクエストを受け取り、結果を同様に JSON で返す処理を書き足してみます。ここで、Cargo.toml に serde への依存を追加しつつ…

use serde::{Deserialize, Serialize};
use tide::{Request, Response};

#[derive(Debug, Deserialize, Serialize)]
struct Counter {
    count: usize,
}

#[async_std::main]
async fn main() -> Result<(), std::io::Error> {
    let mut app = tide::new();
    app.at("/hc").get(|_| async move { Response::new(200) });
    app.at("/json").get(|mut req: Request<()>| {
        async move {
            let mut counter: Counter = req.body_json().await.unwrap();
            println!("count is {}", counter.count);
            counter.count += 1;
            tide::Response::new(200).body_json(&counter).unwrap()
        }
    });
    app.listen("127.0.0.1:8080").await?;
    Ok(())
}

curl を投げてみます。カウントが1のリクエストを投げたので、カウントが2になって JSON 形式で返ってきてくれれば成功です。

$ curl -i -H "Accept: application/json" -H "Content-type: application/json" -d '{ "count": 1 }' -X GET localhost:8080/json
HTTP/1.1 200 OK
content-type: application/json
transfer-encoding: chunked
date: Tue, 24 Dec 2019 09:11:42 GMT

{"count":2}

成功しました。

ちょっと小話

Request-Response

tide のデザインの特徴として、Request-Response 方式を採用している点があげられています。関数のシグネチャは非常にシンプルな構成で、Request を引数に受け取り、Response (を含む Result 型) を返すという構成になっています。

async fn endpoint(req: Request) -> Result<Response>;

これまでは Request と Response のライフサイクルの管理は Context を用いて行っていましたContext を受け取り、その中からリクエストの実体を取り出す構成でしたが、バージョン 0.4.0 になって変更が加えられました

State

State というのはミドルウェアがエンドポイント間で値をシェアするために使用されるものです。actix-web や Rocket でも確かあった機能だったかなと記憶しています。State 付きでサーバーを起動する際には、先ほどのように tide::new() するのではなく、 tide::with_state() する必要があります。サンプルコードを載せておきます。

struct State {
    name: String,
}

async fn main() -> Result<(), std::io::Error> {
    let state = State {
        name: "state_test".to_string(),
    };
    let mut app = tide::with_state(state);
    app.at("/hc").get(|req: Request<State>| {
        async move {
            tide::Response::new(200)
        }
    });
}

重要なことは、

  • app の型はもともと Server<()> だったものから、Server<State> に変わっている。
  • get の部分については、Request<()> だったものから、 Request<State> に変わっている。

点です。

Extension Traits

Request や Response といった構造体を型クラスを用いて拡張することもできます。ちょっとした処理を付け足したい際に便利ですね。たとえば、次のようにヘルスチェックすると「OK」と body に入れて返すエンドポイントを、Extension Traits を用いて実装してみます。

use tide::{Request, Response};

trait RequestExt {
    fn health_check(&self) -> String;
}

impl<State> RequestExt for Request<State> {
    fn health_check(&self) -> String {
        "OK".to_string()
    }
}

#[async_std::main]
async fn main() -> Result<(), std::io::Error> {
    let mut app = tide::new();
    app.at("/hcext")
        .get(|req: Request<()>| async move { req.health_check() });
    app.listen("127.0.0.1:8080").await?;
    Ok(())
}

curl を投げると、上手に動作していることがわかります。

$ curl -i localhost:8080/hcext
HTTP/1.1 200 OK
content-type: text/plain; charset=utf-8
transfer-encoding: chunked
date: Tue, 24 Dec 2019 09:32:16 GMT

OK

ルーティング応用編

最後に、実アプリケーションであれば必須な機能2つを試してみましょう。パラメータとクエリパラメータです。

パラメータを取得する

たとえばよくやる手として、id = 1 の user というリソースから1つ、user を取得したいというユースケースがあります。これももちろん実装されていました。/users/:id というエンドポイントを用意したくなったら、次のように実装すれば実現できます。

use tide::{Request, Response};

#[async_std::main]
async fn main() -> Result<(), std::io::Error> {
    let mut app = tide::new();
    app.at("/users/:id").get(|req: Request<()>| {
        async move {
            // 型注釈は必須の模様。つけないと、推論に失敗する。
            let user_id: String = req.param("id").client_err().unwrap();
            Response::new(200).body_string(format!("user_id: {}", user_id))
        }
    });
    app.listen("127.0.0.1:8080").await?;
    Ok(())
}

curl を投げてみましょう。

$ curl -i localhost:8080/users/1
HTTP/1.1 200 OK
content-type: text/plain; charset=utf-8
transfer-encoding: chunked
date: Tue, 24 Dec 2019 13:12:47 GMT

user_id: 1

期待したとおり、:id に含まれていた 1 という値を返してくれています。正常に動作しているとわかりました。

クエリパラメータを扱う

パラメータが使えるのならば、きっとクエリパラメータも使えてほしいはずです。あります。クエリの方は、パース先の構造体を用意しておいて (サンプルコードの QueryObj)、serde の Deserialize を derive しておくと、あとは勝手に値をパースして構造体に埋めてくれる機能が備わっています。

今回期待する内容は、/users?id=1&name=helloyuki というリクエストを投げると、id と name を返してくれるエンドポイントができていることです。

use serde::Deserialize;
use tide::{Request, Response};

#[derive(Debug, Deserialize)]
struct QueryObj {
    id: String,
    name: String,
}

#[async_std::main]
async fn main() -> Result<(), std::io::Error> {
    let mut app = tide::new();
    app.at("/users").get(|req: Request<()>| {
        async move {
            let user_id = req.query::<QueryObj>().unwrap();
            Response::new(200).body_string(format!(
                "user_id: {}, user_name: {}",
                user_id.id, user_id.name
            ))
        }
    });
    app.listen("127.0.0.1:8080").await?;
    Ok(())
}

curl を同様に投げてみましょう。

curl -i 'localhost:8080/users?id=1&name=helloyuki'
HTTP/1.1 200 OK
content-type: text/plain; charset=utf-8
transfer-encoding: chunked
date: Tue, 24 Dec 2019 13:54:29 GMT

user_id: 1, user_name: helloyuki

よさそうです!一通り、ルーティングに欲しい機能が備わっていましたね。

その他

その他、actix-web や Rocket のように、ミドルウェアを注入する機能も存在しています。今日は入門にしては記事が長くなってしまうのでここにとどめておきますが、詳しいサンプルは下記のリポジトリにあります。

github.com

まとめ

  • tide という async-std ベースの HTTP サーバーフレームワークがあります。
  • 今回はルーティングに限ってご紹介しましたが、ルーティングについては必要最低限の機能が揃っていそうです。
  • まだまだ開発途中なので、プロダクションに使うのは難しいかもしれません。
  • 今後の開発の進捗に期待!
  • また、ビルド用のテンプレートを用意したリポジトリも作っておきましたので、ぜひ上のコードをコピペして遊んでみてください!github.com
  • みなさま良いお年を!

*1:ちなみに、この記事は2019年12月25日時点での tide の概況についてのものであり、今後 tide のデザインは大きく変わっている可能性があります。直近でもまずまず大きな変更が加えられているなど、開発は活発であるもののまだまだ安定していない状態といった感じでしょうか。

*2:Rust の非同期処理基盤について詳しく知りたい方は、こちらの記事がおすすめです: https://tech-blog.optim.co.jp/entry/2019/11/08/163000

【競プロノート】bit全探索を学ぶ

全探索にもいろいろ種類があるそうで、今日は bit 全探索という方法を勉強したのでそれについてまとめてみます。まとめないと忘れる。

解きたい問題

この記事に載っている部分和の問題を解きます。説明のために問題文を拝借します🙏🏻

qiita.com

n 個の正の整数 a[0],a[1],…,a[n−1] と正の整数 A が与えられる。これらの整数から何個かの整数を選んで総和が A になるようにすることが可能か判定せよ。可能ならば "YES" と出力し、不可能ならば "NO" と出力せよ。
【制約】 ・1≤n≤100 ・1≤a[i]≤1000 ・1≤A≤10000
【数値例】 1)  n=3  a=(7,5,3)  A=10  答え: YES (7 と 3 を選べばよいです)

2)  n = 2  a=(9,7)  A=6  答え: NO

解き方のアイディア

普通に解こうとすると、まず与えられた文字列を split して、「+」を入れられる位置を全部網羅して…といった解法になると思います。が、それは少しスマートではないように思えます。ここで出てくるのが、bit 全探索という解法です。ただし、bit 全探索は少々コストの大きい計算で、たとえば n = 100 くらいになると計算時間は膨大です。*1

bit 全探索は何をする方法?

今回の実装では、指定した数 n - 1 の部分集合をすべて探索できます (0-indexed です)。具体的には、n = 2 だった場合、{0, 1} についての部分集合を全探索します。つまり、({φ},) {0}, {1}, {0, 1} を全探索してリストアップしてくれるというすぐれものです。

ちなみに、集合 A のすべての部分集合からなる集合を A の冪集合と呼びます。集合 A = {0, 1} があった際の冪集合は、先ほどの結果を利用して P(A) = {φ, {0}, {1}, {0, 1}} と記述できます*2。bit 探索ではこの冪集合を求めていると考えてよいと思います。

通常の全探索であれば計算量は O(4n) になりますが、この bit 全探索を用いれば、計算量は O(3n) に落ちます。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 2;

    for (int bit = 0; bit < (1 << n); bit++) {
        vector<int> S;
        for (int i = 0; i < n; i++) {
            if (bit & (1 << i)) {
                S.push_back(i);
            }
        }

        cout << bit << ": {";
        for (int i = 0; i < (int)S.size(); i++) {
            cout << S[i] << " ";
        }
        cout << "}" << endl;
    }
}

出力結果は、

$ ./bit_search_prac
0: {}
1: {0 }
2: {1 }
3: {0 1 }

と出てきます。また、n = 5 とすると、集合 A = {0, 1, 2, 3, 4} となります。したがってその冪集合 P(A) は、下記のように出力されます。

$ ./bit_search_prac
0: {}
1: {0 }
2: {1 }
3: {0 1 }
4: {2 }
5: {0 2 }
6: {1 2 }
7: {0 1 2 }
8: {3 }
9: {0 3 }
10: {1 3 }
11: {0 1 3 }
12: {2 3 }
13: {0 2 3 }
14: {1 2 3 }
15: {0 1 2 3 }
16: {4 }
17: {0 4 }
18: {1 4 }
19: {0 1 4 }
20: {2 4 }
21: {0 2 4 }
22: {1 2 4 }
23: {0 1 2 4 }
24: {3 4 }
25: {0 3 4 }
26: {1 3 4 }
27: {0 1 3 4 }
28: {2 3 4 }
29: {0 2 3 4 }
30: {1 2 3 4 }
31: {0 1 2 3 4 }

といったように、すべてのパターンを網羅して出してくれます。初めてみたときちょっと感動しました。1行1行の結果を配列にしてもたせておいて、すべての項を足し上げれば、部分和問題が解けそうな気がしてきますね🙂

実際に使ってみる

まず解いてみた

実装そのものは決して難しくはありません。2重ループを回すだけです。最初のループで部分集合の全探索をし、内側のループで bit の表す集合を求めていくだけです。

#include <iostream>
#include <vector>

using namespace std;

int n;
int a[25];
int A;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> A;

    bool existence = false;
    for (int bit = 0; bit < (1 << n); bit++) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (bit & (1 << i)) {
                sum += a[i];
            }
        }

        if (sum == A) {
            existence = true;
        }
    }

    if (existence) cout << "Yes" << endl; else cout << "No" << endl;
}

この結果、

$ ./total_sum
3
7 5 3
10
Yes
$ ./total_sum
2
9 7 
6
No

記事と同じような期待通りの結果が得られます。

しかし、中でイマイチどういった操作を行っているのか腑に落ちませんでした。そもそも今回のように bit 演算を利用するとなぜ、部分集合を出力できるのでしょうか?原理を知る旅に出ましょう。

原理がわからない!

わからない点を整理します。

  • 最初のループの条件がいきなり黒魔術: for (int bit = 0; bit < (1 << n); bit++) がわからない。具体的には、(1 << n) で何が得られているのか?
  • if (bit & (1 << i)): 条件分岐に使用しているので、たとえば真が存在するなら bit & (1 << i) が 1 になるタイミングがあるのだろうけど、これはどういう原理で起きているんだろう?

ここから Playground が便利な関係で Rust で説明します(笑)。

シフト演算

(1 << n) の正体はシフト演算です。

まずシフト演算の一般的な話ですが、2進数において、ビットの位置をずらす演算をシフト演算と呼びます。左にずらずと左シフト、右にずらすと右シフトです。ちなみにコンピュータは内部はすべて2進数で表現されているので、1ビット左にずらすと任意の数値の2倍を得られ、1ビット右にずらすと任意の数値の1/2倍を得られます。

次に 1 << n をすると何が得られるかという話ですが、これは 2n を得る計算をしています。1 から n ビット左にずらすと得られる値を取得しています。Rust のコードですが、実際に動かしてみてみましょう。

fn main() {
    let bit1 = 1 << 1;
    let bit2 = 1 << 2;
    let bit3 = 1 << 3;
    let bit4 = 1 << 4;
    let bit5 = 1 << 5;
    
    println!("{}", bit1);
    println!("{}", bit2);
    println!("{}", bit3);
    println!("{}", bit4);
    println!("{}", bit5);
}

この結果は、下記のとおりとなります。

2
4
8
16
32

21, 22, ..., 25 という結果が得られているとわかります。せっかくなのでバイナリでも取得してみましょう。わかりやすさのために1も標準出力します。

fn main() {
    let bit1 = 1 << 1;
    let bit2 = 1 << 2;
    let bit3 = 1 << 3;
    let bit4 = 1 << 4;
    let bit5 = 1 << 5;
    
    println!("{:#08b}", 1);
    println!("{:#08b}", bit1);
    println!("{:#08b}", bit2);
    println!("{:#08b}", bit3);
    println!("{:#08b}", bit4);
    println!("{:#08b}", bit5);
}

結果は、

0b000001
0b000010
0b000100
0b001000
0b010000
0b100000

となり、1 がシフトした箇所に立っていっている様子がわかります。美しい🥰

ビットフラグ判定の &

bit & (1 << i) の正体はビットフラグの判定です。

ビット演算には & 演算があります。論理積を取る演算です。それぞれのビットについて両方とも1の場合は1を、それ以外の場合は0を返す演算です。ビット演算における & は、特定のビットを取り出すときに使用します。

まず「論理積を取る」について理解します。次のコードをご覧ください。

fn main() {
    let bit = 5;
    println!("{:#08b}", bit);
    println!("{:#08b}", (1 << 2));
    println!("{:#08b}", bit & (1 << 2));
}

標準出力の結果は次のようになります。

0b000101
0b000100
0b000100

&論理積の取得であったと思い出すと、

   0b000101
*) 0b000100
------------

が行われています(0b は Rust の標準出力上の話で、bit を示す接頭辞なので計算上からはスルーできます)。この掛け算を、各桁ごとに計算すると、

   0b000101
*) 0b000100
------------
   0b000100

です。1 * 1 = 1, 0 * 0 = 0, 1 * 0 = 0 です。これがまず、& 演算子の正体です。

次に、bit & (1 << i) の意味を見ていきましょう。(1 << i) については、先ほどは1 を左に i分だけシフトさせると書きましたが、 (1 << i) は i ビット目に1を立てるという意味でもあります。たとえば、1 << 3 は、3ビット目に1を立てます。つまり、bit & (1 << i) は、ビット bit に i 番目のフラグが立っているかどうかを判定しています。たとえば、bit = 3 だったときに (1 << 0) との論理積を取ると、

fn main() {
    let bit = 3;
    println!("{:#08b}", bit);
    println!("{:#08b}", (1 << 0));
    println!("{:#08b}", bit & (1 << 0));
}
0b000011 // bit = 3
0b000001 // 1 << 0
0b000001 // bit & (1 << 0)

0b000001 は、10進数では 1 を示します。つまり、0番目のビットの論理積は10進数上は 1 になります。これを if 文に入れ込めば、そのまま真偽判定に利用できますね!bit 全探索ではこれを利用していたのでした。

困ったときの標準出力

先ほどの C++ のコードにもう一度戻りましょう。上記を踏まえた上で、結局どういう動作をしているのか改めて見直してみます。状態遷移を追いたくなったら、することはひとつですね。標準出力して確かめてみましょう。コードを次のように改変してみます。

#include <iostream>
#include <vector>

using namespace std;

int n;
int a[25];
int A;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> A;

    bool existence = false;

    for (int bit = 0; bit < (1 << n); bit++) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (bit & (1 << i)) {
+                cout << "i: " << i << ", bit: " << bit  << ", (1 << i): " << (1 << i) << endl;
                sum += a[i];
            }
        }

+        cout << "sum: " << sum << endl;

        if (sum == A) {
            existence = true;
        }
    }

    if (existence) cout << "Yes" << endl; else cout << "No" << endl;
}

まず、1つ目のループで謎だった for (int bit = 0; bit < (1 << n); bit++) についてですが、たとえば n = 3 を与えると、bit < 8 が出来上がります。

bit全探索の紹介時に、 n = 100 くらいにすると計算量が、という話を書きましたが 2100 = 1267650600228229401496703205376 の計算をするので相当大きなループになってしまいます。仮に n = 16 を入れたとしても、216 = 65536 なので、それなりのループ量になってきます。さらに、中でもう一度 n = 16 なり n = 100 のループを回すので、計算量が大変ですね。

楽ちんではあるけれど、そこまで効率のよくない探索の方法ですね。

次に謎だった if 文の条件分岐の動きを見てみましょう。今回は条件分岐の中に入った際に、i の値と bit の値と 1 << i をした結果を標準出力するようにしています。また、sum もついでに取得しています。動かしてみましょう。

$ ./total_sum
3
7 5 3
10
sum: 0 // bit = 0 の出力です
i: 0, bit: 1, (1 << i): 1
sum: 7
i: 1, bit: 2, (1 << i): 2
sum: 5
i: 0, bit: 3, (1 << i): 1
i: 1, bit: 3, (1 << i): 2
sum: 12
i: 2, bit: 4, (1 << i): 4
sum: 3
i: 0, bit: 5, (1 << i): 1
i: 2, bit: 5, (1 << i): 4
sum: 10
i: 1, bit: 6, (1 << i): 2
i: 2, bit: 6, (1 << i): 4
sum: 8
i: 0, bit: 7, (1 << i): 1
i: 1, bit: 7, (1 << i): 2
i: 2, bit: 7, (1 << i): 4
sum: 15
Yes

i の遷移を見ると、 n の部分集合 (今回は配列のインデックスに対応するので、{0, 1, 2} の部分集合) をきちんと取得できています。n = 3 だったとき、部分集合は {φ}, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2} ですね。バッチリ取得できています。あとはこれと、もともとの入力の [7, 5, 3] という配列とを対応させて足し上げ、合計値が10であるかどうかを確かめれば大丈夫です。

ビット演算の左シフトが、1インクリメントすると1つ左のフラグを1に変えていくことを利用して、部分集合を上手に取得できてしまうアルゴリズムを今回は学びました。ビット演算すごい!

参考記事

*1:ちなみにそういうときは DP を使用するようです。もしかすると、DP をそもそも使う問題なので、慣れてしまえば bit 全探索である必要はないのかもしれません。

*2:P = Power で冪の意味。

今年読んだ技術書(2019年)

今年も多くの技術書を読みました。その中で印象に残ったものをご紹介したいと思います。今年は忙しくて休日しか時間がなかったので、読んで知識を体系的に整理できたと思った本の冊数は少ないですが…

Functional Programming

2019年の4月くらいに5年目がはじまるということでやりたいこととしてあげたうちのひとつに、「関数型プログラミングについて深堀りする」というものがありました。その文脈で何冊か読みました。

Debasish Ghosh の書いた『Functional and Reactive Domain Modeling』は、いわゆる DDD によるアプリケーション構築をどう関数型に仕上げていくかを紹介してくれるいい本でした。これまで、Reader や Kleisli、Free などは名前を知ってはいたものの、実際のアプリケーションでどのように使っていったらいいか、想像がついていませんでした。しかしこの本を読んだことによって、アプリケーションの中でそれらの道具がどう使われるか、コード込みでわかるようになりました。この本は、関数型プログラミングのエッセンスである「小さな汎用性の高い部品を上手に組み合わせながら、大きいアプリケーションを作り上げる」を学習する上で非常にいい構成を取っていると思います。社内では私がこの本を紹介したことがトリガーとなり、この本を使った読書会も開かれており、私もそこに参加しています。

Miran Lipovača の『すごい Haskell たのしく学ぼう!』も読みました。本腰を入れて Haskell をやったのは今年が初めてです。最近、型システムや関数型プログラミングの理論周りに関連する論文を読む機会が増えてきており、その中に Haskell のコードが登場してくるものの、読むのに毎回 Google していました。ということで、せっかくなので勉強してみよう!ということで勉強しました。現状のわたしの Haskell 力は、「読めるけど」「1からはスルスル書けない」です。見ながらは書けるんだけど。この本は関数型プログラミングに登場してくる道具たちを細かく解説してくれていて、関数型プログラミングの入門にもいい本だと思いました。

また、Haskell のような言語を扱い始めると登場してくる「モノイド」や「モナド」の数学的な意味が知りたくなって、野崎昭弘『なっとくする群・環・体』や Saunders MacLane の『圏論の基礎』も読んでみました。先日書いた記事の通りで、モノイドやモナドについての数学的な側面が、ほんの少しだけ分かるようになってきました。圏論の本はまだ全然読み進めている最中ですが、「自己関手の圏におけるモノイド対象」と言われてもなんとなくどういう意味合いがあるのかがわかるようになってきました。これらの本を学ぶ中で、数学という学問がそもそも何を議論していて、それがどうプログラミングという分野に応用されてきたかがなんとなくわかってくるのがとてもおもしろかったです。

全体的に、関数型プログラミングの勉強については、今年は実りの多い年だったと思います。ただまだまだ Haskell で行うような型レベルプログラミングについては慣れていない面が大きく、来年はそちらにチャレンジしてみたいなと思っています。

Kubernetes

今年は仕事で Kubernetes にはじめて取り組みました。私の部署はとても恵まれていて、Kubernetes のプロが多くいます。彼らにすべてを託してもよかったのですが、何もわからずに議論しても何の実りもないと思ったので、自分でも勉強することにしました。同僚の @amsy810 さんが書いた『Kubernetes 完全ガイド』を読みました。Kubernetes は、私のようなインフラ・ネットワーク苦手系アプリケーションエンジニアに武器を与えてくれるすばらしいエコシステムです。Kubernetes そのものはとても広大ですが、完全ガイドはその名の通り、完全にガイドしてくれます。この本を読みながらコツコツエクササイズして、家で遊びながら楽しく学ぶことができました。

Distributed Systems

今年は一冊決定版が出ました。Martin Kleppmann の『Designing Data-Intensive Applications』です。夏くらいに日本語版も出ていたんですね。分散システム(大量のデータ、大量のアクセスを何個かノードを分けてさばく、くらいの意味に捉え直すといいでしょうか)については、これまでその場しのぎをして何度か乗り切ってきたのですが、この本を読んではじめて体系的に学ぶことができました。この本を読んで思ったことは、「道具は先人たちがたくさん用意しているのだから、あとはそれらの特徴を学んで、適切に道具を使いこなしていこう」でした。また、高度な分散システムは、それ自身が何をしているかを把握するのがとても難しくなってきています。1つのノードで障害を起こすと、それがバタフライ・エフェクトのように広く波及してしまいます。こういった複雑な問題に立ち向かう道具もたくさん用意されており、それを学ぶという点でもすばらしいですし、またそもそもそういった道具を適切に使いこなせば未然に防ぐことのできる問題も多いでしょう。私のように決して分散システムのプロではなく、知識もなく、闇雲に複雑性と戦っていたエンジニアを巨人の肩に乗せてくれるすばらしい本でした。

また、Brendan Burns の『分散システムデザインパターン』も、今の時代には必読だと思いました。サイドカーなど、分散システムを構築する際にわりと前提として語られがちな用語をひとつひとつさらっていくことができます。私のように、アプリケーションエンジニアだけれどもシステムアーキテクトもつとめていて、けれどもコンテナ側の知識が若干怪しくて議論に参加できないという人におすすめできる本だと思います。

Designing Software

ソフトウェア周りをどうデザインすべきかについては、今年は一冊いい本があり、人にも多くお薦めしました。John Ousterhout による『A Philosophy of Software Design』です。邦訳はまだ出ていない感じですかね。洋書を読むことに抵抗のない方は、ぜひ読んでみてほしいです。私は新人さんにとりあえずお薦めしています。この本では、「なぜソフトウェアデザインをしっかり行わなければならないか?」という問いを立て、その答えのひとつとして、「複雑性への対処」をあげます。複雑性があるというのは、変更をした場合にそれが他の多くの場所に伝播してしまうような状態や、あるいはコードを読む上で認知負荷が高い状態をそうであると定義しています。私がハッとさせられたもののよく考えさせられたのは deep module と shallow module の章で、これらの違いに意識したことがなかったため、これまでのコードを思い返させるいい章だったと思いました。同時に実現性の難しさも感じましたが。

Computer Science

プログラミング言語の基礎的な理論を深めたいと思っているので、猪股 俊光、山田 敬三による『計算モデルとプログラミング』を読みました。この本は大学の講義ノートを本に起こした本のようですが、大学ではこのくらい濃密な授業が行われていて羨ましいです。計算モデルにはいくつか種類があり、それらの間の計算能力には差がないことを一旦説明したあと、チューリングマシンについてまず議論し、そこから抽象機械型計算、命令型計算、関数型計算として帰納的関数λ計算、最後にPrologのような論理型計算をていねいに紹介していきます。プログラミング言語のモデルにどのような種類のものがあるかを整理できたいい機会でした。まだまだマスターできているとは言えませんが、何度も振り返りつつ自分で使いこなせるようにやりきりたいと思っています。

コンピュータそのものやネットワークに対する理解も深めたくて、引き続き何冊か読みました。『CPUの創りかた』は言うまでもない名著だと思いますが、はじめて読みました。私は電子回路は中学生の知識で止まっていたのですが、本書は順を追って説明してくれて大変実りある読書になりました。CPU 周りにでてくる用語はこれまでさっぱり知らなかったのですが、この本を読んでだいぶ何をしている存在かわかるようになりました。また、『マスタリングTCP/IP』と『TCP技術入門』も読みました。今回会社のゼミでネットワーク周りを扱うことになったのですが、TCP/IP の仕組みをさっぱり知らず、これも「それではまずい」と思って読みました。「輻輳制御」を読めるようになったので、入門は突破したと思います(笑)。

林 高勲、川合 秀実による『作って理解するOS x86系コンピュータを動かす理論と実装』も読み進めています。前半の OS に関する座学の章を読むだけ、という読み方をしていますが、それだけでも十分実りある読書になっています。ここまで細かく踏み込んで解説してくれている本はなかなかないと思います。さすがに自分で1から作る時間はまだ確保できていませんが、やりたいことの優先度を整理していつか取り組みたいと思っています。

群、モノイド、半群

数学を勉強している最中に話が出てきたので、少しまとめておこうと思います。理解に誤りがあったら教えて下さい🙇‍♀️ なお、私はモノイドやモナドといった言葉は、その成立条件について Functional Programming in Scala などの本でさらっと理解しています。一方で数学的な意味として一体どのようなものがあるのかなあということが気になって調べたという背景です。

群とは

群とは、集合 G とそこで定義される2項演算 x△y を組み合わせた代数系 (G, △) が、次の3つの条件 (群の公理) を満たすものです。補足ですが、△にはたとえば「+」のような演算が入ります。

  1. 結合法則: x△(y△z) = (x△y)△z
  2. 単位元をもつこと: x△e = e△x = x となる e をもつこと
  3. 逆元をもつこと: x△y=y△x=e となる要素 y をもつこと

ちなみに、参照した本では直前に「演算が閉じていること」を書いてあったのですが、3つの条件さえ満たせばいいよ、と書いてありました。が、ネットで改めて調べてみると、「演算が閉じていること」も条件に含まれそうな気がします。なので書き直すと、下記のようになるかと思います。

  1. 集合 G に対して一意的な演算 (△) が成り立ち、かつその演算に関して集合 G は閉じている。
  2. (下記、そのような演算に対して) 結合法則: x△(y△z) = (x△y)△z
  3. 単位元をもつこと: x△e = e△x = x となる e をもつこと
  4. 逆元をもつこと: x△y=y△x=e となる要素 y をもつこと

モノイドとは

モノイドは実際のところ、「1. 演算が集合内に閉じていること」「2. 結合法則」と「3. 単位元をもつこと」を満たす存在でしたね。なので、群よりかは少し「弱い」存在です。

半群とは

半群は、英語では Semigroup というそうです。私は cats の中でこの単語を見たことがありました。

半群は、「1. 演算が集合内に閉じていること」「2. 結合法則」を満たす存在です。なので、やはり群よりは「弱い」存在で、かつモノイドよりも「弱い」存在です。

余談) マグマ

調べていたら、「1. 演算が集合内に閉じていること」を満たす存在にも名前があるようです。マグマ (Magma) というそうです。勉強になりました。ブルバキが導入した用語なんですね。私はブルバキは聞いたことがあるぞ。

さらに余談) 群は加算のことである…?

ネットの記事を読んでいると、群は「加算 (+) のことである」と定義する記事をたまに読みます。しかし、これは前提条件が抜けていると思います。こう書くときに乗算を含まないのは、乗算の逆元を整数 Z の限りでは定義できないからです。しかし、有理数 Q まで拡張すれば、乗算の逆元は定義可能になります。乗算の単位元 e は 1 ですが、a * 1/a = 1/a * a = 1となるためです。したがって、「群は加算のことである」というテクストは、半分正解で半分誤りの可能性があるため、「整数の範囲で」「群は加算のことである」と説明するのが正しいのかなと思いました。

参考