2021-11-08

1 << 31 == ?

C++

C++言語における符号付き整数型の左ビットシフト<<と符号ビットの関係について。

まとめ：

2の補数表現が保証されたC++20現在、左ビットシフト<<は論理左シフト(logical left shift)が保証される。
おまけ：C++20現在、右ビットシフト>>は算術右シフト(arithmetic right shift)が保証される。

// 前提：int型==32bit幅
constexpr int x = 1 << 31;
// x == -2147483648 (== -2^{31})

C++11時点では符号反転を伴う左ビットシフト演算は未定義動作(undefined behavior)であったがnumeric_limits<T>:::min()の実装がコア定数式(core constant expression)でなくなるという問題が発覚し、C++14策定段階のCWG DR 1457にて処理系定義(implementation-defined)の振る舞いへと修正された。*1

C++20 7.6.7/p1-3より引用。

1 The shift operators << and >> group left-to-right.
　shift-expression:
　　　additive-expression
　　　shift-expression << additive-expression
　　　shift-expression >> additive-expression
The operands shall be of integral or unscoped enumeration type and integral promotions are performed. The type of the result is that of the promoted left operand. The behavior is undefined if the right operand is negative, or greater than or equal to the width of the promoted left operand.
2 The value of E1 << E2 is the unique value congruent to E1 × 2^E2 modulo 2^N, where N is the width of the type of the result. [Note: E1 is left-shifted E2 bit positions; vacated bits are zero-filled. --end note]
3. The value of E1 >> E2 is E1/2^E2, rounded down. [Note: E1 is right-shifted E2 bit positions. Right-shift on signed integral types is an arithmetic right shift, which performs sign-extension. --end note]

関連URL

*1:C++17以前は、符号付き整数型が2の補数表現とは保証されておらず、その内部表現は処理系定義となっていた。

2021-11-04

Preconditions: false is true.

C++ C++2b

C++2b(C++23)向けに提案されているコード不到達表明std::unreachable関数の前提条件。
2022-02-09追記：2022年2月会合にて(PDF)P0627R6が採択され、C++2b標準<utility>ヘッダにstd::unreachable関数が追加される。

2022-07-25追記：次世代C言語標準でもC2x(C23)向け提案(PDF)N2826が採択済み。<stddef.h>標準ヘッダの関数マクロ(function-like macro)unreachable()として導入される。

「false is true」は常に成り立たない（恒偽命題）ため、unreachable関数呼び出しは必ず未定義動作(undefined behavior)を引き起こす。つまり…どういうことだってばよ？

C++コンパイラは同関数呼び出しコード箇所には到達しないと仮定して最適化を行ってもよい、という規定となっている。提案文書(PDF) P0627R6 7. Proposed Wording より該当箇所を引用（下線部は強調）。

[[noreturn]] void unreachable();
1 Preconditions: false is true. [ Note: This precondition cannot be satisfied, thus the behavior of calling unreachable is undefined. -- end note]
2 [Example:
int f(int x) {
  switch (x) {
  case 0:
  case 1:
    return x;
  default:
    std::unreachable();
  }
}

int a = f(1);  // OK; a has value 1
int b = f(3);  // undefined behavior
-- end example]

なお初期の提案文書では素直に自然言語で記述されていた。(PDF) P0627R3 7. Proposed Wordingより該当箇所を引用。

2 Effects: The behavior of calling unreachable is undefined.

関連URL

2021-10-28

2進数フォーマット出力 in 標準C

C C++ C2x

プログラミング言語Cの次期C2x(C23)標準ライブラリprintf関数ファミリでは、変換指定子bによる2進数フォーマット出力がサポートされる。同時にscanf関数ファミリやstrtoT関数では0bプレフィクス付き文字列入力がサポートされる。*1

// C2x
#include <stdio.h>

printf("%08b", 42u);
// "00101010"

C++言語

C++20で追加されたstd::formatはバイナリ書式化指定子bをサポート済み。

// C++20
#include <format>
#include <iostream>

std::cout << std::format("{:08b}", 42u);
// "00101010"

C++17以前はstd::bitsetで手軽に済ませるか、書式化処理を自作する必要あり。

#include <bitset>
std::cout << std::bitset<8>(42u);

関連URL

(PDF) N2630 C23 proposal: formatted input/output of binary integer numbers (rev. 3)
c - Is there a printf converter to print in binary format? - Stack Overflow
cppreference std::format, cpprefjp std::foramt

*1:提案文書N2630によれば、C2xでの2進数リテラルのサポート（→id:yohhoy:20210228）に合わせた機能追加とのこと。~~もっと早くからサポートしてくれ。~~

2021-10-25

自己再帰するラムダ式 @ C++23

C++ C++2b

次期C++2b(C++23)言語仕様に追加される Deducing this により、自己再帰するラムダ式を自然に記述できるようになる。

ラムダ式の第1引数型this autoで宣言されるselfは explicit object parameter と呼ばれ、ここではラムダ式自身のクロージャ型(closure type)へ推論される。パラメータ名は任意だが、PythonやRustなど他言語の流儀にならった方が無難。

// C++2b（P0847R7より引用）
auto fact = [](this auto self, int n) -> int {
  return (n <= 1) ? 1 : n * self(n-1);
};
std::cout << fact(5);  // "120"

C++14/17/20

