yohhoyの日記

技術的メモをしていきたい日記

連番配列を生成

JavaScript(ECMAScript)で連番配列を生成するコード片。いわゆる range 関数に相当。

// NG: [undefined, undefined, undefined, undefined, undefined]
// { length: 5 } のみ設定されたArrayオブジェクトが生成される
// 各要素は未設定(undefinedとも異なる状態)となっている
Array(5).map((val, idx) => idx);
[,,,,,].map((val, idx) => idx);

// OK: [0, 1, 2, 3, 4]
Array(5).fill(undefined).map((val, idx) => idx);
Array(5).fill(0).map((val, idx) => idx);
Array.from(Array(5), (val, idx) => idx);
Array.from({length: 5}, (val, idx) => idx);
[...Array(5)].map((val, idx) => idx);
[...Array(5).keys()];

関連URL

std::expected<T, E>

次期C++2b(C++23)標準ライブラリに追加されるstd::expected<T, E>クラステンプレートについてメモ。

  • 従来C++例外機構(throw文+try/catch構文)に代わり、関数の演算結果(T型)またはエラー情報(E型)を “値” として返す(return)ための部品。
  • C++17 std::optional<T>型の無効値(std::nullopt)表現に代わり、具体的なエラー情報(E型)を保持可能に拡張された型。*1
  • 新しい標準ヘッダ<expected>
    • クラステンプレートexpected<T, E>、補助型unexpected<E>*2、タグunexpect、例外型bad_expected_access<E>
  • expected<T, E> == 結果Tとエラーunexpected<E>の直和型*3
    • constexpr文脈でも利用可能
    • expected<void, E>特殊化 == エラーのみを保持する
    • std::optional同様に参照型は未サポート
  • expected<T, E>型への代入:
    • 結果/Tへ変換可能な型:r = t;またはr = {std::in_place, t};*4
    • エラー/Eへ変換可能な型:r = std::unexpected(e);またはr = {std::unexpect, e};
  • 保持値アクセス:
    • 結果/エラー保持判定:has_value, explicit operator bool*5
    • 結果(T型):value, value_or, operator->, operator*
    • エラー(E型):error
    • 結果未保持でのvalueメンバ関数呼び出しはstd::bad_expected_access<E>{error()}例外送出
    • 結果未保持での間接参照(->, *)アクセスは未定義動作(undefined behavior)*6
    • エラー未保持でのerrorメンバ関数呼び出しは未定義動作
  • expectedモナディック(monadic)操作はC++2bには間に合わず*7C++2c(C++26)向け提案文書 P2505R1 にて継続検討中。
    • C++2b標準ライブラリoptionalモナディック操作(and_then, or_elseなど)は P0789R8 が採択済み。

Boost.Outcomeライブラリとの比較:

関連URL

*1:std::optional<T> ≒ std::expected<T, std::nullopt_t>

*2:C++20現在、識別子 unexpected はZombie nameとして予約されおり、expected<T, E> 導入に伴ってC++2bで蘇生(?)された初のケース。C++的ゾンビのお名前 参照。

*3:無効値 nullopt でデフォルト構築される std::optional<T> とは異なり、エラー情報を明示的に保持する std::expected<T, E> ではデフォルト構築後は結果値 T{} を保持している。

*4:https://cpprefjp.github.io/reference/utility/in_place_t.html

