高階関数を基本的な関数の合成で作った関数でQuickCheckする

高階関数をQuickCheckでテストしてみる

QuickCheckを知っていますか?
QuickCheckと言うのはHaskellのデータ駆動型のテスト用ライブラリで
テストしたい関数を指定するとその引数に合わせて適当なテストデータを生成してくれます。

では高階関数(関数を引数に取る関数)をQuickCheckでテストすると
どんなテストデータ(関数)を生成してくれるのでしょうか。
ちょっと確認してみましょう。

-- QCTest.hs
import Test.QuickCheck
import Test.QuickCheck.Function

prop :: Fun Integer Integer -> Bool
prop f = apply f 10 == apply f 20

main = quickCheck prop
% stack runghc QCTest.hs
*** Failed! Falsifiable (after 2 tests and 12 shrinks):
{20->0, _->1}

...なんだこの関数は?
入力と出力の組が列挙されてるだけやんけ。
僕の思ってる関数と違うんですが。
map (+2)とかtailとかそういうやつを生成してほしいなぁ。

まともなテスト用関数を生成する

QuickCheckのテストデータが気に入らないので、まともな(主観)テストデータを生成してみました。
今回生成するテストデータは[Int] -> [Int]の関数に限定します。

そもそも関数を生成するってどうやればいいんでしょうか?
QuickCheckのように入力と出力の対を列挙するのは筋が悪い気がします。
mapや(+)、tailといった基本的な関数を合成して関数を生成したいのです。
我々がプログラミングするときってそうやりますよね。
入力と出力の組を列挙する人はあんまりいないと思います。

[Int] -> [Int]型の関数を列挙してみます。

tail
reverse
map (* 10)
map (+ 10)

tailやreverseはそもそも[Int] -> [Int] 型です。
mapは(Int -> Int) -> [Int] -> [Int] 型なので
(+ 10) :: Int -> Intを渡すと[Int] -> [Int]型になります。

こんな風にどの関数(例 map)にどの関数(例 (+ 10))を適応すれば
どんな型(例 [Int] -> [Int])になるかを規則として書き出します。
型付け規則っぽく書くとこんな感じです。
Imgur
ちょっとわかりにくいかも知れません。

[Int] -> [Int]型の関数を2つ作ってみました。
Imgur
左はmap (+ 10)のような関数、右はmap (+ 10 (* 5))のような関数を表しています。
一番下の型にある関数の規則を持ってきて、上に必要な型を書いて   さらにその必要な型をもつ関数の規則を持ってきて...という感じです。

とりあえずこの規則を使って関数を生成できるようになりました。
[Int] -> [Int]型の関数を生成した例がこちらです。

% stack exec qcfun-exe
> Test datum are following.
> ["tail","reverse","(map (* 75))","tail","reverse"]
...

今見せた例はこのようなデータ型で表現されています。

data QProg = QMap1 QProg | QMap2 QProg QProg 
             | QTail1 QProg | QTail | QRev | QMult QProg | QAdd QProg | QRand Int deriving (Eq)

instance Show QProg where
  show (QMap1 p) = "(map " ++ show p ++ ")"
  show (QMap2 p1 p2) = "(map " ++ show p1 ++ " " ++ show p2 ++ ")"
  show (QTail1 p) = "(tail " ++ show p ++ ")"
  show (QTail) = "tail"
  show QRev = "reverse"
  show (QMult p) = "(* " ++ show p ++ ")"
  show (QAdd p) = "(* " ++ show p ++ ")"
  show (QRand i) = show i

QProg型がプログラム(関数)を表す型です。
このQProg型に対して適当なShowインスタンスを定義してあげると関数っぽく見えるようになります。

作ったテストデータ用の関数で高階関数をテストする

次に作った関数を使って高階関数をテストしてみましょう。
今回テストする対象のプログラムはこれです。

func f = reverse . f
prop f = (func f [1,2,3]) == [1,2,3]

関数fを引数に取る簡単な高階関数funcの性質をテストします。

しかし作ったテストデータ用の関数はすべてQProg型です。
つまりQProg型をなんとかして[Int] -> [Int]型に変換したうえで
テストしたい高階関数に適用する必要があります。

今回はTemplate Haskellを使ってQProg型を[Int]->[Int]型のHaskellの関数に変換しました。
Template Haskellというのはプログラムの中でプログラムを作るためのツールです。
Lensなんかで使われています。 動作例がこちらです。

% stack exec qcfun-exe
...
Test results are following.
[(False,"tail"),(True,"reverse"),(False,"(map (* 75))"),(False,"tail"),(True,"reverse")]

