[コンピュータ開発][コンピュータシステムの理論と実践] OCamlでHack assemblerを実装(2)

前回からずいぶん間隔が空いたが、Hackアセンブラを拡張し、変数とジャンプ先にシンボルを利用できるようにした。

コードはこちら。
https://github.com/takeisa/ocaml-hack-assembler

サンプルコード Test.asm
1から100まで加算し、シンボルiで示すアドレスに計算結果を格納するプログラム。

// sum from 1 to 100
        @i
        M=1     // i=1
        @sum
        M=0     // sum=0
        
(LOOP) // comment(space)
        @i
        D=M     // D=i
        @100
        D=D-A   // D=i-100
        @END
        D;JGT   // if (i-100) > 0 then jump END
        @i
        D=M     // D=i
        @sum
        M=D+M   // sum=sum+i
        @i
        M=M+1   // i=i+1
        @LOOP
        0;JMP
(END)
        @END
        0;JMP

シンボルテーブルを出力するようにしたので、実行すると以下のようになる。

satoshi@jessie: ./assembler Test.asm
=== Symbol table ===
        SP 0000
       LCL 0001
       ARG 0002
      THIS 0003
      THAT 0004
       R00 0000
       R01 0001
       R02 0002
       R03 0003
       R04 0004
       R05 0005
       R06 0006
       R07 0007
       R08 0008
       R09 0009
       R10 000a
       R11 000b
       R12 000c
       R13 000d
       R14 000e
       R15 000f
    SCREEN 4000
       KBD 6000
         i 0010
       sum 0011
      LOOP 0004
       END 0013

[Docker][Debian]JessieにDockerをインストール

Dockerのインストールの解説には、Debian Jessieへインストールする手順が書かれているが、2015/5/17現在、backportsには存在せず、apt-getでインストールするには、sidからインストールしないとできないようだ。

sidは使いたくなかったので、いろいろ調べてみると、
http://linuxconfig.org/package-docker-io-has-no-installation-candidate-debian-jessie
の手順が一番簡単そうだった。

インストール手順

curlが必要なので、あらかじめ入れておく。
# apt-get install curl

Dockerをインストールする。
# curl -sSL https://get.docker.com/ | sh

試す。
# docker run -i -t ubuntu /bin/bash

root以外のユーザでdockerコマンドを使いたい場合は、dockerグループを追加する。
$ sudo usermod -aG docker your-user

注意点

Debianの場合、

docker - KDE3/GNOME2 docklet アプリケーション用システムトレイ

というパッケージがあり、これをインストールすると、dockerコマンドが衝突してしまうかもしれない。
Dockerを動かすVMはX Windowを使わないので、気にしないことにした。

その他

最近、Dockerを使い始めたのだけど、コンテナの起動は早く、いろいろなコンテナを手軽に起動してサービスを動かすことができるのは、非常に便利で、使っていて面白い。

[コンピュータ開発][コンピュータシステムの理論と実践]OCamlでHack assemblerを実装

「コンピュータシステムの理論と実装」
第6章 アセンブラ まで進んだ。

第一段階のシンボルフリーなHackアセンブラをOCamlで実装した。
https://github.com/takeisa/ocaml-hack-assembler

• 依存ライブラリはCoreとRe2。
• コマンドラインの解析は、Coreのライブラリを使用。ここを参考に実装した。

実行例

デバッグ用出力がいろいろ出ているが、Add.asmをアセンブルして、Add.hackを出力している。

