プログラミング」カテゴリーアーカイブ

関数型言語に関して思うこと

ここ最近というわけではないが,関数型言語に関する話題をよく目にするようになったような気がする.何を持ってして関数型言語であるかというのは非常に悩ましい問題ではあるが,おそらく最も古くに生み出された関数型言語がLispであろうことを考えれば,関数型言語の歴史は非常に古い.それに対して,世の中のコンピュータの基盤であるOSなどの低レイヤを支えるc言語がLispより20年近くあとに生み出されたことを考えれば,c言語やその影響を受けた後続の言語(JavaやLLなど)がいかに新しいかがわかるはずだ.

私はもともとc言語からプログラミングを入門し,次にC++を学び,Java,Pythonと進めてきた.特にC++に触れてきた時間は非常に長く,プログラミングの思考回路がC++をもとに組み上がっていると言っても過言ではない.したがって,初めて関数型言語に触れたときは強い隔たりを感じた.特に違和感を感じたのは,関数型言語の記述がアセンブリから完全に乖離している点だった.CやC++などの手続き型言語が,何をしたいのかを書くのに対して,関数型言語が何が成り立つのかを書くというのはよく言われる話だが,コンピュータの根幹をなすアセンブリ言語が前者の立場にあることを考えれば,関数型言語がそのままの形では全く相容れないことは明らかである.

ではなぜそのような関数型言語が今になって注目されているのだろうか.その一つの答えは,関数型言語を支える非常に強力な仕組みである型システムが,プログラムの記述を簡単にし,更にはバグさえも防ぎ得るということにあるではないだろうか.そもそもc言語やそこから派生した言語は,人間がミスをすると簡単にバグが挿入される可能性がある.これは例えれば鋭いナイフのようなもので,その切れ味をうまく活かせれば大抵のことは効率よく行うことができるが,使い方を誤れば自身を傷つけてしまう諸刃の剣となる.これはc言語の前身であるB言語の更に前身であるBCPLの哲学である

BCPLの哲学は、最良を知ると皆が考える暴君がいるのではなく、何が許されて何が許されないのかという決まりが定められているのでもない。どちらかといえばBCPLは、たとえ明らかに馬鹿げた事態に直面したときでさえ、不平を言わずに自らの能力を最大限に活かしてサービスを提供せんとする召使いとして振舞う。彼が何をしていて、細かい制限に制約されないということを、プログラマーは常に理解しているものと考える。
「BCPL, the language and its compiler」より

にあらわれている.これはプログラマが過ちを侵さないという絶対の信頼のもとで成り立っている.しかし,実際にはそのようなことは絶対にありえない.むしろ世の中にこれほど人為的ミスとしてのバグがはびこっているのは,人間がそこまで賢くないことを示唆しているのではなかろうか.

さて,人の書くプログラムには絶対にバグが入り込むと考えたとき,これを防ぐためにはどのようにしたら良いだろうか.関数型言語における,この問題に対する答えはバグが入り込む可能性があるような書き方は,そもそも許さないというものである.関数型言語では,関数の副作用を極力許さないことと,型に基づいた統一的な記述により制約をかけている.このような制約は,動的型付けであり副作用がてんこ盛りのLLから見れば,非常に強いものだが,バグを防ぐ上では非常によく機能することがわかっている.

ある言語が,手続き型言語と関数型言語のどちらであるかは程度の問題であって,完全な線引があるわけではない.pythonやperlなどであっても記述の仕方によっては関数型言語のように書くことができるだろうし,LispやOCamlでも手続き型言語のような記述ができるはずである.しかし,言語のサポートによって関数型言語として代表されるような記述がどこまで可能であるかが変わってくる.特に大きな線引は高階関数が扱えるかどうかではないかと思う.関数型言語が特に流行りだした頃から,多くの言語でラムダ式(無名関数)をサポートするようになったが,部分適用が言語レベルでサポートされているのは殆ど見たことがない.しかし,関数型言語にとって高階関数が無くてはならない存在であることを考えれば,これをサポートしていない多くの言語は一般には関数型言語とは呼べないのではないか.

