はてなブックマーク

浮動小数点数の演算結果は環境によって変わる場合があります。どういう場合に変わることがあり、それはどういう原因によるのでしょうか。この記事では、演算結果が変わる原因として考えられるものをいくつか紹介します。 対象とする言語はC言語とします。基本的にC17の前提で書きますが、一部にC23への言及を含みます。 C言語では浮動小数点演算の精度は処理系定義です（C17 5.2.4.2.2.7）。C言語的に浮動小数点演算についてまともなことが言えるのは処理系がAnnex Fに準拠している場合です。C17のAnnex FはIEEE 754-1985を参照し、C23のAnnex FではIEEE 754-2019を参照します。 ただ、この記事では「どういう場合に変わるか」を考え、「どういう場合に結果が変わらないことが保証されるか」はあまり考えないので、Annex F準拠であるかはあまり重要ではないかもしれま

浮動小数点数にはIEEE 754という標準規格がありますが、規格の範囲内であっても僅かに実装による差異が認められています。その一つがNaNのビットパターンです。 WebAssemblyはNaNのビットパターンに関しては実装依存の結果を許容しており、Wasmランタイムは特に深い理由がなければホストCPUの浮動小数点命令をそのまま用いると考えられるため、結果として「WasmからNaNのビットパターンを観測することでホストのCPUの命令セットを推測する」ことができます。 ここでは、「x86(_64)」「RISC-V」「その他（Armなど）」の3択で判定することを目指します。 判定コード 判定するコードは以下です： #include <inttypes.h> #include <stdio.h> #include <string.h> float u32_to_f32(uint32_t x) {

interface Animal { ... } class Dog implements Animal { ... } class Cat implements Animal { ... } こういう 「生き物のように感情移入しやすい対象」を例として使うとプログラミング技法の本質を見誤るのではないか？ という話をします。 カプセル化 多くのクラスベースオブジェクト指向言語は、アクセス修飾子によってメンバーの公開範囲を制御できます。カプセル化というやつです。 さて、publicなメンバーが誰でも見られるのはいいとして、privateなメンバーの公開先はどうあるべきでしょうか？候補は次の2つとなるでしょう。 公開範囲は「自分だけ」つまりprivateメンバーを触れるのは this/self 経由のみとする。 同じクラスであれば他のインスタンスのprivateメンバーでも触れるものとする。 ク

モダンなプログラミング言語が多数登場した現代においても、C言語は重要な言語です。具体的に言うと、多くのプログラミング言語（あるいは言語ランタイム）がC言語で実装されていたり、OSのAPIはC言語のインターフェース（ABI）で提供されている場合が多かったり、異なるプログラミング言語間で関数呼び出しをしようとするとC言語のABIがベースとなったりします。 そんなC言語ですが、登場時から現代まで、少しずつですが進化を遂げています。その過程では、「この機能は良くなかった」ということが判明し、非推奨になったり削除された機能もあります。この記事では、C言語のそのような「良くなかった」機能を紹介します。 gets 関数 C言語には、誤って使うとバッファオーバーフローなどの問題を引き起こす関数が多数用意されています。例えば、

将来のIntel製CPUに搭載される命令セット拡張、AVX10.2の情報が先日出ました。 Intel® Advanced Vector Extensions 10.2 (Intel® AVX10.2) Architecture Specification この記事では、AVX10.2の新機能をざっくりと紹介します。 静的な丸め指定 浮動小数点演算において演算結果を浮動小数点形式で正確に表現できない場合は丸めが発生します。この丸めのやり方はIEEE 754でいくつか定義されており、x86系では4つが利用可能です。丸めのやり方は通常は浮動小数点演算器の制御レジスターで選択されますが、AVX-512では、命令の機械語で丸め方を指定できるようになりました。 （宣伝：丸め方を静的に指定する話は「Binary Hacks Rebooted」にも書いたので是非読んでください。） ただ、機械語のエンコード

