mcommit's message

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

C言語でbrainfuckを実装してみた

なんだかすごく今更ですが、気分的になんとなく実装してみました。

仕様把握

そもそもbrainfuckの仕様がよく把握できていないのでwikipedia等いくつかのサイトを参考にさせて頂きました。

Brainfuck - Wikipedia
Brainf*ck

Hello Worldなどいくつかサンプルコードを動かしてみましたが一応動いてそうです。

書いてみたコード

#include <stdlib.h>
#include <stdio.h>

#define CODE_LEN_MAX            (1024)
#define DATA_LEN_MAX            (30000)
#define STACK_LEN_MAX           (32)

static unsigned char code[CODE_LEN_MAX]        = {0};
static unsigned char buf[DATA_LEN_MAX]         = {0};
static unsigned char stackframe[STACK_LEN_MAX] = {0};

int main(int argc, char **argv)
{
    int c;
    int ip = 0;
    int sp = 0;
    int ptr = 0;
    int clen = 0;
    FILE *fp;

    if (argc < 2)
    {
        fprintf(stderr, "Input Code File path.");
        exit(-1);
    }
    fp = fopen(argv[1], "r");
    if (fp == NULL)
    {
        fprintf(stderr, "Source file open failed\n");
        exit(-1);
    }

    while(1)
    {
        c = fgetc(fp);
        if (c == EOF)
        {
            break;
        }

        if (CODE_LEN_MAX < clen)
        {
            fprintf(stderr, "Code Size too large\n");
            exit(-1);
        }
        if (c == '\n')
        {
            continue;
        }
        if (c == '\r')
        {
            continue;
        }
        if (c == ' ')
        {
            continue;
        }

        code[clen++] = c;
    }

    #if 0
    fprintf(stdout, "Program loaded, size:[%d] byte\n", clen);
    #endif

    ip = 0;
    while(1)
    {
        switch(code[ip])
        {
        case '>':
            ptr++;
            ip++;
            break;
        case '<':
            ptr--;
            ip++;
            break;
        case '+':
            buf[ptr]++;
            ip++;
            break;
        case '-':
            buf[ptr]--;
            ip++;
            break;
        case '.':
            printf("%c", buf[ptr]);
            ip++;
            break;
        case ',':
            buf[ptr] = getchar();
            ip++;
            break;
        case '[':
            stackframe[sp++] = ip;
            if (buf[ptr] == 0)
            {
                while(1)
                {
                    ip++;
                    if (code[ip] == ']')
                    {
                    	sp--;
                        ip++;
                        break;
                    }
                }
            }
            else
            {
                ip++;
            }
            break;
        case ']':
            if (buf[ptr] != 0)
            {
                ip = stackframe[sp-1];
                ip++;
            }
            else
            {
            	sp--;
                ip++;
            }
            break;
        default:
            fprintf(stderr, "err:%X, ip:%d, size:%d\n", code[ip], ip, clen);
            exit(-1);
            break;
        }

        if (clen <= ip)
        {
            break;
        }
    }
    exit(0);
}

感想

"[","]"の条件分岐とループのところはちょっと面倒というか仕様理解も含めて時間がかかりました。
いまだに正しい仕様がなんなのかいまいち分かっていないのですが、"[","]"はネストに対応してあげるのが正しい実装のようです。
でもバグがあってちゃんと動かないコードとか出てきたりするかもしれません。

brainfuckを実装するのは楽しいのですが、brainfuck自体のコードは難読でデバッグがやり辛く面倒なので結局自分でコードは書きたいとは正直思いませんでした。
なので実装のバグとりも十分できていない気がします。

brainfuckはコードを書かないから、Lisp処理系でもちょっと書いてみたいと思い、調子に乗ってとりあえず電卓レベルの実装を書いてみました。

mcommit.hatenadiary.com

Lispの電卓機能を実装してみる

冬休みということで少し時間があるのでいろいろ勉強しているのですが、なんとなくLisp処理系を書いてみたくなったのでRubyで実装してみたいと思います。

Lisp処理系の実装というとshemeの仕様を理解して実装するのが一般的らしいのですが、冬休みで時間も限られているのでとりあえずLisp風の入力に対する電卓レベルの機能をRubyで書いてみました。
※そもそもLispの機能自体をよく知らないのでどこまで真面目にかけるか分かりませんが気が向いたら続けて書いてみたいと思います。

このレベルだとまだ比較的短いです。せっかくなのでブログにも挙げておきたいと思います。

書いてみたコード

gist.github.com

補足・解説

LispLisp Processing の通り、リスト構造を使って処理するのが特徴ですが、処理系を実装しようとしてみるとその特徴がよく分かります。

