2016-12-02

R7RS-largeについて

この記事はLisp Advent Calendarの2日目の記事です。

Schemeの最新規格であるR7RSは2つのパートに分かれている。R7RS-smallとR7RS-largeである。通常の文脈でR7RSといった場合はR7RS-smallを指すことが多い。ではR7RS-largeとはなんなのか?

目的

R7RS-largeの目的は以下である:
Working group 2 will develop specifications, documents, and proofs of practical implementability for a language that embodies the essential character of Scheme, that is large enough to address the practical needs of mainstream software development, and that can be extended and integrated with other systems.
The purpose of this work is to facilitate sharing of Scheme code. One goal is to be able to reuse code written in one conforming implementation in another conforming implementation with as little change as possible. Another goal is for users of this work to be able to understand each other's code based on a shared and unambiguous interpretation of its meaning.
The language is not necessarily intended for educational, research, or embedded use, though such uses are not prohibited. Therefore, it may be a "heavyweight" language compared to the language designed by working group 1.
From Charter for working group 2
とんでもなく要約すると、R7RS-smallだけでは実用的なプログラムを書けないので実用的なライブラリ等を整備するよ、という感じである。

どんな感じで進んでるのか

基本的にはWG2Docketsにある項目をSRFIに書き起こして議論し、最終的に投票をするという感じで進んでいる。現状ではRedDocket(データ構造)の投票までが終了している。それらのライブラリ名はWG2のMLに投げられただけで、今のところ明文化はされていない。コミュニティが小さい+(残念ながら)あまり興味のある人がいないというのが大きな問題だろう。最新のSRFIではOrangeDocket(数値)に関するものが出てきている。

ちなみに、風の噂で流れている(た?)ERマクロがR7RS-largeに入るという話は、YellowDocket(構文)に入っているので、Orangeが終わったら着手される可能性がある。RedがR7RS-small制定から3年かかっているので、決まるのは単純計算で6年後ということにはなるが…

決定されたライブラリ

上記のMLを見ればわかるんだけど、文量を増やすために現在までにR7RS-largeに入ることが決定したライブラリとその概要を書いてみたりする。上記のリストからコピーしている(タイポ含む)
  • SRFI 1 (scheme list)
    古くからあるリストSRFI。ほぼ全ての処理系で使えるといってもまぁ過言ではないくらい有名なやつ。
  • SRFI 133 (scheme vector)
    SRFI-43だとR7RS的に互換性がないからという理由で割と最近作られたベクタSRFI。
  • SRFI 132 (scheme sorting)
    ソートSRFI-32が棄却されて12年経った後に出てきたソートSRFI。大体一緒なんだけど、細かいところでAPIが違う。
  • SRFI 113 (scheme set)
    リスト、ベクタがあるのにセットがないのはどうよっていうので出てきたSRFI。
  • SRFI 114 (scheme set char)
    ほぼ間違いないSRFI-14のタイポ。これまた古くからある文字セット用SRFI。
  • SRFI 125 (scheme hash-table)
    R7RSのハッシュテーブルはSRFI-69の後継にあたるSRFIになった。R6RSのハッシュテーブルがあるのにという気持ちでいっぱいの僕としては気に入らない決定の一つ。
  • SRFI 116 (scheme list immutable)
    不変リストなSRFI。中身はほぼSRFI-1と一緒なんだけど、受け取るものが不変リストであるというところが違う。一応通常のcarとかが不変リストを受け取ってもよしなに計らってくれることを推奨しているけど、サポートしてる処理系あるのかな?
  • SRFI 101 (scheme list random-access)
    ランダムアクセス可能なリストSRFI。正直なんでこれがR7RS-largeに入ったのかはよく分からない。
  • SRFI 134 (scheme deque immutable)
    不変な双方向キューSRFI。
  • SRFI 135 (scheme textual)
    O(1)アクセスを保証するテキスト処理SRFI。R7RS-small的には文字列のO(1)アクセスは明示的に要求していないとしているので、パフォーマンスが気になる場合はこっちを使うという感じ。
  • SRFI 121 (scheme generator)
    Gaucheのgeneratorが元のSRFI。
  • SRFI 128 (scheme lazy-seq)
    ほぼ間違いなくSRFI-127のタイポ。GaucheのlseqにインスパイアされたSRFI。SRFI-41のストリームとは多少違うらしいが、ほぼ気にしなくてもいいらしい。
  • SRFI 41 (scheme stream)
    遅延ストリームSRFI。このSRFIはSRFI史上初のR6RSライブラリを使って参照実装が実装されている。
  • SRFI 111 (scheme box)
    ボックスSRFI。ボックスは名前が示す通り単なる箱で、Schemeのオブジェクトをなんでも格納しておくことができるもの。これを使うと明示的に参照渡しが可能になるはず。まぁ、あると便利だけど、なければ(vector obj)で代用できてしまうようなもの。コンパイラが頑張ると最適化してくれるかもしれない。
  • SRFI 117 (scheme list queue)
    単方向キューSRFI。元々はキューという名前だけだったんだけど、SRFI自体がリストを基に実装されていることを前提にしていたので改名されたという経緯がある。SLIBにあった奴とほぼ同じ。
  • SRFI 124 (scheme ephemeron)
    実装者泣かせSRFIの一つ。キーと値を持つデータ構造で、基本的な部分では弱い参照と一緒なんだけど、値がキーを参照していた際でもGCされるという特徴を持つもの。噂によるとまともに実装されているのはRacketとMIT Schemeくらいらしい。
  • SRFI 128 (scheme comparator)
    SRFI-114はあまりにも醜いという理由から作られたSRFI。ちなみに片方あればもう片方は実装できる。
