yohhoyの日記

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

reproducible/unsequenced属性

C C2x gcc

プログラミング言語Cの次期C2x(C23)言語仕様に追加される属性（→id:yohhoy:20200505）reproducible, unsequencedに関するメモ。関数呼び出しに対する最適化ヒント。

// C2x
int calc(int x, int y) [[unsequenced]];

int a = /*...*/;
int b = calc(a) * 2;
/* 任意の処理 */
int c = calc(a) * 4;
// calc関数に付与されたunsequenced属性により、
// コンパイラによる下記の最適化が許可される。
// int b = calc(a) * 2;
// int c = b * 2;
// /* 任意の処理 */

まとめ：

  • 関数または関数ポインタに対して付与する属性。
  • reproducible属性＝副作用を持たない(effectless)＋連続呼出しは同一結果(idempotent)
  • unsequenced属性＝reproducible属性＋可変状態を持たない(stateless)＋引数以外に依存しない(independent)
  • 関数動作セマンティクスが指定属性に反する場合は未定義動作(undefined behavior)となる。
    • Cコンパイラは関数実装が指定属性を満たすことを検査しなくてもよいが、できる限り診断メッセージを出すことが推奨される(recommended practice)。
  • GCC拡張属性__attribute__((pure))≒reproducible、GCC拡張属性__attribute__((const))≒unsequencedと概ね近似できる。
  • 注意：unsequenced属性の関数は再入可能(reentrant)や並行実行(executed concurrently)に対する安全性を直接意味しない。*1

例えば標準ヘッダ<math.h>提供の数学関数群はエラー発生時にerrnoへ値を書込む可能性があるため、一般にreproducible／unsequencedいずれでもない。実引数に対して制約条件を保証できるのであれば、プログラマの責任で同属性を付与した関数再宣言を行ってもよい。提案文書N2956よりコード例を引用。*2 *3

// C2x
#include <math.h>
#include <fenv.h>

inline double distance (double const x[static 2]) [[reproducible]] {
  #pragma FP_CONTRACT OFF
  #pragma FENV_ROUND FE_TONEAREST
  // We assert that sqrt will not be called with invalid arguments
  // and the result only depends on the argument value.
  extern typeof(sqrt) [[unsequenced]] sqrt;
  return sqrt(x[0]*x[0] + x[1]*x[1]);
}

double g (double y[static 1], double const x[static 2]) {
  // We assert that distance will not see different states of the floating
  // point environment.
  extern double distance (double const x[static 2]) [[unsequenced]];
  y[0] = distance(x);
  ...
  return distance(x); // replacement by y[0] is valid
}

C2x WD N3047 6.7.12.7/p3, p5-8より一部引用。

3 The main purpose of the function type properties and attributes defined in this clause is to provide the translator with information about the access of objects by a function such that certain properties of function calls can be deduced; the properties distinguish read operations (stateless and independent) and write operations (effectless, idempotent and reproducible) or a combination of both (unsequenced). (snip)

5 A function definition f is stateless if any definition of an object of static or thread storage duration in f or in a function that is called by f is const but not volatile qualified.
6 (snip) A function pointer value f is independent if for any object X that is observed by some call to f through an lvalue that is not based on a parameter of the call, then all accesses to X in all calls to f during the same program execution observe the same value; otherwise if the access is based on a pointer parameter, there shall be a unique such pointer parameter P such that any access to X shall be to an lvalue that is based on P. A function definition is independent if the derived function pointer value is independent.
7 A store operation to an object X that is sequenced during a function call such that both synchronize is said to be observable if X is not local to the call, if the lifetime of X ends after the call, if the stored value is different from the value observed by the call, if any, and if it is the last value written before the termination of the call. An evaluation of a function call is effectless if any store operation that is sequenced during the call is the modification of an object that synchronizes with the call; (snip)
8 An evaluation E is idempotent if a second evaluation of E can be sequenced immediately after the original one without changing the resulting value, if any, or the observable state of the execution. A function definition is idempotent if the derived function pointer value is idempotent.
9 A function is reproducible if it is effectless and idempotent; it is unsequenced if it is stateless, effectless, idempotent and independent.

