活動報告(2019年1月)

昨年末に「2018年振り返り」という記事を書いたが、これから当面の間、ああいう振り返り記事(活動報告)を定期的(1ヶ月か2ヶ月ごと)に書いていきたいと思う。

昨年の間は「週刊 代数的実数を作る」の連載とか技術書典5とかAdvent Calendarの記事とか、色々目標があったが、年が変わるとそういう差し迫った目標はない。では何をするか。

SML処理系の進捗

https://github.com/minoki/DamepoML

去年の夏に書きかけていたSML処理系が放置されていたので作業をした。取り組んだのは

  • 型推論
  • パーサーのinfix周り(後回しにしていたやつ)

の部分である。パーサーはinfix周りを処理してだいたい完成した(一部のシンタックスシュガーはまだ)ので、あとは型推論をもうちょっとちゃんとやって、コード生成に繋げていきたい。

代数的数のHaskell実装の進捗

https://github.com/minoki/algebraic-numbers

「代数的数を作る」で作ったようなやつをもっとちゃんとしてHaskellパッケージとして使えるようにしたいと思っている。そのための作業を気が向いた時に行っている。

1月は、代数的実数を倍精度浮動小数点数(Double型)へ変換する関数 toDouble を実装した。一般には代数的実数は浮動小数点数ではないので変換の際には丸めを行うわけだが、最近接以外の丸め方向も実装できたと思う。それにしても、正規でない浮動小数点数の扱いは面倒だ。

Windows環境(自作PC)のSSDが死んだ

うちには2013年ごろに組んだPCがあって、Windowsを入れている(最初はLinuxだったが、Linuxではこのマザボ上のNICでWake on LANができない、複数のディスプレイに異なるDPIを設定できない、などの困難があってWindowsを入れた)。

しかし、そのPCのSSDの調子が以前からおかしかった(仮想環境のLinuxが起動しなくなったり、でかいGitリポジトリのデータが破損してgitコマンドがクラッシュしていた)。おかしいとわかった時点で新しいSSDを買ってデータを移行するなどの措置を取るべきだったのだが、それをサボっていた結果ついにWindowsが起動しなくなった。

どうやら簡単には修復できなさそう(Windowsのインストールディスクからは認識すらされない)なので、新しいSSDを買ってWindowsを再インストールすることにする。

(使っていたSSDには3年保証があってこのSSDを入れてからは2年くらいしか経っていないので保証で交換してもらえそうな気がするが、購入時のレシートを探さないとどうにもならなさそうな気がするので、保証は後回しにしてSSDは新規に買うことにする)

使っていたSSDは2.5インチSATA接続のやつで、使っているPCケースでは設置場所にアクセスするのにネジを6本以上外す必要がある。しかも電源ケーブルとSATAケーブルの接続が必要で、配線も面倒である。

最近はM.2と言ってマザーボード上に直接挿せるSSDが流行っている。M.2であればケーブルの配線も必要ないし、マザーボード上に直接載っているので取り回しが楽そうだ。しかし、2013年に買ったマザーボードにはM.2スロットはない。

そこで、M.2 SSDを挿せるPCIeカードを介してM.2 SSDを使うことにする。ただ、マザーボードはNVMeみたいな最新のイケイケ規格は喋れないので、SATAを喋るM.2 SSDを選び、そういうSSDに対応したPCIeカードを使う必要がある。

というわけで選んだSSDはWDの青いやつ(500GB)、選んだPCIeカードはainexのAIF-06Aである。PCIeカードにはSATA端子がついていてケーブルを介してマザーボードのSATA端子につなぐ。結局ケーブルかよ!という気もするが、それでも電源ケーブルを繋がなくて良い(マザーボードから取れる)のはメリットだし、うちのPCケースで2.5インチHDD/SSDの接続場所にアクセスするのにネジを6本外さなくても良いのはメリットだ。

PCIeカード(AIF-06A)にSSDを載せたところ

PCIeカードをマザーボードに挿したところ

そんなわけでSSDを設置して、Windowsのインストール。最近のWindowsはMSの公式サイトからインストールディスクのイメージを落とせるし、ライセンス認証も再インストールの場合はよしなに計らってくれる。便利だ。

問題は、不自由で邪悪なソフトウェアの認証(プロダクトキーとかそういうの)がどうなるか、だ。幸い、使っていたDVD/Blu-rayプレイヤーはどうにかなった(インストーラーの再ダウンロードはできないようだったが、以前ダウンロードしたインストーラーが残っていたのでそこからセットアップできた)。後は何があったっけ……。

1月末時点ではまだ開発環境とかのセットアップはできていないが、気が向いた時にちょいちょいやっていきたい。

Haskell周り

型クラスの和

GADTsを使って型クラス制約の和を表現する記事を書いた。

Haskellで型クラス制約の和を表現する

