日曜プログラマがダラダラ書く このページをアンテナに追加 RSSフィード

2017-02-02

[]root がなくても git-svn が使いたい

よくあるニーズですね。

以下、Linux 環境でのおはなしです。

使いたいコマンドがインストールされていないなら、野良ビルドして、置けるところに置いて、パスをとおせばいいわけです。

git の野良ビルドなんて特に悩むところなんてないんですが、これが、git-svn を使いたいとなると git 本体だけでなく svn の perl バインディングが必要になります。これを、perl が見に行ってくれるところに置くにも root 権限がいるわけで、まあ、デフォルト以外のところも探しに行ってもらうような方法もあるのかもしれませんが、見つけられなかったので、じゃあもう、perl からインストールしちゃおう、というのが以下の手順になります。

なんだかんだと毎年1回くらいこれで苦労してるような気がするので、いい加減なにかメモを書いておこうと思った次第です。

まずインストール先を決める

今回は、${HOME}/.install/ にしました。

で、決めたら、環境変数 PATH と LD_LIBRARY_PATH をこれに合わせて設定しておきます。これが設定されてないと野良ビルドできないやつとかあります。業務の合間にぼちぼちとかいう感じで作業してると、ふつーに数日掛かり *1ということになったりするので、もう .bash_profile (とか、その類のファイル) に書いておきます。

export PATH=${HOME}/.install/bin:${PATH}
export LD_LIBRARY_PATH=${HOME}/.install/lib:${LD_LIBRARY_PATH}

基本的な作業の流れ

目的は、git コマンドが呼びだした → perl インタプリタが → use しようとしているモジュール (svn の perl バインディング) を見つけられるようにすること、なので、

  1. Perl モジュールの置き場所と、そこを見に行くインタプリタを用意するために perl を野良ビルドしてインストール
  2. Perl モジュールをインストール
  3. そのモジュールを見つけられる perl インタプリタを呼び出すような git コマンドを野良ビルドしてインストール

となります。

ところで、2. の Perl モジュールのインストールですが、これは CPAN にはなく、subversiontar 玉からインストールすることができます。

依存関係の解決

ディストロのパッケージシステムを使ってインストールするなら、依存関係は自動的に解決して必要なパッケージもインストールしてくれますが、野良ビルドだとそうはいかないわけで、configure スクリプトを実行してはエラーメッセージを読み、必要なライブラリの tar 玉を取ってきてインストールし、make でビルドエラーが起こればまた必要なライブラリの tar 玉を取ってきてインストールし、ってなことを繰り返して必要なコマンドをインストールすることになります。

今回、野良ビルドしたパッケージはこちら。

  • gdbm-1.12
  • perl-5.24.0
  • apr-1.5.2
  • apr-util-1.5.4
  • swig-3.0.11
  • subversion-1.9.5
  • git-2.11.0

もちろん、環境は千差万別なので、環境ごとに依存ライブラリは変わるでしょう。このメモが次回にどの程度役に立つかはちょっと心配なところです。

あと、野良ビルドしてインストールしたライブラリは、configure スクリプトは勝手には見つけてくれないことが多いので、そういうときはオプションなどで教えてあげる必要があります。configure スクリプトだと --help オプションでだいたいは分かりますが、Makefile の中を検索してうんぬんみたいなことをしたりなんだり。

手順

実行した手順をスクリプトとしてまとめて書いちゃうと以下になります。

#!/bin/bash -eu

DEST=${HOME}/.install

#
# perl

# gdbm
tar xf ~/.download/gdbm-1.12.tar.gz
cd gdbm-1.12
./configure --prefix=${DEST}
make
make install
cd -

# perl
tar xf ~/.download/perl-5.24.0.tar.gz
cd perl-5.24.0
./Configure -des -Dprefix=${DEST} -Dccflags=-L${DEST}/lib -Dldflags=-L${DEST}/lib
make
make install
cd -


#
# Subverion Perl binding

