Let's start Scheme

2014-02-28

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

となりのヤングジャンプとヤングジャンプで連載されてる漫画の原作。漫画読んで原作を読みたくなったのはかなり久しぶりである。5月に日本に帰るのでそのときに買えばよかったような気もするが、はやる気持ちは1年前にもらったギフトカードを使って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見ると面白そうではあるので見に行くかもしれない。

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

2014-02-26

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にはフェーズ指定をするキーワードは提供されていないので、暗黙の内に解決する方向に行くのではないかと思っている。

2014-02-16

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にオプショナル引数がほしいという場合は使えるのではないでしょうか。個人的にはそういったケースは非常に少ない(もしくはない)ので多少適当な紹介になってしまった感があります。

2014-02-14

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でのビルドが可能になりました

2014-02-13

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 :)

2014-02-10

Integrated R6RS record to CLOS

I have made a sort of huge change for Sagittarius in these couple of days and that is now R6RS record can be used with generic functions. So let me show what's the exact change for this.

Sagittarius had 2 type systems, one is CLOS and other one is R6RS record and these didn't have any compatibility. So following code were invalid.
(import (rnrs) (clos user))
(define-record-type (pare kons pare?)
  (fields (mutable x kar set-kar!)
          (immutable y kdr)))

(define-method write-object ((p pare) out) 
  (format out "#<pare ~s:~s>" (kar p) (kdr p)))

(print (kons 1 2))
This was because R6RS record didn't create CLOS class but own record type. I was thinking this is very inconvenient and made me not to use R6RS record. So I have made the change and now above code works as I expect.

Followings are what I've changed internally so may not be so interesting.

[Slot ordering and shadowing]
I needed to change computed slot order of a class from subclass slots followed by super-class slots to super-class slots followed by subclass slots. And to make R6RS record spec satisfied, made not to shadow any duplicated slots. Following code describes a lot;
(import (rnrs) (clos user) (clos core))

(define-class <a> () (a b))
(define-class <b> (<a>) (c d))
(define-class <c> (<a>) (a c d))

(print (class-slots <b>))
;; ((c) (d) (a) (b)) : 0.5.0 or before
;; ((a) (b) (c) (d)) : current

(print (class-slots <c>))
;; ((a) (c) (d) (b))     : 0.5.0 or before
;; ((a) (b) (a) (c) (d)) :current
So basically no eliminating slots and different order. Then I had immediately noticed the problem that this breaks slot accessing. For example, refering <c>'s slot 'a' may return <b>'s 'a' slot value. The solution was very easy. The bottom most class's slots need to be shown first this means searching reverse order was sufficient.

The benefit of this change is big. Accessing slot with class is now always returns proper position of slot. Slot accessor contains index of the slot position and the change made this position always the same no matter how many you extend classes. For above example, position of class <a>'s slot 'a' is always 0 and before this wasn't always 0 (obviously...). Additionally, slot accessor also contains the class information that indicates on which class it's defined.

[Defining procedual layer in Scheme]
I have made a small footprint for this integration with CLOS. And based on this code, I've implemented procedural layer in Scheme world so that those ugly C code for record could be removed.

The Scheme implementation creates a CLOS class per record type descriptor(RTD) and set it to RTD and visa versa. This could save me from a lot of troubles such as refering record constructor descriptor (RCD) from record type. (I think there is a better solution but I was lazy.) There is a small problem with current Scheme code, that is it is impossible to create more than 1 record constructor descriptor from one record type descriptor. I may fix this if it will be a problem but highly doubt it.

[Record type meta class]
To distinguish between normal CLOS instance and record instance, I needed to create an additional meta class for it. However, it was pain in the ass to create meta class in C level so I decided to extend current class structure to have RTD and RCD fields and not to show the slot in but . This makes memory efficiency slightly bad (2 words) but I don't think it's a big deal.

SRFI-4の紹介

(LISP Library 365参加エントリ)

SRFI-4はSchemeで整数データ、及び浮動小数点専用ベクタを扱うSRFIです。 用意されているデータ型としては、u8、s8、u16、s16、u32、s32、u64、s64、f32及びf64です。最後二つ以外は数値の整数ビット+符号を表し、f32とf64は浮動小数点数のビット数を表します。

それぞれのデータ型に対して以下の処理が定義されています。(SRFIに習ってデータ型をTAGと表示しています。)
  • (TAGvector? o)
  • (make-TAGvector n [ TAGvalue ])
  • (TAGvector TAGvalue ...)
  • (TAGvector-length TAGvect)
  • (TAGvector-ref TAGvect i)
  • (TAGvector-set! TAGvect i TAGvalue)
  • (TAGvector->list TAGvect)
  • (list->TAGvector TAGlist)
また、それぞれのデータ型に対してのリーダマクロも定義されています。

具体的な使用例を見てみましょう。動作確認処理系はSagittarius 0.5.0です。
#!read-macro=srfi/:4
(import (srfi :4))

