カラツバ法

CourseraのAlgorithm Part1で出てきてふと実装熱が再燃した。

カラツバ法はかなり面白い乗算のアルゴリズム(と個人的に思っている)で、最初見たときはいきなり意味不明なことしてるぞ、とか思ったりした。アルゴリズムの肝は以下のような感じ。

;; multiplicands, x y
(define x #x123456789)
(define y #x908765432)

(define B 16) ;; radix
(define n 9)  ;; n digits

#|
x = a*B^(n/2) + b
y = c*B^(n/2) + d
|#
(define a #x12345) ;; most significant part of x
(define b #x6789)
(define c #x90876) ;; most significant part of y
(define d #x5432)

#|
x*y = (a*B^(n/2) + b) * (c*B^(n/2) + d)
    = B^n*ac + B^(n/2)*(ad + bc) + bd
    = 16^n*ac + 16^(n/2)*(ad + bc) + bd
|#
(let ((ac (* a c))
      (bd (* b d))
      (xx (+ (* a d) (* b c))))
  (+ (* (expt B (* (div n 2) 2)) ac) 
     (* (expt B (div n 2)) xx)
     bd))

以前実装を諦めた理由を覚えていないのだが、なんとなく実装できたのでベンチマークをとってみた。ベンチマークには以下のコードとスクリプトを仕様。

(import (time) (sagittarius control))
(define ex 2048)
(define ey 2048)
(define x (expt 2 ex))
(define y (expt 2 ey))
(define count 50000)

(time (dotimes (i count) (* x y)))

#!/bin/sh
echo Non karatsuba
time sash multi.scm
echo Karatsuba
time ./build/sash multi.scm

何のことは単なるスクリプト。シェルでtimeコマンド使う必要は無かったかもしれない。っで、以下が結果。

$ ./time.sh
Non karatsuba

;;  (dotimes (i count) (* x y))
;;  2.238128 real    2.215000 user    0.000000 sys

real    0m2.771s
user    0m2.449s
sys     0m0.296s
Karatsuba

;;  (dotimes (i count) (* x y))
;;  1.882108 real    1.872000 user    0.000000 sys

real    0m2.387s
user    0m2.090s
sys     0m0.296s

400msほど高速に計算する。まぁ、5万回まわしてこの程度とも言える。

カラツバ法のアルゴリズムだからなのか実装が悪いのか分からないが、乗算の数値のサイズが違いすぎると逆に遅くなる。適当に計測した結果、Sagittariusの実装だとおよそ10ワードが境界となった。なのでそれ以上の差がある場合は従来の乗算を使う。(この辺例えばToom-3とか実装すると解決するのかも、とか思いながら腰は重い。)

SRFI-11の紹介

(LISP Library 365参加エントリ)

SRFI-11は多値を扱う構文です。このSRFIではlet-valuesとlet*-valuesという構文を提供します。多値を扱う構文といえばすでにSRFI-8を紹介していますが、こちらは構文の名前がもう少しだけ直感的です。

R6RS/R7RSに慣れ親しんだ方なら既に知っているかと思いますが、以下のように使います。

(import (rnrs))
;; or (import (scheme base))
;; or (import (srfi :11))
;; if you want to use it on Gauche, then (use srfi-11)

(let-values (((a b c) (values 1 2 3)))
  (+ a b c))
;; -> 6

(let*-values (((a b c) (values 1 2 3))
              ((d e)   (values a (+ b c))))
  (+ a b c d e))
;; -> 12

(let-values (((a b . c) (values 1 2 3 4 5)))
  (list a b c))
;; -> (1 2 (3 4 5))

(let-values ((v (values 1 2 3)))
  v)
;; -> (1 2 3)

letのように直感的に多値の束縛が可能になります。

これはreceiveにもいえるのですが、処理系によっては多値の実装をこれらの構文で行いcall-wit-valuesを単なる手続きにしているものもあります。そのような処理系では構文で束縛する方がコストが安いことが多いです*1。

今回はSRFI-11を紹介しました。

*1:例えばSagittariusでcall-with-valuesを使うと必ずconsumer手続きに渡される引数がパックされるのでメモリの消費が多少大きくなります。またprocedureもしくはconsumer手続きがlambdaを使って書かれている場合インライン展開されずに手続きが必ず生成されます。多値を多用する際に性能を出すにはlet-valuesもしくはreceiveを使う必要があります。

厄介めなバグ

「厄介め」という言葉があるかどうかは別にして、そこそこどうしようかなぁと思わせるバグを発見してしまった。

端的には以下のようなコードが問題になる。

(read (open-string-input-port "#!r6rs #t"))
(call-with-string-output-port
  (lambda (out)
   (write '|\|| out)))
;; expect: "|\\||"
;; actual: "\x7c;"

要するにreadが読み込んだ#!がVM全体に影響を与えるという問題である。リードテーブルはポート単位なのだが、#!はファイル単位で管理されているのが大元の問題といえばそうなる。

ではどうするか？とりあえず思いつく解決案としては、loadで読まれたのかread(もしくはそれに準じる手続き)で読まれたのかが分かればVMのフラグを立てる立てないのチェックが出来そうである。(そもそも、#!がリーダー以外に影響を与えるというのがよくないというのもあると言えばあるのだが、それを直すのはちと大変なのだ。)

上記の解決案で問題になることがあるとすれば、ユーザーがreadとevalを用いて自作loadを作った場合だろう。そこまで考慮にいれるべきなのかという話でもあるのだが、Scheme精神としてはYesで個人的にはNoだったりする。ただ、既に見えている問題というのは大抵「後で自分が踏む可能性が高い問題」と言い換えることができるので、ここで手抜きして後で苦労するか、ここで苦労して後で楽をするかである。怠惰なプログラマを目指す僕としては「未来の自分が楽をするために努力する」べきだと思うのでもう少し抜本的な解決策を模索するべきだろう・・・

プログラミングスタイル

多少時期を逃した感はあるが、最近「オブジェクト指向 v.s. 関数型プログラミング」というHaskel最高っていってる記事を読んだ*1。僕はオブジェクト指向も関数型プログラミングも中の中くらいの凡々プログラマなのだが、ふと10年くらい前に「これからはオブジェクト指向、手続き型は古い」みたいなのが流行していたのを思い出した。

当時はJavaが(まだ)新興言語に近くオブジェクト指向とはなんぞやみたいな感じだった(気がする)。それに便乗したのか、雑誌の多くは「これからはオブジェクト指向」みたいな感じで、ちょうど上記の記事みたいなことを列挙していた。以下は記憶にある項目

• コードの再利用
• 疎結合
• トップダウンスタイル開発
• 可読性
• メンテナンスの容易さ

等々だった気がする。これ見て当時まだまだ若造(今でもだが)だった僕は「オブジェクト指向ってすごいんだねぇ」と思った記憶がある。

そう思った矢先というわけでもなかったかもしれないが、この風潮に批判的な記事ももちろんあって、その一つで鮮明に覚えているのがC言語でも昔からオブジェクト指向がされてきたみたいなことを言っているものだったと思う。具体的にはlibcにあるFILE構造体はそれだというようなことを指して、gtkとかもCだがオブジェクト指向してるという話をしていた気がする。そこから、プログラミングで重要な要素の一つは抽象化であって、オブジェクト指向言語でなければそれが出来ないというわけではない(が面倒)、というのを学んだ気がする。

さて、そんな猫も杓子もオブジェクト指向な時代は(多分)5年くらい前に終わって、企業が使う言語と言えばJavaな時代が来たわけだ。大勢の人が使うということは、Javaが求めるスタイルに合わない人が多数出てくるということでもある。自分もどちらかと言えば合わない方だろう。そうすると時代は繰り返すのか、今はまだメインストリームではないスタイルを引っ張り出してきてこっちの方がいいから皆も使うべき、見たいなのが出てくる。っで、どの辺が優れているかというので、大体上記の項目が挙げられるわけだ。最近の動向だと、関数型プログラミングがその矢面に立ってる気がする。

それ自体は別に悪いことではない、と思う。ただ、10年前も思ったんだけど、これがすごいからこれをやるべきって声高に叫んでる人はその本質をあまり理解していないんじゃないかなぁと思うことが割りとあるということ。当時Javaと比較されていたC言語のサンプルは大体目も当てられないくらいひどいコードで、こんなひどいコードがJavaを使えばこんなにすっきり書けます、みたいな煽動していた気がする。最近の煽り記事もそんな感じの部分が見えなくもない。相手方が嫌いだからわざわざ不利になるような局面だけを選ぶとか。

結局全てはコードを書く人の技量によるわけで、関数型だからいいとか、オブジェクト指向だからいいということはないと思う。ただ、言語がサポートしていないから書き辛いというのがあるだけで。そうすると求められるのはつまるところ、マルチパラダイムな言語でいざとなればユーザーが言語自体を拡張できる言語ということになるんじゃないかな？*2

どうでもいいのだけど、こういう比較で必ずといっていいほど出てくる、LISPは関数型というの。 いくつか突っ込みどころがあるけど、とりあえず3大方言に限ればLISPは関数型ではないので引き合いに出すのを止めてほしいなぁ*3。関数型、オブジェクト指向、手続き型どれでもいけるマルチパラダイムなんだし、関数型って言われるとそんな風に使っていない自分の心が非常に痛むので。

*1: もし記事を読んで感銘を受けてしまったらこちらも読んでおいてほしい。http://anond.hatelabo.jp/20140410134501
*2: Common Lispはそんな言語なのに不思議と人気がない件
*3: これが言いたかっただけ

SRFI-10の紹介

(LISP Library 365参加エントリ)

SRFI-10は読み込み時にオブジェクトの構築を行う仕組みを提供するSRFIです。 Common Lispでいうところの#.を提供するものです。比較の項目を見るとCLとの違いが書いてあります。端的に言えばdefine-reader-ctorで登録しないと意味を成さないのでより粒度の高いコントロールが可能といった感じです。

使い方を見てみましょう。

;; Sagittarius doesn't support this SRFI
;; so the example code is for Gauche
(use srfi-10)
(define-reader-ctor 'cons cons)
'#,(cons 1 2)
;; -> (1 . 2)

これだけだと普通に(cons 1 2)と書くのと変わらないのですが、SRFIの例にあるように文字列から読み込む等の処理を書いたり、定数/リテラルのように扱うことができます。

さて、このSRFI結構便利そうに見えるのですがサポートしている処理系は以外にも少なそうです(参照)。 個人的にはR6RS以降のライブラリとの相性が悪いからだとも思うのですが、理由のところは定かではありません。(そもそもR6RSでは#,は別の意味があるので実装不可能ですが・・・) リーダーマクロをサポートしている処理系であればこれは要らないというのもあるかもしれません。Sagittariusでサポートしていない理由は後者が大きいです。

今回はSRFI-10を紹介しました。

Set, bag and comparator

I've implemented new final SRFI 114 (not sure if this is really final state since there was no call for final from author...). You may already know this SRFI is used in SRFI-113. it's like the relationship between SRFI-13 and SRFI-14. If this is related to other SRFI then next step would be implementing SRFI-113 (needs to be finalised first though).

So I've read a bit of SRFI-113 specification and realised that this is very generic and can be applied existing charset. However if I apply it to charset, it would be a big internal change. Even though there is still some time to be finalised, it's better to think about how I should implement.

The very first consition is this;

• Charset can't be moved to Scheme world

This is because it's used for builtin regular expression and moving it to Scheme world would be serious performance issue. Then implementing strategy would be like this;

• Make <set> class in C as base clasts
• <char-set> extends it
• Implement <set> constructor and some procedures in C
• Rewrite SRFI-14 implementation

Now there is already a problem with this strategy and which is comparator needs to be implemented in C. As I mentioned above I've already implemented SRFI-114 in Scheme. Implementing in Scheme was really easy but moving to C would be a bit hard. There are 2 considerations;

1. Performance
2. Co-operate with Scheme world

#1 is the biggest. The constructor of comparator takes 4 procedures, though 2 of them can be omitted, and created comparator is used for sets to determine whether or not the given elements are in the set. Thus, for charset I need to implement this behaviour in C. It's not possible of course but naive implementation causes performance issue since calling Scheme procedure from C costs a lot. There are at least 2 solution for this; one is calling procedure directly if it's subr (which is C world procedure). the other one is make comparator be able to have both C functions and Scheme procedures. The first one is used for hashtable and the latter one is used for ports. For builtin charset, the first one would be sufficient but not sure if anyone wants to extend it.

#2 is a bit less serious. It's related to class hierarchy. How should class hierarchy of <set> look like? The very naive but safe way would be like this;

• <abstract-set>
• <charset>
• <set>
• <integer-set>

So <charset> and <set> share the super class but it's not in direct relation. This is more like implementing the same interface. The other one would be like this;

• <set>
• <charset>
• <integer-set>

<set> is the base class of all set related classes. This is more direct. The class hierarchy affects the implementation. If I take the first one, then comparator doesn't have to be in C but second one. However for the first one, it would be very inconvenient/indirect to implement common set APIs. The goal for this merging is sharing the APIs. It doesn't have to support all SRFI-114 APIs but should be able to provide it with common APIs and can be applied for both sets.

Fortunately, there is still time to think about it but not much I think...

SRFI-9の紹介

(LISP Library 365参加エントリ)

SRFI-9はレコードの定義を行う最初のSRFIです。最初といったのはSRFIでのレコード型の導入は4つあり、SRFI-9はその最初のものだからです。

では使い方を見てみましょう。

(import (srfi :9))
(define-record-type <pare> (kons x y) pare?
  (x kar set-kar!)
  (y kdr))

(define p (kons 'a 'b))
;; for convenience, put like this but it's implementation dependent.
;; -> <kons 'a 'b> 

(kar p)
;; -> 'a

(kdr p)
;; -> 'b

(set-kar! p 'c)
;; unspecified

(kar p)
;; -> 'c

(set-kdr! p 'd)
;; -> unbound variable error

これで新しい型<pare>を定義可能します。この定義ではは2引数取るkonsを構築手続きとし、pare?を述語、kar及びkdrをアクセサ、set-kar!をフィールドxの変更手続きとして定義します。ちなみにフィールドyは変更不可能です。

LISP Library 365で到達するか分からないので、他のレコードSRFIを以下の列挙します。

• SRFI-57: Records
• SRFI-9で足りていない機能追加版です。SRFI-9とは上位互換になるはずです(未確認)
• SRFI-76: R6RS Records
• R6RSに入っているレコードです。SRFI自体は棄却されています。
• SRFI-99: ERR5RS Records
• R6RSのレコードは不満が多かったので、それを解消するために作られたSRFIです。R6RSのレコード機能はそのままにSRFI-9ともコンパチになっています。

ちなみに、R7RSに入ったレコードはSRFI-9のものそのままなので、このSRFIもそのまま標準に昇格されたSRFIの一つといえるかもしれません。

SRFI-8の紹介

(LISP Library 365参加エントリ)

 SRFI-8は多値の束縛を扱う構文receiveを提供します。R5RSでは多値はcall-with-valuesでのみ規定されています*1。

まずは、call-with-valuesで書いたものを見てみましょう。

(call-with-values (lambda () (values 1 2 3))
  (lambda (a b c) (+ a b c)))
;; => 6

個人的にcall-with-valuesの可読性*2は低いと思っているのですが、receiveを使うと以下のように書けます。

(receive (a b c) (values 1 2 3)
  (+ a b c))
;; => 6

同様の処理が多少見やすく書けます。もちろん好みによりますが。記述量の面で見てもlambdaを書かない分少なくなります。

今回はSRFI-8を紹介しました。

*1:逆にR6RS以降ではlet-values及びlet*-valuesが標準で入ったのでこのSRFIの出番は終わったともいえるかもしれません。
*2:thunkとクロージャの両方を必要とする手続きなので、処理系によっては性能も落ちます。

マクロ展開器

最近R6RS/R7RSのマクロのエッジケースを攻め込むような呟きをTwitterで目にして、ちと本格的になんとかしないとなぁという気持ちに駆り立てられている。Sagittariusのマクロ展開器は(恐らく*1)R6RSが要求しているものに完全には準拠していない。

現状でRacket(多分)、SagittariusとYpsilonを除くR6RS処理系はpsyntaxもしくはAndre van Tonderの展開器を使っていると思われる*2。どちらもR5RSの処理系にR6RSの要求するライブラリとsyntax-caseを追加するものである。一時期、Andre van Tonderの展開器をフロントエンドにしようかなぁと思ったりもしたのだが、自前でライブラリシステムを持っていると非常に相性が悪いので止めた経緯もあったりする。(R5RSでポータブルに作られている性質上、処理系が用意しているモジュールシステムのことは考えず、単一の名前空間上にリネームして全てを定義しているため)

 現状の実装で何が一番問題かと言えば、自分が今一理解していないとい点は除いて、マクロ展開とコンパイルが同時に行われているために展開時もしくはマクロコンパイル時に識別子とシンボルが混在していることだろう。これによって環境を参照する際に余計なことをしていて今一よく分からない状態になっている。二つの処理を一つのパスで行うことに利点もあるのだが、現状だと今一利点を享受できてない上に欠点の方が目立っている感がある。

とりあえず、利点と欠点をまとめて今後の方針を考えることにする。

【現状の方針】
<<利点>>

• オーバーヘッドが少ない(はず)
• syntax-caseは完全に分けて考えられているのでブートコードの生成時に依存が少ない

 <<欠点>>

• マクロ展開の結果が見辛い
• これはIFormからS式に戻すのを作ればいいだけだが
• マクロ展開時に識別子とシンボルが混在する

【マクロ展開フェーズを作る】
<<利点>>

• (うまくやれば)展開後の結果に識別子が減る
• 仕組み上無くせるわけではない
• ある程度マクロ展開が楽になる(はず)

<<欠点>>

• 展開器とコンパイラの二重実装
• オーバーヘッドが大きい(気がする)

どっこいどっこいな気がしないでもないし、展開フェーズを設けたからといって実装が完璧になる補償もない。う～ん、やはり当面は現状の方針でいった方がいい気がするな。

*1 エッジケースなのでこれが仕様の範囲なのか未定義なのかよく分かっていない
*2 Vicare/Ikarus/Iron Schemeはpsyntax、LarcenyはAndre van Tonder、Moshは両方。Guileは知らない。Biwa Schemeはsyntax-caseをサポートしてない。Chezはpsyntaxに近い何かじゃないかな。

SRFI-6の紹介

(LISP Library 365参加エントリ)

SRFI-6は基本的な文字列ポートを定義したものです。Ratinaleには1986年から使われているAPIとかかれているので歴史のあるものをSRFI化したものといえるかもしれません。

このSRFIで提供される機能は2つで、文字列をポートとして扱えるようにするものとポートを文字列バッファとして扱えるようにするものです。では基本的な使い方を見てみましょう。

(import (rnrs) (srfi :6))

;; string input port
(define in (open-input-string "SRFI-6 test :)"))
(get-string-all in)
;; -> "SRFI-6 test :)"

(define out (open-output-string))
(put-string out "Hello")
(get-output-string out)
;; -> "Hello"

(put-string out " SRFI-6!")
(get-output-string out)
;; -> "Hello SRFI-6!"

注意が必要なのはget-output-stringでしょう。この手続きは出力ポートに呼び出し時点までに溜め込まれた文字列を返しますが、溜め込まれた文字列をクリアしません。上記の例のように複数回の呼び出しでも同一の文字列が取得可能です。これはR6RSで既定されているopen-string-output-portが返す第2値とは異なる振る舞いをします。

ちなみに、このSRFIで定義されているAPIは全てそのままR7RSでも定義されているので、SRFIが標準に取り込まれた例の一つといえるかもしれません。

今回はSRFI-6を紹介しました。

偏見

TLCでAll-American Muslimという番組を見たのだが、これをみて自分の中にものすごい偏見があることに気付かされた。宗教的な偏見を持っているのというは自覚してたんだけど、今回発見したのは言語的な部分。

それは、アラビックな人たちが喋る英語は訛っているという偏見。

実はアラビックである必要はなくて、英語以外の言語を母語もしくはバイリンガルとして持っている人の英語は訛っているという感じ。理由はいうまでもないと思うんだけど、一応経験則から。例えばBBCの料理番組に出てくる中国系イギリス人とかインド系イギリス人はほぼ大抵訛っている。それ以外にも、アメリカ映画に出てくるアメリカ人ラビも訛ってるし、そんな感じ。

ちなみに、上記のTV番組はイスラム系アメリカ人生活のドキュメンタリーなんだけど、その中に出てくる典型的なイスラム系の女性がアメリカ英語を普通に喋ってて、なんか微妙な違和感を覚えてしまった。

json-toolsの紹介

(LISP Library 365参加エントリ)

今回は拙作json-toolsの紹介です。json-toolsはR6RSといくつかのSRFIのみで書かれたJSONを扱うためのライブラリです。SSAX及びJSONSelectの影響を受けて作られています。

インストール

R6RSの処理系でSRFI-1、13及び14をサポートしていれば何でもいいのですが、宣伝も兼ねてPegasusを使ってインストールしてみます。最新のHEADではURL指定でもインストール可能になっているので、その機能を使います。

% pegasus install json-install \
  -u https://raw.github.com/ktakashi/json-tools/master/formula/json-select.scm
-- Retrieving: https://github.com/ktakashi/json-tools/archive/master.zip
-- Extracting: json-tools-master/
-- Extracting: json-tools-master/README.md
-- Extracting: json-tools-master/ext/
-- Extracting: json-tools-master/ext/json.scm
-- Extracting: json-tools-master/ext/packrat.scm
-- Extracting: json-tools-master/ext/srfi/
-- Extracting: json-tools-master/ext/srfi/%3a64.sls
-- Extracting: json-tools-master/ext/srfi/%3a64/
-- Extracting: json-tools-master/ext/srfi/%3a64/testing.sls
-- Extracting: json-tools-master/formula/
-- Extracting: json-tools-master/formula/json-select.scm
-- Extracting: json-tools-master/src/
-- Extracting: json-tools-master/src/text/
-- Extracting: json-tools-master/src/text/json/
-- Extracting: json-tools-master/src/text/json/select.scm
-- Extracting: json-tools-master/src/text/json/select/
-- Extracting: json-tools-master/src/text/json/select/parser.scm
-- Extracting: json-tools-master/src/text/json/tools.scm
-- Extracting: json-tools-master/tests/
-- Extracting: json-tools-master/tests/parser.scm
-- Extracting: json-tools-master/tests/select.scm
-- Extracting: json-tools-master/tests/tools.scm
-- Installing: /usr/local/share/sagittarius/sitelib/src
-- Deleting working directory: json-install-HEAD/json-tools-master

インストールできました。他の処理系で使いたい場合は、Githubから直接クローンするかアーカイブをダウンロードするかしてください。

使ってみる

ここではメインであるJSONSelectを紹介します。JSONSelceとはCSSセレクタ風のクエリを用いてJSONから特定のノードを取り出すためのものです。

#!r6rs
(import (rnrs)
        (text json tools) 
        (text json select))

(define json '#(("name" . #(("first" . "Lloyd") ("last" . "Hilaiel")))
                ("favoriteColor" . "yellow")
                ("languagesSpoken"
                 #(("lang" . "Bulgarian") ("level" . "advanced"))
                 #(("lang" . "English")
                   ("level" . "native")
                   ("preferred" . #t))
                 #(("lang" . "Spanish") ("level" . "beginner")))
                ("seatingPreference" "window" "aisle")
                ("drinkPreference" "whiskey" "beer" "wine")
                ("weight" . 156)))

(json:nodeset->list ((json:select ".languagesSpoken") json))
#|
(("languagesSpoken"
  #(("lang" . "Bulgarian") ("level" . "advanced"))
  #(("lang" . "English")
    ("level" . "native")
    ("preferred" . #t))
  #(("lang" . "Spanish") ("level" . "beginner"))))
|#

(json:nodeset->list ((json:select ".languagesSpoken > .level") json))
#|
(("level" . "advanced")
 ("level" . "native")
 ("level" . "beginner"))
|#

json-toolsはChicken Scheme由来のjsonライブラリのJSONオブジェクト表現を使っています。ただ、そのままだと配列と連想配列を区別し辛かったりと不便な点もあるので、APIは渡されたオブジェクトを<json-node>に変換します。また、json-toolsでサポートしていAPIは基本ノードセットと呼ばれるオブジェクトを返します。そのため、実際に取り出されたS式JSONを得るにはjson:nodeset->list手続きを呼び出す必要があります。

さて、ここまで見て「あれ？」と思った方もいるのではないでしょうか？はい、json-toolsではオリジナルのJSONSelectとは多少違う結果を返します。具体的には連想配列のキーと値のペアもノードとしてカウントされるのでオリジナルでは値のみを返すようなクエリでも、ペアの方を返すようになっています。

今回は拙作のjson-toolsを紹介しました。このツールを使えばJOSN表現の直接リストやベクタを操作するということはなくなりそうです。

続々 コンパイラのバグ

いろいろ考えていたら、破壊的に環境を変更するものの今よりもはるかにすっきり書けることに気づいた。(ってか既に書き換えた)っで、次の一手として局所マクロを何とかしてしまおうという話。

とりあえず何をしたか。
問題になっていたのは内部defineとdefine-syntaxそれにlet(rec)-syntaxの3つを解決するために非常にややこしい方法でやっていたのだが、ざくっと以下のように変更した。

• bodyを解決するためにコンパイル時環境を2本用意。
• 初期値は同値
• 内部defineを見つけたらlvarを作って環境に放り込む(まだ値の初期化はしない)
• define-syntaxを見つけたらマクロにコンパイルして環境に放り込む
• let(rec)-syntaxを見つけたらマクロに変更してメタ環境のほうに放り込む

define-syntaxの解決がちとまずくて、相互参照があったり定義位置が下にあるものを上にあるものが参照していたりすると、マクロコンパイル時に展開してくれない。まぁ、マクロ展開時に普通に展開するだけなので今のところ特に問題にはしていない。

これは第一段階の変更として施したもので、処理の単純化と次への準備である。

次の一手として以下のことを考えている

• let(rec)-syntaxを見つけたらメタ環境を利用してbody部分を展開もしくは内部表現まで落とし込む
• その途中で見つけた内部define及びdefine-syntaxは位置が正しければもう一本の環境に破壊的に追加する
• 最終的に展開もしくは内部表現まで落としたものをマージする

問題になっているのはlet(rec)-syntaxで作られる仮想スコープが範囲を超えて参照可能になっているのがまずいのだからそれを何とかしてやろうという話。あまりひどいコードにするとメンテが大変なので(大変だった・・・)、綺麗に書いておきたいところ。

続 コンパイラのバグ

一つ前の投稿でコンパイラのバグについて書いた。週末を利用して先に展開するのを試してみたのだが見事に穴にはまったので記録しておく。

問題になったのは、マクロの展開とコンパイラの環境が密な関係にあることである。マクロ展開時にはコンパイラが集めた環境フレームを利用しているのだが、局所マクロを先に展開してしまうとそれを当てにした変数参照が動かなくなる。端的なコードしては以下のものがだめになる。

(define (bar)
  (let-syntax ((foo (syntax-rules () ((_ b) (when (< b 10) (bar))))))
    (define (buz b) (foo b))
    (buz 10)))

これが展開後には以下のようになる。

(define (bar)
  (define (buz b) (when (< #<id b> 10) (bar)))
  (buz 10))

問題になるのは識別子#<id b>で現在のマクロ展開器ならば識別子が持つ環境フレームに変数bが入って変数参照手続きがたどれるようになっている。しかし、ナイーブな実装で先にマクロだけを展開してしまうと生成された識別子は局所変数の参照を持たないフレームを持つことになり変数参照がうまくいかない。

これを解決するとすれば以下の2通りだろう。

1. 識別子が持つフレームが参照する変数を含んでいない場合には共有している環境以前のみを探してみつける
2. マクロ展開器が変数束縛を検知する

1は無駄に複雑になるだけなのでやるつもりはない。複雑なコードは理解を阻害しバグを混入させるだけなのだ。(既に複雑怪奇になっていて自分でも全てのパターンを列挙できないようになっている・・・orz)
2は環境フレームの同値性に頼っているコードが山ほどあるので事実上不可能。やれなくはないが、複雑怪奇に(ry
となるとこの方向性で解決するには、全てのマクロをあらかじめ展開してしまうというR6RSが要求している方針を採らざるを得なくなる。マクロの展開とコンパイルを同時にやるというのは不可能ではない(はずな)のだが、現状のコンパイラは中間表現にGauche由来のIFormを使っているためS式との混在がきつい。

となるともう一つの方法である現状のコードを拡張する方向だが、これはこれでまたバグの温床になりそうな雰囲気が既に漂っているのでうれしくない。ちょっと方針に以下の項目も入れる方向で検討することにする。

• IFormを捨てる
• 大幅なコンパイラの変更が必要
• マクロ展開フェーズを設ける
• 重複コードをどうするか？

場当たり的な対応ではバグを埋め込むだけなので根本から解決する必要がありそうではある。

コンパイラのバグ

マクロのバグを直していて以下のようなコンパイラのバグにぶち当たった。

(let ()
  (letrec-syntax ((a (syntax-rules () ((_) 'foo)))))
  (print (a)))
;; -> prints 'foo

火を見るよりも明らかなバグである。なぜこんな挙動になるかといえば、let(rec)-syntaxはマクロ展開後にbeginになるというのに起因している。Sagittariusではマクロ展開フェーズを内部的に持っていないので、コンパイラがマクロを見つけると展開するという仕組みになっている。そして、それを実現するためにlet(rec)-syntaxで束縛されたマクロはコンパイル時環境を破壊的に拡張するという方法をとっている。これが問題なのだ。

上記の場合コンパイル時環境は以下のように推移する

(let () ...)         ;; (()) empty
(letrec-syntax ...)  ;; ((a . <macro>)) *1
(print (a))          ;; ((a . <macro>)) *2

本来であれば*1で足されたマクロは*2の段階では見えなくなっていなければならないが、そんなこともないのが問題になっている。解決方法はいくつかあると思っていて、ぱっと思いつくだけで以下のものがある。

1.  let(rec)-syntaxで束縛したマクロを先に展開してしまう
2. define-syntaxのみを特別視してlet(rec)-syntaxでは破壊的に環境を変更しないようにする

1は効率がかなり落ち、2はかなりトリッキーなコードになるとどちらも一長一短である。ただ、2は現状の延長線上にあるので実装としては楽かもしれない。

読書感想文(All You Need Is Kill)

となりのヤングジャンプとヤングジャンプで連載されてる漫画の原作。漫画読んで原作を読みたくなったのはかなり久しぶりである。５月に日本に帰るのでそのときに買えばよかったような気もするが、はやる気持ちは１年前にもらったギフトカードを使ってAmazon.deでの英語版の購入を後押しした形になる。

核心には触れない形で書くつもりだが、うっかりネタ晴らししてしまっていてもご容赦いただきたい。

とりあえず読んだ感想としては買って損はなかったになる。 日本なら書籍でも600円で買えるのだが、英語版は€10とほぼ2倍の値段である。日本で買える環境にあるなら日本語版をお勧めする。英語の勉強用？多分やめた方がいい。Yonabaruの会話文がえらく訛っているし、そこそこ難しい単語(1ページに1は知らん単語があった)が出てくるので楽しめないと思う。ただ、訳者がよかったのか、元がいいのか、はたまた両方なのかは分からないが個人的には読みやすかったという印象ではある。多分、SiFi系の小説にありがちなこてこての背景説明が少なかったというのもあるのだろう。


Wikipediaのページにある登場人物の項目でShastaがでかでかと載っているのだが、出番は少なめ。眼鏡オタク娘好きにはものたりないかもしれない。ShastaよりYonabaruの方がよっぽど登場回数多いのに載っていないのは何故だ？

Rita Vrataskiという名前からロシア系なのかなと勝手に思っていたのだが実はアメリカ、イリノイ州出身という。Ritaって名前にアメリカ人という印象がないのでいろいろやられた感はある。このページによると0.204%程度らしいのでそもそも珍しいのだろう。読み飛ばしたのかもしれないのだが、Ritaの本当の苗字ってなんだったんだろう？

ギタイ(Mimic)の命名由来も出てこなかった気がする。作中では膨らんだ蛙(bloated frog)と表現されていたが、漫画版ではそんな風には見えない。彼らが人間と戦争している理由に関しては、個人的にだが、ちょっとチープな感じがした。SiFiなのでまぁありなんだろうけど、唐突だなぁ感が拭えなかった。

今年の6月に映画がでる。題はEdge of Tomorrow。なぜ変えたし？Tom CruiseがKiriya Keiji役(役名William "Bill" Cage) なのだがどう見ても20台前半の新兵に見えない件。Rita Vrataski役のEmily Bluntもどう見ても22歳(実際には多分2つか3つ若い設定)に見えない件。原作は舞台日本で主人公日本人なんだけど、そこはアメリカ映画(Warner Brosってハリウッド？)、全部アメリカになってる。Trailer見ると面白そうではあるので見に行くかもしれない。

あまり書くとネタ晴らししそうなのでこれくらいにしておく。

R6RSのマクロ展開フェーズ

日本語で解説してる記事があまりにも少ないのと、これを毛嫌いしてる人が多いので何か書いてみる。随分前にチラッと書いてたりするが、単なる調査用の記事だったのである程度まじめに解説する。英語だとこれが詳しい。

はじめに、なぜフェーズなどというものが必要か？
R6RSでは低レベルマクロであるsyntax-caseがある。これはdefine-syntax内で内部定義を可能にする。マクロとはコンパイラがコンパイル時に(もしくはそれ以前)に定義に従って式を別の式に展開するのだが、以下のようにマクロ定義内に別のマクロ定義があるとそのマクロは何時展開するのかということが問題になる。

#!r6rs
(import (for (rnrs) run expand))

(define-syntax foo
  (lambda (x)
    (define-syntax bar
      (syntax-rules ()
        ((_) #''foofoo)))
    (syntax-case x ()
      ((_)
       (with-syntax ((name (bar)))
         #'name)))))
(foo) ;; -> foofoo

これを解決するのがフェーズというわけである。マクロbarはマクロfooが展開される前に展開される必要がある。ではbar内で使われているsyntax-rules等の名前を解決する必要がある。フェーズとはその名前解決が行われる段階を明示的に指定したものと思えばよい。runとexpandが名前つきで提供されているが、これらは(meta 0)と(meta 1)の別名である。

フェーズとはマクロ内マクロで使われるものである
間違いを恐れずに言い切ってしまえば、フェーズとは上記の場合にのみ考慮に入れる必要があるものだ。もちろん他のライブラリで定義されたマクロもこれに含まれる。

メタレベルの必要性
R6RSのマクロフェーズにはメタレベルなるものがある。デフォルトのrunとexpandで足りない場合はユーザが(meta 2)等適当に指定することができる。 これは本当に必要なのか？結論を言えば必要である。メタレベルはマクロ内マクロが多段になると必要になる。以下のコードがそうだ。

#!r6rs
(import (for (rnrs) run expand (meta 2)))

(define-syntax meta0
  (lambda (x)
    (define-syntax meta1
      (lambda (x)
        (define-syntax meta2
          (lambda (x)
            (syntax-case x ()
              ((_) #'(generate-temporaries '(a))))))
        (syntax-case x ()
          ((_) 
           (with-syntax (((name) (meta2)))
             #'#'name)))))
    (define (gen-name) (meta1))
    (syntax-case x ()
      ((_)
       (with-syntax ((name (gen-name)))
         #'(display 'name))))))


(meta0) ;; -> prints temporary symbol

見た目に分かりやすいようにマクロの名前は各メタレベルにしてある。こんなコード書くやついねぇよ！と思うかもしれないが、例示できるコードレベルで出るということは必ず誰かは使うということである。明示的か暗黙的にかは別にしてもだ。

R7RSではどうなるか？
R7RSもlargeではexplicit renamingが取り込まれる方向に進むと思われるのだが、まだ議論すら始まっていない状態なのでなんとも言えない。ただ、フェーズは毛嫌いしてる人が多い(自分含む、要出展)のとR7RSが提供するdefine-libraryにはフェーズ指定をするキーワードは提供されていないので、暗黙の内に解決する方向に行くのではないかと思っている。

SRFI-5の紹介

(LISP Library 365参加エントリ)

SRFI-5はletの拡張SRFIです。正直使ったことない上に、Sagittariusでは0.5.2になって(ほぼこの紹介記事を書くためだけに)サポートされたものだったりします。なので、ちょっと触ってみたレベルで紹介記事を書きます。

このSRFIは既存のlet、特に名前つきletの拡張を行います。具体的には新しいフォームとオプショナル引数を受け付けるようになります。具体的には名前付きletが以下のよう

(import (srfi :5))

(let (loop (i 0))
  (when (< i 10)
    (display i) (newline)
    (loop (+ i 1))))

loopの位置が束縛の先頭にはいるという感じです。(正直、僕にはエディタの恩恵が受けづらくなるだけに見えるのですが・・・)

オプショナル引数は以下のようにして受け取ります。

(import (srfi :5))

(let (loop (x 0) (y 1) . (z 2 3 4))
  (if (list? x) 
      (list x y z)
      (loop z x y)))

オプショナル引数は複数個の値がリストにパックされます。また通常のletフォームもサポートされるので、通常の名前付きlet+オプショナル引数という感じでも書くことができます。

実際にどういう仕組みで動いているかというのは、マクロの展開形を見ると分かります。

((letrec ((loop (lambda (x y . z) 
                  (if (list? x) 
                      (list x y z) 
                      (loop z x y))))) 
   loop) 0 1 2 3 4)

納得の展開結果ではないでしょうか？

とりあえず触った感想なのですが、名前付きletにオプショナル引数がほしいという場合は使えるのではないでしょうか。個人的にはそういったケースは非常に少ない(もしくはない)ので多少適当な紹介になってしまった感があります。

Sagittarius Scheme 0.5.1リリース

Sagittarius Scheme 0.5.1がリリースされました。今回のリリースはメンテナンスリリースです。

修正された不具合

• マクロの可視性に関する不具合が修正されました
• datum->syntaxによって生成されたシンボルが非可視になる不具合が修正されました
• いくつかのポートに対する手続きに閉じたポートを与えるとSEGVは発生する不具合が修正されました
• 不正なdefineが例外を挙げない不具合が修正されました
• (tlv)ライブラリで長さのエンコーディングに対する不具合が修正されました
• コンパイラにcircular listを渡すと無限ループに陥る不具合が修正されました
• formatにカスタム文字ポートを渡すとSEGVが発生する不具合が修正されました

新たに追加された機能

• R7RSスタイルのSRFIライブラリがサポートされました。例：(srfi 1)
• SRFI-5が追加されました
• 局所メソッドフォームlet-methodが追加されました
• R6RSのレコードが組込みCLOSに統合されました

改善点

• quasiquoteが可能であれば定数を生成するようになりました
• コンパイラが可能であればコンパイル時に手続きの呼び出しをするようになりました

新たにサポートされた環境

• OpenBSDでのビルドが可能になりました

Introduction of JSON tools for Scheme

I'm writing a library which can query JSON. It's still under development state but a bit of sample code wouldn't hurt so let me introduce it.

The repository is here, json-tools and handling JSON structure must be one of the Chicken Scheme egg's library json format. (I've ported it for R6RS Scheme implementations, it's in the repository as well.)

The library consists 2 parts one is JSON tools and the other one is JSON query which is based on the JSONSelect.

JSON Tools

This part of the library is highly inspired by SXPath. There are bunch of basic selectors which can be used by querying libraries. Following piece of code describe the flavour of this part.

(import (rnrs) (text json tools))

(define json '#(("name" . #(("first" . "Lloyd") ("last" . "Hilaiel")))
                ("favoriteColor" . "yellow")
                ("languagesSpoken"
                 #(("lang" . "Bulgarian") ("level" . "advanced"))
                 #(("lang" . "English")
                   ("level" . "native")
                   ("preferred" . #t))
                 #(("lang" . "Spanish") ("level" . "beginner")))
                ("seatingPreference" "window" "aisle")
                ("drinkPreference" "whiskey" "beer" "wine")
                ("weight" . 156)))

((json:filter (lambda (node)
  ;; The given node can be other type and
  ;; this piece of code may raise an error
  ;; but for above structure this works :)
  (equal? "name" (json:map-entry-key node))))
 (json:child-nodes json))
;; -> <json:nodeset>

All JSON selectors return JSON nodeset type which contains sets of JSON node. Followings are the JSON node types;

• JSON map
• JSON map entry
• JSON array
• JSON string
• JSON number
• JSON boolean
• JSON null

All types are sub type of JSON node. The reason why I introduced them is that there was no way to tell the difference between array and map entry which contains array. To avoid ambiguous results, I needed to do it.

To retrieve the result set as S-expression, you can simply call the `json:nodeset->list` procedure like this;

(json:nodeset->list ((json:filter (lambda (node)
                                    (equal? "name" (json:map-entry-key node))))
                     (json:child-nodes json1)))
;; --> (("name" . #(("first" . "Lloyd") ("last" . "Hilaiel"))))

Not sure if the procedure name is proper. (I also though `json:nodeset->sexp`.) To casual use, `json:filter`, `json:child-nodes`, `json:child-nodes-as-list`, `json:child` or `json:child-as-list` are easy to use. The rest of selectors are a bit tricky.

JSON Select

This part of the library is for usability. You can use query language to select  particular nodes from JSON. The example use is like this;

(import (text json select))

;; use the same JSON structure defined above
((json:select ".languagesSpoken") json)
;; --> <json:nodeset>

(json:nodeset->list ((json:select ".languagesSpoken") json))
;; --> '(("languagesSpoken"
;;        #(("lang" . "Bulgarian") ("level" . "advanced"))
;;        #(("lang" . "English")
;;          ("level" . "native")
;;          ("preferred" . #t))
;;        #(("lang" . "Spanish") ("level" . "beginner"))))

The returning value is JSON nodeset the same as tools. So again to retrieve the S-exp result, you need to call the procedure `json:nodeset->list`. Currently, not all query language are implemented but it would be a matter of time.

As I mentioned before, the state is still under development so your opinions or testing results are very welcome :) Of course, your pull requests are much appreciated :)