Hatena::ブログ(Diary)

まめめも このページをアンテナに追加 RSSフィード

2013-04-29

[] TRICK 2013 開催中です

Ruby での変態プログラミングコンテスト、まだ開催中です。締切りは 5 月 18 日 (土) なので、あと 2 週間弱。

ref: https://sites.google.com/site/trickcontest2013/home/ja

GW ひまだなーという人も、GW いそがしい人も、ぜひぜひご投稿ください。たくさんのご応募 (本当に) 待ってます。

2013-04-12

[] TRICK 2013 (第一回 超絶技巧 Ruby 意味不明コンテスト in rubyKaigi) をやります

TAPL が無事出版されたので、そろそろ通常モードに。さっそくですが、@shinh さんに煽られて、Ruby で変態プログラミングコンテストをやることになりました。

ref: https://sites.google.com/site/trickcontest2013/home/ja

一言で言えば IOCCCRuby 版という感じで、役に立たんけどなんか面白い Ruby プログラム作って競おう、という大会です。「変態 (褒め言葉) だー!」と言われそうな作品ほど強い。

応募がないと悲しいので、ぜひぜひご応募ください。5 月 18 日が締め切り、6 月 1 日に RubyKaigi 2013 で結果発表をする予定です。

最近の IOCCC は (ネタ枯渇気味なのか) 手の込んだ大作が多いですが、初期の IOCCC は単純だけどはっとさせるアイデア一発勝負が結構あって、ああいう感じのが来るとといいなあと思ってます。「Ruby のあの機能がこんな風に使えたのか!」とか「こんな書き方ができたとは!」みたいな。

あと、@shinh さんが頑張って審査員を集めてくれたおかげで、無駄に豪華な審査員陣になっております。このメンツ揃えてやることがこれかよ、みたいな。

2013-03-03

[] Type-level Quine (未完)

「型システム入門」(TAPL 日本語版)の発売を記念して、型にまつわる何かを書こうと思い、とりあえず型レベルプログラミングでの Quine に挑戦して見ました。

TAPL の内容には全く関係ありません。型クラスは発展的なものなので、入門書である TAPL には名前しか出てきません *1 。型クラスまで書かなくても 500 ページ超の本になるので、型の世界は奥が深いですね。

デモ

ソースはこちら。

ref: https://github.com/mame/type-level-quine/blob/master/type-level-quine-poc.hs

最後の 2 行に注目。

main = putStr $ show quine                                                                  
quine = undefined :: Q X0 b (...) => b

わけわからん型注釈がついてますが、要は quine = undefined なことに注目。

これを以下のようにコンパイルします。

$ ghc -fcontext-stack=2048 type-level-quine-poc.hs
[1 of 1] Compiling Main             ( type-level-quine-poc.hs, type-level-quine-poc.o )
Linking type-level-quine-poc ...

コンパイルには数十秒から数分かかります。また、-fcontext-stack=2048 を付けることに注意。付けないとコンパイラスタックオーバーフローします。

そして生成された実行ファイルを実行すると、

$ ./type-level-quine-poc 
-- Type-level Quine  (c) Yusuke Endoh 2013

-- snip!

main = putStr $ show quine
quine = undefined :: Q X0 b ((X2,Xd):-(X2,Xd):-(X2,X0):-(X5,X4):-(X7,X9):-(X7,X0):-(X6,X5):-(X2,Xd):-(X6,Xc):-(X6,X5):-(X7,X6):-(X6,X5):-(X6,Xc):-(X2,X0):-(X5,X1):-(X7,X5):-(X6,X9):-(X6,Xe):-(X6,X5):-(X2,X0):-(X2,X0):-(X2,X8):-(X6,X3):-(X2,X9):-(X2,X0):-(X5,X9):-(X7,X5):-(X7,X3):-(X7,X5):-(X6,Xb):-(X6,X5):-(X2,X0):-(X4,X5):-(X6,Xe):-(X6,X4):-(X6,Xf):-(X6,X8):-(X2,X0):-(X3,X2):-(X3,X0):-(X3,X1):-(X3,X3):-(X0,Xa):-(X0,Xa):-(X2,Xd):-(X2,Xd):-(X2,X0):-(X7,X3):-(X6,Xe):-(X6,X9):-(X7,X0):-(X2,X1):-(X0,Xa):-(X0,Xa):-(X6,Xd):-(X6,X1):-(X6,X9):-(X6,Xe):-(X2,X0):-(X3,Xd):-(X2,X0):-(X7,X0):-(X7,X5):-(X7,X4):-(X5,X3):-(X7,X4):-(X7,X2):-(X2,X0):-(X2,X4):-(X2,X0):-(X7,X3):-(X6,X8):-(X6,Xf):-(X7,X7):-(X2,X0):-(X7,X1):-(X7,X5):-(X6,X9):-(X6,Xe):-(X6,X5):-(X0,Xa):-(X7,X1):-(X7,X5):-(X6,X9):-(X6,Xe):-(X6,X5):-(X2,X0):-(X3,Xd):-(X2,X0):-(X7,X5):-(X6,Xe):-(X6,X4):-(X6,X5):-(X6,X6):-(X6,X9):-(X6,Xe):-(X6,X5):-(X6,X4):-(X2,X0):-(X3,Xa):-(X3,Xa):-(X2,X0):-(X5,X1):-(X2,X0):-(X5,X8):-(X3,X0):-(X2,X0):-(X6,X2):-(X2,X0):-(X2,X8):-E) => b

