2015-01-26

JSONパーサの性能改善

現状ではJSONパーサは(packrat)を用いて記述されている。(packrat)はBNFに近い形でパーサが記述できるという点においてはよくできているのだが、性能という点ではあまり(かなり)よろしくない。特にJSON程度の文法であれば、専用のパーサを書くのもそんなに面倒ではないのだが、いかんせん自分があまりタイトに使わないのでとりあえず気にしないでいた。

っで、以下のツイートと性能評価までしていただいた記事が昨日(だったかな?)でてきた。




JSON パーサの性能評価 - 主題のない日記

Guile用のライブラリをR6RS修正したものとの比較で30倍程度の差があるようである。 まぁ、性能に関して遅い方がいいなどという要件は見たことがないので、ここはえいやっとやってしまおうということにした。

せっかく書き直すのだから、後で多少色を付けやすいように(text json)というライブラリを作り、(json)はそれを使用するという形にすることにした。まぁ、実装はゴリゴリと地道にパーサを書くだけなので省略。

っで、ベンチを取る。上記の記事で使用したデータは非公開のようなので、Twitterから適当にJSONデータを取得。(Sagittarius-net-twitterを使用した。これももう少しTwitter API v1.1に対応しないとなぁ・・・) 25KBと多少小さめだがまぁいいだろう。ベンチマークには以下のスクリプトを使用。
(import (rnrs) 
 (prefix (text json) new:)
 (prefix (json) old:)
 (time))

(define (run-bench json-read)
  (call-with-input-file "bench.json"
    (lambda (in)
      (time (json-read in)))))

(run-bench old:json-read)
(run-bench new:json-read)
以下が結果:
;;  (json-read in)
;;  0.815046 real    1.310000 user    0.000000 sys

;;  (json-read in)
;;  0.032002 real    0.031000 user    0.000000 sys
25倍程度の高速化になったみたいである。まぁ、これくらい高速になるのであれば置き換えてもいいかな。

2015-01-23

Implementing non portable syntax-case

There are 2 portable syntax-case implementations, psyntax and SRFI-72. Both can be run on R5RS implementations and provide not only syntax-case but also library mechanism defined in R6RS. It is very reasonable to have such a huge mechanism instead of just providing syntax-case only because bunch of things pretty much related with syntax-case (or more precisely procedural macro and library system).

You can use it as your expander however if an implementation already has own module system then it might not a good idea to use it as it is. As my understanding, at least SRFI-72, expands all bindings to only one namespace which makes the namespace or symbol table really huge and may impacts memory usage. And again, this is reasonable decision because R5RS doesn't provide module system and if you need to write portable library then everything needs to be defined in one single namespace.

