読者です 読者をやめる 読者になる 読者になる

自作言語処理系制作 1. はじめに

はじめに

自作スクリプト言語処理系を作成します。

モチベを少しでも維持するため日記代わりに記事を書きます。

週一くらいで記事を書いていきたい。

目的

勉強と興味です。

作成する言語は実用性を意識せず、「とにかくミニマルに」を心がけます。

どんな言語にするか

今回の主題です。

自作言語を作成するにあたってどんな言語にするのかを決めます。

1. スクリプト言語 or プログラミング言語

言語には大きく分けて機械語コンパイルされるプログラミング言語インタープリタで実行されるスクリプト言語の2種類が存在します。(不適切な説明)

機械語の知識が現状ほぼ皆無なのでインタープリタで実行されるスクリプト言語にします。

2. 静的型付け or 動的型付け

静的型検査を行う静的型付け言語を選択します。

これは最小限という方針には反しますが、動的型付けの言語は既に作成したことがあるためです。

セミコロンレス or セミコロン

最近は式区切りのセミコロンが省略可能な言語が流行っている気がしますが、あえてセミコロンの省略を許可しない言語とします。

これは構文解析器の作成を簡単にするためと、個人的にセミコロン省略が嫌いなためです。

言語の特徴

前述の通り最低限の機能を実装します。

よって、使用可能な型は 整数型IntVoid とそれらを組み合わせて出来る関数型の3種類のみとします。

また、言語機能は 変数/関数定義の他、ひとまずとしてif式のみとします。(Scalaなどと同様 ifを文ではなく式とします。)

実装言語

この言語の処理系はD言語で実装します。これは完全に好みです。

D言語という選択の理由は 「ある程度の愛着があり」、「静的型付け言語であり」、「標準で文字列をUTF-32で扱うことの出来る」言語だからです。

C++もこの条件に合致しますが、正直煩雑になってしまうためD言語を選びました。

ぼちぼちやっていきます。

はいふり 人称行列

はいふりのキャラクター間の一、二、三人称を纏めています。

docs.google.com

現在本編とOVA前編終了時点まで、加えてローレライの乙女たち3話まで完了しています。

収集の条件は大まかに、

  • 呼び掛ける側が呼ばれる側の名前を認識していること。

    (例えば、2話気絶しているミーナに対して岬が呼び掛けた「『あなた』、生きてるよ」などはこの時点で岬がミーナの名前を認識していないため含みません)

  • 呼び掛ける側が呼ばれる側の個人を特定していること。

    (『あなたたち』の様に呼ばれる側が複数形のものなどは含みません)

の二つです。ただし、直前の会話文との重複を避けるために用いられる『あなた』などは例外的に含まないものとします。

また、特別な状況下での呼び掛け(幼少期の ましろ から真霜に対する『お姉ちゃん』など)の場合は可能な限りその話数を併記します。

何かの役に立てばいいです。

数式微分機の作成 と D言語での木走査

モチベーション

無性に微分がしたくなった。

結論

出力が頭悪い。

D言語と振り分け式の外部訪問器は相性がいい。

特に数学的におもしろい話はありません。

はじめに

偏導関数値を求める方法には、数値微分 や (トップダウン/ボトムアップ)型自動微分などがありますが、今回は具体的な値を求めたいわけではないので数式微分を行います。

方法

式木で表される関数を、再帰的に微分することで偏微分関数を表す式木を作ります。

まず、ある程度簡単な関数であれば、三角関数のようなより単純な関数の組み合わせや四則演算で表すことが出来ます。

それらの 関数の組み合わせ に対する微分結果の式木を求めることで微分を行います。

例えば、y(x) = f(x) + g(x) という関数の場合、

 y' = f' + g'

というふうに偏導関数を求めることが出来ます。以下に幾つかの関数の組み合わせに対応する微分結果を挙げます。

微分 微分結果
加算:  y = f + g    y' = f'+g'
乗算:  y = fg       y' = f'g + fg'
正弦:  y = sin(f)   y' = f'cos(f)
余弦:  y = cos(f)   y' = -f'sin(f)
冪乗:  y = f^{g}    y' = f^{g}(g'log(f)+\frac{f'}{f} g)
対数:  y = log(f)   y' = \frac{f'}{f}

