llvmのGC*1およびビットコード*2に関するドキュメントに、ごく簡単に目を通す。 GC llvmはすぐに使えるようなGCを提供してはいなかった。 ただ、GCを組み込むことはあらかじめ想定されており、そのためのフレームは用意されているようなので、GCを実装・利用…

『LLVM Language Reference Manual — LLVM 3.4 documentation』を一通り読み終わる。 仕事の行き帰りに読んでいた『Java 並行処理プログラミング』*1も同時に終了。llvmは、そろそろ本格的にコード(or コードジェネレータ)が書きたくなってきたが、まだ最低G…

『LLVM Language Reference Manual — LLVM 3.4 documentation』を引き続き読む。 phi命令の動作が読んだだけでは分からなかったので、実際に動かして試してみた。 コード: ;;; ファイル名: phi.ll ;;; コンパイル: llvm-as phi.ll -o phi.bc ;;; コマンドの…

少し面白そうだったのでllvm(Low Level Virtual Machine)のマニュアル*1を読んでみる。 今日は、半分くらいまで読んで終了。 現時点の知識で、ハノイの塔を実装してみた。 ;;; ファイル名: hanoi.ll ; printf関数に渡すフォーマット文字列 @.MSG = internal …

JavaにはJavadocという有名なドキュメントコメントがある。 (実践しているかどうかは別として)関数その他にドキュメントをつけるという考えは良いと思う。 ただ、Javadocの場合、名前の通り(一定の規約に従った)コメントを使って(関数その他の)文書化を行っ…

パターンマッチがある関数型言語でよく見かける_変数*1をsbclでも使えないかと少し試してみた。 結局満足出来る結果は得られなかったが、作成したものの一部をメモして残しておく。 ;; 以下は、マクロ文字候補文字xが ;; シンボル名の一部として解釈できない…

Qiという型安全なlispがあるらしい。 僕がcommon lispで物足りないと思うことの一つが、静的型の欠如*1 *2なので、結構興味がある。 公式サイトドキュメントが面白そうなので、後で読む。 ### 最近はやりたいことが多すぎて、毎日寝不足。 仕事が...。 追記:…

Railsをやったことがある人ならお馴染みのeRuby(もどき)を、common lispで実装してみた。 所要時間およそ90分、行数はコメント込みで70行足らずという簡単なもの。 文法 eRubyの文法は次のように紹介されている(Wikipediaで)。 HTMLファイルの中に （もしく…

