plasma.ADTの紹介

a.md

おはようございます。@plasma_effector だよ。この記事はC++アドベントカレンダー8日目の記事です。

この記事ではC++で使える代数的データ型ライブラリplasma.ADT(の最新ver willing)の紹介をしていきます。

What is plasma.ADT

9月下旬に作り始めた代数的データ型のライブラリです。C++で簡単に「ML系言語のデータ型」っぽい型を作ることができ、さらにパターンマッチっぽいことをすることができます。

#include"adt_willing.hpp"
#include<iostream>

using namespace adt_willing;
using namespace place_holder;
typedef data_type<void, std::tuple<int, recursion_tag>> type;
const auto Nil = type::get_instance_function<0>();
const auto Tree = type::get_instance_function<1>();

int main()
{
	const auto func = recursion_match<int>()
		| Tree(0_, Tree(1_, 2_)) <= [](auto f, int x, int y, type t) {return x + y + f(t);}
		| Tree(0_, Nil) <= [](auto, int x) {return x;}
		| Nil <= [](auto) {return 0;};;
	std::cout << func(Tree(1, Tree(2, Nil()))) << std::endl;
	std::cout << func(Tree(1, Nil())) << std::endl;
}

ネーミングが安直かつ自己顕示欲爆発感あるのは気のせい。

plasma.ADTの歴史

初期バージョンでは非常に非効率な実装と無駄に長い名前が問題でした。

#include"algebraic_data_type.hpp"//長い！
#include<iostream>

using namespace plasma::algebraic_data_type;//長い！！
typedef data_type<void, std::tuple<int, recursion_tag>> tree;
const auto sum = tree::make_memoization_recursion_pattern_match_function<int>(//長い！！！
	[](auto) {return 0;},
	[](auto f, int x, tree t) {return x + f(t);});

const auto Nil = tree::get_instance_function<0>();//長い！！！！
const auto Tree = tree::get_instance_function<1>();//長い！！！！！

int main()
{
	std::cout << sum(Tree(1, Tree(2, Nil()))) << std::endl;
	std::cout << sum(Nil()) << std::endl;
}

どれぐらい非効率かと言うと深度250程度で各種操作に0.1秒以上かかるとかいうアレです。原因はコピーの度にstd::make_uniqueを呼んでることにあります。数ヶ月測ったときもっと遅かったので最近のVC++の最適化はすごいなぁとか。

その後adt_rebirthを出しました。

#include"adt_rebirth.hpp"
#include<iostream>

using namespace plasma_adt;
using namespace function_flag;

typedef data_type<void, std::tuple<int, recursion_tag>> list;

const auto Nil = list::get_instance_function<0>();
const auto Tree = list::get_instance_function<1>();

const auto sum = list::make_pattern_match<int>(recursion_flag,
    [](auto) 
    {
        return 0;
    }, 
    [](auto f, int v, list next) 
    {
        return v + f(next);
    });
const auto sum2 = list::make_pattern_match<int, std::tuple<int>>(recursion_flag, 
    [](auto, int x) 
    {
        return x;
    }, 
    [](auto f, int v, list next, int n)
    {
        return v + f(next, n);
    });

int main()
{
	auto t = Tree(1, Tree(2, Tree(3, Nil())));
	std::cout << sum(t) << std::endl;
	std::cout << sum2(t,2) << std::endl;
}

相変わらず色々な名前が長い。確実に初期バージョンより早いです。なんと深度250程度では1msかかりません。初期バージョンが遅すぎるのが問題だった。 このバージョンからboostが必須になりました。boost/variant.hppのパスを通しておく必要があります。

その後adt_willingを出しました。これが現行バージョンとなります。

#include"adt_willing.hpp"
#include<iostream>

using namespace adt_willing;
using namespace place_holder;
typedef data_type<void, std::tuple<int, recursion_tag>> type;
const auto Nil = type::get_instance_function<0>();
const auto Tree = type::get_instance_function<1>();

int main()
{
	const auto func = recursion_match<int>()
		| Tree(0_, Tree(1_, 2_)) <= [](auto f, int x, int y, type t) {return x + y + f(t);}
		| Tree(0_, Nil) <= [](auto, int x) {return x;}
		| Nil <= [](auto) {return 0;};;
	std::cout << func(Tree(1, Tree(2, Nil()))) << std::endl;
	std::cout << func(Tree(1, Nil())) << std::endl;
}

前2バージョンではパターンマッチの自由度が低かったのですが一気に自由度が広がりました。

現在はこれを発展させたバージョンを作ろうとしてます。

使い方

plasma.ADT willingのページには「main.cppを読めばわかる。」とか投げやりなことを書いてますが冷静に考えてわかってたまるかって感じなのでML系言語のコードと対比させながら書いていきます。