# apr
tar xf ~/.download/apr-1.5.2.tar.bz2
cd apr-1.5.2
./configure --prefix=${DEST}
make
make install
cd -

# apr-util
tar xf ~/.download/apr-util-1.5.4.tar.bz2
cd apr-util-1.5.4
./configure --prefix=${DEST} --with-apr=${DEST}/bin/apr-1-config
make
make install
cd -

# swig
tar xf ~/.download/swig-3.0.11.tar.gz
cd swig-3.0.11
./configure --prefix=${DEST} --with-perl5=${DEST}/bin/perl
make
make install
cd -

# svn swig-pl
tar xf ~/.download/subversion-1.9.5.tar.bz2
cd subversion-1.9.5
./configure --prefix=${DEST} --with-swig=${DEST}/bin/swig PERL=${DEST}/bin/perl --libdir=${DEST}/lib
make
make swig-pl
make install-swig-pl
cd -


#
# git

tar xf ~/.download/git-2.11.0.tar.gz
cd git-2.11.0
make prefix=${DEST} PERL_PATH=${DEST}/bin/perl all
make prefix=${DEST} PERL_PATH=${DEST}/bin/perl install
cd -

今回ハマったところをいくつかあげてみると、

  • perl の Configure が LD_LIBRARY_PATH を設定しても必要なライブラリを見つけてくれないので、ccflags、ldflags を指定する必要がある
  • もとから入ってた (=他の人たちが使う) svn に合わせて 1.7.8 を入れようと思ったらコンパイルエラー
  • subversion-1.9.5 の Makefile の distclean がバグってて、make swig-pl のやりなおしをすると必要なライブラリがビルドされない
    • tar玉を展開しなおすとビルドされる

参考にした情報

まとめ

サーバー管理者のひとにお願いして入れてもらうといいと思います。

*1トラブルシューティングしながらという感じにもなるので、今回は2週間かかった。

2013-12-08

[] Verilogのすごく細かいバッドノウハウ的なお話

この記事はHDL Advent Calendar 2013の参加記事というか、途切れてしまうと寂しいので間をつなぐためにお茶を濁してみました的な記事です。

間違い探し

0から15まで数える16進カウンタが必要なので、とりあえず何も考えないでこんな RTL を書いたとします。

  logic [3:0] count;

  always_ff @(posedge clk or negedge rst_b)
    if (~rst_b)
      count <= 4'd0;
    else
      count <= count + 1'b1;

いや、加算器の両側は、ビット幅そろえて書くだろ。

      count <= count + 4'd1;

と思ったあなた。あなたはこの先の罠にははまらないので、もう読まなくても大丈夫です。でも、せっかくなので読んでおくと、今後、いらんデバッグで時間をつぶさずにすむ可能性がちびっとだけ増えるかもしれません。

さて、ここまで書いたところで、カウンタ値は符号付の値と演算するのでカウンタ値も符号付にしなきゃいけない、と後から分かったとします。*1 修正しましょう。宣言だけでなく、リテラルも書き換えないといけませんね。

  logic signed [3:0] count;

  always_ff @(posedge clk or negedge rst_b)
    if (~rst_b)
      count <= 4'sd0;
    else
      count <= count + 1'sb1;