最初C言語で書こうとしていましたが、そもそもList構造のコードを書くのも面倒だなということでとりあえずRubyで書いてみました。

普通の電卓コードは結構前にC言語でかいた事がありますが、電卓を書く際のこつとして、中間記法を後置記法に変換するのがポイントになります。

mcommit.hatenadiary.com

例えば、 1 + 2 であれば、 1 2 + という順番に変換して、スタックをうまく使うとカッコつきの演算がかなり素直に実装できます。

Lispの場合は四則演算の計算する場合、中間記法ではなく前置記法になります。上記の 1 + 2 はLispでは(+ 1 2)と書きます。
また、(1 + 2) * 3 のような式は(* (+ 1 2) 3) のような書き方になります。

後置記法はスタックで処理するのに適していますが、前置記法はリスト構造で前から順番に処理するのに適していることが実際に(電卓レベルですが)処理系を実装してみるとよく分かりました。

こうして四則演算の入力に対する処理系を書いてみると、

では人間はどうして中間記法を使うんだろうか?

という疑問が湧いてきます。

もしかしたら脳内の構造はスタックでもリストでもない構造になっているじゃないかなと思いました。

感想

文字列の解析部のコードがかなりRubyらしくないというかダサい感じになりました。もう少し綺麗にできそうなオーラが漂っています。※異常系の処理も書いていません。

手抜きしたところと、Rubyらしさを活かしてもっと手抜き出来るところもあるのでコードとしては微妙ですがあとでC言語に書き直したいということもあるのであまり手抜きしすぎるとC言語に直す時に「あれっ!?ここどうしよっかな・・・」みたいなことになりそうな気がします。

Lispの実装についてよく知らないので、gaucheのドキュメントとか読んでみたらスタックマシンを使って実装しているそうでした。
Lispの処理系というのは真面目に作る場合やはりVMから作る必要があるんだろうか・・・
VMを作るといってもRubyを使えばスタックマシンの実装はそんなには難しくはない(書くコード量は多くはない)だろうけど、なんというか気合と時間はそれなりに必要になりそうで多分時間が足りなくなる気がする。

2017年にやりたかったことの振り返り

2017年にやったこと振り返り

今年(2017年)の初めにいくつかやりたい事を上げましたが、達成度の振り返りや来年に向けての反省等書いておきたいと思います。

2017年にやりたかった事

こちらの記事に書いていたのは、

http://mcommit.hatenadiary.com/entry/2017/01/16/010634

やりたいこと 期間 規模 難易度
コンパイラorインタプリタを自作する 長期 高い
月に2記事はブログを更新する 長期 まあまあ
ディープラーニングについて勉強する 短期 高い
FPGAで遊ぶ 長期 まあまあ
経済学の勉強をする 短期 まあまあ
Linuxデバイスドライバを書いてみる 短期 低い

の6点。

コンパイラorインタプリタを自作する

残念ながら自作コンパイラインタプリタを完成させることはできませんでした。
ですが、今年は4月から7月まで聴講生として関学理工学部コンパイラの授業に参加させて頂きました。

授業では、C言語のサブセットの言語を実装し、仮想スタックマシン上で動かす課題がありました。
構文解析再帰下降パーサを実装します。スタックマシンの命令はシンプルですが、基本的な命令は揃っていたように思います。
締め切りのある課題は普段なかなか勉強がはかどらない社会人としては締め切りが迫ることで「やらなくては!」となるのでむしろ助かりました。

課題をこなすことで、再帰下降パーサによる言語処理系の実装はイメージができましたが構文解析の自動化等、授業で深く学んでいない部分にも興味が出てきて今勉強しているところです。※所謂first集合とかfollow集合とかの話のあたり。

ということで、コンパイラの勉強に関しては、成果物としては区切りのいいものはアウトプットできませんでしたが、勉強はできたので悪くはない成果だったと思います。

月に2記事はブログを更新する

これは無事達成できました!

月2記事という量は多くはありませんが、仕事が忙しくなると各ネタが無かったり書く時間がなかったりします。
中身のある記事を書くというのは事前準備・学習・情報取集にすごく時間がかかります。

書くのが辛い時でも、内容の質にこだわらず、何かしら最低月2記事を書いたというのは結構達成感があります。

反面、読む人のことを意識したり、何かプラスになるような情報提供ができていない記事が多いようにも思うので、読んでくれる人のプラスになる情報を発信することをより強く意識する必要性を感じました。具体的に落とし込めていない内容もあるので、もっと短時間で内容の濃い文章としてまとめれるように書く訓練が必要な気がします。

反省点

