2020年06月23日

LLVM frontend tutorial Kaleidoscopeのビルドを始めるまでにした苦労

見に来ている人がLLVMとは...なんて話題には多分興味無いと思うので飛ばすとして、かなり頑張っているプロジェクトであるLLVMにはチュートリアルが複数ある。
今回その中のフロントエンド用のチュートリアル Kaleidoscopeを研究室の輪講としてやることになった。
なおAgdaの本をやっていたのはもう終わった。早かった。

LLVMのチュートリアルのページを見るとOCaml版とC++版がある。
しかしLLVMのリポジトリを見たら分かるとおり、OCaml版は本当に長く放置されていて、APIは古すぎてちゃんと新しいのを探さないといけないし、camlp4だし、ところどころ引っかかるみたいだし、そもそもObjective Camlだし...(頑張った方もいらしたようだ)
一方C++は2018年に何かで使ったらしく、修正が入っている。これはありがたい。

ソースコードは全て公開されているので、輪講としては若干気になるものの、絶対に環境に依存するから、事前に動かせるのがありがたい。
と思ったけどそれでも苦労するんだなぁ...

ビルドで困った人の助けになればと書いておく。

Ubuntu編


こちらは二転三転するのだが、結論を言うとリンカーにオプションを渡さないといけない。

aptでLLVMを入れてソースコードを持ってくると簡単にコンパイルできる。さすがUbuntu。優秀。
さくっとMakefile書いて、テスト用に(というにはおこがましいが)チュートリアルに書かれている例題を持ってきて、実行。そしてコケる。

Symbols not found - [ printd ]

そりゃないよ〜

Chapter 4から、JITを使ってシンボル解決をして外部関数を呼び出すということをするのだが、よくある数学関数(sinやcos)は普通に呼べるのに、処理系のソースコード内で定義している関数(putchardとかprintdとかいう名前)が呼べない。
チュートリアルでは何事もなかったように呼べている。いやいや呼べないんだけど。シンボル見つからないって文句言われるんだけど。

最初の解決策


どうやら共有ライブラリの関数は呼べているようなので、呼びたい関数を共有ライブラリ(.so)にして実行時にロードしてもらえばどうか、と試したところうまくいった。
うまくいったけど実行が面倒なんですがこれ...(実行時にいちいち LD_LIBRARY_PATH=. ./toy みたいに書いている)

別の解決策


JITのバグを疑っていて考えなかったけれど、そもそもこの関数シンボルテーブルにあるの?と思い立ってobjdumpで見てみる。
...前にオプションで二つのシンボルテーブルがあることを知った。

  • -tで見られるシンボルテーブル。聞き覚え有り。

  • -Tで見られる動的シンボルテーブル。聞き覚え無し。


人に聞いたらELF(linuxでよく使うバイナリフォーマット)にはあるらしい。動的シンボルテーブルの内容は動的リンク時などに使うテーブルなのだとか。
で、どうやらLLVMのJITがこっちを見ているようだ。printdやらputchardはシンボルテーブルにはあったけど動的シンボルテーブルにはなかった。なるほど動的リンクとJITだから確かに結びつく。
どうせリンカーに何かオプションがあるに違いないと思って調べたところ、--export-dynamicというフラグを見つけたので、clang++越しに渡すことにした。
clang++ -Xlinker --export-dynamic -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core mcjit native` -O3 -o toy

みたいにコンパイルする。
最終的にこれで無事動いた。

Mac編


端的に言うとllvm-configが出す情報がなんか不完全らしく、--libsの先をallにしたら足りた。あとリンカーのバージョンを下げるオプション-mlinker-version=450もつけたら動いた。

これ学生が見つけた話だからここに詳細を書いても仕方ない気がする。
こっちのビルド時のコマンドはこんな感じ。
clang++ -mlinker-version=450 -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs all` -O3 -o toy

Ubuntuの時に使ったオプションは多分使えない。
あとlibsの指定でallを書くのはUbuntuでも有効。記述量減るので使った。頑張れclang。

なんとか無事輪講を開始できそうである。
posted by chiguri at 16:24| Comment(0) | 講義

2010年01月21日

さあ、久しぶりの長文:C言語超入門(?)第・・・6.5回?

かれこれ半年以上ぶりの更新。

というわけで、直接次の話を進めるのではなく、簡単な復習をしてみよう。

現時点でもかなりの量になっているため、今回もやはり長文になると思われる。

それでは、いつもの順に進めよう。やや題は異なるけれど。


復習概要

  1. プログラムは、指示の列である。当然最初があって、次があって、・・・と続く。
  2. C言語では「指示の開始地点」はmain関数と呼ばれる関数である。
  3. 関数は、名前のついた「指示の集まり」である。集まりとして記述するのだから、使うこともできる。
  4. 関数には「返り値」がある。関数を使った場所におかれる値で、関数の中でreturnを使って記述する。関数を作るときに、関数名の前にあるものが返り値の「型」(種類)である。
  5. 関数には「引数」があることもある。ないこともある。複数ある場合コンマで続ける。
  6. 関数の使い方には、そもそもC言語で書ける範囲を超えたものを書く、というものもある。たとえば画面に文字を出力するには、関数を使うしかない*1
  7. 関数の中で自分を呼ぶことを「再帰」と呼ぶ。これで同じような処理を繰り返すことができる。
  8. ある条件で実行する指示が分かれることを条件分岐という。ここではifという語で条件分岐を作った。


・・・こんなものだろうか?かなりつめて説明しているので、これだけ読んでも何のことかわからない気がする。

簡単なmain関数

int main() { return 0; }

第一回から出てきた、何もしない関数。

指示はただ一つ、return 0というものだけ。main関数の結果として、0という数字を返すことを表している。

main関数はint(整数)の要素を返す、と書いてある(1行目)。0は当然整数なので問題なし。

