2022-01-01

Rust で Nested Comment に対応したパーサーを書く

この記事は TSG Advent Calendar 2021 の 18 日目の記事です。 ~~この記事を執筆しているのは年末ですが (本当)、年内は Advent なので (大嘘) セーフです (大嘘)。~~ 寝ていたら新年になっていました。議論の余地なくアウトです。

三行で要約

Rust で
Nested Comment に対応した言語処理系を書くときには
plex と lalrpop を組み合わせると楽

はじめに

情報系のオタクが自作したいもの TOP3 といえば古来から相場が決まっており「CPU・OS・プログラミング言語」です。特にその中でも「プログラミング言語を作る」というのは自分のパソコン一台あればよく¹、また OS を作るのに比べて調べることが少ないという点でお手軽です²。

また最近は色々なプロダクトを Rust で作るのがブームになっています (要出典)。となるとやはり人は Rust で言語処理系を作りたくなるものでしょう。なるものとします。

さて、プログラミング言語を自作しようと思ったとき、ぜひとも導入したい言語機能があります。そう、Nested Comment です！³ (後述) ところがこの Nested Comment はかなり曲者の仕様であり, 巷によくあるモダンな感じのパーサーコンビネーターでは対応できません。検証はしていませんが、高機能な Document Comment を言語機能で組み込む場合なども同様の問題を抱えています。

というわけで、この記事では Rust で Nested Comment に対応した言語処理系を手軽に作る方法を書いていきます。

前提知識

本題に入る前に、そのために必要な前提知識を大まかに解説します。既に分かっている人は実装の章まで飛ばしてしまって大丈夫です

パーサーとレキサー

まず、プログラミング言語のコンパイラを作ろうと思ったとき、その基本的な流れは以下のようになります。(インタプリタでも 5 番以外はほぼ同様です)

レキサー (字句解析器) を作る
パーサー (構文解析器) を作る
型推論を行う (型付き言語のみ)
抽象構文木を適当に変換して最適化する
最適化した抽象構文木をアセンブリ (または LLVM-IL 等の中間表現) として出力する

ここでレキサーとは文字列で与えられたソースコードをトークン列に変換するプログラムのことで, パーサーはそのトークン列を, プログラムとして意味が通るような構文木に変換するプログラムのことでした。

ここで「なぜレキサーとパーサーを分けるのか」という問が生じます。文字列から構文木を作れれば良いのですから, わざわざ間にトークン列を経由することなく、直接変換してしまえば良いのではないかということです。

なるほど確かにその通りなのですが、この考えには一つ重大な欠点があります。それは「言語の文法が複雑になりすぎる」ということです。

形式言語の理論では、言語の文法がある種の単純さを持っていると構文解析が少ない計算量 (例えば文字列長の線形オーダーや二乗のオーダー) で抑えられることが知られています。また一般に単純な文法はコードで記述するときにも単純になり、処理系のバグが減って保守性も向上することが期待されます。

直感的に理解したければ、自然言語の例を考えても良いでしょう。例えば I have a pen という文字列を英語として解釈するとき、普通はこの文字列を [I, have, a, pen] という4つの単語に分割してから、英語の文法に則って文章の意味を判断するでしょう。もし英文法が「"I" の後に " " があって、その後に "h" が来たら……」のように一文字単位で記述されていたら、その英文法書はとんでもない厚みになる上に柔軟性の無いものになってしまう⁴ はずです。⁵

そんな事情で一般的な言語処理系では、文字列をトークン (単語) の列に分解するレキサーと、トークン列を構文木に変換するパーサー。という役割分担を行うことで言語処理系の実装の単純さと構文解析の高速さを確保しています。

レキサー/パーサージェネレーターについて

とはいえ、言語処理系を作るたびにレキサーやパーサーを一から手書きするのは面倒です。そのため世の中には、レキサーやパーサーの作成を支援するツールが数多く存在します。そしてそれらを総称して「レキサージェネレーター」や「パーサージェネレーター」と呼んでいるわけです。ツールによってはレキサーとパーサーでジェネレーターが別れておらず、一つの文法を記述すると勝手にレキサーとバーサーを両方とも生成してくれる場合もあります⁶。

そして重要なこととして、多くのパーサージェネレーターは扱う文法が LR(1) 文法であるという比較的緩い仮定をおいている一方で、レキサージェネレーターは効率の良いレキサーを生成するためにレキサーが 正規言語 を処理するという比較的強い仮定をおいているという事実があります。

Nested Comment とは

話は変わって、OCaml などの一部のプログラミング言語には Nested Comment という言語機能が存在します。これは以下のようなコメント文の記述を可能とする言語機能です。

(* This (* is a *) comment *)
print_string "hello, world!"

当たり前のコードに見えるかもしれませんが、例えば C++ で以下のようなコードを書くとエラーになります。

/* This /* is a */ comment */
std::cout << "hello, world!" << std::endl;

おわかりでしょうか。C++ だと 1 つ目の /* と 1 つ目の */ がコメントとして対応してしまい、上のコードで言う comment */ の部分が通常のコードとして扱われてしまうのです。それに対して OCaml のコードではネストした (* と *) の対応がとられ、しっかり comment *) の部分までがコメントとして扱われます。

Nested Comment の問題点

さて上記の Nested Comment は便利な仕様ですが、多くの言語に導入されない大きな理由が一つあります。それは「コメントがネストすると正規言語で表現できなくなる」という問題です。

通常の言語では、コメントというのはレキサーの段階で処理され、空文字列と同様の扱いになります。そして前述の通り一般的なレキサージェネレーターはレキサーが正規言語しか扱わないという仮定をおいています。

ところが、ネストした括弧列は正規言語では表現できないことが知られています。正規言語とはいわゆる「正規表現」で表される言語のことですが、形式言語理論における正規表現では「ネストした括弧」を表現できないことが示されています (後述に注)。

このため、そのへんの適当なレキサー/パーサージェネレーターを用いると、Nested Comment に対応することはできません。Nested Comment に対応するためには、もう少し「柔軟な」(または「美しくない」) レキサー/パーサージェネレーターを用いる必要があります。

(注) 紛らわしい点として、Perl や .NET 系などのプログラミング言語では、利便性のために「正規表現」として形式言語理論で言うところの「正規表現」よりも表現力の高い表現を処理できる実装がなされていて、ネストする括弧の対応も処理することができます⁷。Rust で標準的な regex クレートでもいくつかの便利な記法が追加されていますが、こちらは括弧列の対応などの強い表現はできません。

Rust のパーサージェネレーター事情

以上のことを踏まえ、ある程度名の知られている Rust のレキサー/パーサージェネレーターをいくつか独断と偏見で比較してみます。ソースコード上のロケーション情報を取得できるか否かを Span としています

名前	種類	`Span`	レキサーのカスタム	開発の活発さ	備考
nom	一体型	o	x	◎	おそらく最も有名
pom	一体型	x	x	o
combine	一体型	o	x	◎
pest	一体型	o	x	◎	PEG 形式。リッチなエラー報告付き
plex	両対応	o	◎	x	かなり素朴
lalrpop	一体型(*)	o	o	o	文法は独自形式のスクリプトで定義
peg	一体型	o	x	◎	PEG 形式。
logos	レキサーのみ	o	◎	o	珍しいレキサー特化型

