2007-07-01

■

7月

2007-07-01

今更

大分前にHaskellで、多項式周りのアルゴリズムを色々実装して遊んでたけど、多項式型は、たぶん、誰でも考えるとおり

data Polynomial a = Const a
                  | Var String
                  | PLUS (Polynomial a) (Polynomial a)
                  | MULT (Polynomial a) (Polynomial a) deriving (Show,Read)

instance (Num a,Ord a) => Num (Polynomial a) where
 p+q = normalize(PLUS p q)
 p*q = normalize(MULT p q)
 p-q = normalize(PLUS p (MULT (Const (negate 1)) q)
 fromInteger n = Const (fromInteger n)

みたいな定義になってる。normalizeは、多項式を適当な標準形に直す関数。

で、がんばってパーサ書いたり、変数に値代入した時は〜とか色々やってたけど、Haskellって

Prelude> (\x y -> 2*x*x+y+3) (Var "x") (Var "y")
PLUS (MULT (Const 2) (MULT (Var "x") (Var "x"))) (PLUS (Var "y") (const 3))
Prelude> (\x y -> 2*x*x+y+3) 4 (Var "hoge")
PLUS (Var "hoge") (Const 35)

とかできてしまうんだよなぁって、気付いた。大したことじゃないけど、私は結構感動した。

逆もできるとよい。つまり、PLUS (MULT (Const 2) (MULT (Var "x") (Var "x"))) (PLUS (Var "y") (const 3))みたいな表現から、(\x y -> 2*x*x+y+3)みたいな式を得たい。式つくるだけなら、

--Language.Haskell.THをimportすること
expandToHs :: Polynomial Integer -> Exp
expandToHs p = LamE (map VarP $ vars p) (mkBody p)
 where
  vars(Const _) = []
  vars(Var x) = [mkName x]
  vars(PLUS p q) = nub $ (vars p)++(vars q)
  vars(MULT p q) = nub $ (vars p)++(vars q)
  mkBody (Const n) = (LitE (IntegerL n))
  mkBody (Var v) = (VarE (mkName v))
  mkBody (PLUS p q) = InfixE (Just (mkBody p)) (VarE (mkName "+")) (Just (mkBody q))
  mkBody (MULT p q) = InfixE (Just (mkBody p)) (VarE (mkName "*")) (Just (mkBody q))

とかでしまい

Prelude> ppr $ expandToHs ((\x y ->2*x*x*x+y*3) (Var "a") (Var "b"))
\a b -> (2 * (a * (a * a))) + (3 * b)

で、evalすればいいんだけど、そうすると、モナドが顔を出すので、なんかイヤ。型に厳しいhaskellでは仕方ないか

2007-07-01

量子こんぷーた

Modeling quantum computing in haskell
http://www.cs.indiana.edu/~sabry/papers/quantum.pdf

　　(　ﾟдﾟ)
＿(__つ/￣￣￣/＿　
　　＼/　　　　/
　　　　￣￣￣

　　( ﾟдﾟ )
＿(__つ/￣￣￣/＿　
　　＼/　　　　/

別に、こんなん探してたわけではないんだけど、偶然見付けてなんか笑ってしまった。ちなみに読んでない。sabryって、確かFelleisenと、call/ccの公理つくったりしてたような気がする。最近は、量子プログラミング(?)の論文を何本か書いてるようで
http://www.cs.indiana.edu/~sabry/

ぐぐったら、quantum programming languageみたいなキーワードで研究してるひとは結構いるっぽい。Sabryの論文が、量子回路ベースなのに対して、簡単な高級言語+コンパイラ(というか、対応する量子回路を直接生成するっぽいけど)も提唱されている模様。
Compiling a functional quantum programming language
http://www.cs.nott.ac.uk/~gmh/bctcs-slides/grattage.pdf

まだ、まともにマシンもないのに、よくやる。今年頭に、うさんくさいと評判のデモは一応あったけど
http://www.youtube.com/watch?v=VQul2asgXbw

SICPの次の版があるなら、量子コンピュータの章とか設けられたらおもろい

2007-07-01

Superoperatorってなに

#ここに書いたことは、論文チラッと見て妄想で補完しただけなので、全部間違ってるかもしれない

そのSabryの最近の論文で、density matrix+superoperatorで量子力学を定式化すると、superoperatorはArrowの公理満たして、だから、量子回路の記述には、Arrow使うといいんじゃね?みたいなことが書いてあった気がする

superoperatorがArrowの公理満たすってのが何か深い意味がある事実なのかどうかはともかく(単にsuperoperatorの積はsuperoperatorだとか、そういう程度のことを言ってるだけなんじゃないかと思う)、古典的な普通の論理回路でもArrow使うといいよってのは、Hughesが最初から言ってるんで、それはいいことにする。

で、密度行列は分かるけど，superoperatorとか初めて聞いたのだった
http://en.wikipedia.org/wiki/Superoperator
によると、トレースを減らさない、完全正値写像という定義。多分、密度行列の時間発展は、superoperatorになるよってことだと思うんだけど、
・密度行列のトレースって時間発展しても1じゃね？トレースが減少しないって条件は弱いような
・密度行列は正行列だから、時間発展がpositive mapってのは自明だけど、completely positive mapになるって条件は強いような
という2点が腑に落ちない。まぁ、実はsuperoperatorは時間発展じゃないっていうオチかもしれないけど

以下，V,Wを複素ベクトル空間としたとき、Hom(V,V)からHom(W,W)へのsuperoperatorを単に、VからWへのsuperoperatorと呼ぶことにする。論文には、SuperというArrowがでている。例えばSuper (Bool,Bool,Bool) Boolという型は、概念的には、8次元ベクトル空間から、2次元ベクトル空間へのsuperoperatorの全体と考えればよいんだろう。通常の波動関数+ユニタリ変換という定式化に比べてのメリットは、一般にsuperoperatorの定義域と値域(上のVとW)が違っていても構わないってことかな。

問題点。最後の方に、この定義だと、arr(\(x,y)->y)みたいな物理的にありえない計算というか回路も書けてしまう、これ克服するには、線形型備えた「量子プログラミング言語」使うといいんじゃね?というようなことがサラッと書いてあるけど、どうだろうね。

2007-07-01

FPGA最終回

なんかLavaに2種類あるとか書いてある。Xilinx-Lavaってのは、そもそもどこかで入手可能なのかもよく分からんのだけど。まぁいいか
http://www.cs.chalmers.se/~koen/Lava/
それはいいんだけど、とりあえず分かったことは、今のLavaは全然未完成。Lavaのサイトに、思い切り
An implementation of Lava for Xilinx's FPGAs will be made available at the Lava download page shortly. Until there here is a snapshot: lava-0.1b.tar.gz
とか書いてあった

気付くのおせえよ。まあ、現時点でも組合せ回路はがんばれば書けると思うけど，順序回路は今のLavaでは多分書けない気がする。というわけで、Lavaが完成するまで待とう。いつ完成するのか知らないけど。VHDL覚えるとか、自分でLava補完するとかいう選択肢もあるけど、まあめんどくさいな

・variable-freeな全加算器
ふるあだー程度でも、基本関数とコンビネータの組合せで書くのは難しいかもしれないと書いたけど，そんなこともなかった。まぁ、なにを基本関数とするのか、決めてないんでアレだけども

halfAdder = fork2 >-> (and2 <|> xor2)
fullAdder = (halfAdder <|> return) >-> flip' >-> (return <|> halfAdder) >-> flip' >-> (return <|> or2)
 where
  flip' = (flip2 <|> return) >-> switch

flip2 :: (Combinational m bit) => (bit,bit) -> m (bit,bit)
flip2(x,y) = return (y,x)

switch :: (Combinational m bit) => ((bit,bit),bit) -> m (bit , (bit,bit))
switch((x,y),z)=(x,(y,z))

とかで。fork2はLavaに含まれてる関数で、
fork2 a = return (a,a)
という定義。

まあ、flip'が、なんとなくエレガントにいかないというか、こういうのを差し込んでいくと無駄に記述が長くなる。それに

fullAdder ((x,y),z) 
 = do (s1,c1) <- halfAdder (x,y)
      (s2,c2) <- halfAdder (s1,z)
      c3 <- or2(c1,c2)
      return (s2,c3)

の方が分かり易いことは否めない