mcommit's message

ソフトウェア開発の仕事をしているsimotinといいます。記事の内容でご質問やご意見がありましたらお気軽にコメントしてください\^o^/

数学素人が線形代数を学ぶときに読んでみてよかった書籍

今年から帝京大学の通信教育課程に入学して勉強しているのですが、線形代数の講義*1を受けるにあたって関連する本を何冊か読んでみました。

せっかくなので、勉強していて躓いたときに助けになった本の紹介記事を書いておきたいと思います。*2

動機

そもそも、本をいくつか読んだ理由ですが、講義で指定教科書をベースに演習問題をこなすことが求められるのですが、個人的に躓いたところの解説が指定教科書には書かれていなかったり説明が少なかったりしたので、躓いたところの答えや考え方を示してくれている書籍を買い漁りました。

躓いたところ

行列式の計算

実際に線形代数を学んでみて分かったのですが、理解すべきポイントは行列式の計算をマスターすることなのかなと感じました。

行列式の計算は3次の正方行列であればサラスの公式が使えます。
サラスの公式という公式はありますが、2次の正方行列と同様に、たすき掛けに掛け算して和と差をとるだけです。

ここまではすんなり理解できたのですが、4次の正方行列の行列式を求めるとなると、劇的に難易度が高くなります。

4次の正方行列では、余因子行列毎の行列式を求めて足したり引いたりするのですが、この足したり引いたりの符号の向きが、どのように決まるのか教科書を読んだだけでは理解できませんでした。

色々書籍を買って、この部分が理解できたのは、「マンガでわかる線形代数の関連箇所をじっくり読んでみたときでした。

マンガでわかる線形代数

マンガでわかる線形代数

この書籍はm文字通りマンガをベースとして難しい数学や物理などの解説をしてくれるシリーズの線形代数版です。
この書籍では、第4章 行列(続き) で4次の行列式の計算について触れられています。

他にもいくつか線形代数の本を買い漁って関連する章を読んでみたのですが、行列式の計算については、この書籍が一番しっくりきました。

固有値

固有値固有ベクトルに関するについても、よくわからずに躓いたのですが、固有値については、

線形代数がわかる」という書籍での説明が分かりやすかったように思います。

線形代数がわかる (ファーストブック)

線形代数がわかる (ファーストブック)

これから読んでみる本

そもそも線形代数を本格的に勉強する前に「プログラミングのための線形代数

プログラミングのための線形代数

プログラミングのための線形代数

という本を買っていたのですが、一切読まずに積み本化していました。

一通り、線形代数に関する基本的な内容は勉強できた(はず!?)なのでこれからこの本も読んでみたいと思います。
注意点として、この本は、目次をざっと見た限りでは「プログラミングで線形代数を活用してみる」というコンセプトではなくて「線形代数を勉強するのにプログラミング(コンピュータで計算)を活用する」という構成になっているようです。

ベクトルの可視化とかあるので、とりあえず一通り学んだ今の自分にはちょうど良いかもしれません。

その他

演習問題の計算をするときによくこちらのサイトのお世話になっておりました。

keisan.casio.jp

このサイト、行列計算に限らず単位換算とかでよくお世話になっていたのですが、電卓のカシオが運営されているんですね。*3

*1:講義といっても通信教育なのでほぼ独学なのですが・・・

*2:帝京大学の通信教育課程については折を見てまた別の記事を書きたいと思います

*3:カシオ様いつも利用させて頂きありがとうございます!感謝

ARMの命令セットの条件指定について (2)

昨日の続き。

mcommit.hatenadiary.com

ARMの命令では最上位4ビットで条件指定ができることがわかりましたがAL(無条件実行)以外の使い方がよく分かりませんでした。

命令の実行条件を指定するというのはイメージ的には

r0 = 1 if flag == true
r0 += 2 

のようにRubyの後置ifのようなおしゃれなイメージがあります。
何が嬉しいかというとこの書き方だとelseを書かなくてよいのでソースコードレベルでのステップ数は削減できます。
分岐の結果に関わらず後続の処理を必ず行う場合はこの条件指定を使ったほうがよさそうに見えます。

さて、ARMの命令として具体的にどのように条件指定をするかを調べてみたところ、アセンブラだと命令の後ろに条件のサフィックスを指定するようです。

例えば、

MOV r0, #1

であれば

CMP       r0, #1
MOVEQ r0, #1

とすると、事前の比較命令の結果に応じてMOVを実行するか判断してくれるようです。
MOVEQ以外にもADDEQとかあります。