このような規則に従い式木を走査し組み直すプログラムをD言語で作成しました。

https://github.com/Ryooooooga/DifferentialCulculator

では試しに  1/tan(x)微分してみます。

出力は以下の様になります。

((((-1)*sin(x))*sin(x)^{(-1)})+(cos(x)*(sin(x)^{(-1)}*((cos(x)*(-1))*sin(x)^{(-1)}))))

はい、出力の整形を面倒くさがったため括弧地獄になっています。

これを適当に手動で整形すると、

 -\frac{sin(x)}{sin(x)} - cos(x)\frac{\frac{cos(x)}{sin(x)}}{sin(x)}

の様になり、 1/tan(x)微分結果である

 -1 - \frac{cos^{2}(x)}{sin^{2}(x)}

と一致することがわかります。

まとめ

一応式木を走査して最低限無駄な項を切り落とすようにはしているのですが、出力結果が見れたものではないので、出力の式木に対してより高度な最適化を施す必要がありそうです。

木構造の走査と戦略

デザインパターンっぽい話です。

式木や構文木のような木構造の走査の戦略にはいくつかのパターンがあり、それぞれにメリット、デメリットが存在します。

下に、よく使われる3つのパターンを挙げます。

また、それぞれに例として簡単なC#ソースコードを載せます。

1. 走査メソッド(Interpreter パターン)

最も直感的なパターンです。

式木のノードを表すクラスが走査メソッドを持ち、再帰的に子ノードのメソッドを呼び出すことで木を走査します。

// ノード
interface INode {
    // 走査メソッド
    double Eval();
}

// 加算
class Add: INode {
    private INode left, right;
    
    public Add(INode left, INode right) {
        this.left  = left;
        this.right = right;
    }
    
    // 走査メソッドの実装
    public double Eval() => this.left.Eval() + this.right.Eval();
}

// 乗算
class Mul: INode {
    private INode left, right;
    
    public Mul(INode left, INode right) {
        this.left  = left;
        this.right = right;
    }
    
    // 走査メソッドの実装
    public double Eval() => this.left.Eval() * this.right.Eval();
}

// 数値
class Num: INode {
    private double value;
    
    public Num(double value) {
        this.value = value;
    }
    
    // 走査メソッドの実装
    public double Eval() => this.value;
}

class Prog {
    public static void Main() {
        // 1*2 + 3*4
        var tree = new Add(
            new Mul(new Num(1), new Num(2)),
            new Mul(new Num(3), new Num(4))
        );
        
        System.Console.WriteLine(tree.Eval());
    }
}

実行結果

14

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

上の例では、「加算」、「乗算」、「数値」というノードクラスがそれぞれ Eval メソッドを実装することで木の評価を行っています。

メリット

  1. わかりやすい

    仕組みが単純で動作がわかりやすいです。

  2. 引数をとれる、返り値を返せる

    基底クラス(インターフェース)の Eval メソッドの定義を変更することで自由な個数の引数をとる様にしたり、返り値の型を変更することが出来ます。

  3. クラスの内部構造を隠蔽できる

    メソッドにより走査するため、クラス内部の情報を外部に公開する必要がありません。

    上の例で言えば、Num クラスは内部にどのような値を保持しているのかを外部に公開していません。

  4. 木クラスの追加が容易

    上の例に平方根を表すノード Sqrt を追加する場合、SqrtEval メソッドを適切に実装するだけで平方根を含む式木の評価を行えます。

デメリット

  1. 処理が分散する

    上では比較的単純な例を示しましたが、非正規化非均質抽象構文木のような複雑になりやすい木構造の場合、クラスの数が数十以上になってしまうこともありえます。その場合、それぞれのクラスに処理が分散してしまうため、変更などが行いにくくなります。

    また、処理の追加(例: プリティプリント機能 や 型検査機能、最適化機能など)を行うごとに木クラスの定義が膨れあがっていきます。

単純な木構造の走査に向いたパターンと言えます。

2. 外部木訪問器(Visitorパターン)

非均質抽象構文木などの走査によく用いられるパターンです。

ダブルディスパッチにより、訪問した木クラスの型に応じた訪問器のメソッドに処理を振り分けます。