9月~10月頃にElixir/Erlangの勉強をした時期がありましたが、勉強した内容を記事に書くことにこだわり過ぎてしまい、遅くまで作業をしたこともあり完全に体調を崩してしまいました。
当たり前のことですが、調子に乗り過ぎず、体調のことも考えて作業する必要性を感じました。

ディープラーニングについて勉強する

AIが流行っていることもあり、勉強しようと思っていたのですが、結局何も手を付けることができませんでした。

FPGAで遊ぶ

こちらも特に成果を出せませんでした。

経済学の勉強をする

経済学の勉強はあくまで趣味ですが、今年も何冊か高橋洋一さんの本を読みました。マンキュー経済学の勉強はできていません。

Linuxデバイスドライバを書いてみる

とりあえずカーネルモジュールは書いてみました。

http://mcommit.hatenadiary.com/entry/2017/12/14/234643

しかしながらカーネルモジュールのメリット(というよりカーネル側の動作の仕組み)がよく理解できていません。

もう少し明確な目標設定と勉強が必要そうです。

全体的な反省

  • 具体的な数字や行動を目標とすべき。数字や具体的な行動がないとただの宣言で終わってしまう・・・
  • 時間が限られている以上、より少なく目標を設定し、達成結果に応じて目標や行動を修正した方がよさそう。


今年もあともう少し・・・来年も頑張ろう。

Ceyo Switch PRO コントローラーの接続手順

[ 12/28日 追記]
この記事で紹介したCeyo のコントローラですが、マインクラフトで試しているとどうもZLボタン(左上の下側)のボタンが認識されていないようです。
やはり廉価品ということで壊れやすかったりするようですので購入される方は注意された方がよいかもしれません。

 -------- ↑追記 --------


昨日12/24日に、どなたか存じ上げませんが親切な人がうちの娘にSwitchを届けてくれました。どうもありがとうございます。
さて、Switchにはジョイコントローラと呼ばれるコントローラが1セットついているのですが、このままでは2人で何かゲームをしたいという場合に一緒に遊べないのでコントローラを買うことにしました。


とりあえず遊べる安価なコントローラを更に探してみたところ、「Ceyo Switch PRO コントローラー」というのが安価でよさげということで買ってみました。

有線(USB)版とBluetoothのワイヤレス版とあるようですが、線があるとやはり邪魔になるだろうということで、Bluetooth のワイヤレス版の方を買ってみました。

さて、このCeyoのコントローラですが、Swith本体に接続するまでにかなり苦戦しましたので接続手順を書いておきたいと思います。

なお、設定手順はAmazonの商品ページに書かれています。あと商品にも英語のマニュアルがついていますがこちらは分かり辛く、下記に書いた必要な手順が抜けていました。

接続手順

コントローラを接続するまでの流れですが、

  1. Switch本体をテーブルモードにする。
  2. コントローラ「持ち方/順番を変える」を選択
  3. コントローラ側で Yボタン+HOMEボタンの2つを同時長押し、LEDが点灯したらAボタンを押す。

になります。

Switch本体をテーブルモードにする。

これが重要なポイントです。テストに出ますセンター試験現代社会」で出ます。

もちろん嘘ですけど、それくらい重要なポイントです。

テーブルモードとはこのような状態のこと。
f:id:simotin13:20171225230443j:plain
※後ろのスタンドは無理に引っ張ると「バキッ」ってなるやつなので注意。あえてスタンド立てる必要はないかもしれません。

ちなみに私はTVモードで2時間ぐらい接続を試していました・・・

f:id:simotin13:20171225230500j:plain
起動したらタッチパネルで操作。ホーム画面へ遷移します。

コントローラ「持ち方と順番を変える」を選択

"コントローラ"→"持ち方/順番を変える" というのがコントローラの登録画面のようです。

f:id:simotin13:20171225230510j:plain

f:id:simotin13:20171225230519j:plain

コントローラ側で Yボタン+HOMEボタンの2つを同時長押し

登録画面が表示されたらYボタン+HOMEボタンの2つを同時長押しします。
続けて、コントローラ側のHOMEボタンのLEDが点灯したらAボタンを押します。
コントローラとのSwitch間の応答性がよくないのが、何回かAボタンを押さないと登録できませんでした。
無事登録されれば、画面にコントローラが表示され、登録したCeyoのコントローラから操作ができる用になります。

1度登録できれば、TVモードでSwitch本体を起動した後でもHOMEボタンを押す事でコントローラを認識してくれます。

試しにマインクラフトで2人同時プレイを試してみましたが、このコントローラで+ボタンを押すと問題なく乱入できました。

感想