ここで「一体型」とは、レキサーとパーサーのジェネレーターが分離していないことを指しています。ただし lalrpop は、デフォルトでは一体型であるものの、パーサージェネレーターのみを用いる (レキサーは自前で用意する) ことができるようになっています。

plex と LALRPOP

上の表を見ると、まずレキサーをカスタムできる選択肢が極端に少ないことに気が付きます⁸。多くのツール (crate) はレキサー/パーサージェネレーターの一体型であり、レキサーを Nested Comment に対応させることが難しいのです。したがってパーサージェネレーターは plex か lalrpop のものを使用せざるを得ません。

それではレキサーとパーサー両方のジェネレーターを両方備えている plex を使用すれば良いではないかと思うのですが、大きな問題として、plex のパーサージェネレーターは機能がかなり少ない上に、そもそもリポジトリが長らく更新されていません⁹。新しい機能が追加されることを期待するのは望み薄ですし、もしバグがあったとしても修正は遅れるでしょう。パーサージェネレーターとして plex を中心的に使いたくはありません。

結果としてパーサージェネレーターとして使えるのは lalrpop のみとなります。こちらは利用者も多く、開発も一応継続的に行われています。ドキュメントはほぼ更新されていませんが、issue を眺めると新機能の追加にもかなり積極的な様子が伺えます。

これで問題は「レキサージェネレーターに何を用いるか」です。といっても候補は plex と logos しかありません。logos はプロシージャルマクロを利用してレキサーを生成できるかなり良い感じの crate ではあるのですが、いかんせんドキュメントがほぼ Docs.rs しかありません。また issue を覗くと regex のマッチあたりで致命的なバグが放置されている様子があります。今回はレキサーには Nested Comment を追加する以外にはそこまで大規模な改造はしないため、不安定であるならば logos ほどモダンなクレートは不要でしょう。

したがって、ある程度枯れている¹⁰レキサージェネレーターとして plex を利用するのが良さそうです。

実装

さて、前置きと前提知識が長くなりました。やりたいことはレキサージェネレーターとして plex、パーサージェネレーターとして lalrpop を利用してNested Comment に対応した言語処理系を作ることです。そのデモとしてこれ以降では簡単なプログラミング言語を定義し、その言語を抽象構文木に変換するところまでを実装します。

なお実装した内容は、以下のリポジトリで公開しています。

github.com

作っていく言語

以下のような、変数名への結果の保存と呼び出しが可能な算術言語を作ってみましょう。ただし (* と *) で囲まれた箇所がコメントで、これが Nested Comment に対応しています。

(* x = 3 *)
let x = 1 + 2;
let y = x * 4;
let z = x + y * x; (* 39 *)
print (x + y + z); (* 54 *)
let w = z / 3 + y;
(* 計算の (* 結果は *) 0 になる *)
let ans = x * (y - w) + y;
print ans;

前準備

まず cargo new で新しいクレート nested-comment-demo を作り、rust のツールチェインを nightly ビルドに変更します。これは plex のビルドに nightly 限定の機能が必要だからです。

$ cargo new --bin nested-comment-demo
$ cd nested-comment-demo
$ rustup install nightly
$ rustup override add nightly

次に Cargo.toml の dependencies 以降を次のようにします。

[dependencies]
plex = "0.2.5"
lalrpop-util = "0.19.6"
regex = "1"
thiserror = "1.0"
anyhow = "1.0"

[build-dependencies]
lalrpop = "0.19.6"

ここでは plex と lalrpop に加えて、エラー出力のために anyhow や thiserror を追加しています。

Nested Comment に対応したレキサーを作る

まずは plex を用いてコメントに対応していないレキサーを作り、それに Nested Comment のサポートを追加します。

src/ 以下に types.rs というファイルを作り、その中身を以下のようにします。

// ソースコード中の位置情報を範囲で表す
pub type Span = (usize, usize);

#[derive(Debug, Clone, PartialEq)]
pub struct Spanned<T> {
    pub item: T,
    pub span: Span
}

impl<T> Spanned<T> {
    pub fn new(item: T, span: Span) -> Self {
        Self {
            item,
            span
        }
    }
}

// レキサーで用いるトークン
#[derive(Debug, Clone, PartialEq)]
pub enum Tok<'a> {
    Num(i64),
    Ident(&'a str),
    Plus,
    Minus,
    Star,
    Slash,
    LPar,
    RPar,
    Let,
    Equal,
    SemiColon,
    Print,
}

次に lexer.rs を作り、その中身に plex を用いてレキサーを定義していきます。ここではいくつかの正規表現のうち与えられた文字列から合致するものを最長一致でマッチする関数である next_token を、plex を用いて定義しています。逆に言うとそれ以外の部分は手書きなので、空白文字の読み飛ばしなども自分で書いていく必要があります。

今回はパーサーとして lalrpop を用いるので、レキサーは iterator を実装する型にした上で、その出力を

std::result::Result<(Loc, Tok, Loc), Error>;

という形式にする必要があります。ここで Loc はソースコード上の位置情報を表す型を、Tok と Error はそれぞれトークン型とユーザー定義のエラー型をそれぞれユーザーが任意に指定します。今回は

 std::result::Result<(usize, Tok<'a>, usize), Spanned<Error>>;

という形式になります。これを lexer::Result 型としてしまいましょう。

plex でのレキサーの書き方自体は単純なので、本家のリポジトリの examples を見ればなんとなく察せると思います。

use plex::lexer;
use thiserror::Error;

use crate::types::{ Spanned, Tok };

#[derive(Debug, Clone, PartialEq, Error)]
pub enum Error {
    #[error("unrecognized token `{0}`")]
    UnrecognizedToken(String),
    #[error("integer constant `{0}` is too large")]
    TooLargeInteger(String)
}

enum LexState<'a> {
    Token(Tok<'a>),
    Skip,
    Err(Error)
}

lexer! {
    fn next_token(text: 'input) -> LexState<'input>;

    r"[\t\n\r ]" => LexState::Skip,
    r"\+" => LexState::Token(Tok::Plus),
    r"\-" => LexState::Token(Tok::Minus),
    r"\*" => LexState::Token(Tok::Star),
    r"/" => LexState::Token(Tok::Slash),
    r"\(" => LexState::Token(Tok::LPar),
    r"\)" => LexState::Token(Tok::RPar),
    r"let" => LexState::Token(Tok::Let),
    r"=" => LexState::Token(Tok::Equal),
    r";" => LexState::Token(Tok::SemiColon),
    r"print" => LexState::Token(Tok::Print),
    r"[a-z][0-9A-Za-z_]*" => LexState::Token(Tok::Ident(text)),
    r"[0-9]+" => {
        if let Ok(i) = text.parse() {
            LexState::Token(Tok::Num(i))
        } else {
            LexState::Err(Error::TooLargeInteger(text.to_string()))
        }
    },
    r"." => LexState::Err(Error::UnrecognizedToken(text.to_owned()))
}

#[derive(Debug, Clone)]
pub struct Lexer<'input> {
    original: &'input str,
    remaining: &'input str
}

impl<'input> Lexer<'input> {
    pub fn new(s: &'input str) -> Self {
        Lexer {
            original: s,
            remaining: s,
        }
    }
}

// lalrpop が受理する形式に合わせる
type Result<'a> = std::result::Result<(usize, Tok<'a>, usize), Spanned<Error>>;