// 外部訪問器インターフェース
interface IVisitor<T> {
    T Visit(Add node);
    T Visit(Mul node);
    T Visit(Num node);
}

// ノード
interface INode {
    // 訪問器の受け入れ
    T Accept<T>(IVisitor<T> visitor);
}

// 加算
class Add: INode {
    public INode Left  { get; }
    public INode Right { get; }
    
    public Add(INode left, INode right) {
        this.Left  = left;
        this.Right = right;
    }
    
    // IVisitor.Visit(Add) を呼び出す
    public T Accept<T>(IVisitor<T> visitor) => visitor.Visit(this);
}

// 乗算
class Mul: INode {
    public INode Left  { get; }
    public INode Right { get; }
    
    public Mul(INode left, INode right) {
        this.Left  = left;
        this.Right = right;
    }
    
    // IVisitor.Visit(Mul) を呼び出す
    public T Accept<T>(IVisitor<T> visitor) => visitor.Visit(this);
}

// 数値
class Num: INode {
    public double Value { get; }
    
    public Num(double value) {
        this.Value = value;
    }
    
    // IVisitor.Visit(Num) を呼び出す
    public T Accept<T>(IVisitor<T> visitor) => visitor.Visit(this);
}

// 評価訪問器
class Evaluator: IVisitor<double> {
    public double Visit(Add node) => node.Left.Accept(this) + node.Right.Accept(this);
    public double Visit(Mul node) => node.Left.Accept(this) * node.Right.Accept(this);
    public double Visit(Num node) => node.Value;
}

class Prog {
    public static void Main() {
        // 1*2 + 3*4
        var tree = new Add(
            new Mul(new Num(1), new Num(2)),
            new Mul(new Num(3), new Num(4))
        );
        
        // 評価器
        var evaluator = new Evaluator();
        
        System.Console.WriteLine(tree.Accept(evaluator));
    }
}

実行結果

14

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

注目して頂きたいのは 各木クラスに定義された Accept メソッドです。

全く同じ定義の関数がそれぞれのクラスで定義されています。これは一見無駄に見えますが、this の型によって呼び出すメソッドを解決するため必要になります。

また、式木の評価は訪問器が担当するため、評価に関する処理が木クラスから切り離されていることがわかります。

メリット

  1. 木構造と処理を分離できる

    処理を訪問器が行うため、木クラスは処理に関する詳細を知る必要がなくなりました。

  2. 訪問器が状態を持てる

    走査メソッドの場合、走査途中の状態は引数として伝播させる必要がありますが、Visitorパターンの場合は訪問器が処理途中の状態を持つことが出来ます。

  3. 機能の追加に強い

    機能を追加する際には、新しく処理を行う訪問器を作成すればよいため、既存のコードを変更する必要がありません。

    例として、式木を文字列に変換する訪問器 Printer の定義を示します。

class Printer: IVisitor<string> {
    public string Visit(Add node) => $"({node.Left.Accept(this)} + {node.Right.Accept(this)})";
    public string Visit(Mul node) => $"({node.Left.Accept(this)} * {node.Right.Accept(this)})";
    public string Visit(Num node) => $"{node.Value}";
}

tree.Accept(new Printer()); // ((1 * 2) + (3 * 4))

デメリット

  1. 木の内部情報を訪問器に公開する必要がある

    上の例であれば、Num クラスの保持している数値に関する情報などの、処理に必要な情報が外部に公開されていることがわかります。

  2. 引数の型や個数が固定

    訪問器によって引数の型や個数を変えることが難しくなります。

    更に、上の例の場合 ジェネリクスを用いて返り値の型を変えていますが、C++の場合は (templateと仮想関数の相性が良くないため) 処理の結果を呼び出し元へと伝播させるためには訪問器の内部状態を利用するなどの工夫が必要になります。

  3. 処理を行うメソッド名が固定

    Interpreterパターンの場合は処理によって適切なメソッド名を付けられますが、上の例の場合は Visit に固定されます。

構文木の解析などの比較的複雑な木構造の走査に向いているパターンと言えます。

3. 外部訪問器(型情報などによる振り分け)

メソッドの振り分けを訪問器の内部で行うパターンです。

// ノード
interface INode {
    // Acceptは必要ない
}

// 加算
class Add: INode {
    // ...
}