接続が恐ろしく分かりにくい商品ですが、一度繋がってしまうとボタンやスティックの配置などはSwithのジョイコントローラと近い感じになっているのでいい感じで使えます。でもまぁお金に余裕があるなら任天堂純正の方がよいかもしれません(高いけど)

GAOHOUのTTL-USBシリアル変換ケーブルを買ってみた

amazonを見ていると格安のUSB-TTL変換ケーブルが売っていたので買ってみました。

商品タイトルにはラズベリーパイ用とありますがTTL(3.3V)であればラズパイに限らずマイコンとのUART通信に普通に使えます。
値段は350円程度なので、壊れてもまぁいいかくらいの感じです。

デバイスドライバ

変換用チップにはPL2303(Prolific)が使われているようです。

私の環境はWindows10ですが

こちらのサイトからドライバをダウンロードしました。

Products

動作確認

値段がすごく安いのはありがたいのですが、説明書とかは一切ありません。
各線の信号が分からなかったのですが、amazonのレビューなどを見ていると、

黒:GND
赤:電源(5V)
白:RX
緑:TX
とのことです。

ということで白と緑を繋いでループバックによる動作確認をしてみたところ問題なく動作しました!

windows10だと相性はいまいち!?

上記の通り、ドライバをインストールして無事通信できたのですが、どうも起動時にケーブルをUSBポートに挿しておかないと正しく認識してくれません。
また、ケーブルUSBポートから一度抜いてしまうとこれまた正しく認識できません。

念のためにと思ってWindows7でも試してみました。7だと抜き差ししても特に問題なく認識しています。

ともあれとりあえず格安で使えるTTL-USB変換ケーブルが手に入れることができてよかったです。

Linuxのカーネルモジュールを書いてみた

今年の1月に書いた、2017年にやりたいこと

mcommit.hatenadiary.com

Linuxデバイスドライバを書いてみる

というのを挙げておりましたが、この12月に至っても達成できていなかったのでとりあえずLinux mint上でカーネルモジュールを書いてみました。
書いたといってもロードとアンロードしかできない、まさにカーネルモジュールのhello world程度のものです。

書いてみたコード

  • kmod.c
#include <linux/module.h>
#include <linux/init.h>

MODULE_LICENSE("Dual BSD/GPL");

static int hello_init(void)
{
	printk(KERN_ALERT "driver loaded, hello kernel.\n");
	return 0;
}

static void hello_exit(void)
{
	printk(KERN_ALERT "driver unloaded, good bye kernel.\n");
}

module_init(hello_init);
module_exit(hello_exit);
obj-m += kmod.o

all:
        make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules

clean:
        make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean

ビルドとモジュールの確認

make を実行し、正常にビルドできると kmod.ko が生成されています。


$ file kmod.ko
kmod.ko: ELF 64-bit LSB relocatable, x86-64, version 1 (SYSV), BuildID[sha1]=0acdb23dfc45137854b91cb3edbb2ed09f205e78, not stripped

modinfo でカーネルモジュールの情報が取得できます。
上記のkmod.cではLicenceくらいしか情報を埋め込んでいませんが、色々とモジュールに情報を埋め込むマクロがあるようです。


$ modinfo kmod.ko
filename: /home/miyazaki/driver/kmod.ko
license: Dual BSD/GPL
srcversion: F5A8F473E31B45AC339CFDB
depends:
vermagic: 4.4.0-21-generic SMP mod_unload modversions

ロードとアンロード

insmodでカーネルモジュールのロード

ロードされているモジュールの確認はlsmodコマンドを使います。


$ sudo insmod kmod.ko

$ lsmod | grep kmod
kmod 16384 0

16384はモジュールのサイズ。最後の0は参照カウンタの値になるそうです。

rmmodでカーネルモジュールのアンロードができます。


$ sudo rmmod kmod

printkの出力先

printkの出力先は標準出力でも標準エラー出力でもありません。
カーネルリングバッファになるそうです。確認は dmsegから。


$ dmesg
...(略)
[26564.817444] driver loaded, hello kernel.
[27166.340079] driver unloaded, good bye kernel.

おぉ。printkも文字列が出力されています。

感想

module_initとかmodule_exitとかrubyの拡張ライブラリとかと雰囲気にてとっつきやすかったです。
コード自体は単純なので、肝になるのは参照しているMakefileの中身だと思いみてみました。

今回私が試した環境は、


$uname -a
Linux mint 4.4.0-21-generic #37-Ubuntu SMP Mon Apr 18 18:33:37 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux

になります。

