WhitespaceをC言語ソースに変換する

はじめに

WhitespaceとはBrainfuckやLazyKと同じ難解プログラミング言語と言われる言語のひとつである． 難解プログラミング言語はジョーク言語と言われるが，実装の容易さやシンプルな言語仕様を考えると，とても興味深い言語である．

Brainfuckはチューリングマシンに毛がはえた程度の言語であるが，Whitespaceはスタックマシン型の処理系を想定した言語である． そして，スタック操作，算術命令，ヒープ操作，フロー制御，入出力機能を持ち，比較的高い水準でのプログラミングが可能である．

BrainfuckをC言語に変換するという例は世の中にあふれ返っており，変換するコードをいくつも見掛けた． 天下のWikipediaにも変換方法は記述されている．

命令	対応するC言語コード
>	ptr++;
<	ptr--;
+	(*ptr)++;
-	(*ptr)--;
.	putchar(*ptr);
,	*ptr = getchar();
[	while (*ptr) {
]	}

しかし，WhitespaceをC言語に変換するという例は見掛けない． そこで，今回はWhitespaceをいかにC言語に変換するかについて書こうと思う．

Whitespaceの言語仕様

まず，Whitespaceの言語仕様を復習しようと思う． どうも簡単にググって出てきた日本語記事で紹介されているWhitespaceの仕様は少し古いものが多く，公式サイトで紹介されているものと異なっている． （日本語Wikipediaにも古い仕様が書かれている） 例えば，以下のサイトには，古いWhitespaceの仕様を記述していたり，古い仕様の処理系を置いてあったりする．

• Rubyist Magazine - Rubyist のための他言語探訪 【第 14 回】 Whitespace
• ネタ言語のぺぇじ
• Whitespace - Wikipedia
• Hello worldプログラムの一覧 - Wikipedia

以下の表の命令欄には，

• [Space] -> S
• [Tab] -> T
• [改行] -> L

として，Whitespaceのコードを書いてある． VM Code欄には，後半の説明で便宜的に利用するVM命令の名称と考えてもらうとよい． そして，動作欄にはその命令の動作を書いている．

命令	VM Code	動作
SS[NUMBER]	STACK_PUSH	引数に指定された値をスタックにプッシュする（即値のプッシュ）
STS	STACK_DUP_N	スタックの上からn番目をコピーし，スタックの一番上に積む
SLS	STACK_DUP	スタックの上から1番目をコピーし，スタックの一番上に積む
STL	STACK_SLIDE	スタックの上から1番目をキープしつつ，上から2番目から（2 + 引数）番目を捨てる
SLT	STACK_SWAP	スタックの上から1番目と2番目を交換する
SLL	STACK_DISCARD	スタックの上から1番目を捨てる
TSSS	ARITH_ADD	スタックの上から1番目と2番目をポップし，それを加算(2番目 + 1番目)した結果を最上段にプッシュする
TSST	ARITH_SUB	スタックの上から1番目と2番目をポップし，それを減算(2番目 - 1番目)した結果を最上段にプッシュする
TSSL	ARITH_MUL	スタックの上から1番目と2番目をポップし，それを乗算(2番目 * 1番目)した結果を最上段にプッシュする
TSTS	ARITH_DIV	スタックの上から1番目と2番目をポップし，それを除算(2番目 / 1番目)した結果を最上段にプッシュする
TSTT	ARITH_MOD	スタックの上から1番目と2番目をポップし，その剰余(2番目 % 1番目)をとった結果を最上段にプッシュする
TTS	HEAP_STORE	スタックの上から1番目と2番目を取り出し，2番目をヒープのアドレスとし，そこに1番目の値を書き込む（heap[2番目] = 1番目）
TTT	HEAP_LOAD	スタックの上から1番目を取り出し，1番目をヒープのアドレスとし，そのアドレスの値をスタックの最上段にプッシュする（ stack_push(heap[1番目]); ）
LSS[LABEL]		引数に指定されたラベルを定義する
LST[LABEL]	FLOW_GOSUB	引数に指定されたラベルをサブルーチンとして呼び出す（呼び出し位置を記憶してジャンプ）
LSL[LABEL]	FLOW_JUMP	引数に指定されたラベル位置にジャンプする
LTS[LABEL]	FLOW_BEZ	スタックの上から1番目を取り出し，その値が0ならば引数に指定されたラベル位置にジャンプする
LTT[LABEL]	FLOW_BLTZ	スタックの上から1番目を取り出し，その値が0より小さいならば引数に指定されたラベル位置にジャンプする
LTL	FLOW_ENDSUB	サブルーチンの呼び出し元にジャンプする（関数のreturn）
LLL	FLOW_HALT	プログラムを終了する
TLSS	IO_PUT_CHAR	スタックの上から1番目を取り出し，その数値に対応するascii文字を出力
TLST	IO_PUT_NUM	スタックの上から1番目を取り出し，その数値をascii文字として出力
TLTS	IO_READ_CHAR	スタックの上から1番目を取り出し，その値をヒープのアドレスとし，そこに標準入力から1文字読み込む（ heap[1番目] = gethar(); ）
TLTT	IO_READ_NUM	スタックの上から1番目を取り出し，その値をヒープのアドレスとし，そこに標準入力から数値を読み込む（ scanf("%d", &heap[1番目]); ）