とにかく,高階関数はもちろんとして,完全に純粋すなわち副作用を持たない言語としてHaskellが有名である.Haskellのすごいところは,その徹底ぶりにある.多くの関数型言語は,副作用を全く持たないことを保証できていない.これはおそらく,利便性の観点から完全に副作用を除外すると,非常に書きづらくなる恐れがあるからではないだろうか.画面に文字を表示するということですら,簡約のやり方によっては表示の順番が変わってしまう恐れがあるため,そのままでは副作用は避けられない.しかし,Haskellではモナドを用いることで,理論的にも妥当なやり方で副作用を追いやることに成功している.さらに,Haskellは遅延評価を用いることで便宜的とはいえ,加算無限の概念を記述することも可能である.Haskellのすごいところは,そういった,一見達成困難なことを理論的に美しい方法で,コンピュータ上の実装のレベルまで落とし込んでいる点にある.これにより,Haskellは数学と非常に相性が良い.特に関数型言語の利点である,性質を記述することでプログラムが可能であるという点がうまく引き出されており,これは数学の式の記述に非常に近いものになっている.

ここまで思ったことをつらつら書いてみたが,あまりに何も考えてなさすぎてとりとめのないものになってしまった.とにかく,最後に私が言えることは,関数型言語を全く知らない人はどのようなものかを一度勉強してみるべきだということだ.そこには,手続き型言語だけでは感じることができない,理論によって整理されたきれいな世界が広がっているのだから.

内容についてどう思いますか?
  • いいね (2)
  • だめ (1)

配列の中で2番めに大きい要素

最近ブログを書いてないって言われたので,何かを書こうとおもったけれど,何を書くのが全く思いつかないので,今日,聞かれた質問について書こうと思う.

聞かれたのは,与えられた配列の中から2番めに大きい要素を知る方法である.1番大きい要素の取得の仕方はよくある話だが2番めはあまり聞いたことがない気がする.どうやって解くのが最も効率が良いだろうか.ちなみにプログラム演習の課題のようなので,あまり高度なライブラリを使用するのは避けなければいけないという制約がついている.

最も簡単な解法は,一番最大の要素をまず見つけ出し,次にその要素を取り除いた配列から最大の要素を取り出す方法だ.これは愚直だがわかりやすく書きやすい.ただし,最大値を求めるループを2回使う必要があり,いくらか冗長な気がする.次に,思いつくのはソートして2番めの要素を取り出す方法である.スクリプト言語を使っているのであればこれが一番ありがちなのではないだろうか.ただし,一から全て実装する場合は,これは少し面倒だ(ライブラリがまったくないそんな状態は普通ないのだが).

さてここではよりフォーマルな形で定式化することで,この問題を効率よく解く方法を考えたい.まず与えられた配列を\(a_n, \dots, a_1\)という数列であるとしよう.\(a_k, \dots, a_1\)の中で一番大きい要素を返す関数を\(f(k)\)とする.このとき明らかに
$$f(k) = \begin{cases}
-\infty & (k=0) \\
f(k-1) & (f(k-1) \geq a_{k}) \\
a_{k} & (otherwise)
\end{cases}$$
が成り立つ.次に,\(a_k, \dots, a_1\)の中で2番めに大きい要素を返す関数を\(g(k)\)としよう.定義から明らかに\(g(k) \leq f(k)\)である.\(g(k)\)の計算は\(f(k)\)と非常に近いはずである.しかし,2番めであるという制約が,問題を難しくしている.まず,\(g(k)\)と\(g(k-1)\),そして\(a_k\)の関係を考えよう.まず,\(a_k\leq g(k-1)\)のときは明らかに\(g(k)=g(k-1)\)である.次に,\(a_k> g(k-1)\)の場合は,\(g(k)=a_k\)としたいところだが,\(f(k)\)との兼ね合いがあるため,それだけでは条件として不十分だ.実際には,\(f(k-1) < a_k\)のときは,\(g(k)\ne a_k\)としなければ,2番めに大きいという条件を満たせない.逆に言えば,これだけで必要条件を満たすことができる.したがって,まとめれば
$$g(k) = \begin{cases}
-\infty & (k=0) \\
g(k-1) & (g(k-1) \geq a_{k}) \\
a_{k} & (f(k-1) \geq a_{k}) \\
g(k-1) & (otherwise)
\end{cases}$$
である.思ったより簡単だった.