*5:if文の条件式などに expected<T, E> 型の値を記述することで、結果を保持しているか否かを判定可能(→id:yohhoy:20121110

*6:提案文書P0323R12 §3.14: "Using the indirection operator for an object that does not contain a value is undefined behavior. This behavior offers maximum runtime performance."

*7:https://github.com/cplusplus/papers/issues/1161#issuecomment-1027125553

コンセプト制約式の構成:包摂関係 vs. コンパイル時間

C++20コンセプトでは制約式(constraint-expression)を&&(conjunction)/||(disjunction)で組み合わせることで複雑な制約式を表現できる。一方で制約式が多数の原始制約(atomic constraint)から構成されるケースでは、包摂関係(subsumption relation)判定のための正規化プロセスが複雑になりコンパイル時間に悪影響を及ぼす。

例えばコンセプトX, Y, Zからなるコンセプトの定義方法として、下記2種類が考えられる。コンセプトC1は3個の原始制約から、一見すると記述が冗長なコンセプトC2は2個の原始制約から構成されるため、包摂関係が重要でなければ後者C2の方がC++コンパイラへの負荷が小さい。

template <typename T> concept X = /*(原始制約#1)*/;
template <typename T> concept Y = /*(原始制約#2)*/;
template <typename T> concept Z = /*(原始制約#3)*/;

template <typename T>
concept C1 = X<T> && (Y<T> || Z<T>);
//           ^^^^     ^^^^    ^^^^
//            #1       #2      #3

template <typename T>
concept C2 = X<T> && requires { requires (Y<T> || Z<T>); };
//           ^^^^    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//            #1     原始制約#4

コンセプトC1C2単体利用であれば両者の意味論に差異はない。C1は制約X && Y, X && Z, Y || Zとの間に包摂関係が成り立つが*1C2ではいずれの包摂関係も成り立たない。*2

// X,Y,Zコンセプトを満たすU型を仮定
template <typename T> requires C1<T>
int f(T) { return 1; }
template <typename T> requires X<T> && Y<T>
int f(T) { return 2; }
assert( f(U{}) == 2 );

template <typename T> requires C2<T>
int g(T) { return 1; }
template <typename T> requires X<T> && Y<T>
int g(T) { return 2; }
// g(U{}) はオーバーロード解決が曖昧

実際にC++2b(C++23)向け提案文書(PDF)P2404R1では、コンパイル時間短縮を目的としてコンセプト定義の変更を行っている。

3.1.1 Avoiding disjunctions
Disjunctions in concepts may slow down compilation times due to added costs in the conversion to disjunctive normal form, so it is desirable to avoid them. As such, this new disjunction should be made into an atomic constraint to avoid this issue. Lost functionality is not a concern in this case, because users are not expected to find it useful to have subsumption between equality_comparable_with<T, U> and convertible_to<const T&, const common_reference_t<const T&, const U&>> or the other similar cases.
Avoiding the disjunctions in this case is easily resolved by forcing the disjunction to be an atomic constraint via a requires expression and nested requirements:

requires {
  requires convertible_to<const T&, const C&> || convertible_to<T&&, const C&>;
}

In this particular case, we have two disjunctions, one for T and one for U. Having a conjunction between atomic constraints is not useful, so the proposed wording will merge them into a single atomic constraint.

提案文書P2304R0およびP2404R1より、common-comparison-supertype-with説明用コンセプト定義を改変引用(メタ関数への引数部は略記)。

// P2304R0
template<class T, class U>
concept common-comparison-supertype-with =
  same_as</*...*/> &&
  (convertible_to</*...*/> || convertible_to</*...*/>) &&
  (convertible_to</*...*/> || convertible_to</*...*/>);

// P2404R1
template<class T, class U>
concept common-comparison-supertype-with =
  same_as</*...*/> &&
  requires {
    requires convertible_to</*...*/> || convertible_to</*...*/>;
    requires convertible_to</*...*/> || convertible_to</*...*/>;
  };

前者のコンセプト定義では10個の原始制約から構成されるのに対し、後者では3個の原始制約(&&に続くrequires式全体で1つの原始制約)から構成される。*3

関連URL

*1:https://wandbox.org/permlink/6l0UgFuTWECJZ9tM

*2:コンセプト C1 と コンセプト X、コンセプト C2 と コンセプト X の間にはそれぞれ包摂関係が成り立つ。https://wandbox.org/permlink/wpodIgRHXuNiVZI6

*3:C++20標準ライブラリ提供の std::same_as コンセプトは2個の原始制約(→id:yohhoy:20190925)、std::convertible_to コンセプトは2個の原始制約から構成される。

*4:2022年2月現在、C++ Core Guidelines ルールT.31はタイトルのみで説明文は未記述。

std::views::commonレンジアダプタの制約

C++20 RangeからC++17互換イテレータペアへの変換にはstd::views::commonレンジアダプタ(range adaptor)を利用する。ただしstd::ranges::basic_istream_viewなどムーブのみ/コピー不可なイテレータからなる一部Rangeは変換できない。*1

#include <sstream>
#include <ranges>
#include <vector>

auto ints = std::istringstream{"0 1 2 3 4"};
auto cv = std::ranges::istream_view<int>(ints)
        | std::views::filter([](int n){ return n % 2 == 0; })
        | std::views::common;  // NG: ill-formed
std::vector<int> vec(cv.begin(), cv.end());

これはstd::ranges::common_view<V>クラステンプレート制約として、対象Viewのイテレータ型(iterator_t<V>)がstd::copyableコンセプトを満たすことを要求するため。C++17互換イテレータではコピー可能・ムーブ可能を要求するが、C++20 Rangeを構成するイテレータはコピー不可・ムーブ可能であればよい。*2

前掲コードのようにRange/Viewからコンテナへ変換したい場合、次期C++2b(C++23)標準ライブラリではstd::views::toレンジアダプタ(→id:yohhoy:20210902)が利用可能となる。

// C++2b(C++23)
#include <sstream>
#include <ranges>
#include <vector>

auto ints = std::istringstream{"0 1 2 3 4"};
auto vec = std::ranges::istream_view<int>(ints)
         | std::views::filter([](int n){ return n % 2 == 0; })
         | std::views::to<std::vector>();
// vec == std::vector<int>{0, 2, 4}

C++20 24.6.4.3, 24.7.13.1, 24.7.13.2より一部引用。

namespace std::ranges {
  template<movable Val, class CharT, class Traits>
    requires default_initializable<Val> &&
             stream-extractable<Val, CharT, Traits>
  class basic_istream_view<Val, CharT, Traits>::iterator {
  public:
    // (snip)
    iterator(const iterator&) = delete;
    iterator(iterator&&) = default;
    iterator& operator=(const iterator&) = delete;
    iterator& operator=(iterator&&) = default;
    // (snip)
  };
}

1 common_view takes a view which has different types for its iterator and sentinel and turns it into a view of the same elements with an iterator and sentinel of the same type.
2 [Note: common_view is useful for calling legacy algorithms that expect a range's iterator and sentinel types to be the same. --end note]
3 The name views::common denotes a range adaptor object (24.7.1). (snip)

namespace std::ranges {
  template<view V>
    requires (!common_range<V> && copyable<iterator_t<V>>)
  class common_view : public view_interface<common_view<V>> {
    // (snip)
  };
}

関連URL

*1:std::ranges::istream_view<Val> は std::ranges::basic_istream_view<Val, char> のエイリアステンプレート。(PDF)P2432R1によりC++20 DRとして遡及適用。

*2:現行gcc/libstdc++は難解なエラーメッセージを生成する https://wandbox.org/permlink/qu5Hl1Lbj6fdhQot

コンセプト定義への属性指定

C++20言語仕様では、コンセプト定義に対して属性(attribute)を指定できない。

template <typename T>
[[deprecated("concept")]]  // NG: ill-formed
concept C = /*...*/;

// OK: 変数テンプレート
template <typename T>
[[deprecated("variable")]]
T var = /*...*/;

// OK: 関数テンプレート
template <typename T>
[[deprecated("function")]]
void func(T) { /*...*/ }

// OK: クラステンプレート
template <typename T>
class [[deprecated("class")]] S0 { /*...*/ };

// OK: エイリアステンプレート
template <typename T> struct S1 {};
template <typename T>
using A [[deprecated("alias")]] = S1<T>;

メモ:エイリアステンプレート(alias template)に対するdeprecated属性指定は、GCC/Clangともに機能しない模様… MSVCは期待通り警告C4996が報告される。

C++20 13.1/p1, 13.7.8/p1より一部引用。

1 A template defines a family of classes, functions, or variables, an alias for a family of types, or a concept.

template-declaration:
  template-head declaration
  template-head concept-definition
template-head:
  template < template-parameter-list > requires-clauseopt
template-parameter-list:
  template-parameter
  template-parameter-list , template-parameter
requires-clause:
  requires constraint-logical-or-expression
(snip)

1 A concept is a template that defines constraints on its template arguments.

concept-definition:
  concept concept-name = constraint-expression ;
(snip)

関連URL

クラステンプレート特殊化型判定

プログラミング言語C++において、与えられた型があるクラステンプレートの特殊化(specialization)か否かを判定する方法。

下記コードは複素数std::complexの特殊化か否かを判定するメタ関数およびコンセプト実装例。

// C++11/14/17: is_complexメタ関数
#include <complex>
#include <type_traits>

template <typename T>
struct is_complex : std::false_type {};
template <typename T>
struct is_complex<std::complex<T>> : std::true_type {};

static_assert( is_complex<std::complex<float>>::value );
static_assert( !is_complex<double>::value );
// C++20: is_complexコンセプト
#include <concepts>
#include <complex>

template <typename T>
concept is_complex = requires (T t) {
  { std::complex{std::move(t)} } -> std::same_as<T>;
  // ムーブのみ可能な型を考慮してrvalueへキャスト
  // コピー可能な型では単にt(lvalue)記述でもよい
};

static_assert( is_complex<std::complex<float>> );
static_assert( !is_complex<double> );

メタ関数バージョンは非型テンプレートパラメータ(non-type template parameter)を含むクラステンプレート(例:std::array, std::span)には利用できない。コンセプトバージョンはコピー/ムーブ不可のクラステンプレート(例:std::atomic, std::counting_semaphore)には利用できない。

関連URL

*1:提案 P2098R1 は2020年5月会合で棄却済み。https://github.com/cplusplus/papers/issues/812 参照。

Math.min@浮動小数点数の実装

Java標準ライブラリMath.minメソッドの実装についてメモ。

浮動小数点数型(float, double)に対するminでは、NaN(Not a Number)および負のゼロ(-0.0)を考慮する必要がある。*1

public static double min(double a, double b) {
  if (a != a)
    return a;   // a is NaN
  if ((a == 0.0d) && (b == 0.0d)
      && (Double.doubleToRawLongBits(b) == negativeZeroDoubleBits)) {
    // Raw conversion ok since NaN can't map to -0.0.
    return b;
  }
  return (a <= b) ? a : b;
}

// Use raw bit-wise conversions on guaranteed non-NaN arguments.
private static final long negativeZeroDoubleBits
  = Double.doubleToRawLongBits(-0.0d);

2つのdouble値のうち小さいほうを返します。 つまり、結果は負の無限大に近いほうの値となります。 引数の値が同じ場合は同じ値を返します。 どちらかの値がNaNの場合はNaNを返します。 数値比較演算子とは異なり、このメソッドは負のゼロが厳密には正のゼロよりも小さいと見なします。 一方の引数が正のゼロでもう一方が負のゼロの場合は、負のゼロを返します。

https://docs.oracle.com/javase/jp/10/docs/api/java/lang/Math.html#min(double,double)

一方、整数型(int, long)に対するminは比較演算<=を用いてシンプルに実装される。*2

public static int min(int a, int b) {
  return (a <= b) ? a : b;
}

関連URL