上記の表を見てわかるように，命令はスタック操作，算術命令，ヒープ操作，フロー制御，入出力の5種類に大別でき，それぞれの命令毎にプレフィックスが決まっている．

命令の種類	プレフィックス
スタック操作	S
算術命令	TS
ヒープ操作	TT
フロー制御	L
入出力	TL

よく使う命令ほど，少ない文字で済むように文字が割り当てられている．

Whitespace処理系では，後方へのラベルジャンプをサポートする必要があるため，一度コード全体コンパイルをすることによって，ラベルが定義されている位置を知っておかなければならない． （コンパイル時にラベルの定義は処理するので，「ラベルを定義する」というVM命令は必要ない）

Whitespaceにおける「引数」とは，正規表現： [ \t]\+$ にマッチするものと考えておくとよい． 数値はSを0，Tを1とした2進数表記で表現する． 例えば，STTST ならば，2進数： 01101 なので，数値13となる． ラベルはSとTの連続させて表現する．8文字用いて1文字のasciiコードで表現する必要はないが，そのようにしているサンプルコードもある．

Whitespace to C

WhitespaceからC言語に変換するにあたって，サブルーチン呼び出しが問題となった（他の命令については，解説する必要はないだろう）． サブルーチン呼び出し（FLOW_GOSUB）はgoto（FLOW_JUMP）と違い，呼び出し元を記憶し，呼び出し終了時（FLOW_ENDSUB）に，記憶していた呼び出し元に戻る必要がある． つまり，C言語でいうところの関数呼び出しを実現しなければならない．

Brainfuckのループのように，ジャンプ先と戻り位置が1対1で対応しているならば問題はないが，サブルーチンは複数箇所から呼び出されるため，戻り位置の候補が複数あることになる． また，Whitespaceには「サブルーチン定義」という命令はなく，サブルーチン呼び出しは単なる呼び出し位置を記憶したラベルジャンプにすぎない． ジャンプ先のラベルがただのジャンプ命令に利用される可能性もあるし，ラベルより前の処理から継続して，ラベル内の処理に突入する可能性もある． そのため，サブルーチンに対応する関数を定義するという手段も使えない． 以上の理由により，サブルーチン呼び出しを単純な方法でC言語に変換することはできない．

そこで， goto と setjmp() ， longjmp() を用いることにより，サブルーチン呼び出しを実現した． setjmp() は簡単に言うと，呼び出し位置の情報を，引数の jmp_buf 型の変数に保存する関数である． longjmp() は，引数に指定された jmp_buf 位置に戻る． これと goto を組み合わせることで，簡易的なサブルーチン呼び出しが実現できるというわけだ．

具体的には，次のコードのようにC言語コードに変換する．

/* ... */
printf("static jmp_buf call_stack[CALL_STACK_SIZE];\n");
printf("static size_t stack_idx = 0;\n");