内容についてどう思いますか?
  • いいね (2)
  • だめ (1)

pytorchで簡単に高速化する方法

pytorchを最近ちょくちょく目にする割には,あんまりこれを使ってるよっていうブログが増えない今日このごろ,pytorchでボトルネックになるのは一体どこなんだろうということでネットで調べていたら次の記事を発見.
https://discuss.pytorch.org/t/pytorch-performance/3079

ここによれば,

というのをつけるだけで速度が爆速になるらしい.
やってみるとモデルがあんまり良くなかったのかイマイチ高速化出来たのか微妙な感じだけれど,まあ多くの場合はいいらしいのでメモ.

内容についてどう思いますか?
  • いいね (1)
  • だめ (0)

pythonでバイナリファイルを一気に読み込む方法

これすごい需要があると思うのに,調べてもstructの使い方とか,ファイル読み込みの方法ばかりが出てきて,具体的にどうやってやるのかいつもわからなくなるのでメモ.

単に以下のコマンドを実行すればいい.ただしここではfloat(4byte)のデータがバイナリで詰まってるファイルを前提とする.

ここでdataが読み出された目的のデータ.もしintとかほかのデータ型なら単に’f’を’d’にしてやればいい.

内容についてどう思いますか?
  • いいね (3)
  • だめ (1)

conemuでWSL使用時に256色使用する

罠だらけだったので備忘録.

手順

基本的なやり方は,公式ページのとおり.
ただ,なかなかうまくいかないので,自分の方法を示す.

conemuでWSL(Windows Subsystem for Linux:BoW)を直接使用した場合は256colorにならない.ただしcygwinを通すと256色にできるので,cygwinとWSLのブリッジ(wslbridge)を使用する.
ただし当然,これを起動するためにはcygwinが必要だが,WSLを使っているのにcygwinを入れるのは何か違う.そこですでにビルドされたものを使用する.それはここからダウンロードできる.インストーラを実行すると,デフォルトでC:\Users\username\AppData\Local\wslttyにインストールされる.

また,conemuでwslbridgeを利用するのにconemu-cyg64.exeも必要となる.それはここからダウンロードする.
7zを展開すると,conemu-cyg64.exeが手に入るので,これを先程のwslttyのbinフォルダに突っ込む(C:\Users\username\AppData\Local\wsltty\bin).

ここまでくれば必要な実行ファイル類は全て揃う.
次にC:\Users\username\AppData\Local\wsltty\bin\wsl.cmdを次の内容で作成.

この部分は,公式ページと少し違うので注意.

最後に,ConEmuのSettingsから,Startup → Tasksで{Shells::WSL}を作り,

を実行コマンドに指定すればok.

このタスクを実行すれば無事256色になっているはず.

内容についてどう思いますか?
  • いいね (5)
  • だめ (0)

ICPC 2005 Domestic D Traveling by Stagecoach

最近,なんやかんやあってICPCの問題を解いている.せっかく解いたのでD問題について解説してみる.もっといい方法もあるのだろうけど,とりあえず基本方針だけでも.

問題:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1138&lang=jp

考え方

この問題は馬車券によって馬の数が変わるため,それによりグラフの重みが変化する.したがって,ダイクストラ法のような経路探索アルゴリズムは使用できない(厳密には嘘.馬車券の状態まで含めてノードにすれば使える).かと言って,深さ優先探索や,幅優先探索するにもグラフが大きすぎるため厳しいものがある.一見手も足も出ない用に見えるけれど,こういう場合は動的計画法でどうにか出来ないか考えてみるといい.

この問題はよくよく考えてみると,今まで進んできた経路はどうでもいいことに気がつく.大切なのは,今どこのノードにいて,そこにたどり着くまでにどれだけのコストと馬車券を使用したかということだけ.そのためにどういう道順できたのかは,わからなくたって問題ない.これを使って漸化式を建てられれば,解けそうな予感がするので,実際にやってみる.

立式

