teensy 3.5でbare metal programmingことはじめ
ちとベアメタルプログラミングしたくなって、いい感じのマイコンボードないかと探していたら、teensyというのが、ARM Cortex-M4を使っていて手軽そうだったので購入してみた。
DEV-14055 Teensy USB Development Board - Teensy 3.5
標準ではArduino IDE環境を使う。Arduino環境にteensyの環境を上乗せしている感じ。 （手順はteensyのサイトに書いてある）
これだとC言語とアセンブラで書いたコードのビルド方法がわからない。 ネット上で探しても最新の環境に合う手順書はなかった。
色々試してたが、結果的にそんなに大変でもなかった。
以下が最短距離メモ。 Arduino環境をインストールしなくてもTeensy向けのバイナリをビルド可能。
(1) ARMから最新の組み込みクロス開発環境をダウンロード
https://developer.arm.com/open-source/gnu-toolchain/gnu-rm/downloads
Max OS X 64bitの結局tar.bz2を展開して、/usr/local/に放り込んだだけ。 あとはPATHを通しして終わり。
(2) Teensyのcore ライブラリのソースをゲットする
https://github.com/PaulStoffregen/cores
このPaulStoffregenのリポジトリはどういうものなのか、よく分かっていないが、 Arduino開発環境を使わない環境とMakefileがゲットできる。 （Makefileのオプション指定でArduinoを使用しないようにする。）
(3) 上記の中の、teensy3/ に入ってビルド
Makefileのビルドターゲットがmain.cppになっていて、これはLEDチカをやっているサンプルコード。
$ export COMPILERPATH=/usr/local/arm-none-eabi $ export NO_ARDUINO=1 $ make
main.hexができるので、これをTeensy Loaderで実機にダウンロードして実行。
以上。
Haskellでミニマムな正規表現のmatch関数を実装してみる
「ビューティフルコード」（オーライリー・ジャパン）のしょっぱなの章で、 カーニハン先生がロブ・パイクさんのミニマムな正規表現のmatch関数のソースコードを紹介していた。
たった３０行ほどのC言語コードで、下記正規表現をサポートする。
| 文字 | 意味 |
|---|---|
| c | 文字cそのもの |
| . | 任意の一文字 |
| ^ | 文字列の先頭にマッチ |
| $ | 文字列の末尾にマッチ |
| * | 直前の文字の0回以上の反復 |
95％の用途はこれで足りると書いてあったが、さもありなん。 短くて日常のほとんどのケースで用が足せる簡潔なプログラムは、まさにUNIX精神そのもの。
この本のパイクさんのコードに触発されて、Haskellで同等のものを書いてみた。
ミニマム正規表現match関数Haskell版
match_here :: [Char] -> [Char] -> Bool match_here [] _ = True match_here (x:xs) [] | x == '$' && xs == [] = True | otherwise = False match_here (x:xs) (y:ys) | x == y || x == '.' = if xs /= [] && head xs == '*' then match_repeat x (tail xs) ys else match_here xs ys | otherwise = False match_repeat :: Char -> [Char] -> [Char] -> Bool match_repeat _ [] _ = True match_repeat _ _ [] = False match_repeat c (x:xs) (y:ys) | x == y = match_here xs ys | c == y || c == '.' = match_repeat c (x:xs) ys | otherwise = match_here xs (y:ys) -- match regex string match :: [Char] -> [Char] -> Bool match _ [] = False match (x:xs) (y:ys) | x == '^' = match_here xs (y:ys) | match_here (x:xs) (y:ys) = True | otherwise = match (x:xs) ys
使用例
*Main> match "^a.*1" "abccfb1" True *Main> match "abc" "abccfb1" True *Main> match "c.*1$" "abccfb1" True *Main> match "ccd" "abccfb1" False
ロブ・パイクさんのコードは、再帰とポインタを巧みに使っていて、 ほとんどC言語で関数型プログラミングをしているようなもの。
このプログラム構成のアイディアはそのまま使った感じだが、 コードを見ながら移植だとつまらないので、 一度みた構成を思い出しながら、Haskellで実装するというスタイルをとった。
Haskell初心者なので、実はもっと簡潔に書けるかもしれない。 が、実際書いてみるとHaskell言語はかなり見通しがよいと思った。 パターンマッチング、条件分岐や関数宣言の簡潔な記法、が効いているな。
続：Haskell/Clojureでrepeated_combinationを実装してみる
http://hifistar.hatenablog.com/entry/2018/03/24/131654:repeat_combinationを実装してみるの続き。
この前書いたコードは結構無駄が多くて、実はもっとぜんぜん簡潔にコードが書けた。 ここまで簡潔なコードにブラッシュアップできたのは、Haskellのおかげだなと。
Clojureだけの場合は、ある程度で満足して、先に思考を進めることはあまりしなかった。 Haskellでコードを書くと、違う視点でものごとを考えることができる、というのが大きい。
Haskellは、文字通り「型にはまる」とコードがものすごくシンプルになる、と実感する。 関数のInput/Outputの型（データの抽象度のレベル感）を揃えることが、が非常に大事だと学んだ。
これはプログラミングの基本中の基本かもしれないが、なかなか意識しても難しい。 Haskellの場合は強制的にそれをさせる、という意味でかなり良い。
Clojureの場合は、そろってなくてもプログラムが組める。自由度が高い。
ifなどの条件文で動的に型をチェックして、処理を振り分けてしまえる。
これはもろ刃の剣で、素早くコードを組んだり変更したりするには向いているが、かなり意識しないとプログラムの構造がmessyになる。
双方をやることでいろいろ気づきが出てきて、「結局こういうことじゃね？」という風に理解が深まる。 短いコードで表現できるアルゴリズム系の勉強に、結構いいんじゃなかろうかと思った。
さて、あらためてrepeat_combinationの実行例：
*Main> repeat_combination [1,2,3] 2 [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]] *Main> repeat_combination [1,2,3] 3 [[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]]
幅優先で組み合わせする場合
結局こういうことだ。（「幅優先」という表現が合っているか微妙だが）
Haskell
repeat_combination :: [Int] -> Int -> [[Int]] repeat_combination xs 0 = [[]] repeat_combination xs n = [ x : y | x <- xs, y <- repeat_combination xs (n-1)]
Clojure
(defn repeat-combination [xs n] (if (= n 0) [[]] (for [x xs y (repeat-combination xs (dec n))] (cons x y))))
上記は、組み合わせた結果の帰り値に対して、さらに組み合わせを計算する。
末尾最適化可能なやり方
同じ幅優先だが、こちらは引数に結果を渡すやり方で、これだと末尾最適化できる。
Haskell
combination :: [Int] -> [[Int]] -> Int -> [[Int]] combination xs ys 0 = ys combination xs ys n = combination xs [ x : y | x <- xs, y <- ys ] (n-1) repeat_combination :: [Int] -> Int -> [[Int]] repeat_combination xs n = combination xs [[]] n
Clojure
(defn combination [xs ys n] (if (= n 0) ys (recur xs (for [x xs, y ys] (cons x y)) (dec n)))) (defn repeat-combination [xs n] (combination xs [[]] n))
深さ優先で組み合わせる場合
これも引数に結果を渡して繰り返すやり方。
Haskell
combination xs ys 0 = [ys] combination xs ys n = concat [combination xs (ys++[x]) (n-1) | x <- xs] repeat_combination :: [Int] -> Int -> [[Int]] repeat_combination xs n = combination xs [] n
Clojure
(defn combination [xs ys n] (if (= n 0) [ys] (apply concat (for [x xs] (combination xs (conj ys x) (dec n)))))) (defn repeat-combination [xs n] (combination xs [] n))
concatが美しさを損ねているが、まあしょうがない・・・。
ひとつ選ぶとしたら、分かりやすさと簡潔さ、プラスStack Overflowにならないので、２番目のやり方かなあ。
Clojureで日付の計算をする
引き続き「プログラマ脳を鍛える数学パズル」の問題を解いて遊んでいる。 第7問は日付を扱う。 問題自体は簡単なのだが、Clojureでの日付の扱い方がよく分からなくて、調べるのに時間がかかった。
clj-timeというライブラリがあるようだが、わざわざな・・・。
結局javaライブラリを生でたたくのが一番で、しかしまあオブジェクト指向のAPIは何かするのにいちいち面倒いこと。 もう一度面倒くさいことをしなくて済むようにメモを残しておこう。
動くコードを残しておくのが一番手っ取り早い。
処理
"19991225" から10日分の年月日を出力する
コード
(ns prog-math-puzzle.test-date (import (java.util Calendar) (java.text SimpleDateFormat))) (def date-format (SimpleDateFormat. "yyyyMMdd")) (defn date [dstr] (let [cal (Calendar/getInstance)] (.setTime cal (.parse date-format dstr)) cal)) (defn to-str [cal] (.format date-format (.getTime cal))) (defn next-day [cal] (let [nc (.clone cal)] (.add nc Calendar/DATE 1) nc)) (defn date-seq [cal] (lazy-seq (cons cal (date-seq (next-day cal))))) (println (map to-str (take 10 (date-seq (date "19991225")))))
出力
(19991225 19991226 19991227 19991228 19991229 19991230 19991231 20000101 20000102 20000103)
メモ
必要なライブラリ
java.util.Calendar、java.text SimpleDateFormat
日付のフォーマット
(def date-format (SimpleDateFormat. "yyyyMMdd"))
の部分で、"yyyy-mm-dd"とかでもOK。
日付オブジェクトの生成
java.util.Calendarオブジェクトを作る。
(defn date [dstr] (let [cal (Calendar/getInstance)] (.setTime cal (.parse date-format dstr)) cal))
.setTimeはjavaのメソッド呼び出しなので、返り値にデータを返す訳ではなくて、calを書き換えちゃうんだな。
なので、最後にcalを返している。
また、javaのメソッドで日付データを変える場合は、データをコピーしてから、やらないといけない。 元のデータが書き換わっちゃうから。
next-day関数ではCalendarインスタンスをcloneしてから、日にちを１つ足している。
(defn next-day [cal] (let [nc (.clone cal)] (.add nc Calendar/DATE 1) nc))
以上。
Haskell/Clojureでrepeated_combinationを実装してみる
前回やった Haskell/Clojureで数学パズル：コインの両替 - Programmer's Note の問題5は、書籍の解答例のひとつに、Rubyのrepeated_combination()を使った解があった。
こいつは任意の回数、配列の要素の組み合わせを出してくれる関数で、 探せばClojure/Haskellにもあるだろうけど、ちょうどいい感じの題材なので実装してみる。
任意の大きさのリスト[a,b,c,d,...]を任意の回数n、各要素の組み合わせを出す。
使い方
repeat_combination [1 2 3] 2 ; -> ((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3)) repeat_combination [1 2 3] 3 ; -> ((1 1 1) (1 1 2) (1 1 3) (1 2 1) (1 2 2) (1 2 3) (1 3 1) (1 3 2) (1 3 3) (2 1 1) (2 1 2) (2 1 3) (2 2 1) (2 2 2) (2 2 3) (2 3 1) (2 3 2) (2 3 3) (3 1 1) (3 1 2) (3 1 3) (3 2 1) (3 2 2) (3 2 3) (3 3 1) (3 3 2) (3 3 3))
アルゴリズムは２通りあって、深さ優先か幅優先か。
いろいろやってみたけれど、下記の実装が一番シンプルでわかりやすいな。 幅優先で処理するやり方。
Haskellの実装：
comb :: [[Int]] -> [[Int]] -> [[Int]] comb xs ys = [ x ++ y | x <- xs, y <- ys] comb_n_times :: [[Int]] -> Int -> [[Int]] comb_n_times xs 1 = xs comb_n_times xs n = comb xs (comb_n_times xs (n-1)) repeat_combination :: [Int] -> Int -> [[Int]] repeat_combination xs 1 = [xs] repeat_combination xs n = let ys = [[x] | x <- xs] in comb_n_times ys n
やっていることは以下のような感じ。
入力データを変換してから [a,b,c] => [[a],[b],[c]] １回目 [[a],[b],[c]] x [[a],[b],[c]] => [a,a][a,b][a,c][b,a][b,b][b,c][c,a][c,b][c,c] ２回目は１回目の結果にたいして、 [[a],[b],[c]] x [[a,a][a,b][a,c][b,a][b,b][b,c][c,a][c,b][c,c]] => [a,a,a][a,a,b][a,a,c] .... 以上を繰り返す
コードとしては分かりやすいが、SICPでいうrecusive processになっているので、末尾最適化できない。 nが大きいとStack Overflowを起こす。 とはいえ、この幅優先な方法は、iterative processな実装も可能ではある。
深さ優先
一方、深さ優先で組み合わせを作っていくやりかたもある。 プロセスはこんな感じ。
[a,b,c] x [a,b,c] x [a,b,c]
a -> a -> a => [a,a,a]
-> b => [a,a,b]
-> c => [a,a,c]
-> b -> a => [a,b,a]
-> b => [a,b,b]
-> c => [a,b,c]
...
こっちの方はClojureの実装を載せる。
(defn repeat-combination [xs n] (letfn [(comb-depth [cnt res] (if (zero? cnt) [res] (apply concat (for [x xs] (comb-depth (dec cnt) (conj res x)))))) ] (if (= n 1) [xs] (comb-depth n []))))
こっちの方法はあまりメリットはないかな・・・。 iterative processな実装にすることができない（たぶん）。
Haskell/Clojureで数学パズル：コインの両替
いやあ「プログラマ脳を鍛える数学パズル」楽しいですわ。 まだ5問しかやっていないけど、Clojure/Haskell両方で解いているので、一粒で二度美味しい。 しかも、解説は違う視点の解法を示してくれるので、３度も４度も美味しい感じだ。
5問目は、お金の両替問題で、これシンプルだけど奥が深い。 1000円を10円、50円、100円、500円に両替する。同じコインは何枚使ってもいいが、最大コイン数は15枚。 この時の両替パターン数を求める。
名著SICPにも内容が少し違う両替問題が出ていて、再帰の威力を見せつけられたな。
さて、この問題、まず最初にぱっと思いつく方法は、ベタに組み合わせと条件判定。
Haskellの回答例は、
change_coin :: Int -> Int -> Int change_coin money max_coins = sum [1 | m10 <- [0..max_coins], m50 <- [0..max_coins], m100 <- [0..max_coins], m500 <- [0..max_coins], m10 + m50 + m100 + m500 <= max_coins, money == (10*m10 + 50*m50 + 100*m100 + 500*m500)] main :: IO () main = do print $ change_coin 1000 15
リスト内包表記、便利で簡潔で美しいですわ。
似た簡潔さでClojureも書ける。for文を使う。
(defn change_coin [money max_coins] (reduce + (for [m10 (range 0 (inc max_coins)) m50 (range 0 (inc max_coins)) m100 (range 0 (inc max_coins)) m500 (range 0 (inc max_coins)) :when (and (<= (+ m10 m50 m100 m500) max_coins) (= money (+ (* 10 m10) (* 50 m50) (* 100 m100) (* 500 m500)))) ] 1))) (println (change_coin 1000 15))
少しだけ考えて、再帰を使って汎用的な関数を作ってみる。
Haskell版：
change_coin :: Int -> [Int] -> Int -> Int change_coin 0 _ _ = 1 change_coin _ _ 0 = 0 change_coin _ [] _ = 0 change_coin money (x:xs) max_coins = sum [ change_coin (money - x * use) xs (max_coins - use) | use <- [0..max_coins]] main :: IO () main = do print $ change_coin 1000 [10,50,100,500] 15
考え方としては、使うコインのリスト[10,50,100,500]を与えて、前からコインを取り出して、
(この場合だとまずは10円）
- コインを0枚使う → 1000-0 に対して残ったコインで両替する
- コインを1枚使う → 1000-10 に対して残ったコインで両替する
- ・・・
- コインを15枚使う → 1000-10*15 に対して残ったコインで両替する
というのを再帰でやる。（まあ15枚使ったら、もう終わりだけどね） 最後に残金が０なら、うまく換金できたので１を返し、 それ以外でコインのリストが空になったり、最大コイン数使ったら０を返す。
Clojureも同じように組める。
(defn change_coin_patterns [money coins max-coins] (cond (zero? money) 1 (empty? coins) 0 (zero? max-coins) 0 :else (reduce + (for [uses (range 0 (inc max-coins))] (change_coin_patterns (- money (* uses (first coins))) (rest coins) (- max-coins uses)))))) (println (change_coin_patterns 1000 [10 50 100 500] 15))
Haskellだとパターンマッチングを使った記述がビューティフル。
Haskell／Clojureで数値をN進数表記に変換
去年からHacker Rankが面白くてハマっている。 今年に入ってからHaskellを始めたので、ますます関数型プログラミングでアルゴリズムをやりたい気分が上がっている。
アルゴリズム勉強したいなと思い、 有名なKnuth先生の「The Art of Computer Programming」を買って、 ちょっと読んでみたら、これアセンブラなんですね。興味を削がれたのでそっと積んで置く・・・。
一方、Hacker Rankに飽き足らず、コードパズル系の本も気になっていて、 「プログラマ脳を鍛える数学パズル」も買ってみた。書籍だと解説もあるので楽しみである。
早速、しょっぱなの２問をやってみた。問題自体はいいのだが、 回答がプログラミング言語の機能をばんばん使う前提にしているんだな。 (rubyのevalレベルまで使っていいとは）
制限時間が設定されていて、とにかく速く問題を解くことに目が置かれているので、 そうしているんだな。
別にいいんだけど、 しかしまあ、美味しい部分は、その端折ったところにあったりする。
1問目は、同じ整数を表す10進・8進・2進表記が回文になっている数を求める問題なのだが、 N進数に変換する部分はプログラミング言語のライブラリを使っていい前提だ。
・・・このN進数表記に変換する部分が美味しい部分ですやん。
実際、Clojure, Haskellで書いてて面白く楽しかった部分だ。 やっていること自体は難しくないが、最大公約数を求めるユークリッドの相除法みたく、 数学に近い部分の本質的な面白さがある。
これは、関数型言語で書くと短くて鑑賞のしがいのあるコードが書ける。 （最近はコードを書いて悦悦と眺めるのが目的みたいな感じになっている。 そのために良問を探している感がある。）
さて、ある数をN進表記に変換する関数を、まずはHaskellで書いてみる。
どんな関数かというと、整数10を2進表記に変換する場合に、
Prelude > n_ary_str 10 2 "1010"
という風に使う関数だ。
import Data.Char n_ary :: Int -> Int -> [Int] n_ary 0 _ = [] n_ary num base = n_ary quotient base ++ [remainder] where quotient = num `quot` base remainder = num `mod` base n_ary_str :: Int -> Int -> String n_ary_str num base = map intToDigit (n_ary num base)
やっていることは、 まずN進の数字のリストを求めて、それを文字列にしている。
n_ary 10 2 は [1, 0, 1, 0] というリストが返る。
これを使ってn_ary_str関数で、順に文字に置換しているだけだ。
Haskellの文字列は文字の配列なので、置換したら終わり。
10進以上は対応していないが、対応するのは簡単だ。
たとえばn_ary 199 16は[12, 7]になるが、これを['C', '7']に変換するだけだ。
つまり、10以上の数字を'A'からのアルファベットに置き換えるだけ。
Haskellは習い始めだが、whereというシンタックスはえらく感動する。
これを使うとコードの本質的な部分を先に書けて意図を強調できる。
上記コードは、別に使わなくてもいいのに、わざわざwhereを使っているが、
結局N進数って何？という問いに対して、ソースコードで、
「Nで割った余りを求める。自分の上の桁に対して商を与えそれを繰り返す」です、と表現できる。
（Nに相当する部分がソースではbase）
Haskellは本当にそのまま定義を書ける感じだ。大学の授業とかで使って欲しい言語No.1だな。
Clojureも同じように書ける。（n_ary関数だけ）
(defn n_ary [number base] (if (zero? number) [] (let [quotient (quot number base) remainder (mod number base)] (conj (n_ary quotient base) remainder))))
たぶんLISPerはこんな冗長なコードは書かない(笑。
自分のいつものClojureのコードだと下記のようになる。（文字列変換も込みで）
(defn n_ary [number base] (loop [n number, res []] (if (zero? n) res (recur (quot n base) (cons (mod n base) res))))) (defn n_ary_str [number base] (apply str (n_ary number base)))
Clojureのloopマクロは本当に便利で多用している。 すごく便利なのだが、実は初見だとコードがわかりづらいかもしれないね。