/* for (vmcodes : vmcode) { のようなコードでループする */
  switch (vmcode) {
    /* ... */
    case FLOW_GOSUB:
      /* LABEL = read_label(); のような感じでLABELを用意しておく */
      printf(
        "  if (!setjmp(call_stack[call_stack_idx++])) {\n"
        "    goto %s;\n"
        "  }\n", LABEL);
      break;
    case FLOW_ENDSUB:
      printf("  longjmp(call_stack[--call_stack_idx], 1);");
      break;
      /* ... */
  }
/* } */

これでサブルーチン呼び出しを実現できた． ラベルに関しては，SpaceをS，TabをTに置換したラベル名で変換先のC言語コード中に定義する．

SSSTSSTT:

まとめ

WhitespaceからC言語への変換は，サブルーチン呼び出しが鬼門であったが， goto ， setjmp() ， longjmp() を用いることで実現できた．

なお，インタプリタ/C言語へのトランスレータの機能を持つWhitespace処理系は，koturn/Whitespaceに置いてある．

$ make

とすれば簡単にビルドできる． MSVCであっても，

> nmake /f msvc.mk

とすればビルドできるはずだ． そして，以下のように実行すると，WhitespaceからC言語へ変換できる．

$ ./whitespace [Whitespace source file] -t -o out.c

WhitespaceからC言語での変換例

最後に，koturn/Whitespaceを用いた変換例を記載する． このプログラムはWhitespaceのインタプリタ，Whitespaceコードのニーモニック表現，およびC言語ソースへの変換機能を有している． ここで，何となくWhitespaceからC言語への変換のイメージが掴めると思う．

なお，Whitespaceのコードは視認できないので，前述と同じように

• [Space] -> S
• [Tab] -> T

とする． ただし，改行文字はそのまま改行を行う文字とする．

変換元のWhitespaceソースコード

SSSS
SSSTSSTSSS
TTSSSST
SSSTTSSTST
TTSSSSTS
SSSTTSTTSS
TTSSSSTT
SSSTTSTTSS
TTSSSSTSS
SSSTTSTTTT
TTSSSSTST
SSSTSTTSS
TTSSSSTTS
SSSTSSSSS
TTSSSSTTT
SSSTTTSTTT
TTSSSSTSSS
SSSTTSTTTT
TTSSSSTSST
SSSTTTSSTS
TTSSSSTSTS
SSSTTSTTSS
TTSSSSTSTT
SSSTTSSTSS
TTSSSSTTSS
SSSTSSSSS
TTSSSSTTST
SSSTTSTTTT
TTSSSSTTTS
SSSTTSSTTS
TTSSSSTTTT
SSSTSSSSS
TTSSSSTSSSS
SSSTTTSSTT
TTSSSSTSSST
SSSTTTSSSS
TTSSSSTSSTS
SSSTTSSSST
TTSSSSTSSTT
SSSTTSSSTT
TTSSSSTSTSS
SSSTTSSTST
TTSSSSTSTST
SSSTTTSSTT
TTSSSSTSTTS
SSSTSSSST
TTSSSSTSTTT
SSSS
TTSSSSS

STSTTTSTTTSTTTSSTSSTTSTSSTSTTTSTSSSTTSSTST

STSTTSTTTSSTTSSTSTSTTTSTTTSTTSTTSSSTTSTSSTSTTSTTTSSTTSSTST




SSSTTSSSSTSTTSSTSSSTTSSTSS
TSSS
T

SSSTTTSTTTSTTTSSTSSTTSTSSTSTTTSTSSSTTSSTST
S
STTTS
S
TSSTTTSTTTSTTTSSTSSTTSTSSTSTTTSTSSSTTSSTSTSTSTTTTTSTTSSTSTSTTSTTTSSTTSSTSS
T
SSSSST
TSSS
S
STTTSTTTSTTTSSTSSTTSTSSTSTTTSTSSSTTSSTST

SSSTTTSTTTSTTTSSTSSTTSTSSTSTTTSTSSSTTSSTSTSTSTTTTTSTTSSTSTSTTSTTTSSTTSSTSS
S

S


T