make -C で参照しているMakefileは /lib/modules/4.4.0-21-generic/build/Makefile にありました。
1600行ぐらいあって、ざっと見ただけでは何が重要なのかわかりませんでした。まぁこの編は必要になったらおいおい勉強ということで・・・

initとexitだけではカーネルモジュールをあまり書いてみた意味がないので今回を取っ掛りとしてもう少し何かデバドラ的なことをしてみたいです。

でもカーネルモジュールで書くメリットとは何なんだろう・・・

  • ハードのデバドラ
  • アプリで書くより早い!?(パフォーマンス面)

とかなんだろうか。

参考にした書籍

Linuxデバイスドライバプログラミング

Linuxデバイスドライバプログラミング

RaspberryPiで学ぶ ARMデバイスドライバープログラミング

RaspberryPiで学ぶ ARMデバイスドライバープログラミング

最初はラズパイのデバドラを作るのを試していましたが、GPIOのレジスタの種類が多そうな感じだったのでとりあえずPC上で何もしないカーネルモジュールを書いてみることにしました。カーネルでGPIO触るだけでもLinuxだと色々と覚えることがありますね。ワンチップマイコンだと方向レジスタとデータレジスタ触るだけでいいのに。

「戦略参謀」を読んだ

ジュンク堂大阪本店のビジネス書のコーナーの目立つところで売られていたので目にとって読んでみたらなんか面白そうだったので買ってみました。

読後の感想、思ったこととか書いておきたいと思います。

概要

基本的には「紳士服のしきがわ」というスーツの小売業の会社を舞台にした小説風のビジネス書です。
同じような雰囲気の書籍としては、「100円のコーラを1000円で売る方法」が近いように思いました。
※「100円のコーラを1000円で売る方法」はマーケティングに関する書籍でしたが、本書は会社経営全般に関わる内容で書かれています。
ざっくりというと、小説8割、ビジネス書としての解説2割といった割り振りでしょうか。

ストーリーとして、「紳士服のしきがわ」をよくするための改革勢力 vs 自己の利益・保身を考える抵抗勢力といった構図で書かれており読みやすく小説としてとても面白かったです。
小説部分は、1日で一気に読みました。ビジネス書としての部分は分量は少ないですが、PDCA・経費削減の手法、社内改革について書かれておりこちらも咀嚼は必要ですがためになる内容だと感じました。

良かった点

「人、性善なれど、怠惰なり」という言葉が、空海真言宗の思想と一緒に本書内で何度か語られます。
ビジネス書ではあまりこういった人間観・宗教感のような内容は語られませんが、ビジネスは人が集まってするものです。
人を束ねて仕事を進める立場にある人間は、こういった「人間の性(さが)」というものをしっかりと見つめ、自分なりの考えを持った上で事にあたらないといけないものだと感じました。

解せなかった点

全体的にとても面白い小説でしたが、本書に登場する登場人物の年齢が設定にいまいち読み取れない箇所がありました。
小説中に、安部野というコンサルタントとその妹の彩という女性が登場します。

高山という、いわばこの小説の主人公とこの妹の彩という女性がくっつく感じでこの小説は終わります。
安部野という人物は相当できるビジネスマンで、人間心理にも通じた人物として書かれており、「紳士服のしきがわ」の会長(どう考えても60後半から70代の高齢)にも物怖じせず話をします。

となると、この安部野は40代後半から50代・60代のイメージになります。

一方、高山という主人公は、まだまだビジネスマンとしては稚拙なところがあるが、一生懸命な行動をとる好青年として書かれています。恐らく20代後半から30代前半のイメージでしょう。

40代後半~60代男の妹である彩と、どう老けさせたとしても30代前半の高山・・・
かなり歳の離れた妹ということなんだろうか・・・

読後感

企業内の改革や、創業者から2代目に事業継承をした後でどういったことが起こるのか、大企業でのどろどろした社内政治など、かなりリアルに描かれているように感じました。
私自身は大企業に勤めたことはありませんが、いろいろと見聞きする限りでは社内政治・人事の力学・権力争い・実績争いはあるようですので、多くのビジネスマンの方は共感したり感情移入して読めるのではないかと思います。

私の考えでは、会社とは仕事を通して価値を生み、その対価をお客様から頂くための組織です。またサラリーマンは自分の能力と時間を企業に提供し、企業はその対価を支払うものだと思います。
社内の政治はお客様視点から見れば一切どうでもよい話です。
本当の勝敗は消費者が決めるもので、社内の政治に勝利したところで、市場での競争に敗れれば何も意味はないと思うのですが、人間というのはなかなか頭で分かっていても心と体はついてこないというのが現実ですね。

「人、性善なれど、怠惰なり」

という言葉はなかなか深いように感じました。