はてなブックマーク

TL;DR: Prologの双方向代入最高！ はじめに 8年ほど前に『論理学を作る』という本を読みまして、そこにタブローの方法と呼ばれる論理式の集合が充足可能か調べるアルゴリズムが載っていました。「暇があったらいつか実装してみるか」と思っていたら8年も経ってしまいましたが、暇があったので実装してみました。Prologで。 タブロー（tableau）とは要は木で、木を書くと論理式の集合が充足可能かどうか分かるというものです。こういう時にはWikipediaさんに説明を任せたいのですが、日本語版にはまるで情報がありません。英語版はきちんと書いてあるっぽいので気になる方はそちらを参照してください。 少しだけ説明をすると、与えられた論理式の集合をルートとして、その中の複合式を充足させるのに必要な（より小さな）式を子として木を作っていき、ルートからリーフに至る経路にAと¬A (Aはリテラル) の両方

（この記事はLISP Implementation Advent Calendar 25日目のためのエントリかもしれません。） 背景 今年の春、訳あって42個のプログラミング言語でLISP処理系を実装しました。ソースコードはすべてGitHub上においてます。作り終えたらやりたくなることは一つ。そう、速度の比較ですね。そんなわけで42個のLISP処理系の速度を計測しました。言語によって100倍以上の速度差があるため、すぐ終わるベンチマークでは速い言語同士の比較ができず、時間のかかるベンチマークだと遅い言語が終わらないため、3種類のベンチマークを用意して速度を比べました。計測には time コマンドの total を使用し、各言語3回の計測を行い、その中間値を使用しました。ハッキリ言っていい加減な値なので、きちんとした結果を知りたい人は各自42個の言語処理系を用意して計測しなおしてください。

（この記事はLISP Implementation Advent Calendar 13日目のためのエントリです。） Standard MLとOCamlでLISPを作りました。 https://github.com/zick/SMLisp https://github.com/zick/OCamLisp Standard MLもOCamlもML系の言語で非常に良く似ています。が、文法はちょっとずつ違っていてCommon LispとSchemeのような薫りがします。 動機 今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその20〜21個目です。 私は変数に型が無い言語や、型が緩い言語が好きなんですが、そういった言語を探すのにも疲れてきたし、ついに20言語を突破するということで、思い切って型の強いStandard MLとOCamlを選びました。両方

（この記事はLISP Implementation Advent Calendar 5日目のためのエントリです。） FactorでLISPを作りました。 https://github.com/zick/FactorLisp Factorはいわゆるスタック指向型のプログラミング言語です。Factorの開発元は concatenative programming という言葉を好んで使っているようですが、この言葉はあまりメジャーではない気がします。 動機 今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその7つ目です。 Factorを選んだ理由はよく覚えていないのですが、確かWikipediaを眺めてテキトーに決めたんだと思います。Lua、Python、Ruby、R、Perlといった有名な（少なくても私が名前を知っていた）言語が続いていたので変わった

（この記事はLISP Implementation Advent Calendar 3日目のためのエントリです。） RでLISPを作りました。 https://github.com/zick/RLisp Rは統計の分野でよく使われる言語で便利な機能を色々持っているらしいです。 動機 今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその5つ目です。 Rという言語を選んだのは同僚から推薦されたからです。ちょっと調べてみたところ書きやすそうな言語に見えるし、これは簡単だなと思いました。書き始めるまでは。 標準入力の罠 私が知らない言語でLISPを書くときは、まず標準入力から1行読み込みそれをそのまま標準出力に書く、というプログラムを書きます。今回もそれを書こうとしたのですが、いきなりつまずきました。readLineとreadLinesという関数が存在

（この記事はLISP Implementation Advent Calendar 2日目のためのエントリです。） LuaとPythonとRubyでLISPを作りました。 https://github.com/zick/LuaLisp https://github.com/zick/PyLisp https://github.com/zick/RbLisp 動機 今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその2〜4つ目です。 Lua、Python、Rubyという言語を選んだのは簡単そうだったからです。1つ目のScratchで苦労したので楽がしたかったんです。どの言語もほとんど書いたことがありませんでしたが、実際に簡単だったため、1日で3つの言語でLISPを実装することが出来ました。しかし、その半面、LISPを書き終えてもこれらの言語がどん