impl<'input> Iterator for Lexer<'input> {
    type Item = Result<'input>;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let state = next_token(self.remaining);
            if state.is_none() {
                // EOF
                return None;
            }

            let (state, remaining) = state.unwrap();

            // 読んだ箇所を更新
            let lo = self.original.len() - self.remaining.len();
            let hi = self.original.len() - remaining.len();
            self.remaining = remaining;

            match state {
                LexState::Token(tok) => {
                    // 正しいトークンなら lalrpop が受理する形に変換
                    return Some(Ok((lo, tok, hi)));
                },
                LexState::Skip => continue, // 空白は読み飛ばす
                LexState::Err(e) => {
                    // エラーであればそれを返す
                    return Some(Err(Spanned::new(e, (lo, hi))));
                },
            }
        }
    }
}

それではこれに Nested Comment を対応させていきましょう。大まかな方針は「コメントが始まったらコメント中専用のレキサーの状態遷移を用いるようにする」です。まずは lexer.rs に以下のコードを追加します。

enum CommentState {
    ReOpen,
    Close,
    Continue
}

lexer! {
    fn comment_consume(_text: 'input) -> CommentState;
    
    r"\(\*" => CommentState::ReOpen,
    r"\*\)" => CommentState::Close,
    r"." => CommentState::Continue
}

そして LexState と lexer::Error の定義をそれぞれ以下のように変更します

#[derive(Debug, Clone, PartialEq, Error)]
pub enum Error {
    #[error("unclosed comment")]
    UnclosedComment, // 追加
    #[error("unrecognized token `{0}`")]
    UnrecognizedToken(String),
    #[error("integer constant `{0}` is too large")]
    TooLargeInteger(String)
}

// ...
// (中略)
// ...

enum LexState<'a> {
    Token(Tok<'a>),
    Skip,
    CommentBegin, // 追加
    Err(Error)
}

あとはこれに対応するため Lexer のメソッドを以下のように変更するだけです。

impl<'input> Lexer<'input> {
    pub fn new(s: &'input str) -> Self {
        Lexer {
            original: s,
            remaining: s,
        }
    }

    // コメント中で用いるレキサーの状態遷移
    // コメントの括弧が正しく対応しているかを返す
    fn skip_comment(&mut self) -> bool {
        loop {
            use CommentState::*;
            let state = comment_consume(self.remaining);
            if state.is_none() {
                // EOF
                return false;
            }
            
            let (state, remaining) = state.unwrap();

            self.remaining = remaining;                
            match state {
                ReOpen => {
                    if self.skip_comment() {
                        continue;
                    }
                    return false;
                },
                Close => {
                    return true;
                },
                Continue => continue
            }
        }
    }
}


impl<'input> Iterator for Lexer<'input> {
    type Item = Result<'input>;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let state = next_token(self.remaining);
            if state.is_none() {
                // EOF
                return None;
            }

            let (state, remaining) = state.unwrap();

            // 読んだ箇所を更新
            let lo = self.original.len() - self.remaining.len();
            let hi = self.original.len() - remaining.len();
            self.remaining = remaining;

            match state {
                LexState::Token(tok) => {
                    // 正しいトークンなら lalrpop が受理する形に変換
                    return Some(Ok((lo, tok, hi)));
                },
                LexState::Skip => continue, // 空白は読み飛ばす
                LexState::Err(e) => {
                    // エラーであればそれを返す
                    return Some(Err(Spanned::new(e, (lo, hi))));
                },
                LexState::CommentBegin => { // 追加
                    if self.skip_comment() {
                        continue;
                    }
                    // コメントが閉じていない
                    return Some(Err(Spanned::new(Error::UnclosedComment, (lo, hi))));
                }
            }
        }
    }
}

これで無事 Nested Comment に対応したレキサーができました。

LALRPOP でパーサーを作る

レキサーができたので、あとはパーサーを作っていくだけです。基本は lalrpop のドキュメント通りなのですが、少しだけドキュメントにない便利な機能を使います。個々の細かい機能の解説はしませんので、lalrpop を知らないという方は雰囲気で察してください。

まず先ほど作った types.rs に抽象構文木を表す以下の型を追加します。

// 二項演算の種類
#[derive(Debug, Clone, PartialEq)]
pub enum BinOpKind {
    Add,
    Sub,
    Mul,
    Div,
}

// 式

#[derive(Debug, Clone, PartialEq)]
pub enum ExprKind<'a> {
    Num(i64),
    Var(&'a str),
    BinOp(BinOpKind, Box<Expr<'a>>, Box<Expr<'a>>),
}

pub type Expr<'a> = Spanned<ExprKind<'a>>;

// 文

#[derive(Debug, Clone, PartialEq)]
pub enum StmtKind<'a> {
    Let(&'a str, Box<Expr<'a>>),
    Print(Box<Expr<'a>>),
}

pub type Stmt<'a> = Spanned<StmtKind<'a>>;

あとは lalrpop を利用して文法を記述していきましょう。ただその前に、クレートのルート (src/ 以下ではない) に build.rs というファイルを作り、以下のコードを記述します。これは lalrpop が文法ファイルをコンパイルするためのものです。

extern crate lalrpop;

fn main() {
    lalrpop::process_root().unwrap();
}

次に src/ 以下に grammer.lalrpop を作り、以下のように文法を記述していきます。

このとき lalrpop のデフォルトのレキサーではなく自前のレキサーを用いるため、チュートリアルのこことここを参考に extern 節を書く必要があります。

また lalrpop のドキュメントにない機能なのですが、パーサー中では precedence と assoc という属性を用いて、ルールの優先順位と演算子の結合法則を指定することができます¹¹。

use crate::types::*;
use crate::lexer::Error as LexError;

grammar<'input>;
extern {
    type Location = usize;
    type Error = Spanned<LexError>;

    // lalrpop の構文定義中で使う「文字列⇒トークン」の置換表
    enum Tok<'input> {
        "(" => Tok::LPar,
        ")" => Tok::RPar,
        Num => Tok::Num(<i64>),
        Ident => Tok::Ident(<&'input str>),
        "-" => Tok::Minus,
        "+" => Tok::Plus,
        "*" => Tok::Star,
        "/" => Tok::Slash,
        "let" => Tok::Let,
        "=" => Tok::Equal,
        ";" => Tok::SemiColon,
        "print" => Tok::Print,
    }
}

TermOp: BinOpKind = {
    "+" => BinOpKind::Add,
    "-" => BinOpKind::Sub,
};

FactorOp: BinOpKind = {
    "*" => BinOpKind::Mul,
    "/" => BinOpKind::Div
};

Atom: Box<Expr<'input>> = {
    "(" <e:Term> ")" => e,
    <l:@L> <x:Num> <r:@R> => Box::new(Spanned::new(ExprKind::Num(x), (l, r))),
    <l:@L> <x:Ident> <r:@R> => Box::new(Spanned::new(ExprKind::Var(x), (l, r))),
}

Term: Box<Expr<'input>> = {
    #[precedence(level="0")]
    Atom,

    // * /
    #[precedence(level="1")]
    #[assoc(side="left")]
    <l:@L> <e1:Term> <op:FactorOp> <e2:Term> <r:@R> => Box::new(Spanned::new(ExprKind::BinOp(op, e1, e2), (l, r))),

    // + -
    #[precedence(level="2")]
    #[assoc(side="left")]
    <l:@L> <e1:Term> <op:TermOp> <e2:Term> <r:@R> => Box::new(Spanned::new(ExprKind::BinOp(op, e1, e2), (l, r))),
}

