D言語erでも純粋に生きたい

この記事を書いたきっかけ

1, 2年くらい前からD言語で式テンプレートを使った行列ライブラリを書いてきまして、
その時に「式テンプレートとモナドって似てるよなあ」と思ったのがきっかけです。

そこで、今回は式テンプレートを使って純粋関数型プログラミングを行ってみたいと思います。

純粋関数型プログラミング on D言語

かの有名なHaskellでは、モナドというものを用いて非純粋な計算でも純粋性を確保しているようですが、モナドとは「手続き命令書」らしいので、D言語では式テンプレートで表せます。

式テンプレートとは、次のように式の計算手順を型として保持しているようなものです。
大きな特徴としては遅延評価があり、式の値は必要になってからしか計算されません。

また非純粋な計算であっても、その計算をしなければ純粋だと言えます(ここ重要)。
つまり、式テンプレートで遅延評価さえできれば純粋関数型プログラミングができそうです。

遅延評価式

まずファンクタを考えます。
Haskellではファンクタは次のように表されます。

ちなみに、ファンクタは「箱であり、その箱の中では箱に入っている値に対して関数を直接適用できる箱である」と考えてください。

class Functor f where
    fmap::(a -> b) -> f a -> f b

またモナドとはファンクタを少しイジったものです。
今回は>>=とreturnしか使用しません。
モナドは「ファンクタのうち、箱が二重になった場合には外側の箱を破ることができる箱」みたいな感じです。

class  Monad m  where
    (>>=)   :: m a -> (a -> m b) -> m b
    (>>)    :: m a -> m b -> m b
    return  :: a -> m a
    fail    :: String -> m a

    m >> k  =  m >>= \_ -> k
    fail s  = error s

遅延評価を行う式テンプレートさえ実装できれば、それを用いてD言語上でも純粋関数型プログラミングができそうであるといいました。
実は、遅延評価を行う式テンプレートはファンクタでもありモナドでもあります。
つまり、Lazy!Tという遅延評価オブジェクトに対して関数を適用した場合の返り値は、Lazy!(typeof(f(T.init)))であり、Lazy!(Lazy!T)とLazy!(T)は同じことをしているということです。

なので、遅延評価を表すオブジェクトにはファンクタのfmapと、モナドの>>=, returnを実装します。
>>=とreturnは名前がD言語的ではないので、bindとmakeとします。

そうすると、D言語でファンクタとモナドを可能な限り表現すると次のようになります。

enum bool isFunctor(T) = is(typeof((T t){
  static if(is(typeof(t.get) == void))
    static assert(is(typeof(t.fmap!(() => int.init).get) == int));
  else
  {
    static U f(U)(U a){ return a; }

    static assert(is(typeof(t.fmap!f.get) == typeof(f(t.get))));
  }
}));


enum bool isMonad(T) = is(typeof((T t){
  static if(is(typeof(t.get) == void))
    static assert(is(typeof(t.bind!(() => T.make(int.init)).get) == int));
  else
  {
    static auto f(U)(U a){ return T.make(a); }

    static assert(is(typeof(t.bind!f.get) == typeof(f(t.get).get)));
  }
}));

さらに、遅延評価を行う式テンプレート(LazyExpr)は次のようになります。

enum bool isLazyExpr(T) = T.isLazyExpr && isFunctor!T;


/**
遅延評価を行う式テンプレートで実装すべきメソッド。
fmapとbindとmakeの3つ。
*/
mixin template LazyExprMethod()
{
  static if(!is(typeof(this.get) == void))
  {
    LazyFuncCallExpr!(a => f(a.get), typeof(this)) fmap(alias f)() pure { return typeof(return)(this); }
    LazyFuncCallExpr!(a => f(a.get).get, typeof(this)) bind(alias f)() pure { return typeof(return)(this); }
  }
  else
  {
    LazyFuncCallExpr!(a => { a.get; return f(); }(), typeof(this)) fmap(alias f)() pure { return typeof(return)(this); }
    LazyFuncCallExpr!(a => { a.get; return f().get; }(), typeof(this)) bind(alias f)() pure { return typeof(return)(this); }
  }

    static ValueExpr!T make(T)(T v) pure { return ValueExpr!T(v); }
}


/**
ただの値を格納する
*/
struct ValueExpr(T)
{
    enum isLazyExpr = true;

    T get() @property { return _v; }
    mixin LazyExprMethod!();

  private:
    T _v;
}


/**
関数呼び出しを遅延評価する
*/
struct LazyFuncCallExpr(alias f, T...)
{
    enum isLazyExpr = true;

    typeof(f(_v)) get() @property { return f(_v); }
    mixin LazyExprMethod!();

  private:
    T _v;
}


/// ditto
LazyFuncCallExpr!(f, T) lazyFuncCallExpr(alias f, T...)(T args)
{
    static assert(isLazyExpr!(typeof(return)));
    return typeof(return)(args);
}

みんな純粋なんだよね

以上のコードをlazymodeというモジュールにすると、次のように凄く純粋にプログラムが書けます。
このコードはreadln.split.writelnと同じ動作をします。

/**
(このmain関数は処理系の一部だと考えてください…)
*/
void main()
{
    auto v = pmain();
    static assert(isLazyExpr!(typeof(v)));
    v.get;
}


pure:   // ここ以下すべてpure

import std.stdio;
import std.string;
import lazymode;

auto preadln(){ return lazyFuncCallExpr!readln(); }
auto pwriteln(T...)(T args){ return lazyFuncCallExpr!writeln(args); }

/**
pureなmain関数
*/
auto pmain()
{
    return preadln.fmap!split.bind!pwriteln;
}

まとめ

本記事では、非純粋な計算を遅延評価することで純粋性を確保しました。
遅延評価を行うために式テンプレートを導入し、また式テンプレートを扱いやすくするためにファンクタとモナドの考え方を導入しました。

最後に

本当はグローバル変数とかも扱いたかったのですが、時間がなかったのでこの程度になってしまいました。
ここに載せたコードを拡張すれば簡単にグローバル変数も純粋な関数で扱うことができるとおもいます。

明日はshooさんです。
なにやらD言語で組み込みのことらしいので、僕はすごく楽しみです。
それでは。