C++14/17/20ではジェネリックラムダ式を利用してラムダ式の自己再帰を実装する*1。呼び出し時にはクロージャオブジェクト自身を追加で指定（下記コードでは第1引数）する必要がある。

auto fact = [](auto self, int n) -> int {
  return (n <= 1) ? 1 : n * self(self, n-1);
};
std::cout << fact(fact, 5);  // "120"

不動点コンビネータfix*2を利用すると、ラムダ式への追加の引数指定が不要になる。そこまでして実装したいかはともかく。

template<typename F>
struct fix {
  F f;
  template<typename... Args>
  decltype(auto) operator()(Args&&... args) const&
    { return f(std::ref(*this), std::forward<Args>(args)...); }
};
// テンプレート推論ガイド(deduction guide)
template<typename F> fix(F) -> fix<F>;  // C++20以降は明示不要

auto fact = fix{[](auto self, int n) -> int {
  return (n <= 1) ? 1 : n * self(n-1);
}};
std::cout << fact(5);  // "120"

// C++14では型推論のためヘルパ関数 make_fix を経由する
// template<typename F> fix<F> make_fix(F f) { return {f}; }
// auto fact = make_fix([](auto self, int n) -> int { ... });

C++11

ラムダ式が導入されたC++11時点ではstd::function利用しか実現手段がない。動的メモリ確保（→id:yohhoy:20201111）や型消去(type erasure)による実行時オーバーヘッドが生じるため、実用性のほどは微妙か。素直に関数定義したほうがマシ。

#include <functional>

std::function<int(int)> fact = [&](int n) -> int {
  return (n <= 1) ? 1 : n * fact(n-1);
};
std::cout << fact(5);  // "120"

関連URL

*1:C++2bの this auto 版もジェネリックラムダ式の一種である。

*2:http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html

2021-10-05

OpenMP 最長コンストラクト

OpenMP

OpenMPの最長コンストラクト*1 Target Teams Distribute Parallel Worksharing-Loop SIMD Construct。

// OpenMP 4.0 for C/C++
#pragma omp target teams distribute parallel for simd
  /*for-loops*/

関連URL

*1:オプショナルな指示節(clause)を除いたプラグマ指定キーワード個数で計上。

2021-10-02

typeof null == 'object'

JavaScript

バグは夜更け過ぎに仕様に変わるだろう*1 -- 詠人知らず

// This stands since the beginning of JavaScript
typeof null === 'object';
In the first implementation of JavaScript, JavaScript values were represented as a type tag and a value. The type tag for objects was 0. null was represented as the NULL pointer (0x00 in most platforms). Consequently, null had 0 as type tag, hence the typeof return value "object".
A fix was proposed for ECMAScript (via an opt-in), but was rejected. It would have resulted in typeof null === 'null'.
typeof null - JavaScript | MDN

2021-09-27

signatureの定義 @ C++20

C++

C++20以降での関数シグネチャ(signature)の定義について。Concepts導入によりテンプレート制約も追加で考慮される。

まとめ：

関数：名前、引数型リスト、所属する名前空間（戻り値型は除外）
関数テンプレート：名前、引数型リスト、戻り値型、所属する名前空間、テンプレートパラメータリスト、requires節
メンバ関数：名前、引数型リスト、所属するクラス＋cv修飾＋参照修飾、後置requires節*1（戻り値型は除外）
メンバ関数テンプレート：名前、引数型リスト、戻り値型、所属するクラス＋cv修飾＋参照修飾、テンプレートパラメータリスト、requires節

前掲リスト中の下線部はC++20における変更箇所。C++17以前のシグネチャ定義は下記の通り。

関数：名前、引数型リスト、所属する名前空間（戻り値型は除外）

関数テンプレート：名前、引数型リスト、戻り値型、所属する名前空間、テンプレートパラメータリスト

メンバ関数：名前、引数型リスト、所属するクラス＋cv修飾＋参照修飾（戻り値型は除外）

メンバ関数テンプレート：名前、引数型リスト、戻り値型、所属するクラス＋cv修飾＋参照修飾、テンプレートパラメータリスト

signatureの定義 - yohhoyの日記

C++20 3.20-27より引用。構文要素template-headはテンプレートパラメータリスト(template-parameter-list)とrequires節(requires-clause)からなる。

〈function〉 name, parameter-type-list, and enclosing namespace (if any)
[Note 1: Signatures are used as a basis for name mangling and linking. -- end note]
〈non-template friend function with trailing requires-clause〉 name, parameter-type-list, enclosing class, and trailing requires-clause
〈function template〉 name, parameter-type-list, enclosing namespace (if any), return type, template-head, and trailing requires-clause (if any)
⟨friend function template with constraint involving enclosing template parameters〉 name, parameter-type-list, return type, enclosing class, template-head, and trailing requires-clause (if any)
〈class member function〉 name, parameter-type-list, class of which the function is a member, cv-qualifiers (if any), ref-qualifier (if any), and trailing requires-clause (if any)
〈class member function template〉 name, parameter-type-list, class of which the function is a member, cv-qualifiers (if any), ref-qualifier (if any), return type (if any), template-head, and trailing requires-clause (if any)
〈class member function template specialization〉 signature of the member function template of which it is a specialization and its template arguments (whether explicitly specified or deduced)

関連URL

*1:クラステンプレートに属する非テンプレートなメンバ関数は、後置requires節(trailing requires-clause)をもつ可能性がある。