// 乗算
class Mul: INode {
    // ...
}

// 数値
class Num: INode {
    // ...
}

// 評価訪問器
class Evaluator {
    public double Dispatch(INode node) {
        // C# 6.0
        if (node is Add) return this.Eval((Add)node);
        if (node is Mul) return this.Eval((Mul)node);
        if (node is Num) return this.Eval((Num)node);
        
        // 処理できなかった
        throw new System.Exception();
    }
    
    private double Eval(Add node) => this.Dispatch(node.Left) + this.Dispatch(node.Right);
    private double Eval(Mul node) => this.Dispatch(node.Left) * this.Dispatch(node.Right);
    private double Eval(Num node) => node.Value;
}

class Prog {
    public static void Main() {
        // 1*2 + 3*4
        var tree = new Add(
            new Mul(new Num(1), new Num(2)),
            new Mul(new Num(3), new Num(4))
        );
        
        // 評価器
        var evaluator = new Evaluator();
        
        System.Console.WriteLine(evaluator.Dispatch(tree));
    }
}

実行結果

14

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

木クラスの Accept メソッドがなくなり、代わりに訪問器の Dispatch メソッドでクラスに応じたメソッドに処理が振り分けられていることがわかります。

mcsが C# 7 に対応していないため if 文を羅列していますが、C# 7 に対応した環境であれば switch 式を用いたパターンマッチングが使える様になるため、よりスマートに記述することが可能になります。

メリット

  1. 処理を行うメソッド名を自由に決められる

  2. 引数の数や個数が自由

  3. 各走査メソッドを private に出来る。

デメリット

  1. 各訪問器に Dispatch メソッドが必要

  2. メソッドの実装忘れがコンパイル時に確認できない

    Dispatch メソッド内のノード型に対応した振り分け機構に実装忘れがあっても、コンパイラはそれを検知できません。実行時に例外が発生してようやく実装忘れを確認出来ます。

このパターンの利点は一見少ないように見えますが、今回の数式微分を行うプログラムでは式木の走査にこれを採用しました。

なぜかと言うと、このパターンとD言語の言語機能である mixin / template mixin の相性が非常に良いためです。

それらの言語機能に関する詳細は省きますが、文法的にクリーンなC言語のマクロを想像すればだいたいそんな感じです。

では、D言語での 評価訪問器 の実装例を以下に示します。

// 訪問器ミックスイン
template Visitor() {
    // 振り分けメソッド
    auto dispatch(string func, Args...)(Node node, Args args) {
        import std.algorithm: castSwitch;
        
        return node.castSwitch!(
            (Add node) => mixin("this." ~ func ~ "(node, args)"),
            (Mul node) => mixin("this." ~ func ~ "(node, args)"),
            (Num node) => mixin("this." ~ func ~ "(node, args)"),
        )();
    }
}

// 評価訪問器
class Evaluator {
    mixin Visitor;
    
    private double eval(Add node) { return this.dispatch!"eval"(node.left) + this.dispatch!"eval"(node.right); }
    private double eval(Mul node) { return this.dispatch!"eval"(node.left) * this.dispatch!"eval"(node.right); }
    private double eval(Num node) { return node.value; }
}

この訪問器の振り分けメソッドは、visitor.dispatch!"eval"(node) のように呼び出します。

上の Visitor が template mixin と呼ばれる言語機能を使った部分で、mixin Visitor; と書かれた部分に Visitor 内部の文(この場合は dispatch メソッド)を展開します。

これによって複数の訪問器を書く場合にも、dispatch メソッドの定義は一度だけでよく、実装忘れの可能性を低減することができます。

更に、dispatch のテンプレート引数(上の場合は "eval") に適当な文字列を渡せば 振り分け先のメソッドを eval 以外にも変えられる他、node に続いて 引数を渡すことで 複数の引数を振り分け先のメソッドに渡すことができます。

最後に

D言語はそれなりに良い言語なのでみんなも書けばいいと思います。

第二魚雷発射管発射管姫路だいじょうぶじゃないでぃす

この記事は はいふり Advent Calendar 2016 - Adventar の10日目の記事です。

www.adventar.org

間に合いませんでした。

第二魚雷発射管姫路さんが掃海時になぜ助かったのかの話をしたかったのですが間に合いませんでした。

