Hatena::ブログ(Diary)

純粋関数型雑記帳 このページをアンテナに追加 RSSフィード Twitter

このページはHaskellを愛でるページです。
日刊形式でHaskellなどについての記事をだらだらと掲載しとります。
2004 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 11 |
2007 | 03 | 04 | 05 | 07 | 08 | 09 | 12 |
2008 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 03 | 05 | 06 | 09 | 10 | 11 | 12 |
2010 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 12 |
2011 | 01 | 02 | 05 |
本体サイト

2007年09月22日(土) TCCC Round 4

[]TCCC Round 4 TCCC Round 4を含むブックマーク TCCC Round 4のブックマークコメント

http://www.topcoder.com/stat?c=round_overview&er=5&rd=10924


ついに一問も通らなかった…。

これはきびしい。


・250点

    sum=vector<long long>(n+1,0);
    sum[0]=sum[1]=1;

そんなばかな…。

これが落ちる処理系があるとは。

これからは配列は固定長で取ろうと誓うのであった…。


・500点

50*50*5000のvector<vector<vector<int> > >を確保しようと思ったら、

bad_allocで落ちてた。そんなばかな…。

やはりこれからは配列は固定長で取ろうと固く誓うのであった…。

そこを直してもコーナーケースで微妙なTLEになっていたので、

高速化(というか、境界をループの中でチェックするのでなくて、外でチェックするようにしただけ)

すると通った。もういやだ…。

最悪計算量的には、50*50*100*5000で、他の人たちと同じはずだよなあ…

メモリを少なくてすむ実装にしたらキャッシュに乗りやすかったりするのかなあ…

もうやだ…。


・1000点

ぽかーん。


・Challenge

250点問題をintで計算している人を今まさに落とそうとしていたら

他の人に落とされた。ふがい無さ過ぎる…。


ボーダーは250弱だったので、

250が通ってChallengeが間に合っていても微妙に届かなかったから、

今回はもう縁もゆかりも無かったということで。

もっとTopCoderのことを知らないといけないと思った一日であったが、

TopCoderにそんなに詳しくなるだけの労力が割に合うか不明。

トラックバック - http://d.hatena.ne.jp/tanakh/20070922

2007年09月18日(火) Low-Level Haskell Programming

x86のオペコード体系がだんだん綺麗に見えてきた。

[]Haskellとインラインアセンブリ(構築編) Haskellとインラインアセンブリ(構築編)を含むブックマーク Haskellとインラインアセンブリ(構築編)のブックマークコメント

前回の内容を踏まえて、今回は、Haskellで記述されたアセンブリプログラムアセンブルして、それを前回述べた方法を用いて実行することを目標とする。


本項ではHaskell上でアセンブリプログラムを記述するための言語を構築し、それに対するアセンブラを作成する。


記述の利便性のため、Haskell上で構築する言語モナドで構成する。普通アセンブラで扱えるような形で記述できればうれしい。

foo :: CodeBlock (IO Int)
foo = assemble $ do
  movl eax 777
  movl eax ecx
  movl eax (mem(eax))
  movl eax (mem(eax,ebx))
  movl eax (mem(eax,(ebx,4)))
  movl eax (mem(eax,4))
  movl eax (mem(eax,ebx,777))
  movl eax (mem(eax,(ebx,8),777))
  ret

サイズ指定を容易にするため、gasのようにニモニックでオペランドサイズを指定することにする。そのほかの部分はintel形式を模倣する。このようにコードを記述できてそれを実行できるようにすべく以降で定義をしてゆく。


まず、アセンブリプログラムを表すAsmモナドを定義する。Asmモナド

type Asm a = RWS () [Mnemonic] AsmState a

このように定義した。RWSモナドは、ReaderWriterState能力を持つモナドで、今回のアセンブラではアセンブリの中間コード(上でのMnemonic)を出力するためのWriterと状態を扱うためにStateを利用する。Asmモナドは一塊のコードを示し、これをassembleにかけることによって関数というまとまった単位コードアセンブルされるものとする。


Mnemonicは次のように定義した。

