クリーネの再帰定理＋ Quine が書けることの証明 - まめめも
クリーネの再帰定理のプログラマ向け説明（＋証明）を書いてみました。何か間違ってたら教えて！ 前提 すべてのプログラムは文字列を 1 つ入力して文字列を 1 つ出力する、という世界を考えます。なお、プログラム自体も当然文字列です。 プログラムは eval っぽい命令を使っていいことにします。つまり、プログラムpと、pへの入力文字列sを受け取って、pを実行した結果の出力文字列を返す関数 E(p, s) が利用可能です。*1 二つのプログラム p と q が完全に同じように振る舞うとき、p 〜 q と書くことにします*2。これは明らかに推移的。 定理 任意のプログラム f に対し、p 〜 E(f, p) となるようなプログラム文字列 p が存在する。*3 定理の証明 以下のような 3 つの文字列を考えます。 h: 入力文字列 x に対し、E(x, x) の結果を出力するプログラム*4 e: 入力
Merry Quine-mas 2012 - まめめも
今夜は、年に一度の W. V. Quine の命日イブです。(もう日が変わってますが) %;';;eval$s=%q{eval(%w~i=1;T="$)*L)L)))0)E(E(0(7(>'>'7&E&0&7&>%L%)%0%E*)$L$)* L)L)))0 )E(E(0(7(>' >'7&E&0&7&>%L%)%0%E5&$L%#8C5G7/530L2B1*/'19-D03 #E*&,1). *G'6#3*>5 &'F'#)E(L)0*)'L'?(#)#)7(E'0&E&#(0%0&L%7&0':+)%E# {"4F"*18} 3F4F5F4 F4@493@1@5@7@6@692@2939325952425+4+3+3F4$5F4F".by tes.each_s lice( 2).map{|s,c|[s*3-99,c/7*3-13-i=-i,c%7+41]};$><<"'# {e=27.
音声の波形からピッチを検出するアルゴリズム - まめめも
去年のクリスマスに公開したカラオケ機能つき Quine の仕組みについて。 ref: 声の高さで操作するゲームを作ってみた で解説されている内容と同一です。おわり。 で終わるのもつまらないので、簡単に解説します。でも思いだしながら書いているので嘘書いてたらごめんなさい。動画には図とかあるので、やはりそっち見た方がいいと思うけど。 「ピッチ検出なんて FFT するだけでしょ」と思ってる人は素人で、音叉みたいにきれいな正弦波を測りたいならともかく、声や楽器の音など倍音を含んだ音では誤判定が起きまくるようです。偉そうなこと言ってる私も素人です。そこで、Wikipedia の Pitch detection algorithm で挙げられている、MPM アルゴリズムを調べて実装してみました。以下の論文。 ref: P. McLeod and G. Wyvill. A smarter way to
RubyKaigi 2011 終了 - まめめも
参加してました。コミッタ特権でタダ飯を食らえるのも残念ながら最後です。 今まではマジタダ飯にならないように何かしら発表することを心がけてたんですが、今回はネタ準備できず、ついに聞くだけ。"1.8 and 1.9" でちょびっとだけ壇上出たけど、その分弁当もらってしまったし。申し訳ない。なのでせめて見た発表ごとの一言感想を書きました。最後に。 そして Ruby とかなり関係ない Alloy 本は、ジュンク堂出張店で販売していただき、個人的な予想をはるかに上回る人数 (予想 1 桁、結果 2 桁) に汚い字でサインさせていただきました。ありがとうございます！おまえら買ったばかりの本を汚していいのか！ちなみにサインは実行可能な Quine になっています。typo してなければ RubyKaigi 中のコミッタの行動にプライバシーはないと思うので、サインさしあげたコミッタだけ晒すと mrkn さ
/dev/dsp で音声を鳴らす方法 - まめめも
超絶技巧 Ruby プログラミングの質疑で「どうやって音を鳴らしているのか」という質問があったので、自分のための記録を兼ねて簡単に紹介。 といっても Linux Sound programming with OSS API にある通り。Ruby で書くとこんな感じ。 # デフォルトでは 8bit 8000 Hz SampleSize = 256 SamplingRate = 8000 # ... 0:ラ 1:ラ# 2:シ 3:ド 4:ド# 5:レ 6:レ# 7:ミ 8:ファ 9:ファ# 10:ソ 11:ソ# 12:ラ ... tone = 3 # ボリューム: 0 〜 SampleSize/2 まで volume = 60 # 再生する長さ: 秒 length = 2 # 周波数: 基準のラは 440Hz 、1 オクターブ上がると倍になる freq = 440 * 2**(tone / 1
Ruby でパターンマッチ - まめめも
ref: 未来の国のアリス - d.y.d. で紹介されている implicit future が Ruby に欲しい！ # promise を作る x = Promise.new a = [1, x, 2, x, 3, x] # 今はまだ値になっていない p a #=> [1, _promise_, 2, _promise_, 3, _promise_] # この promise は 42 に決めた！ (代入ではないよ) x === 42 # x の箇所は勝手に 42 になっている p a #=> [1, 42, 2, 42, 3, 42] というのも、これがあれば Ruby でパターンマッチができる気がするんですよね。こんな感じに。 # 何にでもマッチする箇所には _ と書く (実体は Promise.new) def _ Promise.new end # + と定数だけからなる抽象
brainfuck-dialect quine generator - まめめも
それでも @mametter ならっ・・・！ RT @bonotake: quineの作りがいがありそうな…作んないけど RT @masahiro_sakai: ジョジョ言語わろた http://bit.ly/d0RUUR http://twitter.com/masahiro_sakai/status/9091442089 brainfuck の命令文字を置換しただけの俺言語は結構ある *1 ので、いちいち quine を作るのは面白くありません。そこで、命令文字の割り当てから、その言語での quine を自動生成するソリューションを開発しました。 brainfuck の quine の生成。 $ ruby19 bfd-quine-gen.rb bf > quine.bf $ beef quine.bf > quine2.bf $ diff quine.bf quine2.bfたぶん一番
Ruby とすてきな難読化 - まめめも
(これは Ruby Advent Calendar jp: 2009 の 16 日目の記事です。) Ruby は読みやすいプログラムを簡単に書ける言語ですが、読みにくいプログラムも簡単に書けます。 今回は、Ruby でできるかんたんな難読化のテクニックを 4 つ紹介します。 1. Integer#to_s を使う方法 Integer#to_s *1 は、何進数として文字列化するかを引数で指定できます。普通は 2 、10 、16 くらいしか使わないと思いますが、実は 36 まで指定できます。 0.to_s(36) #=> "0" 1.to_s(36) #=> "1" ... 8.to_s(36) #=> "8" 9.to_s(36) #=> "9" 10.to_s(36) #=> "a" 11.to_s(36) #=> "b" ... 34.to_s(36) #=> "y" 35.to_s(
山手 quine - まめめも
t="+,m-n./mAm0o1p23a4q56r7sBt89u-t-1:v;A<w4x=y1z>[?]A^@CD_ CD_EsF`GHmIJbKa*l";eval$s=%w{F=%q{ceY8#<DvO1=x&t9CSOqMYkzH U.kCpz+Vo8hB.1AF&tq21+$/IrMY]U.aDd!-1y!4MMGQm6m?bYh($QMYpX s4g,x1UlbNKH?>NzbisMn?sT@m3,F.Abb`xW!r%'%Ybee>xkUfjf[(*^Nd Xo_"@hQh%Fx*q[iB7EM"suSG8GVOIzceg/O=4CL,d[-k]twgVP`&wcfaT` 2M)j8sFY?(HKzOrVCHO_694[Uq8g @i/i;tMBG#;-;B]rV[])`3'<os^. OV(SA<=ok%m[iV#qt[&dJ7SIdB;/ VUnVIrH;hEJ*QWD"E+
qif 画像 - まめめも
こぴぺ用。 Y,E=%q~260|0!e0*h0($0j0($"!e0($"f0e0($0!e0*p;4f4#.q9!&8*%"1( }+0!,e4|8,e<.%}e6#g4*};!(4*%})2!e09$"u91&(#6}f0(%+#u0)6"1(7, v0.,*%"<8{9!(4+2}!(4*%90}<.'#<(}$"!e0($")n48$6!(0($".!e0($"$ e0w0($")k0r4*%"<8$"!9!&8*%"<0|0($"#&0()0i;f=87$};!(4+6"!e0j; f0(',}91(4+3e0($j;!.8)2}}}}}}},4"!e0($"!2i2!i0)e0e0(#$0($"!e 0(,0}}o0(%2"1(4~,%~y;0('&!e=8}}q9!($"!"<0}}}}}}y0g4f0+2}441$ !}g;0&<}h2$11!{0!q0}h0m0|20!
quine リレー - まめめも
Update (2013-07-15): I improved this program to 50-language version. 50 言語版にパワーアップさせました。 これはこのプログラム自身を出力する Unlambda プログラム、を出力する Whitespace プログラム、を出力する brainfuck プログラム、を出力する Java プログラム、を出力する C プログラム、を出力する Haskell プログラム、を出力する OCaml プログラム、を出力する Lua プログラム、を出力する Perl プログラム、を出力する Python プログラム、を出力する Ruby プログラム、です。 # ruby l=92.chr;eval s="s=s.dump[r=1..-2].gsub(/("+l*4+"){4,}(?!\")/){|t|'\"+l*%d+\"'%(t .s
ダメなマニュアルの特徴 - まめめも
めちゃくちゃ遅い反応ですが、「よく言ってくれた！」という話。 現状のRDocはユーザリファレンスに向いてないと思ってる。 RDoc書いただけで「リファレンスは完璧だお！」とか言ってるやつなんなの - Greenbear Diary (2009-06-04) 以下関係あるようなないような話。わが身は振り返らない方向で。 ダメなマニュアルの特徴 rdoc に限った話ではないですが、以下はダメなマニュアルに共通する特徴だと思います。 クラスやメソッドを ABC 順に並べている メソッドの説明が長い サンプルコードがない こういう文書は読み手を普通のプログラマだと思ってません。 なぜダメか ABC 順だと、どこから読めばいいかわからない。砂漠の真ん中で迷子になったような気分になります。早く使ってみたいのに使えない歯がゆさ。 説明が長いのは、メソッドの名前が適切でない可能性や、無駄に全機能を列挙しよ
ruby 1.9 を日常的に使うぼくが 1.9 の新機能を寸評する - まめめも
なんか偉そうな見出しですが、ruby 1.9 を主に使うようになって 1 年ちょっと経ったので、1.9 の新機能に思うところや注意点などを書き残そうと思うのです。さらに 1 年後に見たとき、「あのころはあんなふうに考えてたなあ」などと感慨にひたる予定です。 あらかじめ断っておくと、ぼくの ruby 1.9 経験はすべて趣味範囲なので、エンタープライズとかシステム運用の問題とかは知りません。あとぼくは ruby のコミッタなので、色眼鏡もあると思います。あしからず。 YARV VM 実行になったという話。一般的には「速い」という文脈で語られます。1.8 と比べると確かに速いです。でも、1.9 ばかり使い出すとなんとも思わなくなるはずです。速さなんて相対的な価値ですから、当然ですけどね。好意的に考えれば、「なんとも思わない程度に、遅くて困ることが減った」のかもしれない。 コンパイルフェーズを挟
関数ポインタのキャストと gcc - まめめも
C の関数呼び出しは、関数定義の型と互換性のない型として呼び出したら未定義動作です。例えば以下のコードの動作は未定義です。 #include <stdio.h> int main(void) { ((int (*)(char *, ...)) &printf)("Hello, world!\n"); } printf は int printf(const char *, ...) なので、const が無くなってるのが間違ってます。未定義のプログラムはどのような実行結果になろうとも、C の規格には違反しません。 でも、現実問題としてこのコードは期待通りに動くだろー、と高をくくってました。しかし最近の gcc (3.4 以降くらい) では、このコードは落ちます。 $ gcc --version gcc (GCC) 4.3.1 Copyright (C) 2008 Free Software
囚人 100 人のパズル - まめめも
飛廉さんから聞いた問題。 囚人が 100 人います。ある部屋に 100 個の箱があり、囚人の名札が 1 枚ずつランダムに入っています。 これから囚人が 1 人ずつ部屋に入り、自分の名前を探します。 1 人あたり 50 個の箱をあけます。 その中に自分の名前がなければ、全員処刑されます。 事前に相談することはできますが、誰かが部屋に入ったら一切の情報交換が禁止されます。 次の人が部屋に入るとき、部屋や箱の状態は完全に初期化されます。 100 人全員が助かる方法を 30% 以上にする方法を答えなさい。 とてもおもしろかった。絶妙。問題を作った人はすごい。 ちなみに、100 人でなくても任意の n 人でいけます。 補足: 箱は識別可能です。1 から 100 のラベルが貼ってあると思ってください。「完全に初期化されます」は「完全に初期状態に戻ります」と思ってください。
YARV のバイトコードと戯れる方法 - まめめも
YARV では、バイトコードを直接書いて実行する方法が提供されています。バイトコードといってもバイトとかは出てこなくて、配列やシンボルを使って命令列を表現します。こんな感じ。 # encoding: utf-8 # good_example.rb # ヘッダ header = [ "YARVInstructionSequence/SimpleDataFormat", 1, 1, 1, { :arg_size=>0, :local_size=>1, :stack_max=>3 }, "<dummy>", "foo.rb", :top, [], 0, [] ] # バイトコード本体 (スタックマシン) body = [ [:putnil], # レシーバを積む # (関数呼び出しのときは nil) [:putobject, 1], # 1 を積む [:send, :p, 1, nil, 8,
SAT ソルバで数独を解く方法 - まめめも
数独は非常に SAT に変換しやすい問題です。全部参考文献 *1 に載っている内容ですが、なるべくわかりやすく説明してみます。ちょっと長いです。 SAT とは まず SAT をごく簡単に説明します。すでに SAT を知っている人はここは読み飛ばしてください。 命題論理式の形の一つに乗法標準形のというのがあります。変数か変数の否定 (リテラルと言います) を or だけでつないだ式 (節と言います) を and だけでつないだ論理式のことを言います。つまり以下みたいな形です。 ( a1 or !a2 or ... or an) and ( b1 or !b2 or ... or !bn) and ... and (!z1 or z2 or ... or !zn)SAT は「a1 や zn などの変数にうまく true か false を代入して、上の式全体を true にできるか」という問題
fisheye view の計算式とプログラム - まめめも
fisheye view とは、なんかインターフェイスの世界では常識っぽい、フォーカスとなる点を中心に座標をぐにょーんと引き延ばす方法です。日本語が不自由ですみません。要するにこういう変換です。 皇居あたりを中心に線路地図をぐにょーんと引き延ばしています。これを実装しようと思って計算式やサンプルプログラムを探したのですが、意外に情報が少なくて手間取りました。なので記録を残しておきます。 種類 参考文献 *1 を眺めたところ、cartesian fisheye と polar fisheye の二種類があるようです。左が cartesian で右が polar です。でもこの例だとほとんど区別が付かないですね。よく見ると端っこの方のつぶれ方が違います。 cartesian fisheye view フォーカスの座標を 、引き延ばしたい点の座標を 、壁の位置を とするとき ( になる) 、引き
日本語の Coq 情報 - まめめも
ついでに、主に日本語の Coq 情報を (10 分で思い出せる範囲で) まとめてみます。順不同。 公式に近い情報 本家 Coq'Art (Coq の教科書) Cocorico! (本家 Coq wiki) CiteSeer (笑) Coq のことをまとめようとしている wiki 菊さんの Coq wiki Tossy-2 の Coq wiki たまに Coq のことが書いてあるブログ yoshihiro503 さんのブログ (LL 魂で Coq の発表をされた方、Coq の話ばっかり) いまいけいごさんのブログ 菊さんのブログ Tossy-2 のブログ あろはさんのブログ (2006/04 〜 05 頃) 他にもちらほら見かけるはずなのですが、ちゃんとメモしてなかったので思い出せません。見つけたら自発的に適宜追加するかもしれませんが、教えてもらえると助かります。
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