下はお茶を濁すための姫路さんです。

煮たり焼いたりしてください。

f:id:Ryooooooga:20161218103219p:plain

それはそうと

はいふりといえば登場するキャラがみんなかわいいことで有名ですね。

私は第二魚雷発射管の姫路さんがすきです。

魚雷発射管とは

念のため補足しておくと、魚雷発射管は魚雷をしゅぽしゅぽ打ち出すあれです。

晴風には 61cm4連装魚雷発射管 が船体の中央付近に前後 2基 装備されています。*1

それぞれ前側の第一魚雷発射管を りっちゃん(松永 理都子) が、 後ろ側の第二魚雷発射管を かよちゃん こと 姫路 果代子さん が担当していて、 水雷長のメイちゃん(西崎 芽依)の指示で魚雷を発射します。

人物

ちっちゃい。

かわいい。

相撲に詳しい。

あほ毛。

主な登場シーン

魚雷の発射担当という役割上、対比叡戦、対アドミラル・グラフ・シュペー第2戦、対武蔵戦では大活躍だった(はず)のですが画面上にはほとんど登場しませんでした。

(対さるしま戦ではりっちゃんが魚雷(訓練弾)を発射、対シュペー第1戦、対伊201戦では魚雷の残弾が無かったため水雷戦は無し)

また、商店街船「しんばし」の海難救助にはダイバーとして作戦に参加し、被害状況の確認と浸水区画の捜索を担当していました。

そして、姫路さんを語る上で外せないのが機雷掃海作戦です。

機雷掃海作戦

あらまし

機雷の敷設された海域に迷い込んでしまった晴風、安全に後悔航海するために周囲の掃海を行う必要があります。

副長「人力の水中処分は危険だ」
艦長「スキッパーを使おう」
ココ「あれなら小さいので機雷に引っかかる可能性は低いです」
タマ「あん……ぜん*2
艦長「スキッパー乗員には重安全具の装着を」

というわけで晴風の搭載している中型スキッパーを用いた掃海が行われることになりました。

スキッパーの操縦には免許が必要であり、特に中型スキッパー免許の取得には小型スキッパー免許の一年以上の保有が最低条件になります。*3

晴風乗員で中型スキッパー免許を持っているのは艦長、和住 媛萌(ヒメちゃん)ぞな子サトちゃん(勝田 聡子)、そして りっちゃん の4名のみです。*4

そんなこんなで りっちゃん と 姫路さん の二人がスキッパーでの掃海具の曳航を行うことになりました。*5

顛末

結果としてりっちゃんの操縦するスキッパーは係維機雷を支持するケーブルを高々数本*6切断したところで機雷に接触[要出典]し、ふっとばされることと相成りました。

重安全具

さて、はいふり世界のブルマー人はこの現実世界の人間よりも比較的丈夫であることが知られています。

下にその根拠となる幾つかの例を挙げます。

  • 晴風機関科員

    高温の蒸気が噴き出す可能性のある機関室にも関わらず半袖セーラー、あるいは水着で作業。

  • 明石乗員

    半袖で溶接。

  • ヴィルヘルミーナ・ブラウンシュヴァイク・インゲノール・フリーデブルク

    シュペーの15cm砲の至近弾を喰らい、搭乗する小型船は木っ端微塵になるも無傷(ただし数時間気絶)。

  • 艦長 岬明乃

    中型スキッパーで脱落した武蔵の装甲[要出典]に高速で衝突し放り出されるも無傷。

    幼馴染の知名 もえかの危機に動転していた艦長の操縦するスキッパーは、武蔵の航行速度からみても少なくとも60km/hは出ていたと考えられます(なお、中型スキッパーの最大速力は120km/h *7 )。

ということで、頑強なブルマー人(の卵)は基本的に半袖セーラーでなんでもこなしてしまいます。

とはいえ鋼鉄の艦艇を攻撃することを目的とした機雷を相手取るにはいくらなんでもそれだけでは無理があるようで、上の会話の通り重安全具の装着が指示されます。

というわけで以下の画像が重安全具を装備した姫路さん(と りっちゃん)です。

f:id:Ryooooooga:20161218000847j:plain