data Mnemonic =
    Imp Mne
  | Uni Mne Size Operand
  | Bin Mne Size Operand Operand
  | Tri Mne Size Operand Operand Operand
  | Rel Mne LabelID
  | Abs Mne CodeBlock
  | Label LabelID

Impはオペランドなしの命令。Uni,Bin,Triはそれぞれオペランドが1,2,3個の命令。RelとAbsは後述。Labelはラベルの定義。


サイズは、1,2,4,8バイトのいずれか。

data Size = SByte | SWord | SDWord | SQWord deriving (Show)

x86オペランドは、レジスタと即値とメモリアドレスがあり、アドレッシングモードは、(ベースレジスタ)+(インデックスレジスタ)*(スケール(1,2,4 or 8))+(ディスプレースメント)の形および、このうち1つ以上が欠けた形を取る。

data Operand =
    Imm Int
  | Reg RegName
  | Mem Address

data Address =
  Address (Maybe RegName) (Maybe (RegName,Int)) Displacement

実際にアセンブリを記述する際はmovlなどのヘルパ関数を用いる。この際、利便性のために引数オーバーロードしてほしい(数値が書かれていれば即値など)。アドレスを指すためにはmemという関数を用いる。これを用いなくても(eax,(ebx,2),1)のような形であればmovlなどで直接オーバーロードできるが、(eax)というような形は(つまり1-tupleは)eaxと区別できないのでそれらを区別するために用いる。引数オーバーロードするために次のようなクラスを定義する。

class AddrMode a where
  toArgument :: a -> Operand

instance Integral a => AddrMode a where
  toArgument n = Imm $ fromIntegral n

instance AddrMode RegName where
  toArgument r = Reg r

instance AddrMode Address where
  toArgument a = Mem a

instance AddrMode Operand where
  toArgument o = o

これでmovlが定義可能になる。

movl :: (AddrMode a, AddrMode b) => a -> b -> Asm ()
movl = tell [ Bin Mov SDWord (toArgument a) (toArgument b) ]

他の命令も同様に定義できる。


ベルおよびジャンプ命令は次のように記述できるようにする。

hoge = assemble $ do
  l <- genLabel
  label l
  ...
  jmp l

genLabelでラベルIDを生成して、それを用いてラベル定義やジャンプ、条件ジャンプを記述する。ラベルIDを文字列にしてユーザが指定の文字列でラベルを記述できるようにしてもよかったが、後のことを考えるとこちらのほうが有利と判断した。


call命令に関してはローカルなラベルではなくて、他の関数を呼び出せなければいけない。他の関数はCodeBlock型で示される同じくアセンブラで生成された機械語列であるとする。

foo = assemble $ do
  ...

bar = assemble $ do
  ...
  call foo
  ...

このように定義すると、例えば上の場合だと、barアセンブルの際にfooの値が必要になる、つまり、fooのアセンブルが終わっている必要がある。あるいは、fooの値はメモリの先頭なのであるから、ポインタの値だけでも決まっている必要がある。これは再帰的に参照している場合に問題になる。それを許す実装も不可能ではないが、必要以上に複雑になるので、ここでは再帰的な参照は許さないものとする。ただし、直接的な再帰は利用される機会も多いのでselfという特別な名前を用いて行えるようにしておく。相互再帰に関しては、今のところおいておく。


このようにAsmモナドを定義すると、これを実行することによってMnemonicの列が得られる。あとは得られたMnemonicをバイト列にしてやればよい(と一言で言っているが、ここが一番大変)。


そのようにしてできたのがこちらである。命令はごく少数しかサポートしていないのであしからず

http://fxp.infoseek.ne.jp/tmp/asm/AsmX86.zip


コード例をいくつか示す。

前回手書きしたコードと同じもの。

import AsmX86

bar :: CodeBlock (IO Int)
bar = assemble $ do
  movl eax 777
  ret

階乗

fact :: CodeBlock (Int -> IO Int)
fact = assemble $ do
  l <- genLabel
  movl eax (mem(esp,4))
  subl eax 1
  jnz l
  movl eax 1
  ret
  label l
  pushl eax
  call self
  popl ecx
  addl ecx 1
  imull eax ecx
  ret

