3imp ヒープ・ベース・コンパイラ/VM と CEK マシンの関係 (2)

3 年経て改めて考えてみたところ、 無駄と切り捨てたのが、 CEK マシンの素のそれだと、 今頃になって気がついたので、 自己ツッコミ。 なお、 いつものように慣例に合わせて、 R. K. Dybvig, Three Implementation Models for Scheme (1987) を 3imp と略し…

シンボル集合のリストによる安直実装

毎度ながら、 内容の薄い懐古趣味を一席。 K. Dybvig Three Implementation Models for Scheme, 1987 (以下、 3imp) では、 手続きをフラット・クロージャへコンパイルするのに、 自由変数と束縛変数の集合演算を用います。 その集合演算には、 リストによる…

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…

Wirth VM で 1960 年代の S 式構文解析

Niklaus Wirth 表駆動解析法 (Compiler Construction) は、 LL (1) 文法を認識する再帰下降型の構文解析をグラフ・データ構造で表現したものです。 それを命令コード化して VM にしたものを、 暫定的に Wirth VM と呼ぶことにします。 VM の命令は 4 つです…

Turing 言語のコレクション

1980 年代初頭にトロント大学で開発された PASCAL 系列のプログラミング言語 Turing はコレクションと名づけられたおもしろい機能をもっています。 「型 T のコレクションとは、 型 T へのポインタの集合のインスタンスである」として定義してあります。 ⇒ R…

Chibi Scheme のゴミ集め

Chibi Scheme の組み込み手続きは C 言語の関数で記述してあり、 C 言語の auto 変数をヒープ中の Scheme のセルに束縛しています。 そのため、 ゴミ集め時に C 言語のコール・スタックを調べる必要が生じ、 3 つの方式を処理系のビルド時に選べるようになっ…

letrec と letrec*