このmain関数は始まったら即座に結果0を返して終了する。プログラムはmain関数から始まり、main関数が終わると終了する。したがってこのプログラムは始まったら即座に終了する。

ちなみに、main関数の結果として0を返すのは「問題なく終了した」ことを表す*2。ただし、絶対ではない。1を返しても別に問題ないことが多い。

関数の呼び出し

int putchar(char c);

char f(char c) { return c; }

int main() { putchar(f('a')); return 0; }

上のプログラムを動かすと、画面にアルファベットのaが表示されて終了する。

流れは次のようになる。

  1. main関数が始まる。
  2. putchar関数の「引数」である関数f*3を実行する*4
  3. fは引数として文字a('a')を受け取る。そしてそのまま返す。よってf関数を呼び出した箇所は文字aと同じ扱いになる。
  4. putchar関数が呼び出される。実体はプログラムに書かれていないが、内容は決まっていて、文字を表示するものである。
  5. 文字を出したら終了する。

ちなみに、1行目のint putchar(char c)は「putchar関数が引数として文字を1つとり、intを返す関数である」ことを表している。実体は書けないので関数の「宣言」だけである。

再帰単独

int f() { return f(); }

int main() { f(); return 0; }

上のプログラムは「終わらないプログラム」である。以上。

流れは次のとおり。

  1. main関数が始まる。
  2. 関数fを実行する。
  3. 関数fの中で関数fを実行する。
  4. 次の関数fの中で関数fを実行する。
  5. 以下無限に同じ文章。

ただし、このプログラムを実行すると多くのパソコン(+コンパイラ、処理系、コードをコンピュータの実行可能なファイルに変換するもの)では「エラーを出力して終了する」ことになる。

実際のところは、関数を実行するときには「いくつかの情報」を保存しなければならず、それが無限に増えていくためいつか保存しきれなくなって終了する、というのが現実。

「いくつかの情報」とは、たとえばその関数の中でだけ使える変数や引数(戻ってきた後実行を続けるのに必要)、関数を呼び出した場所(戻ってくるときに必要)といったところ*5

条件分岐+include

#include<stdio.h>

int main() {

 if(1 < 2) { puts("YES!"); }

 else { puts("What?"); }

 return 0;

}

上のプログラムは条件分岐を使ったもの。

1行目はstdio.hというファイルを読み込む命令。このファイルにはputchar関数の宣言のほかにもputs関数という関数の宣言なども入っている。

流れは以下のとおり。

  1. main関数が始まる。
  2. ifという語で条件分岐が行われる。1 < 2か?という当然正しいことを条件としている。
  3. 条件が正しいので直後にある命令を実行する。内容はputs関数をYES!という「文字列」を引数にして呼び出す、というもの。
  4. puts関数が実行され、引数であるYES!という文字列が画面に表示される。
  5. elseというのはifの条件が正しくない場合に実行されるものなので、今回の場合その直後の命令は無視する。
  6. 0を返してmain関数が終了する。

以上である。なお、elseのほうは省略してもよい。省略した場合、ifの条件が正しくなかったら何もしない。

まとめ

概要をご覧ください(笑)。

復習のためにある程度のコードを見せ、その説明をした。

次回予告

「繰り返し」について今度こそ説明する。

簡単に言えば、「条件が正しい限り何度も実行する」もの。

3種類ほどあるのだが、この解説では1つしか説明する気はない。

最後に

この方式は変わりそうもないので、あきらめて最後まで書いて、そこから修正するか。

いっそ全体を説明することにすると、残りは組み込み型残り、gotoとラベル、条件分岐や繰り返しの残り、ポインター、構造体と共用体、型の修飾子や別名宣言、マクロなど。

うーん・・・あと10回くらい?

*1:C言語の仕様だけでは絶対に必要。ただし、組み込みなどの一部では関数を使わなくてもできる場合もあるはず。

*2:厳密にはEXIT_SUCCESSという「マクロ」を返すのが正しい。しかし、マクロの説明をしていないのでここでは却下。

*3:なぜかf関数とは言わないことが多い。関数mainは言うことも多いが、最初にmain関数と呼んでしまったのでmain関数に統一。

*4:実行順序について説明していないが、C言語の場合引数が先。

*5:多くのパソコンでは、という言い方からわかる人もいるかもしれないが、終了しないこともある。関数fの実行が常にreturn命令の中で書かれており、かつほかに実行する内容がないため、保存しておいた情報を全て破棄しても問題ない。そのため情報が蓄積されず、終了しなくなる。末尾呼び出し最適化と呼ばれる。

posted by chiguri at 01:51| Comment(0) | TrackBack(0) | 講義

2009年07月07日

C言語超入門(?)第六回

お久しぶり。

ここまで長かったけれど、今度こそ数字を画面に出す。

今回は比較的コードが長い。

ま、軽くプログラムを読む練習になると思う。

注意:このページのソースコードを勝手に使うのはご自由に、といいたいところなのだが、blogの関係上、スペースを一部全角にしているので、それを直さないと動かない。気をつけるように。まあ、たぶん使わないと思うけれどね。


前回の復習と今回の概要

  1. 条件式は、「正しい」か「間違ってる」もの。
  2. 条件分岐は、「ある条件式が正しいとき」と「そうでないとき」で実行する命令をわけること。
  3. 複文は、複数の命令を一つの命令のように扱うこと。
  4. 再帰関数は、関数の定義の中でその関数自身を呼び出すこと。この呼び出しを再帰呼び出しという。
  5. 有効範囲は、変数や関数などの見える範囲のことを言う。それぞれ、宣言や定義を行ったブロックの内側ならば見える。ブロックは中括弧で囲まれた部分のこと。
  6. 有効範囲内ならば通常変数などを使えるのだけれど、「同じ名前」がある場合は近いものしか使えない(遠いものを表せない)。
  7. 関数の中で宣言されている変数は局所的であるという。関数の中でなければ大域的であるという。関数の定義は大域的でなければならない。

