Hatena::ブログ(Diary)

エンジニアのソフトウェア的愛情 このページをアンテナに追加 RSSフィード Twitter

2014-07-21

Lispを作ってみる、ただしC++テンプレートで

なんか、こじらせた。

これだけではLispになりませんが、もだった材料はそろうみたいなので、できそうな気がします。たぶん。

#include <iostream>

// 等値
template<typename T, typename U> struct Eq       { static const bool condition = false; };
template<typename T>             struct Eq<T, T> { static const bool condition = true;  };

// 論理和
template<typename T, typename U, bool cond = T::condition> struct Or;
template<typename T, typename U> struct Or<T, U, true>  { static const bool condition = true;         };
template<typename T, typename U> struct Or<T, U, false> { static const bool condition = U::condition; };

// 論理積
template<typename T, typename U, bool cond = T::condition> struct And;
template<typename T, typename U> struct And<T, U, true>  { static const bool condition = U::condtion; };
template<typename T, typename U> struct And<T, U, false> { static const bool condition = false;       };

// 分岐
template<bool Condition, typename T, typename U> struct If              { typedef T type; };
template<typename T, typename U>                 struct If<false, T, U> { typedef U type; };

// 終端
struct Nil {};

// リスト
template<typename T, typename U>
struct List
{
    typedef T head;
    typedef U tail;

    static std::ostream& value(std::ostream& out)
    {
        return out << head::value << tail::value;
    }
};

template<typename T>
struct List<T, Nil>
{
    typedef T   head;
    typedef Nil tail;

    static std::ostream& value(std::ostream& out)
    {
        return out << head::value;
    }
};

// 構築
template<typename Head, typename List> struct Cons;
template<typename Head, template<typename, typename> class List, typename H, typename T>
struct Cons<Head, List<H, T>>
{
    typedef List<Head, List<H, T>> type;
};

// CAR
template<typename List> struct Car;
template<template<typename, typename> class List, typename H, typename T>
struct Car<List<H, T>>
{
    typedef H type;
};

// CDR
template<typename List> struct Cdr;
template<template<typename, typename> class List, typename H, typename T>
struct Cdr<List<H, T>>
{
    typedef T type;
};

// 包含検査
template<typename X, typename List>
struct Member
{
    static const bool condition = Or<Eq<X, typename List::head>, Member<X, typename List::tail>>::condition;
};

template<typename _>
struct Member<_, Nil>
{
    static const bool condition = false;
};

// 挿入
template<typename X, typename List> struct Insert;
template<typename X, template<typename, typename> class List, typename H, typename T>
struct Insert<X, List<H, T>>
{
    typedef typename If<
        Member<X, List<H, T>>::condition,
        List<H, T>,
        typename Cons<X, List<H, T>>::type
    >::type type;
};

// 利用例

template<char C> struct Char { static const char value = C; };

typedef List<Char<'A'>, List<Char<'B'>, List<Char<'C'>, Nil>>> ABC;

typedef Insert<Char<'A'>, ABC>::type ABC_;
typedef Insert<Char<'D'>, ABC>::type DABC;

int main(int, char* [])
{
    std::cout << ABC::value << std::endl;
    std::cout << ABC_::value << std::endl;
    std::cout << DABC::value << std::endl;

    return 0;
}

実行結果。

ABC
ABC
DABC

2014-07-16

文字列をリンクトリストにする、ただしC++テンプレートで

C++テンプレートを使っていると、ときどき、文字列テンプレートに渡したくなるときがあります。

ですが残念なことに、文字列テンプレート引数にすることはできません。


// こういうことをやってみたい! (けど、できない)

template<const char* S>
struct Str
{
    // ...
};

typedef Str<"abcd"> ABCDE;

直接に文字列テンプレート引数として使うことはできないのですが、先日、おもしろいことに気がつきました。


C++11では、constexprキーワードを使うことで、定数を与えた関数の値も定数として扱うことができるようになりました。

コンパイル時に値が決定する定数ですから、テンプレート引数としても使うことができます。

// N と M を加算するテンプレート
template<int N, int M>
struct Add
{
    static const int value = N + M;
};

// コンパイル時に定数が与えられれば定数として扱える関数
constexpr int abs(int n)
{
    return (n >= 0) ? n : -n;
}