テストデータは先頭から順に["tail","reverse","(map (* 75))","tail","reverse"]だったので正常に動いているようです。

まとめ

高階関数をまともな(主観)関数でテストできるようにしました。
しかし技術的な制約のためテストデータをコンパイル時に生成するので
テストデータを完全にランダムに生成することはできませんでした。

参考

http://haskell.g.hatena.ne.jp/mr_konn/20111218/1324220725

付録

githubへのリンクです
https://github.com/akawashiro/qcfun
以下のコマンドで実行できます。

git clone https://github.com/akawashiro/qcfun.git
stack build
stack exec qcfun-exe

ソースコードはTemplate Haskell的な事情で2つにわかれています。

Vimで初めてコマンドを定義してみた

書かないと忘れちゃうから…


これだけ

:command! MT :MerlinTypeOf
:MT

Vimをコンパイルしてインストールする

使っているプラグインの関係で+python,+lua,+perlVimが必要になりました。
しかし、Ubuntuのパッケージで条件を満たすものが見当たりません。
そこで自分で一からコンパイルしてインストールしました。

僕は自分でコンパイルしたソフトウェアを$HOME/.local/以下にインストールしているので、
--prefix=$HOME/.localとしています。
必要に応じて適当に変更してください。

git clone https://github.com/vim/vim
cd vim
./configure --prefix=$HOME/.local/ --with-features=huge --enable-multibyte --enable-gpm --enable-cscope --enable-fail-if-missing --enable-perlinterp --enable-python3interp --enable-rubyinterp
make install

あとは$HOME/.local/bin/vimにパスを通すだけです。

nvimに移行したほうがいいのかなぁ。

githubのバックアップを取る

年末も近くなってきたのでgithubが落ちた時に備えてリポジトリのバックアップを取ることにしました。
以下のスクリプトを実行するとgithub以下にすべてのリポジトリがバックアップされます。

YOUR_ACCESS_TOKENはSign in to GitHub · GitHubで作れます。
Select scopesのところでreposの欄をすべてチェックしてトークンを作成してください。

#! /bin/bash