Since Sagittarius is using none of them but implementing own syntax-case expander and library system, it wouldn't hurt to write an article for this. Plus, apart from my lack of searching skill, I couldn't find any article mentioning how to implement it, other then couple of papers (could be that's enough for everybody...), I thought I can contaminate the search engine result a bit more with mine. This is basically my memo before I forget everything.

WARNING: The following sections may or may not contain mistakes. DO NOT TRUST :P

How to implement syntax-case on top of own library system


Implementing syntax-case is not an easy task to do especially in a portable way. The 2 portable implementation provides syntax-case expander and library system. This is because R5RS doesn't provide module system and R6RS procedual macros require phasing to resolve from where the bindings are imported during macro evaluation (not expansion) period. However if an implementations already has own library system, it is better to implement syntax-case on top of it so that the implementations can reuse the existing libraries without modifying anything. The following sections describe how Sagittarius' macro expander is implemented on top of own library system.

Pre-requirements


On Sagittarius, 2 Scheme objects were introduced for syntax-case, identifiers and macros. Identifier has the following slots:
  • name: raw name of the identifier, symbol
  • envs: compiler environment frame, alist
  • library: a library where this identifier belongs, library object
  • identify: a unique symbol generated per macro expansion, uninterned symbol
  • pending: a flag that indicates if the identifier is a template variable or not, boolean
The last slot, pending, is used to make an identifier unique so that evaluating template variable makes unique identifier each time. This may not needed if macro expander itself generates unique bindings like SRFI-72. However doing so may cause symbol explosion so I decided to introduce this. Internally, macro expansion is done by renaming symbols or identifiers. Each expansion remembers which symbol or identifier renamed to which so that if a symbol is renamed to an identifier twice then it will be the same object in sense of eq?.

Macro has the followings slots:
  • transformer: a procedure which expands given expassion
  • envs: a compile time environment when this macro is bound, vector
Whenever a macro is invoked, then VM swaps current macro environment with the one the macro has. And new identity is generated to rename symbols or identifier properly. Swapped environment and identity are restored when the transformer returns.

Renaming


Renaming, on this context, means converting symbol or identifier to new identifier. There are 2 rules when renaming is invoked:
  • Symbols are renamed to be global identifier (passing null environment frame)
  • Not all identifiers are renamed (pattern variables, non local variables, etc.)
The idea of the first rules is inspired by SRFI-72 implementation which very first step is wrap all symbols to identifiers with empty environment. To avoid unnecessary memory allocation, I've decided to delay this step as late as possible. Thus raw symbols and identifiers created with empty environment are treated the same.

The second one is preservation. For example, local variables need to be preserved so that it can be referred. The same goes pattern variable and pending identifier which the pending slot contains #t.

Renaming is done 3 times in total. The first one is during syntax-case compilation. In this step, both pattern and template are renamed. Then the pattern variables are stored in compile time environment. The second one is during syntax compilation. In this step, only raw symbols are renamed to identifiers. The last one is during expansion. The target template needs to be renamed so that it can generate fresh identifier each time. After the expansion, raw symbols are also renamed if there is. The raw symbol conversion is required because of R6RS procedures. (actually not needed if I don't care about compliance but unfortunately I do.)

Identifier equivalence


Comparing identifiers are crucial. R6RS defines 2 types of comparison procedures, bound-identifier=? and free-identifier=?. On Sagittarius, returning #t from bound-identifier=? means given 2 identifiers have the same identities and libraries. Thus they are generated on the same macro expansion phase. Free identifiers are pretty much simple, it just checks if the given 2 identifiers are bound to the same value. This also means different named identifier can be #t in sense of free-identifier=?. (R6RS allows implementations to behave like this.)

Local variables are also simply looked up. Compiler just needs to compare variables in sense of bound-identifier=?. Because of the trick described above section, the same source identifiers are renamed to the same object. This makes look up process simply and easy. Even though the process is simple, however, comparing identifier and symbol needs special treatment. In basic concept, raw symbols and global identifiers are the same. The special treatment is when an identifier contains the same environment frame as current compile time environment frame. Variable look up is done per frame and whenever an identifier is generated by macro expander, then it contains environment frame of that moment. Following is the example case:
(import (rnrs))

(let ((a 1))
  (let-syntax ((foo (syntax-rules () ((_) a))))
    (let ((a 2))
      (+ (foo) a))))
The macro foo contains the first a which will be an identifier when it's expanded. However the compiler environment frame contains raw symbol a. So to look up it properly when the identifier contains the same frame, then it needs to compare the target as either raw symbol or global identifier.

Pit falls


Fresh template variables: R6RS requires the following template variable to be unique:
(import (rnrs))

(define-syntax define-dummy
  (syntax-rules ()
    ((_)
     (define dummy))))

dummy
;; -> unbound variable error
As I described above section, SRFI-72 resolves this by renaming all bindings to unique symbols. However this might be overkill if implementations already have its module system or namespace. A symbol can have different bindings if module system allows. On Sagittarius, a binding uses the raw symbol name of an identifier. Thus without any treatment, above piece of code can be run without problem. To resolve this, I introduced pending slot. The syntax which creates bindings such as define, then it always swap raw symbol name of pending identifier to uninterned symbol so that the identifier can not be seen out side of the template where it's defined. This is rather ugly solution, so I want something better.

Pattern variables: pattern variables are also identifiers except its environment frame is not a valid compiler environment frame. This is needed because pattern variables need to be preserved. However preserving pattern variable made incompatibility of portable implementations. The particular issue is following:
(import (rnrs))

(define-syntax foo
  (syntax-rules ()
    ((_ x)
     (let-syntax ((bar (syntax-rules (x)
                         ((_ a) #t)
                         ((_ b) #f))))
       (bar b)))))

(foo a)
;; -> #f
The pattern variable a is not renamed so the first pattern of bar won't match (because the pattern variable a and input variable a are not the same in sense of free-identifier=?). I believe this behaviour is still R6RS compliant since it doesn't specify this type of pattern variable renaming (if I read it correctly). To avoid this, the following is one of the solution:
(import (rnrs))

(define-syntax foo
  (syntax-rules ()
    ((_ x)
     (let-syntax ((a (syntax-rules ())))
       (let-syntax ((bar (syntax-rules (x)
                           ((_ a) #t)
                           ((_ b) #f))))
         (bar b))))))

(foo a)
;; -> #t
This behaviour is, again if I read R6RS correctly, specified in R6RS. In this case, pattern variables need to be renamed.

Conclusion


Using portable implementations is much easier then implementing own syntax-case. As long as implementations don't have own module system, it is better to use it. I just wanted to show at least there is a way not to use portable implementations. If you can integrate syntax-case on your own implementation, then core part can be really small (less than 1000 LoC in my case).

味園ユニバース(La La La at Rock Bottom)

ロッテルダムでやっている国際映画フェスティバルで日本語の映画がやるということで、同僚(もうすぐ元になるが)と映画を見に行った。詳細はこちら(オランダ語):味園ユニバース(La La La at Rock Bottom)

以下はネタばれを含むので見てない方、これから見ようと思っている方は読まない方がいいかも。

2015-01-18

SRFIを書く/採用する理由

まだドラフトにもなっていないが新しいSRFIを提出した。ぶっちゃけ大したものではないが、あると便利系のものである。実装はR7RS+既存のSRFIで行ったのだが、これがまた面倒であった(多少SRFIを書く理由にかかる)。一つの処理系のみを使ってる、もしくは手元に過去の資産としてある程度のコードがあるという状態であればSRFIは特に必要ないだろう。ただ、それだと非常に面倒なのである。ソート手続き一つを取ったとしても、たとえ20行もあれば書けるとはいえ、毎回書きたくはない。開発効率を見れば、よく使うものは処理系がサポートしているべきである。そう、私がSRFIを書くもしくは採用する一つの理由はあれば便利だからである。特に最近のR7RS-large絡みのSRFIはScheme用ライブラリの拡充に近い部分があり、あると便利なのである。

私はちょいちょいポータブルなライブラリを書く。 R6RSかR7RSかはそのときの気分次第ではあるが。最近はR7RSの方が多い気がする、処理系の更新があるから。よく使うR6RS処理系(Mosh、Ypsilon)は更新とまってるんだよねぇ、はぁ・・・。ポータブルなものを書く理由は特にない、あるとすれば名前を売るか自己満足くらいだろう。Schemerが増えてSagittariusへのフィードバックが多くなるといいなぁとかも考えてはいるが、期待はしていない(正直特に反応もないし)。これはポータブルなものに限った話ではないのだが、ライブラリを書く際に部品が足りていないと非常に辛い。例えば優先度つきキューを考えてみる(最近適当なのを書いたのだ)、こんな超が付くほど有名なデータ構造は標準もしくは準標準でサポートされていてほしいと思うのが多少なりともプログラムを書いた人間なら思うだろう(学習用とかは除く)。しかし、残念ながらSchemeにはどちらにもないのである。

なければその場で書いてもいいだろう、 実際適当な実装であれば50行もあれば書けてしまうのだ。問題はそれがこれか何万回と続く可能性があることだ。誰もが使う可能性があるデータ構造、アルゴリズムというものは裏を返せば(返さなくても)自分もよく使うのである。R5RS以前のSchemeはモジュールという概念がなく、そういったものを標準の範囲内でまとめておくことができなかったが、R6RS以降はライブラリがあるのだ、使わない手はない。

もう一つ理由がある。インターフェースの統一である。例えばスレッド関連のSRFIとしてSRFI-18があるのだが、不思議なことに採用している処理系はそんなに多くない。POSIXスレッドモデルを採用している処理系であれば互換レイヤを書くのはそんなに難しくないのだが、世の中そんなに甘くない。私がよく使うR6RS処理系、MoshとYpsilon、はMutexすらユーザに見せていない。 そうすると同期を必要とするライブラリを書くのが非常に面倒になる(それらをサポートしないという手ももちろんあるが・・・)。こうなったときに処理系側にサポートを強要することが可能な一つの手段としてSRFIがあると思っている。

例えばSRFI-1を考えてみる。リスト処理に特化したこのSRFIは数多くの処理系がサポートしている(ポータブルに書けるというのは置いておくとしてだ)。多くの処理系がサポートしているデファクトSRFIというのは他の処理系もないがしろにしないだろう(個人的感想)。例えばSagittariusは元々SRFI-25とSRFI-78をサポートしていなかったが(特にSRFI-78はSRFI-64とコンセプトが似ているので)、ユーザからのフィードバックでサポートするようになった(実装まで送られてきたのではしないわけにもいくまい)。こういう経験から、あるSRFIが幅広く使われるようになれば、例えポータブルなものが使えない処理系でも、サポートされるのではないかという期待が持てるのである(その処理系が継続的に開発されてればではあるが・・・MoshもYpsilonも数年新しいリリース出てないなぁ・・・)。

特に何のオチもないのだが、終わり。

2015-01-13

マクロの健全性または如何にして私はerマクロを使うのをやめsyntax-caseを愛するようになったか

メモワール(Memoir)という単語をTwitter上で見かけて、自分も何か(主にあほなこと)を書きたくなっただけ。

Schemeにはhygienic macroなるものがあり、清潔なマクロとか健全なマクロとか訳されるのであるが、それを使うと変数の衝突などの問題をあまり考えなくてもよくなるである。Scheme界では長年このマクロについて議論されてきたらしいのだが、R6RSで終に低レベルかつ健全なマクロの一つであるsyntax-caseが標準に入ることになった。これでマクロ展開時に式変形以上のことができると喜んだのもつかの間、R7RSではまた不便なsyntax-rulesだけに戻されてしまった。理由はよく分からない。風の噂ではR7RS-largeではExplicit Renamingと呼ばれる別の低レベルな健全マクロが入るとされている。

erマクロとはどんなものか?大まかに言えば、Common Lispのマクロに健全性を追加する機能を備えたものである。与えられた式の解析、どのシンボルを衝突しないものにするか等は全てユーザーに任される。どのような見た目になるのか、伝統的なaifをerマクロで作ってみることにした。
(define-syntax aif
  (er-macro-transformer
   (lambda (form rename compare)
     (let ((test (cadr form))
           (then (caddr form))
           (els  (if (null? (cdddr form))
                     #f
                     (cadddr form))))
       `(,(rename 'let) ((it ,test))
         (,(rename 'if) it ,then ,els))))))

(aif (assq 'a '((a . 0))) it)
;; -> (a . 0)
マクロの定義が与えられただけではどのような式を渡せば良いのか皆目検討もつかない。さらにはこのままでは期待する式が与えられなかった際のエラーもよく分からないものになる。
;; Oops!
(aif (ass 'a '((a . 0))))

#|
*error*
#<condition
  &compile
    program: (aif (assq 'a '((a . 0))))
    source: "macro.scm":17
  &assertion
  &who car
  &message pair required, but got ()
  &irritants ()

>
stack trace:
  [1] raise
  [2] caddr
  [3] #f
    src: (caddr form)
    "macro.scm":7
  [4] macro-transform
  [5] pass1
  [6] #f
  [7] with-error-handler
  [8] load
|#
きっちりやるのであればかなりのコードを書く必要があり、僕のようなずぼらな人間には使うのが辛いものである(もちろん式解析などパターンマッチでやってしまえば良いのではあるが...)。

ではsyntax-caseではどうだろう?同様のものは以下のように書ける。
(import (rnrs))

(define-syntax aif
  (lambda (x)
    (syntax-case x ()
      ((aif test then)
       #'(aif test then #f))
      ((aif test then else)
       (with-syntax ((it (datum->syntax #'aif 'it)))
         #'(let ((it test))
             (if it then else)))))))

(aif (assq 'a '((a . 0))) it)
;; -> (a . 0)

(aif (ass 'a '((a . 0))))
#|
*error*
#<condition
  &compile
    program: (aif (assq 'a '((a . 0))))
    source: "macro.scm":32
  &syntax
    subform: #f
    form: (aif (assq 'a '((a . 0))))
  &who aif
  &message invalid syntax

>
stack trace:
  [1] raise
  [2] macro-transform
  [3] pass1
  [4] #f
  [5] with-error-handler
  [6] load
|#
マクロ定義からどのような構文なのか分かりやすいし、エラーも構文がおかしいといってくれる(パターンを列挙する等もう少しエラーメッセージが詳しいとうれしいかもしれないが)。なにより、erマクロにはない必要な部分のみを記述しているという感じがよい。

僕にもsyntax-caseは人間が使うには複雑すぎる、erマクロのような式が直接いじれるマクロの方がいいと思っていた時期があった。しかしその思いは簡単なマクロを書くには問題ないのだが規模が大きくなればなるほど逆転していった。これは式解析、変形を記憶しておくことができる頭のいい人間用のマクロではないのではないかと。事実、入力された式の何番目にこの要素を期待してというようなおよそ僕の頭では処理しきれないような処理を負担さてくるではないか。確かにerマクロは直感的である。マクロとは単なるリスト操作であるということさえ分かっていればその使用感は単なるリスト操作プログラムとほぼ同等である。逆にsyntax-caseはwith-syntax等の新しい概念を要求するため初期投資はerマクロより大きいかもしれない。しかしながら、余計なことを考えなくてもよいというその払い戻しは計り知れない。特に僕のようなまずは目的を達すること、その後で手段を見直すような人間にはとても便利なツールである。

こうして僕はerマクロには別れを告げsyntax-caseを愛するようになった。

2015-01-10

Shallow string copy

Since Sagittarius 0.5.10, symbols and keywords are also target of GC. And both are using string as it's real name. The strings were copied and made as literal string before so that symbol->string could just return the given symbols name. It's not the same story now. The whole purpose of GCable symbols and keywords is saving memory. For example, what would happen if symbols were not GCed:
(dotimes (i 10000000)
  (string->symbol (format "symbol.~a" i)))
;; -> 10000000 symbols will be created
You would think nobody writes this type of code. But what if the input was user dependent? To avoid these type of out of memory, I've decided to introduce GCable symbols and keywords.

Now, I didn't make literal string GCable. I don't remember the exact reason but I think it was too naive implementation to do it and caused a lot of problem (maybe I should try again but feels like it would be very tricky to do it since symbols' and keywords' names are string). So whenever symbol->string is called and the name is not a literal string then the procedure copies the string. Thus it can be O(n) process. Stupid isn't it? So I'm thinking to introduce shallow string copy that only takes O(1).

To do it, I need to reconstruct C world string structure. It's currently defined like this:
struct SgStringRec
{
  SG_HEADER;
  unsigned int literalp: 1;
  int size             : (SIZEOF_INT*CHAR_BIT-1);
  SgChar value[1];
};
This is because of GC efficiency. Strings are allocated as atomic memory means there is no pointer inside. This makes GC impact a bit lighter because collector won't traverse inside of allocated pointer (according to Boehm GC document). If I make shallow string copy takes O(1) then the structure should be something like this:
struct SgStringRec
{
  SG_HEADER;
  unsigned int literalp: 1;
  int size             : (SIZEOF_INT*CHAR_BIT-1);
  SgChar *start;
  SgChar *end; /* or add one more flag if this is shallow copied */
};
Then copy string just puts the source pointer. If modification happens, it just make sure the pointer will be deep copied. Seems fine, the consideration is how much GC performance impact it would cause.

The GC impact can be 2 parts:
  • Making string non atomic pointer
  • Limited range shallow copy
The first one is Boehm GC thing so I just need to profile it. The second one can be a problem. Lets say you create a huge string and substring it like this:
(define (split-string s)
  (values (substring s 0 10)
          (substring s 10 20)
          (substring s 20 30)))
The number of character you want is only 30. However if the input string is, let's say, 10000, then the original source pointer would remain until all 3 strings are GCed (or modified). On the other hand, if string copy happens so many times with small string, then actual memory consumption would be smaller. Well, it's not about memory consumption but processing order so this might be kinda trade off.

So to estimate how much impact we would have, I've counted the number of possibly affected procedures.
string-copy103
substring178
symbol->string167
string-set!158
Not so many. This result even includes test cases. symbol->string is not called in many place. So the overhead of O(n) process may not be an issue. (Well, I know this is rubbish because it doesn't show how many it's actually called.)

Hmmmm, should I?

2015-01-08

識別子を識別するために

SRFI-72を確認した結果
  • 識別子の比較は、名前とその識別子の色で行われる
  • 識別子が含む色はリストである(colors)
  • 色はマクロが呼ばれる度に生成される
  • 色は一意のシンボル(eq?でのみ比較される何か)である
  • ソースの式に含まれるシンボルは全て識別子に変換される
    • その際の色は空(nil)
  • 識別子が含む環境は、リネームされるたびに追加されている
  • 束縛は識別子の名前と色をキーとして作られる
  • 全ての束縛には一意の名前が付けられる
    • ライブラリからエクスポートされる際にはそれに対して別名がつく
上記はまぁ前から分かっていたことなので単なる覚書でしかない。本当に知りたいことはリネームのタイミングと識別子の識別方法だったりする。ポータブルなR6RSマクロ展開器であるPsyntaxやこのSRFI-72はどちらもライブラリ機構も提供していて、少なくともSRFI-72はマクロ展開器自体がその機構と密接に関連している。なので一部だけを取り除いて使うということはなかなか難しい。例えば、テンプレート変数が展開されるたびに一意のシンボルになるというのとか。(色付け機能だけを取り除いて実装してみた結果分かったこと。手を動かさないと理解できない程度には頭が悪いので・・・)

とりあえずそれは忘れて現状のリネームの粒度を見直してさらに変数参照の見直しをした結果もう一つわかったこと。おそらく見直し後のリネームの粒度は正しい(syntax-caseのコンパイル時とsyntaxテンプレートの展開時の2回。以前は合計で3~4回やってたorz)。識別子の比較には別の要因がいる。現状識別子が持っている環境を比較をeq?で比較しているのだが、これではまずい場合がでてきている。マクロ展開器を起動した際に環境フレームのみをコピーして一意にしているのだが、これだと同一であるはずのもが非同一になる。これは困る。ここでSRFI-72で行われている色づけが使えそうな気がしないでもない。上記に書いたように、これだけに絞るとまずいので、現状の仕組みの上につける必要がある。(アホみたいな識別子のスロットを排除したいところなのだが、無理っぽいな。)

問題は、どのタイミングで色を変えるかということ。一つはマクロ展開器を起動したタイミングなのだが、そこだけでいいのかが不安。なんとなくもう一息な感じのところまでは来ている気がするので、MPが残っているうちに片付けてしまいたいところではある。走り書き過ぎて自分でも何言ってるのか分からなくなった。

2015-01-07

致命的目な勘違い

随分長いこと勘違いしていたのだが、以下のコードはエラーにならないといけない。
(import (rnrs))

(define-syntax aif
  (lambda (x)
    (syntax-case x ()
      ((_ test then)
       #'(aif test then #f))
      ((k test then else)
       (with-syntax ((it (datum->syntax #'k 'it)))
         #'(let ((it test))
             (if it then else)))))))

(aif (assq 'a '((a . 0))) it)
;; -> error
理由は、一つ目のパターンが展開された際に挿入されるaifは与えられた式のものではないためdatum->syntaxで生成される識別子が期待されるテンプレート識別子から生成されないため。_aifとして、置き換えの際に元の識別子が挿入されるようにすればOKになる。

何が問題かといえば、Sagittariusはこれをエラーにしない。さらにまずいことに僕自身がこの動作を期待してコードを書いている点である。datum->syntaxを多用した記憶はあまりないのだが、CLOS周りとかはかなり処理系の中身べったりで書いているので問題が起きる。また記憶が正しかったら(binary data)辺りもこれ系の動作を期待しているような気がする。

上記のような記憶にあって目に見えてる系のものならまだ救いがあるのだが(それでも影響範囲広いけど)、下記のような間接的に期待しているものがあると困る。
(define-syntax aif1
  (syntax-rules ()
    ((_ test then)
     (aif1 test then #f))
    ((_ test then else)
     (aif test then else))))

(aif1 (assq 'a '((a . 0))) it)
見た目的にはaif1aifの薄いラッパーで単に式をaifに移しているだけなのだが、これはR6RS的には動かない(はず)。が、Sagittariusでは動いてしまう。これ系のコードはdefine-methodで山ほど書いてる気がする。

ここらで一発マクロ周りの見直しをしないといけないな。この辺りを網羅したR6RS準拠なテストケースがほしいところである。PLTのやつはマクロ周りのテストが貧弱すぎて、全パスしてもスタート地点にすら立ってない感じががが・・・

2015-01-04

Environment frames on identifiers

Happy new year! I've kinda missed Japanese holidays around new years day since I needed to work on 2nd January. Some friends even remained me that it's holiday. Shoot!

I've written the article about the bug of datum->syntax. Now I think I've got an idea to resolve without doing O(n^2) identifier rewriting thing during showering. It's always good to let it sit for couple of days (can be weeks or even months).

The problem is that if a renamed identifier is a local variable however variable look up can't find it properly because it's comparing somewhat awkwardly. The reason why it's doing weirdly is more like historical reason (mostly my ignorance of hygienic macro). It might be cleaner if it can refer just comparing environment frame however because of the lack of knowledge, it's now a huge spaghetti even I don't understand why it's like that. Currently identifiers can hold one set of compile time environment frames. The structure of env frame is like this:
(type . ((var val) ...))
type indicates if this is a local variable frame or a pattern variable frame. To look up proper variables from this, it required (or not) somewhat very complicated pile of shit. It basically tries to find proper frames of given identifiers. However because macro expander doesn't rename all identifiers, some frames are the same in identifiers that should be different variables.

The idea came up during showering is making identifiers can contain multiple sets of env frames. The frames should be used from the latest to oldest and macro expander should always rename with prepended env frames. This seems identifier can hold proper environment where it's defined no matter how many it's got renamed. The issues I can see are:
  • Cache file explosion
  • Memory consumption
The first one should not be big deal but I may face this since I've already got huge cache file issue. The second one is sort of inevitable if we rename identifiers each macro expansion.

I'm not totally sure if this works or not yet but sounds like a plan. Need to consider a bit more before start doing this.