205行ではありません。205文字です。
... この記事は早稲田大学 Advent Calendar 2016 11日目の記事です。(続投失礼します)
今回は、コマンドラインで使える簡易計算機を作ってみました。以下のように動作します。
> echo "3+2*4+6*7/2" | ./a.out
32
プログラム
それでは、このC言語のソースコードをお見せしましょう。
a,b,c,i,j,k;r(){a=getchar();}g(){for(k=0;47<a&&a<58;r())k=k*10+a-48;}t(){for(g(),j=k;a==42||a==47;g(),
j=b-47?j*k:j/k)b=a,r();}main(){r();for(t(),i=j;a==43||a==45;i+=c-45?j:-j)c=a,r(),t();printf("%d\n",i);}
(見やすいように適当に改行を入れています。gcc 6.2.1で確認済み)
コードを短くしていった過程
驚くべきことに、上記の(#include さえ存在しない)コードはgccで正しくコンパイルできます。このような短いプログラムに至った過程を述べます。
その1. 最初のコード
#include <stdio.h>
int a;
int get_number(void){
int i = 0;
while ('0' <= a && a <= '9') {
i = i * 10 + a - '0';
a = getchar();
}
return i;
}
int term(void) {
int i = get_number();
while(a == '*' || a == '/') {
if (a == '*') {
a = getchar();
i = i * get_number();
} else if (a == '/') {
a = getchar();
i = i / get_number();
}
}
return i;
}
int expression(void) {
int i = term();
while(a == '+' || a == '-') {
if (a == '+') {
a = getchar();
i = i + term();
} else if (a == '-') {
a = getchar();
i = i - term();
}
}
return i;
}
int main(void) {
a = getchar();
printf("%d\n", expression());
}
これが、私がこのプログラムを書くに当たって最初に書いたコードです。
C言語の標準関数としてgetchar()及びprintf()関数を使用しているシンプルなものです。ただし、この時点ではまだ644文字(42行)あります。
簡単に説明しておくと、expression()では式全体、term()では掛け算及び割り算、get_number()では整数リテラルの読み込みを行っています。詳しく知りたい方は「再帰下降パーサ」等のワードで調べていただきたいとおもいます。
その2. get_number()を短くする。
int get_number(void){
int i = 0;
while ('0' <= a && a <= '9') {
i = i * 10 + a - '0';
a = getchar();
}
return i;
}
このコードを短くしていきます。
まず、while文をfor文に置き換えます。下の例を見てください。
while(条件式){ ... }
for(;条件式;}{ ... }
この例では、while文とfor文は等価です。しかし、文字数も同じであり、短くなる効果はまだありません。
for文に置き換えることの利点は、前後の文をfor文の中に取り込めることです。では具体的にやってみましょう。
int get_number(void){
for (int i = 0; '0' <= a && a <= '9'; a = getchar()) {
i = i * 10 + a - '0';
}
return i;
}
for文にint i = 0;とa = getchar()を取り込むことで、セミコロン2つ分文字数を節約出来ています。
と同時に、for文の複合分({〜})を省略できるようになったので、それもやってみます。
int get_number(void){
for (int i = 0; '0' <= a && a <= '9'; a = getchar())
i = i * 10 + a - '0';
return i;
}
さらに、文字定数を文字コードに変換すると、'0' <= a && a <= '9'の部分を48 <= a && a <= 57とできます。この形だと、加えて<=を<に変換できて、47 < a && a < 58となります。以上を適用すると以下のようになります。
int get_number(void){
for (int i = 0; 47 < a && a < 58; a = getchar())
i = i * 10 + a - 48;
return i;
}
その3. term()を短くする
int term(void) {
int i = get_number();
while(a == '*' || a == '/') {
if (a == '*') {
a = getchar();
i = i * get_number();
} else if (a == '/') {
a = getchar();
i = i / get_number();
}
}
return i;
}
このプログラムでは、ループ内でまずaの文字種判定を行い、aに次の文字を代入し、その後get_number()を実行します。これらの処理は同じ処理が複数行に書かれているため冗長に思えますが、かならずこの順番で実行しなければなりません。そこで工夫をします。まず文字種判定の処理を移動させるために、変数bを用意してa=getchar();する前のaの値を保存しておくようにします。これで文字種判定の位置をa = getchar();の後に持ってこられるようになり、a = getchar()を2箇所に書かなくても良くなります。これで下のようにできます。
int term(void) {
int i = get_number(), b;
while(a == '*' || a == '/') {
b = a;
a = getchar();
if (a == '*') {
i = i * get_number();
} else if (a == '/') {
i = i / get_number();
}
}
return i;
}
さらに、if文を三項演算子で置き換えます。
int term(void) {
int i = get_number(), b;
while(a == '*' || a == '/') {
b = a;
a = getchar();
i = b == '*' ? i * get_number() : i / get_number();
}
return i;
}
この後、先ほどと同様に文字定数を文字コードに変換し、while文をfor文に置換し、複合文を省略すると以下のようになります。
int term(void) {
int b;
for (int i = get_number(); a == 42 || a == 47; i = b == '*' ? i * get_number() : i / get_number())
b = a, a = getchar();
return i;
}
途中、複合文を省略するためにカンマ演算子を用いています。
その4. expression()とmain()を短くする
int expression(void) {
int i = term();
while(a == '+' || a == '-') {
if (a == '+') {
a = getchar();
i = i + term();
} else if (a == '-') {
a = getchar();
i = i - term();
}
}
return i;
}
int main(void) {
a = getchar();
printf("%d\n", expression());
}
まず、expression()はmain()から1度しか呼ばれていません。よって、expression()をmain()に統合します。
int main(void) {
a = getchar();
int i = term();
while(a == '+' || a == '-') {
if (a == '+') {
a = getchar();
i = i + term();
} else if (a == '-') {
a = getchar();
i = i - term();
}
}
printf("%d\n", i);
}
term()の時と同様に、ループの部分を短くします。
int main(void) {
a = getchar();
int b;
for(int i = term(); a == 43 || a == 45; i += b != 45 ? term() : -term())
b = a, a = getchar();
printf("%d\n", i);
}
ここで、b != 45 は b - 45と等価なので変換します。
int main(void) {
a = getchar();
int b;
for(int i = term(); a == 43 || a == 45; i += b - 45 ? term() : -term())
b = a, a = getchar();
printf("%d\n", i);
}
ここまでのまとめ
ここまで短くしてきたコードをまとめると以下のようになります。
#include <stdio.h>
int a;
int get_number(void){
for (int i = 0; 47 < a && a < 58; a = getchar())
i = i * 10 + a - 48;
return i;
}
int term(void) {
int b;
for (int i = get_number(); a == 42 || a == 47; i = b == '*' ? i * get_number() : i / get_number())
b = a, a = getchar();
return i;
}
int main(void) {
a = getchar();
int b;
for(int i = term(); a == 43 || a == 45; i += b - 45 ? term() : -term())
b = a, a = getchar();
printf("%d\n", i);
}
心なしか短くなったような気がしますね。この段階で469文字です。
では、続けていきましょう。
その5. 変数をグローバル名前空間で宣言する
まず、今ローカル名前空間で宣言している変数をグローバル名前空間に移します。
こうすることで、毎回intと書く必要がなくなるので、一定の文字削減効果がありそうです。
また、その際各関数で使われている変数名が同じ場合に被ってしまうため、適宜変更します。
#include <stdio.h>
int a, b, c, i, j, k;
int get_number(void){
for (k = 0; 47 < a && a < 58; a = getchar())
k = k * 10 + a - 48;
return k;
}
int term(void) {
for (j = get_number(); a == 42 || a == 47; j = b == '*' ? j * get_number() : j / get_number())
b = a, a = getchar();
return j;
}
int main(void) {
a = getchar();
for(i = term(); a == 43 || a == 45; i += c - 45 ? term() : -term())
c = a, a = getchar();
printf("%d\n", i);
}
その6. 関数名を短くする
term(), get_number()等の関数名が長ったらしいですね。折角なので1文字にしてしまいましょう。
#include <stdio.h>
int a, b, c, i, j, k;
int g(void){
for (k = 0; 47 < a && a < 58; a = getchar())
k = k * 10 + a - 48;
return k;
}
int t(void) {
for (j = g(); a == 42 || a == 47; j = b == '*' ? j * g() : j / g())
b = a, a = getchar();
return j;
}
int main(void) {
a = getchar();
for(i = t(); a == 43 || a == 45; i += c - 45 ? t() : -t())
c = a, a = getchar();
printf("%d\n", i);
}
さて、ソースコードを遠目で見てみましょう。何か邪魔なものはないでしょうか? そうです、getchar()とreturnが邪魔ですね。では、これらを取り払ってみましょう。
その7. getchar()の省略
getchar()という名前の関数が多くの場所から呼ばれていますね。これらを短くできればかなりの文字削減効果が見込めるでしょう。
#include <stdio.h>
int a, b, c, i, j, k;
void r(void) {
a = getchar();
}
int g(void){
for (k = 0; 47 < a && a < 58; r())
k = k * 10 + a - 48;
return k;
}
int t(void) {
for (j = g(); a == 42 || a == 47; j = b == '*' ? j * g() : j / g())
b = a, r();
return j;
}
int main(void) {
r();
for(i = t(); a == 43 || a == 45; i += c - 45 ? t() : -t())
c = a, r();
printf("%d\n", i);
}
その8. return文の省略
「その5. 変数をグローバル名前空間で宣言する」で、ローカル変数をすべてグローバル変数に出しました。
これによって、関数が内部で扱っている変数にどこからでもアクセスできるようになりました。例えば、ある関数を呼び出して、その関数が内部で書き込んだ値を呼び出し元の関数が参照することができるわけです。
このテクニックを使えば、return文を省略できそうですね。では、実際にやってみましょう。
#include <stdio.h>
int a, b, c, i, j, k;
void r(void) {
a = getchar();
}
int g(void){
for (k = 0; 47 < a && a < 58; r())
k = k * 10 + a - 48;
}
int t(void) {
for (g(), j=k; a == 42 || a == 47; g(), j = b == '*' ? j * k : j / k)
b = a, r();
}
int main(void) {
r();
for(t(), i = j; a == 43 || a == 45; i += c - 45 ? j : -j)
c = a, r(), t();
printf("%d\n", i);
}
return文の省略に従って、関数呼び出し部が変更されています。例えば、j=g()が、g(),j=kになっています。
その9. 規格を逸脱したテクニック
さて、このあたりからセコいテクニックを繰り出していこうと思います。
C99では、main()関数の戻り値の型を省略するとintであると見なされます。またmain()関数内でreturn文を省略するとreturn 0;したものとみなされます。
さらに、手元のgccではそれ以外の関数の型名も省略できるようです。(警告は表示されます。)その場合も、returnがなくても大丈夫なようです。
また、関数の仮引数のvoidは規格上は必要ですが、これも省略しても動作します。
#include <stdio.h>
int a, b, c, i, j, k;
r() {
a = getchar();
}
g(){
for (k = 0; 47 < a && a < 58; r())
k = k * 10 + a - 48;
}
t() {
for (g(), j=k; a == 42 || a == 47; g(), j = b == '*' ? j * k : j / k)
b = a, r();
}
main() {
r();
for(t(), i = j; a == 43 || a == 45; i += c - 45 ? j : -j)
c = a, r(), t();
printf("%d\n", i);
}
gccでは、基本的な標準関数のみを利用するときには#include <stdio.h> を書かなくてもコンパイルできます。
さらに、グローバル名前空間で宣言しているint型の変数についても、型名を省略できます。これらを適用すると以下のようになります。
a, b, c, i, j, k;
r() {
a = getchar();
}
g(){
for (k = 0; 47 < a && a < 58; r())
k = k * 10 + a - 48;
}
t() {
for (g(), j=k; a == 42 || a == 47; g(), j = b == '*' ? j * k : j / k)
b = a, r();
}
main() {
r();
for(t(), i = j; a == 43 || a == 45; i += c - 45 ? j : -j)
c = a, r(), t();
printf("%d\n", i);
}
これでスペース及び改行を削除すると、冒頭で示したコードが出来上がります。
a,b,c,i,j,k;r(){a=getchar();}g(){for(k=0;47<a&&a<58;r())k=k*10+a-48;}t(){for(g(),j=k;a==42||a==47;g(),
j=b-47?j*k:j/k)b=a,r();}main(){r();for(t(),i=j;a==43||a==45;i+=c-45?j:-j)c=a,r(),t();printf("%d\n",i);}
最後に
いかがだったでしょうか。本稿で筆者が示したかったことは2つあります。
- 学校の授業(教養的なもの)で敬遠されがちな再帰下降パーサ(?)がたったの205行で書ける
- ショートコーディングは楽しい
--
1. について。今回作成したプログラムが再帰下降パーサである、という点についてはツッコミどころがたくさんあるでしょう。例えば、変数をすべてグローバルに出してしまったことにより、同じ関数が再帰的に呼ばれる(expression()->term()->expression()など)ような状況には対応できません。よって、例えばこのままでは括弧「()」を含む式には対応できません。しかし、基本的な部分についてはある程度抑えられているのではないか、と思うのです。ショートコーディングした結果205文字におさまるようなプログラムであれば、初心者が1から考えてプログラミングすることも可能なのではないでしょうか。(もちろんショートコーディングまで学生がする必要はないとは思いますが。)
2. について。はっきり言ってショートコーディングはほとんど役に立ちません。バイナリを小さくすることやアルゴリズムの改善によって処理の効率を上げるようなことは現実に役に立つと思いますが、ソースコードが短くなったところで読みにくくなるだけで、それ以上の効果はありません。しかし、ソースコードの文字数というのは数字で計算されるはっきりとした値であり、明確な目標を定めることや(筆者は200文字という目標を設定していましたが達成できませんでした)、問題をきちんと設定すれば友人同士で競い合うことが出来ます。実際にやってみると結構ハマりますし、C言語についての知識もそれなりに身につきます。Anarchy Golfのようなウェブサイトもあるので、世界に挑むこともできます。気になる方は、ぜひチャレンジしてみてください。