Hobbit Scheme to C compiler for SCM 犬飼大 (dai inukai)

2003年 8月11日月曜日 15:43:32 JST

hobbitの概要

hobbitはSchemeコードをSCMのネイティブコードであるCコードに変換してSCMに組み込むためのトランスレータで、SCMディストリビューションに含まれています。
Lambda-lifting as an optimization for compiling Scheme to C (SchemeをCにコンパイルする場合の最適化の一方法としてのラムダ持ち上げ)として開発され、もともとは



	  (hobbit "Schemeソースファイル" ...)

のように使用して、6回のパスででSchemeソースコードをCソースコードに変換したテキストファイルを出力するものでした。現在はSCMの'compile' 環境に統合されて、コンパイル済みオブジェクトファイルを出力できるようになっています。

手続きが参照し、手続き内部で定義されていない変数は自由変数 (free variable) と呼ばれます。自由変数を消去して変数の値をローカルに決定できるようにするために、hobbitは再帰的にラムダ持ち上げ(lambda-lifting)を使用してローカルな手続きをトップレベルの定義まで持ち上げます。その際ラムダ持ち上げできない変数が手続き内にある場合は最適化の程度が制限されます。

SCMのSchemeプリミティブはC関数で実現されていますが、Schemeで作成される手続きは、手続き本体と手続きが作成された環境を合わせ持つクロージャとして実現されます。Scheme手続きが評価されるときには、プログラム内で手続きが評価される環境(コンティニュエーション)が参照されます。Schemeで書かれた手続きをCコードとして実行する場合は、手続きと環境を渡してapply関数を呼び出す必要があり、これは計算を伴う作業ですので、Scheme手続きを単純にCコードに移し変えただけではオーバヘッドが大きくなります。hobbitはSchemeで作成された手続きをC関数に写像するにあたって環境渡しを避け、 Scheme手続きの構造を保ったままで可能な限り裸のC関数呼び出しに変換します。hobbitはその他にも、Schemeプログラムを可能な限り計算量が少ないCプログラムに近づけるような最適化を行ないます。詳細はhobbit.info参照。

hobbitは、r4rsのキーワードとSCMの拡張キーワードの一部を認識します。hobbitが認識するSchemeキーワードは、hobbit.scmの *standard-s->c-fun-table*などで確認できます。

SCMでhobbitを使う