SSSTTTSSTSSTTSSTSTSTTSSSSTSTTSSTSS
S
SS
ST
TSTTTS
SSSSTSTS
TSST
TSSTTTSSTSSTTSSTSTSTTSSSSTSTTSSTSSSTSTTTTTSTTSSTSTSTTSTTTSSTTSSTSS
S

SSST
TSSS
S
STTTSSTSSTTSSTSTSTTSSSSTSTTSSTSS

SSSTTTSSTSSTTSSTSTSTTSSSSTSTTSSTSSSTSTTTTTSTTSSTSTSTTSTTTSSTTSSTSS
S

SSST
TSSSSSSS
TTS
T

SSSTTSTTTSSTTSSTSTSTTTSTTTSTTSTTSSSTTSTSSTSTTSTTTSSTTSSTST
SSSTSTS
SSSTTST
T
SST
SS
T

• 実行例

$ ./whitespace.out hworld.ws
Hello, world of spaces!

ニーモニック表現

上記Whitespaceコードを擬似的なVM命令のニーモニック表現で表現したものである． C言語への変換に用いるわけではないが，イメージを掴む助けになるだろう． なお，ジャンプは絶対アドレス指定である．

0000: STACK_PUSH 0
0005: STACK_PUSH 72
0010: HEAP_STORE
0011: STACK_PUSH 1
0016: STACK_PUSH 101
0021: HEAP_STORE
0022: STACK_PUSH 2
0027: STACK_PUSH 108
0032: HEAP_STORE
0033: STACK_PUSH 3
0038: STACK_PUSH 108
0043: HEAP_STORE
0044: STACK_PUSH 4
0049: STACK_PUSH 111
0054: HEAP_STORE
0055: STACK_PUSH 5
0060: STACK_PUSH 44
0065: HEAP_STORE
0066: STACK_PUSH 6
0071: STACK_PUSH 32
0076: HEAP_STORE
0077: STACK_PUSH 7
0082: STACK_PUSH 119
0087: HEAP_STORE
0088: STACK_PUSH 8
0093: STACK_PUSH 111
0098: HEAP_STORE
0099: STACK_PUSH 9
0104: STACK_PUSH 114
0109: HEAP_STORE
0110: STACK_PUSH 10
0115: STACK_PUSH 108
0120: HEAP_STORE
0121: STACK_PUSH 11
0126: STACK_PUSH 100
0131: HEAP_STORE
0132: STACK_PUSH 12
0137: STACK_PUSH 32
0142: HEAP_STORE
0143: STACK_PUSH 13
0148: STACK_PUSH 111
0153: HEAP_STORE
0154: STACK_PUSH 14
0159: STACK_PUSH 102
0164: HEAP_STORE
0165: STACK_PUSH 15
0170: STACK_PUSH 32
0175: HEAP_STORE
0176: STACK_PUSH 16
0181: STACK_PUSH 115
0186: HEAP_STORE
0187: STACK_PUSH 17
0192: STACK_PUSH 112
0197: HEAP_STORE
0198: STACK_PUSH 18
0203: STACK_PUSH 97
0208: HEAP_STORE
0209: STACK_PUSH 19
0214: STACK_PUSH 99
0219: HEAP_STORE
0220: STACK_PUSH 20
0225: STACK_PUSH 101
0230: HEAP_STORE
0231: STACK_PUSH 21
0236: STACK_PUSH 115
0241: HEAP_STORE
0242: STACK_PUSH 22
0247: STACK_PUSH 33
0252: HEAP_STORE
0253: STACK_PUSH 23
0258: STACK_PUSH 0
0263: HEAP_STORE
0264: STACK_PUSH 0
0269: FLOW_GOSUB 282
0274: FLOW_GOSUB 367
0279: FLOW_HALT
0280: ARITH_ADD
0281: FLOW_ENDSUB
0282: STACK_DUP_N 0
0287: HEAP_LOAD
0288: STACK_DUP_N 0
0293: FLOW_BEZ 310
0298: IO_PUT_CHAR
0299: STACK_PUSH 1
0304: ARITH_ADD
0305: FLOW_JUMP 282
0310: STACK_POP
0311: STACK_POP
0312: FLOW_ENDSUB
0313: STACK_DUP_N 0
0318: STACK_DUP_N 0
0323: IO_READ_CHAR
0324: HEAP_LOAD
0325: STACK_DUP_N 0
0330: STACK_PUSH 10
0335: ARITH_SUB
0336: FLOW_BEZ 353
0341: STACK_POP
0342: STACK_PUSH 1
0347: ARITH_ADD
0348: FLOW_JUMP 313
0353: STACK_POP
0354: STACK_PUSH 1
0359: ARITH_ADD
0360: STACK_PUSH 0
0365: HEAP_STORE
0366: FLOW_ENDSUB
0367: STACK_PUSH 10
0372: STACK_PUSH 13
0377: IO_PUT_CHAR
0378: IO_PUT_CHAR
0379: FLOW_ENDSUB

