記号だけで brainfuck インタプリタ - まめめも
Ruby 1.9 の新機能のひとつに「lambda { ... } を -> { ... } と書ける」というのがあります。この表記は反対意見が根強い *1 ですが、確実にすばらしい点があって、全部記号だということです。これによって Ruby が記号だけでチューリング完全になります *2 。 デモとして、brainfuck インタプリタを記号だけで書いてみました。 $___,@_,@__,$_=(@@__="")=~//,?#=~/$/,->(_){_<(__="####"=~/$/)**__&&(@@__<< _;@__[_+@_])},[*$<]*@@__;@__[$___];$____,$_,@___,$__,@__=$_[@_+($_+?!=~/!/ )..-@_],$`,[],[],->(_){(__=$_[_];__=~/[><+\-\.,]/?$__<<$_[_]:__==?
YARV のバイトコードベリファイアを作ってみた - まめめも
YARV ベリファイアを試作してみました。製作時間一晩、リファクタリング一晩なので適当です。不正なバイトコードを食わせると例外を投げます。 # encoding: utf-8 # bad_example.rb require "verifier" # ヘッダ header = [ "YARVInstructionSequence/SimpleDataFormat", 1, 1, 1, { :arg_size=>0, :local_size=>1, :stack_max=>3 }, "<dummy>", "foo.rb", :top, [], 0, [] ] # バイトコード本体 (スタックマシン) body = [ [:getlocal, 10000], # 10000 番目のローカル変数を読む [:leave] # 終わり ] bytecode = header + [body] # バ
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,
Rubyfuck ライブラリ - まめめも
Rubyfuck というライブラリを作ってみました。以下の美しい Ruby のプログラムは Hello, world! を出力します。 Rubyfuck.new do |_| _.+_.+_.+_.+_.+_.+_.+_.+_.+_.+_[ _.>_.+_.+_.+_.+_.+_.+_.+_.>_.+_.+_. +_.+_.+_.+_.+_.+_.+_.+_.>_.+_.+_.+_.>_.+_.<_.<_.<_.<_.-_]._.>_.+_.+_. /_.>_.+_./_.+_.+_.+_.+_.+_.+_.+_./_./_.+_.+_.+_./_.>_.+_.+_./_.<_.<_. +_.+_.+_.+_.+_.+_.+_.+_.+_.+_.+_.+_.+_.+_.+_./_.>_./_.+_.+_.+_./_.-_. -_.-_.-_.-_.-_./_.-_.-_.-_.-_.-_.
Verilog quine - まめめも
誰も quine を書いたことのなさそうな言語で quine を書いてみたくなったので、ちょっと調べても見つからなかった Verilog で書いてみました。 module quine; wire [648:1] s = 648'h3b0a696e697469616c2023312024646973706c617928226 d6f64756c65207175696e653b5c6e77697265205b3634383a315d2073203d20363438 276825682573222c732c73293b0a656e646d6f64756c65; initial #1 $display("module quine;\nwire [648:1] s = 648'h%h%s",s,s); endmodule 数値リテラル中の改行は適当に省いてください。 Icarus Verilog で
palindromic quine - まめめも
回文になっている quine です。以下のように動けば正解です。 $ ruby pquine.rb > pquine2.rb $ diff pquine.rb pquine2.rb $ ruby -e 's = File.read("pquine.rb"); p(s == s.reverse)' true 以下は僕の考えた解答。 どれも改行コードは LF で、ファイル末尾に改行をつけないで実行してください。 まずはインチキ。 DATA.rewind $> << DATA.read __END__ __DNE__ daer.ATAD << >$ dniwer.ATAD 一行コメントを使うとわりと簡単。 eval s="$><<\"eval s=\#{t=s.inspect}#\"+(s[5,7]+t).reverse"#"esrever.)t+]7,5[s(+"\#}tcepsni.s=t{
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 にできるか」という問題
ruby-minisat とパズルのソルバ - まめめも
minisat という SAT ソルバの ruby バインディングを作ってみました。1.8.5 と 1.9.0 で動作確認してます。 http://dame.dyndns.org/misc/misc/ruby-minisat-1.14.0.tar.bz2 例えば という SAT 問題を解くときはこんな風にします。 require "minisat" solver = MiniSat::Solver.new # 問題定義 a = solver.new_var b = solver.new_var solver << [a, b] << [-a, b] << [a, -b] # 解の探索 p solver.solve #=> true (satisfiable) # 解の表示 p solver[a] #=> true p solver[b] #=> true リテラルの配列で表現した clau
Functional Programming IAT : 関数型指数心理テスト - まめめも
http://dame.dyndns.org/misc/fpiat/ あなたの潜在意識の関数型指数を測定する IAT です。10 分ほどのテストであなたが関数型言語派か手続き型言語派かわかります。ジョークなので本気にしないでください。 「素晴らしい」などのいい言葉、「苦悩」などの悪い言葉、「Haskell」などの関数型言語*1、「C」などの手続き型言語を素早く分類してもらいます。「いい言葉 or 関数型言語」と「悪い言葉 or 手続き型言語」で分類したり、今度は「いい言葉 or 手続き型言語」と「悪い言葉 or 関数型言語」で分類したりします。そうするとあなたの関数型指数 (プラスほど関数型人間) がわかります。IAT の詳細は前のセクションを見てください。 そのうち統計を取って (分布図の棒グラフにするくらいしか考えてないけど) 公開したいと思っています。個人が特定されないようにするつも
Lightweight Language AHP : おすすめ軽量言語診断 - まめめも
http://dame.dyndns.org/misc/llahp/ 30 問の質問に答えると、Perl 、Python 、Ruby 、PHP の中からあなたの価値観に合った言語を教えてくれる AHP です。各言語を以下の 4 つの評価基準で評価してください。 実行速度 コードを高速に実行できる。 開発環境 ライブラリ、ドキュメント、IDE などが充実している。 記述性 短く簡潔に、メンテナンス性の高いコードが書ける。 変態性*1 遊び心や信念がある (Acme::* 、TOOWTDI 、DRY 、callcc など) 。 AHP の詳細は前のセクションを見てください。「評価基準が作為的」とか言われそうですが、いいのを思いつかなかっただけなので許してください。「書きやすさと読みやすさがあるから記述性などとひとくくりにはできない」とかも言われそうですが、気合いでひとくくりにしてください。 ち
カプレカの定数 - まめめも
6174 はカプレカの定数というそうで、各桁の数字を大きい順に並べた数字と小さい順に並べた数字の差が自分自身になる数字だそうです (7641 - 1467 = 6174) 。(ぞろ目以外の) 任意の 4 桁の数字に対してこの操作を繰り返すと必ず 6174 になるそうです。graphviz でグラフ化してみたら、何となく面白かっこいい絵になりました。 桁数 1 の場合: 0 になる 桁数 2 の場合: 00 になるか、09 -> 81 -> 63 -> 27 -> 45 -> 09 ... のループになる 桁数 3 の場合: 000 か 495 になる 桁数 4 の場合: 0000 か 6174 になる 桁数 5 の場合: 00000 になるか、74943 -> 62964 -> 71973 -> 83952 -> 74943 ... のループか、63954 -> 61974 -> 8296
brainfuck to 数学ゴルフ - まめめも
数学ゴルフが終了したようです。僕の解答も niha さんのと同じです。それはともかく、数学ゴルフの言語の入出力拡張版*1を提案されていました。とりあえず turing 完全であることを確かめるため brainfuck インタプリタを書こうと思ったのですが、面倒だったので brainfuck から数学ゴルフへの変換を定義してみました。 テープのエンコード 僕も変数の数は有限な方がかっこいいと思うので、テープをエンコードするために多倍長倍数を使うことにしました。テープ上の各セルは 1 バイトとして、以下の 3 変数でエンコードします。 l : ポインタ位置より左側の数字を多倍長で表現する m : ポインタ位置の数字を表現する r : ポインタ位置より右側の数字を多倍長で表現する 例えばテープが [1, 2, 3, 4, 5, 6, 7] で、ポインタが 4 の位置を指している状態は l = 3
日本語の 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 頃) 他にもちらほら見かけるはずなのですが、ちゃんとメモしてなかったので思い出せません。見つけたら自発的に適宜追加するかもしれませんが、教えてもらえると助かります。
後方参照のある正規表現の能力 - まめめも
定期的に出てくる話題ですが、プログラミングで出てくる正規表現は正規表現ではないので、素数判定ができます。正確には、文字列の長さが素数かどうかを判定できます。2 文字以上のマッチが 2 回以上出現するかどうかを見ます。後方参照がポイント。 p (2..30).select{|x| !("X" * x)[/^(..+)\1+$/] } #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] ところで、{ a^n | n は素数 } は文脈依存言語のはずなので、後方参照のある正規表現は線形拘束オートマトン以上の表現力を持つことになるのでしょうか。でも、文脈自由文法である { a^nb^n | n は自然数 } や括弧の対応は書けなさそうです。ちょっと調べてみても、後方参照のある正規表現の能力はよくわかりませんでした。 とりあえずPerl の正規表現マッチングで 3-CN
rope ライブラリ - まめめも
ICFPC で話題になった rope/cord ですが、特定の言語環境でしか使えないのはもったいない話です。そこで Ruby の拡張ライブラリとして実装しようとしました。 rope とは 以下の特徴を持った文字列の実装です。 文字列と文字列の結合が速い (O(log n)) らしい 部分文字列の切り出しが速い (O(log n)) らしい 部分の書き換えはできない 指定位置からの文字の取り出しは遅い (O(log n)) でも一文字ずつ順にたどるのは実用上は O(n) らしい 詳しい話はいなばさんの解説なり元論文なりを見てください *1 。 実装方針 Boehm GC 付属の Cord のコードを Boehm GC なしで動くようにする (リファレンスカウントを実装する) 。 Ruby 側のインターフェイスは String 互換 (ただし破壊的操作と正規表現機能はなし) ただ、C の文字列
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
計算量動物園 - まめめも