// 関数の値をテンプレート引数として与えることができる
int n = Add<abs(-10), abs(5)>::value;

実行結果。nに 15 という値が設定されています。

	.section	__TEXT,__text,regular,pure_instructions
	.section	__DATA,__data
	.globl	_n                      ## @n
	.align	2
_n:
	.long	15                      ## 0xf

さらに加えて。以前、関数はテンプレート引数になるというエントリを書きました。

文字列文字列という形でテンプレートに渡すことはかないませんが、たとえば次のようにすれば、文字のシーケンステンプレートに渡すことができます。

static constexpr char abcd(int n) { return "abcd"[n]; }

また文字のシーケンスに含まれる値(=文字)も定数として取り出せますから、それをされにテンプレート引数として渡すことができることになります。


これらをふまえて。


// 終端
struct Nil {};

// 文字-型変換テンプレート
template<char C>
struct Char
{
    static const char value = C;
};

// 後続の型を定義するテンプレート(先行宣言)
template<constexpr char (&String)(int), int N, typename C>
struct Tail;

// 文字列からシーケンスを生成するテンプレート
template<constexpr char (&String)(int), int N = 0>
struct StringSequence
{
    typedef Char<String(N)>                      head;
    typedef typename Tail<String, N, head>::type tail;
};

// 後続の型を定義するテンプレート
template<constexpr char (&String)(int), int N, typename C>
struct Tail
{
    typedef StringSequence<String, N + 1> type;
};

// 後続の型を定義するテンプレート(終端)
template<constexpr char (&String)(int), int N>
struct Tail<String, N, Char<'\0'>>
{
    typedef Nil type;
};

// 以下、利用例

// 文字列定数を表現する関数
static constexpr char abcd(int n) { return "abcd"[n]; }

// 間接的に文字列を受け取るテンプレートから型を生成
typedef StringSequence<abcd> ABCD;

// 値を取り出す
char a   = ABCD::head::value;
char b   = ABCD::tail::head::value;
char c   = ABCD::tail::tail::head::value;
char d   = ABCD::tail::tail::tail::head::value;
char eos = ABCD::tail::tail::tail::tail::head::value; // end of string

実行結果。変数 _a, _b, _c, _d にそれぞれの文字コードが格納されています。eos の値は 0初期化された状態を維持しているため、値は明示的には格納されていません。

	.section	__TEXT,__text,regular,pure_instructions
	.section	__DATA,__data
	.globl	_a                      ## @a
_a:
	.byte	97                      ## 0x61

	.globl	_b                      ## @b
_b:
	.byte	98                      ## 0x62

	.globl	_c                      ## @c
_c:
	.byte	99                      ## 0x63

	.globl	_d                      ## @d
_d:
	.byte	100                     ## 0x64

	.globl	_eos                    ## @eos
.zerofill __DATA,__common,_eos,1,0


このままではメリットは感じられませんが、文字列シーケンスになったということで 昨日の畳み込みテンプレート引数に渡すことができるようになったということです。


つづく。

2014-07-15

畳み込み、ただしC++テンプレートで

// リンクの終端
struct Nil {};

// 左畳み込みテンプレート
template<template<typename, typename> class Operator, typename N, typename Sequence>
struct Foldl
{
    static const int value = Foldl<
                                 Operator,
                                 Operator<N, typename Sequence::head>,
                                 typename Sequence::tail
                             >::value;
};

// 左畳み込みテンプレート(終端処理)
template<template<typename, typename> class Operator, typename N>
struct Foldl<Operator, N, Nil>
{
    static const int value = N::value;
};

// 以下、畳み込みの利用例

// 整数-型変換テンプレート
template<int N>
struct Int
{
    static const int value = N;
};

// N から 1 までのシーケンスを生成するテンプレート
template<int N>
struct DownToOne
{
    typedef Int<N>           head;
    typedef DownToOne<N - 1> tail;
};

// N から 1 までのシーケンスを生成するテンプレート(終端)
template<>
struct DownToOne<1>
{
    typedef Int<1> head;
    typedef Nil    tail;
};

// 加算演算子テンプレート
template<typename T, typename U>
struct Add
{
    static const int value = T::value + U::value;
};