もちろん条件指定もEQ以外にあります。

条件指定実行のメリット

  1. 分岐命令を使うより命令数が少なくできる場合がある→サイズの節約
  2. 条件指定実行だと、条件が成立していない場合は後続の命令が実行されるので、ジャンプ先アドレスを別途取得する必要がない。

といったところでしょうか。

条件指定実行のデメリット

よく分かりません・・・なんとなく使える状況では使って行ったほうがよい気がしますが。

実際

実験のために、raspberrypiでMOVEQを使ってくれそうなコードを書いてビルドしてみました。

int add(int oneOriginFlg, int a, int b)
{
   int ret = 0;
   if (oneOriginFlg == 1)
   {
      ret = 1;
   }
   ret += a;
   ret += b;
   return ret;
}

コンパイルの結果、残念ながら普通にコンパイルしただけでは、MOVEQを使うコードははいてくれませんでした。

gcc -Osとか O1とかつけるとMOVEQをつかってくれていたのでgccだと必要に迫られないとこういった条件指定実行のコードははいてくれないようです。
gccは多くのアーキテクチャをサポートしているので当然といえば当然かも知れません。

参考書籍

今回も調査にはARMで学ぶアセンブリ言語入門を参考にしました。

ARMで学ぶ アセンブリ言語入門

ARMで学ぶ アセンブリ言語入門

条件実行についてもP62-P63で説明されています。ARMのアセンブラを学習するのには重宝しています。

ARMの命令セットの条件指定について

ARMの命令セット(v7)について調べていたので備忘録のためメモを残しておきます。

■ARMv7のマニュアル

https://www.macs.hw.ac.uk/~hwloidl/Courses/F28HS/Docu/DDI0406C_C_arm_architecture_reference_manual.pdf

とりあえず命令セットのところを読んでみる。
参考用に簡単な加算と条件分岐を含むコードを書いてみる。

■サンプルコード hoge.c

int add(void)
{
    int a = 0;
    a += 0x10;
    if ( a == 0x10) {
      return a;
    }
    return 0;
}


$ arm-linux-gnueabi-gcc -g -c hoge.c
$ arm-linux-gnueabi-objdump -S hoge.o


■サンプルアセンブラコード

