2011-01-01から1年間の記事一覧
最近の Emacs では、PostScript を書いて直接 Emacs バッファ内に表示できる(doc-view)ことに気づき、急に PostScript を勉強する気が高まった。実際は GhostScript も対話的に操作できるのだったが、Emacs のインターフェースに慣れすぎているので。 Link h…
構造 Common Lisp でコンパイラを書き、X86 または X86_64 アセンブラを生成する gcc でコンパイルし、共有ライブラリを作る。 gcc で実行ファイルを作る。 テストケースを書く gdb で実行し、問題があればデバッグする。 機能を拡張し、繰り返し 論文で使用…
残念ながら Common Lisp の LOOP マクロでもできないことがあるようだ。「あらゆる数独パズルを解く」の python のコードで、search という関数で見つけた。 def search(values): "深さ優先探索と制約伝播を使い、すべての可能なvaluesを試す。" if values i…
Python で書かれたプログラムを Common Lisp に置き換えるのに数独パズルで慣れてきた。ついでにスペル修正プログラムもやってしまおう。 Python の dict, set はとても強力だ。CL でも union とか pushnew とかリストを set のように扱うことはできるけど、…
少し改良。エンバグしていませんように。 ;; sudoku solver ;; see peter norvig's article(sudoku.htm) (in-package :common-lisp-user) (ql:quickload :com.gigamonkeys.test-framework) (defpackage :sudoku (:use :cl :com.gigamonkeys.test)) (in-packa…
LOOP マクロを使うとき、わたしはつい、以下のように書いてしまう。 (defun parse-grid (grid) "テキスト形式 grid を可能な値のハッシュテーブルに変換する。 square => digits ただし矛盾が見つかった場合は nil を返す。" (let ((values (make-hash-table…
続き。問題は解けているようだ。 データ構造としては、Python の辞書(dict)をCLのハッシュテーブルとしている。またオリジナルのコードで文字列で保持しているsquareが取りうる値は、とりあえずリストとしている。まだ残念ながら Python の リスト内包表記の…
Peter Norvig の「あらゆる数独パズルを解く」 を実装したくなった。途中だが記録として取っておく。まだ面白いところ（探索とか制約伝播とか）には入っていない。 ;; sudoku solver ;; see peter norvig's article(sudoku.htm) (in-package :sudoku) (defva…
twitter で教えていただいたもののメモ。 xlisp http://www.xlisp.org/ "XLISP 3.0 is a superset of the Scheme dialect of Lisp with extensions to support object-oriented programming." XLISP は 1.0 2.0 3.0 と全部別ものらしい ISLisp OKI ISLisp "I…
ユーザエージェント Web ブラウザの Safari は、開発者向けのメニューがついていて、ユーザエージェントを変更できる。変更できるユーザエージェントの一覧は XML で定義されている。Drakma の場合は、関数 http-request にユーザエージェントのためのキーワ…
再び郵便番号API。検索結果が多いときは、複数のリクエストが必要になる。定義されているAPI通りに、ページを順番に取っていく。 (defun retrieve-from-zip-ricollab (query) (let ((uri (format nil "http://zip.ricollab.jp/search?q=~a&type=json" query)…
DRAKMA で RESTFul な API を叩いてみる。例として「Web を支える技術」の郵便番号検索サービスを使う。 REST-TEST> (let ((uri "http://zip.ricollab.jp/1620846")) ;; 技術評論社 (http-request uri :method :get)) "<html xmlns=\"http://www.w3.org/1999/xhtml\" xml:lang=\"ja\"> <head> <title>〒162-0846</title> </head> <body> <h1>〒162-0846</h1> <dl> <dt>番…</dt></dl></body></html>
途中だがRESTFul への道。たぶん、1) Hunchentoot の request-dispatcher を置き換える( 'rest-request-dispatcher を作る), 2) リソースと CLOS の対応付けを行う、といい気がする。 リソースクラスは、URL と関連づけられる機能を持たなくちゃいけない。Sh…
process-request メソッドを粗く眺めていると、*show-lisp-error-p* という変数がありました。これを t にしておくと、エラーが生じたときにブラウザ上に lisp のエラーが表示されました。これで PHP 風の開発ができますね！REPL があるので誰もやらないとは…
Hunchentoot が受け取ったHTTP リクエストの中身を見ることにします。list-request-dispacher を簡単に置き換えるだけで十分でした。 TBNL> (defvar *my-slime-output* *standard-output*) *MY-SLIME-OUTPUT* TBNL> (defun my-request-dispatcher (request) …
Hunchentoot (http://weitz.de/hunchentoot/) は Common Lisp で書かれた Web サーバです。 dispatch Hunchentoot でのリクエストの処理は、以下のようになっているようです。 taskmaster がクライアントからのリクエストを受け付ける (中略) acceptor イン…
レンタルサーバを借り、Lisp の開発環境を構築する際のメモ。 サーバ さくらのVPS (http://vps.sakura.ad.jp/) を借りた。すぐに安価に始められ root 権限を持てる。Cent OS 5.6 環境。 デフォルトでは決して安全ではないのでファイアウォールを設定した。必…
四則演算をCLで。 (defun parse-calc (string) "Parse calc string. operator: +,-,*,/ number is only 0-9." (parse-calc-iter (make-string-input-stream string))) (defun parse-calc-iter (stream) (let ((table (make-hash-table))) ;; operator => pri…
元論文が入手できればたぶん一発で理解できるのだが、メモ。 reverse - subset - reverse - subset の操作で NFA を最小化するアルゴリズム。 NFA を反転させる操作 reverse は、オートマトンを図示した場合、すべての矢印の向きを反転させ、開始状態と終了…
メモ。 Finite state automaton construction through regular expression hashing Chapter 5 Brzozowski's algorithm with state merging Watson B.W., Kourie D.G., Ngassam E.K., Strauss T. and Cleophas L. Efficient Automata Constructions and Appro…
http://eliza.newhaven.edu/lang/lectures.html "CS 636 / 536 Spring 2009 The Structure of Programming Languages Lecture Notes, Resources, and Homework" の Structure of Programming Languages – Lecture 2 (http://eliza.newhaven.edu/lang/attach/…
Common Lisp で Forth インタプリタを少し実装してみた。リストあそびならぬ「スタックあそび」という感じ。面白い。 FORTH> (run-forth '(1 2 3 |.|)) ;; display: 3 #<data stack: (2 1) > FORTH> (run-forth '(|:| fn 2 * 1 + |;| 10 fn)) #<data stack: (21) > FORTH> (run-forth '(|:| doubler </data></data>…
以下個人的 Forth 情報。まだちゃんと読んでいないのがほとんどなので注意。 Forth の有用/有名な文章 Starting Forth http://www.forth.com/starting-forth/ Forth Inc 社に置いてあるオンライン版 Thinking Forth http://thinking-forth.sourceforge.net/ …
いろいろあるものだ。どれもまったく動かせていないがいつか。 名前 説明 作者 URL 備考 ECL for iPhone iPhone 用の ECL port? kriyative https://github.com/kriyative/ecl-iphone-snapshot 2010.2 更新 KondoLisp Arduino hayamiz http://d.hatena.ne.jp/…
Common Lisp で PPM フォーマットの画像を作った。 Ascii 形式の PPM 画像 (defun test-ppm () (with-open-file (out "/tmp/tmp.ppm" :direction :output :if-exists :supersede) (format out "P3~%") (format out "100 100~%") (format out "255~%") (loop …
SLIME(The Superior Lisp Interaction Mode for Emacs) の REPL バッファに画像を表示できることがわかった。この機能はなかなか応用が利きそうだ。 SLIME の準備 以下必要な準備。 SLIME を環境を最新にする conrib/slime-media.el をロードする eval-in-em…
DFA の状態数の最小化について、"Brzozowski のアルゴリズム"なる方法があるらしい。Dragon Book アルゴリズム 3.39 とは違うアプローチで、二回 reverse して二回 部分集合構成法を適用するだけ、というものだ。まだ実装できていないが、このアルゴリズムで…
setf とループを組み合わせてより簡潔に。initially という loop キーワードを初めて使った。 (defmethod convert-to-dfa ((nfa nfa)) (labels ((goto* (n-set a) (loop for s in n-set with res = () do (loop for q in (transit nfa s a) do (pushnew q re…
整理。 (defmethod convert-to-dfa ((fa nfa-e)) (with-accessors ((alphabet alphabet-of) (start start-state-of) (accepts accept-states-of)) fa (let ((Dstates (make-hash-table :test #'equal)) (Di (sort-states (epsilon-closure fa (list start)))…
さらに loop マクロを使ってみたけどあまり奇麗にはならないなぁ。 hashtable 使ってみたけど :test に equal を使っているのがいまいち気に入らない。 (defmethod convert-to-dfa ((fa nfa-e)) (labels ((goto* (n-set a) (loop for s in n-set with res = …