token=YOUR_ACCESS_TOKEN
curl "https://api.github.com/user/repos?access_token=${token}&per_page=100&affiliation=owner" 2>/dev/null -o tmp
repos=`cat tmp | grep ssh_url | cut -d" " -f 6 | sed -e 's/"//g' | sed -e 's/,//g'`
mkdir github
cd github
for r in ${repos}; do
    name=`echo ${r} | sed -e "s:git.*/::" -e "s:[.]git::"`
    git clone ${r}
    cd ${name}
    for branch in `git branch -a | grep remotes | grep -v HEAD | grep -v master `; do
        git branch --track ${branch#remotes/origin/} $branch
    done
    cd ..
done
rm tmp

これでgithubが落ちても安心ですね。

Freeモナドについて今更勉強してみた

5年ほど前、Freeモナドという言葉がHaskell界隈でよく見られました。
僕のフォローしている人たちが次々に解説記事をアップしていたように思います。
5年たった今になって、Freeモナドについて興味が湧いてきたので記事を書いてみることにしました。

Freeモナドの定義に行く前にFree型について説明します。

-- The kind of f is * -> * like Maybe, [].
-- The kind of a is * like Int, Char, [Char].
data Free f a = Pure a | Free (f (Free f a)) 

ここでfはカインド * -> * を持つ型コンストラクタであり、あとで述べるようにFunctorのインスタンスです。
aはカインド * のただの型です。
fが[]、aがIntの場合について調べてみましょう。

free1 :: Free [] Int
free1 = Pure 10

free2 :: Free [] Int
free2 = Free [Free [Free [Free []]]]

free3 :: Free [] Int
free3 = Free [Pure 10]

これら3つの定数関数はすべてFree [] aの型を持ちます。
直感的に言うとリストもリストのリストのリストもただの整数もすべて同じ型になっています。
これだけではFree型をどう使っていいのかわかりません。

これをモナドにしてみましょう。

-- functor is typeclass which "fmap" is defined
-- (<$>) :: Functor f => (a->b) -> f a -> f b
-- (<$>) = fmap
instance Functor f => Functor (Free f) where
  fmap f (Pure a) = Pure (f a)
  fmap f (Free fa) = Free (fmap (fmap f) fa)

instance Functor f => Monad (Free f) where
    return = Pure
    Pure a >>= k = k a
    Free fm >>= k = Free (fmap (>>= k) fm)

モナドになると何が良いのでしょうか?
簡単なゲームを作る例を見ながら、Freeモナドの利点を確認しましょう。

このゲームは

  1. 入力を受け取る
  2. 文字列を出力する
  3. 一秒待つ

の3つの要素の組み合わせで構成されています。
ゲームを表すデータ型がこれです。

data Game cont = GetInput (String -> cont) | Render String cont | Wait cont

instance Functor Game where
  fmap f (GetInput g) = GetInput (f . g)
  fmap f (Render str cont) = Render str (f cont)
  fmap f (Wait cont)     = Wait (f cont)

各コンストラクタは動作を行ったあとの続きの計算を持ちます。
例えば、GetInput fだったら入力を受け取ってfに渡すことで
続きの計算contを計算し、contを実行します。

ここでGameデータ型をFreeモナドと組み合わせて使う利点を説明します。

game1 :: Free Game ()
game1 = Free (Wait (Free (Render "Hello" (Pure ()))))

game1' :: Free Game ()
game1' = (Free (Wait (Pure ()))) >>  (Free (Render "Hello" (Pure ())))

一秒待って"Hello"と出力するゲームを2つの方法で記述してみました。
game1は愚直な記述、game1'は>>演算子を用いた記述です。

実はこの2つは全く同じものです。
game1'を定義にしたがって展開してみます。

(Free (Wait (Pure ()))) >>  (Free (Render "Hello" (Pure ())))
==> (Free (Wait (Pure ()))) >>= (\x -> (Free (Render "Hello" (Pure ()))))
==> Free (fmap (>>= (\x -> (Free (Render "Hello" (Pure ()))))) (Wait (Pure ())))
==> Free (Wait ((>>= (\x -> (Free (Render "Hello" (Pure ()))))) (Pure ())))
==> Free (Wait ((Pure ()) >>= (\x -> (Free (Render "Hello" (Pure ()))))))
==> Free (Wait (Free (Render "Hello" (Pure ()))))

同じになりましたね。
モナドの枠組みを使えばGameデータ型同士を簡単に合成できることがわかります。

input :: (String -> Free Game ()) -> Free Game ()
input f = Free (GetInput f)

render :: String -> Free Game ()
render str = Free (Render str (Pure ()))

wait :: Free Game ()
wait = Free (Wait (Pure ()))

miniGame = do
  render "Please input your name."
  input (\x -> render $ "Your name is " ++ x)
  wait
  render "End"

miniGame関数ではdo記法で3種類のGameコンストラクタを合成しています。
あとはFree Game ()をIO ()に変換する、つまり実際の入出力を行う部分を書けば完成です。

runGame :: Free Game () -> IO ()
runGame (Pure ()) = return ()
runGame (Free (Wait cont)) = runGame cont
runGame (Free (GetInput f)) = getLine >>= \s -> runGame (f s)
runGame (Free (Render str cont)) = putStrLn str >> runGame cont

main :: IO ()
main = runGame miniGame

コンパイルしてmain関数を実行すると名前を聞いてくれます。(ソースコードはこの記事の末尾にあります。)

結局Freeモナドを使うとどんな利点があるのでしょうか。
この記事の例ではゲームの構造と入出力が分離できています。
つまり、テストがしやすいということが言えます。
またゲームの構造だけ作っておいてあとで入出力の部分を差し替えたりするのも簡単です。
Freeモナドを使った2Dゲーム用のライブラリというのもあります。

参考

Freeモナドって何なのさっ!? - capriccioso String Creating(Object something){ return My.Expression(something); }

そろそろFreeモナドに関して一言いっとくか - モナドとわたしとコモナド

以下ソースコード

続きを読む

型レベル自然数を使って型付き行列を作ってみた

#動機 研究で行列計算ライブラリを使っているのですが、numpyはなぜか異なる型の行列同士を足せてしまいます。 このせいでデバッグがめちゃくちゃ大変でした。

こんな単純な間違いはコンパイル時に弾いてくれればいいのにと思ったので、違った型の行列は足せないようなちょっとしたライブラリを作ってみました。

※行列を安全に計算したい人のためには

Numeric.LinearAlgebra.Static

↑のライブラリが既に存在しました。不勉強ですみません。この記事は「型レベル自然数ってこんなに簡単に(僕でも)使えるんだ」、程度に読んでください。

型レベル変数

最近のGHCでは、自然数をパラメーターとするデータ型を定義できる。固定長リストの長さを型に持たせるとか、行列の大きさを型に持たせるとか、そういうことができる

引用元:Haskell (GHC) の型レベル自然数とリフレクションを試してみる

行列の大きさの情報を型に持たせることができる。 →やってみました

仕様

  • 行列の足し算・掛け算をサポートする・
  • 足し算/掛け算できないものを計算しようとしたらコンパイル時にエラーにする

実装

{-# LANGUAGE DataKinds, KindSignatures #-}
{-# LANGUAGE TemplateHaskell #-}

module SizeFixedMatrix where
import GHC.TypeLits
import Data.List.Split
import Data.List

data SizeFixedMatrix (h :: Nat) (w :: Nat) = MakeMartix [[Integer]] deriving (Eq,Show)

mat1 = MakeMartix [[1,2],[2,3]] :: (SizeFixedMatrix 2 2)
mat2 = MakeMartix [[2,9],[1,3],[4,3]] :: (SizeFixedMatrix 3 2)
mat3 = MakeMartix [[5,9],[3,3],[0,3]] :: (SizeFixedMatrix 3 2)


add :: SizeFixedMatrix p q -> SizeFixedMatrix p q -> SizeFixedMatrix p q
add (MakeMartix m1) (MakeMartix m2) = MakeMartix (map (\(a,b) -> map (\(c,d) -> c+d) (zip a b)) (zip m1 m2))

mul :: SizeFixedMatrix p q -> SizeFixedMatrix q r -> SizeFixedMatrix p r
mul (MakeMartix m1) (MakeMartix m2) = MakeMartix $ splitEvery (length (head m2)) [sum $ zipWith (*) v w | v <- m1, w <- transpose m2]

…これだけです。拍子抜けするくらい簡単に作れました。もう少し凝ったものを作りたかったのですが、締切に間に合いそうにありませんでした。

一応ちょこっとだけ解説しておくと

SizeFixedMatrix p q

が縦p行横q列の行列の型になります。

不適切な型同士でaddしたりmulしたりするとコンパイルエラーになるので安心してプログラミングできます。

結果

$stack ghci
(省略)
*Main FiniteField Lib SizeFixedMatrix> mat1
MakeMartix [[1,2],[2,3]]
*Main FiniteField Lib SizeFixedMatrix> mat2
MakeMartix [[2,9],[1,3],[4,3]]
*Main FiniteField Lib SizeFixedMatrix> mat3
MakeMartix [[5,9],[3,3],[0,3]]

足し算

*Main FiniteField Lib SizeFixedMatrix> add mat1 mat2

<interactive>:4:10: error:
    • Couldn't match type ‘3’ with ‘2’
      Expected type: SizeFixedMatrix 2 2
        Actual type: SizeFixedMatrix 3 2
    • In the second argument of ‘add’, namely ‘mat2’
      In the expression: add mat1 mat2
      In an equation for ‘it’: it = add mat1 mat2

mat1は2行2列の行列型、mat2は3行2列の行列型なので足せないと言われてしまいます

*Main FiniteField Lib SizeFixedMatrix> add mat2 mat3
MakeMartix [[7,18],[4,6],[4,6]]

掛け算

*Main FiniteField Lib SizeFixedMatrix> mul mat1 mat2

<interactive>:8:10: error:
    • Couldn't match type ‘3’ with ‘2’
      Expected type: SizeFixedMatrix 2 2
        Actual type: SizeFixedMatrix 3 2
    • In the second argument of ‘mul’, namely ‘mat2’
      In the expression: mul mat1 mat2
      In an equation for ‘it’: it = mul mat1 mat2
*Main FiniteField Lib SizeFixedMatrix> 

mat1*mat2(行列積)は存在しません

*Main FiniteField Lib SizeFixedMatrix> mul mat2 mat1
MakeMartix [[20,31],[7,11],[10,17]]

感想

型レベル変数などという難しい名前の機能をはじめて使いました。案外簡単に使えたので、他にも応用できると思います。

参考文献

CTF入門記

11月の終わりからCTFをかじり始めました。この熱意がいつまでつづくのか分からないのですがとりあえずこの二週間くらいでやったことを書いてみようと思います。

動機

CTFは高校の先輩に一年ほど前から勧められていたのですが放置していました。最近寒いし何か家の中でできることないかなと考えてCTFを思い出したので初めてみました。

絶望

別にPCを初めて触るわけでもないし、ksnctfのポイントの低い問題ならなんとかなるやろ…


舐めてました。難しすぎる。というわけで梅田の丸善ジュンク堂
セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方-
をお買い上げてしまいました。その後も

などと(初心者なので)当然すぎる知識不足を露呈し続けました。

感動


初めて自力で解いたのはksnctf - 8 Basic is secure?だったと思います。嬉しかったですね。(小並感)