個人的に番号が新しい(100番以降くらい)のは時期尚早感のあるものが多いと思っている。というか、使える処理系が少ない。Sagittariusくらいじゃないかなぁ、一応全部サポートしてるの(手前味噌)。

控えているライブラリ

以下には入るかもしれないし、入らないかもしれない議論すらされてないライブラリを載せる。既にSRFIになってるものはそのSRFI+その他の提案。まだ提案なだけなものリストだけで提案は省略。
  •  OrangeDocket: 数値関係
    • Numeric types and operations: 
      • Integer division: SRFI-141
      • Bitwise integer operations: SRFI-142, SRFI-60 or R6RS
      • Fixnums: SRFI-143 or R6RS
      • Flonums: SRFI-144 or R6RS
      • Compnums: John's proposal
      • Random numbers: SRFI-27 plus Gauche's generator
      • Prime numbers: Gauche's prime number library
    • Numeric and semi-numeric data structures
    • Enumerations (なんでこれここにあるんだろう?)
    • Formatting (同上)
  • YellowDocket: 構文関係
    • Low-level macros (有名どころの低レベルマクロがリストされてる)
    • Syntax parameters: SRFI-139
    • Matching (パターンマッチ)
    • Combinators
    • Conditional procedures (if等をdefineで定義した感じのなにか?)
    • cond guards: SRFI-61
    • Lambda* (Scheme Workshop 2013に出た論文がもとっぽい)
    • Void (eq?で比較可能なNULLオブジェクト)
    • Named parameters: John's proposal or SRFI-89
    • Generalized set!: SRFI-17
    • and-let*: SRFI2
    • receive: SRFI-8
    • cut/cute: SRFI 26
    • Loops: SRFI-42, foof-loop or Chibh loop
    • Generic accessors/mutators: SRFI-123
    • Conditions (例外、なぜにR6RSではないのか…)
  • GreenDocket: ポータブルに書けない何か
    • File I/O
    • Threads: SRFI-18
    • Real-time threads: SRFI-21 (分ける必要あるのか?)
    • Socket: SRFI-106
    • Datagram channels (UDP sockets)
    • Timers: SRFI-120 (なんでこれがあるんだろう?)
    • Mutable environments
    • Simple POSIX (Windowsは完全無視ですね、わかります)
    • Access to the REPL (これ完全にR6RS殺しに来てるな…)
    • Library declarations
    • Symbols
    • Interfaces
    • Process ports (紛らわしいけど、プロセスI/Oをポートにリダイレクトする話)
    • Directory ports (ディレクトリをポートみたいに読む、正直紛らわしい)
    • Directory creation/deletion
    • Port operations
    • System commands (Process portsと被り気味な気がする)
    • Pure delay/force (スレッドを使ったdelay/forceっぽい)
  • BlueDocket: ポータブルだけど高度なものたち(portable but advanced things)
    • Time types: SRFI-19
    • Binary I/O
    • Character conversion (要するにR6RSのコーデック的なもの)
    • Parallel promises (pure delay/forceじゃだめなん?)
    • Pathname objects
    • URI objects
    • Unicode character database
    • Environment (紛らわしいけどusernameとかメモリとかを引くためのもの)
    • Trees (リストにあるけど提案なし)
