Named let performance

When I was playing around with Sagittarius compiler, I've found that some of named let expression was compiled to (looks) slow code. Following piece of code is one of them;

(lambda (pred lst)
  (let loop ((lst lst))
    (cond ((null? lst) '())
          ((pred (car lst)) (loop (cdr lst)))
          (else (cons (car lst) (loop (cdr lst)))))))

You can see this type of code anywhere (although it's not tail recursive so I don't like it). And you would expect this not to have any performance issue other than stack consumption because of the recursive call.

Now, I was also thinking like that however things are bit worse. The compiled code describes everything;

;; size: 3
;;    0: CLOSURE #<code-builder #f (2 0 0)>
;;   size: 13
;;      0: UNDEF
;;      1: PUSH
;;      2: BOX(0) !!!! IMPLICIT BOXING !!!!
;;      3: LREF_PUSH(0)
;;      4: LREF_PUSH(2)
;;      5: CLOSURE #<code-builder loop (1 0 2)> !!!! CLOSURE CREATION !!!!
;;     size: 26
;;        0: LREF(0)
;;        1: BNNULL 3                  ; ((null? lst) '())
;;        3: CONST_RET ()
;;        5: FRAME 4
;;        7: LREF_CAR_PUSH(0)
;;        8: FREF(1)
;;        9: CALL(1)
;;       10: TEST 6                    ; ((pred (car lst)) (loop (cdr l ...
;;       12: LREF_CDR_PUSH(0)
;;       13: FREF(0)
;;       14: UNBOX
;;       15: LOCAL_TAIL_CALL(1)
;;       16: RET
;;       17: LREF_CAR_PUSH(0)
;;       18: FRAME 5
;;       20: LREF_CDR_PUSH(0)
;;       21: FREF(0)
;;       22: UNBOX
;;       23: LOCAL_CALL(1)
;;       24: CONS
;;       25: RET
;;      7: LSET(2)
;;      8: LREF_PUSH(1)
;;      9: LREF(2)
;;     10: UNBOX
;;     11: LOCAL_TAIL_CALL(1)
;;     12: RET
;;    2: RET

I've put comments where it causes performance issue.

The first one, implicit boxing, is because the loop is transformed to letrec and it needs to refer loop itself inside of it. The second one is creating a procedure each time the top procedure (I haven't named it though) is called because it has a free variable pred inside. Sounds reasonable? No, it doesn't at all to me now. If you write a piece of code with named let, then you would expect the calling named procedure would be compiled to just a jump. However this is compiled to a procedure call. Well, on the other hand this is not a tail recursive call so you wouldn't expect to be a jump though. Actually if the code was tail recursive then compiler would compile it to a simple jump without implicit boxing and creating a closure.

Now, then should users always be careful or adjust their code how compiler compiles to maximumised performance instructions? My answer is yes and no. In above case, I expect at least compiler should emit non implicit boxing code. In general, compiler should be smart enough to emit good quality code. Then problem is how? ... that's something I need to think, though.

SRFI-17の紹介

(LISP Library 365参加エントリ)

SRFI-17は一般化したset!です。発案者はKawaの製作者Per Bothner氏ですね。(他のSRFIでも既にGuileやらLarcenyやらの製作者が出ていたのですが、文量の水増しです。)

CL使ってる方はsetfに近いものだと思ってもらえればいいです。使い方は以下のようになります。

(set! (car a) 'b) ;; -> (set-car! a 'b)
(set! (cdr a) 'c) ;; -> (set-cdr! a 'b)

(set! (vector-ref v 0) 'a) ;; -> (vector-set! v 0 'a)

実際にこのように展開されるかは実装次第なところもあるのですが、SRFI内では以下のようになると書かれています。

(set! (proc args ...) value) 
 ;; -> ((setter proc) args ... value)

例えば、Gaucheでは(set! (car a) 'b))はSRFIのように展開されますが、Sagittariusはset-car!が直接呼ばれるようにコンパイルされます(それがいいかどうかは別の問題ですが)。他の処理系は調べてません。

あまりに文量が少ないので多少余計な情報も。

このSRFIはどうやらかなり不評だったようです。

I have gotten no support for my proposal. While the srfi process allows for srfis that are controversal and don't have consensus, at this stage it seems kind of pointless to pursue it. I have no particular desire to push for something most people dislike, at least in this context. So if anybody out there thinks the generalized set! is a good idea, now is the time to speak up.
http://srfi.schemers.org/srfi-17/mail-archive/msg00049.html

この投稿が投げられる前にあったMatthias Felleisen氏が投げた投稿から始まる議論(罵り合い？)がなかなか面白いです。個人的には便利なSRFIだと思っているのですが、Scheme的ではないかもしれませんね。

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

How to emulate pthread_cond_wait with SRFI-18

I was implementing multi thread queue like Gauche has but in pure Scheme with SRFI-18. Then I've got confused how to wait condition variable. If it's POSIX then you can use pthread_cond_wait. However it's SRFI-18 and it doesn't provide a procedure to wait condition variable directly. Well, in the end there are some example code which explains how to do it but at that moment I couldn't figure it out. So there may be some people who also have the same issue as me. (It's basically because of my lack of knowledge of multi threading and, well, if there aren't at least this could be my memo to remember...)

The answer was a combination of mutex-unlock! and mutex-lock!. I was always thinking that pthread_cond_wait or similar procedure is the only way to wait for a condition variable. I skipped reading this section (and caused my confusion...)

NOTE: mutex-unlock! is related to the "wait" operation on condition variables available in other thread systems. The main difference is that "wait" automatically locks mutex just after the thread is unblocked. This operation is not performed by mutex-unlock! and so must be done by an explicit call to mutex-lock!. This has the advantages that a different timeout and exception handler can be specified on the mutex-lock! and mutex-unlock! and the location of all the mutex operations is clearly apparent. A typical use with a condition variable is:

(I don't complain this is very confusing but don't you think?) So what I needed to do is instead of searching something that specifically says condition-wait! or something, I needed to use mutex-unlock! and mutex-lock!. Following piece of code is more concrete example;

(import (rnrs) (srfi :18))

(define-record-type (<foo> make-foo foo?)
  (fields (immutable mutex foo-mutex)
          (immutable cv    foo-cv)
          (mutable   count foo-count foo-count-set!))
  (protocol (lambda (p)
              (lambda ()
                (p (make-mutex)
                   (make-condition-variable)
                   0)))))

;; Utilities for above foo record
(define-syntax lock-foo!
  (syntax-rules ()
    ((_ foo) (mutex-lock! (foo-mutex foo)))))
(define-syntax unlock-foo!
  (syntax-rules ()
    ((_ foo) (mutex-unlock! (foo-mutex foo)))))
(define (with-locking-foo foo thunk)
  (dynamic-wind
      (lambda () (lock-foo! foo))
      thunk 
      (lambda () (unlock-foo! foo))))

(define-syntax wait-cv
  (syntax-rules ()
    ((_ foo)
     (let ((r (mutex-unlock! (foo-mutex foo) (foo-cv foo))))
       (display "unlocked! with cv") (newline)
       ;; mutex is not locked so lock it if you need it.
       (mutex-lock! (foo-mutex foo))
       r))))

(define-syntax notify-foo
  (syntax-rules ()
    ((_ foo)
     (condition-variable-broadcast! (foo-cv foo)))))

(let ()
  (define foo (make-foo))

  (define (producer)
    ;; increment count
    (with-locking-foo foo
     (lambda ()
       (display "Increment count!") (newline)
       (foo-count-set! foo 1)
       (notify-foo foo))))

  (define (consumer)
    ;; wait until the count is one
    (with-locking-foo foo 
     (lambda ()
       (let loop ()
         (cond ((zero? (foo-count foo))
                (display "It's zero need to wait!") (newline)
                (if (wait-cv foo)
                    (loop)
                    (error #f "something went wrong")))
               (else (foo-count foo)))))))

  (let ((ct (thread-start! (make-thread consumer)))
        (pt (make-thread producer)))
    ;; consumer is waiting but make sure
    (thread-sleep! 10)
    ;; let producer increment
    (thread-start! pt)
    (thread-join! pt)
    (display (thread-join! ct)) (newline)))

#|
It's zero need to wait!
Increment count!
unlocked! with cv
1
|#

This just tries to emulate pthread_cond_wait using mutex-unlock! and mutex-lock!. The wait-cv is the emulation macro. notify-foo assumes that given foo
's mutex is locked. It took couple of hours to figure out this simple thing for me...
I haven't met any case that this mutex model is convenient but if this how it is I need to get used to it. (though, my case was just the name confusion...)

SRFI-16の紹介

(LISP Library 365参加エントリ)

SRFI-16は可変長引数を受け取る手続きに対する構文です。要するにcase-lambdaです。R6RSから標準になった構文なので、あまり目新しいものは無いかもしれません。

以下のように使います。

;; because it's very famous I've become a bit lazy
;; so just a bit of taste...
(define foo
  (case-lambda
    ((c key) (foo c key #f))
    ((c key default) (ref c key default))))

上記の(いい加減な)例では、束縛される手続きは2つもしくは3つの引数を受け取ります。2つの場合は3つ目の引数にデフォルトの値として#fを設定して自身を呼びなおします。以下のように書くのとそんなに変わりません。

(define (foo c key . rest)
  (let ((default (if (null? rest) #f (car rest))))
    (ref c key default)))

ちなみに、参照実装だと上記のcase-lambdaは以下のように展開されます。

(define foo
  (lambda args
    (let ((l (length args)))
      (if (= l (length '(c key)))
          (apply (lambda (c key) (foo c key #f)) args)
          (if (= l (length '(c key default)))
              (apply (lambda (c key default) (ref c key default)) args)
              (error #f "Wrong number of arguments to CASE-LAMBDA"))))))

これだと多少手間が減る程度の恩恵しかありません。(もちろん処理系によっては引数のパックとapplyが異常なまでに安い処理系もあるかもしれませんが･･･) また、コンパイル時に手続きの呼び出しを行わない処理系だと、lengthの呼び出しが定義された分だけ呼び出されるので精神衛生上あまり好ましくありません。

さすがにこれはどうかとも思ったらしく、以前syntax-rulesのみを使った多少効率のいいcase-lambdaの実装を作っていました。(ちなみに、Sagittariusではもう少し前に書き直しています。やってることは一緒なのでsyntax-rules版にしてもいいかとは思いますが。)

これならば引数がパックされるだけでapplyを呼び出すことがないので、参照実装よりは多少効率がいいはずです(オプション引数として受け取るのと同等程度)。もう少し進めるのであれば、組み込みの構文にしてしまってコンパイラが受け取る引数をうまいこと解決するということも可能かもしれません。

今回はSRFI-16を紹介しました。RnRS準拠でもっと効率のいい実装があるよ！という方がいらしたらご一報くださいm(_ _)m

Shibuya.lisp meetupに行ってきた

Lisp コンパイラの評価マークシティの駐車場の方に行ったり、chikuさん(だと思う)に5階まで来てもらったのに入れ違いで17階にたどり着いたりしたのはまぁ誤差の範囲だろう。初見殺しだね、あのビル。

発表の見出しはここ。とりあえずざくっと感想。

ELSの。パリだったんだし行けばよかったなぁというのが真っ先に出てきた感想。 論文は目を通したのもあったけど、見てないのの方が多い。日本からだとトータルで旅費がどれくらいかかったんだろう？と思ったが、僕が質問することでもないなぁと思ったので思っただけにとどめた。(これ出てこなかったということは、会場の人はお金を気にしなくてもいいくらいの身分の人ばかりか、ECLにそこまで興味がないかのどちらかかなぁ、とも思ったり。)

僕の。

Inside of Sagittarius (ja) from Kato Takashi

メインはサルミアッキで発表はおまけ。最初に行ったけど、詳細と書いてあるけど割りと表面の概要だけ。

CLの最適化。いくつか聞いてて気になった部分はあったけど、質問したのは1個だけ。ちなみに気になったのは以下。

• プロファイル取らない点
• コード見て遅いのが判別できるのはあるけど、性能出すのってその先が結構要る場合が多いので。
• まぁ、でも複数アルゴリズムを試すとかじゃなかったから問題ないのか？
• レジスタに乗せる方に割いてた点
• x86だとレジスタに乗らんのでは？と思ったが環境がMacのCore i7だったし、いいのか？
• SBCLだとx86でもレジスタ6個使うから問題ないかもしれない。
  参照：Lisp コンパイラの評価
• ちなみに、これは質問したやつ
• 性能と抽象化の両方を取るけど、性能にかなり傾いてた点
• pixel(だったかな)型をばらして渡すよりはdynamic-extentでスタックに載せて抽象度を保ったままの方が好みかなと思っただけ。

Picrinの。これのスライドを5枚みたくらいで時間切れ。スライドを見た感じだと面白そうだったので見たかった。(しかし40枚以上あったけど、9時半までに終わったのかな？)

自分のPCにシリアルポートが付いてないとか昨日初めて知ったりしていた(あれが無ければ10分くらい時間節約できたよね、すいません)。開始前に皆席について静かに待っていたので自己紹介もあるしと思い郷にいってしまったが、ここで回っておけばよかった。おかげでほぼ顔とTwitter IDが一致しない・・・Shibuya.lisp in the Netherlandsとか開くべき。まぁ、ELSにもっと日本から人がくればいいだけの話ともいう。(行ってないけどｗ)

なんだか日本っぽいと思ったもの

休暇で日本にいるのだが、特にやることもないので地元をぶらぶらとしている(暑いので名古屋に行くのも面倒という・・・)。っで、ふとすごく日本っぽいものを発見した。

まずは以下のような張り紙。

 30km/h制限の道に貼られていたのだが、「みんなが見ています」というのがなんとも日本っぽいなぁという感じである。

次にビル(アパート)名

 住んでいる人は王族か貴族か何かだろうか？10年前とかに見たときは特に気にしなかったような気がするのだが、今はふと気になった。そういえば、ほぼ全てのビルに名前が付いているのも日本っぽい気がする(自分が今住んでいるアパートに名前はない)。名前の付け方はセンスを疑うが、名前があるというのは目印にしやすいし、いいことじゃないかなぁと思う。

見る人が見ると今どこにいるのかバレバレな写真な気もしないでもないが、まぁいいか。

Want to use SFTP?

I've added SFTP library (rfc sftp) recently so let me introduce it.

If you are a lazy programmer, you would have thought, at least once, that avoiding GUI operations to upload files to SFTP server. (Yes, that was my motivation!) I've been thinking that for already couple of months (or even close to a year). SFTP is a protocol that depending on SSH so first I needed to write the SSH library. From that, for some reason, I didn't have much need to do. (Basically SFTP operation was reduced at my work.) Then a week ago or so, I needed to collect log files from multiple servers and I simply disliked that task. So I wrote it.

Following is the basic usage.

(import (rfc sftp))

(call-with-sftp-connection "hostname" "23"
  (lambda (conn)
    ;; downloading is very straight forward
    (sftp-read conn "a/file" (sftp-file-receiver "a/local/file"))

    ;; uploading is a bit complicated
    ;; firstly, you need to open the file handle
    (let ((handle (sftp-open conn "a/file2" 
                    (bitwise-ior +ssh-fxf-creat+ +ssh-fxf-write+))))
      ;; then you need to use the handle
      ;; uploading uses binary input port as it's input.
      (sftp-write! conn handle 
        (open-bytevector-input-port (string->utf8 "Hello SFTP from Sagittarius")))
      ;; finally close the handle
      (sftp-close conn handle))

    ;; want the contents of a directory?
    ;; (sftp-readdir conn ".") ;; >- this returns a list of sftp-name object
    ;; this returns a list of string representing directory contents (file names)
    (sftp-readdir-as-filenames conn "."))
  :username "user" :password "pass")

sftp-close may not be needed as long as the server can handle it correctly but it's better to do it. You can also write a very thin wrapper for this. (I just didn't have any good API for this so maybe for future.) If your SFTP server doesn't need any authentication then you don't have to specify the keyword arguments (never seen such a server though). For now, the library doesn't support any other authentication method such as login with certificate.

One important note; the underlying SSH library doesn't support key re-exchange properly so if the uploading/downloading file is more than 1 GB in total then it would most likely fail. However I don't need this yet so not sure when this will be fixed. (patches are always welcome!)

This library will be available from 0.5.4 (will be release very soon).

プロのプログラマ

Twitterで「本物のプロのプログラマは数学に精通している」みたいなのを見かけてもやもやしているのでちょっと吐き出すことにした。

そもそも、プロとアマの差というのはあることに対しての対価をもらっているかいないかだと思うのでそもそもの言葉の定義からおかしいという話もあるのだが、とりあえずそれはおいておくとしよう。個人的にはそれがたとえコピペでプログラムを書いてても、それに対しての対価をもらっているのであればプロのプログラマである。品質に対する気概とか、自分の作ったものに対する何かしらとかはどちらかと言えば職人気質に分類されるべきで、プロとアマの差というのに使われるべきではないと思う。

おそらくTwitterでの意図としては「凄腕のプログラマ」くらいの意味だろう。では何をもって「凄腕のプログラマ」とするのか？これはいろいろ議論があるだろうが、まず第一に挙がるのは「問題解決力」、次に「抽象化能力」じゃないだろうか？仮にこれらを持つプログラマを凄腕のプログラマとするならば、そのプログラマは数学に精通している必要があるのだろうか？例えば暗号分野に特化しているのであれば、三角関数とかはあまり必要ない気がする。(僕の経験上でしかないので本当に必要ないかはちょっと微妙。) ついでに言えば、自分が知っている限りの範囲でしかないが、凄腕と呼べるプログラマは引き出しが多いイメージである。ここでいう引き出しが広いとは、あることに対しての解決策の「名前」を知っている、という意味である。

例えば(自分の分野で申し訳ないのだが)、パスワードの保存をセキュアにしたい、という要望があったとする。そうすると「暗号化」がまず出てくる。どのように暗号化するかといえば、「秘密鍵」が出てくるだろう。「公開鍵」ではセキュアではないからだ*1。どの方式がいいかはまぁ後で調べればいいだろう。次に出てくるのは「ハッシュ」を使う方式だろう。ただし、ハッシュにする場合はパスワードを再送するというのは諦める必要がある。ハッシュ方式は「SHA-256」が一応安全か。

これぐらいの引き出しがあれば「実装の中身」までは特に知らなくてもなんとかなる。(暗号分野では大体自分で実装するっていうのはありえないので。) この程度では凄腕とはいえないが、言いたいこととしてはこれだけあれば調べ方が分かるので解決できる。抽象化はまぁその先にあるのでここで上げるのは多少厳しい。で、数学の話は出てきただろうか？

何がいいたいかといえば、プログラマが必要な知識は問題領域に大きく依存するということである。(数学が必要なところってとりあえずゲーム関連しか知らないのだけど、他にもあるの？) そして、その問題領域に精通していれば「凄腕」になる資質は十分にある。他の分野も知っているにこしたことはないが、「必須」ではない。自分の理想像のみを指して「本物のプロのプログラマ*2」といわれると、世の中のプロのプログラマの門を極端に狭くするのでいかがなものか、という話である*3。

*1 暗号化でセキュアとは基本的に総当り以外の解き方がないこと＋暗号文に平文の情報がないことの2点である。公開鍵方式は後者が満たされないという話。
*2 そもそも「偽者のプロのプログラマ」というのがあるのか？という話でもあるが・・・プログラム書いて金もらってりゃ本物のプロだよ、という理論の前だとないので・・・
*3 自分が数学に精通してないのでというのがこれ書いた最も大きな理由だわね。一応金もらってやってるプロだし、それなりにプライドもあるのでちょっとムカっとしたのさ・・・

SRFI-14の紹介

(LISP Library 365参加エントリ)

SRFI-14は文字セットを扱うSRFIです。このSRFIは他のSRFIの下請け的に使われることが念頭にあります(Abstract参照)。実際SRFI-13にはSRFIを使っている部分があります。

基本的な使い方を見てみましょう。

(import (srfi :14))

(char-set-contains? char-set:digit #\a)
;; -> #f

(char-set-contains? char-set:digit #\1)
;; -> #t

基本はこれだけです。一応セットなので以下のようにセットに登録されている文字を扱うことも可能です。

(char-set-map char-upcase char-set:lower-case)
;; -> charset with #\A-#\Z range

ただ、上記のような手続きを日常的に使うということはまずないでしょう。新たに文字セットを構築するのであれば以下の手続きの方がはるかに便利です。

(list->char-set '(#\a ...))
;; -> charset with given chars

(string->char-set "abc..."))
;; -> charset contains given string's characters

(ucs-range->char-set #x100 #x10FFFF)
;; -> charset with range 0x100-0x10FFF

既存の文字セットものから文字を追加もしくは削除ということも可能です。

(char-set-adjoin char-set:letter #\-)
;; -> charset with letters (#\a-#\z #\A-#\Z) + #\-

(char-set-delete char-set:digit #\0)
;; -> charset of #\1-#\9

上記の手続きには破壊的に操作を行うものも用意されています。

これだけだとちょっと寂しいので多少実装にも踏み込んでみます。SRFI-14は参照実装も用意されていますが、参照実装では最大でLatin-1までの範囲しかサポートされていません。実装もかなり素朴で、char-set-containsは256までしかないことを利用したO(1)の手続きです。(ちなみに反復子的な手続きは逆に256回反復させます。)

これはLatin-1までの範囲に絞っているから可能なのであって、Unicodeをサポートするのであれば不可能な実装とも言えます。(ハッシュテーブルのエントリを2^32個作るのは現実的ではないでしょう。) セットが含む文字を全て舐めるO(n)の実装でもまぁ問題はないのかもしれないですが、二分木辺りを使ってO(log(n))くらいで抑えられるといいかもしれません。(疎な配列を使ったO(1)とかも実装によって現実的かも。ただエントリが増えるとハッシュテーブルと同じ問題が起きる？)

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

R7RSのMLで何が起きたのか

別にたいしたことは起きてないんだけど、ちょっと気になるやり取りが(というほどですらないが)あった。

事の発端はJohn CowanがR7RSで数値塔に関することの多数決を取るためにMLに草案を投げたことにある。草案はこれとこれ(改)。 で、どこで線引きするんだ？という議論にPeter BexとJohn Cowanが発展させて、何故かAndy Wingoが噛み付いた。以下がAndyの投稿(意訳)

> 標準ってのは実装者とユーザ間の契約だ。仮定が少なすぎるとユーザが苦しむし
> 多すぎれば実装者が泣きを見ることになる。こいつはGoldilocks問題で、
> 大き過ぎず、小さ過ぎず、ちょうどいいべきだ。
この議論は率直に言ってばかげてる。Dybvig、Flatt、Clingerたちはどこだ？
Feeleyは？俺がもっとも尊敬する実装者たちだよ。
(もちろん、ShiroやPeterがいてくれることには感謝してるよ。けど彼らが今の有権者を
成功に導くことを期待できないよ。) 前述のやつらが興味持ってないなら、なんでまだ
Schemeって呼ぶのさ？

Kent Dybvig(Chezの実装者)、Matthew Flatt(Racketの実装者の一人)、William Clinger(Larcenyの実装者)、Marc Feeley(Gambitの実装者)ですね。Shiroさんは説明する必要すらないでしょうが、Gaucheの開発者です。Peter BexはKawaの開発者。AndyはRatification Voteでこんなコメントをしているので、全面的にR7RSに賛成なShiroさんやPeterでは彼が望む姿に持っていけないという意味でしょうか？(ShiroさんとPeterがR7RSに全面的に賛成しているというのは僕の妄想です)

質問ついでに、R7RS-smallの最終稿はどこだよ？なんでr7rs.orgにないのさ？

コアになる部分に強力で質のいい処理系の参加がないんだったら、R7RSは永遠に
端っこのSchemeと大して違わない標準にしかならないね。それに、こいつらが標準に
なるかもってのも、Johnが(勝手に)決めたことだろ？例えばvector-for-each、こいつを
Johnが投票用紙に並べて、多くの人が賛成票を投じた -- ひょっとしたら後者は必要で
すらなかったか、最低投票数とかないわけだし。SRFIプロセスはRnRSになったしな。

large版でこの違いと要求の議論が起きてるのって、なんていうか…なんだろうな。
なんていっていいのかも分からねぇよ。まぁ、頑張れや、けど俺を巻き込むな。

ちと訳に自信がない。現状のプロセスと人がいないことを憂いて去っていく感じですかね？これに対してJohn Cowanの返信。

> この議論は率直に言ってばかげてる。Dybvig、Flatt、Clingerたちはどこだ？
> Feeleyは？
Wingoはどこだよ？

Andy WingoはGuileの開発者の一人ですね。 なかなか洒落が効いてて好きです。

(中略)

> large版でこの違いと要求の議論が起きてるのって、なんていうか…なんだろうな。
> なんていっていいのかも分からねぇよ。まぁ、頑張れや、けど俺を巻き込むな。
お仲間がいねぇからって、助けるわけでもなくお前はここを去るのか？高貴な身分だ
な！参加したらどうだよ？ここじゃ実装者視点ってのはすげぇ価値があるんだよ --
そいつが得られるならな。

中略の部分はWorking Groupではscheme-reports.orgの変更はできないし、r7rs.orgは別の人の持ち物だから触れもしないよ、という旨が書いてあります。r7rs.orgは2009年に出来て以来特になんら代わり映えしてないのですが、r7rs.comの方は一応R7RSの最終稿へのポインタがあったりするので、Andyの調査不足が露呈してたりします。

そういえば、上記のAndyが尊敬する処理系実装者のうち、Scheme処理系として開発を継続してる人っているの？RacketはRacket言語としての道を選んだし、ChezとLarcenyは開発とまってるし(ChezはCiscoで内部的に開発されているという噂もある)。Gambitは継続されてるのか、そこそこの頻度でコミットがあるな。

O記法

CourseraのAlgorithms: Design and Analysis, Part 1の復習。別に毎週書くつもりはないんだけどこの記法しょっちゅう使うくせに厳密な定義を知らなかったので(入力nに対する計算量くらいしか知らなかった)、ちょっとメモ。

形式的な定義： T(n) = O(f(n)) iff there exists constants c*n₀ > 0 such that T(n) ≦ c*f(n) for all c ≧ n₀
ここで問題になるのがc*n₀の存在で(実際これにはまった)、具体的には以下のような点n₀を指す。

ここはc = 2となりT(n)と2f(n)が交差する点がn₀となる。っでO(n)が適用されるのはn₀以降になるのが味噌。逆に言うと、n
< n₀まではT(n) = O(f(n))ではないということになる。
上記ではまったと書いたのだけど、これではまるのは例えば実際に計算量の増加率が高い順に並べるとかいうのをやった際に、nがかなり巨大にならないと反転しない場合(n₀=10^13とか)。

ここからは適当な感想というか、考察というかになるんだけど、例えばO(2^(2^log(n)))なアルゴリズムとO(n^2 * log(n))なアルゴリズムがあった場合(底は10とするw)、nが10^5までは前者で10^6からは(もう少し前からだが)は後者のアルゴリズムを使う必要があるということになる。定義的には前者の方が計算量が少ないことになるんだけど、現実的にはねぇっていう話。

ついでにアルゴリズム的には計算量少なくても使用する空間が大きいと実装した際には速度出ないということはまぁ言わずもがなだわね。divide and conquerって使用する空間のこと考えないと涙出るし。こういうの書くと自分は以下に計算機科学の基礎(とか理論)ができてないのかがわかって凹むが、まぁ凹んだ部分は今からでも埋めればいいかと開き直ることにする。

SRFI-13の紹介

(LISP Library 365参加エントリ)

SRFI-13は文字列操作を行う手続きを定義したSRFIです。SRFI-1と同様に超有名なSRFIなので知らない人はいないのではないでしょうか？今回はそんなSRFI-13の中から便利だけど意外と知られてなさそうな手続きを紹介します(RnRSに入っているものは除きます)。

string-tabulate
文字列の構築を行う手続きです。SRFI-1のlist-tabulateとほぼ同じですが、受け取る引数の順番が違います(先に手続きを受け取る)。以下のように使います。

;; make string range 0-255
(string-tabulate integer->char 256)
;; "\x0;\x1;\x2;\x3;\x4;\x5;\x6;\a\b\t\n\v\f\r\xE;\xF;\x10;\x11;\x12;\x13;\x14;\x15;\x16;\x17;\x18;\x19;\x1A;\x1B;\x1C;\x1D;\x1E;\x1F; !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~\x7F;\x80;‚ƒ„…†‡ˆ‰Š‹ŒŽ‘’“”•–—˜™š›œžŸ ¡¢£¤¥¦§¨©ª«¬­®¯°±²³´µ¶·¸¹º»¼½¾¿ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖ×ØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñòóôõö÷øùúûüýþ\xFF;"

;; the first argument doesn't have to be integer->string
(string-tabulate (lambda (i) #\a) 256)
;; "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

ランダムな文字列がほしいときとかに使えそうです。

string-take string-take-right
string-drop string-drop-right
SRFI-1にあるtake/dropの文字列版です。使い方を載せるまでもないくらいそのままです。

string-prefix? string-prefix-ci?
string-suffix? string-suffix-ci?
第一引数に与えられた文字列が第二引数に与えられた文字列の接頭文字列・接尾文字列かどうかを判別します。オプションで引数に与えられて文字列の開始位置及び終了位置を指定可能です。-ci?で終わるものは大文字小文字を無視します。

(string-prefix? "http" "http://localhost")
;; #t

(string-prefix? "https" "http://localhost")
;; #f

string-replace
名前のとおり文字列の置き換えを行います。対象文字列、置き換え文字列、開始位置、終了位置を受け取り、新しく文字列を生成します。(破壊的操作ではない)

(string-replace "Hello horrible Scheme" "beautiful" 6 14)
;; "Hello beautiful Scheme"

参照実装ではsubstringしてappendしてるだけだったりします。処理系によっては最適化しているものもあるかもしれません。(ちなみに、Sagittariusは参照実装のままです。組み込みにしてメモリの割付を減らしてもいいかなぁとは思ったりしますが。)

string-tokenize
文字列をトークンに切り出してリストとして返します。オプション引数としてトークンにする文字セットを受け取ることが可能です。 デフォルトの文字セットはchar-set:graphicです。

(string-tokenize "Hello world!!")
;; ("Hello" "world!!")

(string-tokenize "Helloaaaworld!!" (string->char-set "edlowrH"))
;; ("Hello" "world")

文字セットに関する手続きはSRFI-14で定義されています。

その他にもパディングやトリムといった手続きがあるので、興味があれば覗いてみてはどうでしょう？

To good to be true?

No, it wasn't!

I've wrote about implementing Karatsuba multiplication in previous post (sorry it's in Japanese). So I wanted to make all internal bignum multiplication to use it. Now I've modified expt to use it. Then next step is of course benchmark :)

Actually, it didn't make any performance better and it's quite difficult to compare because of the bug. So I've decided to compare with Mosh and Ypsilon, especially Mosh which is using GMP internally. So I wrote this piece of code;

(import (rnrs) (time))
(define-syntax dotimes
  (syntax-rules ()
    ((_ (var i res) . body)
     (do ((limit i)
          (var 0 (+ var 1)))
         ((>= var limit) res)
       . body))
    ((_ (var i) . body)
     (do ((limit i)
          (var 0 (+ var 1)))
         ((>= var limit))
       . body))
    ((_ . other)
     (syntax-violation 'dotimes
                       "malformed dotimes"
                       '(dotimes . other)))))

;; To avoid compile time constant folding
;; Sagittarius' compiler is a bit smarter than
;; the others :)
(define v (make-vector 1 512))

(time (dotimes (i 5000) 
        (let ((e (vector-ref v 0)))
          (expt #x123456789ABCDEF12 e))))

(display 'done) (newline)

And for Mosh, this was also required;

;; file name time.mosh.sls
(library (time)
    (export time)
    (import (mosh)))

Now, it's good to go. It took a bit time to figure out that Sagittarius compiler computes constant variable in compile time even though I implemented it. (That causes benchmark time always 0.00ms, so it was indeed 'too good to be true'. well but true though :-P)

The result was like this;

% ./build/sash.exe num.scm

;;  (dotimes (i 5000) (let ((e (vector-ref v 0))) (expt 20988295479420645138 e)))
;;  3.160898 real    3.2290000915527344 user    0.000000 sys
done

% ypsilon num.scm

;;  4.47794 real    4.524029 user    0.0 sys
done

% mosh num.scm

;;4.463438034057617 real 4.18 user 0.234 sys
done

As usual, I was very surprised with Ypsilon. It doesn't use GMP but the same time as Mosh. Anyway, Sagittarius' expt is faster than any others now. (could be before as well but incorrectly.)

カラツバ法

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の一つといえるかもしれません。