まあこんなところ。ブロックの説明が少しアバウトすぎるかな?


今回の概要は、実に短い。

  1. 数字を表示する関数print_numberを定義する。

もう少し詳細に書くと、

  1. 表示に使う関数はputcharのみ。
  2. 各桁を表示するために再帰関数を用いる。
  3. 今までに説明したことのない演算子(+や-、*のようなもの)を使う。もっとも、似たものは知っているはずなので別に難しくも何ともない。

こんなところ。では、始めよう。

まず、簡単なところから

putchar関数は、「指定した文字(1文字)を画面に表示する」関数だった。

なので、数字として簡単な場合について考えよう。

ちょっと先回りをするようで悪いのだが、0から9までの、1桁の数字が渡された場合について。

この表示、書く量が面倒なので、関数で作ってしまおう。

名前は・・・print0to9でいいかな?*1

引数はint(整数)で、受け取った値は0から9までの数字だったとしよう*2

では、早速書いてみる・・・のだが、引数が0から9までのどれかなので、「愚直に」条件分岐するしかない*3

ちなみに、引数をそのままputcharに渡すのはおかしいので注意。例えば数字の1と文字の'1'は違うものである*4

全部書くと長いので、0,1,9の場合だけ書いて、後は「...」という形で省略させてもらう。あまりにそのままだから、間違えようもない。

int print0to9(int n) {

 if(n == 0) { putchar('0'); }

 else if(n == 1) { putchar('1'); }

 ...

 else if(n == 9) { putchar('9'); }

 return 0;

}

elseの後にifが書いてある部分は「前回書いた条件分岐で正しくなかった場合に、また条件分岐をするよ」という意味。

今回は、この条件分岐の並びのうち一つしか正しくならないので、elseがなくても正常に動く。

だが、elseを明示することで「nが1だったらこうしてほしい、そうでないときでnが2だったらこうしてほしい、・・・」というこの関数で書きたいことを明示できる。

もしなかった場合、「同時にいくつか実行される可能性もあるんじゃ・・・?」と考えてしまう。ここではそんなつもりはないのだから、しっかりelseも書いた。

return命令は、とりあえず終わることを表しているだけで、特にこの関数がどんな値を返そうと(呼び出した箇所がどんな値になろうと)私たちは興味がない*5。基本的に、私たちは「この関数が数字を画面に表示する」ことさえわかればそれでかまわない。


ちなみに一応説明しておくと、nの値(についての私たちの予想)が正しい限り、この関数は正しく動く*6

では、全体を構築してみよう。


全体の構築・その1:単純だけど間違えているもの

タイトルを見てうんざりする人もいるだろうが、とりあえず見てほしい。

単純であれば間違いようがない、という考えは間違っている、という例である。


数字の表示は、大きい桁を左に、小さい桁を右に、である。

コンピュータでの文字の表示は左から右なので、大きい桁から順番に表示しなければいけない。

さて、簡単に思いつく方法は、値の一番大きな桁を上の関数で表示して、その桁を消して次の桁を表示して、という動きを繰り返せばいい、というもの。


例えば、数字の123というものを表示するとしよう。

123のもっとも大きな桁は3桁目、1である。

桁数を数えることはできそうだ。例えば、10より小さければ1桁、100より小さければ2桁、1000より小さければ3桁、などなど。

1を取り出すのは、例えば100で割った値を出せばいい。整数同士の割り算は、小学校でやった「余り」のある割り算だと思えばいい*7。そう考えると、100で割れば1が出てくる。


では残りの23を取り出すには?

面倒なやり方としては、1を取り出せたのだし、桁数もわかっているのだから、数字を桁に合わせて引けばいい。

だが、まあそんなことをしなくても、C言語には「余り」を出す演算子――足し算の+とか引き算の-のように、操作を表す記号――がある。なんと、「%」だ。

イメージがわかないだろうけれど、我慢してほしい。これを決めたのは私ではないのだ*8

というわけで、あとは残った23がまだ表示しなければいけない状態ならば、上と同じように処理すれば・・・

いい・・・の?


さて、この表示方法は「明らかに」間違っている。

いやいや、上から順に見ていくんだから間違えようがないじゃないか、と言われそうだが、そんなことはない。間違っているものは間違っている。

たとえば101を表示しよう。できるかな?


答えは、101は表示できない。11が表示されてしまう。

上のやり方を見ると、最初の表示で1を出した後、101から100を引いている。答えは1。

1を表示しようとすると、当然1を表示する。

あれ、2桁目の0は?


全体の構築・その2:回避策

途中の0が表示されない問題は、「表示する数字の桁数」をとっておかなかったことだ。

だから、これを回避するには、桁数を数えながら表示を進めればいい。

「今何桁目を表示しているよ」という情報があれば、101から100を引いた1(次に0を表示する予定)と、ただの1(1だけを表示する予定)に対する表示を変えることができる。

表示のチェックは1桁目、2桁目、・・・と進めていくので、「自分の表示する桁より上は、次の桁をチェックするやつが勝手に表示してくれる。」と考えよう。

こうすると、1桁目の表示担当は、「(数字が2桁以上なら)2桁目より上は2桁目担当に投げれば勝手に表示してくれるから、その後自分の桁を表示しよう」ということになる。

2桁目は2桁目で、「(数字が3桁以上なら)3桁目より上は3桁目担当に投げれば・・・(以下略)」ということになる。

ちなみに、「自分の表示する桁」より「表示しようとする数字の桁」が大きくなることはないとしよう。

1桁目から始めれば、「表示しようとする数字の桁」は必ず1以上なので、逆転することはない。