hobbitの使い方には2通りあります。


	         (require 'compile)
	         (compile-file "Schemeソースファイル1" ...)

ダイナミックロード可能なオブジェクトファイルが作成されます。


	          (require 'hobbit)
	          (hobbit "Schemeソースファイル1" ...)

SCMに組み込み可能なCソースコードが出力されます。

hobbitのベンチマークプログラムのコンパイル


		(define (pi n  . args)
		  (let* ((d (car args))
	                 (r (do ((s 1 (* 10 s))
		                 (i 0 (+ 1 i)))
		                 ((>= i d) s)))
	                 (n (+ (quotient n d) 1))
	                 (m (quotient (* n d 3322) 1000))
	                 (a (make-vector (+ 1 m) 2)))
                    (vector-set! a m 4)
                    (do ((j 1 (+ 1 j))
	                 (q 0 0)
	                 (b 2 (remainder q r)))
	               ((> j n))
                       (do ((k m (- k 1)))
	                   ((zero? k))
	                 (set! q (+ q (* (vector-ref a k) r)))
	                 (let ((t (+ 1 (* 2 k))))
	                    (vector-set! a k (remainder q t))
	                    (set! q (* k (quotient q t)))))
                       (let ((s (number->string (+ b (quotient q r)))))
	                  (do ((l (string-length s) (+ 1 l)))
	                      ((>= l d) (display s))
	                    (display #\0)))
                       (if (zero? (modulo j 10)) (newline) (display #\ )))
                     (newline)))

書込み権限があるディレクトリであればどこに保存しても構いません。SCMをコンパイルしたディレクトリにおけば特別なことをせずにコンパイルできますが、後々いろいろなSchemeプログラムをコンパイルしてみたいので、例えば $HOME/bench/bench-pi.scmとしてファイルを保存するとします。

ダイナミックロード可能なSCMにロードできるモジュールを作成するためには、SCMをコンパイルした元のディレクトリにあるものと同じscm.h、scmfig.hが必要です。モジュールを Schemeソースコードから作成する場合は、更にscmhob.hも必要です。シンボリックリンクをはるか、それができなければファイルをコピーしておきます。SCMをコンパイルしたディレクトリを$HOME/scmとすると次のようになります。


		    ln -s $HOME/scm/scm.h $HOME/scm/scmfig.h $HOME/scm/scmhob.h $HOME/bench

以後の作業は$HOME/benchをカレントディレクトリとして説明します。

bench-pi.scmをコンパイルします。


		    % cd $HOME/bench
		    % scm -rcompile -e'(compile-file "bench-pi.scm")'

                    Starting to read bench-pi.scm

                    Bounded integer (fast) arithmetic assumed.

                    ** Pass 1 completed **
                    ** Pass 2 completed **
                    ** Pass 3 completed **
                    ** Pass 4 completed **
                    ** Pass 5 completed **
                    ** Pass 6 completed **

                    C source file bench-pi.c is built.
                    C header file bench-pi.h is built.

                    ; Scheme (linux) script created by SLIB/batch Sun Jul 20 01:04:28 2003
                    ; ================ Write file with C defines
                    (delete-file "scmflags.h")
                    (call-with-output-file
                      "scmflags.h"
                      (lambda (fp)
                        (for-each
                          (lambda (string) (write-line string fp))
                          '("#define IMPLINIT \"Init5d8.scm\""
                            "#define BIGNUMS"
                            "#define FLOATS"
                            "#define ARRAYS"
                            "#define DLL"))))
                    ; ================ Compile C source files
                    (system "gcc -O2 -fpic -c -I/usr/local/lib/scm/ bench-pi.c")
                    (system "gcc -shared -o bench-pi.so bench-pi.o -lm -lc")
                    (delete-file "bench-pi.o")
                    ; ================ Link C object files
                    (delete-file "slibcat")

このディレクトリにbench-pi.soが作成されます。

性能を見てみます。使ったマシンはCeleron 500MHz、メモリ512MbのDebian Linux boxです。SCMはMakefileで udscm5として作成されたもので、起動オプション-no-init-file を指定して、ホームディレクトリの ScmInit.scmを読み込まないようにしています。出力される bench-pi.cプログラムではSchemeの多倍長演算を使用しませんので、丸め誤差を避けるために出力桁数を3桁にしています。最後の例は、SCMディストリビューションに含まれる、最初からCでハンドコードしたプログラムpi.cの実行結果です。


		    % uname -a
		    Linux daip 2.4.18 #1 2003年 4月 12日 土曜日 03:34:49 JST i686 unknown
		    % scm --version
		    scm 5d8
                    ...
                    % /usr/bin/time scm -no-init-file -lbench-pi.scm -e'(pi 4000 3)'
                    003 141 592 653 589 793 238 462 643 383
                    ...
                    227 211 166 039 
                    94.51user 0.04system 1:36.85elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k
                    0inputs+0outputs (164major+101minor)pagefaults 0swaps

                    % /usr/bin/time scm -no-init-file -lbench-pi.so -e'(pi 4000 3)'
                    003 141 592 653 589 793 238 462 643 383
                    ...
                    227 211 166 039 
                    3.13user 0.00system 0:03.18elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k
                    0inputs+0outputs (168major+102minor)pagefaults 0swaps

                    % cc -O2 -opi pi.c
                    % /usr/bin/time ./pi 4000 3
                    003  141  592  653  589  793  238  462  643  383
                    ...
                    227  211  166  039  
                    1.68user 0.00system 0:01.82elapsed 91%CPU (0avgtext+0avgdata 0maxresident)k
                    0inputs+0outputs (96major+17minor)pagefaults 0swaps

jfilter.scmのコンパイル

jfilter ホームページ

jfilterは、


		(cv-file "入力ファイル" "出力ファイル" 入力コード 出力コード #t #f #f #t)

jfilter.scmにはhobbitが理解しないコードとラムダ持ち上げできないコードが入っていますので、その部分をコメントアウトします。


		*** jfilter.scm~	Sat Jul 19 05:52:37 2003
		--- jfilter.scm 	Sun Jul 20 05:15:32 2003
		***************
		*** 22,33 ****
		;;
		;; The BIT twiddling operations are provided by SLIB:LOGICAL
		;; Comment out when compiling with HOBBIT
		! (require 'logical)
		;;
		;; logsleft and logsright are defined in scmhob.scm
		;; Comment out when compiling with HOBBIT
		! (define (logsleft x y) (ash x y))
		! (define (logsright x y) (ash x (- 0 y)))
		;;
		;;
		;; Pocedures helping to convert 3 different Japanese character codes
		--- 22,33 ----
		;;
		;; The BIT twiddling operations are provided by SLIB:LOGICAL
		;; Comment out when compiling with HOBBIT
		! ;(require 'logical)
		;;
		;; logsleft and logsright are defined in scmhob.scm
		;; Comment out when compiling with HOBBIT
		! ;(define (logsleft x y) (ash x y))
		! ;(define (logsright x y) (ash x (- 0 y)))
		;;
		;;
		;; Pocedures helping to convert 3 different Japanese character codes
		***************
		*** 1235,1250 ****
		;; and returns the converted string.
		;; The bridge between file and string for cv-string
		;; comment out when compiling with hobbit
		! (require 'string-port)
		;;
		;; comment out the following procedure when compiling with HOBBIT
		;; and execute it by SCM interpreter
		;;
		! (define (cv-string s from-code to-code)
		!   (call-with-output-string
		!     (lambda (outport)
		!       (call-with-input-string s
		!         (lambda (inport)
		!           (jfilter:cv inport outport from-code to-code #t #f #t))))))
  
		(provide 'jfilter)
		--- 1235,1250 ----
		;; and returns the converted string.
		;; The bridge between file and string for cv-string
		;; comment out when compiling with hobbit
		! ;(require 'string-port)
		;;
		;; comment out the following procedure when compiling with HOBBIT
		;; and execute it by SCM interpreter
		;;
		! ;(define (cv-string s from-code to-code)
		! ;  (call-with-output-string
		! ;    (lambda (outport)
		! ;      (call-with-input-string s
		! ;        (lambda (inport)
		! ;          (jfilter:cv inport outport from-code to-code #t #f #t))))))
  
		(provide 'jfilter)

jfilter:cvは引数を8つとります。最後の引数に#tを渡すと、全角英数字があった場合にそれを半角英数字に変換します。


		% scm -r compile -e'(compile-file "jfilter.scm")'

jfilter.soが作成されます。

性能を比較してみます


		    %/usr/bin/time scm -ljfilter.scm -e'(cv-file "/usr/share/xemacs21/mule-packages/etc/mule/FAQ-Mule.ja" "./FAQ-Mule.ja.eucj" #f #f)'
		    2.13user 0.03system 0:02.16elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
		    0inputs+0outputs (252major+499minor)pagefaults 0swaps

		    %/usr/bin/time scm -ljfilter.so -e'(cv-file  "/usr/share/xemacs21/mule-packages/etc/mule/FAQ-Mule.ja" "./FAQ-Mule.ja.eucj" #f #f)'
		    0.23user 0.00system 0:00.23elapsed 96%CPU (0avgtext+0avgdata 0maxresident)k
		    0inputs+0outputs (228major+80minor)pagefaults 0swaps

wbモジュールを使って郵便番号データベースを作るために、 SHIFT_JISコードの郵便番号簿をeuc-jpコードに変換してみます。郵便番号簿は日本郵政公社のページからダウンロードできます。ダウンロードして展開した後のファイルken_all.csvは12,135,822バイトあります。 jfilterはこのファイルの文字コードを自動判定できませんので、シフトJISから日本語eucへの変換を強制的に指定しています。
単一引用符はscmのコマンド行オプション-eに渡す式を囲む文字に使用され、したがってコマンド行から渡す式には略記'を使用できませんので、評価させる手続き内ではquoteを使用しています。最後の引数を#tにしていますので、ファイル内の全角英数字は半角英数字に変換されます
```
		    %/usr/bin/time scm -no-init-file -ljfilter.scm -e'(cv-file "ken_all.csv" "ken_all.csv.eucj" (quote sjis) (quote eucj) #t #f #f #t)'
		    481.77user 0.69system 8:13.60elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k
		    0inputs+0outputs (165major+187minor)pagefaults 0swaps

		    %/usr/bin/time scm -no-init-file -ljfilter.so -e'(cv-file "ken_all.csv" "ken_all.csv.eucj"  (quote sjis) (quote eucj) #t #f #f #t)'
		    24.77user 0.44system 0:25.60elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k
		    0inputs+0outputs (174major+90minor)pagefaults 0swaps

		
```

SLIBライブラリシステムへの組み込み

SCMは(implementation-vicinity)に、ライブラリのカタログファイルimplcatとslibcatを作成します。implcatはSchemeを実装した処理系依存のライブラリで、mkimpcat.scmで作成されます。 SCM以外の処理系からSLIBを使用している場合はimplcatは存在しないかも知れません。slibcatは実装に依存しないSLIBパッケージのカタログファイルで、mklibcat.scmで作成されます。ダイナミックロードライブラリをSLIBに組み込む場合はmkimpcat.scmを、 Schemeで書いたパッケージを組み込む場合はmklibcat.scmを編集します。

mkimpcat.scmの中では手続きadd-linkとadd-sourceが定義されています。add-linkはオブジェクトファイルのカタログへの追加に使用され、add-sourceは処理系依存のSchemeソースプログラムの追加に使用されます。作成したjfilter.soを追加する場合は、 (implementation-vicinity)にjfilter.soを置いた上で (implementation-vicinity)にあるmkimpcat.scmを次のように変更します。


		% diff -C5 mkimpcat.scm~ mkimpcat.scm
		*** mkimpcat.scm~       Sat Jul 12 01:54:31 2003
		--- mkimpcat.scm        Wed Jul 16 01:24:21 2003
		***************
		*** 159,168 ****
		--- 159,170 ----
		        (in-implementation-vicinity "record" link:able-suffix))
		    (add-link 'generalized-c-arguments
		        (in-implementation-vicinity "gsubr" link:able-suffix))
		    (add-link 'array-for-each
		        (in-implementation-vicinity "ramap" link:able-suffix))
		+   (add-link 'jfilter
		+       (in-implementation-vicinity "jfilter" link:able-suffix))
		)
		(display* ")")
		)
		
		(begin

mkimpcat.scmを編集したらカタログファイルを書き換えておかないと、変更が反映されません。SCMセッションから(require #f) を発行すると既存のカタログファイルが削除されます。次回に SCMを起動してライブラリをrequireしたときに、新しいカタログファイルが作成されます。


		% scm -e'(require #f)' -e'(require (quote jfilter))'

(implementation-vicinity)内のファイルを書き換えますから、このディレクトリに対する書込み権限が必要です。 (implementation-vicinity)がデフォルトの "/usr/local/lib/scm"の場合は、通常はroot権限を持って書き換えを実行する必要があります。

-> ひとつ前へ

-> ホーム

犬飼大

Hobbit

目次