$ ./assembler Add.asm && echo "----" && cat Add.hack 
ignore :   1 43 [// This file is part of www.nand2tetris.org]
ignore :   2 51 [// and the book "The Elements of Computing Systems"]
ignore :   3 36 [// by Nisan and Schocken, MIT Press.]
ignore :   4 37 [// File name: projects/06/add/Add.asm]
ignore :   5  0 []
ignore :   6 22 [// Computes R0 = 2 + 3]
ignore :   7  0 []
command:   8  2 [@2]
command:   9  3 [D=A]
dest=2 comp=48 jump=0
command:  10  2 [@3]
command:  11  5 [D=D+A]
dest=2 comp=2 jump=0
command:  12  2 [@0]
command:  13  3 [M=D]
dest=1 comp=12 jump=0
----
0000000000000010
1110110000010000
0000000000000011
1110000010010000
0000000000000000
1110001100001000

その他

デバッグ用に、レコード型やバリアント型の値を文字列に変換して表示したかったので、以前、Twitterで教えていただいたmeta_convを使って、変換する関数を自動で生成させようとした。
とりあえず、以下の単純なコードを作成して、

==hello.ml==

open Meta_conv.Open
open Ocaml_conv

type hello =
  | Foo of string
  | Bar of int
with conv(ocaml)

ocamlfindでコンパイルすると、エラーとなった。

$ ocamlfind ocamlc -verbose -package meta_conv,ocaml_conv -syntax camlp4o -package meta_conv.syntax hello.ml 
findlib: [WARNING] Interface topdirs.cmi occurs in several directories: /home/satoshi/.opam/4.02.1/lib/ocaml, /home/satoshi/.opam/4.02.1/lib/ocaml/compiler-libs
Effective set of preprocessor predicates: preprocessor,syntax,camlp4o
Effective set of compiler predicates: pkg_meta_conv,pkg_compiler-libs,pkg_compiler-libs.common,pkg_ocaml_conv,pkg_camlp4,pkg_type_conv,pkg_meta_conv.syntax,syntax,autolink,byte
+ ocamlc.opt -verbose -I /home/satoshi/.opam/4.02.1/lib/ocaml/compiler-libs -I /home/satoshi/.opam/4.02.1/lib/ocaml_conv -I /home/satoshi/.opam/4.02.1/lib/ocaml/camlp4 -I /home/satoshi/.opam/4.02.1/lib/type_conv -I /home/satoshi/.opam/4.02.1/lib/meta_conv -pp "camlp4 '-I' '/home/satoshi/.opam/4.02.1/lib/ocaml/camlp4' '-I' '/home/satoshi/.opam/4.02.1/lib/type_conv' '-I' '/home/satoshi/.opam/4.02.1/lib/meta_conv' '-I' '/home/satoshi/.opam/4.02.1/lib/meta_conv' '-parser' 'o' '-parser' 'op' '-printer' 'p' 'pa_type_conv.cma' 'meta_conv.cmo' 'pa_meta_conv.cma' " hello.ml
+ camlp4 '-I' '/home/satoshi/.opam/4.02.1/lib/ocaml/camlp4' '-I' '/home/satoshi/.opam/4.02.1/lib/type_conv' '-I' '/home/satoshi/.opam/4.02.1/lib/meta_conv' '-I' '/home/satoshi/.opam/4.02.1/lib/meta_conv' '-parser' 'o' '-parser' 'op' '-printer' 'p' 'pa_type_conv.cma' 'meta_conv.cmo' 'pa_meta_conv.cma'  'hello.ml' > /tmp/ocamlpp86694c
File "hello.ml", line 1:
Error: Error while linking hello.cmo:
Reference to undefined global `Ocaml_conv'
ocamlc.opt returned with exit code 2 

Ocaml_convがうまく参照できないようだ。
きっとライブラリの指定の方法か、OCamlの開発環境に原因があるのだろう。
こちらは、そのうち調べてみよう。

[OCaml]正規表現ライブラリRe2を使う

Core Document を眺めていたら、
Re2 OCaml bindings for RE2, Google's regular expression library
があった。
使い方をメモしておく。

インストール

opamでインストールできる。

$ opam install re2

例

以下はutopでの確認。

utop[11]> #require "re2";;

(* create関数の定義を確認 *)
utop[16]> Re2.Regex.create;;
- : ?options:Re2.Regex.Options.t list -> bytes -> Re2.Regex.t Or_error.t = <fun>

(* 正規表現を作る *)
utop[18]> let re = Re2.Regex.create_exn "aaa(.*)bbb";;
val re : Re2.Regex.t = <abstr>

(* 正規表現のパターンを取得する *)
utop[19]> Re2.Regex.pattern re;;
- : bytes = "aaa(.*)bbb"

(* マッチさせる *)
utop[20]> Re2.Regex.find_all re "aaaほげbbbaaaふがbbb";;
- : bytes list Or_error.t =
Core_kernel.Result.Ok ["aaaほげbbbaaaふがbbb"]

(* .*部分を最長一致さたいので正規表現を作り直し *)
utop[21]> let re = Re2.Regex.create_exn "aaa(.*?)bbb";;
val re : Re2.Regex.t = <abstr>

(* 再度マッチさせる *)
utop[22]> Re2.Regex.find_all re "aaaほげbbbaaaふがbbb";;
- : bytes list Or_error.t =
Core_kernel.Result.Ok ["aaaほげbbb"; "aaaふがbbb"]

(* サブマッチを取り出す *)
utop[23]> Re2.Regex.find_all re ~sub:(`Index 1) "aaaほげbbbaaaふがbbb";;
- : bytes list Or_error.t = Core_kernel.Result.Ok ["ほげ"; "ふが"]

(* マッチした文字列を置換する *)
utop[26]> Re2.Regex.rewrite re ~template:"<replaced>" "aaaほげbbbcccふがddd";; 
- : bytes Or_error.t = Core_kernel.Result.Ok "<replaced>cccふがddd"

(* サブマッチを取り出す(その2) *)
utop[27]> Re2.Regex.find_submatches re "aaaほげbbbaaaふがbbb";;
- : bytes option array Or_error.t =
Core_kernel.Result.Ok [|Some "aaaほげbbb"; Some "ほげ"|]

(* 先頭からマッチさせる *)
utop[28]> Re2.Regex.find_first re "aaaほげbbbaaaふがbbb";;
- : bytes Or_error.t = Core_kernel.Result.Ok "aaaほげbbb"

(* 先頭からのサブマッチ *)
utop[29]> Re2.Regex.find_first re ~sub:(`Index 1) "aaaほげbbbaaaふがbbb";;
- : bytes Or_error.t = Core_kernel.Result.Ok "ほげ"

(* マッチした部分で文字列を分割する *)
(* ~include_matches:true でマッチした文字列を含めることができる *)
utop[30]> let sre = Re2.Regex.create_exn ",";;
val sre : Re2.Regex.t = <abstr>
utop[31]> Re2.Regex.split sre "あい,うえ,おお";;
- : bytes list = ["あい"; "うえ"; "おお"]

マッチしない場合に例外となる関数も用意されている。
これらの関数は後ろに、_exnが付く。

utop[33]> Re2.Regex.find_first re "aaほげbbaaふがbb";;
- : bytes Or_error.t =
Core_kernel.Result.Error
 ("Re2_internal.Exceptions.Regex_match_failed(\"aaa(.*?)bbb\")")
utop[34]> Re2.Regex.find_first_exn re "aaほげbbaaふがbb";;
Exception: Re2_internal.Exceptions.Regex_match_failed("aaa(.*?)bbb").

エンコーディングはデフォルトでUTF-8が使用されるようだ。
オプション指定により、Lantin-1として扱うこともできる。
オプションはRe2.Optionsモジュールに定義されている。

とりあえず、これだけ分かれば、正規表現を使った文字列処理は困らないかな。

参考

• 高速かつ省メモリなGoogleの正規表現ライブラリ re2 についてのメモ

[コンピュータ開発][コンピュータシステムの理論と実践] CPUの作成

「コンピュータシステムの理論と実装」を課題をこなしながら、読み進めている。
1章あたり1週間のペースで課題を消化して、やっとCPUの作成が完了した。

NANDゲートを使ったANDやOR等の基本論理ゲートの作成から始まり、ALU、レジスタ、RAM、カウンタを作成した後、これらの素子を組み合わせて、CPUが完成した。

回路設計は回路図を書かずに、HDLを使うという簡易さはあるものの、ハードウェアエミュレータを使って、動作確認する際は、回路上の論理値の表示がピコピコ更新されて、なかなか面白い。
図はハードウェアエミュレータでCPUのテストが完了したところ。

 過去に、いろいろな回路を設計してきたが、簡易的とはいえCPUは初めてで、設計過程はとても面白かった。
今まで作成したものは、
https://github.com/takeisa/nand2tetris-project
に公開した。

[コンピュータ開発][コンピュータシステムの理論と実践] ALUの作成

先日、O'Reillyから「コンピュータシステムの理論と実装」が発売された。

NANDという電子素子からスタートし、論理ゲート、加算器、CPUを設計します。そして、オペレーティングシステム、コンパイラ、バーチャルマシンなどを実装しコンピュータを完成させて、最後にその上でアプリケーション（テトリスなど）を動作させます。 

という内容で、まえがきには「腕まくりをし、コンピュータをゼロから作り上げたいと願う読者のための本」と書かれている。
実際にはハードウェアは作成せず、Javaで書かれたエミューレータ上で、コンピュータを作っていく。

自分でデザインしたCPUを動かしたいと思い、DE0を購入し、入門書を参考に、簡単な回路を作ったりしていたのだけど、この本を一通りこなしてから、DE0でのCPU作成にとりかかろうと思う。

各章毎にテーマがあり、動作するものを作成していく構成になっている。
第1章 NANDを使って基本的な論理回路の作成
第2章 ALUの作成 まで完了した。
HDL(Hardware Description Language)で回路か記述し、ハードウェアエミュレータで動作確認をしていく。
エミューレータによるテスト中は、入力データ、出力データ、回路内部のデータがピコピコ表示されて面白い。

はまった点

いくつか、はまった点があったので書いておく。

Hardware Emulator

Windows8.1 + Java8の環境

画面右上にあるViewでOuputとCompareを選択しても、表示されない。
この挙動を見て、Linuxで作業することにしたので、解決方法は不明。
Javaのバージョンを下げると動くのかもしれない。

Debian Wheezy + Awesome Windowの環境

Manager Awesomeが便利なので、常用しているが、HardwareEmulatro.shを実行すると、一面グレーのウィンドウが表示されるだけ。
Java6,7,8、いずれも同じ現象。
Window ManagerをXfce4に変更したら正しく表示された。

HDLの書き方

ALUで、出力が0の場合に nz=1 となるように、以下の定義を書いたが、hdlの読み込みでエラーとなった。

Mux16(a = out0, b = nout0, sel = no, out = out, out[15] = ng);

Or8Way(in[0..7] = out[0..7], out = or0);
Or8Way(in[0..7] = out[8..15], out = or1);
Or(a = or0, b = or1, out = nonzero);
Not(in = nonzero, out = zr);

エミュレータの下部にエラーメッセージが表示されるが、一行しか表示されず、エラーの行番号は分かるが、肝心なエラー原因は途中で切れて分からない。エミュレータのウィンドウを広げても、表示幅は固定のため、内容を確認できない。
検索したり、試行錯誤したりして、以下のように記述したら、正しく解釈できた。

Mux16(a = out0, b = nout0, sel = no, out = out, out[15] = ng, out[0..7] = out1l, out[8..15] = out1h);

Or8Way(in = out1l, out = or0);
Or8Way(in = out1h, out = or1);
Or(a = or0, b = or1, out = nonzero);
Not(in = nonzero, out = zr);

エミューレータのソースは公開されているので、手っ取り早く対応するには、エラーメッセージを標準出力に出力するようにすれば、便利かも。

 その他

ハードウェアエミュレータは素子の遅延時間は見ない 遅延時間は見ないので、非効率な回路を定義しても、論理的に合っていればテストOKとなる。 実際に回路を組むときは、この遅延時間を考慮することは非常に重要なのだけど、ここまで、記述はないようだ。

[Ruby][Hipchat]Hipchat用のBotをLitaで作る(2)

前回に引き続き、LitaでBotを作る。
今回は簡単な応答をするようにしてみよう。

後でgemで公開するつもりなら、
$ lita handler lita-ハンドラ名称
とすれば、雛形を作ってくれるようだ。

今回は単純に、「@Bot名 hello」と書きこみがあったら、「〜さん、こんにちは。」と応答するだけのHandlerを作る。
ソースは以下の通り。

module Lita
  module Handlers
    class HelloHandler < Handler
      route(/^hello/, :hello, command: true)

      def hello(response)
        response.reply("#{response.user.name}さん、こんにちは。")
      end
    end
  end

  Lita.register_handler(Handlers::HelloHandler)
end

routeで応答するメッセージの正規表現と呼び出すメソッド(:hello)を指定し、
呼び出されるメソッドhelloでは response.user.nameでメッセージを書いたユーザ名を参照し、response#replyで、応答メッセージを返している。
routeメソッドで command: trueを渡しているのは、@Bot名で、Botを宛先にしたメッセージだけに応答するためである。
commandの詳細については、こちらを参照。

デバッグ中は lita_config.rb を以下のように設定すると、コマンドラインで動作確認できる。

config.robot.adapter = :shell
config.adapters.shell.private_chat = true 

ただし、この場合は、routeメソッドでcommand: false にし、 テスト時には、@Bot名を付けずに、helloだけにしないと応答しない。

      route(/^hello/, :hello, command: false)

コマンドラインでの実行例

$ lita
Type "exit" or "quit" to end the session.
Lita Bot > hello
Shell Userさん、こんにちは。
Lita Bot >