米ハーバード大学のコンピューターサイエンス講座を受講し始めてから早いものでもう3週目。メインのDavid先生による動画を視聴し、メンターが説明してくれている短編の動画も視聴し、Labと呼ばれる練習問題を終え、Problem(課題)を提出する。この一連の勉強サイクルにも慣れてきた。

今週の内容も盛り沢山で、未だにこの講義が無料とは信じ難い(良い時代になったものだ!)。コンパイル、デバッグ、メモリの有効活用術、配列の説明(分かりやすい)、String型というのはC言語には用意されておらず配列を使って表す等の基本的な内容から、mainにはいつも呪文のようにvoidを引数として宣言していたが文字列の引数を渡せたり、本日学んだことから簡単な暗号化についても学べる講義となっている。

post office

 

CS50第3回目の講義「Arrays(配列)」

Compiling(コンパイル)

前回までコンパイルを実行するときは、make hello とコマンドラインに打っていたが、これは一体何だったのか?ということを深く説明するところから授業は始まる。make hello は、CS50 IDEが用意した自動化ツールの一つだが、本来であれば、clang hello.c とする必要があり、結果として a.out が出力される。この a.outa とは、assembley の略で、コンピューターが理解できる言語を出力するという意味を指す。

この出力ファイル名を変えるためには、clang -0 hello hello.c とコマンドラインから指示を与える。

さらには、プログラム内でヘッダーで指定する各種ライブラリーは、ファイル名の宣言だけであって、そのライブラリーとプログラムをリンク(-lcs50)する必要がある。実際のコマンドラインは、clang -o hello hello.c -lcs50

Preprocessing(前処理) #include など、# から始まるヘッダーを読み、変換する。例えば、以下のようなプログラムがあったとすると…

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    string name = get_string("What's your name? ");
    printf("hello, %sn", name);
}

以下のように変換される。

...
string get_string(string prompt);
int printf(string format, ...);
...

int main(void)
{
    string name = get_string("Name: ");
    printf("hello, %sn", name);
}

Compiling(コンパイル)、はコンピュータが理解できる言語(アセンブリ言語)に変換する作業。コンパイルするときに出力ファイル名を指定しない場合に a.out と結果ができるのは、assembly outputの省略のため。

...
main:                         # @main
    .cfi_startproc
# BB#0:
    pushq    %rbp
.Ltmp0:
    .cfi_def_cfa_offset 16
.Ltmp1:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
.Ltmp2:
    .cfi_def_cfa_register %rbp
    subq    $16, %rsp
    xorl    %eax, %eax
    movl    %eax, %edi
    movabsq    $.L.str, %rsi
    movb    $0, %al
    callq    get_string
    movabsq    $.L.str.1, %rdi
    movq    %rax, -8(%rbp)
    movq    -8(%rbp), %rsi
    movb    $0, %al
    callq    printf
    ...

Assembling(アセンブリ言語)次に、アセンブリ言語からMachine code(マシン言語?)に変換する。

Linking(繋げる)そして最後に、ヘッダーで宣言したファイルを全て結合して出来上がりとなる。

 

Debugging(デバッグ)

Debuggingとは、その名の通りBugを取り除く作業のこと。プログラミングをしていると多くの構文の間違いや自分の意志とは違うプログラムを書いてしまうことがある。これらを総称してバグと呼び、それを取り除くというもの。今まで help50 style50 check50 など既に多くの便利ツールが用意されていたが、更に debug50 が紹介された。 もちろん、printf を多用して変数の値に何が入っているのかを逐一出力することはできるが、長いプログラムになってくるとこれも手間となってしまう。そこで、debug50 が便利になるということだ。仮に buggy0 という実行ファイルがあったとしたら、debug50 ./buggy0 とコマンドラインに打ってあげれば良い。

例えば、以下のようなプログラムで # を10回出力したいとする。でも結果は11回出力されることになる。間違っていそうな行を選択すると赤丸が付く。プログラムはここで一旦止まることを意味する。

code editor with red icon next to line 6 of code

原因を詳しく見るために、debug50 ./buggy0 でデバッグ機能を立ち上げながら実行できる。また、プログラムを終了したい場合は、 control + C と押せば強制終了できる。

debugger panel with controls, variables

 

Memory(メモリ)

コンピューターの中には、RAM(Random Access Memory)と呼ばれる短期的にデータを格納するメモリが入っている。例えば、実行中のプログラムやファイルが開いている間などはこのRAMを使うことになる。ハードディスクにいちいち保存するより、このRAMを使用する方が素早く処理を実行可能で、コンピューターはそう設計されている。ただ、電源が切れた場合やバッテリーがなくなった場合に、開いていたファイルが消えたり、保存していないデータが消えてしまうのは、このRAMにデータが格納されているからで、そういった欠点もある。

computer chip with grid overlaid

