(a + b - 1) / b で a / b の切り上げを計算する

整数 a, b に対して、 a / b の切り上げを計算したい場合 (a + b - 1) / b するという小技が競技プログラミングではよく使われる。 なぜこれで切り上げが計算できるのか、良い感じの説明が検索しても出てこなかったので自分なりの理解を書いておく。

以下 / は一時的に分数の記号として、 b = 3 , a を 3から1ずつ増加させていく場合を考える。

3/3 = 1

4/3 = 1+1/3

5/3 = 1+2/3

6/3 = 2

7/3 = 2 + 1/3

...以下略

となるので、1 - 1 / b （b=3 の場合は 2/3) を加算して小数点以下を切り捨てれば切り上げと同じになる。

切り上げすべき場合は必ず商が繰り上がる。

切り上げすべきでない場合（上記の 3/3 , 6/3 のケース）は商が繰り上がらない。

よって、floor(a/b + (1-1/b))をすればよく、今度は / を切り捨て除算の記号として式変形すると (a+b-1)/b で同値と言える。したがってa / b の切り上げを計算したい場合 (a + b - 1) / b で計算できる。

ceil が使える言語ならそれでもいいんじゃないか？と思われるが、a, b の値によっては浮動小数点計算の誤差が発生する可能性があるので、この方法が安全らしい。なるほど。

まあ (a+b-1)/b の方がシンプルだし賢いやり方感がある。

TypeScript の共用体型は or ではないのかについて考えた

TypeScript の共用体型（Union Types）は or ではない を読み、確かによく分からん挙動だなーと思って色々調べたり考えたりしたことを書いておく。

最初に書いておくと、結論はよく分かってない。

まず、共用体型はタグ無し共用体型とタグ付き共用体型（Discriminated Unions）の2つに分けることができる。ので分けて考える。タグ付き共用体型が何を指すのかは後述する。

タグ無し共用体型

最初に、タグ無し共用体型について考える。

形状A, B に対して、A | B と A & B で定義される型の性質

そもそもの性質の整理。何かベン図を使った説明をすることが多いみたいだけど、形状*1を表す型の場合はベン図ではうまく説明できない気がしている。

• A | B は 少なくとも、A, B のいずれかの型を満たすようなプロパティを持つ（Aを満たすなら部分的にBのプロパティを持つことは許容される）

• A & B は A, B のプロパティを全て持つ形状（A, B を満たしながら他のプロパティを持つことは許容されない）

ここで、A | B は Partial(A & B)、つまり A, B のプロパティを全て持つが、省略も可能な形状と同値なのか？と思ったが、それは違う。A | B は、

• A,B のプロパティを部分的に持ち、A, B のいずれも満たさない場合は不可
• プロパティを持たない形状 {} は代入不可

type A = {
  a: string;
};

type B = {
  b: number;
};

type C = A | B;

const ab : C = {} // error 

A | B ＝ A ∪ Bという理解は正しいのか

ベン図で理解しようとすると、A | B ＝ A ∪ B 、つまり、AかBかAとB両方を満たす集合なんじゃないかと考えたくなる。

集合A を形状Aに割り当て可能な型とみるか、形状Aが持つプロパティの集合と見るかで違ってきそう。

前者で考えると、A を満たしながら B のプロパティを一部持つ形状は、A に割当不可能だし、A, B, A&B のどれにも割当不可能なので、A ∪ B に含まれないということになってしまう。「共用体型が or でない」ように思える。

後者で考えると、型を満たすかは関係なくて、単にプロパティの集合なので A ∪ B になる。すると共用体型が or であるように思える。

結局 A | B とは何なのか

少なくとも、A, B のいずれかの型を満たすプロパティを持つ形状としか言えないような。A, B のいずれかの型を実際に満たすわけでなくて、（余計なプロパティがなければ）少なくとも A, B のいずれかを満たすようなプロパティを持つ形状というだけなことが大事なのかも。

同じことを、単一の形状として、オブジェクトリテラル表記で形状の型として定義することはできない気がしている。

ちなみに type-fest というライブラリに、RequireAtLeastOne という型定義があり、見た感じ形状をA | Bすることで得られる性質を利用しているみたいだった。この型ユーティリティは1つの形状から特定のプロパティの集合を選択していずれかを必須にできるので、もっと汎用性が高い感じ。