呼び出し例

main = do
  ret <- exec fact 10
  print ret

実行例

$ ghc --make Main.hs

[1 of 2] Compiling AsmX86 ( AsmX86.hs, AsmX86.o )

[2 of 2] Compiling Main ( Main.hs, Main.o )

Linking Main.exe ...

$ ./Main

3628800

このようにごく自然に呼び出せる(くれぐれもx86以外で実行しないように)。


以上のようにHaskell用インラインアセンブリを定義することができたが、AsmモナドHaskell上で構築するものであり、その際にはフルスペックHaskell能力が利用可能である。つまり、これを用いると一般的なマクロアセンブラ能力あるいはそれ以上に便利な機能が実装できる可能性がある。AsmはモナドでありHaskell普通に扱えるデータであるので、これを用いてより抽象的なブロックが作れるだろうし、AsmモナドStateを加えればより便利な機能が実装できるかもしれない。そこで、次回はそちらの方向に話をすすめて、アセンブラをより使いやすいものへと変化させたい。

desumasudesumasu 2007/09/19 07:58 tanakhさんがされていることと同じようなことが、Harpyというプロジェクトで行われているようです。もしご存じでなければ、参考までに。

http://uebb.cs.tu-berlin.de/harpy/

tanakhtanakh 2007/09/20 09:48 これは知りませんでした。確かに同じような書き方で書けるようになっていますね。実装の方法とかがだいぶ違うようなので、参考にさせて頂きます。

通りすがり通りすがり 2007/10/02 11:56 Haskellでインラインアセンブリとは素晴らしいですね。感動しました。実行時動的アセンブリコード生成ということで、C++で似たようなものがありますのでご紹介いたします。
http://homepage1.nifty.com/herumi/soft/xbyak.html

トラックバック - http://d.hatena.ne.jp/tanakh/20070918

2007年09月17日(月) Ultra Low-Level Haskell Programming

非生産的生産活動を行うときほど楽しいものは無い。

[]Haskellとインラインアセンブリ(導入編) Haskellとインラインアセンブリ(導入編)を含むブックマーク Haskellとインラインアセンブリ(導入編)のブックマークコメント

(以下では前提として実行するCPUx86とします。SPARCとかの人はごめんなさい)


Haskellから任意の機械語コードを実行するにはどうすればよいのだろう。

Foreign.PtrにFunPtrという型が定義してあり、これは機械語コードの入っているメモリへのポインタを示す。

さらに、

type IntFunction = CInt -> IO ()
foreign import ccall "dynamic" 
  mkFun :: FunPtr IntFunction -> IntFunction

などとすることによりFunPtrの指すコードを呼び出すためのラッパを生成できる。

型ごとに別個のラッパが必要になり、必要に応じて自動的に定義されるわけでもないので、必要なものは個別に書いてやる必要がある。


これらを用いれば、Haskellからmallocを用いてメモリを確保し、そこにデータを書き込み、それをラッパにかけてやることによって、Haskellから任意の機械語コードを実行することができるだろう。


まず、利便性のために、ラッパを自動的に選択できるよう、FunPtr a から a に変換できる型のクラスを作っておく。

class MkFun a where
  mkFun :: FunPtr a -> a

foreign import ccall "dynamic"
  mkFunInt :: FunPtr (IO Int) -> IO Int
foreign import ccall "dynamic"
  mkFunInt2Int :: FunPtr (Int -> IO Int) -> (Int -> IO Int)

instance MkFun (IO Int) where
  mkFun = mkFunInt

instance MkFun (Int -> IO Int) where
  mkFun = mkFunInt2Int

当面はIntを返す関数とIntを取ってIntを返す関数のみをサポートしておく。


機械語列からはその関数の型を推論することなどできないので、関数の型はこちらが与えてやる。その際に、コードに対して型が付与できるように型を作る。

newtype CodeBlock a = CodeBlock (Ptr Word8)

newtypeでなくtypeでやると、typeは単なるエイリアスになるため、うまく型が付かない。


