2026/04/02 8:35
新しいC++バックエンド for `ocamlc`
RSS: https://news.ycombinator.com/rss
要約▶
日本語訳:
新しいC++バックエンドが
ocamlcprimes.cppConsIifthenelseg++ -Dlimit=100 primes.cppprint::Cons<hd, tl>-ftemplate-depth=999999limit = 10000この改訂された要約は、すべての主要ポイントを反映し、不当な推測を避け、明確な主旨を提示し、あいまいまたは混乱を招く表現を排除しています。
本文
このパッチの概要
このパッチは ocamlc に新しい C++ バックエンドを追加し、
ランタイムや FFI で現在使用されている「インクリメントされない」C を改善します。
以下に示すサンプルプログラムは、ユーザーが指定した上限までの素数を計算します。
module List = struct let rec filter p = function | [] -> [] | x :: l -> if p x then x :: filter p l else filter p l let rec init i last f = if i > last then [] else f i :: init (i + 1) last f end let primes n = let rec sieve candidates = match candidates with | [] -> [] | p :: ps -> p :: sieve (List.filter (fun n -> n mod p <> 0) ps) in sieve (List.init 2 n (fun i -> i)) let main ~limit = primes limit
このプログラムを C++ に変換するには、次のようにします。
ocamlc -cpp -o primes.cpp <source.ml>
すると primes.cpp が生成されます。
primes.cppprimes.cpp
に出力された C++ コード
primes.cpp#ifndef limit #error "Parameter limit missing" #include <stop_after_error> #endif template <typename...> struct Cons; template <int tag, typename...> struct Cons_; template <int n> struct I { static constexpr int tag = 1000; static constexpr bool nonzero = (n != 0); static constexpr int val = n; }; struct EXCEPTION {}; template <typename f0_, typename f1_> struct Cons<f0_, f1_> { static constexpr int tag = 0; static constexpr bool nonzero = true; static constexpr int val = -1; typedef f0_ f0; typedef f1_ f1; }; template <int tag_, typename f0_, typename f1_> struct Cons_<tag_, f0_, f1_> { static constexpr int tag = tag_; static constexpr bool nonzero = true; static constexpr int val = -1; typedef f0_ f0; typedef f1_ f1; }; template <typename f0_, typename f1_, typename f2_> struct Cons<f0_, f1_, f2_> { static constexpr int tag = 0; static constexpr bool nonzero = true; static constexpr int val = -1; typedef f0_ f0; typedef f1_ f1; typedef f2_ f2; }; template <int tag_, typename f0_, typename f1_, typename f2_> struct Cons_<tag_, f0_, f1_, f2_> { static constexpr int tag = tag_; static constexpr bool nonzero = true; static constexpr int val = -1; typedef f0_ f0; typedef f1_ f1; typedef f2_ f2; }; template <typename filter, typename p, typename x, typename l, bool cond> struct ifthenelse; template <typename filter, typename p, typename x, typename l> struct ifthenelse<filter, p, x, l, true> { typedef Cons<x, typename filter::template app<p>::res::template app<l>::res> res; }; template <typename filter, typename p, typename x, typename l> struct ifthenelse<filter, p, x, l, false> { typedef typename filter::template app<p>::res::template app<l>::res res; }; template <typename filter, typename p, typename param, bool cond> struct ifthenelse_; template <typename filter, typename p, typename param> struct ifthenelse_<filter, p, param, true> { typedef typename param::f1 l; typedef typename param::f0 x; typedef typename ifthenelse<filter, p, x, l, p::template app<x>::res::nonzero>::res res; }; template <typename filter, typename p, typename param> struct ifthenelse_<filter, p, param, false> { typedef I<0> res; }; template <typename init, typename i, typename last, typename f, bool cond> struct ifthenelse_2; template <typename init, typename i, typename last, typename f> struct ifthenelse_2<init, i, last, f, true> { typedef I<0> res; }; template <typename init, typename i, typename last, typename f> struct ifthenelse_2<init, i, last, f, false> { typedef Cons<typename f::template app<i>::res, typename init::template app<I<(i::val) + (I<1>::val)>>:: template app<last>::res::template app<f>::res> res; }; template <typename List, typename sieve, typename candidates, bool cond> struct ifthenelse_3; template <typename List, typename sieve, typename candidates> struct ifthenelse_3<List, sieve, candidates, true> { typedef typename candidates::f0 p; struct Primes_primes_sieve__fun_ { template <typename n> struct app { typedef I<(I<(n::val) % (p::val)>::val) != I<0>::val> res; }; }; typedef Cons<p, typename sieve::template app< typename List::f0::template app<Primes_primes_sieve__fun_>::res:: template app<typename candidates::f1>::res >::res> res; }; template <typename List, typename sieve, typename candidates> struct ifthenelse_3<List, sieve, candidates, false> { typedef I<0> res; }; struct filter { template <typename p> struct app { struct res { template <typename param> struct app { typedef typename ifthenelse_<filter, p, param, param::nonzero>::res res; }; }; }; }; struct init { template <typename i> struct app { struct res { template <typename last> struct app { struct res { template <typename f> struct app { typedef typename ifthenelse_2<init, i, last, f, I<(i::val) > (last::val)>::nonzero>::res res; }; }; }; }; }; }; typedef Cons<filter, init> List; struct primes { template <typename n> struct app { struct sieve { template <typename candidates> struct app { typedef typename ifthenelse_3<List, sieve, candidates, candidates::nonzero>::res res; }; }; struct Primes_primes__fun_ { template <typename i> struct app { typedef i res; }; }; typedef typename sieve::template app< typename List::f1::template app<I<2>>::res:: template app<n>::res:: template app<Primes_primes__fun_>::res >::res res; }; }; struct main { template <typename limit_> struct app { typedef typename primes::template app<limit_>::res res; }; }; typedef typename main::template app<I<limit>>::res output; typedef typename output::print print;
C++ は純粋関数型言語である
C++ は「可変状態」をサポートしません。
そのため、OCaml 標準ライブラリ（多くはミューテーションに依存）を直接利用できず、
上記例では
List生成された C++ プログラムの実行方法
プログラムを実行するには C++ コンパイラ（またはインタプリタ）が必要です。
例では g++ を使用し、
-D$ g++ -Dlimit=100 primes.cpp
limit = 100ただし
printprimes.cpp:159:26: error: ‘print’ in ‘output’ ...
この不思議な出力形式は、C++ が C の高度なプリプロセッサとして誕生したことに由来します。
コンパイラのエラーメッセージでは OCaml の infix
::ネストされた
Cons<hd, tl>注意
C++ は既にを名前解決演算子として使用しているため、::
OCaml のリスト構造を表す構文はサポートされません。::
出力を読む際には「ネストされた」とみなしてください。Cons<hd, tl>
テンプレート深度の増加
長時間実行する計算では、デフォルトのテンプレート深度を超えてしまうことがあります。
次のようにオプションを追加して深さを増やせます。
$ g++ -ftemplate-depth=999999 -Dlimit=10000 primes.cpp
私の環境では、10 000 までの素数を約半分の時間で出力し、
約 11 GiB のメモリを消費しました。
コンパイラによって性能は異なります：
clang++わずか数 MB を使用しますが、極端に大きい入力ではセグメントフォールトすることがあります。
アルゴリズム上の考慮点
今回示した単純なエラトステネスの篩は、素数生成には効率的とは言えません。
O'Neill の優先度付きキューアルゴリズム（Okasaki の左辺ヒープに基づく）は
ずっと高速です。
この手法を用いると、
g++メモリは約 3.1 GiB に抑えられます。
今後の展望
バックエンドは他言語への拡張も可能です。
Rust が部分テンプレート特殊化をサポートするようになれば、
OCaml プログラムを直接 Rust で実行できるようになるでしょう。