例えば、RequireAtLeastOne<A, "a" | "b"> すると a, b のどちらかを必須にできる。

型定義の理解の仕方はこの記事 が役に立った。

タグ付き共用体型

次にタグ付き共用体型について考える。そもそもタグ付き共用体型とは何かというと、こういうやつ。

type A = {
  type: 'a'
  a: string
};

type B = {
  type: 'b'
  b: number
};

type C = A | B;

タグは、同じプロパティで定義され、値は共用体型の中で一意である必要がある。

この場合は、単純で、A | B は必ず A, B のいずれかになる。両方を満たしたり、片方を満たしながら片方のプロパティを持つことはできない。ベン図でいうと、A ∪ B から A ∩ Bを除いた集合で、形状以外の型の共用体型はこうなるはず。

なので、上の例でいうとこういうのはエラーになる。A を満たしているが、他の型のプロパティを部分的に持つことは許されない。

type C = A | B;

const c :C = {type: 'a', a: "hoge", b: 1} // error

タグ付きの場合は A | B に対する TypeScript の型推論も単純になる。(例えば a.type == 'a' で分岐させれば以降は 型が A に定まる)

ちなみに、タグを重複させるとタグ無し共用体型みたいに部分的にプロパティを持つことが可能になる。というか多分タグ無し共用体型と同じ型定義になる気がする。

type A = {
  type: 'a'
  a: string
};

type B = {
  type: 'a'
  b1: number
  b2: number
};

type C = A | B;

const c :C = {type: 'a', a: "hoge", b1: 1} // ok

*1:形状は、書籍プログラミングTypeScript で使われている用語で、オブジェクトリテラル表記で宣言される型のこと。TypeScript のオブジェクト型の他、クラスインスタンスも含まれる。多分最終的に JavaScript のオブジェクト型に変換されるものは全て含まれる

そもそも reflection とは何なのか

Go 言語を勉強していて reflection って何なんだろ、となったので調べた内容を書いておく。

そもそも reflection とは何なのか

wikipediaによると

情報工学においてリフレクション (reflection) とは、プログラムの実行過程でプログラム自身の構造を読み取ったり書き換えたりする技術のことを指す。

よく分からない。以下では reflection の概念について書いていく。（Go 言語の reflection パッケージ固有の話ではない）

自己書き換えコード

プログラムの実行過程でプログラム自身の構造を読み書きするというのはどういうことか。1つの例として自己書き換えコードがある。

プログラムはプロセッサが処理可能な機械語に変換されて動作する。例えば C言語の場合だと以下のような変換になる。

C言語 -> アセンブリ言語 -> 機械語

より変換の下流に位置している、アセンブリ言語や機械語のコードの内容をプログラムから書き換えることができれば、プログラム(ソースコード)に記述された処理とは見かけ上異なる処理*1を実行させることができる。そのようなプログラムを自己書き換えコードと呼ぶ（らしい）

例えば、C言語やアセンブリ言語で書かれたプログラムで命令が格納されているメモリを直接操作すると、その前にプログラム内で書かれた命令は意味をなさなくなる。具体例としては、自己書き換えコード(self-modifying code) 等を参照。

自己書き換えをしたいモチベーションとしては色々あるみたいで自分は低レイヤーな部分に明るくないのであまり理解できていない。とりあえず wikipedia には色々載っていた。

Brian Cantwell Smith は、このアセンブリ言語の自己書き換えコードの発想（メタプログラミング）を高級言語にも導入しようとした。これが reflection という概念の元になっているらしい。(Procedural reflection in programming languages がその論文っぽい。読んではない。)

reflection はメタプログラミング

上述のような背景があるので、メタプログラミングをしたいから reflection がある、と考えても良さそう。

メタプログラミング

ところでメタプログラミングとは何か。定義は色々ありそうだが、メタなプログラミング、プログラムをプログラムする（ある言語がある言語を読み書きする）というイメージで良いっぽい。

例えば eval に渡す文字列を組み立てるプログラムは、まさにプログラムをプログラムが書いているのでメタプログラミングの1つになると思う。 また、SQL の組み立てもそうだし、TypeScript も JavaScript のメタプログラミングになると思う。