大きなプログラムの流れは、次のようになる。

  1. 今表示しようとしている桁と、表示しようとしている数字の桁を比べる。桁数が同じならば、自分の桁を表示するだけで終了。
  2. そうでなければ(表示しようとしている数字の桁の方が大きいので)、自分より一つ大きな桁「以降」を表示するように繰り返す(関数を呼び出す)。
  3. 繰り返した処理が終わったら自分の桁を表示して終了。

以上。わざと関数の再帰呼び出し風に書いている。

全体の構築・その3:プログラム・・・の前に

さて、これをC言語で書いてみよう。

といっても、結構細かな問題はある。

  1. 桁数から10とか100とかもってくるのはどうすればいい?
  2. 「自分の桁の数字」をどうやってとりだそう?

など。


1については実際は簡単で、別に桁数でなくても、「自分がどこを表示するか」と「自分より上の桁を指示する方法」さえわかれば問題ない。10とか100とかを桁数の代わりに使えばいい*9

ならば2はどうだろうか?


大まかには、「自分より上の桁」と「自分より下の桁」を全て消してしまえばいいことになる。

その1で少し話したが、「自分より下の桁」は「自分の桁」で割ればいい。1桁目ならば1(何も変わらないけれど)、2桁目ならば10、3桁目ならば100、といった具合に。

「自分より上の桁」は、「自分より一つ上の桁」で割った余りを使えばいい。1桁目ならば10で割った余り、2桁目ならば100で割った余り、3桁目ならば1000で割った余り、といった具合に。

この計算は同時に行えないので順番に行う。下の二つのどちらかを使えばいい。

  • (数字 % (自分の桁 * 10)) / 自分の桁
  • (数字 / 自分の桁) % 10

これで、自分の桁の数字が1桁で出てくる。なお、前者は「上の桁を消して、その後下の桁を消す」、後者は「下の桁を消して、その後上の桁を消す」という順番。

後者では、下の桁を消すと「自分の桁」が1桁目にくるので、余りを計算する箇所は2桁目を表す10を使っている。

なお、後者の方が計算としてはほんの少し早い・・・かもしれない*10


「自分の桁の数字」を返す関数を作る。必要なのは「表示する数字」と「桁」なので、次のように。

int place_number(int n, int place) { return (n / place) % 10; }

以上。placeは桁(を10の累乗で表したもの)、nは表示したい数字。

place_numberで一つの関数の名前である。名前にはアルファベットや数字、"_"*11を使うことができる。C言語では割と単語の区切りに"_"を入れる。

さて、前準備は以上、本来の関数を作ろう。


全体の構築・その4:プログラム

前々節で説明した方法を、そのままプログラムにすると次のようになる。

int print_number(int n, int place) {

 if(n < place * 10) { print0to9(place_number(n, place)); }

 else { print_number(n, place * 10); print0to9(place_number(n, place)); }

 return 0;

}

最初のifは、「placeの10倍(=自分の桁の上の桁)より小さい(=自分の桁で終わり)」かどうかで分岐する。

正しい場合(自分の桁で終わりの場合)、自分の桁を取り出して、その数字を画面に表示させる。

正しくない場合、自分の一つ上の桁以上を表示させて、それから自分の桁を表示させる。

分岐が終わった後に終了。


少し気がつく人ならば、自分の桁の表示がどちらにも(全く同じ形で)あることに注目するだろう。

だから、これを少しだけ短くできる。

int print_number(int n, int place) {

 if(n >= place * 10) { print_number(n, place * 10); }

 print0to9(place_number(n, place));

 return 0;

}

>=という見慣れない記号が出てきたが、「左側が右側以上である」ことを表す。両方が同じであるときも正しい。

上に出てきた<とはちょうど逆になるので、上に出てきたelseの場所でだけやっているprint_numberの再帰呼び出しだけをやって、その後に「どちらの場合でも」自分の桁を表示して終了している。


あとは、この関数をmain関数から呼び出せば使える。placeの引数を忘れないように。1桁目からだから、1を渡す。

main関数の例としては次の通り。

int main() { print_number(707, 1); putchar('\n'); return 0; }

これで707という数字が画面に表示され、改行されて終わる。連続でprint_numberを呼び出すと数字が続いてしまうので、putcharなどで区切りを入れないと読めない。

例えば、次のmain関数:

int main() { print_number(1,1); print_number(2,1); return 0; }

は、画面に12と表示する。12なんだか1と2なんだかわからない。

どうせいつもplaceの引数を1で呼び出すのだから、次のような関数を準備して使うのも一つの手だろう。

int print_number1(int n) { print_number(n, 1); putchar('\n'); return 0; }


補足

このプログラムは、いろいろと改善の余地がある。

例えば、このプログラムは10桁の数字(10億の位)の数字を出せない*12

これは、そもそもintという型の値はおおよそ20億(厳密には2の31乗から1を引いたもの)までしか正確に持てないことが原因である。

このプログラムは10倍の値をもってきてその値との大小で桁数をチェックしているので、10億を超える値については、(100億を表現できないので)桁数を確認できない。

それでも20億を超えない限り(15億あたりなど)は表現できるのだから、表示したいかもしれない。

というわけで、もっと効率よく表示するプログラムを考える。


今度の関数は、自分のすべきことは1桁目を表示することとする。

2桁目以降は「10で割った値(=1桁目を取り除いたもの)」で再度行うことで、全ての桁を表示させる。

以下のプログラムと、この説明で「どうして全ての桁が表示されるか」を考えてみてほしい。

まあ、何となくわかると思うが。

int print_number2(int n) {

 if(n < 10) { print0to9(n); }

 else { print_number2(n / 10); print0to9(n % 10); }

 return 0;

}

ifの条件が正しいときにnについて余りをとっていないのは、nが10未満(だから負の値でなければ1桁)だとわかっているからである。

この関数だと、placeという引数が不要になり、プログラムもすっきりしている*13

