Hindley-Milner型推論をCで実装した話

SecHack365 2019 Advent Calendar 14日目の記事です(大遅刻)．

what is this

　型理論とか全く知らない人がHindley-Milner型推論器(+ REPL)をCで実装したお話．

記事に誤謬などを発見したらコメントとかDM，リプライください(@cmpl_error)．

C言語でポリモーフィズム

C言語にはオブジェクト指向に関する機能はないですが，ポリモーフィズムを実現する方法をいくつか紹介します．

まずC言語でオブジェクトの継承を表現します．

以下のサンプルにおいて，Personオブジェクトは「名前」という情報を持っています． StudentとTeacherはPersonを継承しており，Studentには学年，Teacherには教えてる教科名を持たせます．

new_studentとnew_teacherはStudentとTeacherのコンストラクタです．

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

typedef struct Person {
    char *name;
} Person;

typedef struct Student {
    struct Person base;
    int grade;
} Student;

typedef struct Teacher {
    struct Person base;
    char *subject;
} Teacher;

Student *new_student(char *name, int grade) {
    Student *n = malloc(sizeof(Student));

    ((Person *)n)->name = name;
    n->grade = grade;

    return n;
}

Teacher *new_teacher(char *name, char *subject) {
    Teacher *n = malloc(sizeof(Teacher));

    ((Person *)n)->name = name;
    n->subject = subject;

    return n;
}

int main(void) {
    Student *john = new_student("john", 4);
    Teacher *garin = new_teacher("garin", "English");

    printf("%s %s\n", ((Person *)john)->name, ((Person *)garin)->name);
    printf("%s\n", john == &john->base ? "john == &john->base" : "john != &john->base");
}

実行結果

john garin
john == &john->base

以上のように，構造体(子オブジェクト)の一番最初のメンバに継承させたいオブジェクト(親オブジェクト)の変数を持ってくれば継承が実現できます．

子オブジェクトへのポインタの値 == 親オブジェクトへのポインタの値が常に成り立つため(ここではjohn == &john->base)，親オブジェクトへのアップキャストが可能になります．

自己紹介をさせよう

　先生と生徒で合計6人いる教室の全員に自己紹介をさせます．

教室にいる人は先生と生徒なので(つまり人間)，自己紹介させるプログラムは以下のようになるはずです．

void introduce(Person *person);

int main(void) {
    Person *class_member[6] = {
        (Person *)new_student("john", 4),
        (Person *)new_teacher("garin", "English"),
        (Person *)new_student("takashi", 1),
        (Person *)new_teacher("hoge", "math"),
        (Person *)new_student("fuga", 6),
        (Person *)new_student("piyo", 2)
    };

    for(int i = 0; i < 6; i++) {
        introduce(class_member[i]);
    }

    return 0;
}

ここからintroduce関数を2つのやり方で実装していきます．

①Person構造体に生徒か先生かの情報を持たせる

生徒か先生かという情報を定義して，

enum PersonType {
    TYPE_STUDENT,
    TYPE_TEACHER,
};

Person構造体のメンバに追加します．

typedef struct Person {
    char *name;
    enum PersonType type;
} Person;

そして，各コンストラクタでtypeの初期化を行わせます．

Student *new_student(char *name, int grade) {
    Student *n = malloc(sizeof(Student));

    ((Person *)n)->name = name;
    ((Person *)n)->type = TYPE_STUDENT;    // here
    n->grade = grade;

    return n;
}

Teacher *new_teacher(char *name, char *subject) {
    Teacher *n = malloc(sizeof(Teacher));

    ((Person *)n)->name = name;
    ((Person *)n)->type = TYPE_TEACHER;    // here
    n->subject = subject;

    return n;
}

introduceでは素直に生徒か先生かを見て出力を変えればOKです．

void introduce(Person *person) {
    printf("My name is %s. ", person->name);

    switch(person->type) {
    case TYPE_STUDENT:
        printf("%dth student.\n", ((Student *)person)->grade);
        break;
    case TYPE_TEACHER:
        printf("%s teacher.\n", ((Teacher *)person)->subject);
        break;
    default:
        puts("space alien");
    }
}

出力結果

My name is john. 4th student.
My name is garin. English teacher.
My name is takashi. 1th student.
My name is hoge. math teacher.
My name is fuga. 6th student.
My name is piyo. 2th student.

②関数ポインタを使う

　Person構造体に関数ポインタをもたせます．introduceは引数にPerson *を取り，戻り値はvoidなので，

typedef struct Person {
    char *name;
    void (*introduce)(struct Person *);
} Person;

となります．

次に，先生と生徒にそれぞれ自己紹介させる関数を実装します．

void intro_student(Person *student) {
    printf("My name is %s. %dth student.\n", student->name, ((Student *)student)->grade);
} 

void intro_teacher(Person *teacher) {
    printf("My name is %s. %s teacher.\n", teacher->name, ((Teacher *)teacher)->subject);
}

そして，各コンストラクタでintroduceを初期化します．