先程の自己書き換えコードがメタプログラミングに含まれるかは微妙かもしれない（C言語がアセンブリ言語(機械語)を読み書きしていると言えるのかもしれない）

reflection を実装し、プログラム自身の構造を読み書きしたい背景として、このメタプログラミング（特に、操作する言語と読み書き対象の言語が一致している場合）に役立つからというものがあると思う。 自分は reflection の概念を Go 言語で初めて知ったが、他の多くの言語にも実装されている。例えば Java や JavaScript にもある。

なぜメタプログラミングしたいのか

じゃあなぜメタプログラミングしたいのか。特に、操作する言語と読み書き対象の言語が一致しているメタプログラミングは何が目的なのか。

TypeScript 等、別の言語を生成するならまだしも、なぜ同じ言語を取り扱うメタプログラミングが必要とされるのか。

実行時にしか分からない情報を取得したい・その情報を使った処理を行いたい

例えば、Go の場合は以下がある。

• interface 型の変数の値の型*2
• 構造体タグ (タグ名や値は任意の値を設定でき、構文がおかしい場合は実行時エラーになる）
• json 等の外部データ (を Go の型システムの世界に変換したい）

また、ジェネリックに近いことも reflect パッケージを使えば実現できる（コード例はWho needs generics? Use ... instead!の 5. Use reflection を参照）

ジェネリックのためにreflect パッケージを使うとそれなりに面倒な感じにはなるっぽいが、元々の言語仕様にないことを実現できてしまうのはメタプログラミングの力だと思う。

Go 言語の reflection について

色々と reflection の概念について書いてきた。実際の Go の reflect パッケージの取り扱い方については以下の資料が役に立ちそうなのでリンク。

• The Laws of Reflection
• プログラミング言語完全入門 13. リフレクション (期間限定)

その他参考

• Learning to Use Go Reflection — Part 2
• What is reflection and why is it useful?
• Reflection (computer programming))
• まつもとゆきひろ コードの未来（日経BP Next ICT選書） のメタプログラミングの章

*1:プログラムは記述された通りにしか動かないのであくまで見かけ上

*2:一応 reflect を使わなくてもtype assertion で特定の型かどうかの判定はできる

Go の型システム周りについてのメモ

Go の型システムについて、今理解していることを書く。もしかしたら間違っているかもしれない。

Go の型システム

• 型同士に階層がない（サブタイプ・スーパタイプのような関係がない）
  • 型は名前によって区別される。階層がないので、ある型が要求された場合にその型のサブタイプが許容されるようなことはない。
  • ただし、例外としてinterface 型の解決は形状(実装するメソッド)が一致していれば許容
• 型は named type と unnamed type に分けられる

型の割当可能性

同一の型同士の割当は以下のルールに従う。

同一の型とは、以下を満たす型を指す。

• named type 同士は名前が一致している（したがって型の実体が一致している）
• unnamed type と named type は型の実体が一致している
  • unnamed type 同士も同様

以下の表では、同一の型同士であっても割当不可な場合について☓を記載している。

\	named type	unnamed type
named type	○	☓
unnamed type	☓	○

(例) 2行目3列の場合は☓なので割当できない

// named type to unnamed type
hoge1 := "hoge1"
type a string 
var hoge2 a
hoge2 = "hoge2"
hoge1 = hoge2 // error : cannot use hoge2 (type a) as type string in assignment

ただし、interface 型の場合は例外で形状(実装するメソッド)が一致しているかどうかだけが問題になる

(例)

type c struct{}
func(p c) hoge(){}

func main(){

type hoge interface{hoge()}
var b1 hoge
var b2 interface{hoge()}

b1 = c{} // ok , named type to named type
b2 = c{} // ok , named type to unnamed type
}

複雑な型について

例えば、map[string]interface{}にmap[string]int は割当可能か？

型に階層関係の存在する言語（型システム）に慣れていると、これは割当可能ではないかと感じるが Go の型には階層関係がないので割当できない。互いに独立した無名型でしかない。

例えばTypeScriptの場合は map 型は以下のように割当できる。

const a = (b : Map<string, any>) => {};
const c = new Map<string, number>([['hoge', 1]])

a(c); // ok

TypeScript は、複雑な型（オブジェクト、クラス、配列、関数の戻り値）等はそのプロパティに関して全て共変である(=サブタイプ or 同じ型を要求すうる)とのこと*1

Go の場合は型に階層自体がないので、変性という概念もないのかもしれない。

Go は duck typing (あるいは structural typing) なのか

そもそも duck typing とは何か、その明確な定義があまりよく分かっていない。duck typing は動的型付言語に対して言う言葉らしいので、duck typing ではなく structural typing という言葉が正しいらしい。

例えば TypeScript は structural typing と言われ、いわゆる named type (名前型) はサポートしていないので以下が通ってしまう。

type a = string
const b = (c :a) => {};
b('hoge'); // ok 

Go は interface 型については structural typing だが、上でも書いたとおり名前型が使えるという点では完全な structural typing な言語とは言えないのでないか？ その言語が structural typing である、というとき、それはどういう意味で使われているんだろうか？

Does Golang use structural typing, nominal typing, or both?

上記の回答によると、Go に関しては両方ということになるらしい。まあ確かにそうである。

これも Go が行っている試みの1つなのかもしれない

There are many things in the Go language and libraries that differ from modern practices, simply because we feel it's sometimes worth trying a different approach.

Why does Go not have assertions? より引用

参考

Named and Unnamed Types

*1:プログラミングTypeScript P122

シェルスクリプトの任意の箇所で git の branch 名をあいまい検索するエイリアスが便利

環境

• mac OS 10.14.6
• zsh 5.3 (x86_64-apple-darwin18.0)

モチベーション

git push や git checkout など、branch 名を タイプしないといけないときに正確に branch 名を入力するのが面倒くさい

結果

B と書かれている箇所にあいまい検索で見つけた branch 名を挿入する

設定

.zshrc に以下のエイリアスを置く

alias -g B='$(git branch -a | fzf)'

• fzf のインストールは必要
• -g オプションでコマンドの先頭以外でもエイリアスが効くようにする

その他

remote にしか branch がない場合は git checkout -t B すると 対象を upstream に指定しつつローカルに同名の branch を作れる

GraphQL と Apollo Client / Server を学ぶためにやったこと

GraphQL と Apollo Client / Server を学んだので何をしたかを書いておく。

GraphQL

読んだ本

• 初めての GraphQL
• GraphQL スキーマ設計ガイド

最初に「初めての GraphQL」で概要を掴んだ。ちなみにこの本は Apollo Client / Server についても書かれている。

併せて、設計パターンや実際の開発で課題となるテーマを把握した。(最初は気づかなかったが、設計ガイドは一部が「初めての GraphQL」 の付録にもなっている)

実装

「初めてのGraphQL」には簡単なWeb アプリを開発するチュートリアルがあるので、それを写経した。多分不完全。

GitHub - pokuwagata/photo-share-api

感想

• GraphQL + TypeScript はフロントとバックエンドの分業に良さそう。ただし適切なschema の設計と継続的な改善が必要で、経験がないと辛いことも多そう。
• クエリの書き方をよく忘れる

Apollo Client / Server

GraphQL の実装として、Apollo Client / Server がデファクトらしいので GraphQL を学ぶなら Apollo も必須となる。

読んだ本 / ドキュメント

• 初めての GraphQL
• Apollo ドハマリ事件簿
• Apollo 公式
• apollo-tooling

Apollo については「初めての GraphQL」で概要は掴んだが、実際に手を動かすときに公式のドキュメントを参照することが多かった。

apollo-tooling は個人的に苦手な codegen という schema と クエリから TypeScript の型定義を生成するコマンドと格闘したためよく読んだ。

実装

• portfolio-go-mysql-docker-webapp

• apollo-bff-todo-mvc

既存のポートフォリオに無理やり BFF 層を追加して、一部のリクエストを GraphQL に置換してみた。logging も少し試した。

0 → 1 を少しやってみたかったので所謂 todo-mvc を 実装しようとした。単純に全てのリクエストを Apollo Server で処理するだけだとあまり面白くないので、 apollo-client で local state managemet を試してみた。

Client / Server の両方で schema を定義して TypeScript の型定義を生成して... という流れを経験できた。そして apollo-client の local state management は辛いという結論に達して挫折した。

現状 apollo-client で local state management するのは時期尚早感あるのかな...

- apollo-client-devtools が client schema 対応してない（と思う）
- apollo-codegen は local resolver の型定義生成しない

— メロン (@yn2011) 2020年5月2日

あと Graph Manager というサービスも触ってみた。課金しないと全然試せることが少ないけど、本番運用するなら必須の機能が簡単に使えるっぽい。

Graph Manager 触ってみた pic.twitter.com/Qh0hljYz6e

— メロン (@yn2011) 2020年4月5日

感想

• 実際に手を動かすと関連する ライブラリ が色々見つかり最初辛い。
  • graphql-code-generator
  • graphql-schema-linter
  • graphql-modules
  • graphql-config

graphql-code-generator は TypeScript 使うならほぼ必須。linter は linter としての機能というより error が分かるのが嬉しい。VSCode をちゃんと設定すればエディター上でも分かるようになるんだろうか。

graphql-modules は良さそうだけど、設計がこの ライブラリ にロックインされそうな印象がある。

graphql-config は使っていないが、GraphQL 関連のライブラリとかエディタ毎に設定ファイルを独立して書かなきゃいけない傾向があり、辛いので一括で管理できるようにしてくれるっぽい。確かに設定ファイルどんどん増えてくるのは分かる。

• schema と 型定義の自動生成により、関数型プログラミングのスタイルで開発できる。

  • 最初に問題を解決するための入力と出力の型を定義して、その型を満たす実装を埋めていくというスタイルの開発が容易に行える（少なくともApollo Server側は）
  • また、型定義を元に VSCode が補完・エラー表示してくれないと Reactと Apollo を使って実装していくのはそもそも現実的なのか？という印象もある

• React の Component に GraphQL のクエリを紐付けて管理するのはコンポーネント指向感あって良い。ただし複雑な Web アプリケーションだと色々辛い部分もあるんだろうな...

• 正直 GraphQL の導入は Apollo Server の実装よりもフロント側の方が考えなきゃいけないことが沢山あって大変そうという気持ちになった（まあ今回のサーバー側は REST API の中継しかしてないからかもしれないけど...）

AtCoder Beginner Contest に参加し始めた

AtCoder が毎週開催している AtCoder Beginner Contest (以下ABC)に参加するようになって 1ヶ月程度経ったので何かその辺りのことを書いておく。

今の成績

Rating 132 の灰色

なぜやるか

• 新しい趣味が欲しかった
• 実装力の強化
• 有給消化 + GW で25連休中のため比較的時間がある*1

始める前の実力

コンテストに関係しそうなやつだと

• 競技プログラミング未経験
• 高校数学は大体分かる（ただし整数問題は分からない*2）、大学の数学はほぼ忘れた
• 電子・情報系の学部にいた。ただしコンピュータ・サイエンスはそんなに身に付いていない*3
  • 計算量・ビッグオー記法の概念・数学的な定義は何となく分かる
• 業務でコード書くエンジニアとしての経験は3年ぐらい
  • C++ は書いたことない
  • 業務はフロントエンドを担当することも多く、複雑なアルゴリズムの実装が要求されたことはない

ABC 初参加前にやったこと

• AtCoder に限らず、所謂競技プログラミングは C++ が主流とのことだったので、まずは C++ の環境構築と学習から始めた（ちなみに、この選択は正しくて、ほぼ全てのAtCoder 関連の記事・解説放送、書籍は C++ を前提にしているので C++ やったことなくても学習した方が絶対効率よく学べる）

環境構築

VSCode の場合について書く。以下が揃えば良い感じに C++ でコンテストに参加できる。

• 拡張のインストール
  • ms-vscode.cpptools
  • formulahendry.code-runner

code-runner (C++17 実行) の settings.json

  "code-runner.executorMap": {
    "cpp": "cd $dir && g++ -std=c++1z $fileName && ./a.out",
  },

• <bits/stdc++.h> を利用可能にする

  • C++ の標準ライブラリが大体使えるようになるので便利（というかほぼ必須）
  • Visual studio codeで競プロ環境構築[mac OS] を参考にする。ちょっと面倒くさい。

• 標準入力/外部ファイルから入力を受け付けてデバッグを行えるようにする

  • vscodeでstdinを扱える環境構築を参考にする。work around 感は強い。

• atcoder-cli

  • コンテスト用のディレクトリの作成/テスト実行/提出 が可能（たまに動作しない場合もあるけど...）
  • コンテスト参加時や過去問を解く時に便利

AOJ ITP1 を解いた

自分の場合は C++ をまったく知らなかったので、レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】 でオススメされている通りに AOJ の ITP1コースを解いて練習しておくことにした。

愚直に9割ぐらい解いたんですが、注意点としては

• 解答例は C++14 or 17 を見るようにする (標準ライブラリに慣れる)
• ある程度プログラミング経験がある場合は全部やらなくていいと思う。 とりあえずA,B 問題に取り組んで解説放送聞いたり提出されたコードを読んだほうが実践的かも
• ITP1 では標準入力の受け取りに慣れるのが1番大事かも

ABCに初めて参加した

自分はこの時点でA, B 問題までは解けた。コンテスト自体の知識は参加して覚えたほうが早い。（提出方法、問題の形式、誤答するとペナルティが発生する等）

スニペットを用意した

ABC の解説放送のライブコーディングで使われているスニペットを参考にした。自分の場合は start とタイプすると以下が挿入されるように設定している。

  "start-template": {
    "prefix": "start-template",
    "body": [
      "#include <bits/stdc++.h>",
      "#define rep(i,n) for(int i=0; i < (n); i++)",
      "#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)",
      "using namespace std;",
      "using ll = long long;",
      "",
      "int main() {",
      "  $0",
      "  return 0;",
      "}"
    ],
    "description": "basic"
  },

いちいちテンプレートファイルを準備して問題毎にコピーして新しく書き始めるよりも早いと思う。

コンテストで学んだこと

主に数値の取り扱い。Webアプリケーションを書いているだけだと意識することが少ない（気がする）

でもコンテストでは必須の知識だと思う。（A, B 問題でそこを狙ってくるテストケースや問題設定が多いので）

• int (符号付き32bit 整数) の最大値は 2³¹ -1 で、大体 2.14 * 10⁹ で 、10桁
• long int (符号付き64bit 整数)の最大値は 2⁶³ -1 で、大体 9.22 * 10¹⁸ で 、19桁
• 除算は小数部切り捨て（例 5/2 = 2)
  • 切り上げする場合は (a+b-1) / b →説明