姫路さん(不安げな表情がかわいい) の手首についているのが恐らくそれです。

本来はこの重安全具の話がしたかったのですが間に合いませんでした。

ともあれ、機雷の至近爆発に巻き込まれた 姫路さんら は重安全具のお陰[要出典]で軽症で済んだのでした。

まとめ

はいふり世界の人間は丈夫。

姫路さんはかわいい。

ハイスクール・フリート ファンブックを買って。

www.hai-furi.com

*1:ハイスクール・フリート ファンブック P110

*2:危険

*3:ハイスクール・フリート ファンブック P114

*4:ハイスクール・フリート ファンブック P114

*5:二人乗りのため 姫路さん は免許がなくても問題はない

*6:画面で確認できるのは少なくとも2本

*7:ハイスクール・フリート ファンブック P114

篤見唯子のスロウスタート

この記事は まんがタイムきらら Advent Calendar 2016 - Adventar の10日目の記事です。

www.adventar.org

はじめに

今年は今までで最も多くの まんがタイムきらら の作品に触れることの出来た一年でした。

その中でも最も私の好きな作品の一つ、篤見唯子先生の「スロウスタート」を紹介したいと思います。

可能な限りネタバレなどは避けます。

作品について

スロウスタート は 篤見唯子先生 によって まんがタイムきらら 2013年7月号より連載されている作品です。

単行本は3巻まで発売されています。(2016年12月現在)

淡く優しいふんわりとした色使いの特徴的な絵柄がかわいらしいです。

登場人物

※ 単行本内のイラストを貼り付けるのがはばかられたので画像はありません。1巻のAmazonプレビュー、3ページ目あたりを見ながらだとキャラクタの想像がし易いと思います。

主な登場人物をざっくり紹介します。

いち花名はな

主人公。

高校一年生。実家を離れて従姉のおんの管理するアパートで一人暮らしをしている。

人見知りでネガティブ思考、泣き虫で打たれ弱い豆腐メンタル。

みんなには言えない秘密がある。

かわいい。

くら

高校一年生。ヘアピンがトレードマーク。

花名のクラスメイトで人気者、圧倒的コミュ強。天然たらし。

かわいい。

ももたまて

高校一年生。ツインテールの元気っ娘。

栄依子とは同じ中学出身。

重度のオタク。

八重歯。かわいい。

せんごくかむり

高校一年生。ちっちゃくてマイペース。

栄依子とは小学校の同級生。栄依子によく懐いている。

かわいい。

魅力

スロウスタートは言うなれば、花名が自身の抱えた秘密と向き合う物語です。

友人たちと過ごす何気ない日常の中で、時折ふっと鎌首をもたげるそれとどう折り合いをつけるのか。

秘密を打ち明けることで何かが変わってしまうかもしれないという不安と、親しくしてくれる友だちにそれを隠し続けることへの罪悪感。

けれども周囲の優しさの中でゆっくりと成長する花名の姿こそがこの作品の魅了だと思うのです。

かなり短くなってしまいましたが、文字通りいい意味でスロウな作品なのでこれ以上踏み込んだ話をしようとするとどうしてもネタバレを含んでしまうのでこのあたりで。

蛇足ではありますが、あんまり短すぎるのも申し訳ないので拙作の花名とたまてのデフォルメアイコンを投げておきます。酔狂な方が居ましたらTwitterのアイコンなどにご自由にどうぞ。

f:id:Ryooooooga:20161209220312p:plain:w300f:id:Ryooooooga:20161209225600p:plain:w300

C++17 optionalの実装について

C++17で、optionalが標準ライブラリに入ることが決定した。

そして、C++17 optionalはconstexprに対応している。

以前からその実装について気になっていたので調べたついでに少しまとめる。

optionalとは

無効値を取ることのできる型である。

C++17 optionalはBoost.Optionalの実装を元に設計された。

Boost.Optionalに関しては以下の記事が詳しい。

d.hatena.ne.jp

C++03 Boost.Optionalの実装

C++03時代のBoost.Optionalの実装についても触れておく。

C++03 Boost.Optionalの実装は単純だ。

予めoptionalオブジェクト内にデータを格納するストレージを確保しておき、
適切なタイミングでplacement newをして、初期化する。

