CWEBをC/C++に変換する方法 — cube20.orgをコンパイルする

CWEB言語で書かれたドキュメントをctangleとcweaveを用いてC/C++とTeXに変換する方法を説明します。



CWEBとは

CWEB (ctangle, cweave) とは、1980年台に Donald Knuth 氏と Silvio Levy 氏によって開発されたツールです。 CWEBフォーマットで記述された1つのファイルから、 CWEBシステムが「プログラム実行ファイル (の元となるソースコード)」と「ドキュメント (の元となるソースコード)」へ変換します。 ツールは ctanglecweave の2つのプログラムで主に構成されます。 全体フローを以下の図に示します。

cweb-flow

Knuth氏による公式ページです。

現在は積極的に開発はされていないぽくて、CWEBを利用しているプロジェクトもほとんど見かけないと思います。 今回は、ルービックキューブの任意の状態から完成状態までの手数の上限値が20であることを証明した cube20.org というプロジェクトの配布形式がCWEBであったため、 CWEBの導入方法を調査したので共有します。

CWEB環境 (cweave, ctangle) の構築

Windows

以下のサイトから cweb.exe をダウンロードしてください。 これがインストーラとなっています。 インストーラでインストール完了後、ツールの実行バイナリが Program Files のどこかに保存されると共にパスも勝手に通してくれるので インストール直後からコマンドラインでツールが使用可能になると思います。 私は Windows 7 (64bit) で試してみました。

Linux (CentOS)

私の環境は Cent OS 6.7 です。 ソースファイルへはこの記事の冒頭に書いた公式ページに張ってあるリンクからアクセスできます。 具体的には以下のコマンドでインストールすることが可能です (ctanglecweave/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

ctanglecweave のヘルプを表示させてみましょう。 この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.)

cube20.org のコードを実行してみる

さて、CWEBの環境構築が完了しました。

以前書いた記事で紹介したことがあるように cube20.org は「ルービックキューブのGod’s Numberが20手であることを証明するときに使用されたプログラムです」。 God’s Numberが20手であるということは、すなわち、

  1. ルービックキューブの任意の状態から完成状態まで高々20手で到達可能である。
  2. ルービックキューブのある状態から完成状態まで少なくとも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個のバイナリは各機能のテスト用です。
今回はプログラムの詳細までは解説しませんが、twophasehcoset の使い方は以下のドキュメントに書いてあります。

最後に、生成された 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” です。 無事計算できました。めでたしめでたし。

この記事をシェアする:Tweet about this on Twitter
Twitter
Share on Facebook
Facebook
Email this to someone
email