nが10未満の時に10で割った余りをとっても同じ値なので、print_number関数の時にまとめた方法と同じ方法でprint0to9の呼び出しを一ヶ所にまとめることもできる。

・・・してもしなくてもそんなに変わらないけれど。


今回のまとめ

まとめも何も、関数を作っただけだからまとめることはないのだけれども、所感を書いておく。

  1. if 〜〜 else if 〜〜 ・・・という書き方は「どれか一つだけ」を選ぶ場合によく使う記述である。
  2. intという整数は表現できる範囲がある程度決まっている。範囲を超えると正確でない値になるので、その範囲に注意する必要がある。
  3. 関数でよく使う形があるなら、それを表す関数を再度作るのも一つの手である。特に、「最初に渡したい」引数が完全に決まっている場合は、「最初に渡したい」値を見つけやすくできる(上に表面的にはその値を見る必要がなくなる)ので、よく関数が準備される。
  4. 処理が一見単純でも、本当に正しい保証なんてどこにもない。このようなプログラムは一見正しいことが多いので、正しくない例を見つけられるかが問題である*14
  5. やり方を思いついても、そのままプログラムにできるかはわからない。今回、途中途中で挙げた問題は、(特になれない頃は)プログラムを書いている途中で発見するような内容である。
  6. 簡単に考えられること≠プログラムが単純であること。プログラミングに慣れるとかなり近くなるのだが、そうでない場合、簡単な考えというのは余計な処理が多くなりがちである*15

もっとも、これらの内容(最初を除く?)は割と経験則なので、ここでのスタンス(「これを読んでも書くな」)とはかなりずれている。

しかし、プログラムの意図を読む(読めるように書く)のは重要である。

総じて、今回は言語の説明と言うより、プログラミングの細かな技術の説明、というニュアンスが強かったかもしれない。


次回予告

しばらく今回に向けて突っ走ってたので、あまり考えていなかったが・・・

次回は「繰り返し」について。

実は、今回のprint_number関数くらいだと繰り返しの方が書きやすく、しかも速かったりする。

一般的に、C言語では同じような操作を実行するならば繰り返しの方が速い。

・・・もっとも、無理に繰り返しにすると、面倒が生じることが多々あるのだけれども、ね・・・

*1:いい名前が思いつかない・・・

*2:例として書いている関数ではそれを確認していない。本当は確認したほうがいいのだが、面倒なのでしない。

*3:C言語にはswitch文という、もう少しこんな場合に楽にかけるものもあるのだけれど、本質的には何も変わらない。

*4:本当は、文字も「数字」の一種なので、計算でもっと簡単に出せる。特に'0'から'9'までの「文字」は通常並んでいるので、ある値を加えるだけでできるのだが、文字についての説明をかなり省いているのでここではその方法を用いない。

*5:行儀の悪いプログラミング作法ではある。値がいらないならばそれを明示すべきで、明示する方法は実際にある。が、説明していないので適当に0にしている。別に1でも-3500でもいい。普通0か1くらいだが。

*6:nの値が予想通りでなく、1から9以外の数字だった場合、この関数は何もしない。

*7:厳密には負の値について面倒な話がある。今回は0以上の値だけなので、これで正しい。

*8:私が決めろ、といわれてもイメージがわきやすい候補がなくて困るのだが。

*9:自分より上の桁は10をかけたものだから簡単。

*10:遅くなるのは特殊な場合なので、よほど問題が起こらない限りは後者を選べばよい。

*11:記号の名前は「アンダースコア」。「アンダーバー」と呼ぶ人もいるが、少なくとも記号として正確な呼び方ではない。

*12:一般のパソコンの場合。100京まで出せるようになっているものもあれば、1万すら出せないシステムもあるので、一概には限界をいえないが、多くの場合10億に入った時点でプログラムがまともに動かなくなる。

*13:しかも余計な計算がないため、わずかながらprint_number関数より速い。

*14:ある程度正しくない例を見つける方針は存在するが、それは完全ではないし結局経験に頼ることが多い。まだプログラミングが職人芸となっている所以だろう。

*15:print_numberのplace引数がいい例である。10億以上で表示できなくなる問題を作ってしまった上、よりプログラムを単純にしたら不要になる。

posted by chiguri at 15:16| Comment(0) | TrackBack(0) | 講義

2009年06月30日

C言語超入門(?)第五回

今日も今日とて説明が多い。

このまま十回くらいまでで終われるのだろうか・・・?

何回まで続くのか、甚だ疑問である。


前回の復習と今回の概要

  1. 変数の宣言は、値を置く場所の確保。
  2. 変数への代入は、確保した場所に置く値を置き換えること。
  3. 変数の使用は、ただ名前を書けばいい。するとその変数が確保している場所の値に置き換わる。

前回説明した内容はこんなところ。

前回のまとめとずいぶん説明の語彙が違うと思うが、あまり気にしない方向で。


今回説明する内容は・・・前回の予告とずいぶん違うけれど。

  1. 条件式。端的に言えば、「正しい」か「正しくない」もの。YesかNoで答えられるもの。
  2. 条件分岐。条件式を書いて、その条件式が正しいときと正しくないときで、実際の命令を分ける。
  3. 複文。複数の命令を一つの命令として扱う。
  4. 再帰呼び出し。関数のなかで、「その」関数を呼ぶこと。
  5. 変数、引数、関数(それぞれの名前)の有効範囲(スコープ)。

・・・多分、これだけ説明したらその時点で前回の予告を無視することに。

だけど、これを全部終わらせたら今度こそ数字が画面に出せる!*1

さあ、がんばっていく、のは、私なんだよなあ・・・


条件式

条件式とは、YesかNoで答えられるもの。ドラクエの勇者でも答えられるもの*2

例えば、1+1=2は正しい*3。1+1=1は正しくない。

