カラツバ法

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