型の定義

使いたいデータ型を定義します。基本はvariant型です。

type hoge = D of double | I of int;;

#include"adt_willing.hpp"

using namespace adt_willing;

typedef data_type<double, int> hoge;

ML系言語と違いその型での値を生成するコンストラクタはまだ定義されていません。インスタンス関数を呼び出すことで定義されます。

それぞれの型にはtuple型を渡すことができます。

type hoge = Value of int | Set of int*int;;

#include"adt_willing.hpp"

using namespace adt_willing;

typedef data_type<int, std::tuple<int, int>> hoge;

また自己再帰したり何もvoid型を渡したりすることもできます。

type expr = Value of int | Plus of expr*expr | Minus of expr*expr;;
type tribool = True | False | None;;

#include"adt_willing.hpp"

using namespace adt_willing;

typedef data_type<int, std::tuple<recursion_tag, recursion_tag>, std::tuple<recursion_tag, recursion_tag>> expr;
typedef data_type<void, void, void> tribool;

ただし現在以下のようなことはできません。

type hoge = Value of int | List of hoge list;;
type piyo = Value of int | Set of (piyo*piyo)*int;;

インスタンス関数の定義

次のような型を考えます。

type intlist = Nil | Tree of int*intlist

#include"adt_willing.hpp"

using namespace adt_willing;

typedef data_type<void, std::tuple<int, recursion_tag>> intlist;

C++の方ではまだtypedefしただけで名前がついていません。このままでは変数を作ることができません。変数を作るための関数オブジェクトを返すstaticメンバ関数get_instance_functionがあります。

#include"adt_willing.hpp"

using namespace adt_willing;

typedef data_type<void, std::tuple<int, recursion_tag>> intlist;

const auto Nil = intlist::get_instance_function<0>();
const auto Tree = intlist::get_instance_function<1>();

const intlist v = Nil();
const intlist u = Tree(1, Tree(2, Nil()));

テンプレート引数で何番目のコンストラクタかを指定します。上の例ではNilが0番目、Treeが1番目の型で生成する関数オブジェクトとなるように定義しています。

パターンマッチ

特定の構造とマッチするかどうかで場合分けするパターンマッチも行えます。

let sum x =
	match x with
	| Nil -> 0;
	| Tree(v, next) -> v + (sum next);

using namespace place_holder;

const auto sum = recursion_match<int>()//返り値の型を指定しておく
							| Nil <= [](auto)
								{
									return 0;
								}//recursion_matchを使う場合第1引数は再帰用の関数オブジェクトなのでautoで受ける
							| Tree(0_, 1_) <= [](auto f, int v, intlist next)
								{
									return v + f(next);
								};
const int test = sum(Tree(1, Tree(2, Tree(3, Nil()))));

plasma.ADTの使いドコロ

構文木

雑に構文木を作ってみる。

#include"adt_willing.hpp"
#include<string>

using namespace adt_willing;
using namespace place_holder;

typedef data_type<
	int,//Value
	std::tuple<recursion_tag, recursion_tag, std::string>,//BiOpe
	std::tuple<recursion_tag, std::string>>//MonoOpe
		expr;
const auto Value = expr::get_instance_function<0>();
const auto BiOpe = expr::get_instance_function<1>();
const auto MonoOpe = expr::get_instance_function<2>();

const expr = BiOpe(MonoOpe(Value(1), "-"), Value(2), "+");//(+ (- 1) 2)

既存の問題点

Visual Studioにてインテリセンスがまともに機能しない

パターンマッチを利用して生成した関数オブジェクトの型がerror-typeになりその関数関連でインテリセンスがまともに機能しなくなります。コンパイルは通ります。

Visual Studioにてインスタンス関数のパラメタヒントが酷いことになることがある

基本はtypedefなので自分を含むインスタンス関数のパラメタヒントが酷いことになります。

自分の型を入れたコンテナを型定義に含むことができない

PEGのパーサを作ろうとしてつらいことになりました。パーサ書くために作ったのに…。

型定義が完全に順番に依存している

後から間に新しく追加しようとすると全てが崩壊します。

今後の展開について

実装を思い出しながら問題点をいくつか解消した新バージョンを現在製作中です。とりあえずコンテナを使えるようにします。

いい忘れてた大事なこと

boostソフトウェアライセンスです。

まとめ

・C++でパターンマッチができるライブラリ
・様々な問題点が残ってるのでそれを解消したバージョンを製作中

最後に

「plasma.ADTでこんなの作ったよー」って言う声があったらぜひください。 私も新バージョンが完成したら流石にまじめにパーサ書いてプログラミング言語作ります。