メモリを確保してコードを書き込むのと機械語列を実行する関数を作る。

writeCode :: [Word8] -> CodeBlock a
writeCode code = unsafePerformIO $ do
  let len = length code
  q <- mallocArray len
  pokeArray q code
  return $ CodeBlock q

exec :: MkFun a => CodeBlock a -> a
exec (CodeBlock p) = mkFun $ castPtrToFunPtr p

これで次のようにして望みのコードを実行させることができる。

foo :: CodeBlock (IO Int)
foo = writeCode
  [ 0xb8, 0x09, 0x03, 0x00, 0x00 -- mov eax,777
  , 0xc3                         -- ret
  ]

main = do
  ret <- exec foo
  print ret

fooは単に777を返す関数で、mainはそれを呼び出してprintしている。

$ ghc --make AsmTest.hs

$ ./AsmTest

777


さて、これでインラインアセンブリの可能性が見えてきた。当然のことながら次は機械語列をHaskellから生成したいという要求が出てくるので、そちら方面に話を進めることにする。

トラックバック - http://d.hatena.ne.jp/tanakh/20070917

2007年09月15日(土) 聖地巡礼

[]聖地巡礼 聖地巡礼を含むブックマーク 聖地巡礼のブックマークコメント

f:id:tanakh:20070915171646j:image:right:w240

もとい、帰省中でございます。

何も無いところね〜。


近所の会社がこんなネタアニメを作るようになるとはのお。

いやいや、いいぞ、もっとやれ。

[]TCCC Round 3 TCCC Round 3を含むブックマーク TCCC Round 3のブックマークコメント

辛勝……!

実際のところ負けのようなもんですけど。


http://www.topcoder.com/stat?c=round_overview&er=5&rd=10908


250点

ねずみそれぞれは捕まえられなくなるまでに捕まえればいつ捕まえてもよいし、

捕まえるのは早ければ早いほどよいので、捕まえられなくなるタイミングが早いものから順に捕まえてよいのと、

待ち時間の短い帽子から使ってよいというのはすぐに分かったのだけど、

いかんせん英語読むのとコード書くのが遅すぎた。


500点

題意を把握するのに相当手間取る。

3ラインで被覆できればよいので、

横3ライン、横2縦1ライン、横1縦2ライン、縦3ラインのすべてを試せば

O(n^4)ぐらいで計算が終わるのでそれで実装したのだけど、

時間がぎりぎりかつ200行ほどコードを書いてしまったので、

実装にバグひとつ。見事に落とされた。

しかし、バグなおしてもSystem Testが1個通らなかったので、

想定パターンが細かいところでひとつ抜けていた模様。

というか、そんな重たい実装をしなくても、

普通に左上からなめながら探索すれば、

ラインのおき方は横か縦かの二通りで、ラインは3個しか置かないから

せいぜい8回探索するだけでなんともあっさり答えが求まってしまいますがな。

莫迦すぎる…。

書き直したら70行ぐらい。

TopCoderでそんなに書かされた時点で見直しを検討すべきか。


1000点

3分ぐらい残ってたからOpenしたけど題意をつかむまでに至らず。


最初200位ぐらいだったからだめかと思ったけど、

みんなぼろぼろ落ちていって意外にも通過してしまった。

どうせ拾った命、次こそは。

トラックバック - http://d.hatena.ne.jp/tanakh/20070915

2007年09月12日(水) SRM

[]SRM 365 SRM 365を含むブックマーク SRM 365のブックマークコメント

久しぶりにSRMにも出てみた。

なんだかSRMはレートが下がった思い出しかないので、

なかなか出るのが億劫になっていたのですけども。


http://www.topcoder.com/stat?c=round_overview&er=5&rd=10780


・300点

約数を列挙するだけの問題だったのだけど…。

約数のうち4で割ると1余るもの - 約数のうち4で割ると3余るもの、を求める問題なので、

実際に約数をすべて生成すればそれでよいのだけど、

何を血迷ったかよくわからない考察を始めて、

その考察は合ってたのだけどちょっとした勘違いから実装を間違えて自滅。

アルゴリズムは、前者をd1後者d3とすると、