変換後のC言語ソースコード

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

#ifndef __cplusplus
#  if defined(_MSC_VER)
#    define inline      __inline
#    define __inline__  __inline
#  elif !defined(__GNUC__) && (!defined(__STDC_VERSION__) || __STDC_VERSION__ < 199901L)
#    define inline
#    define __inline
#  endif
#endif

#define STACK_SIZE 65536
#define HEAP_SIZE 65536
#define CALL_STACK_SIZE 65536

#define LENGTHOF(array) (sizeof(array) / sizeof((array)[0]))
#define SWAP(type, a, b) \
  do { \
    type __tmp_swap_var__ = *(a); \
    *(a) = *(b); \
    *(b) = __tmp_swap_var__; \
  } while (0)

inline static int  pop(void);
inline static void push(int e);
inline static void dup_n(size_t n);
inline static void slide(size_t n);
inline static void swap(void);
inline static void arith_add(void);
inline static void arith_sub(void);
inline static void arith_mul(void);
inline static void arith_div(void);
inline static void arith_mod(void);
inline static void heap_store(void);
inline static void heap_read(void);

static int stack[STACK_SIZE];
static int heap[HEAP_SIZE];
static jmp_buf call_stack[CALL_STACK_SIZE];
static size_t stack_idx = 0;
static size_t call_stack_idx = 0;


int main(void)
{
  push(0);
  push(72);
  heap_store();
  push(1);
  push(101);
  heap_store();
  push(2);
  push(108);
  heap_store();
  push(3);
  push(108);
  heap_store();
  push(4);
  push(111);
  heap_store();
  push(5);
  push(44);
  heap_store();
  push(6);
  push(32);
  heap_store();
  push(7);
  push(119);
  heap_store();
  push(8);
  push(111);
  heap_store();
  push(9);
  push(114);
  heap_store();
  push(10);
  push(108);
  heap_store();
  push(11);
  push(100);
  heap_store();
  push(12);
  push(32);
  heap_store();
  push(13);
  push(111);
  heap_store();
  push(14);
  push(102);
  heap_store();
  push(15);
  push(32);
  heap_store();
  push(16);
  push(115);
  heap_store();
  push(17);
  push(112);
  heap_store();
  push(18);
  push(97);
  heap_store();
  push(19);
  push(99);
  heap_store();
  push(20);
  push(101);
  heap_store();
  push(21);
  push(115);
  heap_store();
  push(22);
  push(33);
  heap_store();
  push(23);
  push(0);
  heap_store();
  push(0);
  if (!setjmp(call_stack[call_stack_idx++])) {
    goto STTTSTTTSTTTSSTSSTTSTSSTSTTTSTSSSTTSSTST;
  }
  if (!setjmp(call_stack[call_stack_idx++])) {
    goto STTSTTTSSTTSSTSTSTTTSTTTSTTSTTSSSTTSTSSTSTTSTTTSSTTSSTST;
  }
  exit(EXIT_SUCCESS);

STTSSSSTSTTSSTSSSTTSSTSS:
  arith_add();
  longjmp(call_stack[--call_stack_idx], 1);

STTTSTTTSTTTSSTSSTTSTSSTSTTTSTSSSTTSSTST:
  dup_n(0);
  heap_read();
  dup_n(0);
  if (!pop()) {
    goto STTTSTTTSTTTSSTSSTTSTSSTSTTTSTSSSTTSSTSTSTSTTTTTSTTSSTSTSTTSTTTSSTTSSTSS;
  }
  putchar(pop());
  push(1);
  arith_add();
  goto STTTSTTTSTTTSSTSSTTSTSSTSTTTSTSSSTTSSTST;

STTTSTTTSTTTSSTSSTTSTSSTSTTTSTSSSTTSSTSTSTSTTTTTSTTSSTSTSTTSTTTSSTTSSTSS:
  pop();
  pop();
  longjmp(call_stack[--call_stack_idx], 1);

STTTSSTSSTTSSTSTSTTSSSSTSTTSSTSS:
  dup_n(0);
  dup_n(0);
  heap[pop()] = getchar();
  heap_read();
  dup_n(0);
  push(10);
  arith_sub();
  if (!pop()) {
    goto STTTSSTSSTTSSTSTSTTSSSSTSTTSSTSSSTSTTTTTSTTSSTSTSTTSTTTSSTTSSTSS;
  }
  pop();
  push(1);
  arith_add();
  goto STTTSSTSSTTSSTSTSTTSSSSTSTTSSTSS;

STTTSSTSSTTSSTSTSTTSSSSTSTTSSTSSSTSTTTTTSTTSSTSTSTTSTTTSSTTSSTSS:
  pop();
  push(1);
  arith_add();
  push(0);
  heap_store();
  longjmp(call_stack[--call_stack_idx], 1);

STTSTTTSSTTSSTSTSTTTSTTTSTTSTTSSSTTSTSSTSTTSTTTSSTTSSTST:
  push(10);
  push(13);
  putchar(pop());
  putchar(pop());
  longjmp(call_stack[--call_stack_idx], 1);

  return EXIT_SUCCESS;
}


