proper-list? 手続きのアセンブリ記述

Scheme

SICP では仮想マシンの解釈器をわざわざ使ってインタプリタとコンパイラを記述してますけど、 Scheme でそのまま実行できる仮想ストアド・レジスタ機械のアセンブリを、 Scheme の手続きとして記述することができます。例として、正規リストかどうかを検査する手続きを記述してみました。

(define (proper-list? x)
 (define (go k) (k))
 (define (return v) v)
 (let ((t0 #f) (t1 #f) (t2 #f))
  (define (L1) (set! t1 x)
               (set! t2 t1)
               (go   L2) )
  (define (L2) (set! t0 (null? t2))
               (if t0 (go L5) (begin
               (set! t0 (pair? t2))
               (if t0 (go L3) (begin
               (set! t1 'dotted)
               (go   L6) )))))
  (define (L3) (set! t2 (cdr t2))
               (set! t0 (null? t2))
               (if t0 (go L5) (begin
               (set! t0 (pair? t2))
               (if t0 (go L4) (begin
               (set! t1 'dotted)
               (go   L6) )))))
  (define (L4) (set! t1 (cdr t1))
               (set! t2 (cdr t2))
               (set! t0 (eq? t1 t2))
               (set! t0 (not t0))
               (if t0 (go L2) (begin
               (set! t1 'cyclic)
               (go   L6) )))
  (define (L5) (set! t1 'proper)
               (go   L6) )
  (define (L6) (set! t2 'proper)
               (set! t0 (eq? t1 t2))
               (return t0) )
  (L1)))

2019-06-23

crit-bit 木 (その3)

C言語

crit-bit木は Ruby で試したものですが、本番の C 言語の落ち穂拾いをしてみます。

D. J. Bernstein の qhasm の C 言語で記述したソースコードの中に含まれている crit-bit 木の挿入手続きは次のような goto を使った箇所があります。ここでは、挿入したいキーと木の中から見つけた critical bits が一致する文字列で、共通する接頭ビット列の長さを求めています。 newbyte へ一致するバイト数、 newotherbits へ最初の一致しないビットをゼロにしたビット反転マスク・パターンを求めます。

なお、両方の文字列が一致するときを特別扱いして、値 1 で手続きから戻ります。

  uint32 newbyte;
  uint32 newotherbits;
  for (newbyte = 0; newbyte < ulen; ++newbyte) {
    if (p[newbyte] != ubytes[newbyte]) {
      newotherbits = p[newbyte] ^ ubytes[newbyte];
      goto different_byte_found;
    }
  }
  if (p[newbyte] != 0) {
    newotherbits = p[newbyte];
    goto different_byte_found;
  }
  return 1; different_byte_found:
  newotherbits |= newotherbits >> 1;
  newotherbits |= newotherbits >> 2;
  newotherbits |= newotherbits >> 4;
  newotherbits = (newotherbits & ~(newotherbits >> 1)) ^ 255;

ここで、 p は木から探した文字列の先頭バイトへのポインタで、 ubytes はキー文字列の先頭バイトへのポインタです。両方の文字列ともに、ゼロ終端であることを前提にしています。 ulen は ubytes が先頭を指している文字列のバイト長です。

これを goto を使わずに、簡潔な記述に書き直してみます。まず、 for ループを繰り返す条件は、 p と ubytes の両方の newbyte 位置のバイトが一致するときです。ただし、両方共ヌル文字で一致するときは、両方の文字列が終端まで同一であることを意味しており、手続きから戻らねばなりません。そのとき、 newbyte は ulen になっています。

  for (newbyte = 0; p[newbyte] == ubytes[newbyte]; ++newbyte)
    if (newbyte == ulen)
      return 1;
  newotherbits = p[newbyte] ^ ubytes[newbyte]);
  newotherbits |= newotherbits >> 1;
  newotherbits |= newotherbits >> 2;
  newotherbits |= newotherbits >> 4;
  newotherbits = (newotherbits & ~(newotherbits >> 1)) ^ 255;

コンパイラの最適化が賢いなら、バイトの一致判定が排他的論理和結果のゼロ判定と等価であることを利用して、 4 行目を 1 行目に取り込んでくれるかもしれません。中間変数が減り、レジスタ割当が有利になるので、そうなって欲しいところです。ですが、ここでは賢くないコンパイラのために、可読性を落として、手作業で最適化向けの記述にしておきます。

  for (newbyte = 0; (newotherbits = p[newbyte] ^ ubytes[newbyte]) == 0; ++newbyte)
    if (newbyte == ulen)
      return 1;
  newotherbits |= newotherbits >> 1;
  newotherbits |= newotherbits >> 2;
  newotherbits |= newotherbits >> 4;
  newotherbits = (newotherbits & ~(newotherbits >> 1)) ^ 255;

2019-02-11

テキスト・エディタの interactive 引数指定の正規表現

Ruby

GNU Emacs の編集コマンドは interactive 特殊形式を持つだけでなく、この特殊形式で対話時に引数をどのように得るかを指定します。この仕掛けは、関数と編集コマンドの差異をなくす働きをします。エディタの read-eval-print ループからは、特殊形式を基に引数を作ってコマンドを呼び出します。一方、関数やコマンドからは、この特殊形式を無視し、コマンドをあたかも通常の関数であるかのように摘要に利用できます。

引数指定は文字列になっています。その中で、 1 つの引数を 1 文字で指定します。例えば、コマンド・プレフィックスから数を得たいときは (interactive "p") と記述します。ミニバッファを使って文字列を得たいときは s にプロンプトを続けて (interactive "sString ?") と記述します。ミニバッファから値を得る引数指定のプロンプトを省略することはできません。また、プロンプト付き引数指定の後に他の引数指定を続けるときは、 1 つの改行で区切ります。

  (interactive "sString 1 ?\nsString 2 ?")

プロンプトが付かない引数指定も改行で区切ります。現点 (d) とマーカー (m) の値を引数に受け取る指定は次のようにします。

  (interactive "d\nm")

ここでのローカルな規則の緩和として、末尾に改行を付けても良いことにしましょう。

  (interactive "sString 1 ?\nsString 2 ?\n")

さらに、パターンを簡単にするため、プロンプトなしの引数指定文字 p と、プロンプト付きの引数指定文字 s の 2 つだけが使えるものとしましょう。

空行を許す
p にプロンプトを指定しない
p の後に p か s を続けるときは改行を 1 つ挟まなければならない
s にプロンプトを指定しなければならない
sプロンプト の後に p か s を続けるときは改行を 1 つ挟まなければならない
末尾に改行があっても良い
改行を 2 つ以上並べることは禁止

このような規則にマッチする ruby の正規表現は簡単なものです。

  INTERACTIVE_PATTERN = %r{
    \A (?: [p] | [s][^\n]+ ) (?: \n (?: [p] | [s][^\n]+ ) )* \n? \z
  }msx