d1 =(4で割ると1余る素因数任意個からなる約数の数)*(4で割ると3余る素因数偶数個からなる約数の数)

d3 =(4で割ると1余る素因数任意個からなる約数の数)*(4で割ると3余る素因数奇数個からなる約数の数)

なのと、n=r^2 から、

(4で割ると3余る素因数偶数個からなる約数の数)-(4で割ると3余る素因数奇数個からなる約数の数)= 1

であるので結局求めるd1-d3は、(4で割ると1余る素因数任意個からなる約数の数)と等しくなる。

そういうわけで、素因数分解しながら掛け算すれば答えが求まるはずだったのであるが…。

なんで間違うのかなあ…ぶくぶく……

・500点

細かい考察が終わる前に書いて提出したので、

いまだになんで通ったのか分からん…。

数三つを選んで、それらを含む"もっとも大きな幅の"等差数列としてaptitudeを計算。

反例があると思ったんだがなあ。より小さな幅の等差数列は、

それによってスコアが上がるならそれが含まれるもので尽くされるのかしらん…。

・1000点

時間があんまり無かったから

これまた反例があるよなあと思いながら

普通に前からトポロジカルソートを書いたら普通に落とされましたとさ。

そうか、うしろからか。


とりあえず0問という最悪の事態は避けられて一安心……

なんかしてる場合じゃないな。

トラックバック - http://d.hatena.ne.jp/tanakh/20070912

2007年09月08日(土) TCCC Round 2

[]TCCC Round 2 TCCC Round 2を含むブックマーク TCCC Round 2のブックマークコメント

細々とQualification、Round 1、Round 2と参加していたのですが、

なんだかもういろいろと限界を感じる今日この頃

本日は問題を読むのに辞書を一度も使わなかったのが

微妙にうれしかったところですが、

それよりももうこういう戦いは精神的につらい…。

神経が磨り減ります…。

せめてICPC方式だったらなあ。

Round 4まで行けたら、もう今の私では

よほど運がよくなければ勝てないだろうから、

乾坤一擲、あまり神経を使わずに、全速力で参加してみようと思いますよ。


問題についての感想

http://www.topcoder.com/stat?c=round_overview&er=5&rd=10891


  • 250点 整数 a,b に対して a<=x^k<=b なるx,kのうちkを最大にするものを求める
  • 500点 RLEで現された整数二つを加算する
  • 1000点 コスト最小になるように仕事を割り振る

250点問題は普通ループまわして間に合いそうだったから、普通ループをまわした。

500点問題はどう見てもやるしかなさそうだったからこれもゆるゆると実装。

なんだか伸びに伸びて100行以上も書いてしまった。

最初書いたバージョンには間違いがあったけど、

コード書きながら考えていたテストケースで見つかったのでよかったよかった。

1000点問題は20分ぐらい考えたけどわからず。コストが二乗じゃなければ最小費用流…

というか、そもそもそんなものを持ち出してくる必要も何も無い問題になってしまうが…。

得点の高い人達ソースを見てみると、

とってもグリーディーな感じになっておりました。

ある人にi個目のタスクを追加したときコストの増分を小さい順にソートして、

それを小さい順になめながら、その人にタスクが追加できるなら追加していく、

という方式で、タスクが追加できるかどうかは、

その人ができるタスクいずれかを割り当てるのですが、

すでにほかの人に割り当てられているタスクがあれば、

そのタスクを行っている人に別のタスク再帰的に割り当てて、

そのタスクはその人に割り当てる、ということを行うようです。

これでよいのかどうかは、

そもそもコストの増分の小さい順に追加していっていいのか、と、

この方法で本当に割り当てが可能なときに可能であるとわかるのか、

という二つの点において私には不明なのですが、

後者に関しては、この部分の割り当てを

最大流を用いて行っている人もいたので、

それであれば問題の半分は解決したことになります。

しかし、なんというか、こんなの5分やそこらで思いつくってレベルじゃねーぞ

よくあるタイプの問題なのかなあ。

トラックバック - http://d.hatena.ne.jp/tanakh/20070908