(define s8 #s8(0 -1 2 -3 4))

(s8vector-ref s8 1)           ;; => -1
(s8vector-set! s8 0 5)        ;; => unspecified
(list->s8vector '(1 2 3 4 5)) ;; => #s8(1 2 3 4 5)
(s8vector->list s8)           ;; => #s8(5 -1 2 -3 4)
R6RS以降バイトベクタが基本データ型に入ったのでこのSRFIの存在意義が薄れた感はありますが、R5RSで書かれたスクリプト等に使われている場合があるので知っておいても損はないかと思います。

こんなSRFIないの?的なリクエストをお待ちしてます。(順番どおりにやると使用頻度低めのSRFIが続くのでw)

2014-02-06

マクロのバグを非常にひどい方法で解決したのでメモ

どこかにメモしておかないと忘れるw

一つ前の記事でaifのitがマクロにくるまれるとうまく参照できないというバグの話をしたが、一応直したのでメモ(というか、FIXME的な何か・・・)。

どうしたか。
問題はマクロ展開時に生成される識別子の環境が不十分なために参照する際に大雑把にしか(というと語弊があるが)識別ができなかったこと。ただ根本を解決せず搦め手で直してしまった。
このit識別子を参照可能にすると、syntax-rules内でネストした識別子の誤参照が置き、不可能にすると、まぁitが見えないという状況に置かれたので、とりあえずコンパイル時環境に何が入っていて何を見つけないといけないかを大まかに見てみたら、参照可能にした場合は同一の識別子が後ろにあるにもかかわらず一つ二つ前のものを誤参照していた。そこで、一度全部環境を舐めてから見つからなかった場合にそれっぽいものを返すという荒業を使うことにしている。もちろんバグの匂いしかしないw

根本的には全く解決されていないので、正しくは環境(恐らく)テンプレート変数のコピーをする際にオリジナルの環境をそのまま使うのではなく、何かしらマークを入れてやり識別可能にするという方法を取るべきなのだろう。ただ、何をどうすればいいのかさっぱり分かっていないので、どうしたものかという感じ。

2014-02-03

Schemeのマクロにおける変数参照についてのメモ

自分の考えをまとめるためのメモ。主にSagittariusでの実装の話。

Schemeは変数のシャドウイングがある。そのためコンパイラが適切に変数を参照するためにはそれがどこで束縛されたかを知っている必要がある。これだけなら環境はスタックのように束縛された変数を持っておき、上から順に探索すればいいだけなのだが、問題になるのはhygenic macroで束縛された変数(便宜上テンプレート変数と呼ぶ)である。

例えば以下のケース
(define-syntax test
  (syntax-rules ()
    ((_ a b)
     (let ((a a))
       (+ a b)))))
(let ((a 1) (b 2)) (test b a))
というのは、3を返す必要がある。(今一いい例ではないかもしれないが)上記の例ではaがテンプレート変数ということになる。Sagittariusではテンプレート変数は基本的にリネームされ、実際に渡される式とは別の扱いになっている。リネームの再に現在のマクロ環境が用いられてリネームされるので生成される識別子aはこの場合は空の環境を持ったものになる。(実際にはマクロであることを識別するためのマークと定義されたライブラリの情報が入る)

この辺りまでならまだ混乱は少ないのだがR6RSにはdatum->syntaxがある。これが頭の痛い問題で、syntax-rulesでは不可能な「識別子が定義される環境を任意の場所に指定する」ことができる。例えば、CLで有名なaifは以下のようになる。
(define-syntax aif
  (lambda (x)
    (syntax-case x ()
      ((aif expr then else)
       (with-syntax ((it (datum->syntax #'aif 'it)))
         #'(let ((it expr))
             (if it then else)))))))
(aif (car '(a)) it #f) ;; => a
上記の例ではitはマクロaifが定義された環境(つまり空)を持つ識別子となる。そうすることでaif式内で参照されるitはあたかもグローバルに束縛された変数を参照するような挙動をする。しかし、現状の実装では以下のような場合に上手く動かない。
(define-syntax wrap
  (syntax-rules ()
    ((_)
     (aif 'ok it #f))))
(wrap) ;;=> should return ok but raises an error
一段マクロをかますことで、itがテンプレート変数に変更され環境が変わるからである。本来であればitは大域で定義された変数と同様な動きをするべきだが、そうなっていない。(wrapが局所で定義されたらどうするんだという話もあるがとりあえず放置・・・)

細かいケースを上げたらきりがないのだが、本題としてはどの場合にどの識別子を同一のものとみなすかということである。例えば同じ環境を保持しているのか、コンパイラ環境に格納された変数が、ターゲットの変数と環境を共有していればいいのか、とかそんな感じである。現状の実装ではマクロの定義時と展開時にリネームが走るのだが、その部分もおそらく見直す必要がある。余計な情報を付加しているか、または逆に情報の欠落が起きている可能性があり変数参照時に正しく参照できていないからである。

マクロのバグを踏むたびに既存の展開器を使っておけばよかったなぁと思ったりもするが、それだと面白くないというのもあったりで複雑な気分である。