式に落とすために変数を定義しよう.まず都市の集合を\(A\)とする.このとき,ある都市\(a \in A\)から直接道路でつながっている都市の集合を\(P(a)\)と表記しよう.また都市\(a\)から隣の都市\(b\)への距離を関数\(C(a,b)=C(b,a)\)で表す.次にすべての馬車券の集合を\(B\)と表し,今までに使用した馬車券の集合を\(Q_n\)とする.このとき\(n\)は移動した回数のこと.以上の変数を用いてある都市までの最小の総移動時間(コスト)\(f\)について次のような漸化式が成り立ちそうなことがわかる.

$$f(Q_n, a)=\min_{q\in (Q_n – Q_{n-1}), b\in P(a)} \left( f(Q_{n-1}, b) + \frac{C(a,b)}{q} \right) $$

ここで注意しなくちゃいけないのは,あくまで左辺が与えられたときに右辺を計算するということ.何が言いたいかというと,都市\(a\)にたどり着くために使用する馬車券は決まっていて,それでどれだけコストが抑えられるか計算するのが上の式が表していることの意味.だから\(Q_n\)が与えられたときの\(Q_{n-1}\)を計算することになる.おんなじように\(b\)もaからアクセスできる都市を手当たり次第試す必要がある.あとは上の式を実際に適用して解けばいい.

プログラミング

次が実際に僕が書いたプログラム.中身は上の式をただ落とし込んだだけなんで説明は省略.

 

内容についてどう思いますか?
  • いいね (2)
  • だめ (1)

BoWで音を鳴らす

Windowsの次の大型アップデートはCreators Updateというらしい.このCreators Updateでは様々な変更がなされているらしいが,今回注目したいのはBash on Windows(BoW)である.今までは日本語が不自然に切れてしまったり,ちょっとしたことで落ちてしまったりと微妙な感じだったが,今回のアップデートでは随分完成度が高くなるとのことである.

この新しいBoWがどの程度の完成度なのか非常に気になったので,試しに最新のビルド(番号は忘れた)をインストールして試してみることにした.インストールした直後はなぜかWindowsが不審な動きをして,非常に焦ったが時間が立つと勝手に治っていつもどおりの状態になった(よくわからない).次にBoWを起動して使ってみると,確かに今までと比べて色んな所が改善されており,これならある程度常用に耐えられるかもしれないと感じるまでになっていた.しかし,残念ながら音を流すことができない.私としては音声ファイルを再生して確認したい場面が多いため,これは非常に困る(音声関係もやっているので).そこでどうにか音を流す方法を調べたところ発見できたので備忘録として残しておこうと思う.

まずlinuxで音を流すといえばpulse audioを使うのが標準的だろう.ただしBoWはホストのオーディオデバイスを叩くことができない.そこでネットワーク経由でデータをホスト側に転送する方法が考えられる.具体的にはWindows用のpulse audioサーバを用意し,そこにBoW側のpulse audioを接続する形だ.この方法であればネットワークつながっていさえすれば音を流せるはずである.ここではその設定の詳細は次のサイトを参考にした.

http://nishio.hateblo.jp/entry/20111215/1323962652

さてこれに合わせて設定を行ったわけだが,残念ながらうまくいかない.

どうやら内部のpulseaudio側でクラッシュしているようだ.これをどうにか解決したいところである.そこでgoogleで調べると次のURIを発見した.

https://github.com/Microsoft/BashOnWindows/issues/486

これに従えばpulseaudioのソースコードを修正することで起動させることができるらしい.そこでまずはpulseaudioのソースコードをgitを使って手に入れる.

つぎにsrc/pulsecore/mutex_posix.hを編集し,23行目あたりを次のように編集する.

これで./autogen.shと言いたいところだが,実行したところ私の環境ではエラーが出てしまった.どうやらlibtoolのバージョンに伴うエラーのようだが,そもそも必要なバージョンより新しいものが入っているのでこれはおかしい.そこでこの部分をコメントアウトした(もっといい解決方法がある気がする…).具体的にはconfigureの10206行目にある

の部分である.コメントアウトできたら./autogen.shをする.もしエラーが出たら,基本的にパッケージ絡みのエラーだと思われるので必要なパッケージをインストールしまくる.必要なパッケージはエラーメッセージで検索すればわかるだろう../autogen.shが成功したら,次に下記のコマンドを打ち込む.

