Onigmo の \G アンカーによる字句走査

ruby の組み込み正規表現オブジェクト Regexp には match メソッドが一つあるだけです。 このメソッドの第 1 引数に文字列を、 第 2 引数には検索開始位置を文字単位で指定します。 第 2 引数は省略可能でそのときはゼロを指定したことになります。 match メ…

StringScanner で戻り読みパターンが利用できない理由

添付ライブラリ strscan 0.7.0 ではパターンに戻り読みが使えません。 理由は簡単で、 次の引用箇所のように、 検索対象文字列に指定するアドレスに、 文字列先頭アドレス (S_PBEG マクロ) ではなくスキャン・ポインタに対応するアドレス (CURPTR マクロ) を…

Markdown ブロックの WikiWikiWeb 方式での書式変換

これまで書いた Markdown 書式変換器は、 John Gruber によるPerl によるリファレンス実装の入れ子認識法を参考にしていました。 そこでは、 ブロックを構成する一連の行の行頭マークを一つずつ削りながら下の行へと降りていき、 削り終えたら、 削り初めた…

再帰データ型宣言

プログラミング言語 Pascal の直系では、 ワン・パス・コンパイル対応のため、 定数・型・変数宣言を let* で、 手続き宣言を letrec* で処理する伝統があります。 ただし、 再帰データ型対応のため、 ポインタ型宣言だけが例外で、 POINTER TO IDENT のよう…

Wirth VM のアセンブラ改

Wirth VM はすべての命令の第一と第二オペランドに飛び先番地を記入します。 これまでは、 すべての命令にラベルを割り振ってみましたが、 行番号時代の BASIC のように、 どこが飛び先なのかわかりにくくなってしまっていました。 そこで、 これまで書いて…

左・右再帰と Wirth VM

一個以上の項目をコンマで区切った単純なリストを、 左再帰と右再帰のそれぞれで Yacc 風に記述してみましょう。 話を単純化するため、 item の FIRST 集合はコンマを含まず、 item の FOLLOW 集合と fold_left および foldright の FOLLOW 集合には重なりが…

型記述子ごとの Cheney Copying ゴミ集め (その 2)

C99

ペア・オブジェクトやベクタ・オブジェクトのようにヒープ空間に割り当てるオブジェクトの最小単位のことを LISP の慣例にならってセルと呼ぶことにします。 セルはゴミ集めの処理単位です。 コピー方式のゴミ集め Cheney Copy 算法では、 移動元 from 空間…

Oberon システムのゴミ集め

Oberon システムのゴミ集めは完全なマーク & 一括スイープ方式です。 ゴミ集めは協調型タスクとしてスケジュールされ、 ゴミ集め中に他のタスクのスタックは空なので、 全ロード済み MODULE のグローバル変数のポインタをルート・セットに選ぶだけで済んでい…

Oberon-07 のシンボル・ファイル

プログラミング言語 Oberon-07 は Modula 言語族に属し、 翻訳時環境の束縛対を永続化してシンボル・ファイルを作成する、 この言語族共通の機能を持ちます。 永続化の対象は、 翻訳単位である MODULE 宣言のトップ・レベルと、 そこから見える構造体フィー…

M. Adams 等の R6RS equal? の find 手続き

M. D. Adams, R. K. Dybvig, Efficient Nondestructive Equality Checking for Trees and Graphs, 2008 (以下、 ADAMS2008 と略す) の find 手続きについて。 結論は先送りで、 気になった点を備忘録として残しておきます。SRFI-85 で提案されて、 R6RS Sche…

Snapshot Isolation のおもちゃ・undo ログ MVCC 版

1ヶ月前に作ってみた「行持ち MVCC」では、 行ごとに並んでいる作業データの残骸を取り除くのにゴミ集めが必要になります。 一方、 同じ MVCC でも表単位での undo ログを利用すると、 ゴミ集めが不要になります。undo ログ方式もいくつか流儀があり、 ここ…

Packrat 解析器を Wirth VM で (その2)

以前の Ierusalimschy VM 用に作った Parsing Expression Grammar DSL の PEG モジュールを、 Packrat 化 Wirth VM でも利用できるようにします。 PEG モジュールは grammar モジュール関数のブロック中で、 Ruby の式を使って PEG を記述できるようにしてあ…

Packrat 解析器を Wirth VM で (その1)

感桁 PEG の字下げを扱える Packrat 解析器を作ってみようと試行錯誤しています。 まず、 以前、 Ierusalimschy VM で書いた Packrat 解析器を手直しすることを考えたのですが、 継続の取り回しが面倒で諦め、 その辺が単純化できる Wirth VM に乗り換えてみ…

Wirth VM の簡易アセンブリ

字下げ判定のための命令を Wirth VM に追加して動かしてみようと考えたのですが、 その前にアセンブリを作っておきます。 Wirth VM はすべての命令に成功時と失敗時の飛び先を記入するため、 飛び先をラベルで指定できないと修正が大変です。 さらに、 すべ…

Adams の字下げ文法による YAML 風構文 (その2)

絶対カラム位置で字下げを扱うようにすることで、 構文の生成規則が簡潔になる上、 変更しやすくなります。 昨日は YAML を尊重して、 ブロック・シーケンスで許している、 コンパクト形式と呼ばれている同一行でのブロック要素の入れ子をブロック・マッピン…

