CWEB言語で書かれたドキュメントをctangleとcweaveを用いてC/C++とTeXに変換する方法を説明します。
CWEB (ctangle, cweave) とは、1980年台に Donald Knuth 氏と Silvio Levy 氏によって開発されたツールです。 CWEBフォーマットで記述された1つのファイルから、 CWEBシステムが「プログラム実行ファイル (の元となるソースコード)」と「ドキュメント (の元となるソースコード)」へ変換します。 ツールは ctangle と cweave の2つのプログラムで主に構成されます。 全体フローを以下の図に示します。
Knuth氏による公式ページです。
現在は積極的に開発はされていないぽくて、CWEBを利用しているプロジェクトもほとんど見かけないと思います。 今回は、ルービックキューブの任意の状態から完成状態までの手数の上限値が20であることを証明した cube20.org というプロジェクトの配布形式がCWEBであったため、 CWEBの導入方法を調査したので共有します。
以下のサイトから cweb.exe をダウンロードしてください。 これがインストーラとなっています。 インストーラでインストール完了後、ツールの実行バイナリが Program Files のどこかに保存されると共にパスも勝手に通してくれるので インストール直後からコマンドラインでツールが使用可能になると思います。 私は Windows 7 (64bit) で試してみました。
私の環境は Cent OS 6.7 です。
ソースファイルへはこの記事の冒頭に書いた公式ページに張ってあるリンクからアクセスできます。
具体的には以下のコマンドでインストールすることが可能です (ctangle と cweave は /usr/local
ディレクトリ以下にインストールされます)。
本記事執筆時点 (2015-10-10) で Version 3.64 がインストールされます。
本記事の残りのパートはCentOS環境下での実行です。
$ sudo yum install texlive-* (※TeX環境が未インストールの場合のみ) $ wget ftp://ftp.cs.stanford.edu/pub/cweb/cweb.tar.gz $ mkdir cweb && tar xzf cweb.tar.gz -C cweb $ cd cweb $ make $ sudo make install
ctangle と cweave のヘルプを表示させてみましょう。 この2つのプログラムはコマンドライン引数を省略するとusageが出力されます。
$ ctangle ! Usage: ctangle [options] webfile[.w] [{changefile[.ch]|-} [outfile[.c]]] (That was a fatal error, my friend.)
$ cweave ! Usage: cweave [options] webfile[.w] [{changefile[.ch]|-} [outfile[.tex]]] (That was a fatal error, my friend.)
さて、CWEBの環境構築が完了しました。
以前書いた記事で紹介したことがあるように cube20.org は「ルービックキューブのGod’s Numberが20手であることを証明するときに使用されたプログラムです」。 God’s Numberが20手であるということは、すなわち、
ことを示しました。このプログラムは以下に示したリンクより配布されていますが、形式がCWEBです。 早速今構築した環境でコンパイルしてみましょう。
まず、ソースをダウンロードします。
$ cd ~ $ wget -r -np http://cube20.org/src/ $ cd cube20.org/src/
cube20.org の配布に含まれているMakefileにすでにCWEBからC/C++への変換するコマンドが記述されていますので、
自らコマンドを打つ必要はありません。
make -n
とタイプすることで make したときに実行されるコマンド列を見てみましょう。
$ make -n ctangle twophase ctangle phase1prune ctangle phase2prune ctangle kocsymm ctangle cubepos g++ -DHALF -O4 -Wall -DLEVELCOUNTS -o twophase twophase.cpp phase1prune.cpp phase2prune.cpp kocsymm.cpp cubepos.cpp -lpthread ctangle hcoset g++ -DHALF -O4 -Wall -DLEVELCOUNTS -o hcoset hcoset.cpp phase1prune.cpp kocsymm.cpp cubepos.cpp -lpthread g++ -DHALF -O4 -Wall -DLEVELCOUNTS -o cubepos_test cubepos_test.cpp cubepos.cpp g++ -DHALF -O4 -Wall -DLEVELCOUNTS -o kocsymm_test kocsymm_test.cpp kocsymm.cpp cubepos.cpp g++ -DHALF -O4 -Wall -DLEVELCOUNTS -o phase2prune_test phase2prune_test.cpp phase2prune.cpp kocsymm.cpp cubepos.cpp g++ -DHALF -O4 -Wall -DLEVELCOUNTS -o phase1prune_test phase1prune_test.cpp phase1prune.cpp kocsymm.cpp cubepos.cpp
はい。 ctangle コマンドで twophase.w 等のCWEBファイルを変換するコマンドが実行されようとしていることがわかります。 .cpp が生成されて g++ で実行バイナリへコンパイルするようです。 実行してみましょう。
$ make
twophase, hcoset, cubepos_test, kocsymm_test, phase1prune_test, phase2prune_test という6個の実行バイナリが無事生成されました。
このうち *_test の名前が付いている4個のバイナリは各機能のテスト用です。
今回はプログラムの詳細までは解説しませんが、twophase と hcoset の使い方は以下のドキュメントに書いてあります。
最後に、生成された Two-Phase ソルバ (twophase) を用いて superflip と呼ばれるすべてのエッジが反転した状態から完成状態への手順を計算してみましょう。
twophase の標準入力にキューブの状態を与えて実行します。
superflip のキューブ状態は次の文字列で表現します:
FU RU BU LU FD RD BD LD RF LF RB LB UFR URB UBL ULF DRF DFL DLB DBR
これをパイプで twophase の標準入力へ与えます。-s 20 オプションは探索の手数を20手で打ち切る命令です。
$ echo "FU RU BU LU FD RD BD LD RF LF RB LB UFR URB UBL ULF DRF DFL DLB DBR" | ./twophase -s 20 This is twophase 1.1, (C) 2010-2012 Tomas Rokicki. All Rights Reserved. Solution 1 len 20 probes 2775964 F1B1U2R1U3D1R2B2L2F1U2R3L3U1B2D1R2U1B2U1 Verified integrity of phase one pruning data: -1939391245 Verified integrity of phase two pruning data: 1084146253 Solved 1 sequences in 1.41001 seconds with 2775964 probes. Completed in 1.41005
整形すると、”F B U2 R U’ D R2 B2 L2 F U2 R’ L’ U B2 D R2 U B2 U” です。 無事計算できました。めでたしめでたし。