ちなみに、この二つの式をC言語で書くと怒られる。C言語では「=」は「代入」を表すものであって、「等しいこと(等号)」を表すものではないから。

1+1=2をC言語で解釈すると、「1+1に2を代入しろ」ということになる。意味がわからない。

C言語で正しく書くと、1+1==2、1+1==1と、「==」のようになる。


さて、それでは条件式でないものとはなんだろう?

これは例えば、3+4。言うまでもなく、答えは7であってYesやNoではない*4

ちなみに、Yesを1、Noを0とすると、条件式は「結果が1か0であるもの」ということになる*5


お、条件式の説明が終わったぞ、これならそんなに長くならないかも?

・・・次が長いだろうけど。


条件分岐

さて、上で挙げた条件式は「結果が常に同じ」条件式なので、あまり意味がない。

では、前回説明した変数や、その前の引数が関わってきたらどうなるだろうか?

例えば、変数xがあったとして、x > 0は正しいと断言できるだろうか?否、状況によるとしかいえない。

引数yがあったとしたら、y == 1は正しいのだろうか?今度はさっぱりわからない。

関数を呼ぶ側が実引数として何を与えたのかわからないのだから*6

というわけで、「この結果が正しければこうしたい」「正しくなければああしたい」というタイプの書き方ができないと、プログラムを書く側は困るわけである。

少なくとも、わざわざ関数というものを書くときに、面倒すぎる。

もちろん、これから先利用価値はどんどん上がる。


さて、簡単に条件分岐の書き方を説明。

if(条件式) 「正しいときの命令」 else 「正しくないときの命令」

ifとかelseとかは、C言語で決まった言葉。

ちなみに、intやcharみたいなのも同種で、このような「C言語で決められた言葉」を「予約語」という。

予約語は名前に使えない、とかいろいろ制限はある。

しかしまあ、あまり気にしなくてもいいし、まともな神経をしていれば名前になんて使わないだろう。

ちなみに、elseと「正しくないときの命令」は、書く必要がないならば書かなくてもいい。


条件分岐を使った例を挙げてみよう。

if(x == 0) x = 1; else x = x * 2;

xが0だったらxに1を代入して、そうでなかったらxにx * 2――変数xに2をかけたもの――を代入する。

ちなみに、elseの後ろに出てくるx * 2は、代入される前のxの値に2をかけたもの、の意味である。


さて、次の例にいこう。今度はelseがないが、先ほど言ったとおり、なくても正しい。

if(x > y) y = x; x = x + 1;

この一連の命令はどう動くだろうか?

ぱっと見ると、「xの値がyの値より大きかったら、yにxの値を代入して、xにx+1を代入する」と見える。

が、残念ながらこれは不正確。

正確に意味を書くとこうなる。

「xの値がyの値より大きかったら、yにxの値を代入する。(xの値とyの値がどうだったとしても)その後にxにx+1を代入する。」

つまり、予想とは「xにx+1を代入する」という操作の場所が違う。


これは、ifによる条件分岐が「それぞれ一つの命令だけ」実行できるからである。

しかし、当然のことだが複数の命令を実行したい(こともある)。

そこで出てくるのが、複数の命令を一つとして扱う方法。

一つの命令を「文」と言ったりする関係で、「複文」と言ったりする。


複文

関数を書くときに、内容である命令の前後を「{ }(中括弧)」で囲っていた。

そして、この中では複数の命令が書けていた。

中括弧は「複数の文を書く」ことを許す構文である*7

ちなみに、「複文」は「文」とは言うけれど、セミコロンは不要*8


では、この書き方でさきほどの例を書き直してみよう。

最初の解釈はこちら。

if(x > y) { y = x; x = x + 1; }

それで、その次の解釈を、明確に括弧をつけていくとこのようになる。

if(x > y) { y = x; } x = x + 1;

このように、「複文」という名前はついているけれど、中にある「文」は1つでもいい。

もちろん、0でもいい。

だから、「単一の」文(命令)だけが書ける場合、自分の意図を明確にするために複文の形にしたほうがいい。

別にコンピュータにしてみれば、前に書いた例と、すぐ上の例は何一つ変わりはしない。

だが、人間が見るときは(特になれていない人ほど)すぐ上のように囲んであった方がわかりやすい。

・・・まあ、「面倒だ」という異論もあるので、あなたが気に入ったようにした方がいいだろう*9


うあ、既に長い・・・でも続けて説明するよ。

再帰関数・再帰呼び出し

再帰関数については、特に面倒な説明もない。

関数の定義の中で、その関数自身を呼び出す関数のことを再帰関数といい、その呼び出しを再帰呼び出しという。

しかし、何もせずに関数を呼び出すと、大体永遠に関数を呼び出し続ける*10ので、条件分岐を使う。

では、次のプログラムに行こう。

定義している関数は、0から引数として渡された値までの和を足したものを出す*11

int sum(int n) {

 if(n == 0) { return 0; }

 else { return sum(n - 1) + n; }

}

sumという関数の中で、else側にてsum関数をもう一度呼び出している。

しかし、引数の値が少し違って、「nの値(ここでは元の関数の引数の値そのまま)から1を引いたもの」を引数にしている。

sum関数を呼び出した結果として期待している内容は、「0から渡した値までの値の和」である*12

なので、else側で書いているreturn命令には「nの一つ前までの和(0からn-1までの和)にnを足したもの(=0からnまでの和)」をくっつけているわけである。

ちなみに、ifの条件式が正しい(=nが0である)ときは0にしている。0から0までの和は0に決まっている。


説明の中で初めて関数の「結果」を使っているが、「return命令に書いた内容が呼び出した場所の値に変わる」という関係上、上のような使い方も割と一般的である。

まあ、残念ながら、目的とする関数(画面に数字を出す)は「結果」が不要なので、上のような使い方はしないのだけれども。


