Syntax highlighter

2014-03-29

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とクロージャの両方を必要とする手続きなので、処理系によっては性能も落ちます。

2014-03-24

マクロ展開器

最近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に近い何かじゃないかな。

2014-03-21

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を紹介しました。

2014-03-17

偏見

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

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

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

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

2014-03-07

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表現の直接リストやベクタを操作するということはなくなりそうです。

2014-03-04

続々 コンパイラのバグ

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

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

2014-03-03

続 コンパイラのバグ

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

問題になったのは、マクロの展開とコンパイラの環境が密な関係にあることである。マクロ展開時にはコンパイラが集めた環境フレームを利用しているのだが、局所マクロを先に展開してしまうとそれを当てにした変数参照が動かなくなる。端的なコードしては以下のものがだめになる。
(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を捨てる
    • 大幅なコンパイラの変更が必要
  • マクロ展開フェーズを設ける
    • 重複コードをどうするか?
場当たり的な対応ではバグを埋め込むだけなので根本から解決する必要がありそうではある。

2014-03-01

コンパイラのバグ

マクロのバグを直していて以下のようなコンパイラのバグにぶち当たった。
(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は現状の延長線上にあるので実装としては楽かもしれない。