00000000 <add>:
int add(void)
{
   0:   e52db004        push    {fp}            ; (str fp, [sp, #-4]!)
   4:   e28db000        add     fp, sp, #0
   8:   e24dd00c        sub     sp, sp, #12
    int a = 0;
   c:   e3a03000        mov     r3, #0
  10:   e50b3008        str     r3, [fp, #-8]
    a += 0x10;
  14:   e51b3008        ldr     r3, [fp, #-8]
  18:   e2833010        add     r3, r3, #16
  1c:   e50b3008        str     r3, [fp, #-8]
    if ( a == 0x10) {
  20:   e51b3008        ldr     r3, [fp, #-8]
  24:   e3530010        cmp     r3, #16
  28:   1a000001        bne     34 <add+0x34>
      return a;
  2c:   e51b3008        ldr     r3, [fp, #-8]
  30:   ea000000        b       38 <add+0x38>
    }
    return 0;
  34:   e3a03000        mov     r3, #0
}
  38:   e1a00003        mov     r0, r3
  3c:   e24bd000        sub     sp, fp, #0
  40:   e49db004        pop     {fp}            ; (ldr fp, [sp], #4)
  44:   e12fff1e        bx      lr

条件指定について

ARMの命令のうち、最上位の4bitは条件指定のビット(cond)として割り当てられているそうです。

f:id:simotin13:20180606010019p:plain

アセンブラを見るとこのcondビットはほぼほぼ1111(0xE..)になっていることが多い。
ここまでは過去の経験として知っていたのですが、このcondビットの意味がいまいちよく分かっていませんでした。※そういえばpine64のダンプとか読んだときも少し調べていました。

mcommit.hatenadiary.com

結論ですが、ARMでは(ほとんどの)命令に対して実行するかしないかの条件をつけることができるそうです。これだけだとピンとこないのですが、条件と言うのは要するにフラグレジスタの各種フラグビット(ゼロフラグとかキャリーフラグ...etc)に応じて実行するかしないかを命令に対して指定できるという意味になります。

実際に、上記のhoge.oの逆アセンブルですとbneだとcondは1になっています。
条件指定実行ができるということは
addとかmov命令をフラグレジスタの値を元に実行するかしないか切り替えれるというような意味だと思います。*1

というわけで実際にどの命令で条件指定が可能なのか、適当に試してみたいと思います。

が、今日眠いので続きは明日にします。

[2018/06/06 追記]

条件実行について更に調べてみた続きです。

mcommit.hatenadiary.com

*1:なんかrubyの後置記法みたいでおしゃれ

スタックの状態を可視化するWebツールを書いてみた。

Webページ上でStackの状態を可視化するコードを書いてみました。

Simple Stack Viewer

Stackを可視化するツール自体に目新しい感じはしないのですが、Web上でこういうツールってありそうでなかったので作ってみました。
かなりざっくりしたものですが、よかったら使ってください。

個人的なニーズとして普段Cとかアセンブラをガチでデバッグするとき、紙のノートにスタックの状態を書きながらデバッグしたりしているのですが、ノートだと動的にイメージし続けるのが辛いのであると便利な気がします。*1

課題

現状だと、pushするたびにページが下に伸びていくのでなんかしっくりこない気もするので、時間があるときに改善したいと思います。*2

その他

ついでにずっとほったらかしにしていたホームページも書き換えてみました。シンプルにindex.htmlだけにしてみました。

mcommit toppage

*1:GDBを使うとスタックとかレジスタの状態を見ることはできますが、いかんせんCUIなのが地味で直感的じゃない気がしていました

*2:もちろんpushはスタックトップに積まれて、popはスタックトップから取り出されていくのでご安心ください

構文解析ハンズオン 関西出張版に参加させて頂きました

lang-impl.connpass.com

参加させて頂きました。

良かった点

久しぶりにパーサ系のコード書きました。普段パーサ系のコードを書くことはあまりありませんが、時々必要に迫られるときがあるので定石やいろいろなテクニックや流行とか知っておくというのは大切な気がします。ハンズオンでいろいろ実際に書いてみるというのは自分にはぴったりでした。

あと、普段は再帰を使ってコードを書く機会が少ないので再帰を使うちょうどよい練習になりました。

苦労した点

Javaのコード書くのが久しぶりすぎてやばかった・・・
事前にJavaでハンズオンをするので環境を用意しておいてくださいと告知があったのですが、環境は構築していましたが、心と体の準備が追い付いていませんでした。
Javaはもう何年も書いていないけどまぁなんとかなるだろう」と思っていたら、コード書くのと実行するのに戸惑いました。やはり事前に復習をしておけばよかったように思います。

構文解析について思ったこと

パーサを書く場合に気を付けないといけないポイントとして、パースをする際の入出力と内部状態をしっかりと把握しておく必要があると思います。
入出力と状態は、

入力

  • 文字列

出力

  • 解析結果(AST)
  • 解析の成否(正常に解析できたのか、解析できなかったのか)

パーサ内部で保持する状態

  • 現在の解析位置
  • 入力文字列長

のような構成になります。

再帰下降的にパースする場合、各非終端記号に対応する関数は呼び出し元に

  • 解析結果(AST)
  • 解析の成否(正常に解析できたのか、解析できなかったのか)

を返す必要があります。

パーサを作る時に話がややこしくなるのは出力が複数存在するというのが1つの要因なのかなと思いました。
例えば戻り値をASTとした場合、解析の成否の情報は戻り値以外の方法で返す必要があります。

例外がサポートされている言語だと例外が1つの選択肢としてありますが、その場合例外クラスの設計をきちんと考えておく必要があります。
NULLやそれに類するものがある言語であれば戻り値のASTがNULLであれば解析異常とするのもありかなと思います。*1

Rubyで式の構文解析をしてみた

復習がてらハンズオンの課題の数式の解析コードを書いてみました。

gist.github.com

書いてみて気づいたこと

上記コードを書いていて気づいたのですが、入力が不正な場合の異常系に対応できていません。
非終端記号に対応する各関数は、解析異常時はnilを返すというポリシーで実装してみたのですが、再帰下降型で書くと想定していない文字が出てきたときに関数レベルではエラーハンドリングができないです。やはり字句解析フェーズがないというのはつらい気がする。
この辺は好みだと思いますが、個人的には先に入力を全てレキサーにかけるのが好きです。*2

再帰か状態遷移か

再帰を使わず状態遷移で書けば、適切に入力を弾けるので、仕様が小さくて手書きでパーサを書くのであれば状態遷移の方がいいようにも思いました。*3

再帰を使うメリットは何か考えてみたのですが、コードが短くなるというのはあるかも知れません。あと仕様が大きくなると状態遷移を考えるのがかえって面倒になる気がする。デバッグは状態遷移の方が断然しやすい気がしました。*4

今後やってみたいこと

パーサジェネレータを書く

パーサ系の実装についてはパーサジェネレータを書いてみたいです。*5
あまり難しくないはずですがBNFパーサを書かないといけないというところでいつも面倒くさくなって挫折してしまいます・・・あと、懇親会でPEGというものを教えてもらったので勉強してみると何か開けてきそうな気がしました。

関数型言語でパーサを書く

勉強会や懇親会でもイミュータブルとかパーサコンビネータの話題が挙がっていましたが、オブジェクト指向言語に囚われずに関数型の頭で何かパーサを書いてみたいです。

その他

ハンズオンの課題でJSONのパーサを書こうというのがありましたが、twitterで最近JSONのパーサに関して面白そうな論文が紹介されていました。

https://www.microsoft.com/en-us/research/publication/mison-fast-json-parser-data-analytics/

ざっと読んでみたところ

  1. JSONニーズ高まってて大きなデータ扱うことが増えてきたけど、パース遅いので何とかせねば。
  2. どうやってやるか→投機的解析と並列化で高速化してみた。
  3. やってみた結果→いい感じ。CSVとかHTMLとかXMLにも適用したい。

といった感じでしょうか。rustのプロジェクトが実装になるのかな。

github.com

解析する際にDBのようにインデックスをつけたり、SIMDとビット演算を使った並列化したりするらしい。
大量のデータとか扱う機会があれば、SIMDGPUFPGAあたりをデータの解析を目的として勉強してみたいです。

感想

勉強会も懇親会も色々と勉強になることが多かったです。

参加して思ったのは、構文解析を短い時間で「理解する、誰かに教える」というのは結構難しいのではないかと思いました。勉強会への参加だけでなく予習とか復習が欠かせない気がします。
あと、勉強会だと主催者の方や周りの詳しい方に質問できるので、やはりこういった場があるのはいいなぁと感じます。

kmizu様、チューターの皆様、いろいろ教えてくださった参加者の皆様、会場を使わせて頂いたはてな様、ありがとうございました。

*1:もしかしたら複数のオブジェクトを返せる言語(goとか!?)というのはパーサを書くのに向いているのかもしれない。Rubyでも複数返せるけど、そういう場合はなぜかHashを使いたくなる

*2:パーサに渡った時点で不正な文字が登場しないことが保証されるので

*3:組込だとスタックサイズの見積りの事情により再帰が使えない場合がある

*4:再帰のパースをデバッグする場合はログをしっかりと入れておかないとデバッグが難しいです

*5:せっかく勉強会に参加して気持ちが高ぶったので

Goでバイナリファイルを読み込んでHexダンプしてみた

最近触り始めたGo言語で、勉強としてバイナリファイルを読み込んでHexダンプしてみました。
バイナリファイルといってもfile.Readを使った読み込みなのでバイナリかどうかはあまり関係ないかもしれない。

package main

import (
  "fmt"
  "os"
)

func main() {
  argc := len(os.Args)
  if argc < 2 {
    fmt.Println("input file name.")
    return
  }

  filename := os.Args[1]
  f, err := os.Open(filename)
  if err != nil {
    fmt.Println("err:", err)
    return
  }

  c := make([]byte, 1)
  var buf []byte
  size := 0
  for {
    len, r_err := f.Read(c)
    if len == 0 {
      break
    }
    size += len
    if r_err != nil {
      fmt.Println("err:", err)
      return
    }
    buf = append(buf, c[0])
  }

  fmt.Printf("size:[%d]\n", size)
  for i := 0; i < size; i++ {
      fmt.Printf("%02X ", buf[i])
      if i % 16 == 15 {
        fmt.Println("")
      }
  }
}

感想

Go言語的な書き方がよくわからない

なんとなくC言語っぽく書いてみたけど、Go言語的に正しい書き方がよくわからない。
特にファイルから全データをリードする場合C言語だと大抵、EOFまで1byteずつreadするけどgoでもそんなのりでいいのかな・・・

配列とslice

RubyのArray的なのが使いたいけどgoだと配列とsliceを組み合わせて使うみたい。
sliceって機能と名前があってない気がする。

そもそも、goって名前自体英語だと普通の動詞になるので検索性がよくない。
例えば、for文について調べようとしたら

f:id:simotin13:20180326011052j:plain

みたいな結果になった。やはり名前重要。

参考

Go言語を勉強するにあたって「基礎からわかるGo言語」を手元に置いて読んでいます。

改訂2版 基礎からわかる Go言語

改訂2版 基礎からわかる Go言語

この書籍では前半で言語の基本的な機能について解説されていて、後半で逆引きサンプルが載っているのでかなり役に立っています。
今のところやりたいことに合わせて前半と後半をいったり来たりしながら読んでいます。

goらしい書き方についてはこの書籍だけでは掴めないので、go好きな人が書いたコードとかもっと読んだり写経した方がよさそう。

レジスタの値を取得するi386のアセンブラ関数を書いてみた

前回書いたPINE64+の続きとして、とりあえずBROMの処理が終わった状態でCPUがどうなっているか知りたいのですが、難航しています。

mcommit.hatenadiary.com

BROMのコードのダンプを見た結果、コプロセッサの設定とかをしていることは分かりましたがどうも追いきれないところもあるのでとりあえずCPUのレジスタの値をUARTでダンプ出力とかしてみたいと思いました。

レジスタを直接触るためにはアセンブラでコードを書く必要があり、少しハードルはあがります。
といってもARMのABIを理解して、出力したいレジスタからMOV命令で汎用レジスタにコピーするだけなのでそこまでは難しくはないはずです。

が、とりあえず練習もかねてi386で試してみました。

ABI的にポインタで渡す変数がスタックトップの次にあることを前提としています。関数側ではEBPの設定とかしないようにしたので、スタックトップはリターンアドレスになります。抜けるときもret命令だけで問題ありません。

reg.asm

section .text
global get_eax
global get_ecx
global get_edx
global get_ebx
global get_ebp
global get_esi
global get_edi
global get_esp
global get_eip

get_eax:
    mov ebx, [esp+0x04]
    mov [ebx], eax
    ret

get_ecx:
    mov eax, [esp+0x04]
    mov [eax], ecx
    ret

get_edx:
    mov eax, [esp+0x04]
    mov [eax], edx
    ret

get_ebx:
    mov eax, [esp+0x04]
    mov [eax], ebx
    ret

get_ebp:
    mov eax, [esp+0x04]
    mov [eax], ebp
    ret

get_esi:
    mov eax, [esp+0x04]
    mov [eax], esi
    ret

get_edi:
    mov eax, [esp+0x04]
    mov [eax], edi
    ret

get_esp:
    mov eax, [esp+0x04]
    mov [eax], esp
    sub [eax], dword 0x08
    ret

get_eip:
    mov eax, [esp]
    mov ebx, [esp+0x04]
    mov [ebx], eax	; return address on stack frame.
    ret

呼び出す側は、

main.c

#include <stdio.h>
#include <stdint.h>

extern void get_eax(uint32_t *reg);
extern void get_ecx(uint32_t *reg);
extern void get_edx(uint32_t *reg);
extern void get_ebx(uint32_t *reg);
extern void get_ebp(uint32_t *reg);
extern void get_esi(uint32_t *reg);
extern void get_edi(uint32_t *reg);
extern void get_esp(uint32_t *reg);
extern void get_eip(uint32_t *reg);

int main(int argc, char **argv)
{
    uint32_t eax, ecx, edx, ebx, esp, ebp, esi, edi, eip;

    get_eax(&eax);
    get_ecx(&ecx);
    get_edx(&edx);
    get_edx(&ebx);
    get_ebp(&ebp);
    get_esi(&esi);
    get_edi(&edi);
    get_esp(&esp);
    get_eip(&eip);

    printf("eax: [%08X]\n", eax);
    printf("ecx: [%08X]\n", ecx);
    printf("edx: [%08X]\n", edx);
    printf("ebx: [%08X]\n", ebx);
    printf("ebp: [%08X]\n", ebp);
    printf("esi: [%08X]\n", esi);
    printf("edi: [%08X]\n", edi);
    printf("esp: [%08X]\n", esp);
    printf("eip: [%08X]\n", eip);
    return 0;
}

のような感じで、ポインタ引数で受け取ることを想定した関数にしてみました。
※最初戻り値で作ってみたのですが、戻り値だとEAXが取れなくなってしまいます。
まだ全関数のデバッグはできていませんが、問題なく動いていそうです。

ビルドは、


$ nasm -f elf reg.asm
$ gcc main.c reg.o
のような感じです。nasmを使う場合は -f でフォーマットを指定する必要があります。

getがなんとなく書けたのでついでにsetも書きたい。それができたらARMv7版も書いてみよう。