他にもあるけど、多分色付きの名前の奴が優先だとは思うので省略。

2016-11-29

Syntax parameter 2

Couple of months ago, I've written about syntax parameter. Now, I noticed that this implementation isn't really useful in certain (probably most of the) cases. For example, consider like this situation: You want to parameterise user inputs and your macro need to cooperate with auxiliary macros something like this:
;; default input is '()
(define-syntax-parameter *input* (syntax-rules () ((_) '())))
(define-syntax aux
  (syntax-rules ()
    ((_ body ...)
     (let ((user-input (*input*)))
       ;; do what you need to do
       body ...))))
(define-syntax foo
  (syntax-rules (*input*)
    ((_ (*input* alist) body ...)
     (syntax-parameterize ((*input* (syntax-rules () ((_) 'alist))))
       (foo body ...)))
    ((_ body ...) (aux body ...))))

(foo (*input* ((a b) (c d))) 'ok)
;; *input* is '()
I would expect that in this case *input* should return ((a b) (c d)). And, indeed, Racket returns ((a b) (c d)) as I expected.

The problem is simple. My implementation of syntax-parameterize is expanded to letrec-syntax with bound keyword. However since the above case crosses macro boundaries, *input* always refers to globally bound identifier. Now, my question is; can it be implemented portable way? If I read "Keeping it Clean with Syntax Parameters", then it says it's implemented in a Racket specific way. (If I read it properly, then syntax parameter is really a parameter object which can work on macro.)

Hmmm, I need to think how I can implement it.

2016-11-21

ニュースを読もう

ここ数週間の空き時間を使ってちょっとしたサイトを作っていた。news-reader.nl
ちなみに、ニュースを比較しながら読むとか、ダイジェストだけ知りたいとかいうモノグサな思いから生まれたものだったりする。今のところシンプルな機能しかないけど、そのうち自動でカテゴリわけしたりとか、似ている記事を列挙したりとかできたらいいなぁとは思っている。

適当によく見るニュースサイトを載せてるだけなので、これがあるといいというのがあればリクエストください。

これだけだとなんなので、ちょっと内側も覗いてみたりする。

構成としてはリバースプロキシとしてNGINX、フロントエンドはAngularJS、バックエンドには当然Sagittariusが使われている。NGINXは静的ファイルを返すようにして、Angujarが適当にAJAXでゴニョゴニョする。っで裏で動いているPaellaがPostgreSQLにアクセスしてデータを返すと。

ニュース自体はRSSを取ってきて、タイトルと説明を表示している。裏でCronが一時間に一回走るようになっているので、適当に更新される。(今のところ削除されないから、記事が貯まるとサーバーがパンクするような気もするが、まぁこれは後で考えよう…)

デプロイはAnsibleである程度自動化されている。テスト中はフルオートだったんだけど、本番にデプロイする際に手作業が発生したので。まぁ、そのうち気が向いたら直すことにしよう。(二度目があるとも思えんしなぁ)

広告載せてるけど、これかなりうざいのでサーバー代をお布施するつもりがないのであればアドブロック推奨で。

2016-10-19

Connection and session model

CAUTION: It's rubbish. Just my brain storming.

I'm not even sure if this is a proper model name or not. But I often see in low level communication specification, there is a connection and sessions (or channels) belong to the connection. Sometimes (or most of the time?) channels can be recovered on different connections, but here I discuss non recoverable channel for my ease.

I've written couple of scripts which handles this type of things already. For example AMQP. I think one of the pros for this model is preventing actual connection count. Recently, I've faced a concurrency problem caused by reading data from one single connection. At that moment, I didn't want to create much of connections (but in the end realised that there's no other way, though). Then I've started thinking about it.

Now I'm thinking can this be done in generic way or at least something which can be reused instead of writing the same mode everywhere? Suppose,a connection have a port. If a session is derived from the connection, then connection gives the session a session id or so. Whenever data are read from sessions, then actual connection dispatches read data according to the required session id. Something like this:
(import (rnrs))

(define-record-type connection
  (fields port ;; suppose this is input/output port
          sessions)
  (protocol (lambda (p)
              (lambda (port)
                (p port (make-eqv-hashtable))))))
(define-record-type session
  (fields id connection))

(define (open-connection port) (make-connection port))
(define (open-session connection)
  (let* ((sessions (connection-sessions connection))
         ;; FIXME
         (id (+ (hashtable-size sessions) 1))
         (session (make-session id connection)))
    (hashtable-set! sessions id session)
    session))

(define (read-from-session session)
  ;; IMPLEMENT ME
  (read-for-session
   (session-connection session)
   (session-id session)))
To keep it clear, here connection is the physical connection and sessions are logical layers derived from a connection. A channel is a communication pipe between connection and session.

Obviously, this doesn't work as it is even if I implement reading part, because:
  1. There's no way to know which message should go which session
  2. There's no negotiation how to open a session, this type of things are usually client-server model.
To know how to dispatch messages, connections need to know how message frames look like. So connections should have something like receive-frame field which contains a procedure receiving a message frame?
(define-record-type connection
  (fields port
          ;; suppose this returns 2 values, message id and payload
          receive-frame
          negotiate-session
          sessions)
  (protocol (lambda (p)
              (lambda (port receive-frame negotiate-session)
                (p port receive-frame  negotiate-session (make-eqv-hashtable))))))
Is it good enough? But what if there are like these 2 process is simultaneously running; opening a session and reading payload from a session. So it might be a good idea to have channel like this?
(define-record-type connection
  (fields port
          receive-frame
          ;; takes session-id, channel-id and connection.
          ;; returns physical-session-id
          negotiate-session
          sessions
          channels)
  (protocol (lambda (p)
              (lambda (port receive-frame negotiate-session)
                (p port receive-frame
                   negotiate-session
                   (make-eqv-hashtable)
                   (make-eqv-hashtable))))))
(define-record-type session
  (fields id channel-id connection
          (mutable physical-session-id)))
(define-record-type channel
  (fields id buffer))

(define (open-connection port) (make-connection port))
(define (open-session connection)
  (let* ((sessions (connection-sessions connection))
         (channels (connection-channels connection))
         ;; FIXME
         (session-id (+ (hashtable-size sessions) 1))
         (channel-id (+ (hashtable-size channels) 1))
         (channel (make-channel channel-id
                                ;; IMPLEMENT ME
                                (make-buffer)))
         (session (make-session session-id channel-id connection #f)))
    (hashtable-set! sessions session-id session)
    (hashtable-set! channels channel-id channel)
    session))
Hmmm, would it be enough? I'm not sure yet. And I'm not even sure if this is useful. Maybe I need to implement a prototype.

2016-10-10

SXMLオブジェクトビルダー

なんとなくSXMLをレコード変換するフレームワーク的なものがあると便利かなぁと思って作ってみた。まだ作りこみが甘い部分もあるが、必要そうな部分は動いているのでちょっと紹介。

ライブラリは(text sxml object-builder)としてみた。基本的な使い方はこんな感じ。
(import (rnrs)
        (text sxml ssax)
        (text sxml object-builder)
        (srfi :26))

(define-record-type family
  (parent xml-object))
(define-record-type parents
  (parent xml-object))
(define-record-type child
  (parent xml-object))
(define-record-type grand-child
  (parent xml-object))

(define family-builder
  (sxml-object-builder
   (family make-family
    (parents make-parents
     (? child make-child
        (? grand-child make-grand-child))))))

(define sxml (call-with-input-file "family.xml" (cut ssax:xml->sxml <> '())))

(sxml->object sxml family-builder)
;; -> family object
family.xmlはこんな感じ。
<?xml version="1.0" ?>
<family>
  <parents father="Daddy" mother="Mommy">
    <child name="Big bro">
      <grand-child name="Bekkie">Boo!</grand-child>
      <grand-child name="Kees">Bah!</grand-child>
    </child>
    <child name="Sis"/>
  </parents>
</family>
sxml-object-builderマクロはなんとなくいい感じにオブジェクトビルダーを構築してくれる。基本的には(tagname constructor . next-builder)みたいな構文。next-builderが空リストだと渡ってきたSXMLそのまま使う感じ。後は量指定子だったり、複数タグにしたり。最終的にはXSDと同等の表現力を持てたらなぁとは思っている(ほぼカバーしてるつもりだけど、仕様書を真面目に読んだことがないので何が足りてないのかが分かっていないという…)。

ここではレコードを定義してるけど、constructorは3引数受け取る手続きなら何でもいい。便利かもしれないということで、xml-objectなるものをデフォルトで用意してるけど、特に使う必要はない。

これだけだとイマイチ嬉しくないんだけど、もうひとつSchemeオブジェクトからSXML変換するライブラリを考えていて、それがあれば多少嬉しくなる予定ではいる。

2016-10-06

スペシャリテ

料理の話ではない。

Scheme処理系は世の中に山ほどある。RnRS準拠(n≧5)に絞ったとしてもかなりある(というかR5RSが多い)。そこで、有名処理系が選ばれる理由を考えてみた。

有名所の処理系

R5RS
  • Chicken
    • Eggが便利
    • Cに変換すれば高速に動く
    • コミュニティが大きい
R6RS
  • Chez
    • 現状最高速の処理系
  • Guile
    • GNU公式拡張言語
    • コミュニティが大きい
  • IronScheme
    • .Netで動く
  • Larceny
    • 高速
    • R7RSハイブリッド
  • Racket
    • 高速
    • コミュニティが大きい
    • Planetが便利
    • リッチな環境がついてくる(DrRacket)
  • Mosh
  • Ypsilon 
  • Vicare
    • ファンが多い?
R7RS
  • Chibi
    • コンパクト
    • C拡張が書きやすい
  • Gauche
    • 日本語ドキュメント
    • 手軽?
  • Kawa
    • JVMで動く

あんまりよく考えてないけど考察

Chicken、Guile、Racketはコミュニティの多きさ≒問題解決のしやすさとライブラリの豊富さが大きいかなぁと。Chezは元商用の処理系だけあって速い。Gaucheは日本語ドキュメントが大きいかなぁ(日本限定で考えれば)

KawaとIronSchemeは環境固定されるのでその環境で使いたいならほぼ一択状態。流石にJVMだと他にもあるけど、知名度的にはKawa一択だろう。

Larcenyがどれくらい使われているかはちと分からんけど、超有名な処理系なのでそこそこユーザーはいるんじゃないかなぁ。

Mosh、Ypsilon、Vicareはリリースが年単位でされてないから(MoshとVicareはリポジトリの更新があるけど、Ypsilonに関しては多分放棄されてる)、正直これらを選ぶ理由が見つからない。バグリポートしても直らんし。強いて言えばファンが多いくらい?

スペシャリテ?

じゃあどうするか?そもそも知名度が低いという点でどうしようもないんだけど、宣伝するにしても「それなら〇〇でいいじゃん」ってことにならないようにしたい。っで、現状ある武器で考えると以下かなぁ:
  • R6RS/R7RSハイブリッド
  • リーダーマクロ
  • そこそこ手軽
  • Cトランスレータ有り(バイナリ走らせるのにランタイムがいるけど)
挙げてみて思ったけど、ユーザー視点でいいことないなぁ。これだと「〇〇でいいじゃん」にしかならない。将来的に入れようかなぁと思っているのは日本語ドキュメントなんだけど、入れたところでGaucheの牙城を崩せる気はしないしなぁ。

地道にライブラリを増やすとか、環境を整えるとかなぁ。

2016-09-28

C translator (2)

Starting 0.7.8, Sagittarius provides experimental C translator. Currently it's more or less toy quality (though, just using is not a problem). There are 2 way of translations:
  1. Dump all required library cache
  2. Doing the same as precompiled files
Both solutions have problems. The first one requires huge amount of static area and generated files are huge. The second one can't translate macros.

Dumping cache file is not a good solution so I want to discard it. To do so, second solution must support macro translation. The challenge of doing it is that macro contains shared structures and may contain subrs (Scheme procedures defined in C). Translating shared structure to C may not be so difficult but subrs. Subrs themselves don't have any information where it's defined, so they only have their name and C pointer. As far as I know, there's no subr in macro so this may not be a problem as long as users (me mostly) don't do some black magic (and I know I can...).

One of the benefits (or maybe this is the only) of translating C is that considerably short amount of starting time. Sagittarius is, unfortunately, not so fast implementation, and its starting time is not so fast even when it loads only cached libraries. For example, one of my daily routine scripts takes 500ms to just showing help message (8000ms if it's not cached) and translated version takes 130ms. It's not that much difference (yet) but still it's almost 5 times faster than raw Scheme.

However, I think it's still slow or doing some unnecessary things. Consider the following script:
(import (rnrs))

(define (main args)
  (display args) (newline))
If I run this script, then it loads 32 libraries currently. But the only bindings required in this script are display and newline. So if the C translator is smart enough to detect them, then the result script should look like this:
;; imaginary script... 
(define (main args)
  (#{(core)#display} args) (#{(core)#newline}))
Then it doesn't require any unnecessary library loading.

Hmm, I think I have a lot to do.