C言語では、このRAMにデータ型によって、違うサイズの容量を使うことになる。

  • CS50 IDE環境では、以下のバイト数を使用している
    • bool 1 byte
    • char 1 byte
    • double 8 bytes
    • float 4 bytes
    • int 4 bytes
    • long 8 bytes
    • string ? bytes

なので、プログラムを最適にデザインすることは大事ということだ。

 

Arrays(配列)

arrays
#include <stdio.h>

int main(void)
{
    int score1 = 72;
    int score2 = 73;
    int score3 = 33;

    printf("Average: %fn", (score1 + score2 + score3) / 3.0);
}

上のプログラムをメモリ上で見ると、以下のようにそれぞれのスコアに数字が格納されている。スコアの型宣言は、int なので、4バイト(それぞれの四角が1バイトを表しているとする)を使用している。

grid with values and scores variables

メモリにデータが連続して格納される様子を見ると、Loop機能を使って四角の場所を特定し、情報にアクセスできることが分かる。そして、この一つ一つの四角をArray(配列)と呼ぶ。配列を用いた構文に変更すると次のようになる。

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    int scores[3];
    scores[0] = get_int("Score: ");
    scores[1] = get_int("Score: ");
    scores[2] = get_int("Score: ");

    // Print average
    printf("Average: %fn", (scores[0] + scores[1] + scores[2]) / 3.0);
}

更に、次のようにメモリ上の位置を指定できることは分かったが、さらにそれは変数にすることもできる。

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    int scores[3];
    for (int i = 0; i < 3; i++)
    {
      scores[i] = get_int("Score: ");
    }

    // Print average
    printf("Average: %fn", (scores[0] + scores[1] + scores[2]) / 3.0);
}

または、定数機能を用いて const int TOTAL = 3; 指定してあげることもできる。

#include <cs50.h>
#include <stdio.h>

const int TOTAL = 3;

int main(void)
{
    int scores[TOTAL];

    for (int i = 0; i < TOTAL; i++)
    {
      scores[i] = get_int("Score: ");
    }

    printf("Average: %fn", (scores[0] + scores[1] + scores[2]) / TOTAL);
}

Functionを使って、配列を引数に指定することもできる。このときに配列の長さは分からないため、指定する必要がない。次のプログラムでは、指定された配列まで格納されている整数を足し続け、最後に配列の長さ(データ数)で割ることで平均を計算している。このときに、配列の長さをキャスト使って float 型に変換している。

float average(int length, int array[])
{
    int sum = 0;

    for (int i = 0; i < length; i++)
    {
        sum += array[i];
    }
    return sum / (float) length;
}

Characters(文字型)

1文字を出力するプログラムは、次のようにかける。

#include <stdio.h>

int main(void)
{
    char c = '#';
    printf("%cn", c);
}

ここで、仮に char 型の c int型に変更した場合、どうなるか見てみると35 が出力される。35 とは、ASCIIコードの # であることが分かる!この説明は、後に続く暗号化の説明の序章に過ぎない。

#include <stdio.h>

int main(void)
{
    char c = '#';
    printf("%in", (int) c);
}

 

Strings(ストリングス型…はないので)

char 型を連続して出力すればそれは、Strings型と同じということも教わる。

#include <stdio.h>

int main(void)
{
    char c1 = 'H';
    char c2 = 'I';
    char c3 = '!';

    printf("%c%c%cn", c1, c2, c3);
}

そして、それを int 型に変換すると、

#include <stdio.h>

int main(void)
{
    char c1 = 'H';
    char c2 = 'I';
    char c3 = '!';

    printf("%i %i %in", c1, c2, c3);
}

72 73 33 とASCIIコードを返してくれる。

grid with 72, 73, and 33 labeled c1, c2, and c3

よって、Strings とは文字の配列であることが分かる。その配列にアクセスしたい場合は、 s[0]s[1]のように記述すれば良い。そして、Stringは、文字の連続をコンピューターに教えるために、null character と呼ばれる''を最後のバイトに使用する。

grid with H labeled s[0], I labeled s[1], ! labeled s[2], � labeled s[3]
#include <cs50.h>
#include <stdio.h>

int main(void)
{
    string s = "HI!";
    printf("%i %i %i %in", s[0], s[1], s[2], s[3]);
}

s[4] にアクセスすると、全然見覚えのない数字が返される。これは、RAMメモリに一時的に残ったデータであり、C言語を使って他のデータを書き換えられてしまうリスクがある。

Loop文を使えば、ストリングスに入っている文字を全て書き出すこともできる。

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    string s = get_string("Input:  ");
    printf("Output: ");

    for (int i = 0; s[i] != ''; i++)
    {
        printf("%c", s[i]);
    }
    printf("n");
}

もしくは、s[i] != '' まで、と指定することもできる。String ライブラリーの strlen を使えば、Stringの長さを返してくれるので、プログラムは更に簡潔に書ける。

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string s = get_string("Input:  ");
    printf("Output: ");

    for (int i = 0; i < strlen(s); i++)
    {
        printf("%c", s[i]);
    }
    printf("n");
}