R5RS 以前の letrec は実装に依存します。 R6RS でセマンティック・エラーになる書き方をしてみると…… (let ((a 4) (b 5)) (list (letrec ((a (begin (set! b 2) b)) (b (begin (set! a 3) a)) (f (lambda (t) (cons a b)))) (f #t)) (cons a b))) ;=> ((3 .…

3imp のフラット・クロージャ

R. K. Dybvig Three Implementation Models for Scheme (以後、 3imp と略す) でこってりと解説してある Chez Scheme 用フラット・クロージャについて。レキシカル・スコープの実装方法はいくつもあり、 Scheme 動作の説明で使われることが多い環境束縛モデ…

XML 内部サブセットと引数実体参照

整形式制約から、 XML の内部サブセットでは、 リテラル内含めて宣言中に引数実体参照を使えません。 この点は、 XML 1.0 でも 1.1 でもそこは同じなので、 1.0 の仕様から。 ⇒ XML 1.0 Well-formedness constraint: PEs in Internal Subset In the internal…

Knuth の乗算ハッシュ法

整数ハッシュの計算の一つ、 乗算ハッシュ法についての覚書です。⇒ D. Knuth, The Art of Computer Programming 2nd Edition, Volume 3 6.4 HASHING, 516 page (TAoCP と略す)ある整数 k に対するハッシュ値を求めるのに、 Knuth 乗算ハッシュ法は、 固定小…

グラフィック・カードのキャパシタ破裂

自宅の Linux デスクトップ用マシンを使っていると、 突然、 前触れなくリブートをおこしました。 リブート後に /var/log 以下の Xorg と Kernel のログを見てもどこにも異常の記録がありません。 それで、 電源絡みの故障だろうと見当をつけました。 電源を…

Gtk+ 3 アプリケーションの Makefile.am

Ubuntu 14.04 LTS の libgkt-3-dev のバージョンは 3.10.8 で、 アプリケーションを GNU Automake と GNU make でビルドします。 Meson より前の古いビルド方式で、 過渡期だったためか、 ドキュメントが乏しいので、 自分用に事例をメモしておきます。題材…

Ubuntu 14.04 LTS MATE 改 + IBus の .xprofile の謎

Ubuntu 14.04 LTS を GNOME3 から MATE に入れ替えると、 その段階で Gtk3 と Gtk2 が混在しています。 そこにさらに Qt-5.5 を混ぜて、 日本語入力をフレームワークに関係なくできるようにしました。 なお、 Ubuntu 配布の qt-5.2.1 は 14.04 LTS にアップ…

テキスト差分 Wu によるO(NP) 法の Hirschberg 法化まとめ

テキスト差分アルゴリズムでは現在知られている最も高速な Wu による O(NP) 法に、 2 N の作業領域で求める Hirschberg 法を摘要した試みへのリンクをまとめます。 第一期は Ruby によるスタディで、 第二期は、 diff に準拠したコマンドを C++11 で書いたも…

Ubuntu 14.04 への MySQL-5.7 インストール失敗回避バッドノウハウ

Ubuntu 14.04 標準の MySQL-5.5 から、 JSON のため MySQL-5.7 へ乗り換えようと再インストールしていたら、 途中でエラーが発生して正常にインストールができませんでした。 /usr/sbin/mysqld: Can't read dir of '/etc/mysql/mysql.conf.d/' (Errcode: 13 …

n 分木 Rope データ構造のランクはキーより左側の部分木を連結した文字列長

前回、「ここまでは二分木なのですが、 B+ 木のような多分木で同様の部分木ランク付けを使おうとするとどうなるのだろうかと考えが進みます。 例えば、 B+ 木にランク付けする用途だけではなく、 文字列データ構造 Rope を n 木で扱う方法の参考になるかもし…

3imp スタックベース compile/VM の begin 形式とクロージャ

2017 年 12 月 5 日追記 この稿の説明には勘違いが含まれています。 式の並びを入れ子 lambda に変換しなくても、 それぞれの式から求めた変数の集合の和集合を求めることで、 正しい集合を求めることができ、 必要な box 化をおこなうことができます。Dybvi…

3imp ヒープベース compile/VM での begin 形式

Dybvig Three Implementation Models for Scheme (以下 3imp) では、 begin 形式と lambda 形式のボディを、 入れ子の lambda 形式へ変換してコンパイルするとあります。 それでも間違いではないのですが、 一つ注意点があって、 入れ子になっている lambda …

3imp ヒープ・ベース・コンパイラ/VM と CEK マシンの関係

Dybvig Three Implementation Models for Scheme (以下 3imp) のヒープ・ベース VM は、 VM だけでは CEK マシンから逸脱する動作もできてしまいますが、 コンパイラで CEK マシンに等価になるようにコード生成して制限をかけています。複合手続きのアプリケ…

SICP 積極制御評価器と CEK マシンの関係

サスマン「計算機プログラムの構造と解釈 第二版」(以下 SICP) 5.4 節記載の Scheme の積極制御評価器 (Creative Commons 版の翻訳)は、 いきなりレジスタ計算機のアセンブリのソースがずらずらと並んでいて見落としがちですけど、 CEK マシンを実装したもの…

非カーネル用のスラブ・アロケータ

オペレーティング・システムのカーネルのオブジェクト・キャッシュとして利用されているスラブ・アロケータは、 単なる高速なアロケータではなく、 割付・初期化済みのオブジェクトを alloc して、 free の時点ではデストラクタを動かさずに、 次の alloc で…

Hash オブジェクトの内部データ構造が更新されていました

CRuby の開発リポジトリの trunk へ、 1 月間前の2016年11月7日にハッシュ法の新しい実装がマージされました。 CRuby trunk st.c ⇒ Introduce table improvement by Vladimir Makarov <vmakarov@redhat.com>. · ruby/ruby@7577515 · GitHub開発ブランチ ⇒ GitHub - vnmakarov/ruby</vmakarov@redhat.com>…

日本語 Wikipedia の深さ優先探索

説明省略のリンク先に使おうかと読んでみたところ、 日本語 Wikipedia に記載されている while ループ版のアルゴリズムは、 訪問済みチェックを継続に入れる前におこなう方法で、 ゴミ集めなどで使われているやりかたです。 この方法は、 行きがけ順を気にせ…

ECMAScript のスラッシュ判断

そのスラッシュは、 コメントか? 除算記号か? 正規表現リテラルか? それが問題だ。 ということで、 テキスト・エディタのシンタックス・ハイライト規則を覗いてみました。 GNU Emacs 24.3 の場合 ⇒ /usr/share/emacs/24.3/lisp/progmodes/js.el.gz = ( [ { ,…

ISO 8601 の週と年

ISO 8601 の週は月曜日から始まり日曜日で終わります。 数値で月曜日を 1、日曜日を 7 で表します。 年の最初の木曜日を含む週が最初の週になり W01 と表記します。 最初の週の前は前年の最後の週になります。2016 年 5 月 14 日書き直し: Chronological Jul…

正規表現の角括弧記法の DFA

正規表現の角括弧で囲んだ文字集合要素リスト中に \d 等が使えると便利です。 \d 等が使える文字集合要素リストは NFA で簡潔に記述可能ですが、 これを DFA に変換してみました。 ただし、 DFA の状態数が増えすぎるので、 8 進数や 16 進数でのコード・ポ…

OpenSSL の probable_prime 関数

OpenSSL の巨大整数の素数の候補を生成するとき、安全素数に限定せず、合同関係の限定もしない場合、 probable_prime 関数を使います。 そこの、候補からふるい落としをしている箇所の、 コメントの記述とコード自体が合っていません。 ⇒ openssl/crypto/bn/…

GF(2**m) のベクトル表現

久しぶりに Rijndael 暗号で Galois 体 GF(256) をいじったら、 原始多項式の根である原始元と、 既約多項式 (因数分解できない多項式) の根によるベクトル表現がごっちゃになってしまい、 記憶が薄れていたのを実感しました。 用語と意味を簡単に復習します…

TOML の LALR (1) 文法の構文 行指向版

前回は単純化のため改行と空白を同一視した構文にしました。 これを修正して、仕様通りに改行をいれるべき場所と、改行をいれてはいけない場所を構文で扱えるようにします。 さらに、 ベアキーの特別扱いフラグを構文と字句解析の両方で操作する方法も考えま…

TOML の LALR (1) 文法の構文

TOML の仕様はなぜか行指向になっています。 構文上では行指向にする必要性がなく、 字句間の任意の位置に空白と改行を区別せずに置いてもあいまいさが生じません。 下向きでも上向きでも行指向でない構文を記述可能ですし、 その方が生成規則がすっきりしま…