（この記事はLISP Implementation Advent Calendar 1日目のためのエントリです。） ScratchでLISPを作りました。 ScratchLisp on Scratch Scratchとはマウスを使い、ブロックを並べることでプログラムの作成ができる教育用プログラミング言語/開発環境です。詳しい説明はWikipediaなどに譲るとして、ScratchでLISPを作った時の思い出話を始めようと思います。 動機 今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその1つ目です。 Scratchという言語を選んだのは同僚から推薦されたからです。「ただの奇妙な言語だと、どうせトランスレータを書くことになるだけだから面白く無い。もっと手を動かして苦労してもらいたい」という慈悲の心に溢れた素晴らしいコメントも頂きました。 変数

突然ですが問題です。この画像は何でしょうか。 答え: Lispインタプリタのソースコード 「なんちゅうソースコードだ」と思った方はぜひこちらからお試しください。 「中を見る (See inside)」を押すことでソースコードが読め、その場で書き換えることも出来ます。 — というわけでScratchでLispインタプリタを作りました。ScratchとはSmalltalkを元に作られたSqueak、を元に作られた教育用のプログラミング言語/開発環境だそうです。キーボートで文字を打ち込むのではなく、マウスでブロックを並べることによってプログラムを作ります。子供でも簡単にプログラムを作成することができるらしいので、つまり子供でも簡単にLispインタプリタが作成できるということですね。 一見、非常に低機能な言語のように見えますが、一通りの機能は揃っているので、足らない部分は努力で補えます。 ビット演

（この記事はLisp Advent Calendar 2日目のためのエントリです。） 「え、お前の家、カレーに味噌汁付けてるの！？」 頑張って作っていたLispインタプリタがついに完成。友達に自慢してソースコードを見せてみたら 「え、なんでそんな実装になってるの？ それって変じゃない？」 といった反応が返ってきたことはありませんか。きっとありますよね。昔から「人の数だけLispがある」と言われていまして、書く人によって色々と違いが出てくるのは当然です。しかし、どんな違いが出てくるのかを知らないと、要らぬ混乱を招く可能性があります。 この記事を読むことで、一言に「自作Lispインタプリタ」と言っても、色々なやり方があることを知り、友人の心ない発言に傷ついたり、逆に人を傷つけないようにする知識を身につけた気分になれます。 「あの人は自分でごみ集めを書いてくれたのに」 Lispインタプリタを書く

32bit用に書かれたC++のプログラムを 64bit環境で動かそうとした時にハマったのでメモ。 void GetParam(const char* key, int size, ...) { ... for (int i = 0; i < size; ++i) { int* var = va_arg(va, int*); if (var) *var = values[i]; } ... } ... GetParam("foo", 4, &bar, 0, &baz, 0); // ここでsegmentation fault ... 上記のプログラムを動かしたらsegmentation faultで死んでしまいました。 if (var) *var = values[i]; のあたりが怪しいと目星をつけて調べてみると、 なんということでしょう。varの値が0であると期待している箇所で、 0x7

【メリークリスプマス！】 クリスマスにこのセリフを言って、みんなを凍り付かせよう。 This entry was posted on 日曜日, 12月 25th, 2011 at 12:00 AM and is filed under 雑記. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