ただし、上のプログラムは最適のデザインではない。なぜならLoopを回す都度にStringの長さを調べてしまっているから。なので、以下のように n = strlen(s) と初期化するよう書き換えた方が良い。

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string s = get_string("Input: ");
    printf("Output:n");

    for (int i = 0, n = strlen(s); i < n; i++)
    {
        printf("%cn", s[i]);
    }
}

配列に2つのStringsを宣言した場合、

string words[2];
words[0] = "HI!";
words[1] = "BYE!";

配列には、次のように格納される。

grid with H labeled words[0][0], I labeled words[0][1], and so on, until words[1][4] with a �, each of which takes up one box, and empty boxes following

words[0] は、1つ目のwordsであることを指定し、words[0][0] は、その中のどの文字かを指定している。

それでは、配列の章の総まとめとして、小文字を大文字に変換するプログラムを見てみる。

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string s = get_string("Before: ");
    printf("After:  ");

    for (int i = 0, n = strlen(s); i < n; i++)
    {
        if (s[i] >= 'a' && s[i] <= 'z')
        {
            printf("%c", s[i] - 32);
        }
        else
        {
            printf("%c", s[i]);
        }
    }
    printf("n");
}

もうお分かりの方もいると思うが、ASCIIコードの表を見ながらaからAに変換するためには、32を差し引けば良いことが分かる。もちろんこの程度のプログラムは既に先人たちが作っていてライブラリー(ctype.h)が用意されているが、コンピューターの裏側の仕組みを知るという意味では非常に有益な講義である。

#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string s = get_string("Before: ");
    printf("After:  ");

    for (int i = 0, n = strlen(s); i < n; i++)
    {
        if (islower(s[i]))
        {
            printf("%c", toupper(s[i]));
        }
        else
        {
            printf("%c", s[i]);
        }
    }
    printf("n");
}

そして、toupper() には文字型ではないデータは処理されない仕様になっているため、もっと簡略できる。

#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    string s = get_string("Before: ");
    printf("After:  ");

    for (int i = 0, n = strlen(s); i < n; i++)
    {
        printf("%c", toupper(s[i]));
    }
    printf("n");
}

 

Command-line arguments(コマンドライン引数)

mainにはいつも呪文のようにvoidを引数として宣言していたが文字列の引数を渡せる。以下のプログラムでは、argcargv は、main 関数の2つの引数となる。argc は、argument countの略で引数の数を意味し、argv は、argument vector (argument list)を意味する。

#include <cs50.h>
#include <stdio.h>

int main(int argc, string argv[])
{
    if (argc == 2)
    {
        printf("hello, %sn", argv[1]);
    }
    else
    {
        printf("hello, worldn");
    }
}

最初の argv[0] はプログラム名(./hello など)で、コマンドラインに仮に「David」と打ったとすると、出力結果は、hello, David となる。

次のプログラムでは、各文字を一文字ずつ出力している。

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(int argc, string argv[])
{
    if (argc == 2)
    {
        for (int i = 0, n = strlen(argv[1]); i < n; i++)
        {
            printf("%cn", argv[1][i]);
        }
    }
}

また、main 関数は、int を返すことが分かるが、デフォルトでは 0 が返されるようになっている。ただこれも、次のように明示することも可能。技術的には必要ないが、一般的には return 0; と返すことによってプログラムを終了させる。

#include <cs50.h>
#include <stdio.h>

int main(int argc, string argv[])
{
    if (argc != 2)
    {
        printf("missing command-line argumentn");
        return 1;
    }
    printf("hello, %sn", argv[1]);
    return 0;
}

 

Applications

encryption

以上の、文字列操作を覚えると、誰かにデータを送るときに暗号化をしたかったり、傍聴されても聞き取りづらくしたりしたい場合がある。オリジナルのデータや入力のことをPlaintext(プレーンテキスト)と呼び、暗号化されたあとの出力はciphertext(暗号文)と呼ぶ。解読するためには、key(鍵)が必要になる。

仮に、 I L O V E Y O U という文字列を送りたいとしたら、まずASCII に変換する 73 76 79 86 69 89 79 85。次に、全ての値に 1 を足すというシンプルなアルゴリズムを用いるとすると、74 77 80 87 70 90 80 86 となる。これをASCII を使って戻すと、 J M P W F Z P V となる。この暗号文を解くためには、-1 をしてあげれば良いというわけだ。

  

感想

第2回目の講義「Arrays」の動画を見終えての感想は、10年間もブランクがあるとやはり基本的なことでさえ結構忘れていて、復習は大事ということ。推奨されているスピードの倍速で進めて入るものの、もっと早く終わらせて最新のテクノロジーにも触れてみたいという興味が次第に湧いてきた。