文字列の分割を行いたいけど、cl-ppcreパッケージをその(cl-ppcre:split関数の)ためだけに使用したくはなかったので、分割関数を作成した。 ;; 第一版: 平易 (defun split (delim seq &aux (len (length delim))) (declare (unmuffle-conditions compiler-no…

以前に作成したC++によるURLエンコード/デコード関数は、変換先の文字列を格納するためにstd::stringクラスを使っていた。 std::stringを使えば、クラス側がメモリ管理を適切に行ってくれるので楽(バグも生じにくい)なのだが、その分オーバヘッドもある。 UR…

sbclでCGIスクリプト(#!/usr/local/bin/sbcl --script)を作成して、Apacheのもとで動かしてみようとしたら、失敗した。 OSはCentOS 5。 rubyやperlで作成したCGIは普通に動く。 Apacheのエラーログには次のような出力がはかれていた。 [Wed Jan 20 03:30:01 …

前回と重複するところがあるが、ftype型宣言の有用な使い方について書いておく。 関数の戻り値の型指定 ftype型宣言を使うと、関数の戻り値の型を指定することができる。 これが何故有用かと云うと、sbclは関数の戻り値の型が指定されている場合、それに基づ…

長さ制限付きハフマン符号化に合わせて、普通の*1ハフマン符号化のソースコードも整理。 ### 最初にハフマン符号化本体のソースを載せて、次にその中で利用しているヒープ(順序キュー)の実装を載せる。 ハフマン符号ソース。 参照: nlet, ???-obj-??? ;;;;;;…

長さ制限付きのハフマン符号化のソースコードは、以前にも載せたが、結構無駄が多かったので書き直し。 ついでに、整理中に気づいたこと(間違っているかもしれない!)を注釈として残しておく。 ;;;;;;;;;;; ;;;; 構造体 (defstruct obj ; コスト値を持つオブ…

急にocamlのコードを書いてみたくなったので、以前に他言語用に書いたURLエンコードのソースをocamlに翻訳した。 以下、成果物のメモ。 (* file: url_encode.ml *) (* Read whole file *) (* refer: http://www.ocaml-tutorial.org/ja/if_statements,_loops_…

メモ２。 各コードを符号化するのに最適なビット長は、(- (log (/ コードの出現数 コード総数)) 2)、で求めることができる。 そのため次のような関数で、入力データの最適なハフマン符号化のために必要なビット長が得られる。 ;; コードの出現頻度表を引数に…

長さ制限付きハフマン符号の整理中。 気づいたことメモ。 N個のコードを符号化するには、ビット長が最低(log N 2)*1は必要。 一番(最大の)ビット長が短くて済むのは、全てのコードを同じビット長でエンコードした場合。 いわゆる普通の文字表現(256文字を、8…

BWTに続いて、MTF(Move To Front)。 BWTは、対象の列を、同じ値の要素が隣接する傾向がある列へと変換した。 MTFは、それらの隣接した要素を0(あるいは他の小さい整数)で置き換えるアルゴリズムらしい(不正確)。 BWT -> MTFの適用を経た列は、要素の多くが0…

gzipに続いて、bzip2圧縮(もしかしたら解凍も)をcommon lisp(sbcl)で実装してみようと思う。まだ詳しく調べてないので不確かだが、bzip2では「入力データ -> BWT*1 -> MTF変換 -> ハフマン符号 -> 圧縮データ」のようなプロセスで圧縮を行っているようだ。今…

前回書いたBWT関数はかなり非効率だったので、その修正版を作成した。 修正点は主に以下の三つ。 対象を文字列からバイト列に変更 列のローテートは実際には行わない。代わりに、各列の先頭位置を保持する変数を用意し、その値をずらすことで循環列を表現す…

半年くらい前に書いた「アナフォリックマクロとpacakge」の続き。この方法だとダメなケースを発見したので、その改善策(?)を考えてみる。 以前の方法 以前の方法は、アナフォリックマクロの定義と使用が別パッケージに分かれる場合に、アナフォリック変数の…

ftype型宣言。 あまり使われているのを見ない気がするが、これを使うと「型宣言なしでは遅いけど、宣言をつけるとコードが汚くなる」というような問題を解決できる時があるので、少し書いておく。以下はsbcl(1.0.34)での挙動。 準備 ;; 処理速度を最優先 (de…

冬休みに作成したgzip圧縮器を整理*1して、パッケージにまとめた。 ・deflate(0.1.0) ※ 依存: common-utils 以下は簡単な計時など。 比較対象は、gzipコマンドとcommon lispのsalza2パッケージ。 # gzip > time gzip -c /path/to/file > file.gz ;; salza2 (…

『On Lisp』のmkstrの話。オリジナルの実装はこれ。 ;; 引用: http://www.komaba.utmc.or.jp/~flatline/onlispjhtml/utilityFunctions.html (defun mkstr (&rest args) (with-output-to-string (s) (dolist (a args) (princ a s)))) この実装は、sbcl(1.0.34…

gzip圧縮/解凍器作成の４。 ようやくgzip圧縮器の作成に着手。 gzipパッケージ 今回は、DEFLATEフォーマットに準拠したデータの作成/書き出し部分の実装が主となるが、それに取りかかる前にgzipファイル作成用のユーティリティパッケージを定義しておく。コ…

RFC1951のDEFLATE圧縮データフォーマットを実装するために作成したビットストリーム。 DEFLATEを実装するのに当面必要な関数だけが定義してあり、インターフェースは適当。 ;;;;;;;;;;;;;;; ;;;; パッケージ (defpackage :bit-stream (:use :common-lisp) (:…

gzip圧縮/解凍器作成の３。 軽く整理 gzipはデータの圧縮に(主に)DEFLATEアルゴリズム(or DEFLATE圧縮データフォーマット)を利用している DEFLATEでは以下のような方法でデータの圧縮が行われる 入力データをLZ77アルゴリズムで圧縮する 上記圧縮データをさ…

冬休み(中に終わらせたい)の取り組み、gzip圧縮/解凍器作成の２。 前回は、RFC 1951(日本語訳)で定義されているDEFLATEフォーマットに準拠したデータを作成するのに必要な符号長の制限付きのハフマン符号化アルゴリズムを実装した。 今回はDEFLATEに関する残…