inline static int pop(void)
{
  assert(stack_idx < LENGTHOF(stack));
  return stack[--stack_idx];
}


inline static void push(int e)
{
  assert(stack_idx < LENGTHOF(stack));
  stack[stack_idx++] = e;
}


inline static void dup_n(size_t n)
{
  assert(n < stack_idx && stack_idx < LENGTHOF(stack) - 1);
  stack[stack_idx] = stack[stack_idx - (n + 1)];
  stack_idx++;
}


inline static void slide(size_t n)
{
  assert(stack_idx > n);
  stack[stack_idx - (n + 1)] = stack[stack_idx - 1];
  stack_idx -= n;
}


inline static void swap(void)
{
  assert(stack_idx > 1);
  SWAP(int, &stack[stack_idx - 1], &stack[stack_idx - 2]);
}


inline static void arith_add(void)
{
  assert(stack_idx > 1);
  stack_idx--;
  stack[stack_idx - 1] += stack[stack_idx];
}


inline static void arith_sub(void)
{
  assert(stack_idx > 1);
  stack_idx--;
  stack[stack_idx - 1] -= stack[stack_idx];
}


inline static void arith_mul(void)
{
  assert(stack_idx > 1);
  stack_idx--;
  stack[stack_idx - 1] *= stack[stack_idx];
}


inline static void arith_div(void)
{
  assert(stack_idx > 1);
  stack_idx--;
  assert(stack[stack_idx] != 0);
  stack[stack_idx - 1] /= stack[stack_idx];
}


inline static void arith_mod(void)
{
  assert(stack_idx > 1);
  stack_idx--;
  assert(stack[stack_idx] != 0);
  stack[stack_idx - 1] %= stack[stack_idx];
}


inline static void heap_store(void)
{
  int value = pop();
  int addr  = pop();
  assert(0 <= addr && addr < (int) LENGTHOF(heap));
  heap[addr] = value;
}


inline static void heap_read(void)
{
  int addr = pop();
  assert(0 <= addr && addr < (int) LENGTHOF(heap));
  push(heap[addr]);
}

• 変換 & コンパイル & 実行例

$ ./whitespace.out hworld.ws -t -o hworld.c
$ gcc -Ofast -march=native -DNDEBUG hworld.c -o hworld.out
$ ./hworld.out
Hello, world of spaces!

Wandboxでの実行結果はこちら

参考

• 公式サイト
• 公式サイトのクローン？
• White space - Wikipedia, the free encyclopedia