また、オブジェクトを破棄する際には、必要があれば明示的デストラクタ呼び出しを行う。

ストレージの確保には、(C++11以降でいうところの)std::aligned_storageのようなものを用いる。

つまり、optionalの内部で領域の動的確保は行われない。

下記のコードはBoost.Optionalの実装のイメージだ(故に正確ではない)。

template <typename T>
class optional {
    //  storage
    typename std::aligned_storage<sizeof(T), alignof(T)>::type storage_;
    bool init_;
    
    //  pointer to storage
    T* ptr() {
        return static_cast<T*>(static_cast<void*>(&storage_));
    }
    
public:
    // default constructor
    optional() : init_(false) {}
    
    // value constructor
    optional(const T& val) : init_(true) {
        //  placement new
        new (&storage_) T(val);
    }
    
    //  destructor
    ~optional() {
        if (init_) {
            // explicit destructor call
            ptr()->~T();
        }
    }
};

見て分かる通り、この実装のoptionalクラスはtrivialデストラクタを持たない。

更には引数付きコンストラクタはconstexprコンストラクタの条件を満たさない。

なので、このままではconstexpr対応の条件であるリテラル型クラスの条件を満たさない。

C++17 optionalはどのような実装により、constexpr対応を果たしたのだろうか。

その前に

上のコードでは、Tの型に関わらずoptional<T>型はデストラクタで明示的デストラクタ呼び出しを行っているが、
実際には、Tがtrivialデストラクタをもつ場合は明示的デストラクタ呼び出しを省略できる。

そのため、Tがtrivialデストラクタを持つときには、optional型もまたtrivially destructibleとなれる。

実装について

さて、ようやくC++17 optionalの実装を確認する。

constexpr対応のoptionalの実装は以下のリポジトリのものを参考にした。

github.com

だが、実際のソースコードは一息に読むには長いので、部分部分に分解して見ていく。

まずは、optional<T>型の定義を確認する。

定義は上記のリポジトリ、optional.hppファイルの350行目付近である。

// 350行目付近
template <class T>
class optional : private OptionalBase<T>
{
   ...
};

optional<T>型はOptionalBase<T>型を継承している。

OptionalBase<T>型はそのすぐ上で定義されている。

// 341行目付近
template <class T>
using OptionalBase = typename std::conditional<
    is_trivially_destructible<T>::value,
    constexpr_optional_base<typename std::remove_const<T>::type>,
    optional_base<typename std::remove_const<T>::type>
>::type;

std::conditional<B, X, Y>::typeは、B == trueの時 X型になり、B == falseの時 Y型となる。

ようは、条件分岐のようなものだ。

この場合の分岐条件は、

is_trivially_destructible<T>::value

つまり、Tがtrivialデストラクタを持つかどうかだ。

Tがtrivialデストラクタを持つ時、OptionalBase<T>は、constexpr_optional_base<T>となり、
Tが非trivialデストラクタを持つ時、OptionalBase<T>は、optional_base<T>となる。

双方の定義を確認する。

// 296行目付近
template <class T>
struct optional_base
{
    bool init_;
    storage_t<T> storage_;

    ...

    ~optional_base() { if (init_) storage_.value_.T::~T(); }
};

// 319行目付近
template <class T>
struct constexpr_optional_base
{
    bool init_;
    constexpr_storage_t<T> storage_;

    ...

    ~constexpr_optional_base() = default;
};

「...」で省略した部分はどちらのクラスもほぼ同じであった。

違いは2点。

1つ目は、storage_ メンバ変数の型、

2つ目は、デストラクタでのメンバの明示的デストラクタ呼び出しの有無だ。

constexpr_optional_baseは、Tがtrivialデストラクタを持つため、明示的デストラクタ呼び出しを省略しているのだろうと予想できる。

では、storage_t と constexpr_storage_t の定義を確認する。

// 266行目付近
template <class T>
union storage_t
{
  unsigned char dummy_;
  T value_;

  ...

  ~storage_t(){}
};

// 281行目付近
template <class T>
union constexpr_storage_t
{
    unsigned char dummy_;
    T value_;

    ...

    ~constexpr_storage_t() = default;
};

このoptionalは、ストレージにstd::aligned_storageのような型を使わず、共用体を使って実現しているようだ。