さて、再帰関数が出てくると、引数が何度も出てくることになる。

例えば、上のsum関数でsum(5)を呼び出すとどうなるだろう?

まず、nが5としてsum関数が実行される。

そして、5は0ではない(そりゃそうだ、などと言わない)ので、else側が実行される。

return命令の中でsum関数が呼び出される。このとき引数はn-1、nは5なので引数は4になる。

そして、nは4になる。


・・・さて、今回4になったnと最初に呼び出した時の(5だったはずの)nは同じだろうか?

まあ、同じだと困る。sum(4)を呼んだ後、その結果にn(当然5だと思っている)を足すのだから、4だと予想に合わない。

というか、この先も再帰呼び出しがあるので、最終的に0になっているはず。


困るのだから、当然そうなっているはずがない。

だから、呼び出し毎に引数nは新しく場所が作られていることになる。

当然、nといったら「そのとき呼んだ関数での引数n」である。

こうなると、どの変数が見えているのか、ということで、変数の「見える範囲」が大事になってくる。

この「見える範囲」が有効範囲と呼ばれるものである。


引数・変数・関数の有効範囲

有効範囲(英語でscope、よくカタカナでスコープと書く)は、「見える範囲」=「使える範囲」のこと。

この外側では、変数や引数、関数が見えない(ので当然使えない)。

さて、有効範囲について、それぞれ簡単に書いていこう。

  • 引数の有効範囲は「関数が始まってから終わるまでの、定義における命令の中」。再帰呼び出しした場合、その「呼び出された関数」は「呼び出した関数」と別のもの、という扱いになる。
  • 変数の有効範囲は「宣言したブロックの中」でかつ「書いた後」。ブロックとは、中括弧で囲まれた(複文のときか関数の定義のとき)範囲。どの中括弧にも囲まれていないとき、宣言された変数を「大域的である」といい、書いた場所以降どこでも使えることになる。逆に、関数の中で宣言された変数は「局所的である」といい、その関数の外側では見えない。
  • 関数の有効範囲は「宣言または定義以降全ての場所」。ちなみに、関数は通常関数の中で定義できない*13。なので、変数での言い方をすれば、常に「大域的」である。

最後に、同じ名前の変数などがあるとき。

これは、「最も近い」変数になる。例えば、大域的な変数と、(見える範囲の)局所的な変数があった場合、局所的な変数が優先される。

つまり、次のプログラム・・・

int x;

int f() {

 int x;

 x = 1;

 return x;

}

の場合、代入やreturn命令で使っているxは、最初に宣言しているxではなく、その直前に宣言しているxになる。


最後に、「同じブロックでは同じ名前のものは定義(変数の場合は宣言)できない」ことが決まっているので、ほとんど「距離的に近い」が上で言う「近い」に当たる。

ちなみに、関数は全て大域的なので、同じ名前のものは二度定義できない。

組み込み関数(C言語に最初から作られている関数)と同じ名前にならないように注意しなければいけない。


今回のまとめ

今回やったことは、結構幅が広い。あえて言えば、「プログラムに構造が書けるようになった」というもの。

  1. 条件式とは、「正しい」か「正しくない」のどちらかと判断できるもの。
  2. 条件分岐とは、条件式を伴って、その条件式が「正しいときに行う命令」と「正しくないときに行う命令」に分岐するもの。
  3. 複文とは、中括弧で複数の命令を囲んだもので、一つの命令として扱われる。
  4. 再帰関数とは、定義の中で自分を呼び出す関数。自分を呼び出す部分を再帰呼び出しという。
  5. 有効範囲とは、名前が使える範囲。スコープと呼ぶ。大雑把には、「宣言された場所と同じ範囲」で「宣言された場所以降」である範囲。関数の中で定義された変数を局所的であるといい、そうでないとき大域的であるという。

最後の局所的・大域的の説明が上と少し異なるが、C言語では宣言や定義以外の命令を大域的に書くことがいけないので、結果的には同じになる。

次回予告

今度こそ三度目の正直ということで、数字を画面に表示する。

今度こそは書けるので。今度こそする。本当に。いや、嘘じゃないよ?


最後に

補足ではないけれど、今回はこれまたC言語の普通の解説と違うやり方をしている。

普通は、「命令の一種」である「繰り返し」を先に書く。

が、なぜかここでは「再帰関数」を先に書いている。

理由は割と単純で、「再帰関数のほうが楽に書ける」から。

ま、呼び出しは遅い(ほかにもいろいろ問題がある)ので、いわゆる「実用的な」プログラミングでは「再帰関数」を極力使わない。

でも、この解説はなにせ「実用的」からかけ離れたスタンスでやっている。

「これを読んでもプログラムは書くな。」だから。

だから「書きやすい」ほう、「楽な」ほうを優先して使った。

・・・まあ、引数の説明の面倒さはあるけれどね。


あー、本当に長い・・・

*1:前回も言ったが、printf関数を使えば一瞬で終わる。しかし、実際にそれをもっと簡単な機能から作ろうとすると、ここまで説明しないといけない。

*2:YesとNoではなく「はい」と「いいえ」だが。

*3:小学生のような問答をしたいわけではないので。

*4:ドラクエの勇者にこの答えを求めたらおそらくプレイヤーが激怒するだろう。

*5:これだと、1-1は条件式になる。C言語では、1-1は条件式としても扱え、結果が0になるものは全て「正しくない」ことを表す。一方、「結果が0でないもの」は全て「正しい」ものであるとしてある。

*6:分からなくてもいいように引数という機構があるのだし。

*7:ただし、関数の定義では中括弧をなくして一つの命令を書くことは不可である。仮にできたとしてもあまりうれしくないし。