関連URL

*1:unsequencedを満たすには関数終了時点で観測可能な変化がなければよく、関数は（呼出し元がポインタ経由で渡した）静的記憶域期間(static storage duration)変数に対して読取／書込を行う可能性がある。...そんな用途にstatic変数を使うんじゃねぇ（｀ェ´）

*2:関数引数リスト中の T arg[static N] はC99で導入された構文。T 型のポインタ型仮引数 arg が少なくとも N 要素を持つデータ領域を指すことを表明する。id:yohhoy:20170503 も参照のこと。

*3:typeof はC2xで導入される型情報を取り出す演算子（→id:yohhoy:20220912）。typeof(sqrt) はC標準ライブラリ関数 sqrt の型情報つまり「戻り値doubleかつ引数リスト(dubule)をもつ関数型」を表す型指定子であり、該当文は extern double sqrt(double) [[unsequenced]]; 関数宣言となる。

nullptr定数 in 標準C

C C2x

プログラミング言語Cの次期仕様C2x(C23)にて、ついにC言語にも真のヌルポインタ定数nullptrがやってくる。
C++11（→id:yohhoy:20120503）から遅れること12年。

int *p1 = nullptr;  // C2x以降
int *p2 = NULL;
int *p3 = 0;

まとめ：

  • C/C++両言語のnullptrがセマンティクス一致するよう設計されている。
  • 事前定義定数*1nullptrは、専用のnullptr_t型が取りうる唯一の値。
    • 定数nullptrはいつでも利用可能（ヘッダinclude不要）。
    • nullptr_t型は標準ヘッダ <stddef.h> で定義される。*2
  • C2xで追加されるnullptrのほか、現行の整数定数値0やマクロNULLをいずれもヌルポインタ定数(null pointer constant)として扱う。
  • nullptr_t型はvoid*型と同じサイズ／アライメントを持ち、nullptrと(void*)0の内部表現は等しい。
    • 可変引数リストに対する番兵(sentinel)実引数として、nullptrはNULLよりもポータブルに使える。（→id:yohhoy:20160224）

関連URL

*1:predefined constants はC2xにて新たに導入される構文要素。false, true, nulllptr の3種類が追加される。false/true については C言語のbool型とその名前について 〜もう_Boolは嫌だ〜 を参照。

*2:C2xで導入される typeof_unqual を利用して typedef typeof_unqual(nullptr) nullptr_t; と定義される。

改行コード(CR/LF)と改行文字と標準C

C

プログラミング言語C標準規格における改行文字(new-line character)と改行コードCR, LFとの関係性について。

まとめ：

  • C標準規格ではプログラム内部で扱う「改行文字」と、外部ファイルにおける具体的なCR, LF等の「文字コード」を区別する。*1 *2
  • 改行文字をファイル上でどう表現するかについて何ら規定しない。CR/LFを使わない方式も想定されている。
    • UNIX互換システムの場合、改行文字==改行コードLF(0x0A)となる。
    • Windows OSの場合、改行文字は2個の改行コードCRLF(0x0D 0x0A)で表現される。
    • 上記のような改行コードによる行区切り表現だけでなく、メタ情報を利用した行区切り位置表現、長さプレフィックスと文字列データ表現、固定長レコードと特殊パディング文字表現（！）*3など、多種多様なテキストデータの表現方式を許容する。
  • 仮想ターミナルなどの文字表示デバイスへ出力する場合、下記エスケープシーケンスの動作を規定する。
    • \n(new-line)：次行の先頭位置にカーソル位置を移動する。
    • \r(carriage return)：現在行の先頭位置にカーソル位置を移動する。

文字集合(Character sets)

C99 5.2.1/p1, p3より一部引用（下線部は強調）。

1 Two sets of characters and their associated collating sequences shall be defined: the set in which source files are written (the source character set), and the set interpreted in the execution environment (the execution character set). (snip)