Adams の字下げ文法による YAML 風構文 (その 1)

YAML 1.2 の構文は、 下向き解析に属性文法を使って、 相続属性と合成属性で相対カラム幅を扱うことで、 字下げ情報を構文に落とし込んであります。 一方、 M. D. Adams Indentation-Sensitive Parsing for Parsec (2014) も、 下向き解析に属性文法で字下げ…

qp-trie

crit-bit 木は二分木です。 それの節で扱うビット数を増やして N 分木の基数木にすることが考えられます。 N 分木の基数木の節は一般に nil ばかりでほんの一部しか使わない疎な配列です。 そこで、 疎配列の実装の一つである P. Bagwell による array mappe…

Snapshot Isolation のおもちゃ・行持ち MVCC 版

前回のおもちゃはトランザクションごとに大域データを丸ごと局所データにコピーして隔離を実現しました。 今度のおもちゃは複数のバージョンをデータに混ぜる Multiversion concurrency control (MVCC) で隔離してみます。 バージョンの混ぜ方は様々で、 今…

AVL 木 その場書き換え版

赤黒木で左右の条件分岐を一つにまとめた方法を、 AVL 木でも試みてみます。 AVL 木は、 平衡因子が左右で反対称になっているため、 赤黒木ほど簡単に条件分岐を一つにまとめることができません。今回の AVL 木も、 親節への参照を持たない節を使います。 節…

赤黒木 その場書き換え版

赤黒木の平衡調整は、 綺麗に左右対称の記述になっています。 それを利用して、 crit-bit 木のように子への参照を 2 要素の配列にすることで、 左右の場合分けを一つにまとめることができます。 左をゼロの位置に、 右を 1 の位置に配置することにします。 …

crit-bit 木 (その2)

次のように、 crit-bit 木に含まれる最小値・最大値、 指定した値の一つ前・一つ後を求められるようにメソッドを追加します。 tree = Critbit::Tree.new ["xyz`", "xyza", "xyze", "xy`", "xya", "xye"].each {|k| tree.insert(k) } #=> ((("xy`" 23 "xya") …

crit-bit 木 (その1)

D. J. Bernstein (以下 djb) が 2006 年に発表した crit-bit 木 はビット列用のwikipedia:基数木で、 二分木になっています。 djb の qhasm に C 言語で記述したソースコードが入っています。 葉にビット列を保持し、 節はビット位置を持ちます。 節のビット…

Snapshot Isolation のおもちゃ・修正版

昨日のおもちゃは、 トランザクションで生じた編集過程をすべて記録して、 コミット時にグローバル・データの書き直しに利用していました。 そのため、 定義通りの Snapshot Isolation とは異なる挙動を示すことがありえます。 定義では、 スナップショット…

Snapshot Isolation のおもちゃ

Snapshot Isolation の提唱元 Berenson 等 A Critique of ANSI SQL Isolation Levels (1995) の定義通りに動く「おもちゃ」を実用性無視で記述するのは割と簡単です。 トランザクションの開始時点でグローバル・データのスナップショットをとりトランザクシ…

配列上の B+ 木

B+ 木の挿入・削除の算法に触れるのに、 節をオブジェクトにして節オブジェクトから節オブジェクトを参照する記述にするのはわかりやすくはありますが、 B+ 木の利点を活かすには節をファイルに配置します。 ファイルに配置している節に挿入・削除するときは…

あふれありの TAoCP 流その場書き換え B+ 木

節の先頭ポインタを別扱いせずに一つの配列にまとめるあふれなしのやりかたで、 あふれありのその場書き換え B+ 木を修正してみます。 あふれなしのときは、 B+ 木の次数 ORDER 分の配列にしていたのに対して、 あふれを許すときはさらに一つ大きくします。 …

その場書き換え方式の赤黒木

二分探索木の基本の左右表現に色と親への参照を加えた節を使った、 ありきたりな赤黒木です。 class RedBlacktree #@<左右表現に色と親への参照を加えて節にします@> #@<葉の nil は黒、 節はそれ自身の色とします@> #@<根の上に、 無限に黒の節を並べます@>…

二分木の子・兄弟表現 (その2)

二分木の通常の表現は、 左と右の子節への2つの参照を節にもたせます。 それに対して、 子と兄弟への2つの参照で表すのが子・兄弟表現です。 兄弟参照は左から右へと指して、 右から向きを変えて親を指すようにします。前回は参照を素のままで二分探索木の表…

スプレー木 (その3)

前の版のスプレー木は、 木の回転を標準とは異なりノードの親子関係を配置換えしない方法で書いていました。 今度は、 木の回転を標準にしてノードの親子関係を配置換えすることにします。 さらに、 削除でも根とノードを配置換えするようにします。 配置換…

二分探索木の子・兄弟表現

ペアリング・ヒープ (pdf) 向けとされている二分木の子・兄弟表現を二分探索木で使うとどうなるのか試してみました。 子・兄弟表現とは、 ノードの 2 つのポインタの一方を子ノードへのポインタ、 他方のポインタを兄弟もしくは親ノードへのポインタに変更し…