2015-08-14

MLからC++テンプレートへのコンパイラー

Evil ML: ML to C++ template language

akabe/evilml

MLからC++テンプレートメタコードへのコンパイラーが公開されている。

以下のMLにおけるクイックソートが、 

(* Example: quick sort *)

type 'a list = [] | :: of 'a * 'a list

let rec foldr f xs acc = match xs with
  | [] -> acc
  | x :: xs -> f x (foldr f xs acc)

let length xs = foldr (fun _ acc -> acc + 1) xs 0
let append xs ys = foldr (fun y acc -> y :: acc) xs ys
let filter f xs = foldr (fun x acc -> if f x then x :: acc else acc) xs []

let rec qsort xs = match xs with
  | [] -> []
  | [x] -> [x]
  | pivot :: rest ->
    let ys = qsort (filter (fun x -> x < pivot) rest) in
    let zs = qsort (filter (fun x -> x >= pivot) rest) in
    append ys (pivot :: zs)

let rec nth i xs = match xs with
  | [] -> error
  | x :: xs -> if i = 0 then x else nth (i-1) xs

let l1 = [5; 4; 8; 1; 6; 3; 7; 2]
let l2 = qsort l1
let x0 = nth 0 l2
let x1 = nth 1 l2
let x2 = nth 2 l2
let x3 = nth 3 l2
let x4 = nth 4 l2
let x5 = nth 5 l2
let x6 = nth 6 l2
let x7 = nth 7 l2

(*!
// This is C++ code.

#include <cstdio>

int main () { // We use printf in order to output readable assembly code.
  std::printf("%d  ", x0::val);
  std::printf("%d  ", x1::val);
  std::printf("%d  ", x2::val);
  std::printf("%d  ", x3::val);
  std::printf("%d  ", x4::val);
  std::printf("%d  ", x5::val);
  std::printf("%d  ", x6::val);
  std::printf("%d\n", x7::val);
  return 0;
}
*)

以下のような素敵なC++テンプレートメタコードに変換される。 

#include "evilml.hpp"


struct __ml_nil {
  static const int tag = 1000123519;
};

template <class x0, class x1>
struct __ml_cons {
  static const int tag = 478463344;
  typedef x0 fst;
  typedef x1 snd;
};

struct foldr {
  template <class f, class xs, class acc>
  class fun {
  private:
    struct __then2 {
      template <class>
      struct fun {
        static const int tag = 0;
        typedef acc type;
      };
    };
    struct __else2 {
      template <class>
      class fun {
      private:
        struct __then1 {
          template <class>
          class fun {
          private:
            typedef typename xs::fst x;
            typedef typename xs::snd xs1;
          public:
            static const int tag = 0;
            typedef typename
              f::template fun
                <x, typename foldr::template fun<f, xs1, acc>::type>::type type;
          };
        };
        struct __else1 {
          template <class>
          struct fun {
            static const int tag = 0;
            typedef void type;
          };
        };
      public:
        static const int tag = 0;
        typedef typename
          __ml_if<(xs::tag == 478463344), __then1, __else1>::type::
            template fun<void>::type type;
      };
    };
  public:
    static const int tag = 0;
    typedef typename
      __ml_if<(xs::tag == 1000123519), __then2, __else2>::type::template fun
        <void>::type type;
  };
};

struct length {
  template <class xs>
  class fun {
  private:
    struct __fun1 {
      template <class, class acc>
      struct fun {
        static const int tag = 0;
        typedef __ml_int<(acc::val + 1)> type;
      };
    };
  public:
    static const int tag = 0;
    typedef typename
      foldr::template fun<__fun1, xs, __ml_int<0> >::type type;
  };
};

struct append {
  template <class xs, class ys>
  class fun {
  private:
    struct __fun2 {
      template <class y, class acc>
      struct fun {
        static const int tag = 0;
        typedef __ml_cons<y, acc> type;
      };
    };
  public:
    static const int tag = 0;
    typedef typename foldr::template fun<__fun2, xs, ys>::type type;
  };
};