3 Both the basic source and basic execution character sets shall have the following members:
　(snip)
In source files, there shall be some way of indicating the end of each line of text; this International Standard treats such an end-of-line indicator as if it were a single new-line character. In the basic execution character set, there shall be control characters representing alert, backspace, carriage return, and new line. (snip)

C99 Rationale, 5.2.1より一部引用。

The C89 Committee ultimately came to remarkable unanimity on the subject of character set requirements. There was strong sentiment that C should not be tied to ASCII, despite its heritage and despite the precedent of Ada being defined in terms of ASCII. Rather, an implementation is required to provide a unique character code for each of the printable graphics used by C, and for each of the control codes representable by an escape sequence. (No particular graphic representation for any character is prescribed; thus the common Japanese practice of using the glyph "¥" for the C character "\" is perfectly legitimate.) Translation and execution environments may have different character sets, but each must meet this requirement in its own way. The goal is to ensure that a conforming implementation can translate a C translator written in C.

For this reason, and for economy of description, source code is described as if it undergoes the same translation as text that is input by the standard library I/O routines: each line is terminated by some newline character regardless of its external representation.

文字表示セマンティクス(Character display semantics)

C99 5.2.2/p2-3より一部引用（下線部は強調）。

2 Alphabetic escape sequences representing nongraphic characters in the execution character set are intended to produce actions on display devices as follows:

  • (snip)
  • \n (new line) Moves the active position to the initial position of the next line.
  • \r (carriage return) Moves the active position to the initial position of the current line.
  • (snip)

3 Each of these escape sequences shall produce a unique implementation-defined value which can be stored in a single char object. The external representations in a text file need not be identical to the internal representations, and are outside the scope of this International Standard.

C99 Rationale, 5.2.2より一部引用（下線部は強調）。

The Standard defines a number of internal character codes for specifying "format-effecting actions on display devices," and provides printable escape sequences for each of them. These character codes are clearly modeled after ASCII control codes, and the mnemonic letters used to specify their escape sequences reflect this heritage. Nevertheless, they are internal codes for specifying the format of a display in an environment-independent manner; they must be written to a text file to effect formatting on a display device. The Standard states quite clearly that the external representation of a text file (or data stream) may well differ from the internal form, both in character codes and number of characters needed to represent a single internal code.

The distinction between internal and external codes most needs emphasis with respect to new-line. INCITS L2, Codes and Character Sets (and now also ISO/IEC JTC 1/SC2/WG1, 8 Bit Character Sets), uses the term to refer to an external code used for information interchange whose display semantics specify a move to the next line. Although ISO/IEC 646 deprecates the combination of the motion to the next line with a motion to the initial position on the line, the C Standard uses new-line to designate the end-of-line internal code represented by the escape sequence '\n'. While this ambiguity is perhaps unfortunate, use of the term in the latter sense is nearly universal within the C community. But the knowledge that this internal code has numerous external representations depending upon operating system and medium is equally widespread.

ストリーム(Streams)

C99 7.19.2/p1-3より一部引用（下線部は強調）。

1 Input and output, whether to or from physical devices such as terminals and tape drives, or whether to or from files supported on structured storage devices, are mapped into logical data streams, whose properties are more uniform than their various inputs and outputs. Two forms of mapping are supported, for text streams and for binary streams.232)
脚注232) An implementation need not distinguish between text streams and binary streams. In such an implementation, there need be no new-line characters in a text stream nor any limit to the length of a line.

2 A text stream is an ordered sequence of characters composed into lines, each line consisting of zero or more characters plus a terminating new-line character. Whether the last line requires a terminating new-line character is implementation-defined. Characters may have to be added, altered, or deleted on input and output to conform to differing conventions for representing text in the host environment. Thus, there need not be a one-to-one correspondence between the characters in a stream and those in the external representation. Data read in from a text stream will necessarily compare equal to the data that were earlier written out to that stream only if: the data consist only of printing characters and the control characters horizontal tab and new-line; no new-line character is immediately preceded by space characters; and the last character is a new-line character. Whether space characters that are written out immediately before a new-line character appear when read in is implementation-defined.