シリーズ： CPUの機能を実行時に検出する：x86編（この記事） CPUの機能を実行時に検出する：Arm編 CPUの機能を実行時に検出する：実践編 その辺で売っているCPUは世代を経るにつれて性能が向上するだけではなく、使える命令が増えていきます。x86系であればSSEが実装され、AVXが実装され、AVX-512が実装され（そして削除され）、という感じです。Armもアーキテクチャーのマイナーバージョンが上がると命令が増えたりします。 新しく追加された命令をプログラムから利用したいとき、直接呼び出してしまうとそのプログラムは古いCPUでは動かなくなってしまいます。コンパイルオプションで切り替えるというのも一つの方法ですが、同じバイナリーを複数のCPUで動かし、最適な性能を得たいという場合に困ります。そこで、実行時にCPUの機能を検出して、プログラム内で分岐するという方法が考えられます。擬似コ

GHC 9.10.1が2024年5月11日にリリースされました。 GHC 9.10.1 is now available! - Announcements - Haskell Community この記事では、GHC 9.10の新機能を確認していきます。過去の類似の記事は GHC 9.2の新機能と、GHCの動向2021 GHC 8.10とGHC 9.0の新機能 GHC 9.4の新機能 GHC 9.6の新機能 GHC 9.8の新機能 です。 この記事は網羅的な紹介記事とはなっていません。是非、公式のリリースノート類も参照してください： 2.1. Version 9.10.1 — Glasgow Haskell Compiler 9.10.1 User's Guide docs/users_guide/9.10.1-notes.rst · ghc-9.10 · Glasgow Haskell

この記事はUTF-8のバリデーションとオートマトンの続きです。 前回はUTF-8のバリデーションが8状態のオートマトン (DFA) で表現できることを見ました。状態と遷移を擬似コードで書けば次のようになるでしょう： -- 8つの状態 data State = START | TAILx1 | TAILx2 | TAILx3 | A | B | C | D -- 入力バイトに応じて次の状態を返す。次の状態が該当しなかったら Nothing を返す next :: Word8 -> State -> Maybe State +----+----+-----+----+ | a0 | a1 | ... | aN | 8ビット整数列 +----+----+-----+----+ | | | v v v +----+----+-----+----+ | m0 | m1 | ... | mN | モノ

この記事では、JavaライクなインターフェースとHaskellライクな型クラスを比較します。どちらも、複数の異なる型を統一的に扱うための仕組みです。 インターフェース インターフェースはご存知の方も多いと思いますが、コード例を載せておきます。 // インターフェースの定義 interface Greetable { String greet(); } // 実装の例1 class Hello implements Greetable { String message; Hello(String m) { this.message = m; } public String greet() { return "Hello " + message + "!"; } } // 実装の例2 class Goodbye implements Greetable { public String gree

UTF-8は今日の文字エンコーディングの中で最も重要なものと言って差し支えないでしょう。UTF-8の仕様はこの辺で確認できます： Unicode 15.1.0 > 3.9 UTF-8 RFC 3629 - UTF-8, a transformation format of ISO 10646 この記事では、読者はすでにUTF-8にある程度の馴染みがあるものとして、UTF-8のバリデーションの細かいところを考えます。 UTF-8のバリデーションを行うには、以下のことを確かめなければなりません： 最初の1バイトが所定の範囲にあること：ASCII (0x00-0x7F) または0xC2以上。 後続のバイト（たち）が0x80-0xBFの範囲にあること。 長すぎないこと：U+007F以下の文字はちょうど1バイトで表現されていること、U+0080以上U+07FF以下の文字はちょうど2バイトで表現されて

JSONは最も普及したデータ形式の一つでしょう。JSONの仕様はECMA-404やRFC 8259として標準化されています。 ECMA-404 - Ecma International RFC 8259 - The JavaScript Object Notation (JSON) Data Interchange Format 細かいネタ 文字コード RFC 8259では、外部と交換するJSONテキストはUTF-8でエンコードされなければならないということになっています。BOMは禁止です。昔のRFCではUTF-16やUTF-32も許容されていました。 ただし、キーや文字列の中身としては単独のサロゲート（例："\uD800"）は禁止されていません。JSONのキーや文字列はUnicodeスカラー値の列とは限らないのです。 UTF-8を前提とする実装にとっては、単独のサロゲート（不正なUTF-