(わざとらしく) おっと! 符号ビットの分、ビット幅を増やすのを忘れていました。そうするとオーバーフローにも対処しないといけませんね!

  logic signed [4:0] count;

  always_ff @(posedge clk or negedge rst_b)
    if (~rst_b)
      count <= 5'sd0;
    else if (count == 5'sd15)
      count <= 5'sd0;
    else
      count <= count + 1'sb1;

さて、いちおうシミュレーションして動作を確認してみましょう。

……あれ?

間違い探しの答え

えー、まー、ここまで読んでいただいた方には、もうほとんど分かってると思うんですけど、私はこれでハマって、すくなくとも数時間は浪費したことがあります。ばかと呼んでください。

      count <= count + 1'sb1;

ここの 1'sb1 が問題なんですね。インクリメントしてほしいところがなぜかデクリメントされてる。はて、考えてみると符号付1ビット幅の数とはなんぞや。符号ビットしかないじゃないか、と。

3ビット幅あたりから考えてみましょうか。符号付3ビット幅の数の取りうる値の範囲は[-4,3]。2の補数表現を全部並べると[100,101,110,111,000,001,010,011]。同様に2ビットでは[-2,1]、[10,11,00,01]。*2

というわけで、1ビットでは[-1,0]ということになりますね。1'sb1 とは -1 のことなんです。count + 1'sb1 とは count + (-1) のことなんです! こんなん絶対だまされるわ!

回避方法

は、すでに書きましたね。加算器の両側のビット幅はそろえましょう。

うぅ、なんか当時を思い出して力がぬけてきた。

補足

このシチュエーションなら、カウンタは unsigned のままで $signed({1'b0, count}) とかってしたほうがよさげですね。

なお、この記事に限らず、私個人の見解は所属組織の見解とは関係ございませんので、あしからずご承知お願いいたします。

*1:Verilog がこんないいかげんな文法なのに Spyglass であんなにうるさくチェックするの、徒労になってる面が多々あると思うんだ……

*2: (2013-12-20修正) 恥ずかしいことに2の補数表現を間違えていたのを修正しました。

2013-09-21

[][] Lazy K での Hello World の書き方が分かった、気がする

CodeIQ の Hello World 問題に挑戦とかしてました。楽しかったです。

https://codeiq.jp/ace/cielavenir/q431

問題は「"Hello World" を出力するプログラムを、文字、文字列、数値リテラルを使わずに書け」というもの。最初は特に挑戦する気とかなかったんですが、ちょっと思いついたことをツイートしてみたら、出題者さんからレスをいただきました。*1

そういえば、Template Haskell を諦めたとしても、そもそも Lazy K 処理系を、数値リテラル抜きで書かなきゃないのでした。まぁ、@fumieval さんが書いた Lazy K 処理系と、Wikipedia からコピペしてきた Lazy K の Hello World を組み合わせただけで、自分が書いたプログラムとは言えないし、やっぱりやめとこ、とか思ったところで、また、ちょっと思いつきました。

……必要な数はわりと簡単に手に入る気がする。

というところで、@fumieval さんの Lazy K インタプリタを眺めてみましょう。

http://ideone.com/ST3kF

使っている数値リテラルは、0, 1, 256 の 3つだけです。というわけで、符号付き 8bit 整数の上限下限を組み合わせるだけで、いずれの値も手に入ります。

num127 :: Int
num127 = fromIntegral (maxBound::Int8)

num128 :: Int
num128 = abs $ fromIntegral (minBound::Int8)

num0 :: Int
num0 = num127 - num127

num1 :: Int
num1 = num128 - num127

num256 :: Int
num256 = num128 + num128

インタプリタの数値リテラルを、これらの変数で置き換えれば、要件は満たせますね。やったぁ。

……いえ、満たせません。問題はこうです。

標準出力に

Hello World

と出力するプログラムを作成して下さい。

Wikipedia からコピペした Lazy K プログラムの出力はこう。

Hello, world!

ざっとぐぐってみたところ、どの Hello World も "Hello, world!" っぽい。

ところで、わたしは Lazy K でのプログラムの書き方を知った上で、LazyKQQ の記事を書いたわけではないのです……。*2

Lazy K 処理系はなにをしているのか

そのようなわけで、Lazy K で ("Hello, world!" でなく) "Hello World" を出力する方法をさぐらなければいけなくなったのでした。そもそもの出題意図から軽く脱線している気がしますが、どうせいつものことです。

さて、既存の Lazy K プログラムを読んで理解しようなどと思うのは、多分無謀です。むしろ処理系の動作をちゃんと理解した上で、所望のプログラムを書くにはどうすればいいかを考える方がマシでしょう、多分。

もちろん、LazyKQQ を書いたときには、処理系がなにをしているかも全然分かってなかったのです。@fumieval さんのコードをコピペしただけですからねー。ただ、今月あたまにpartake.inという (正気とは思われない名前の) 会に参加させて頂いたこともあって、ちょっとはマシになったかな、と。

で、LazyKQQ を書いたときに、分かりやすく書き換えてみた main を引用してみましょう。

main = do
  input <- getContents
  output $ eval $ program :$ (encode input)

LazyKQQ は QuasiQuoter なので、コンパイル時にすでに program は構文解析済みの式ですが、そうでなければ、main でまずファイルからプログラムを読み込み、構文解析してから program を束縛します。

入力のバイト列は encode でコンビネータ式に変換されます。

(:$) は、2つの引数の、前者を後者に適用する式を作る構築子です。これで、program と (encode input) をひとつに式にします。合わせてできたひとつの式は、評価され、評価結果は encode と逆に (output 関数内で) デコードされ、標準出力に出力されます。

以上から、Hello World プログラムにおいて、eval に渡されるべき式はどうなるでしょう。イメージとしては、こう。

K "Hello World" (encode input)

Hello World は、入力に関わらず "Hello World" を出力しますので、プログラムとしては、Kコンビネータで、第2引数の入力を捨てるだけですね。*3 というわけで、問題は、文字列 "Hello World" をどうやって得るかですね。

……今、そこに、文字列をコンビネータ式に変換する encode 関数があるじゃないですか。

スコットエンコーディング

ghci で encode "Hello World" を評価してみましょう。

*LazyKQQ> encode "Hello World"
(S :$ ((S :$ I) :$ (K :$ ((S :$ ((S :$ (K :$ S)) :$ K)) :$ ((S :$ ((S :$ (K :$
S)) :$ K)) :$ ((S :$ ((S :$ (K :$ S)) :$ K)) :$ ((S :$ ((S :$ (K :$ S)) :$ K))
:$ ((S :$ ((S :$ (K :$ S)) :$ K)) :$ ((S :$ ((S :$ (K :$ S)) :$ K)) :$ ((S :$ (
(S :$ (K :$ S)) :$ K)) :$ ((S :$ ((S :$ (K :$ S)) :$ K)) :$ ((S :$ ((S :$ (K :$

(中略)

K)) :$ ((S :$ ((S :$ (K :$ S)) :$ K)) :$ I)))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) :$ (K :$ ((S
:$ ((S :$ I) :$ (K :$ (((S :$ I) :$ I) :$ (((S :$ I) :$ I) :$ ((S :$ ((S :$ (K
:$ S)) :$ K)) :$ I)))))) :$ (K :$ (((S :$ I) :$ I) :$ (((S :$ I) :$ I) :$ ((S :

長ぇ!! (37092 bytes)

一応、これをそのままコードに埋め込んで Hello World は動くみたいだけど、実行速度的に不安がある、かな……。

仕方がないので、"Hello World" のエンコードもちゃんと考えてみましょう。

encode は、このようなコードになっています。*4

encode :: String -> Expr
encode = foldr cons (cons (church 256) (church 256)) . map (church . ord)

cons :: Expr -> Expr -> Expr
cons a b = S :$ (S :$ I :$ (K :$ a)) :$ (K :$ b)

Lazy K は、自然数をチャーチエンコーディング、リストをスコットエンコーディングでエンコードします。*5

チャーチエンコーディングは聞いたことあるけど、スコットエンコーディングってなんぞや? って話は、ゆるふわ Lazy K 入門会で勉強してきました。よく思い出してみたら SICP で読んだことありました。ラムダ式でコンスリストを表現するってやつです。*6

cons = λ a b . (λ f . (f a b))
car = λ p . (p (λ a b . a))
cdr = λ p . (p (λ a b . b))

SKI コンビネータで書くとこうなります。

cons a b = S (S I (K a)) (K b)
car p = p K
cdr p = p (K I)

なんで、こうなるのか、っていうと、こういうこと、……らしいです。

(なんか、機械的に求める方法もあるっぽい……? *7 )

car と cdr については簡単なんで考えてみて下さい。

そんなわけで、encode は、Char から Int に変換して、チャーチエンコーディングして、それらをコンスリストにする、という処理になってます。

チャーチエンコーディング

ついでにデコードするほうも見てみましょう。

output :: Expr -> IO ()
output expr
    | x < 256 = putChar (chr x) >> (output $ cdr expr)
    | x == 256 = exitWith ExitSuccess
    | otherwise = exitWith $ ExitFailure $ x - 256
    where
      x = realize $ car expr

car :: Expr -> Expr
car expr = apply expr K

cdr :: Expr -> Expr
cdr expr = apply expr $ K :$ I

デコードするだけでなく、出力までしてますが、こんな感じです。コンスリストの処理なので、当然のように cdr ダウンしてます。チャーチエンコーディングされたコンビネータ式を整数にデコードしてるのが realize です。

realize :: Expr -> Int
realize expr = export $ expr `apply` Inc `apply` Export 0

export :: Expr -> Int
export (Export x) = x
export x = error $ "invalid output format (result was not a number:" ++ show x

チャーチエンコーディングされた整数n、というのは、関数 f を受け取り、f を引数に n 回適用する関数を返す高階関数、ですから、整数をインクリメントする関数を succ として、(チャーチ数 succ) 0 とすれば、チャーチ数→整数というデコードができます。

51b 数

そんなわけで、encode "Hello World" は、

cons (church $ ord 'H') $ cons (church $ ord 'e') $ cons (church $ ord 'l') $ ...

のように作られ、その結果が 37092 bytes になるわけです。*8 それにしては、よく見られる "Hello, world!" を出力するプログラムはそれほど長くはありません。LazyKQQ のサンプルに使った Hello World で 1K bytes 前後です。

Lazy K と Hello World でぐぐると、 究極の関数型言語による至高のHello, world! - Life Goes Onという記事が見つかります。この記事で、より短くチャーチエンコーディングする方法が紹介されています。ゴルフをするわけではないので、ここまでこだわることはありませんが、こちらの記事のために書かれたというコードを使わせてもらって、十分短い "Hello World" が得られそうです。

正直よく理解してませんが、得られたのでよしとしましょう。

Prelude> :l LazyK/Number.hs
*Main> map (fst . nb . Data.Char.ord) "Hello World"

として、得られた「51b数」のリストが以下です。

nbHelloWorld :: [Expr]
nbHelloWorld = [
 (S :$ ((S :$ S) :$ S)) :$ (((S :$ ((S :$ (K :$ S)) :$ (S :$ S))) :$ I) :$ ((S :$ S) :$ (S :$ K))),
 (S :$ S) :$ ((S :$ ((S :$ S) :$ (S :$ K))) :$ ((S :$ S) :$ ((((S :$ S) :$ S) :$ S) :$ ((S :$ S) :$ (S :$ K))))),
 (S :$ ((S :$ S) :$ ((S :$ S) :$ ((S :$ S) :$ S)))) :$ ((S :$ S) :$ ((S :$ S) :$ (S :$ K))),
 (S :$ ((S :$ S) :$ ((S :$ S) :$ ((S :$ S) :$ S)))) :$ ((S :$ S) :$ ((S :$ S) :$ (S :$ K))),
 (S :$ S) :$ ((S :$ ((S :$ S) :$ S)) :$ ((S :$ S) :$ ((((S :$ S) :$ S) :$ S) :$ ((S :$ S) :$ (S :$ K))))),
 (S :$ ((S :$ S) :$ (((S :$ S) :$ I) :$ ((S :$ S) :$ (S :$ K))))) :$ ((S :$ S) :$ (S :$ K)),
 (S :$ ((S :$ ((S :$ ((S :$ S) :$ S)) :$ ((S :$ S) :$ (S :$ K)))) :$ S)) :$ ((((((S :$ S) :$ S) :$ S) :$ S) :$ S) :$ ((S :$ S) :$ (S :$ K))),
 (S :$ S) :$ ((S :$ ((S :$ S) :$ S)) :$ ((S :$ S) :$ ((((S :$ S) :$ S) :$ S) :$ ((S :$ S) :$ (S :$ K))))),
 (S :$ S) :$ ((S :$ S) :$ ((S :$ S) :$ ((S :$ S) :$ ((S :$ ((S :$ S) :$ S)) :$ ((S :$ S) :$ ((((S :$ S) :$ S) :$ S) :$ ((S :$ S) :$ (S :$ K)))))))),
 (S :$ ((S :$ S) :$ ((S :$ S) :$ ((S :$ S) :$ S)))) :$ ((S :$ S) :$ ((S :$ S) :$ (S :$ K))),
 (S :$ ((S :$ S) :$ (S :$ K))) :$ ((S :$ S) :$ ((((S :$ S) :$ S) :$ S) :$ ((S :$ S) :$ (S :$ K))))]

実際短い!

定数、ふたたび

ところで、チャーチエンコーディング済みコンビネータ式と、realize があったら、そこから整数は得られるじゃないか、とあとから気づいたり。

0 だけは realize 自体に使われているので必要です。1 も使われてますが、これは succ に置き換えが可能です。

できあがり

以上をまとめたコードは Gist に上げておきました。提出したコードより、もう少しだけ整理してあります。

https://gist.github.com/h-hirai/6648418


追伸

HaskellVerilog を書く話は、もう飽きたので、つづかないと思います。

AST を直接いじるのはやっぱり面倒で、もう一層くらいはさまないとダメだなー、というのがやってみた感想。

*1:問題内容や解法についてのネタバレは遠慮してくれという注意が CodeIQ にある (そりゃそうだ) のをあとで見て、ちょっと反省してる。この記事については「問題やご自身のコードに関して、ツイートブログ記事など書いてくださって構いません。」とのことで書いてます。

*2:実は、Lazy K 処理系を書ける人より、Lazy K で Hello World 書ける人の方が少ないんじゃなかろうか。

*3http://d.hatena.ne.jp/rst76/20090427/1240845612

*4:なんで foldr の seed が (256 . 256) なのかはよく分かってない

*5http://fumieval.hatenablog.com/entry/2013/02/22/010432

*6:Lazy K は遅延評価なので自動的にストリームになる、……って理解であってる?

*7https://twitter.com/gengar68/status/376259612598497281

*8:長さについては記法もあると思いますが。

2013-06-23

[][] HaskellVerilog を書く話 (2)

ここのところ毎週そうしているように、この土曜日も、昼からビールを飲んでダラダラすごす予定だったんですが、ちょっと気が変わって、(500ml 缶 2本ほど飲み終わってから、) ゆるふわHaskell入門会に行ってきました。そこで pheaver さんの Verilog パーサをいじったり、懇親会で @wakaba_faure さんとお話ししたり、うっかりガチ勢の2次会に紛れ込んでしまい、なに話してんだかさっぱり分からないなりに刺激を受けたりと、それなりに有意義な一日でした。

で、Verilog パーサをいじってた内容がちょうど、チュートリアルの内容について @kazu_yamamoto さんがツイッターで触れていたことにちょっと関わるので、ついでにここでご紹介しようかな、と。



間違いた。



「データがそのまま入力できる」、「リテラルが自由自在」とはどういうことでしょうか。

別段、難しい話ではありません。例えば、以下のようにデータ型を定義すると、その型の値を表すリテラルが自動的に、一緒に定義されるということです。*1

data Puella = Mado | Homu | Saya | Anko | Mami

これで、"Mado", "Homu", "Saya", "Anko", "Mami" というリテラルが、Puella 型の値のリテラルとして、Haskell コード中で扱えるようになります。試しに、このコードをファイルに保存して、ghci に読ませてみましょう。

*Main> let magi = Homu
*Main> :t magi
magi :: Puella

このように、"Homu" という文字列が、ソースコード中で有効な値リテラルとして扱われ、そのまま入力できることが分かります。

ところでここで、Puella 型の値、Homu に束縛された変数 magi評価してみるとエラーになります。

*Main> magi

<interactive>:9:1:
    No instance for (Show Puella) arising from a use of `print'
    Possible fix: add an instance declaration for (Show Puella)
    In a stmt of an interactive GHCi command: print it

これは、Puella 型の値を、印字用の文字列に変換する方法が定義されていないため、ghci が print 関数を使ってその値を表示することができない、というエラーです。*2

これは、そのまま "Homu" を評価してみても同じです。

*Main> Homu

<interactive>:16:1:
    No instance for (Show Puella) arising from a use of `print'
    Possible fix: add an instance declaration for (Show Puella)
    In a stmt of an interactive GHCi command: print it

エラーメッセージにある通り、Puella 型を、Show 型クラスインスタンスにすることで、この問題を解決することが出来ます。あるデータ型を Show クラスインスタンスにするのは、自動導出という仕組みが使えるので簡単です。以下のようにコードを書き換えて、ghci に読み込み直してみましょう。

data Puella = Mado | Homu | Saya | Anko | Mami deriving Show
*Main> let magi = Homu
*Main> magi
Homu
*Main> (Mado, Homu)
(Mado,Homu)

後者の例は、まどほむにしてみたかっただけで、タプルにした意味は特にありません。要素が Show のインスタンスなら、そのタプルも Show のインスタンスになるというお話は、別にするつもりないです。とにかく、このように、あるデータ型の Show クラスインスタンスを自動導出すると、そのデータ型の値を評価した結果、そのリテラル表現と同じ文字列が出力されるようになります。


このような、言語処理系に入力する文字列表現と、言語処理系が出力する文字列表現が、同じになる性質を同図像性 (homoiconicity) と言います。


括弧の世界の人たちが重要視する性質です。*3 Haskell も、このような homoiconic な言語です。

(追記: あとになって、homoiconicity の説明としてはなにか間違ってるような気がして仕方がないのですが、どなたかつっこんでくださいませんでしょーか……。)


で、Verilog パーサの話

前回、「38行の AST 表現を Pretty Print して 11行の RTL 出力が得られましたやったー」という (間抜けな) ことを書いたわけですが、そもそも、Pretty Printer に食わせて所望の出力を得るための AST をどうやって得るのか、という話です。*4 手っ取り早い方法があります。所望の RTL をパーサに食わせてみればいいわけです。同図像性から、その出力はそのまま Haskell ソースコードとして有効な表現のはずです。

*Language.Verilog> Text.Parsec.parseTest module_item "always @(posedge clk) q <= d;"
AlwaysItem (EventControlStmt (EventControlExpr (EventPosedge (ExprVar (Ident "clk"))))
  (Just (NonBlockingAssignment (ExprVar (Ident "q")) Nothing (ExprVar (Ident "d")))))

印字された表現を、そのままコピペして Pretty Printer に食わしてみます。

*Language.Verilog> ppItem $
AlwaysItem (EventControlStmt (EventControlExpr (EventPosedge (ExprVar (Ident "clk"))))
  (Just (NonBlockingAssignment (ExprVar (Ident "q")) Nothing (ExprVar (Ident "d")))))

always @(posedge clk) q <= d;

バッチリですね。*5

ほかの例も試してみましょう。

*Language.Verilog> Text.Parsec.parseTest module_item "reg q;"
RegDeclItem (RegDecl reg Nothing [RegVar (Ident "q") Nothing])
*Language.Verilog> ppItem $
RegDeclItem (RegDecl reg Nothing [RegVar (Ident "q") Nothing])

<interactive>:3:31:
    Not in scope: `reg'
    Perhaps you meant `rem' (imported from Prelude)

ダメだ!! なんだこりゃ!?

問題は、module_item パーサが返した値のうち、RegDecl 値コンストラクタの第1引数です。"reg" なんて変数はたしかにありません。

RegDecl reg Nothing [RegVar (Ident "q") Nothing]

RegDecl 値コンストラクタの型は

RegDecl :: RegType -> Maybe Range -> [RegVar] -> RegDecl

なので、"reg" にあたる部分は RegType 型の値がくるべきだと分かります。ここで、AST を定義しているソースコード、Language/Verilog/Syntax/AST.hs を見てみましょう。*6 RegType 型の定義とともに、RegType 型の Show 型クラスインスタンス宣言があります。

data RegType
  = Reg_reg      -- ^ unsigned variable of any size = "
  | Reg_integer  -- ^ signed 32-bit variable
  | Reg_time     -- ^ unsigned 64-bit variable
  | Reg_real     -- ^ double-precision floating point variable
  | Reg_realtime -- ^ (same as above)
  deriving (Eq, Ord, Bounded, Enum, Data, Typeable)

instance Show RegType where
  show Reg_reg      = "reg"
  show Reg_integer  = "integer"
  show Reg_time     = "time"
  show Reg_real     = "real"
  show Reg_realtime = "real"

見つけました! おまわりさんこいつです! こいつが犯人です!! RegType 型の値を評価するとどうなるか、ちょっと見てみましょう。

*Language.Verilog> Reg_reg
reg
*Language.Verilog> Reg_integer
integer

当然ですが、上記の show で定義されてるように文字列が印字されます。やはり当然ですが、これらの印字結果は、定義されてる値コンストラクタの表現とは異なりますので、これをこのままソースコード中に書いてもエラーになります。逆に、先に Pretty Printer に渡そうとしてエラーになった "reg" の部分を正しい値コンストラクタに直してやると、正しく Haskell プログラムとして読み込まれるようになります。

*Language.Verilog> ppItem $
RegDeclItem (RegDecl Reg_reg Nothing [RegVar (Ident "q") Nothing])

reg q;

このように、自動導出まかせにせずに独自の show を定義したりすると、同図像性がくずれてしまい、利用者が「ちょっと式を評価してみてどんな値になるか試してみよう」と思っても、よく分からない表現が印字されて困ったりすることがあります。よっぽどのことがないかぎり、自前の show を定義しようなどと思わない方がよいでしょう。値を、その値コンストラクタとは異なる表現の文字列へ変換する関数が欲しい場合も、当然ありますがその場合でも、たとえば toString などといった Show 型クラスとは関係ない関数を定義するべきです。

というわけで、ゆるふわ Haskell 入門会のハッカソンタイムでは、このような同図像性が壊れてる部分をちまちまなおしたりしていました。修正したコードを、Fork して github に上げておきましたので、よろしければご覧になってみてください。

https://github.com/h-hirai/netlist-verilog

*1:正確にはこれはリテラルではないと思うけど、リテラルと見なしても実用上問題なさそうに思う。

*2:ghci を起動していたら、:t print してみましょう。

*3:こわい山本さんももともとそちらの出自ですね。

*4:いや、まぁ、実際は、地道にソースコードを追っかけてるわけなんですけど……。

*5:ちょっと改行をいじりました。

*6https://github.com/pheaver/netlist-verilog/blob/f3a0c46c3d0d8316c9471ea65cdc9dc6dba744e4/verilog/Language/Verilog/Syntax/AST.hs#L565

2013-06-14

記事名に(1)とかつけて続き物を書き始めておいてなんですが、真・女神転生IVで忙しいのでしばらく続きはありません。よろしくお願いいたします。

真・女神転生IV (2013年5月23日発売) - 3DS

真・女神転生IV (2013年5月23日発売) - 3DS