C99 Rationale, 5.2.1, 7.19.2より一部引用。

C inherited its notion of text streams from the UNIX environment in which it was born. Having each line delimited by a single newline character, regardless of the characteristics of the actual terminal, supported a simple model of text as a sort of arbitrary length scroll or "galley." Having a channel that is "transparent" (no file structure or reserved data encodings) eliminated the need for a distinction between text and binary streams.

(snip)

Troublesome aspects of the stream concept include:

The definition of lines. In the UNIX model, division of a file into lines is effected by newline characters. Different techniques are used by other systems: lines may be separated by CR-LF (carriage return, line feed) or by unrecorded areas on the recording medium; or each line may be prefixed by its length. The Standard addresses this diversity by specifying that newline be used as a line separator at the program level, but then permitting an implementation to transform the data read or written to conform to the conventions of the environment.
Some environments represent text lines as blank-filled fixed-length records. Thus the Standard specifies that it is implementation-defined whether trailing blanks are removed from a line on input. (This specification also addresses the problems of environments which represent text as variable-length records, but do not allow a record length of 0: an empty line may be written as a one-character record containing a blank, and the blank is stripped on input.)

Transparency. Some programs require access to external data without modification. For instance, transformation of CR-LF to a newline character is usually not desirable when object code is processed. The Standard defines two stream types, text and binary, to allow a program to define, when a file is opened, whether the preservation of its exact contents or of its line structure is more important in an environment which cannot accurately reflect both.

関連URL

*1:プログラムへのデータ入出力をテキストストリーム(text stream)で扱う場合のお話。バイナリストリーム(binary stream)で扱う場合は外部ファイル上の文字コード値に直接アクセスする。

*2:標準入出力 stdin, strerr や標準エラー出力 stderr はいずれもテキストストリームとして初期化される。（C99 7.19.3/p7）

*3:テキストストリームをファイルに書き出す場合、処理系によっては一定長に切詰め(truncated)られる可能性が明記されている。（C99 7.19.3/p2）

MC Hammer in C++ Standard

C++ C++2b