// 10 から 1 までを初期値 0 から加算で左畳み込み( ((((((((((0 + 10) + 9) + 8) + 7) + 6) + 5) + 4) + 3) + 2) + 1) )
int n = Foldl<Add, Int<0>, DownToOne<10>>::value;

実行結果。

$ g++ --std=c++11 -S foldl.cpp 
$ cat foldl.s 
	.section	__TEXT,__text,regular,pure_instructions
	.section	__DATA,__data
	.globl	_n                      ## @n
	.align	2
_n:
	.long	55                      ## 0x37


つづく。

2014-07-09

遅延評価if

C++テンプレートで。


Haskellのばあい

基本に立ち返って、まずはHaskellのばあい。

Haskell基本的遅延評価なので、不適切な式が含まれていても評価されないのであれば全体としては正しく評価してくれます。

ここでinfinityを評価してしまうと無限再帰呼び出しになってしまいますが、if_に与えられるconditionがFalseであるかぎりinfinityは評価さません。結果としてif_は値を返すことができます。

if_ condition m n = if condition then m else n

infinity = infinity + 1

main = print $ if_ False infinity 1

C++テンプレートで失敗したばあい

先日、Haskellと同じ調子で次のように書いてしまいました。

template<bool F, int M, int N> struct If { static const int value = M; };
template<int M, int N> struct If<false, T, U> { static const int value = N; };

template<int N = 0> struct Infinity { static const int value = Infinity<N + 1>::value; };

int n = If<false, Infinity<>::value, 1>::value;

もう少しだけ複雑な式だったため、なぜエラーになるのかわからず半日ほど考えてしまう始末。

落ち着いて考えてみれば自明なのですが、Ifに値を与えるばあい、MNの値は確定していなければなりません。Mの値、Nの値を含めたIf<F, M, N>全体が型なので当然の結果でした。


C++テンプレートでやりなおし

数値を直接テンプレートに渡してしまったための過ちなので、テンプレートには型を与えて、その型から数値を取得するように書き換えます。


template<bool F, typename T, typename U> struct If { static const int value = T::value; };
template<typename T, typename U> struct If<false, T, U> { static const int value = U::value; };

template<int N = 0> struct Infinity { static const int value = Infinity<N + 1>::value; };

template<int N> struct Int { static const int value = N; };

int n = If<false, Infinity<>, Int<1> >::value;

このC++テンプレートを実行してみます。OSOS X Mavericks 、実行環境は G++ 5.1 です。

$ g++ -S lazy_if.cpp 
$ cat lazy_if.s 
	.section	__TEXT,__text,regular,pure_instructions
	.section	__DATA,__data
	.globl	_n                      ## @n
	.align	2
_n:
	.long	1                       ## 0x1

Infinityテンプレートに惑わされず、nに1が入ることが確認できました(爆)。

2014-06-30

練習をしないで試合に臨むアスリートはいない

はてなダイアリーにポストしているにもかかわらず、完全にマンスリーと化しています。自らの横着が成せる技。

それはそれとして。

目減りする技能

以前に「稼働率を100%にしてはいけない、と思う」というエントリを書きました(検索してみたら、ちょうど4年前の2010年6月30日!)。

現在のわたしの稼働がカツカツになっています。端から見るとそんな様子には見えないかもしれません。が、同僚より技術面体力面で劣るせいもあり、主観的には目一杯な感覚でいます。一日が終わると頭の奥がしびれているような感覚があり、帰宅してから能動的になにかをするのにも気持ちを奮い立たせないとなかなか行動にうつせません。で、実際に行動にうつせていません。技術力がたりないならば、練習訓練をしないといけないことは、承知していても、頭が働かない。日を追うごとに、自分の技術レベルが相対的に後退していく、この感覚。


技術を磨かずに仕事をするのは、練習せずに試合に臨むようなもの

こう例えると、いかに無謀なことをしているかがわかります。

仮に好きに連戦を組めるとしても、勝ち数を稼ぎたいからと練習をせずに試合ばかりを重ねても、よい成績を得られるはずがありません。



∴ いま必要なのは、練習の時間を確保すること。さて、来月からの仕事、うまく調整していかないと。