struct filter {
  template <class f, class xs>
  class fun {
  private:
    struct __fun3 {
      template <class x, class acc>
      class fun {
      private:
        struct __then3 {
          template <class>
          struct fun {
            static const int tag = 0;
            typedef __ml_cons<x, acc> type;
          };
        };
        struct __else3 {
          template <class>
          struct fun {
            static const int tag = 0;
            typedef acc type;
          };
        };
      public:
        static const int tag = 0;
        typedef typename
          __ml_if<f::template fun<x>::type::val, __then3, __else3>::type::
            template fun<void>::type type;
      };
    };
  public:
    static const int tag = 0;
    typedef typename foldr::template fun<__fun3, xs, __ml_nil>::type type;
  };
};

struct qsort {
  template <class xs>
  class fun {
  private:
    struct __then8 {
      template <class>
      struct fun {
        static const int tag = 0;
        typedef __ml_nil type;
      };
    };
    struct __else8 {
      template <class>
      class fun {
      private:
        struct __then7 {
          template <class>
          class fun {
          private:
            typedef typename
              xs::fst x;
            struct __then6 {
              template <class>
              struct fun {
                static const int tag = 0;
                typedef __ml_cons<x, __ml_nil> type;
              };
            };
            struct __else6 {
              template <class>
              class fun {
              private:
                struct __then5 {
                  template <class>
                  class fun {
                  private:
                    typedef typename xs::fst pivot;
                    typedef typename
                      xs::snd rest;
                    struct __fun4 {
                      template <class x>
                      struct fun {
                        static const int tag = 0;
                        typedef __ml_bool<__ml_lt<x, pivot>::val> type;
                      };
                    };
                    typedef typename
                      qsort::template fun
                        <typename filter::template fun<__fun4, rest>::type>::
                        type ys;
                    struct __fun5 {
                      template <class x8>
                      struct fun {
                        static const int tag = 0;
                        typedef __ml_bool<__ml_ge<x8, pivot>::val> type;
                      };
                    };
                    typedef typename
                      qsort::template fun
                        <typename filter::template fun<__fun5, rest>::type>::
                        type zs;
                  public:
                    static const int tag = 0;
                    typedef typename
                      append::template fun<ys, __ml_cons<pivot, zs> >::type type;
                  };
                };
                struct __else5 {
                  template <class>
                  struct fun {
                    static const int tag = 0;
                    typedef void type;
                  };
                };
              public:
                static const int tag = 0;
                typedef typename
                  __ml_if<(xs::tag == 478463344), __then5, __else5>::type::
                    template fun<void>::type type;
              };
            };
          public:
            static const int tag = 0;
            typedef typename
              __ml_if<(xs::snd::tag == 1000123519), __then6, __else6>::type::
                template fun<void>::type type;
          };
        };
        struct __else7 {
          template <class>
          class fun {
          private:
            struct __then4 {
              template <class>
              class fun {
              private:
                typedef typename xs::fst pivot;
                typedef typename
                  xs::snd rest;
                struct __fun6 {
                  template <class x9>
                  struct fun {
                    static const int tag = 0;
                    typedef __ml_bool<__ml_lt<x9, pivot>::val> type;
                  };
                };
                typedef typename
                  qsort::template fun
                    <typename filter::template fun<__fun6, rest>::type>::type ys;
                struct __fun7 {
                  template <class x10>
                  struct fun {
                    static const int tag = 0;
                    typedef __ml_bool<__ml_ge<x10, pivot>::val> type;
                  };
                };
                typedef typename
                  qsort::template fun
                    <typename filter::template fun<__fun7, rest>::type>::type zs;
              public:
                static const int tag = 0;
                typedef typename
                  append::template fun<ys, __ml_cons<pivot, zs> >::type type;
              };
            };
            struct __else4 {
              template <class>
              struct fun {
                static const int tag = 0;
                typedef void type;
              };
            };
          public:
            static const int tag = 0;
            typedef typename
              __ml_if<(xs::tag == 478463344), __then4, __else4>::type::
                template fun<void>::type type;
          };
        };
      public:
        static const int tag = 0;
        typedef typename
          __ml_if<(xs::tag == 478463344), __then7, __else7>::type::
            template fun<void>::type type;
      };
    };
  public:
    static const int tag = 0;
    typedef typename
      __ml_if<(xs::tag == 1000123519), __then8, __else8>::type::template fun
        <void>::type type;
  };
};