去る2023年は、WebAssemblyにGCを入れる仕様、WasmGCがChromeとFirefoxに実装された記念すべき年でした。WasmGCはコンパイラ作成者の長年の悲願であり（筆者の脳内調べ）、GCに依存する言語をWebAssembly上で動かすことを容易にします。2024年は、WasmGCがより広い環境で使えるようになることでしょう。まさにWasmGC元年と言っても過言ではありません（元年はなんぼあってもいいですからね）。 この記事は、2024年1月時点でのWasmGCの現状を、コンパイラ作成者の観点から調査したものです。筆者自身はWebAssemblyについては素人で、調べながら書いています。 概要と仕様 WasmGCの概要はChrome/V8界隈の人が書いた次の記事が参考になるでしょう： A new way to bring garbage collected program

この記事はx86-64機械語入門の続きです。SSE/AVX/AVX-512の紹介と、それに伴うVEXプリフィックス、EVEXプリフィックスの紹介を行います。 SSE x86-64で単精度・倍精度の浮動小数点数を扱うには、SSE (Streaming SIMD Extensions) と呼ばれる機能（命令セットとレジスター）を使います。元々は命令セット拡張でしたが、x86-64ではSSE2が常に利用可能なので、標準で使える機能だと思って構いません。 SSEでは128ビット幅のレジスターを16本（32ビットモードでは8本）利用できます。データ型は無印SSEでは単精度浮動小数点数（32ビット幅）が、SSE2以降では倍精度浮動小数点数（64ビット幅）や整数が使えます。 SSEの128ビット幅のレジスターはXMMレジスターと呼ばれ、xmm0, xmm1, ..., xmm15のように番号をつけて呼ば

この記事は Haskell Advent Calendar 2023 の7日目の記事です。 zip関数について Haskellには zip 関数というものがあります。この関数は、2つのリストを受け取って、それぞれから取り出した要素を組にしたリストを返します。

この記事は C言語 Advent Calendar 2023 の 2 日目の記事です。 C 標準には C99 で複素数型 _Complex が導入されました。実部が x, 虚部が y の複素数の値を構築するには、 x + y * I と書きます。 一方で、C99 の次の改定 C11 では複素数を構築する別の方法として CMPLX マクロが導入されました。この記事では、なぜ C99 の方法に問題があって CMPLX マクロが導入されたのかを説明します。また、コンパイラー間の違いによって起こる問題も説明します。 虚数単位 I は <complex.h> で定義されるマクロです。I は _Complex_I または _Imaginary_I に展開されます。気に食わないユーザーは #undef I することが特例で認められています。 _Complex_I は const float _Compl

Haskellは「入出力のためにIOモナドを使う必要があるので難しい」というイメージを持たれがちです[要出典]。この記事ではそのイメージに異を唱えることを目指します。すなわち、モナドを使わずに入出力を含むプログラミングをやってみます。 と言っても、Haskell標準の入出力関数には IO 型がついていることに変わりはありません。ですが、 unsafePerformIO という魔法の関数を使うと、IO 型を外して値を取り出すことができるのです。この記事ではこれを最大限活用します。 module System.IO.Unsafe where -- 魔法の関数 unsafePerformIO :: IO a -> a

この記事はx86-64の機械語を書けるようになるためのガイドとなることを目指します。読者はアセンブリー言語について既にある程度知っていることを想定します。 情報源 x86-64の機械語のオフィシャルなガイドはIntelのSoftware Developer ManualまたはAMDのAMD64 Architecture Programmer's Manualです。 Intel SDM: Intel® 64 and IA-32 Architectures Software Developer Manuals AMD64 Architecture Programmer's Manual, Volumes 1-5 このほか、Cから呼び出される関数を定義したり、Cの関数を呼び出すためには、呼び出し規約の知識も必要です。使用される呼び出し規約はOSに依存し、Unix系では主にSystem V ABI