いつの間にやら、GoogleからDartという言語が発表されました。 世間の評判を見てみると、一部の方々からは 「無難な感じで刺激が足りない」 「クラスベースが気に食わない。JavaScriptみたいに実行時にプロパティを追加したい」 などといった意見も出ているようです。 そこで本エントリでは、刺激を求める方々のために、 Dartで実行時にメソッドを追加する方法を紹介します。 まずはこちらのコードを御覧ください。 main() { var i = new Flexible(); i.addMethod("plus1", (self, n) { return n + 1; }); i.addMethod("wawa", (self, x, y) { return self.plus1(x) + self.plus1(y); }); var x = i.plus1(99); print(x);

* はじめに * ここ最近(昔から?)、C言語の本や記事などに 「ポインタを使うことで参照呼び(call by reference)が…」 なんて書いてあると、 「C言語には値呼び(call by value)しかないくぁwせdrftgyふじこlp…」 などというツッコミで荒れるみたいでが、 C++の本や記事に「参照呼び」と書いてあることで荒れるところを (少なくても私は)見たことがないのが不思議なので、このエントリを書きます。 * 参照でcall by reference? * C++でこんなコードを書くと、 int f(int& x) { ... } int g() { ... f(a + 1); ... } こんな感じのエラーが出ますと。 error: invalid initialization of non-const reference of type ‘int&’ from

プログラミング Coqを参考に、CoqとCoqIDEを入れて試してみたが、 どうもCoqIDEの動きがおかしい。時々固まったり変な動作をする。 周りの人に相談したところ 「CoqIDEは使いものにならないからProof Generalを使え」 と言われたのでProof Generalとやらを入れてみた。 Emacs上で動く便利なものらしい。 以下はただのメモ書き。 * ダウンロード * 公式サイトからダウンロードする。 現時点のバージョンは4.0のようだ。 * インストール * 公式サイトの説明に従い、ファイルを展開して、 .emacsにload-fileを追加。 試しにEmacsで拡張子がvのファイルをひらいてみるが、 「Emacsのバージョンが23.1じゃないからダメ」 と怒られる。これまた公式サイトの説明に従いmake。 make clean make compile EMACS=`

今日は風子の誕生日ですね。 風子、誕生日おめでとー。 まあ、それは置いといて、 サーバサイドでCommon Lispを使いたい! *サーバでCLの処理系を動かす* まず、どうやってCLの処理系を動かすか、少し考えてみました。 1. CGIとしてCLを走らせる (恐ろしく遅い予感) 2. 何か専用のモジュールとか使う 3. 頑張って何とかする で、調べてみたら、mod_lispというものがあるそうです。 FreeBSDならportsから簡単に入れることが出来ます。 これは、Apacheにきたリクエストを「Lispサーバ」に渡し、Lispサーバからのレスポンスを 元のレスポンスとして返すものです。Reverse Proxyのようなもの？ この「Lispサーバ」は、mod_lisp専用のプロトコルを話すCLのプログラムです。 これは、Apacheと同一マシンで動かしても異なるマシンで動かしてもい

※リストの循環は脳に悪影響を及ぼす可能性があります。 本エントリを読むときは必ず(setq *print-circle* t)を利用して下さい。 ＜括弧を書かずに循環構造をつくろうとしたのがことの始まりでした＞ '#1='#1# => #1='#1# リーダマクロ ‘ を展開すると結果は、 #1=(quote #1#) になり、循環構造ができます。 しかし、CLISPでこれのcdrを取るとスタックオーバフローします。 (cdr '#1='#1#) *** - Program stack overflow. RESET ちなみに、SBCLだとちゃんと結果が表示されます。 (cdr '#1='#1#) => (#1='#1#) ＜ちゃんと！？＞ よくよく見ると、微妙におかしなことに気づきました。 #1=(quote #1#)は2個のコンスセルから構成されます。 しかし、(#1=’#1#)は3個

「C言語のsetjmpとlongjmpがあればスレッドは作れる」 という話を聞いたので実際にやってみました。 まずは、完成品の使用例から。 #include <stdio.h> #include <stdlib.h> #include "ahothread.h" void f1(void *args) { int i, j; char *str = (char*)args; for (i=0; i<3; i++) { puts(str); for (j=0; j<10000000; j+= 1 + rand()%2); } } int main(int argc, char **argv) { int t1, t2; ahothread_init(); t1 = ahothread_create(f1, "aho"); t2 = ahothread_create(f1, "baka");

Javaのアセンブラと逆アセンブラをCommon Lispで作りました。 一部対応してない命令がありますが、大体動作します。 アセンブリはもちろんS式で記述します。読み込むときはreadするだけ。 オペランドのない命令はアトム、オペランド付きの命令はリストとなっています。 とりあえずhello world。 ;; ljTest.lja (class "ljTest" "java/lang/Object" (public super) method ("<init>" "()V" (public) aload_0 (invokespecial "java/lang/Object" "" "()V") return) method ("main" "([Ljava/lang/String;)V" (public static) (meta max-stack 2) (getstatic "