これでインストールは終了である.

さてここまでやって先程と同様にvlcを起動してもうまくいかない.なぜならvlc側でロードされる動的ライブラリはあくまで標準ライブラリのpulse audioのものであって,今回用意したものではないからだ.そこで次の環境変数を設定することで動的ライブラリをすり替える.

これをした後にvlcを利用するとうまくいくことが確認できる.めでたしめでたし.

 

内容についてどう思いますか?
  • いいね (0)
  • だめ (0)

VCSのエラー

verilogエミュレータとして有名なSynopsysのVCSだが,次のようなエラーが出て実行できないバグに出会った.

一体何が起こったのかと思いきや,gccの引数を見たところリンカに渡すファイルの順番が正しくないことが原因であることがわかった.そこで

vcs -LDFLAGS -Wl,-no-as-needed ~~~

という風にリンカのオプションに-no-as-neededを加えるようにしたらうまく動作した.

備忘録

内容についてどう思いますか?
  • いいね (0)
  • だめ (0)

FPGAでCPUを実装して、テトリスを動かした

先に断っておくが、以前のブログは残してあるというか放置してある。単純に新しいサーバを借りたので、以前のブログから移ったので放置状態になっているだけだ。おそらく更新することはないので、向こうは気にしなくて構わない。

また、今回の記事では自作CPUを作成したことについて話すつもりだが、私は決してハードウェア設計について詳しいわけでも何でもない。むしろ今回作成したものが初めてといっていいだろう。したがってハードウェア設計に通じた人であれば、眉唾物な内容である可能性がある。よって、ここで書いている内容を絶対のものと信じず、むしろ疑ってかかってほしい。ここの内容に騙されたといわれても、私は責任をとれない。

さて、私の大学では研修Aと呼ばれる、各研究室で課題を設定される必修単位がある。私の研究室では、この研修の半分の時間を使ってCPUを作成し、もう半分は好きなものをFPGAで作るということになっている。後半の自由課題は前半で作ったCPUと関連させる必要はない。したがって比較的自由に好きなものを作れるのだが、私は前半の課題で設計したCPUを強化させることとした。

そもそも、前半で作成するCPUはとてもCPUと呼べるような代物ではない。具体的にはパタヘネに掲載されているシングルサイクルプロセッサからパイプラインまでの内容をFPGAで実装するという内容なので、ほとんどの命令はサポートしないし、ピン入出力さえ行うことができないお粗末なものである。例外もないので割り込み処理もできず、仮想メモリもサポートしないのでOSすら乗らない。しかし、最小限の骨組みだけでも作成することで、CPUの動作の基本原理を学ぼうというところにその趣旨があるのだろう。実際、パタヘネを参考にすれば、必要なデータパスはすべて掲載されているので、私がわざわざここで説明しなくても誰でも作ることができる。おそらく最大の問題はむしろFPGAのボードを手に入れるほうではないだろうか。

しかし、私はとてもじゃないがそんなのでは満足できなかった。せっかくCPUを作るなら最低限OSの動作保証をするべきだろうということで、そこからOSが動作するのに必要な機能をどんどん実装していくことにした。最終的な目標はOS動作だが、研修Aの時間で作ることができなかったため、続きは今後個人的にやっていくこととした。したがって現段階ではCPUの動作のみしか確認していない。とりあえずデモとしてテトリスを作成し、これをgccでクロスコンパイルしたものを動作させた結果の動画を掲載する。

画面のすぐ前にあるキーボードの隣にあるのがFPGA(DE0-CV)であり、これに液晶と手前のキーボードが接続されている。今回参考したアーキテクチャはパタヘネに合わせてMIPSだが、その中でも簡単なものとしてR3000プロセッサという、プレイステーションにも搭載されたものをまねて作成した。せっかく作ったのでソースコードを上げようかと思ったが、とりあえず中身があまりきれいではないので、一度全体を作り直そうかと思っているところである。でき次第アップロードしようかと思っている。

参考にした文献を一応挙げておくと、

