Syntax highlighter

2014-07-30

Industriaのテスト

IndustriaというR6RS Scheme用のポータブルなライブラリをご存知だろうか?Göran Weinholt氏が作成しているライブラリで、暗号器からX86のアセンブラまであるという巨大なライブラリである。(GitHubで最後にコミットがあったのが去年の8月なのでひょっとしたら開発が停止しているかもしれない。)リポジトリのweinholt/netディレクトリの中にあるtcp.slsからサポートしている、もしくは検討された処理系を知ることができる。以下がそのリスト。
  • Chez
  • Guile
  • ikarus
  • IronScheme
  • Larceny
  • Mosh
  • mzscheme (Racket)
  • Sagittarius
  • vicare (ikarusの後継)
  • Ypsilon
Biwa Schemeを除いたr6rs.orgに挙げられている処理系のリストほぼそのままである。可搬性のない部分のみをうまく切り出して、あとはR6RSの仕様どおりに書かれているということであろう。

以前このライブラリで定義されているマクロがうまく動かないことがあったこともあり、マクロ展開器のバグを直すたびくらいにテストを走らせていたのだが、ふと他の処理系ではどうなのかと思い試してみた。依存しているSRFIとCygwinという関係上、テストを走らせることが出来たのは以下の3つ。
  • Sagittarius (0.5.7 HEAD)
  • Mosh (0.2.7)
  • Racket (6.0.1 Windows x86_64)
GitHubのIssueに挙げたのだが、weinholt/assembler/x86.slsにあるfind-instruction-encoding手続きで定義されているbailoutが0引数で呼ばれている箇所があるため、直してやる必要がある。(でないとSagittariusはコンパイルエラーを挙げる。)毎回コマンドを叩くのもあほらしいので以下のようなスクリプトを用意した。
#!/bin/sh

usage() {
    echo "run-test.sh CONFIG"
    echo " CONFIG argument must be a shell script file"
    echo " contains $program and $load_flag"
}

if [ -f $1 ]; then
    . `pwd`/$1
    if [ "$?" != "0" ]; then
 echo "source command failed"
 exit -1
    fi
else
    usage;
    exit -1
fi

load_path=`pwd`

init $load_path

cd tests
for f in *.sps
do
    echo "Testing $f"
# hack for Windows racket...
    temp_file=$f.tmp.scm
    echo -n ';;' | cat - $f >  $temp_file
    echo "$program $load_flag $f"
    "$program" $load_flag $temp_file
    rm $temp_file
done
っで、以下の設定ファイルをそれぞれ用意。
# sash.conf
#!/bin/sh
# -*- mode:shell; coding:utf-8; -*-

program=/opt/bin/sash
load_flag=

init() {
load_flag=-L$1
}

# mosh.conf
#!/bin/sh
# -*- mode:shell; coding:utf-8; -*-

program=mosh
load_flag=

init() {
    load_flag='--loadpath='$1
}

# racket.conf
#!/bin/sh
# -*- mode:shell; coding:utf-8; -*-

program='/cygdrive/c/Program Files/Racket/plt-r6rs'
load_flag=

init() {
    load_flag="++path ../"
}
後は以下のようなコマンドで走らせる。
$ ./run-tests.sh sash.conf
テストを走らせた結果、意外にもSagittariusだけが全てのテストをパスするということが起きた。(これを書きたかった。)

Moshはpsyntaxのエラーがあったり、行末文字に起因すると思われるエラーがあったりでいくつかのテストが失敗する。またSRFI-25をサポートしていないのでライブラリがないというエラーも見受けられた。NMoshで走らせた場合はマクロ展開に起因するエラーは発生しないものの、通常のMoshと同様のエラーは発生する。

Racketは恐らく行末文字に起因するエラーが一つといくつかのテストが走ることさえなく落ちていくという現象が起きていた。