プログラミング言語C++標準規格のサンプルコードでビートを刻むMCハマー。
"U Can't Touch This" ( 'ω' و(و♪ ƪ( 'ω' ƪ )♪

template<ranges::constant_range R>
void cant_touch_this(R&&);

vector<char> hammer = {'m', 'c'};
span<char> beat = hammer;
cant_touch_this(views::as_const(beat));
  // will not modify the elements of hammer
https://github.com/cplusplus/draft/commit/32535186bc66b3485194b41d5b2107e15c6bd34a

std::ranges::constant_rangeコンセプトやstd::views::as_constレンジアダプタはC++2b(C++23)標準ライブラリへの追加予定機能。

関連URL

std::shared_ptr型と->*演算子とstd::invoke関数

C++

C++標準ライブラリのスマートポインタ型std::shared_ptr<T>では->*演算子オーバーロードを提供しない（注：->はあるよ）。

#include <memory>

struct X { int mf(); };
// メンバ関数ポインタ
int (X::*pmf)() = &X::mf;

// (通常)ポインタ型
X* p = new X;
p->mf();      // OK
(p->*pmf)();  // OK

// std::shared_ptr型
std::shared_ptr<X> sp{ p };
sp->mf();      // OK
(sp->*pmf)();  // NG!
(sp.get()->*pmf)();  // OK: get()でポインタを取出す
(&*sp->*pmf)();      // OK: 暗号じみた記法

C++17で追加されたstd::invoke関数を利用すると、メンバ関数ポインタ呼び出しであっても通常ポインタとスマートポインタ型を統一的に扱える。

#include <functional>

std::invoke(pmf, p);   // OK: X*
std::invoke(pmf, sp);  // OK: std::shared_ptr<X>

// 代替(C++03/11/14)
(*s.*pmf)();   // OK
(*sp.*pmf)();  // OK

マイナー機能のため有用性は低いが、技術的には->*演算子オーバーロードを提供可能。C++14機能までを使った実装例（エッセンスのみ）：

// スマートポインタ型
template <typename T>
struct SP {
  T* p_ = nullptr;
  SP(T* p): p_(p) {}

  // ->演算子オーバーロード
  T* operator->() { return p_; }

  // ->*演算子オーバーロード
  template<typename R, typename... Ts>
  auto operator->*(R (T::*pmf)(Ts...)) {
    return [p=p_, pmf](Ts&&... args) -> R {
      return (p->*pmf)(std::forward<Ts>(args)...);
    };
  }
};

// スマートポインタ型
SP<X> sp{ p };
sp->mf();      // OK
(sp->*pmf)();  // OK

関連URL

std::generator<T／T&&／T&／const T&>

C++ C++2b

次期C++2b(C++23)標準ライブラリのコルーチンサポート型std::generator<Ref>（→id:yohhoy:20220801）の第1テンプレートパラメータRefと、オブジェクトのコピー／ムーブの関係性についてメモ。

まとめ：

  • 利用側にconst参照を提供：const-lvalue参照const T&を指定。
  • 利用側に可変参照を提供：lvalue参照T&を指定。
  • ムーブのみ(Move-only)型：値型Tまたはrvalue参照型T&&を指定。
    • 実動作は両者で同一。“ムーブ” 動作を示唆するT&&の方が好ましい？
  • プリミティブ型など*1：値型Tを指定。
  • 利用側の範囲for：auto&&（→id:yohhoy:20120609）またはconst auto&を推奨。

テンプレートパラメータRefに値型Tまたはその参照型を指定した場合*2、各箇所において発生するコピー／ムーブは下表のとおり：

Ref yield-v yield-cv yield-rv consume-v
T 1 copy 1 copy 0 1 move
T&& 1 copy 1 copy 0 1 move
T& 1 copy 1 copy (ill-formed) 1 copy
const T& 0 0 0 1 copy

凡例：0=コピー／ムーブなし、(ill-formed)=コンパイルエラー

// C++2b
#include <generator>

// ユーザ定義コルーチン
std::generator<??> gen()
{
  T v;
  co_yield v;   // yield-v
  const T cv;
  co_yield cv;  // yield-cv

  // yield-rv
  co_yield T{};
  co_yield std::move(v);
}

// 利用側コード
void consumer()
{
  // consume-v
  for (auto v: gen()) { ... }

  // 下記2パターンは常にコピー／ムーブ発生しない
  for (const auto& cr: gen()) { ... }
  for (auto&& ur: gen()) { ... }
}

ノート：コルーチン内でco_yield std::move(v);を記述しても、即座にはムーブ処理が行われないことに留意。Ref=T／T&&であれば利用側コードでムーブ処理が行われる。

関連URL

*1:コピー処理コストの安い型：std::string_view や std::span<T> 型も含まれる。

*2:C++ムーブセマンティクスの文脈では const T&& 型には使い道がない。

std::generator<R>

C++ C++2b

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

提案文書P2502R2よりコード引用：*1

// C++2b
#include <functional>
#include <generator>
#include <range>
#include <utility>

std::generator<int> fib() {
  auto a = 0, b = 1;
  while (true) {
    co_yield std::exchange(a, std::exchange(b, a + b));
  }
}

int answer_to_the_universe() {
  auto rng = fib() | std::views::drop(6) | std::views::take(3);
  return std::ranges::fold_left(std::move(rng), 0, std::plus{});
}

コルーチンfibから生成されるフィボナッチ数列 0, 1, 1, 2, 3, 5, 8, 13, 21... のうち、先頭6要素を破棄(drop)した後に3要素のみ取出す(take)遅延評価レンジrngを作成する（この時点ではコルーチン本体処理は開始されない）。rngに対して初期値 0 と算術加算(plus)による畳み込み(fold)操作を行い、結果値 42 を得る。

まとめ：

  • ユーザ定義コルーチンの記述で利用するR型の値を生成するジェネレータ(generator)型。Rangesライブラリとの高い親和性をもつ。
    • co_yield valによる単一値の生成。
    • co_yield elements_of(range)による複数値の逐次生成。
    • コルーチン本体処理は遅延評価される。*2
  • 新しい標準ヘッダ<generator>*3
    • クラステンプレートstd::generator<R, V, Allocator>（V, Allocatorは省略可）
    • generatorはviewコンセプトとinput_rangeコンセプトのモデル。範囲for文や各種レンジアダプタ(range adaptor)と組み合わせて利用可能。
  • 標準ヘッダ<ranges>の拡張
    • std::ranges::elements_of<R, Allocator>クラステンプレート（Rはrangeコンセプトのモデル、Allocatorは省略可）
    • elements_ofはco_yield式に対するタグ型として機能する。
  • ジェネレータ利用側イテレータの提供型
  • generator<R>型（V省略時）
    • 大半のユースケースはテンプレートパラメータR型のみ指定でOK。
    • Reference型=R&&*5／Value型=remove_cvref_t<R>
    • 例: generator<int>, generator<string>
  • generator<R, V>型
    • 参照プロキシ型の利用や、右辺値を生成する特殊なユースケース向け。
    • Reference型=R／Value型=V
    • 例: generator<string_view, string>
  • co_yield val
    • co_yield式の評価結果はvoid。
    • co_yield式に指定する右辺値valはコピーされない（R=値型Tのシンプルなケースを想定）。
    • 内部的には指定値へのアドレス情報のみを保持しており(value_ = std::addressof(val))、ジェネレータ利用側イテレータで実体(*value_)をReference型へとキャストする。
    • co_yield式に指定する左辺値valはAwaitableオブジェクト内部にコピー格納され、そのアドレス情報が保持される。
    • 2022-08-10追記：テンプレートパラメータRへ指定する型とコピー／ムーブの関係性は id:yohhoy:20220810 を参照。
  • co_yield elements_of(range)
    • レンジrangeの全要素eに対して、同コルーチンから逐次的に生成(co_yield e)する。Flatten操作。
    • コルーチンが入れ子構造になる場合、動作効率改善のため内部的に対称転送(symmetric transfer)が行われる。*6
  • co_await式はサポートしない。
  • コルーチンから送出された例外はジェネレータ利用側にそのまま伝搬する（→id:yohhoy:20211112）。
    • co_yield elements_of(child)の子コルーチンchildの送出例外は、親コルーチン側でもcatch可能。ハンドリングしなければ親コルーチンが返すジェネレータ利用側へと伝搬する。
  • アロケータサポート
    • コルーチンフレーム*7のメモリ確保／解放に用いられる。
    • テンプレートパラメータAllocator型またはコルーチン引数にてstd::allocator_arg_t＋アロケータ型を指定する。
    • アロケータの型消去(type erasure)をサポート。例: std::generator<int>型は任意のアロケータ型をコルーチンフレーム上に格納する。
    • ステートレス／ステートフル両アロケータをサポート。
  • 動作性能はC++コンパイラの最適化性能に強く依存する（→id:yohhoy:20180415）。

関連URL

*1:std::ranges::fold_left アルゴリズムは P2322R6 にてC++2b標準ライブラリへ追加予定となっている。

*2:std::generator<R>::promise_type 型の初期サスペンドポイント(initial_suspend)は suspend_always 型を返す。

*3:C++20 <coroutine>ヘッダはコルーチン機構実装用の低レイヤ機能のみを提供する。

*4:Value型は std::generator それ自身からは参照されず、利用側で イテレータの value_type 型にアクセスするユースケース向け。

*5:テンプレートパラメータ R に対して "reference collapsing" 規則が適用される。例: R=const T& ならば R&&=const T& となる。

*6:std::generator<R>::promise_type 型の yield_value メンバ関数が返すAwaiter型では、await_suspend メンバ関数が転送先コルーチンの std::coroutine_handler 値を返す。

*7:C++標準規格では "coroutine state" と呼称される。