これが和書としては詳しい。ただし古い本であるので、もしかしたら手に入れるのが難しいかもしれない。と思ったらAmazonには中古が大量にあるようだ。ちなみに私は大学の図書館で手に入れたので購入していない。

また

MIPS32™ Architecture For Programmers Volume I: Introduction to the MIPS32™Architecture

でグーグルで検索してみると、いろいろpdfが出てくるだろう。これらを参考にすればMIPSについてはずいぶんな情報を得られるはずである。もちろんパタヘネも役立つはずである。特にパタヘネの命令表は非常に見やすく便利である。

まだまだFPGAが高価なためか、ネット上にはFPGAにまつわる情報がほかの組み込み系(例えばマイコンで自作するといったような)の話題と比べると少ないように感じる。今後技術的な内容については、ソースコードを直していく際に触れていく予定なので、それがそれらに対する一助になれば幸いである(といっても私のやる気がなくなればそれで終わってしまうわけだがw)。

続き書きました.

FPGAでCPUを実装する(1)

内容についてどう思いますか?
  • いいね (7)
  • だめ (2)

カルマンフィルタとEMアルゴリズム

この辺りの話についての記事が恐ろしくWEB上では枯渇しているようだ。中にはMATLABによる実装なども見つけることができるが、私がMATLABが好きではないという至極個人的な理由で、そのようなものは受け入れられない(そもそもあんなに言語として欠陥のある物を、高い金を出して購入するという風習を理解できない)。

今回、諸事情でカルマンフィルタと、それのオフライン実装、加えてEMアルゴリズムによるパラメータの推定までを行う必要があった。そこで、そのコードに多少の説明を加えて公開しようと思ったわけである。ただし、私は別に専門家でもなんでもないので、場合によっては内容に不備や間違いが含まれている可能性がある。したがって、ここに記載された内容により何か不利益を被るようなことになったとしても、私は責任を取ることは出来ない。よって、読者は内容を鵜呑みにせず自分の目で正しいかどうかをよく確かめてほしい。また、なにか気づいたことがあれば、些細な事でも連絡をいただけるとありがたい。

まずは定義式を確認しよう。

$${\bf z}_n = {\bf A}{\bf z}_{n-1} + {\bf w}_n$$

$${\bf x}_n = {\bf C}{\bf z}_{n} + {\bf v}_n$$

$${\bf z}_1 = {\bf \mu}_{0} + {\bf u}$$

ただしここで

$$p({\bf w}) = {\cal N}({\bf w|0,\Gamma})$$

$$p({\bf v}) = {\cal N}({\bf v|0,\Sigma})$$

$$p({\bf u}) = {\cal N}({\bf u|0},{\bf P}_0)$$

さてカルマンフィルタの目的は、観測値$${\bf x}_n$$から内部状態$${\bf z}_n$$を導くことである。詳しい説明は他のページに譲るとして,この問題はガウス性ノイズが邪魔となり簡単には求めることは出来ない。しかし、うまいことやることでこれは計算可能である.

ここまでの話はどこにでも乗っていることだ。重要なのはここからで、今までの枠組みでは$$\bf \Gamma$$や$$\bf \Sigma$$などは事前に知っている必要がある。しかし、世の中そんな都合のいい話ばかりではない。私たちは問題に取り組む際、パラメータを都合よく知っているといつでも仮定できるわけではない。実際問題としては、観測値$${\bf x}_n$$から内部パラメータを推定できることが最善だろう。そのための解決策としてここではEMアルゴリズムを使用する。これについても詳細は省略するが(知りたければコメントを書いてほしい)、要約すれば初期値を与えたあとに、そこから反復計算を行い、収束した頃にはだいたいちょうどよいパラメータ値になるというものである(超雑)。詳細は置いといて、実際のコードを下に示そう。

これがクラスファイルである。と言ってもstructかつすべての変数がpulicなので到底まともなクラスとはいえないが。使い方は次の通り

ここではノイズの乗ったsin関数について、そのノイズ除去を行っている。実際の出力結果をgnuplotで表示したものがこれ

test

色が気持ち悪いことを除けば、特に問題はなさそうだ。

内容についてどう思いますか?
  • いいね (3)
  • だめ (0)