(途中を snip! してしまってるのを除けば)めでたく Quine になってます。quine = undefined なのにどうしたことか。

種明かし

インタプリタにかけてみるとわかります。

$ ghci -fcontext-stack=2048 type-level-quine-poc.hs
GHCi, version 7.4.2: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( type-level-quine-poc.hs, interpreted )
Ok, modules loaded: Main.
*Main>

やはり -fcontext-stack=2048 が必要なことに注意。プロンプトが出るまで時間がかかります。

プロンプトが出たら、おもむろに quine の型を見てみます。

*Main> :t quine
quine
  :: (X2, Xd)
     :- ((X2, Xd)
         :- ((X2, X0)
             :- ((X5, X4)
                 :- ((X7, X9)
                     :- ((X7, X0)
                         :- ((X6, X5)
                             :- ((X2, Xd)
                                 :- ((X6, Xc)
                                     :- ((X6, X5)
                                         :- ((X7, X6)
                                             :- ((X6, X5)
                                                 :- ((X6, Xc)
                                                     :- ((X2, X0)
...

中置のコンストラクタを使っているので面食らうかもしれないですが、これは型がリストになっています。Either をリストの cons として使っている感じです (Either head tail のように) 。

このリストの先頭の要素 (すなわち型) は (X2, Xd) です。これは ASCII コードの 0x2d 、つまりハイフンを表しています。その次の要素 (X2, Xd) もハイフン。その次 (X2, X0) は空白。その次 (X5, X4) は T 。同じように解釈を続けて行くと、

-- Type-level ...

というように、ソースコード文字列になっていることがわかります。つまり、quine は項としては undefined だけど型がソースコードを表していたのでした。

コード解説

Quine にするトリックは型クラス Q です。リストの append と Quine の encode を一括しておこなう型レベルの関数として機能しています。

X0 から Xf は nibble (16 進数の 1 文字分) を表しています。型クラス I は、それぞれの nibble を ASCII 文字に変換するための型レベルの関数と、型 X? から対応する整数の値に変換する関数を兼ねています。

文字列を表す型を実際の文字列の値に変換するのは、instance Show のあたりです。

完全な Quine

snip! で省略しない完全な Quine のソースコードは以下。

ref: https://github.com/mame/type-level-quine/blob/master/type-level-quine.hs

quine = undefined の型注釈が長くなったこと以外は poc と同じです。

しかし、このソースをコンパイルしようとするとghc がメモリを食いつぶして OSフリーズするので、動作は確認できていません。コンパイルだけで OS を落とす Quine 。

なので残念ながら未完です。誰かもっと Haskell に詳しい人が効率的に実行できる型レベル Quine を書いてくれることを期待します。

注意 (再掲)

念のためもう一度。この内容は TAPL とは全く関係ありません。

TAPL には、Quine の名前の由来となった Willard Van Orman Quine の著書の引用がちらほらあって何となく嬉しい気持ちになりましたが、もちろん本記事の意味での Quine の話は出てきません。

また、本内容は @keigoi さんの型レベルプログラミング会議の発表内容をちょっと Quine にしてみただけです。なお、@keigoi さんも TAPL の訳者の 1 人です。

本内容とは無関係ですがアフィリエイトを置いておきます。↓クリックするなよ!

型システム入門 −プログラミング言語と型の理論−
Benjamin C. Pierce
オーム社
売り上げランキング: 598

*1:型レベルプログラミングを示唆する記述は 30 章あたりで微妙に出てきます。

2013-03-01

TAPL の訳本「型システム入門 -プログラミング言語と型の理論-」が発売されます

プログラミング言語の「型」の定番書と言われる Types and Programming Languages (通称 TAPL) の翻訳本が、ついに 3 月 26 日に発売されます。

型システム入門 −プログラミング言語と型の理論−
Benjamin C. Pierce
オーム社
売り上げランキング: 598

(↑アフィリエイトなのでクリックするなよ!)

(個人的に) 読んで欲しい人たちへ

「型」の教科書ということで、わりと Ruby の対極にあるような内容ですが、Ruby ユーザ (動的型付き言語しか知らない人) にこそ読んで欲しいと思ってます。

PHP しか知らない人が PHP の良さを語るのが滑稽なように *1 、型がないことのメリット・デメリットを語るには、本気で型がある言語の考え方を学ぶべきです。そのために最適な一冊になっていると思います。

あと、本書の事例研究のテーマは「オブジェクト指向を如何に型付けするか」なので、Ruby に optional な型が欲しいとか言う人はこの本を買う義務があります。

TAPL を読んだことある人たちへ

すでに TAPL をご存知の人にぼくが語ることは正直あまりないのですが、一言だけ。「TAPL の英語は簡単」は大嘘だと思います。

かなり慎重に選ばれた繊細な英語表現だらけで、よほど英語できる&知識のある人でない限り、誤読してるところがあるはず。

おかげで翻訳はかなり難航しましたが、監訳の住井先生と訳者たちで恐ろしいほど (明らかにわりに合わないほど :-) 議論に議論を重ねて出来上がった一冊になってます。

原著を完読した人も、日本語版を読みなおしてみるときっと新たな発見が得られる。はず。

ということで

みなさん是非読んでみてください!

*1PHP ユーザを dis りたいわけではなく、あくまで例です!

2013-01-01 あめましておめでとうございます 2013 このエントリーを含むブックマーク このエントリーのブックマークコメント

あけましておめでとうございます。日本のプログラマには古来より「正月はフラクタル」という習わしがあります。正月はフラクタルに触れて心穏やかに過ごそうというものです。

今年はあまり芸がないですが Substitution tiling で遊んで見ました。以上。

# coding: UTF-8

I = Complex::I
V = Complex(1, 1)

def f(screen, pos, dir, size, minsize = 1)
  [1, 1, 2, 2, 1, 1].each do |mult|
    (size * mult).times { screen[pos += dir * V] = dir.imag == 0 ? "\\" : "/" }
    pos -= (dir *= -I)
  end
  pos += dir
  dir *= I
  if size.even? && size > minsize
    f(screen, pos - dir *  size * I     ,  dir    , size / 2, minsize)
    f(screen, pos + dir * (size * I + V), -dir    , size / 2, minsize)
    f(screen, pos + dir * (size     + 1),  dir * I, size / 2, minsize)
    #(screen, pos + dir                 ,  dir * I, size / 2, minsize)
  end
end

def g(size, minsize = 1)
  marks = {}
  f(marks, 0, -I, size, minsize)
  min_x, max_x = marks.keys.map {|pos| pos.real }.minmax
  min_y, max_y = marks.keys.map {|pos| pos.imag }.minmax
  screen = (min_y .. max_y).map { " " * (max_x - min_x) }
  marks.each {|pos, mark| screen[pos.imag - min_y][pos.real - min_x] = mark }
  screen.map! {|line| line.rstrip.gsub(" ", " ").gsub("/", "").gsub("\\", "") }
  puts *screen
end

g(8, 8); puts
g(8, 4); puts
g(8, 2); puts
g(8, 1); puts

               /\
              /  \
             /    \
            /      \
           /        \
          /          \
         /            \
        /              \
       /               /
      /               /
     /               /
    /               /
   /               /
  /               /
 /               /
/               /
\               \
 \               \
  \               \
   \               \
    \               \
     \               \
      \               \
       \               \
        \              /
         \            /
          \          /
           \        /
            \      /
             \    /
              \  /
               \/

               /\
              /  \
             /    \
            /      \
           /        \
          /          \
         /            \
        /              \
       /\      /\      /
      /  \    /  \    /
     /    \  /    \  /
    /      \/      \/
   /       /       /
  /       /       /
 /       /       /
/       /       /
\       \       \
 \       \       \
  \       \       \
   \       \       \
    \      /\      /\
     \    /  \    /  \
      \  /    \  /    \
       \/      \/      \
        \              /
         \            /
          \          /
           \        /
            \      /
             \    /
              \  /
               \/

               /\
              /  \
             /    \
            /      \
           /\  /\  /\
          /  \/  \/  \
         /   /    \   \
        /   /      \   \
       /\   \  /\  /   /
      /  \   \/  \/   /
     /    \  /    \  /
    /      \/      \/
   /\  /\  /       /
  /  \/  \/       /
 /   /   /       /
/   /   /       /
\   \   \       \
 \   \   \       \
  \  /\  /\       \
   \/  \/  \       \
    \      /\      /\
     \    /  \    /  \
      \  /   /\  /\   \
       \/   /  \/  \   \
        \   \      /   /
         \   \    /   /
          \  /\  /\  /
           \/  \/  \/
            \      /
             \    /
              \  /
               \/

               /\
              /  \
             /\/\/\
            / /  \ \
           /\ \/\/ /\
          /  \/  \/  \
         /\/\/    \/\/\
        / / /      \ \ \
       /\ \ \  /\  / / /
      /  \/\/\/  \/\/\/
     /\/\/\  /    \  /
    / /  \ \/      \/
   /\ \/\/ /       /
  /  \/  \/       /
 /\/\/   /       /
/ / /   /       /
\ \ \   \       \
 \/\/\   \       \
  \  /\  /\       \
   \/ /\/\ \       \
    \ \  / /\      /\
     \/\/\/  \    /  \
      \  /\/\/\  /\/\/\
       \/ / /  \/  \ \ \
        \ \ \      / / /
         \/\/\    /\/\/
          \  /\  /\  /
           \/ /\/\ \/
            \ \  / /
             \/\/\/
              \  /
               \/