Statement: Stmt<'input> = {
    <l:@L> "let" <x: Ident> "=" <t:Term> ";" <r:@R> => Spanned::new(StmtKind::Let(x, t), (l, r)),
    <l:@L> "print" <t:Atom> ";" <r:@R> => Spanned::new(StmtKind::Print(t), (l, r)),
}

pub Program: Vec<Stmt<'input>> = {
    Statement => vec![<>],
    <mut p:Program> <s:Statement> => {
        p.push(s);
        p
    }
}

パーサーを呼び出す

これでレキサーとパーサーが定義できたので、あとはこの文法通りに与えられた文字列をパースするプログラムを追加するだけです。まずは src/ 以下に parser.rs を追加し、以下のプログラムを記述します。

use thiserror::Error;
use crate::types::{Stmt, Tok, Spanned};
use crate::lexer;

lalrpop_mod!(pub grammer);

type LalrpopError<'a> = lalrpop_util::ParseError<usize, Tok<'a>, Spanned<lexer::Error>>;

#[derive(Debug, Clone, PartialEq, Error)]
pub enum ErrorKind<'a> {
    #[error("parse error: unexpected end of file")]
    Eof,
    #[error("lexer error: {0}")]
    Lexical(lexer::Error),
    #[error("parse error: found extra token `{0:?}`")]
    ExtraToken(Tok<'a>),
    #[error("parse error: unrecognized token `{0:?}`, expected `{1}`")]
    UnrecognizedToken(Tok<'a>, String)
}

pub type Error<'a> = Spanned<ErrorKind<'a>>;

// lalrpop のエラーを自前のエラー型に変換
fn convert_error(err: LalrpopError) -> Error {
    match err {
        LalrpopError::InvalidToken { location } => Spanned::new(ErrorKind::Eof, (location, location)),
        LalrpopError::ExtraToken { token: (lo, tok, hi) } => Spanned::new(ErrorKind::ExtraToken(tok), (lo, hi)),
        LalrpopError::User { error } => Spanned::new(ErrorKind::Lexical(error.item), error.span),
        LalrpopError::UnrecognizedToken {
            token: (lo, tok, hi),
            expected
        } => {
            assert!(!expected.is_empty());
            // 最初の候補だけ見る
            let expected = expected[0].clone();

            Spanned::new(ErrorKind::UnrecognizedToken(tok, expected), (lo, hi))
        },
        LalrpopError::UnrecognizedEOF { location, .. } => Spanned::new(ErrorKind::Eof, (location, location)),
    }
}

pub fn parse<'input>(src: &'input str) -> Result<Vec<Stmt>, Error> {
    let lex = lexer::Lexer::new(src);
    let parser = grammer::ProgramParser::new();

    parser.parse(lex).map_err(convert_error)
}

lalrpop のエラーを隠蔽して自作のエラー型に変換していますが、本体はレキサーとパーサーを構築して呼び出すだけの parse 関数です。あとは main.rs を以下のように変更して、この parse 関数を呼び出すようにすれば終わりです。

mod types;
mod lexer;
mod parser;

use anyhow::{ Result, Context };

#[macro_use]
extern crate lalrpop_util;

fn load_file(path: &str) -> Result<String> {
    std::fs::read_to_string(path).context(format!("failed to open file: {}", path))
}

fn main() -> Result<()> {
    let path = "test.txt"; // ソースファイルへのパス
    let src = load_file(path)?;
    let ast = parser::parse(&src).map_err(|err| {
        anyhow::format_err!("[{}:{}:{}] {}", path, err.span.0, err.span.1, err.item)
    })?;
    println!("{:#?}", ast);
    Ok(())
}

最終的なクレートの構成は以下のようになります

nested-comment-demo/
├ src/
│ ├ main.rs
│ ├ types.rs
│ ├ lexer.rs
│ ├ parser.rs
│ └ grammer.lalrpop
├ build.rs
└ Cargo.toml

あとはクレートのルートに test.txt を以下の内容で作成し、cargo run すれば求める出力が得られていることが確認できるはずです (長いため省略)。

(* x = 3 *)
let x = 1 + 2;
let y = x * 4;
let z = x + y * x; (* 39 *)
print (x + y + z); (* 54 *)
let w = z / 3 + y;
(* 計算の (* 結果は *) 0 になる *)
let ans = x * (y - w) + y;
print ans;

なおこの記事のプログラムではレキサーとパーサーのみを実装し、インタプリタは実装していません。簡単に実装できると思いますので、興味がある人は実装してみてください (丸投げ)。

まとめ

以上のように、Nested Comment というそのへんのモダンなクレートでは扱いにくい仕様が入っていても、plex と lalrpop を利用すればそれなりに手軽にレキサーやパーサーを作れることができました¹²。

また、今回対応したのは Nested Comment という比較的マイナーな仕様でしたが、今回用いた手段と同様の策を用いることで、レキサーの改造が必要そうな諸々の仕様 (例: Document Comment) を自作言語に組み込みやすくなると思われます。

皆さんがレキサーやパーサーのような非本質的な部分¹³で躓くことなく、楽しく自作言語の処理系を作る一助になれば幸いです。

なおこの記事は、理情の CPU 実験において、min-caml という Nested Comment が入った言語のパーサーを作るために四苦八苦した僕の備忘録でもあります。

……2022年の目標は、アドカレで遅刻しないことです。

謎の基盤や FPGA を買わないで良いということ↩
つまり、みんなやろうということです↩
この記事は飛ばし記事であり、Nested Comment は実用上かなりマイナーな言語機能です。またおそらく採用する優先度が高い言語機能でもありません↩
例えば新しい単語が登場するたびに「文法」を書き換えなければなりません↩
言語によっては、レキサーとパーサーを分離できないことが知られています。例えば分かち書きをしない日本語では「ももももも。すももももも。」という文が「もも/も/もも。すもも/も/もも」なのか「もも/もも/も。す/もも/もも/も」なのか、構文解析なしに判断することは困難です↩
本記事ではこのような統合されたジェネレーターも「パーサージェネレーター」と呼称します↩
このために、形式言語理論で言う正規表現を regular expression、プログラミング言語が提供する「正規表現」を regex と言い分ける場合もあるようです↩
このような事情からかは分かりませんが、Rust で書かれた言語処理系はレキサーやパーサーを一から手書きしているものが結構あるようです↩
記事執筆時点で最終コミットが 14 ヶ月前↩
ここでは「モダンではないがある程度安定している」という意味↩
この issue を参照↩
もっと楽な方法があるよ！という方がいましたら、気になるのでぜひ教えて下さい↩
言語の文法をどうするかは非常に重要ですが、そのレキサーやパーサーの実装は基本的には作業です↩

2020-12-19

色々な集合論の公理系

この記事は TSG Advent Calendar 2020 の 19 日目の記事です。

昨日はイワシイラさんのヤフオクでサーバーを買うときの話でした。

序文

「集合論は現代の数学の基礎である」というのは大学数学に足を踏み入れた人の多くが一度は聞かされるセリフだと思います。一方でここで言われるような「集合論」は多くの場合暗黙に ZFC 公理系 (あるいは選択公理を抜いた ZF 公理系) を指していることが多いように見受けられます^[要出典]。