storage_t と constexpr_storage_t の定義の違いは、デストラクタの定義のみである。

ではこの違いは何故必要なのか。

これには、C++11の「共用体の制限解除」が関係している。

C++11以降では非trivialデストラクタを持つオブジェクトも共用体のメンバにすることが可能になった。

しかし、その時その共用体のデストラクタは暗黙的にdeleteされる。

そのため、非trivialデストラクタを持つT型のメンバ value_ を持つstorage_tには空のデストラクタ定義が必要になる。

さらに、共用体のコンストラクタの初期化子を使って value_ を初期化すれば、T型のコンストラクタが呼び出されるため、
optional<T>のコンストラクタ内での placement new の必要がなくなる。

以上をもって、Tがリテラル型である場合に、constexpr_storage_t<T>、constexpr_optional_base<T>、optional<T>の全てがリテラル型の条件を満たし、コンパイル時のオブジェクト構築が可能となる。

#include <type_traits>
#include <string>
#include <cassert>

template <typename T>
union storage_t {
	char dummy_;
	T value_;

	template <typename... Args>
	constexpr storage_t(Args&&... args) : value_(args...) {}

	~storage_t() {}
};

template <typename T>
union constexpr_storage_t {
	char dummy_;
	T value_;

	template <typename... Args>
	constexpr constexpr_storage_t(Args&&... args) : value_(args...) {}

	~constexpr_storage_t() =default;
};

template <typename T>
struct optional_base {
	bool init_;
	storage_t<T> storage_;
    
	template <typename... Args>
	constexpr optional_base(Args&&... args)
		: init_(true), storage_(args...) {}

	~optional_base() { if (init_) storage_.value_.~T(); }
};

template <typename T>
struct constexpr_optional_base {
	bool init_;
	constexpr_storage_t<T> storage_;

	template <typename... Args>
	constexpr constexpr_optional_base(Args&&... args)
		: init_(true), storage_(args...) {}

	~constexpr_optional_base() =default;
};

template <typename T>
using OptionalBase = std::conditional_t<
	std::is_trivially_destructible<T>::value,
	constexpr_optional_base<T>,
	optional_base<T>
>;

template <typename T>
class optional : OptionalBase<T> {
public:
	constexpr optional(const T& value) : OptionalBase<T>(value) {}

	constexpr const T& operator*() const {
		return OptionalBase<T>::storage_.value_;
	}
};

int main() {
    // constexpr
    constexpr optional<int> a(42);
    static_assert(*a == 42);
    
    // 非constexpr
    /*constexpr*/ optional<std::string> b("nyan");
    assert(*b == "nyan");
}

コンマ

ふと不思議に思ったものがあった。
線形代数ライブラリEigenの行列、ベクトルの初期化方法だ。

Eigen::Vector3d v;
v << 1.0, 2.0, 3.0;
v;  //  (1, 2, 3)

なんだか妙なことをしている。
どのようなしくみになっているのかを確かめるために実装を調べた。

どうやら コンマ演算子オーバーロードしているようだ。
はじめに <<演算子 で CommaInitializer なる中間オブジェクトを生成し、CommaInitializer の コンマ演算子オーバーロード で値を格納しているらしい。

恥ずかしながら今まで コンマ演算子オーバーロード可能であることを知らなかった。
そういえば、オーバーロード可能演算子に含まれている。

まあせっかくなので少し遊んでみたい。

#include <iostream>
using namespace std;

namespace hoge {
    template <typename Value>
    ostream& operator,(ostream& stream, Value value) {
        return stream << ',' << value;
    }
}

int main() {
    cout << 1,2,3,4,5;   // 1
    cout << endl;
    using namespace hoge;
    cout << 1,2,3,4,5;   // 1,2,3,4,5
    cout << endl;
}

出力

1
1,2,3,4,5

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

さて、この記事を書いている途中、コンマ演算子オーバーロード用いた Boost.Assign なるものがあることを教えていただいた。

#include <boost/assign.hpp>

int main() {
    using namespace boost::assign;
    std::vector<int> v;

    v += 1,2,3,4,5; // [1,2,3,4,5]
}

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ
内部は、Eigen のそれと似たようなものなのだろう。
Boost.Assign ではこれ以外にも演算子オーバーロードされているようだ。