*8:C言語には「空文」という、何も書かないでセミコロンを書いた「文」が存在する。もちろん何もしない命令(?)なのだが、複文の直後にセミコロンを書いたら空文があると見なされるだけで、複文の終わりとは判断されない。

*9:実際、簡単な計算をするだけの短いプログラムを書くときには、作ってそれ以上何もしないことが多いので、別に見やすかろうが見にくかろうが気にする必要はない。こうなると「面倒」という意識の方が強くなるし、私も複文にしないことがある。

*10:多くの場合、コンピュータが文句を言ってプログラムが止まる。C言語というカテゴリの中では別に永遠に動いても問題ではないが・・・

*11:もちろん、普通はこんな計算方法はしないが、わかりやすいのだから仕方がない。ただ、この関数に負の値を渡すとこれまた永遠に呼び出し続ける。

*12:少なくとも私はそう言った。

*13:C言語を実行するために必要な「処理系」(プログラム)によっては定義できるようにしてあるものもある。だが、標準的ではないので注意。

posted by chiguri at 00:36| Comment(0) | TrackBack(0) | 講義

2009年06月26日

C言語超入門(?)第四回

前回の復習と今回の概要

  1. 関数を使うために必要な部分だけを書いたものを「宣言」という。
  2. 書かなくても作られている関数を「組み込み関数」という。使うには「宣言」だけは必要。
  3. 組み込み関数のように「誰かが作った関数」は多くの場合「宣言」をまとめた「ヘッダファイル」がある。
  4. ヘッダファイルを使うには#include <ヘッダファイル名>と書く。
  5. 文字列は"で囲んだもの。文字と違って複数の文字が書ける。
  6. putcharとputsはそれぞれ文字と文字列を出力する組み込み関数。

こんなところかな?そして今回はこんなことを説明。

  1. 変数の定義。変数は「値をしまう場所」。
  2. 分岐の書き方。条件に合う場合はこっち、そうでなければあっち、という分け方ができる。

今回は・・・数字でも画面に出してみるかな。

ただしputcharを使って*1


変数の定義

変数の定義とは、端的に言えば、「値を置く場所を作る」こと。

しかし、「場所」があっても、その「場所」を指示する方法がないといけない。

どこかで見た書き方?それはまあ、ある程度意識して書いてますから。

変数の定義は、次のようになる。

型 名前

この定義もやはり;(セミコロン)で終わる。

つまり、書き方としてint i;、char c;など。


書き方が関数の引数に似ている?

それは、(目的以外は)同じものだからである*2

したがって、今回話す内容は、ほぼ全体にわたり引数についても利用できる。


変数の宣言は、「場所」を作って、その「場所」を指しているだけなので、その「場所」に何があるかということは何も言っていない。

だから、その「場所」に「値」を置くこと、そしてその「場所」にある「値」をとってくる(使う)こと、の二つができる。

・・・というか、できないとあまり意味がない。


なお、変数が「場所」を指す、という説明をした*3が、説明が非常に面倒くさいので、「場所」という表現は使わず、変数とだけ言う。

変数の値、といった場合は「変数の指している場所にある値」と考えてほしい。

変数の使用

こちらは至って簡単なので、先んじて書こうと思う。

変数の値を利用するには、「利用したい場所」に変数の名前を書けばいい。

例えば、x+1と書けば、(変数xが何かわかるならば)変数xの中身に1が足される。

・・・それだけ?と聞かれそうだが、それだけ、である。

引数の時と全く同じ。

なのでさらっと次へいこう。

今度は、変数の値を変更すること――「代入」を説明する。

変数の値を変更、と言うのをもう少し「場所」を使って正確に説明すると、「元々あった値を捨てて、代わりに指定された値を置く」というものである。


変数への代入

C言語での変数への「代入」は、次のように書く。

変数名 = 式

ちなみに、これまた立派な命令なので、セミコロンを最後につける。

これは、「式」が計算されて*4、その結果を変数の値とする、という内容。

例えば、x = 1 + 2;と書くと、変数xには1 + 2の結果である3が「代入」される。なので、この命令以降で変数xの値を使おうとすると3になる。


なお、C言語には変則的(変態的?)な記述がいくつかあるのだが、ここでは特に説明しないことにする。

一応「超入門」と銘打っている以上、混乱を招くものは排除しないと。


目的の関数を・・・

書くとまた倍くらい書かないといけないので、次回に回そう。

少しは細かくしたほうがいいだろうし。


補足

最初に述べたとおり、今回書いたことは基本的に関数の引数に対しても適用できる。

なので、引数にxという名前がつけられているとき、xに代入することもできる。

変数と引数は、見た目も、使い方も変わらない。


まとめ

今回やったことは、変数のお話。

  1. 変数とは、値を置く場所(を指す名前)のこと。
  2. 変数の名前は、その(指す場所にある)値と置き換えられる。
  3. 変数の(指す場所にある)値は、「代入」という操作で書き換えられる。
  4. 「代入」は「変数名 = 入れたいもの」で書ける。

この命令が終わった時点だと、変数xの値は3だね、などと考えることができる。

次回予告

今回までに使った内容で、最初に言った関数を作る。

最初に言った関数とは、putchar関数を使って、int(整数)の値を画面に表示する関数である。

まともにプログラムが出てくるので、読むのが面倒かもしれない。

が、このくらいは簡単、というプログラム・・・のはず。

・・・多分、ね。

*1:前回少し出したprintf関数を使えばあっさり画面に出せるのだが、あえて面倒なことをしよう。

*2:変数は基本的に「上書き」することを目的とし、引数は「扱う名前」の定義そのものを目的としているので、明確に異なる。

*3:もっとコンピュータに近い視点では正しいが、C言語のレベルでは別に場所である必然性もない。

*4:いたって普通の足し算や掛け算を思い浮かべれば十分。

posted by chiguri at 00:35| Comment(0) | TrackBack(0) | 講義