この ZFC は素朴集合論で発生することの多いカントールのパラドックスなどを回避するために慎重に作られていますが、その代償として(？)「全ての集合からなる集まり」や「全ての順序数からなる集まり」のような非常に大きい集まりを扱えない事が知られています。

その結果、例えば圏論において圏全体からなる圏のような非常に大きい対象を扱いたいと思った場合、その基礎を ZFC に置くことができず、「集まり」を扱う ZFC 以外の集合論の公理系が必要になることがあります。

この記事ではそんな日陰物の^[要出典] ZFC 以外の集合論の公理系について、僕が調べた事を書いていこうと思います。

備忘録のつもりで曖昧な理解で書いている箇所があり、間違いなどが多く含まれている可能性が高いです。明らかな誤りを見つけた際にはぜひ @azaika_ に教えて下さい。指摘内容が理解できた場合土下座して直します。理解できなかった場合は未熟を恥じて該当箇所を爆破します。

[追記 2020/12/19]

Twitter 上でめいぜんおーえす (@Meizen_OS) さんから誤りのご指摘とアドバイスをいただきましたので記述を一部書き換えました。

[追記 2020/12/21]

再び Twitter 上で Alwe (@Alwe_Logic) さんからいくつかのご指摘をいただきましたので記述を一部書き換えました。

ZF/ZFC

はじめに ZFC (Zermelo-Fraenkel [ツェルメロ=フレンケル] with the axiom of Choice) 公理系について復習しましょう。まず ZF 公理系とは以下の 8 つの公理からなる公理系です。

外延性公理 (等しさの定義) : $\forall A \forall B (\forall x (x \in A \Leftrightarrow x \in B) \Rightarrow A = B)$
空集合公理 :
- このような $E$ を空集合と呼び、通常 $\emptyset$ と書く
無限公理 (無限集合の存在) :
- これは自然数の存在を認めるもので、またこれにより自然数が最小の無限集合となっている
対の公理 ( $\{x, y\}$ の存在 ) : $\forall x \forall y \exists A \forall z (z \in A \Leftrightarrow z = x \vee z = y)$
和集合公理 ( $\bigcup X$ の存在 ) : $\forall X \exists A \forall a (a \in A \Leftrightarrow \exists x(x \in X \wedge a \in x))$
冪集合公理 ( $\mathcal{P} (X)$ の存在 ) : $\forall X \exists A \forall a(a \in A \Leftrightarrow a \subseteq X)$
置換公理 ( map() の存在 ) :
- $F$ は「集合から集合の特殊な関係」という意味での関数ではなくて、いわゆるクラス関数でも良いことに注意
- これは特にフランクな表現である。正しい表現は下に記述する記事など他の文献を当たって欲しい
正則性公理 :
- わかりにくいが、ここから無限降下列 $x_0 \ni x_1 \ni x_2 \ni \cdots$ が存在しない事が言える

簡略化のため、 $\notin,\subseteq,\cap$ などの一部の記号を定義なしに使用しており、また自由変数の扱いについてはあまり記事の本筋に関係ないと考えたため記述を省いています。あくまでお気持ちの一部を書いているものだと思ってください。正確な公理の記述に関してはめいぜんおーえすさんの記事などが参考になると思います。

ZFC 公理系とはこれに更に以下の公理を追加した公理系になっています。

選択公理 :
- これも特にフランクな表現である。正しい表現は上記記事など他の文献を当たって欲しい

ZF や ZFC においては (論理式以外の) 全ては集合です。現代数学の多くはこの公理系の上に成り立っており, 自然数や実数, 関数も特別な形をした集合として定義されます。

また重要なこととして、上のような公理で巧妙な制約がかけられていることにより ZF(C) では「集合全ての集まり」や「自身を含まない集合(？)の集まり」は構成できません。つまりそのような「集まり」は集合ではなく、ZF(C) の上で扱うことは出来ません。

以下ではこれをベースに色々弄り回したバリエーションを考えていきます。

Zermelo set theory

さて、この ZF(C) ですが、最初に Zermelo が提唱したときには少し違う形のものでした。この Zermelo が最初に提案した集合論 (を書き直したもの) は Zermelo set theory と呼ばれており, Z または Z^- と書かれます。

Z と ZF の本質的な違いは、置換公理の代わりに以下の分出公理を用いるという点です。

分出公理 ( filter( $\psi,X$ ) の存在 ) : $\forall X\exists A\forall x(x \in A\Leftrightarrow(x \in X \wedge \psi(x)))$

ここで「置換公理 + ZF のその他の公理」から分出公理を導出することは可能ですが、「分出公理 + ZF のその他の公理」から置換公理を導出することは出来ません (まあ filter より map のほうが強いよね) 。例えば順序数 $\omega\times 2$ は Z から導出できないことが ZF において示せます。

したがって、Z (もしくは Z + 選択公理) は ZF(C) より制約が厳しい、つまり扱える対象の少ない (記述能力が低い) 集合論になっています。

MacLane set theory

大きな集まりの話を導入に使っていてなんですが、まだ大きな集まりを扱わない公理系の話です。

Mac Lane set theory は圏論の祖として知られる Mac Lane が提案した公理系で、ほとんど Zermelo set theory と同じですが以下の点で違いがあります。

分出公理において、内の限量子は集合にしかわたってはならない
- $\Delta_0$ 論理式でなければならない。とも言いかえられる。

つまり分出公理中の $\psi(x)$ として $\psi(x) := \forall a(\varphi(a, x))$ のような「範囲が広い」量化子は使えません。

この制約を加えた MacLane set theory は Z より真に弱い事が知られており *1、Z や ZF においては全ての集合のあつまりは集合にならない事が知られているので、分出公理を使うときに全ての集合をわたるような量化子は使えないということになります。

ここまでは ZF(C) を制約を厳しくする方向に変えていく拡張を考えました。次からは ZF(C) を拡張して、集合より大きい集まりを考えられるようにした公理系について考えましょう。

Morse-Kelley set theory

MK, Kelly-Morse, KM などとも呼ばれます。ここでは MK と呼ぶことにしましょう。

ZF(C) では全ては集合でした。MK では全てはクラスと呼ばれる「集合より大きいかもしれない」ものとして、そのクラスを集合と集合ではない真の (proper な) クラスの2つに大別します。MK において、あるクラス $A$ が集合であるという述語 $\mathrm{set}(A)$ は以下のように定義されます。

集合の定義 : $\forall A(\mathrm{set}(A) \Leftrightarrow \exists X(A \in X))$

つまり、他のクラスの要素になっているようなものが集合で、そうでないものが真のクラスです。

MK の他の公理は ZFC とよく似ています。というかほぼ同じです。ただし、いくつかの公理に「集合に対して」という制約が付いていること、後述する内包性公理が入っているために対の公理と選択公理が不要になっている事に注意が必要です。

外延性公理 (等しさの定義) : $\forall A \forall B (\forall x (x \in A \Leftrightarrow x \in B) \Rightarrow A = B)$
和集合公理 ( $\bigcup X$ の存在 ) : $\forall X(\mathrm{set}(X) \Rightarrow \exists A \forall a (a \in A \Leftrightarrow \exists x(x \in X \wedge a \in x)))$
冪集合公理 ( $\mathcal{P} (X)$ の存在 ) : $\forall X(\mathrm{set}(X) \Rightarrow \exists A \forall a(a \in A \Leftrightarrow a \subseteq X))$
無限公理 (無限集合の存在) : $\exists A(\mathrm{set}(A) \wedge \emptyset \in A \wedge \forall a(a \in A \Rightarrow a \cup \{a\} \in A))$
正則性公理 : $\forall X(X\neq\emptyset \Rightarrow \exists x(x \in X \wedge x \cap X = \emptyset ))$