また、テスト完了までの時間もSagittariusが最速であった。以下がtimeコマンドを用いたテストケースの起動結果。(Cygwin 32 bit on Windows 7 64 bit Core 7i)
% time ./run-tests.sh sash.conf > sash.log 2>&1              [~/work/industria]
./run-tests.sh sash.conf > sash.log 2>&1  68.94s user 6.14s system 103% cpu 1:12.23 total

% time ./run-tests.sh mosh.conf > mosh.log 2>&1              [~/work/industria]
./run-tests.sh mosh.conf > mosh.log 2>&1  111.95s user 2.98s system 99% cpu 1:55.56 total

% time ./run-tests.sh racket.conf > racket.log 2>&1          [~/work/industria]
./run-tests.sh racket.conf > racket.log 2>&1  0.21s user 0.71s system 0% cpu 5:56.48 total
以外なのはRacketが5倍近く遅かったことである。

この結果を受けて着実に使える処理系になっていっているということと勝手に解釈することにする。

2014-07-27

みんな仲良く

ドラクエ4の作戦みたいだw 博愛主義とは違うんだろうけど、こういうのなんていうんだろう?

生きていれば、好きになれない人、どうにも馬が合わない人、関わりたくない人なんていくらでも出てくると思う。そんな人との付き合いが発生したときにどうするかという話。あくまで僕個人の話で、これが唯一絶対ではないし、一般論ですらないかもしれないけど・・・(どちらかと言えば単なる愚痴というか精神衛生を保つために何かしら吐き出すという行為に近いw)

こういう話を一般論でするのは多少危険なので、少しだけ具体的な状況を記しておくことにする。相手は、僕のことを散々人格否定した人。ちなみにそれに関しての謝罪はない。状況としては第三者から今のギクシャクした関係をなんとかできないかという話を振られた。これ以上具体的に書くのは辛いのでこれくらい。

個人的にはそんな話が第三者からでてくること自体がおかしな話だと思うのだが、まぁ理解できなくもない範囲であるし、こういった場合にどう答えるのかというのが趣旨なのでそれは置いておく。僕の答えはもちろん「No」である。できるわけがない。

感情的に言えば、相手は僕の人生の中に存在しないレベルでいてほしいくらいになっている。そもそも謝罪もされていないのだから相手方にそんな意思はないと捕らえるのが普通で、そんな人間との関係をどうこうするつもりはない。まぁ、謝罪されたからといって許すつもりは全然ないし、謝罪がほしいとすら思っていない。そもそも、存在してほしくないのだ。

理性的には、そうするメリットがない。幸か不幸か相手の状況を大体把握しているのと、相手から学ぶことはない(IT界隈の人ではないという意味)のと、相手が持つコネクションは僕にとって価値があるものではない。最悪の場合、デメリットが発生する可能性の方が高い(金の無心等)。打算的にみて一切の利がないのであれば、関係を改善する理由はない。

感情的にも理性的にも「No」という答えがでてくるのだ、それこそどうしようもない。こういった場合に求められるのは「大人の対応」ができるかどうかだけである。人それぞれ「大人の対応」の定義に違いがあるとは思うが僕の定義では、必要最小限の会話で波風を立てずただやり過ごす、である。必要最小限の会話なんてビジネスの場でないのであればそれこそ挨拶程度でいいし、それも他に誰かいるときだけでいい。道端でばったり出会ったときは無視すればいい。社交性が求められるのは自分と相手の第三者がいるときだけである。

綺麗ごとだけで生きていける人からすれば、僕の対応は間違っているのかもしれないけれど、残念ながらそんな幸せな世界では生きていないみたいである。全ての人と仲良くする必要はないし、全ての人を許す必要もない、嫌な人は変な波風を立てないように適当にあしらえばいい。あんまり褒められたものではないが、30余年の人生で学んだ処世術の一つである。

2014-07-26

SRFI-22の紹介

(LISP Library 365参加エントリ)

SRFI-22はSchemeスクリプトをUnix上で実行形式であるかのうようにして走らせるためのSRFIです(日本語難しいな・・・)。何を定義しているかといえば、スクリプトの先頭に現れた#! /usr/local/bin/sashのような形式のラインを無視することと、main手続きの呼び出しです。