Haskellプロジェクトの「良い習慣」と考えられるやつをまとめてみます。あくまで私の個人的な意見です。 プロジェクト固有のPrelude Prelude に相当するモジュールをプロジェクト独自に持っておくと便利ではないか、という話をします。代替Preludeの話ではありません。 プロジェクト固有のPreludeがあると便利な理由 理由の一つは、標準 Prelude の変化です。直近では次のような変化がありました： GHC 9.4: ~ 型演算子が追加（これまでは構文だった） GHC 9.6: liftA2 が追加 GHC 9.10（見込み）: foldl' が追加 もっと昔に遡ると、Semigroup((<>)) が増えるやつなどがありました。 この帰結として、 新しいGHCで名前の衝突が起きやすくなる 新しいGHCで「冗長なインポート」の警告が出やすくなる ことが言えます。これらの問題

GHC 9.6.1が2023年3月12日にリリースされました。 GHC 9.6.1 is now available - Announcements - Haskell Community この記事では、GHC 9.6の新機能を確認していきます。過去の類似の記事は GHC 9.2の新機能と、GHCの動向2021 GHC 8.10とGHC 9.0の新機能 GHC 9.4の新機能 です。 この記事は網羅的な紹介記事とはなっていません。是非公式のリリースノート類も参照してください： 2.1. Version 9.6.1 — Glasgow Haskell Compiler 9.6.1 User's Guide Changelog for base-4.18.0.0 | Hackage GHC 9.6.x Migration Guide GHC 9.6に入る機能 JavaScriptバックエンド

C言語の符号付き整数の足し算、引き算、掛け算は「2^nを法とするモジュラー演算である」と説明されることがありますが、これは間違いです。正しい説明は、「C言語の符号付き整数のオーバーフローは未定義動作である」となります。 この違いが観測できる例を2つ紹介します。 まず、単項マイナスについて。以下のプログラムを考えます： #include <limits.h> #include <stdbool.h> #include <stdio.h> bool f(int x) { return x == -x; } int main() { printf("%s\n", f(INT_MIN) ? "true" : "false"); } int 型の単項マイナスが2^nを法とするモジュラー計算で行われるのであれば、f が true を返す x は 0 と INT_MIN の2つのはずです。ですが、実際に

この記事は、新しくプログラミング言語を設計する際に数値型をどうするべきかについて、私の持論をまとめたものです。 数の体系 JavaScript（BigInt以前）やLua（〜5.2）などは唯一の数値型が浮動小数点数型で、整数も実数も同じ「number」型で表現します。ミニマルな言語を作るのならそういう設計もアリかもしれませんが、ネイティブコンパイルも視野に入る実用的な言語を作るなら整数と実数を一緒くたにする設計はやめた方が良いと思います。 特に、JavaScriptにコンパイルする言語を作るからと言って、数値型の設計まで真似る必要はありません。 整数を浮動小数点数で表現すると、思わぬ性能低下の要因になったりします。最近（2023年2月）、次のツイートが話題になりました： これは正のゼロと負のゼロが値として区別され、正のゼロは内部的に整数扱いされるのに対し負のゼロはそうではないことによるもの

整数除算の流儀 整数除算は割り切れなかった時の商の扱い方によって何種類かに分類でき、商を0に向かって切り捨てるものと、-\inftyに向かって切り下げる（床関数）ものの2種類がよく使われます。この記事ではこれらの関係を見ていきます。 ここではquot, rem, div, modを次のように定めます。ただし、\mathrm{trunc}(x)はxと同じ符号を持ち、絶対値が\lvert x\rvertを超えない最大の整数であるような整数です。 \begin{aligned} \mathrm{quot}(n,d)&:=\mathrm{trunc}(n/d), \\ \mathrm{rem}(n,d)&:=n-\mathrm{quot}(n,d)\cdot d, \\ \mathrm{div}(n,d)&:=\lfloor n/d\rfloor, \\ \mathrm{mod}(n,d)&:=n

浮動小数点形式 IEEE 754で規定された浮動小数点形式は、基数b, 指数部の最大値\mathit{emax}, 精度pの3つのパラメーターで表されます。このうち基数bは2または10で、この記事で扱うのはb=10の場合です。 指数部の最小値\mathit{emin}は1-\mathit{emax}と定められています。 浮動小数点数として表現できる実数は、0\le M<b^pを満たす整数M（仮数部）および\mathit{emin}-p+1\le e\le\mathit{emax}-p+1を満たす整数e（指数部）および0\le s\le 1を満たす整数s（符号）について (-1)^s\times M\times b^{e} と表現できるものです。 Mを範囲b^{p-1}\le M<b^pに収まるようにしたときに指数部が範囲に収まるものを正規化数と呼びます。 例えばb=10, p=3となる形式