もともとこのテクニックは数学の完全体 (perfect field) をHaskellの型クラスとして表現する方法を考えていた時に思いついたものだが、難しい数学の例で説明してもその辺のプログラマーには伝わらない気がしたので、記事の中での例としてはIntegerとBoundedを使った。

フィボナッチ数

Haskellコードの例でフィボナッチ数を計算するのに

fib :: Int -> Integer
fib 0 = 0fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

みたいな非効率極まりないコードを紹介されるのは……よくない。

というわけで、

Haskellでフィボナッチ数列 〜Haskellで非実用的なコードを書いて悦に入るのはやめろ〜

という記事を書いた。この記事ではフィボナッチ数を順番に計算していく方法と、n番目のフィボナッチ数をピンポイントで計算する方法(ビネの公式、行列のべき乗)を紹介した。

その後考えてみるとビネの公式を使う方法も行列のべき乗の方法も改善の余地があるな……と思ったので

最速のフィボナッチ数計算を考える

という記事を書いた。こちらでは、モノイドの話も織り交ぜて最終的にfast doublingと呼ばれる方法を導出している。早い方法を天下り的に与えるのではなく、既知の方法の改良として、割と自然に話を持っていけたのは良かったと思う(自画自賛)(ほんまか?)。

unboxed vectorとnewtype

そういう記事を書いていたところ、ツイッターでフィボナッチ数(の一般化)を題材にした競技プログラミングの問題を教えてもらった。

https://tdpc.contest.atcoder.jp/tasks/tdpc_fibonacci

フィボナッチ数の記事を書いていた手前、無視もできないので挑戦してみたのだが、その際Haskellの遅延評価の罠か何かで、unboxed vectorを使わないと制限時間をパスできない、ということが判明した。(Data.Vectorには非正格なboxed vectorと正格なunboxed vectorしかなく、正格なboxed vectorがないので、正格評価とunbox化のどっちが効いているのかは不明)

値の範囲は64ビット整数に収まる(でかい整数でmodを取る)ように問題設定がされているので Data.Vector.Unboxed.Vector Int64 を使えば良いのだが、どうせなら newtype N = N Int64 として独自に(演算の際にmodを取る)型を用意して Vector N を使うようにしたい。しかしData.Vector.Unboxedはnewtypeと相性が悪く、作った型 N に対する Vector N は簡単には使えない。

Haskellはカジュアルにnewtypeで型を作る文化で、最近はsafe zero-cost coercionsやderiving viaなど、newtypeの効率的な利用を支援したり、より積極的にnewtypeを使うようになっていっているのに、unboxed vectorはnewtypeと相性が悪い、というのはよくない。

というわけで、newtypeと相性の良いunboxed vectorを作った。パッケージ名は unboxing-vector, モジュール名は Data.Vector.Unboxing にした。

https://github.com/minoki/unboxing-vector

実際にはこいつは Data.Vector.Unboxed に処理を丸投げしているラッパーに過ぎないのだが、ラッパーをかますことでnewtypeとの相性が良くなっているというのがポイントである。

1月末時点ではドキュメントとかテストとかベンチマークがまだなのでHackageにはまだ上げていない。

ちなみにきっかけとなった競プロの問題は解くのに3時間かかった。せっかく解いたので解法を記事にしたい気もするが、ググるとすでに解法を説明している記事は見つかるので、どうしたものか(書くかもしれないけど優先度はそんなに高くない)。

cluttex

https://github.com/minoki/cluttex

LaTeX処理自動化ツールcluttexの作業を進めている。

Makefileとの連携用に --make-depends オプションを実装した。

あとはマニュアルを書いて、新しいバージョンとしてCTANに上げたい。マニュアルの英語をチェックしてくれる人がいると良いのだが……。

purescript-tsd-gen

https://github.com/minoki/purescript-tsd-gen

PureScriptのリリースがあったようなので、最新のコードに追従した。しかしまだコンパイルを通しただけで、ちゃんと動くかは確かめていない。

構成的代数

「代数的数を作る」と関連して、A Course in Constructive Algebraをちょっとずつ読んでいる。

「代数的数を作る」には「GCD整域」や「多項式の因数分解ができる係数環」が登場したが、その辺の話をもうちょっと体系的に勉強しておきたい。

この辺のあれこれをHaskellの型や型クラスとして実装した既存のパッケージとしては

などがあるが、ドキュメントが少なかったり、計算可能実数みたいな(イコールが決定可能じゃない)対象に適用できるのか怪しかったりする。

振り返り記事を書いて

こうして書いてみると「Windows機のSSDが死んだ話」は独立した記事として書いてもよかった気がする。小粒なネタを、内容が少なくてもいいから個別の記事として出していくか、こういう振り返り記事でまとめて回収するか、悩みどころだ。


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です