さて、クラスという新しい概念は導入されたものの、これだけだと MK が ZFC より嬉しい要素は特に見当たりません。MK の真価は、以下の内包性公理という「クラスの定義の幅広さ」にあります。

内包性公理 : 述語に対して
- 適当な論理式を満たす集合からなるクラスが構成できる
- 例によって自由変数に関する制約を省略している。正しい記述は英語版 Wikipediaなどを参照のこと

この内包性公理において $\varphi$ を集合について常に真になるような述語、例えば $\varphi(x) := (x=x)$ などとすれば、集合全てからなるクラス $V=\{x \mid x = x\}$ すらも作ることが出来ます。

このような $V$ を考えたときに素朴集合論のようなパラドックスが生じないのは、上で定めた公理の対象の多くを集合に限定しているためです。例えば $V$ は真のクラスであって、真のクラスである $V$ に対しては冪集合公理や和集合公理が適用できません。したがって少なくとも素朴集合論のときのように安易な論法では矛盾を導くことは出来ない事が分かるかと思います。

さて、このように相当強力に見える MK ですが、クラスを考える上で以下のような制約が設けられています。

大きさの制限 :
- 真のクラスならば $V$ との全単射がある

この制約によって、MK では真のクラスについて細かく考えることは出来なくなっています。

ただし逆にこの制約によって、真のクラスについてかなり強い定理が成り立つ事が知られています。例えば順序数全体からなる $\Omega$ は MK における真のクラスとなりますが、これと大きさの制限から、任意のクラスに $\Omega$ との全単射があることが従います。全ての集合からなるクラス $V$ との対応を考えると「全ての集合からなる集まりに順序が付けられる」事になりますから、これは選択公理よりも強い命題になっています。

またこの MK は ZFC より強く、ZFC の無矛盾性を証明できることが知られています。

von Neumann, Bernays, Gödel set theory

NBG, NGB, VBG, VGB, GBC などとも呼ばれます。ここでは NBG と呼ぶことにしましょう。

NBG はほとんど MK と同様ですが、MK よりも ZF(C) に対して保守的な公理系です。MK に対する NBG の関係は、Z に対する MacLane のような関係で、MK と NBG の違いは以下の一点のみです。

内包性公理において、論理式 $\varphi$ は $\Delta_0$ でなければならない

たったこれだけの違いですが、NBG は MK より真に弱い公理系になっています。例えば MK では選択公理は内包性公理によって導出されますが、NBG では上の制約によって少なくとも同様の論法では選択公理を導出することはできません。NBG で選択公理を用いる場合は、選択公理をクラスに拡張した大域選択公理と呼ばれるものを追加した公理系を考えることになります。

また、NBG (または NBG + 大域選択公理) で ZF(C) の無矛盾性を示す方法は知られていません (これが単に不可能なのか、それとも知られていないだけなのか曖昧なのは私の勉強不足によるものです)。

[追記 2020/12/21]

Twitter 上で Alwe (@Alwe_Logic) さんから

NBGではZFCの無矛盾性は示せませんね。NBGで証明可能なZFの文は全てZFで証明可能、NBGがZFの無矛盾性を示せばZFCでも示すことができ、またGodelの構成可能集合の理論からZFとZFCの無矛盾性は同値であるから第2不完全性に矛盾します

との情報をいただけました。ありがとうございます。(追記終わり)

更に MK と NBG の大きな違いとして、MK は有限公理化可能ではない事が知られていますが、NBG は有限公理化可能らしいです。気になる方は調べてみてください。

Ackermann set theory

さて、ここまではクラスのある集合論として MK と NBG を見てきましたが、これらは大きさの制限という公理がありました。このような大きさの制限がない公理が Ackermann set theory です。

Ackermann set theory では、全てがクラスであり、集合が特殊な性質を満たすクラスとして定義される点は MK 同じですが、その公理系は MK と (つまり ZFC と) 少し変わっています。まずは公理を列挙してしまいましょう。