• 最終的な計算結果はオーバーフローしなくても計算途中の評価がオーバーフローすると駄目（例 a * b - c で a * b がオーバーフロー）

あと、AtCoder のコンテストで C++ で解答する場合は計算機の性能は大体 10⁸ step / sec ぐらいと想定すると良いみたいです。（例えば O(N) でも 10¹⁸ step だと 2sec 以内には絶対に収まらない）

ここに書いてた

今やっていること

週に4時間もコンテスト関連には時間使えていないと思う。土日にコンテストに参加して次のコンテストまでに解説放送聞いて実装してみたりぐらいが限界。

ABC に参加する

忘れない限りは毎週参加している。C, D問題は実戦で学ぶ感じになっている。C問題は慣れれば解けるようになってくる印象。実はそんなに高度なことを要求していないことが多い。

解説放送を聞く

神コンテンツ。これがなければ ABC 止めてたかも。模範解答自体はコンテスト終了と同時に公開されるが、大抵読んでも理解に時間がかかるか何も得られないので、最近は始めから解説放送を聞いている。（これは自分の読解力の問題もある）

D 問題以降は正直ちゃんとアルゴリズム等の実装経験積まないと対応できないことが明らかなんだけど、それをする時間をまとめて取れなさそうなので 解説放送に出てきたものから順に学んでいこうかと思っている。まあいつかは D で要求される範囲全部カバーできるようになるんじゃないかな...

今後の目標

• コンテストに参加し続ける（後5回ぐらい参加で茶色になりそう)
• C, D 問題の正答率を上げる
• 楽しむ

*1:とはいえ次の業務で使う技術や知識のキャッチアップの方が優先なので、余暇を全て費やすことはできないが

*2:整数問題の対策が必要なのは当時は東大ぐらいだったのでやってない。今もそうかもだが

*3:C 言語でダイクストラとかバブルソートとか実装する演習があった記憶はある。当時は理解していた。今は実装は無理