実数を浮動小数点数に丸めるときに相対誤差がどのくらいになるかを考えます。実数を浮動小数点数に丸める関数をR\colon\mathbf{R}\rightarrow\mathbf{F}とした時に \left|\frac{R(x)-x}{x}\right| あるいは \left|\frac{R(x)-x}{R(x)}\right| を評価したいです。 ここでは浮動小数点数の基数はb、精度はp桁とし、指数部の範囲は無制限とします。 区間b^i\le \lvert x\rvert\le b^{i+1}での浮動小数点数の刻み幅はb^{i-p+1}となります。この刻み幅をulp (unit in last place) と呼びます。 丸め関数Rは次の性質を満たすべきです： 単調である：x\le yの時、R(x)\le R(y) 元の値との差は1ulp未満である：b^i\le \lvert x\rvert

こんにちは、浮動小数点数オタクのmod_poppoです。 昨日開催されたABC284のD問題でsqrtがどうのこうのという声がツイッターで観測されたので、ガチで考察してみます。 問題文（引用） まず最初に問題文を引用しておきます。 AtCoder Beginner Contest 284 | D - Happy New Year 2023 問題文 正整数Nが与えられます。Nは、2つの相異なる素数p, qを用いてN=p^2qと表せることがわかっています。 p, qを求めてください。 T個のテストケースが与えられるので、それぞれについて答えを求めてください。 制約 入力は全て整数 1\le T\le 10 1\le N\le 9\times 10^{18} Nは、2つの相異なる素数p, qを用いてN=p^2qと表せる 2023が7\times 17^2と素因数分解できることにちなんだ問題のよう

これは言語実装 Advent Calendar 2022の9日目の記事です。Luaをターゲットとする言語を実装する際に役立つかもしれない情報です。 後付けですがLua Advent Calendar 2022にも登録させていただきました。 私が作っているStandard ML処理系LunarMLでは限定継続を提供しています。限定継続についての話はブログの方に何回か書きました： LunarMLと継続 限定継続いろいろ これまでのLunarMLではJS-CPSバックエンドでCPS変換による限定継続の実装を行なっていましたが、最近Luaバックエンド（の亜種）でコルーチンによるワンショット限定継続の実装を追加しました。 この記事では、Luaのコルーチンを使った限定継続の実装の解説を試みます。 Luaのコルーチン コルーチンというのは途中で中断できる関数みたいなやつのことです（ざっくり）。 いろんな

この記事はHaskell Advent Calendar 2022の1日目の記事です。 この記事では、2022年12月時点のHaskellの環境構築手順を紹介します。2023年になっても通用するといいなあ。 対象とする環境 対象とする環境は以下の通りです： Unix系 macOS (Intel / Apple Silicon) Linux (x86_64 / aarch64) WSL2を含む（WSL1は不具合があった気がするので避けてください） Windows (x64) Arm系CPU搭載のコンピューターを使っている場合は、別途LLVMが必要になる場合があります。以下に当てはまる場合は、「補遺：LLVMバックエンドを使う」も読んでください： 64ビットArm（Apple Silicon Macや、Raspberry Pi OSの64ビット版など）で、GHC 9.0またはそれ以前のバージョ

Haskellで本格的に開発する際はcabalなりstackなりでプロジェクトを作るわけですが、ファイル一つで済むような（書き捨て）スクリプトをHaskellで書きたい場合があります。 依存関係のないスクリプトであれば、普通にファイルを作って runghc/runhaskell すれば良いでしょう。しかし、Haskellには標準ライブラリー（base）以外にも「準標準」と呼べる外部のライブラリーが多数あり（例：bytestring, text, vector）、それらに明示的に依存することは runghc ではできません。 そこで使えるのが、cabal scriptやstack scriptと呼ばれる機能です。 cabal script cabal run コマンドを使うと、ファイル中に {- cabal: 形式の特殊なコメントを含むHaskellコードをその場でビルドして実行することがで