外延性公理 (等しさの定義) : $\forall A \forall B (\forall x (x \in A \Leftrightarrow x \in B) \Rightarrow A = B)$
内包性公理 : 述語 $\varphi$ に対して $\exists A \forall x (x \in A \Leftrightarrow (\mathrm{set}(x) \wedge \varphi(x)))$
要素公理 (集合の要素は集合) : $\forall A \forall x( (\mathrm{set}(A) \wedge x \in A) \Rightarrow \mathrm{set}(x))$
部分公理 (集合の部分は集合) : $\forall A \forall B ( (\mathrm{set}(A) \wedge B \subseteq A) \Rightarrow \mathrm{set}(B))$
集合の内包性公理 : 述語がその中に述語を含まず、ならば
- 「集合である」という命題を直接を使わずに集合であることを示せるものの集まりは集合
- 例によって自由変数に関する制約を(ry 他のサイトを(ry

正則性公理や選択公理を入れる場合もあるようですが、今回はそれらなしのバージョンを考えます。また $\mathrm{set}(A)$ は $A$ が集合であることを表す述語です。

この公理を見ると、MK と異なり別のクラスの要素になるクラスが存在しても良いことが分かります。例えば順序数全体のクラス $\Omega$ に対して、それを含む $\Omega + 1$ というクラスを考えることも出来ます。

また、ZF などに比べると随分公理が少ないのが分かります。しかし公理が少ないからと言って Ackermann set theory が弱いというわけではなく、全ての集合のクラス $V$ の存在や空集合の存在は示すことが出来ますし、Z における対の公理や和集合公理、冪集合公理、無限公理、置換公理に対応する命題をそれぞれ示すことが出来ます。

さらに簡単な対応により、対象を集合に限った命題については Ackermann set theory + 正則性公理は ZF と同等の強さがあることが知られています。

時間がなくて書けなかった公理系

時間が無くて書けなかった公理系です。これについて後に記事をひっそりと加筆する可能性があります。

Typed Set Theory (TST)
Pocket set theory
New Foundations

調べられなかった公理系

見たけどよく分からなかった公理系です。これについて後に記事を加筆する可能性は薄いです。

ZFC + グロタンディーク宇宙
ETCS (Elementary Theory of the Category of Sets)

最後に

…いかがでしたか？結局集合論についてはよく分かりませんでした！

このあたりの話は英語の資料がちらほらある割に日本語の資料を目にする機会が少なく、調べていると結構目新しいことがあって楽しかったです *2。繰り返しになりますが、理解があやふやなまま楽しむだけ楽しんでいる疑惑があるので、怪しい箇所はぶっ叩いてくれると嬉しいです。

あと、みなさんも色々な公理系について調べて記事を書いてくれると僕が嬉しいです。

次は domperor さんの「２段抜きと３段抜きの並存」です。

*1:残念ながら私自身は証明を追えていません

*2:これは僕の見聞が狭いことに由来する楽しさかもしれませんが…

2020-10-23

Raspberry Pi 4B をモニターと無線 LAN なしでセットアップする

Raspberry Pi 4B (8GB) を買い、64bit 版 Raspberry Pi OS (beta) をモニターと無線 LAN なしでインストールして起動することに成功したので、その備忘録を書いておく。

ラズパイを買う

ラズパイの 4B には排熱問題があるらしく、更に手持ちでまともな microSD があるかを確かめるのが面倒になったりしたので、今回は色々入っている下のパッケージを買った。

だたし記事を書く段になってアマゾンの商品ページにアクセスしたところ、商品内容が大きく違うものになっていた (？？？) ので、一応 URL は貼っておくがちょっと警戒したほうが良いかもしれない。

Raspberry Pi 4 アーマード (4GB基盤, アーマーケース(ブラック：FAN無), Anker 18W電源, 高速型64GB MicroSD,4K出力用HDMIケーブル2本, スイッチケーブル)

メディア: Personal Computers

自分について言えば、ディスプレイケーブルは要らないのだがこのパッケージには二本も入っているのでちょっと無駄だったかも知れない。また有線 LAN ケーブルは入っていないので手元にあるものを使用した。

Raspberry Pi OS (64bit) beta をダウンロード

以下の公式 Forum から 64bit 版 OS の iso が入手できる。ダウンロードはかなり遅かった。 www.raspberrypi.org

Raspberry Pi Imager をダウンロード

以下の公式ダウンロードページから環境にあったものをダウンロードする。 www.raspberrypi.org

OS イメージの書き込み

ダウンロードした Imager を起動して CHOOSE OS から Use Custom に進み、先ほどダウンロードした 64bit 版の img ファイルを選択する。適当に microSD カードを選んで書き込み。

SSH の有効化

完了したら microSD カードをラズパイ本体に入れる前に Win とか Mac とかで読み込み、マウントする。Unix 系 OS だったら普通にマウント出来るはずなので色んな人の解説サイト (一例) みたいなのに従って色々設定することが出来る。

Windows の場合、2020-10-12 現在では ext4 がマウントできないので 2 つ外部メモリが刺さっているような表示になるが片方は読み込めない。(僕の環境では microSD カードが E: と F: として追加されたが、F: の方は全く読み込めなかった.)

読み込める方のドライブを開き、ssh という名前で空のファイルを追加する。これでラズパイの起動時に sshd が有効化されるようになる。

次の Windows の大型アップデート (21H1？) では WSL2 経由で ext4 を弄れるようになるらしい。現在も Insider Preview の Dev チャンネルに登録していれば弄れる。早めの正式リリースを期待しましょう。

本体の組み立て

本体に適当にケースをネジ止めしていく。出典は無いが、強くネジ止めすると死ぬらしい。手応えを感じたらドライバーを止める程度で良さそう。

ファンも取り付ける。僕が買ったセットに入っていたファンの電源は 5V (多分) なので、GPIO の 04 と 06 の Pin に指した。 Raspberry Pi 4B の GPIO の一覧はここを参照。

僕はファンを強くネジ止めしたところ外壁が歪んでブレードが干渉してしまったので、ネジ止めをかなり緩めることになった。

本体の起動

電源と有線 LAN ケーブルを繋げて起動する。少し待ってからパソコンで

$ ssh pi@raspberrypi.local

すると接続できる。デフォルトパスワードは raspberry。接続できない場合は正常に起動できていない気がする。

新規ユーザーの作成

既にユーザーグループ sudo がある (pi はデフォルトでそれに所属している) ので利用する

$ sudo useradd -m <new_username> -g sudo
$ sudo su <new_username>
<new_username>$ sudo passwd

までやって sudo 権限のある新規ユーザーが作れているかを確認しつつパスワードを設定。

APT を日本のミラーサーバーに変える

$ sudo nano /etc/apt/source.list して上の三行を

deb http://ftp.jp.debian.org/debian buster main contrib non-free
deb http://deb.debian.org/debian-security/ buster/updates main contrib non-free
deb http://ftp.jp.debian.org/debian buster-updates main contrib non-free

に書き換え (debian-security は JAIST のリポジトリにないので特に変更していない)

(2020-10-12 現在)

Raspberry 固有のパッケージのリポジトリは /etc/apt/sources.list.d/raspi.list で設定できるが、日本のミラーサーバーには 64bit 版のビルドが入っていないので書き換えていない。

パッケージの更新

$ sudo apt update && sudo apt upgrade

でパッケージが更新できたらおしまい。好きに使おう。

最後に

なんかあったら追記します。

ところでこの記事は既にブログに投稿した気分になって 2 週間ほどデスクトップに放置されていた。デスクトップを整理しようとして存在に気づき、よく考えたら投稿していないことも思い出したので今更投稿した。我ながらアホである。

2020-08-09

結局僕たちは intptr_t 同士を演算させても良いのか

C++ において intptr_t 同士の演算がどの程度許可されているのか気になって調べたら意外な事が見つかったのでメモ。

記事中の C++ 規格は 2020/08/09 現在の C++20 の最終 WD である N4861 を参照しています。

intptr_t の定義

そもそも intptr_t や uintptr_t はどう定義されているのか確認しましょう。C++ の規格においてはこれらの型は <cstdint> ヘッダの中に定義される適当な符号付き/符号なし整数型の using であって、コンパイラが実装するかは optional であるとだけ述べられており、その詳細は C ISO 7.20 を参照せよとぶん投げられています。仕方なく C11 の規格を参照し、§7.20.1.4 を読むと intptr_t について

The following type (引用注:intptr_tのこと) designates a signed integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer:

と述べられています (uintptr_tについても同様)。つまり、有効なvoid*からvoid* → intptr_t → void*と変換できて、変換の結果が元のポインタを保存するような整数型であるということです¹。

intptr_t で整数演算がしたい (こともある)

ここで重要なのは、intptr_t → void*という変換単体については何も保証されていないということです。つまり以下のコードの動作は保証されません。

std::intptr_t a = 42;
void* p = reinterpret_cast<void*>(a); // p は (おそらく) 無効なポインタになる
std::intptr_t b = reinterpret_cast<std::intptr_t>(p); // 無効なポインタの変換は保証されない
assert(a == b); // => assertion failed になる可能性が高い

ここから導かれる結論は一般には 「ポインタを整数として扱うべきではない」 というものです。一方で、稀には ポインタが整数であることをフルに活用したコードを書く必要のある場面もあります。その一例が XOR Linked List の実装です。詳細は Wikipedia のページを見ていただければ良いのですが、XOR Linked List は排他的論理和の性質を用いて双方向連結リストの省メモリ化を行うデータ構造であり、ポインタを整数とみなして演算することで実現されます。例えば XOR Linked List 上の要素から終端まで走査する処理を C++ で実装する場合は以下のようなコードを書くことになるでしょう。

template <tyopename T>
struct Node<T> {
    T value; // この要素が持つ値
    std::uintptr_t xored; // 前の要素と次の要素へのポインタの XOR
};

//...

Node<T>* const end = /* 終端のポインタ */;
Node<T>* prev_ptr = /* 一つ前の要素を指すポインタ */;
Node<T>* cur_ptr = /* 最初の要素のポインタ */ ;

while (cur_ptr != end) {
    some_process(cur_ptr->value); // 何かしらの処理

    auto tmp = cur_ptr;

    cur_ptr = reinterpret_cast<Node<T>*>(
        cur_ptr->xored ^ reinterpret_cast<std::uintptr_t>(prev_ptr));
    
    prev_ptr = tmp;
}

前述の C 言語の規定に則れば、このコードの動作は全く保証されず、未定義動作が起こりうるように思われます。しかし C++ では実は (普通に要素を動的確保している分には) このコードの動作は 保証されているのではないか？というのが今回の趣旨です。

Safely-derived pointers

ほとんど知られていませんが、C++ のポインタには valid/invalid という区別とは別に Safely-derived pointer かどうかという区別があります²。Safely-derived pointer は「有効である事が処理系から確実に追跡可能なポインタ」であり、valid 性よりも少し条件が厳しくなっていること以外はそこまで特段に注意すべきことはない概念なのですが、重要なのはその規格内に存在する integer representation of a safely-derived pointer (Safely-derived pointer の整数表現) についての規定 [basic.stc#dynamic.safety-3] です。少し長いですが丸々引用します。

An integer value is an integer representation of a safely-derived pointer only if its type is at least as large as std::intptr_t and it is one of the following:

the result of a reinterpret_cast of a safely-derived pointer value;

the result of a valid conversion of an integer representation of a safely-derived pointer value;

the value of an object whose value was copied from a traceable pointer object, where at the time of the copy the source object contained an integer representation of a safely-derived pointer value;

the result of an additive or bitwise operation, one of whose operands is an integer representation of a safely-derived pointer value P, if that result converted by reinterpretcast<void*> would compare equal to a safely-derived pointer computable from reinterpretcast<void*>(P).

これを見ると、まず Safely-derived pointer の整数表現とは大まかには Safely-derived pointer を intptr_t や uintptr_t に変換したもの及びそれらを追跡可能な範囲で弄ったものを指すっぽいです。特に最後の文章がこの整数表現性が伝播される二項演算についての記述であり、これによれば intptr_t 同士の二項演算を @ として c = a @ b と書けば

@ が加算(減算も？)やビット演算であって
a か b のどちらかが Safely-derived pointer である P の整数表現であり
結果である c が P から計算可能である³

という条件を満たすとき、c も Safely-derived pointer の整数表現である。ということのようです。当然ですが、このとき reinterpret_cast<void*>(c) の結果は Safely-derived pointer であり、その結果をデリファレンスしても未定義動作は起きません。

XOR Linked List のコード再考

ここでもう一度 XOR Linked List のコードを見てみましょう。一箇所コメントを足してあります。

template <tyopename T>
struct Node<T> {
    T value; // この要素が持つ値
    std::uintptr_t xored; // 前の要素と次の要素へのポインタの XOR
};

//...

Node<T>* const end = /* 終端のポインタ */;
Node<T>* prev_ptr = /* 一つ前の要素を指すポインタ */;
Node<T>* cur_ptr = /* 最初の要素のポインタ */ ;

while (cur_ptr != end) {
    some_process(cur_ptr->value); // 何かしらの処理

    auto tmp = cur_ptr;

    cur_ptr = reinterpret_cast<Node<T>*>(
        cur_ptr->xored ^ reinterpret_cast<std::uintptr_t>(prev_ptr)); // ???
    
    prev_ptr = tmp;
}

ここでは prev_ptr および cur_ptr の初期値は Safely-derived pointer (変な事をしていない、動的領域への valid なポインタ) だと仮定します。すると ??? が付いている部分の XOR 演算では被演算変数である cur_ptr->xored と prev_ptr のうち、prev_ptr が Safely-derived pointer の整数表現であり、またその演算結果は Safely-derived pointer を指しているので、演算結果は無事 Safely-derived pointer の整数表現となります。したがって ??? 部分の後も cur_ptr は Safely-derived 性を保っており、このコードの動作が全体として保証される事が分かりました。

まとめ

以上のように、C 言語では合法ではなかったポインタの演算が C++ で追加された (全く使われていない) 概念により合法になってしまうという現象が発生しているのは非常に面白いなと思いました。一方で、コードを書くたびにこのような事を気にしなければならないのは精神をすり減らす事にもなりますし、まず絶対どこかでチェック漏れが生じます。安全なこともあるとはいえ、基本的にはポインタは整数として扱うべきではないというのは胸に刻んでおくべきでしょう。

後から調べたら同じ旨の記述が cpprefjp のページでもされていました。基本から調べる姿勢を忘れてはいけないですね。↩
C++11 で GC のサポートを入れようとする動きがあり、そのために追加された機能みたいです。最近はめっきり GC サポートの話を聞かないので機能としては死んだ機能に近そうです。↩
この"computable"であるという条件はあまり well-defined でないように見えます。はっきりした定義が分かる方は Twitter やコメント欄で教えてくださると助かります。↩

2020-07-10

2020年6月にメモしたことまとめ

相変わらず投稿を忘れがちになる。どちらにせよただの自己満足ではあるのだけど

2日

f:id:azaika:20200710005754j:plain

17日

f:id:azaika:20200710005829j:plain

20日

f:id:azaika:20200710005855j:plain

21日

f:id:azaika:20200710005908j:plain

雑感

コロナでゴタゴタしていて気付いたら夏学期が終わろうとしている。試験も近い。辛いね。

それはそうと大学でやっていた自主ゼミが (ほとんど) 炎上することなく無事終了して、かなり安心した。複雑ネットワークという、ある条件を満たす大規模なグラフの解析についてのもので、試験が落ち着いたら資料が公開できるかもしれない。社会的グラフ上での感染症の広がりのモデル化とかがあって奇しくもかなりタイムリーなものだった。

2020-06-17

2020年5月にメモしたことまとめ

完全に投稿を忘れていて月も半分が過ぎている。我ながらひどい

2日

f:id:azaika:20200617103827j:plain

8日

f:id:azaika:20200617103856j:plain

20日

f:id:azaika:20200617103928j:plain

28日

f:id:azaika:20200617103944j:plain

雑感

レポートが忙しい。レポートに書いた内容でもあとでこっちにまとめなおす事で何か得られる気がするので気が向いたらやっていきたい。

2020-05-03

2020年4月にメモしたことまとめ

明日 (と言うには日が昇ってきた今では無理があるが) は予定がある。なぜお前は寝ていないんだと自分で思ってる。

6日

f:id:azaika:20200503044307j:plain

7日

f:id:azaika:20200503044322j:plain

9日

f:id:azaika:20200503044342j:plain

10日

f:id:azaika:20200503044401j:plain

14日

f:id:azaika:20200503044420j:plain

雑感

最初の2週間しか記事を書いていない。これは怠惰ゆえか。多分そう。

とはいえ怠惰なのは昔からの事で、それを除けば一番の要因は授業が始まったことだと思われる。先月は「授業が始まればこういうメモに書けること増えるかな〜」みたいなセリフを宣っていた気がするが、実際は授業中の気づきは普通ノートやスライドに書き込む。当たり前の話だった。

とはいえ授業やゼミ以外で記すべき事が無かったかといえばそんな事もないはずで、5月分の記事でも同じ言い訳をするわけにはいかない。やり方とか意識とか、ちょっとづつ変えていきたいものは色々ある。まあ一番変えるべきなのは暇な時にベッドに寝転がって Twitter を開くのではなく、気になっていた記事や論文を読んだり技術に触ってみたりする事なのは言うまでもないのだが。

目次