common lisp
Haskellのモナドの簡単なものをcommon lispで実装してみたので、コードを載せておく。 ※ 対象としたのは、maybeモナド、listモナド、stateモナド、continuationモナドの四つで、それぞれの定義は『All About Monads』の第三部を参考にさせてもらった。(各モ…
ensure-directories-existは、pオプション付きのmkdirコマンドと同じような動作をすると思っていたのだが、少し違ったのでメモ。 mkdirコマンドは、引数のパスをディレクトリ名として解釈する。※以下の例では、全て空の/tmpディレクトリのみが存在すると仮定…
オンラインで読める『Real World Haskell』という本の目次を眺めていたら、BloomFilterという言葉を発見。 どうやらデータ構造の一種らしいが、聞いたことがなかったので調べてみた(Wikipediaで)。 結果、セット(集合)を表すためのデータ構造だということが…
ふと思い立って、カリー化を行う関数を書いてみた。 (defun curry (fn &rest args) (lambda (&rest rest-args) (apply fn (append args rest-args)))) ;;; > (curry #'cons :first) -->#<CLOSURE (LAMBDA (&REST REST-ARGS)) {B3BC96D}> > (funcall * :second) --> (:FIRST . :SECOND) カリー化関数は他の誰</closure>…
以前DoubleArrayのTAIL圧縮を取り扱った時に参考にした『ダブル配列におけるキャッシュの効率化』*1という論文には、TAIL配列の他に、BASE配列とCHECK配列を圧縮する方法も載っていた*2。 それほど長くないので、該当個所を引用させてもらう。 ダブル配列は…
『Let Over Lambda』を読んでいたら、p.22の脚注に次のような記述を発見した。 We can also indicate the specialness of variables by using declarations to make them locally special. declareで宣言すれば、"locally"なspecial変数が使える、というよう…
Wikipediaのcommon lispの項目を読んでいたら、iterateというパッケージの存在を知った。少し興味を引かれたのでマニュアルに(簡単に)目を通してみた。 名前の通り、繰り返し処理を行うためのパッケージで、立ち位置的にはloopマクロに近いようだ。 >(iter (…
asdf-installを使ってパッケージをインストールしようとすると、下のように「GPGのキーがありません」(?)とよく云われる。 >(asdf-install:install "cl-ppcre") ...略... debugger invoked on a ASDF-INSTALL::KEY-NOT-FOUND in thread #<THREAD "initial thread" RUNNING {AB6E569}>: No key found for </thread>…
JSONのようにデータの記述だけからなる言語の場合、パーサさえ書いてしまえば、それをcommon lispに組み込むことは容易だ。例えば、『JSONデコード: トップダウン』で作成したJSONパーサを使った場合は、以下の4行だけで、common lispがJSONを解釈するように…
数日前にcommon lispでJSONパーサを実装したが、そのC++版を書いてみた。実装的には、common lisp版とほとんど変わらないが、サロゲート・ペアに対応したり、エンコード関数も(おまけ程度)に作成したり、と若干以前よりは高機能になっている。ソースコードは…
今までのDoubleArrayの実装では、当然のように(vector (unsigned-byte 8))をキーとして利用してきた。文字列(キー)を扱う場合は、1byte(=8bit)を単位として扱うのが自然なので、悪くはない(むしろ良い?)とは思うのだが、2byte以上を単位として扱うのも、それ…
JSONのパーサを作ってみた。 参考にしたのは、こことここ。 今回作成したのはトップダウン(再帰下降)型のパーサ。 ボトムアップ版もいつか作ってみたいという思いを込めて、タイトルに「トップダウン」と入れておく。 割合高速。 実装 ほぼJSONの仕様(?)通り…
DoubleArrayの3-1。 今回はTAIL配列の圧縮を行う。 参考にした(かな?)のは、次の論文: 『ダブル配列におけるキャッシュの効率化』*1。上の論文の中に「後方一致する接尾辞を併合することで、TAILを圧縮することができる」という記述があるが、今回はこの通り…
以前、中途半端にHTMLパーサを実装したが、htmlをS式に変換してくれるcl-html-parseというライブラリが既にあったようだ。 > (asdf-install:install :cl-html-parse) > (net.html.parser:parse-html "<html><head><title>title</title></head><body></body></html>") --> ((:HTML (:HEAD (:TITLE "title")) (:BODY)))
コンパイラの本を流し読みしていたら、中置記法とか前置記法とか後置記法とかが出てきた。これらの記法間の変換処理(正確には中置記法から後置記法への変換)は、だいぶ前に実装しようとして挫折(?)したことがあったのだが、今日試してみたら、(適切なコード…
common lispでは、標準出力にバイナリデータを出力する方法が定義されていない(多分)。unix系(?)のOSの場合は、以下のように/dev/stdoutをopenすればバイナリデータを標準出力に出力できるようだ。 > (sb-ext:string-to-octets "標準出力") --> #(230 168 15…
DoubleArrayシリーズ(?)の続き。 今回は、insert関数の処理速度を改善する。 改善点 前回の実装では、insert関数の処理速度がもの凄く遅かったが、その原因はinsert関数の中(の関数の中)で呼び出されているx-check関数にある。 この関数は、簡単に云えば(要…
最近は少し忙しいので、気分転換を兼ねて簡単な関数を実装する。リストの破壊的なリバース。 以下、ソース。 参照: nlet (defun list-reverse! (lst) (nlet self ((lst lst) head) (if (endp lst) head (self #1=(cdr lst) (progn (setf #1# head) lst))))) …
alpha-char-p関数が自分の予想外の挙動をするのを発見。(確認したのは、sbclとclisp) ;; 予想通り > (alpha-char-p #\a) --> T ;; これも > (alpha-char-p #\0) --> NIL ;; 予想外 > (alpha-char-p #\あ) --> T 別に「アルファベット」が、aからzまでの文字…
あまり好きなわけではないのだが、諸々の事情によりsql(特にmysql)を使わなければならないことが結構あるので、開発補助用のマクロを定義しておく。 (require :clsql) ;; DBに接続(DBの各種情報はハードコーディング) (defmacro with-db (&body body) `(clsq…
今日たまたま見つけた『(Sather を試そう) 1. Sather vs C++: 実行速度の比較』*1というページに触発され、lisp(sbcl-1.0.28)でも同様の比較を行ってみた。 C++のソースコードは、上記ページのものと同様だが、g++のオプションには'-O3'を渡している。 実行…
DoubleArrayでの実験用にハフマン符号化を実装。 ※ここの続きでもある ハフマン符号化は、本で良く目にしてはいたのだが、これまで実装したことはなかった。 実際にやってみると案外簡単で、大体以下の四ステップで実装できた。 1. 入力文字列中の各文字の出…
ちょっとヒープ(優先順位付きキュー)を使いたくなったので、実装。とりあえずは、実装が簡単な(かつ性能が良いらしい)pairing-heapを選択。一群の関数は、後で他のものに変更しやすいようにpackageにまとめておく。 ;;; package (defpackage :pairing-heap (…
しばらくDoubleArrayでいろいろ試してみようと思っているので、今日はそのベースとなるソースコード(+覚え書き)を掲載。 『An Efficient Implementation of Trie Structures』*1を参考に実装した。 前置き DoubleArrayの簡単(かつテキトウ)な説明。 Trieの実…
可変配列マクロ(?)の最新版。 index部分もS式で指定可能に。ex. @array#(+ 1 1) エラーチェックとかが適当なのは、以前のものと同様。 ※ @array#(incf i)などのように式は、(incf i)が二度評価されてしまうので注意が必要 (defmacro assure-access (vector i…
アナフォリックマクロをpackageに分けて使う場合のメモ書き。 カレントパッケージで、定義・使用する場合 (defmacro a.when (expr &body body) `(let ((it ,expr)) (when it ,@body))) > (a.when (member 2 '(1 2 3)) (car it)) --> 2 特に問題なし。 定義と…
HTMLパーサのところで、パース結果のlistをcl-whoに渡せば、HTML文字列が生成できるということを書いたが、整形されていなくても良いなら、変換処理自体はpretty-printを使って*1簡単に実装できる。 準備 参照: nlet ;; 型定義: car部がkeywordならHTMLリス…
今試していることで可変の配列が使いたくなったので、用意。 ;; indexが(length vector)の範囲を越えている場合は、自動で配列を拡張 ;; vectorはsymbolである必要がある (defmacro assure-access (vector index) `(locally (declare ,@(if (symbolp index) …
昨日のブログにあるHTMLパーサを試していたら、(組み込みのものではない)read-xxx系関数がボトルネックとなっていることが分かったので、修正する。一番、大きな影響を与えていたのは、この関数(若干簡略化)。 ;; (funcall fn c)がtになるまで、文字列を読み…
HTMLパーサは、たまに使いたいと思うのだが、なかなか良さそうなのが見つからないので、自分で作ることにした。ソース: html2list(0.0.2) 行数は250行くらいで、依存packageはcommon-utils。 とりあえず、行儀良く(?)書かれているHTMLは、だいたいちゃんとパ…