具体的な例を見てみましょう。(この例では/usr/local/binにSagittariusがインストールされていることを前提としています。)
#! /usr/local/bin/sash

(import (rnrs))

(define (main args)
  (display "hello world!") (newline))
このスクリプトを仮にsrfi-22.scmとして保存し実行権を付与すれば、Unixライクなシェル上で以下のように実行することができます。
$ ./srfi-22.scm
このSRFIで重要になるのは、実は#!の部分だけで、それ以外は処理をトップレベルにおいてしまえば動きます。(R5RS時代にcommand-line手続きがなかったのであればmainの意味は大きいとは思いますが、R6RS以降であれば単なるショートカットくらいの意味しかないでしょう。)

個人的にはもっともよく使っているSRFIの一つですが、割と賛否両論あるみたいです。

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

2014-07-25

R7RS implementation differences

Recently, Gauche 0.9.4 has been out and it now supports R7RS. Now, I have couple of R7RS implementation in my hand, like followings;
  • Sagittarius (of course)
  • Chibi Scheme
  • Gauche
  • Foment
Well, only 3. I've also tried foment and picrin which are is supposed to be R7RS implementations however it didn't work on Cygwin which is my main environment. (Sorry, I'm Windows user...)

July 28th 2014: Foment compiled on VC2010 has been added.

The purpose of this article is to show some corner cases of R7RS. Sagittarius is R6RS/R7RS and Chibi and Gauche are R5RS/R7RS implementation so there should be something but how much? So I've prepared this test script.
;; #!r7rs is supported only Gauche and Sagittarius...
;; #!r7rs
(import (scheme base)
        (scheme write)
        (scheme read)
        (scheme file)
        (scheme inexact)
        (scheme lazy))

(define (print . args) (for-each display args) (newline))

;; string
;; allow #\null in string?
(print "String range")
(write "abc\x0;def")(newline)

;; file
;; are binary and textual port separated?
(print "Port separation")
(define-syntax check-port
  (syntax-rules ()
    ((_ opener reader data)
     (let ((in (opener data)))
       (guard (e (#t (print "ERROR: "(error-object-message e))
                     (close-input-port in)))
         (print 'opener ":" 'reader)
         (reader in)
         (close-input-port in))))))

;; files
(check-port open-binary-input-file read-char "r7rs-comp.scm")
(check-port open-binary-input-file read-u8 "r7rs-comp.scm")
(check-port open-input-file read-char "r7rs-comp.scm")
(check-port open-input-file read-u8 "r7rs-comp.scm")
;; memory
(check-port open-input-bytevector read-u8 #u8(0 1 2 3))
(check-port open-input-bytevector read-char #u8(0 1 2 3))
(check-port open-input-string read-u8 "abc")
(check-port open-input-string read-char "abc")

;; error object
(print "Error object")
(define-syntax check-error
  (syntax-rules ()
    ((_ pred expr)
     (guard (e (#t (print 'pred ":" (pred e))))
       expr))))
(check-error error-object? (car 'a))
(check-error read-error? (read (open-input-string "#0#")))
(check-error file-error? (open-input-file "this doesn't exist.txt"))

(define-syntax check
  (syntax-rules ()
    ((_ expr)
     (guard (e (#t (print 'expr ":" (error-object-message e))))
       (print 'expr ":" expr)))))

;; sqrt
(print "Procedures")
(check (sqrt 4))

;; promise
(print "Promise")
(check (+ (delay (* 3 7)) 13))
The script is constructed based on what I thought could be a corner case. Mostly port related procedures and error object. Then this is the output;
Sagittarius
String range
"abc\x0;def"
Port separation
open-binary-input-file:read-char
ERROR: textual port required, but got #<file-binary-input-port r7rs-comp.scm>
open-binary-input-file:read-u8
open-input-file:read-char
open-input-file:read-u8
ERROR: "binary-port" required, but got #<transcoded-textual-input-port r7rs-comp.scm utf8-codec>
open-input-bytevector:read-u8
open-input-bytevector:read-char
ERROR: textual port required, but got #<bytearray-binary-input-port>
open-input-string:read-u8
ERROR: "binary-port" required, but got #<string-textual-input-port>
open-input-string:read-char
Error object
error-object?:#t
file-error?:#t
Procedures
(sqrt 4):2
Promise
(+ (delay (* 3 7)) 13):"number" required, but got (13 #<<promise> 0x80599100>)
---
Chibi Scheme
String range
"abc\x00;def"
Port separation
open-binary-input-file:read-char
open-binary-input-file:read-u8
open-input-file:read-char
open-input-file:read-u8
open-input-bytevector:read-u8
open-input-bytevector:read-char
open-input-string:read-u8
ERROR: not a binary port
open-input-string:read-char
Error object
error-object?:#t
read-error?:#t
file-error?:#t
Procedures
(sqrt 4):2
Promise
(+ (delay (* 3 7)) 13):invalid type, expected Number
---
Gauche
String range
"abc\0def"
Port separation
open-binary-input-file:read-char
open-binary-input-file:read-u8
open-input-file:read-char
open-input-file:read-u8
open-input-bytevector:read-u8
open-input-bytevector:read-char
open-input-string:read-u8
open-input-string:read-char
Error object
error-object?:#t
read-error?:#t
file-error?:#t
Procedures
(sqrt 4):2
Promise
(+ (delay (* 3 7)) 13):operation + is not defined between 13 and #<promise 0x80445480>
Following it the output from Foment
String range
"abc^@def"
Port separation
open-binary-input-file:read-char
ERROR: read-char: expected an open textual input port
open-binary-input-file:read-u8
open-input-file:read-char
open-input-file:read-u8
ERROR: read-u8: expected an open binary input port
open-input-bytevector:read-u8
open-input-bytevector:read-char
ERROR: read-char: expected an open textual input port
open-input-string:read-u8
ERROR: read-u8: expected an open binary input port
open-input-string:read-char
Error object
error-object?:#t
file-error?:#t
Procedures
(sqrt 4):2
Promise
(+ (delay (* 3 7)) 13):+: expected a number
Hmmm, not much difference than I expected. The only difference is port related procedures. Gauche is the most tolerant then Chibi, Sagittarius is the strictest one. Well, Sagittarius is an R6RS implementation and it's required to be. Gauche's behaviour is a bit too flexible to me but still consistent. Chibi looks a bit tricky to me. It actually reject to pass texutal port to read-u8 however read-char accept binary port.

Even though, R7RS explicitly says that implementation may reject #\null in strings however none of implementations does it. Interestingly, Foment doesn't support writing #\null. So it writes as it is. It would be better to consider that it doesn't support properly or particially supported. So to write portable string library, users should not depend on null character.
 
I thought error object could have some difference but not really (or the test script doesn't cover that much).

I was hoping one of the implementations (Chibi or Gauche though) have implicit forcing but the result was none of them.

The difference is small and it's avoidable if users are consistent. So if you write R7RS scripts and it could be run on Sagittarius, then most likely it would run on the other implementations.

2014-07-24

バグは寝かせてみるといい

かなり長めに寝かせていたバグの糸口を掴んだのでメモ。

問題になるのは以下のようなコード
(import (rnrs))
(define-syntax wrap-let
  (syntax-rules ()
    ((_ expr)
     (let-syntax ((foo (lambda (x) (syntax-case x () ((_) #'expr)))))
       (foo)))))

(define-syntax wrap
  (lambda (x)
    (syntax-case x ()
      ((_ expr)
       #'(let ((temp expr))
           (wrap-let (car temp)))))))

(wrap '(a b c))
これがなぜ問題になるのかというのが重要で、展開された後を見るとなんとなく答えが出てくる。以下が展開形コードのイメージ。
(let ((temp.0 '(a b c)))
  (let-syntax ((foo (lambda (x) (syntax-case x () ((_) #'(car temp.0))))))
    (foo)))
問題はここからで、let-syntaxの中にある#'(car temp.0)が原因。Sagittariusのマクロ展開器は現状syntax-caseのパターン及びテンプレートを全てリネームする。さらにsyntaxが展開されるときにもリネームする。そうすると、元々のtemp.0は持っていない構文情報を付加されてしまい、結果的に一意の識別子になってしまう。

ならば、テンプレート変数と分かっている場合はリネームしなければいいだけのように見えるのだが、そうも行かないのが面倒なところ。テンプレート変数はリネームされなければならないのだ。とりあえずマクロ展開形が局所マクロを含んでいるというのは(おそらく)なんとか分かる気がするので、その場合のみを特殊扱いするという感じでいこうかと思う。既に不安材料が見えているのでそれが正しいのかは今一よく分からないのではあるが・・・

このバグ、6ヶ月くらい寝かせてあったのだが、最近になって気運が高まってきたのか原因が掴めるところまできた。どうやら困難なバグほど寝かせておいた方が角が取れて消化しやすくなるらしい。

2014-07-22

packratの機能追加

SagittariusにはChicken由来のpackratライブラリがあるのだが、このライブラリ数量指定子が使えなくて非常に使い出が悪い。例えば、0個以上の何かを取るというのを書くのに以下のようにする必要がある。
(import (rnrs) (packrat))

(define (generator tokens)
  (let ((stream tokens))
    (lambda ()
      (if (null? stream)
          (values #f #f)
          (let ((base-token (car stream)))
            (set! stream (cdr stream))
            (values #f base-token))))))

(define quantifier (packrat-parser
                    top
                    (top ((vs <- item*) vs))
                    (item* ((i <- item i* <- item*) (cons i i*))
                           (() '()))
                    (item (('+) '+))))


(let* ((q (generator '((+) (+) (+))))
       (r (quantifier (base-generator->results q))))
  (parse-result-semantic-value r))
;; -> (+ + +)
BNFで書かれた定義を持ってくる際に数量指定子がないというのは非常に面倒で、パーサを書くのを何度も何度も億劫にしてくれた。quantifierの定義はこう書けた方が直感的である。
(define quantifier (packrat-parser
                    top
                    (top ((vs <- (* item)) vs))
                    (item (('+) '+))))
ずっとほしいと思っていたのだが、そろそろあった方がいいなぁという気運が高まってきたので、えいや!っと中身を読むことにした。

中身を読んで分かったのは、複数回マッチするというのを何とかするAPIが足りていないのが原因ぽかったので、こんなのを追加してマクロ側にも手を入れてみた。
(define (packrat-many parser n m k)
  (lambda (results)
    (define (>=? many max) (and max (>= many max)))
    (define (return-results vs result)
      ;; if we inline map then for some reason step on a bug...
      (let ((vals (map parse-result-semantic-value vs)))
        (merge-result-errors ((k vals)
                              (parse-result-next result))
                             (parse-result-error result))))
    (when (and (zero? n) (eqv? n m))
      (error 'packrat-many "both min and max are zero" n m))
    (let loop ((i 0) (vs '()) (s #f) (results results))
      (if (>=? i m)
          (return-results (reverse! vs) s)
          (let ((result (parser results)))
            (cond ((parse-result-successful? result)
                   (loop (+ i 1) (cons result vs) result
                         (parse-result-next result)))
                  ((<= n i)
                   (return-results (reverse! vs) result))
                  (else result)))))))
なぜか、インライナーのバグを踏んだのはまぁご愛嬌ということで・・・
マクロの方は+、*、?に加えてマッチ回数を指定できる=も入っている。長いのでここには載せない。これで多少便利になる気がする。

2014-07-14

ライブラリの作られるタイミング

Chaton Gauche部屋から流れてきたこれ
REPLからエラーの起きるライブラリを繰り返しr7rs#importすると,エラーが起きなくなります.

;; temp.scm
(define-library (temp)
  (begin
    (f)))

;; REPL
gosh> (import (temp))
*** ERROR: Compile Error: Compile Error: unbound variable: f

"(standard input)":1:(import (temp))

Stack Trace:
_______________________________________
  0  (eval expr env)
        At line 179 of "/usr/local/share/gauche-0.9/0.9.4-rc2/lib/gauche/interactive.scm"
gosh> (import (temp))
#<undef>
gosh[r7rs.user]>
全く同じ問題がSagittariusでも起きる。原因も分かっていて、コンパイラがコンパイル時にライブラリを作ってしまうけど、エラー自体はランタイムで起きるのでimportが呼ばれた際にはライブラリはあるものとして扱われてしまうから。

あまりうまい解決策が思いつかないんだけど、とりあえずぱっと思いついたのがVM側で何とかするというもの。っが、実際に実装しかけては無理だなぁということが分かってしまったので破棄。案としては、evalの中身をwith-exception-handlerで囲ってしまい、エラーが起きた際に現在のライブラリと保存されたライブラリが異なっていたら現在のライブラリを破棄するというもの、だったのだが、これはライブラリの変更がインストラクションでのみ発生するということに依存している上に、それ以外の方法で変更することが可能なので火を見るより明らかにだめだろうという・・・

次に思いついたのが、ライブラリのコンパイル全体をwith-exception-handlerで囲ってしまうとうもの。実際の手順としては以下のようになる予定。
  • ダミーのライブラリを作る
  • 実行コードをwith-exception-handlerで囲う
  • コンパイル及び実行
    • エラーがあればダミーを破棄
    • なければ正式名で作成及び中身をコピー
こっちはまだ実装をしていないのだが、見えているだけで以下のデメリットががが
  • エラーが存在しない場合でも呼ばれる
    • キャッシュがでかくなる
  • 余分な手続きを2つ作る必要があるため、性能に影響が出そう
  • コピーが重い
  • マクロ展開がライブラリを使用しているのだけれど・・・
まぁ、ダミーのライブラリを作る必要はないかもしれないのでそこは下2つは無視できるかもしれないが。

REPLでしか起きない問題なので多少以上にやる気が低いのも問題だろう・・・

2014-07-11

SRFI-19の紹介

(LISP Library 365参加エントリ)

SRFI-19は日時を扱うライブラリです。関連性が強いのでSRFI-18と同じ著者だと思っていたのですが、実は違うということに今日気づきました。新たな発見です。

このSRFIでは時間と日付の両方を扱います。まずは簡単に使い方を見てみましょう。
(import (rnrs) (srfi :19))
;; simple stop watch
(define-syntax time
  (syntax-rules ()
    ((_ expr)
     (let* ((s (current-time))
            (r expr)
            (e (current-time)))
       (display "execution time: ")
       (display (time-difference e s))
       (newline)
       r))))

(define (tak x y z)
  (if (not (< y x))
      z
      (tak (tak (- x 1) y z)
           (tak (- y 1) z x)
           (tak (- z 1) x y))))

(time (tak 21 14 7))
;; prints
;; <time-duration 0.0000000>
;; -> 14
どのような形で表示されるかは処理系依存なので、値を真面目に取得するにはtime-secondやtime-nanosecond等のアクセサを使います。

current-timeで現在の時間オブジェクトを取得するのがよく使われると思いますが、計算して時間を求めることも可能です。その際にはmake-time及び計算用の手続きを使います。
(define one-hour (make-time time-duration 0 3600))
(let ((c (current-time)))
  ;; I don't want to do anything for an hour...
  (thread-sleep! (add-duration c one-hour)))

make-timeは最初に時間タイプを受け取ります。このSRFIでは以下のタイプが定義されています。
  • time-duration
    時間の差分を扱います
  • time-monotonic
    Monotonicな時間を扱います
  • time-process
    現在のプロセス時間を扱います
  • time-tai
    TAI時間を扱います
  • time-thread
    現在のスレッド時間を扱います
  • time-utc
    UTC時間を扱います
処理系によってはプロセス時間とスレッド時間はサポートしていない可能性があります。

日付を扱う手続きのいくつかを見てみましょう。
(current-date)
;; -> date object

(date->string (current-date))
;; -> "Sat Jul 12 19:03:24+0100 2014"

(date->string (current-date) "~Y-~m-~d")
;; -> "2014-07-12"

(string->date "2014-07-12" "~Y-~m-~d")
;; -> date object

(date->julian-day (current-date))
;; -> 7075728736710773/2880000000

(julian-day->date 7075728736710773/2880000000)
;; -> date object
上記以外にも日付⇔時間、修正ユリウス暦⇔日付or時間、TAI時間⇔UTC時間等の変換手続きが用意されています。

個人的に日付⇔文字列の変換は拡張性が無く、またXSD等が採用しているISO-8601のフォーマットのタイムゾーン形式に対応していなかったりと、多少使いにくい点があります。日付のアクセサは用意されているのでその辺は自前で書けということなのかもしれませんが・・・

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

2014-07-09

Unicode character set

I'm implementing SRFI-115 on top of builtin regular expression engine adding missing feature to implement and struggling with its Unicode requirement. Even though the SRFI says Unicode support is an optional feature and those Unicode related SREs have no effect if it's not supported.

However I don't like taking conservative way. It's always better to implement full feature so that users don't have to consider implementation's limitation. Now the problem is how and compatibility with built in engine. If Unicode is supported then SRFI requires, for example, alphabetic to match L, Nl and Other_Alphabetic characters. Current builtin engine only considers ASCII for named character sets (e.g. [[:alpha]] or even \w). Well there are bunch of options to resolve this but followings are, I think, rational;
  1. Support these only in this SRFI
  2. Builtin engine should support Unicode as well
Option #1 is the easier way  to do it. Option #2 would break backward compatibility so I need to be very careful especially \w. I believe I've already wrote bunch of code which depend on the fact that it only matches ASCII characters.

Let's think about #1 first. This must be relatively easy so that I just need to convert the named character set to Unicode character set or ASCII character set depending on the expression. The problem, if I dare to call, is that I need to prepare 2 types of the same named character sets; one of them is already there, though. So all what I need are adding full Unicode character sets and switch them according to the context. Easy isn't it?

Now option #2. The problem is backward compatibility. There are 2 main possible breaking compatibility issues; one is regular expression itself and the other one is SRFI-14. The whole point to do this option is make my life easier for later stage to merging Unicode character sets to predefined ones such as char-set:letter. For regular expression engine, I probably just need to make sure by default it's ASCII context. However I'm not even sure whether or not I wrote a piece of code with SRFI-14 that depending on ASCII character set. (quick grep showed I have, so if I merge it then I need to check all code...)

So if I take #2 then the following things need to be done;
  • Separating Unicode/ASCII context on builtin regular expression engine
  • Adding full unicode set to builtin character sets (including SRFI-14)
  • Checks if there is a piece of code which depends ASCII charset
I feel somewhat it doesn't worth but cleaner than #1. Well, it's always good to have some challenges so I should take the harder way.

2014-07-05

SRFI-18の紹介

(LISP Library 365参加エントリ)

SRFI-18はマルチスレッドを扱うライブラリです。POSIXが採用しているスレッドモデルとほぼ同じなのでなれている人はほぼ同じように使えます(条件変数の扱いが多少違うのと、ミューテックスが破棄された状態を持つのが違う点かと思います)。

使い方を見てみましょう。以下は簡単なスレッドの作成です。
(import (srfi :18))
(let ((t (thread-start! (make-thread (lambda () (write 'a))))))
  (write 'b)
  (thread-join! t))
;; -> <unspecified>
;; prints ab or ba
スレッドの作成にはmake-thread、開始にthread-start!、終了を待つのにthread-join!を使います。

スレッドを使っていると数秒止めたくなることもあるでしょう。そんなときにはthread-sleep!を使います。
(import (srfi :18))
(thread-sleep! 1) ;; sleep 1 second
一応スレッドの停止(破棄)もサポートされています。このオペレーションは非常に危険なので注意して使えという注釈も付いています。
(thread-terminate! (current-thread)) ;; -> never return
thread-yieldは他のスレッドに処理時間を明け渡す手続きです。非常に重たい処理を行うスレッドが可能な限りCPUの空き時間に処理を行いたい場合などに使えます。
(import (rnrs) (srfi :18))

(define m (make-mutex))
(define (do-something-else) (print 'something-else) (thread-sleep! 1))

(let ((t (make-thread (lambda ()
                        ;; a busy loop that avoids being too wasteful of the CPU
                        (let loop ()
                          (if (mutex-lock! m 0) ; try to lock m but don't block
                              (begin
                                ;; Do some heavy process
                                (display "locked mutex m")
                                (mutex-unlock! m))
                              (begin
                                (do-something-else)
                                (thread-yield!) ; relinquish rest of quantum
                                (loop))))))))
  (mutex-lock! m 0)
  (thread-start! t)
  (thread-sleep! 1)
  (mutex-unlock! m))
僕自身はそんなミッションクリティカルな処理を書いたことが無いので使ったことのない手続きの一つですが・・・

次にミューテックス及び条件変数の使い方を見てみましょう。ミューテックスを扱う手続きは既に上記の例で出ていますが、ロックを書けるのにはmutex-lock!、外すのにはmutex-unlock!を使います。また、このSRFIで採用しているモデルでは条件変数はシグナルを送る以外の手続きを持っていないので、pthreadのpthread_cond_waitのようなことをするにはmutex-unlock!を使います。mutex-unlock!のオプショナル引数が条件変数を受け取った場合には、pthread_cond_waitとほぼ同様の動作をします。ただし、ミューテックスはロックされていないので、注意が必要です。

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

2014-07-01

You gotta LOVE side effect...

Recently I've implemented the procedure that checks if given closure is transparent/no side effect. Then I thought that's cool so that compiler can eliminate some of no-side-effect expression or compute the result in compile time if the given argument is constant variable. Now I've got a problem.

To describe it, here is the small piece of code which causes the problem.
(import (rnrs))

(define label-counter (lambda () 0))
(define (new-lbl!) (label-counter))

(define (change-label-counter)
  (set! label-counter (lambda () 1)))

(define (print . args) (for-each display args) (newline))

(let ((lbl (new-lbl!)))
  (print lbl))
(change-label-counter)
(let ((lbl (new-lbl!)))
  (print lbl))
This should print 0 then 1. Well, it doesn't seem there is a problem except the change-label-counter. The defined label-counter is obviously constant so it'd be inlined in the new-lbl!. Now, the change-label-counter sets the new value to label-counter, here comes the problem. The new-lbl! has already compiled with inlined value and just returns 0 so change-label-counter doesn't have any effect to it. Then the result value would be always 0.

If these procedures are defined in a library, then Sagittarius compiler could check if the global defined variable would be changed or not however because this is defined in a script it can't and just tries to inline so that the target procedure looks constant.

What I can do is;
  • Don't inline them if it's in script.
  • Forbit set! for globally defined variable.
    • Make impossible to run some of R5RS code (e.g. Gambit benchmark's compiler)
  • Read all expression and wrap with a library before compiling a script
    • I can already see the horrible future...
Hmmmm, I guess I need to disable this check for now...

2014-06-30

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 #&lt;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 #&lt;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.

2014-06-28

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

2014-06-15

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

2014-06-14

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

2014-05-30

Shibuya.lisp meetupに行ってきた

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

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

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

僕の。


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

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にもっと日本から人がくればいいだけの話ともいう。(行ってないけどw)

2014-05-28

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

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

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

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

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

2014-05-12

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

2014-05-11

プロのプログラマ

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

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

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

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

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

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

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

2014-05-09

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