Student *new_student(char *name, int grade) {
    Student *n = malloc(sizeof(Student));

    ((Person *)n)->name = name;
    ((Person *)n)->introduce = intro_student;    // here

    n->grade = grade;

    return n;
}

Teacher *new_teacher(char *name, char *subject) {
    Teacher *n = malloc(sizeof(Teacher));

    ((Person *)n)->name = name;
    ((Person *)n)->introduce = intro_teacher;    // here

    n->subject = subject;

    return n;
}

この変更に伴い，main関数でのintroduceの呼び出しは，

    for(int i = 0; i < 6; i++) {
        class_member[i]->introduce(class_member[i]);
    }

のようになります．

出力結果

My name is john. 4th student.
My name is garin. English teacher.
My name is takashi. 1th student.
My name is hoge. math teacher.
My name is fuga. 6th student.
My name is piyo. 2th student.

C言語はいいぞ．

いかがでしたか？

プログラミング言語を作っているよというお話．

自作言語をかれこれ8ヶ月ぐらい作ってるんですが，ちょっとドキュメント(笑)的なものは書いとくかと思ったので投稿します． 随時更新していきます．
リポジトリはここ！

特徴

インタプリタ

内部でソースコードをバイトコードにコンパイルして，それをVM(仮想機械)上で実行します．replもついてます．

repl

>> 10
10 : int
>> [10] 
[10] : [int]
>> 10 + 40
50 : int
>> let a = 10
>> a * 20000000  
200000000 : int
>> "println" + "orintln"
printlnorintln : string

普通のreplですが，pythonやrubyのreplとは違い型を書いてくれるので便利です．

静的型付け

コンパイル時に型を解析します．

フルスクラッチ

(言語の特徴では無いですが，)解析，実行までの全フェーズ自分の手で書いています．

Cでスタックを実装したよ

どうも．
暇すぎてCでスタックを実装するか〜となって実装したので，そのときのメモです．
ネットに転がってるサンプルコードなどを見てると，int型のデータしか格納できないものが多かったので，それはつまらんということで「なんでも入る」スタックを作りました．

TL;DR

　汎用ポインタ(void *)を使ってスタックを実装した．

Google Form自動回答Botでクソアンケートに勝つ(Python3)

ある時、僕の学校にあるGoogle Formで作られたアンケートに答えるよう手紙が来ました。
見てみると結構長め、さらには回答必須という地獄のような物でした。やるのは面倒だし回答はしなきゃダメ……

そうだ、自動化すればいいじゃないか！
「退屈なことはPythonにやらせよう」

というわけで結構前にGoogle Formに自動で回答を送信するBot(不完全)を作ったので備忘録程度に書きます。
といっても先人にGoogle Form回答自動化してる方がいらっしゃったのでそれを参考にカチカチとやるだけでした。先人に感謝。

Google FormのURL

最初はURLがhttps://docs.google.com/forms/d/e/1FAIpQLSc7J4XPNKYodJlKDeDzfNJHlEGSFbSWqzxhgORDm0ODQWj0Tw/viewformのように最後にviewformがくっついてます。で、情報を送信するとhttps://docs.google.com/forms/d/e/1FAIpQLSc7J4XPNKYodJlKDeDzfNJHlEGSFbSWqzxhgORDm0ODQWj0Tw/formResponseとなり、最後にviewformの代わりにformResponseがくっつきます。
また、Google Formでは回答の送信をURLパラメータを使って行っています。

Ubuntu 18.04で30日OS自作入門をやりたい[3日目-1]

Ubuntu 18.04で「30日でできる！OS自作入門」をやりたい[2日目] - まりものメモ帳の続きです。
定期試験と文化祭とかいろいろ重なっていつの間にかこんな時期です。終わるのかこれ。まずいでしょ。
前回と間が空き過ぎてて「あっ…(察し)」と思った方もいるかと思いますが大丈夫です。俺は生きてる。
というわけで3日目やっていきます。

使ったツール

• nasm
• qemu
• make

詳しくは二日目を参照して下さい。

アセンブリタイム

やることは特に変わらず、nasmくんが読んでくれるように頑張りながらアセンブリを写経します。

IPL作り

ipl.asm

Ubuntu 18.04で「30日でできる！OS自作入門」をやりたい[2日目]

Ubuntu 18.04で30日OS自作入門をやりたい[1日目] - まりものメモ帳の続きです。
2日目でも現実の日数的には大きくかけ離れるんですがそれは許して下さい。深夜までみんなとPUBGmをしてたのが敗因です。

使ったツール

・nasm
・qemu
・make
詳しくは一日目を参照して下さい。

9月9日, 9月10日, 9月12日, 9月13日

事件

いろいろやらかしてOSが起動しなくなった(！)んですが

$ fsck -y /dev/sda2

であっさりと直りました。fsckちゃんすき💕。すっげえ焦りました。OSを作ってる間にOSが壊れるというなんとも皮肉な…
ちなみに明日提出(9月9日現在)のレポートは終わってません。よろしくお願いします。こっちの方が大事件な気がする

アセンブリ写経タイム

いつものおまたせってことでアセンブリを(nasmに都合のいいように)写経していきます。