struct nth {
  template <class i, class xs>
  class fun {
  private:
    struct __then11 {
      template <class>
      struct fun {
        static const int tag = 0;
        typedef void type;
      };
    };
    struct __else11 {
      template <class>
      class fun {
      private:
        struct __then10 {
          template <class>
          class fun {
          private:
            typedef typename xs::fst x;
            typedef typename
              xs::snd xs1;
            struct __then9 {
              template <class>
              struct fun {
                static const int tag = 0;
                typedef x type;
              };
            };
            struct __else9 {
              template <class>
              struct fun {
                static const int tag = 0;
                typedef typename
                  nth::template fun<__ml_int<(i::val - 1)>, xs1>::type type;
              };
            };
          public:
            static const int tag = 0;
            typedef typename
              __ml_if<(i::val == 0), __then9, __else9>::type::template fun
                <void>::type type;
          };
        };
        struct __else10 {
          template <class>
          struct fun {
            static const int tag = 0;
            typedef void type;
          };
        };
      public:
        static const int tag = 0;
        typedef typename
          __ml_if<(xs::tag == 478463344), __then10, __else10>::type::
            template fun<void>::type type;
      };
    };
  public:
    static const int tag = 0;
    typedef typename
      __ml_if<(xs::tag == 1000123519), __then11, __else11>::type::
        template fun<void>::type type;
  };
};

typedef __ml_cons
  <__ml_int<5>, __ml_cons
     <__ml_int<4>, __ml_cons
        <__ml_int<8>, __ml_cons
           <__ml_int<1>, __ml_cons
              <__ml_int<6>, __ml_cons
                 <__ml_int<3>, __ml_cons
                    <__ml_int<7>, __ml_cons<__ml_int<2>, __ml_nil> > > > > > > > l1;

typedef qsort::fun<l1>::type l2;

typedef nth::fun<__ml_int<0>, l2>::type x0;

typedef nth::fun<__ml_int<1>, l2>::type x1;

typedef nth::fun<__ml_int<2>, l2>::type x2;

typedef nth::fun<__ml_int<3>, l2>::type x3;

typedef nth::fun<__ml_int<4>, l2>::type x4;

typedef nth::fun<__ml_int<5>, l2>::type x5;

typedef nth::fun<__ml_int<6>, l2>::type x6;

typedef nth::fun<__ml_int<7>, l2>::
  type x7;

// This is C++ code.

#include <cstdio>

int main () { // We use printf in order to output readable assembly code.
  std::printf("%d  ", x0::val);
  std::printf("%d  ", x1::val);
  std::printf("%d  ", x2::val);
  std::printf("%d  ", x3::val);
  std::printf("%d  ", x4::val);
  std::printf("%d  ", x5::val);
  std::printf("%d  ", x6::val);
  std::printf("%d\n", x7::val);
  return 0;
}

ドワンゴ広告

この記事はドワンゴ勤務中に見つけたのでメモ代わりに書いた。

ドワンゴ社内に関数型プログラマーが何人いるかは把握していない。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報｜株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

at

1 comment:

  1. AnonymousAugust 18, 2015 at 10:15 PM

    作ったことは称賛する。するが……。よめねーようわわわーん。Orz

    ReplyDelete

You can use some HTML elements, such as <b>, <i>, <a>, also, some characters need to be entity referenced such as <, > and & Your comment may need to be confirmed by blog author. Your comment will be published under GFDL 1.3 or later license with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.