Hindley-Milner型推論をCで実装した話
SecHack365 2019 Advent Calendar 14日目の記事です(大遅刻).
- what is this
- きっかけ
- 実装したもの
- 型と型推論について
- 実装
- 感想
- 参照したリンクとか
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ヶ月ぐらい作ってるんですが,ちょっとドキュメント(笑)的なものは書いとくかと思ったので投稿します.
随時更新していきます.
リポジトリはここ!
- 特徴
- サンプルコード
- ハロワ
- 変数定義
- if・while
- 関数定義・関数呼び出し
- UFCS
- 関数のオーバーロード
- if式
- リスト
- import(2019-9-19追加)
- assert
- オブジェクト(構造体)
- メソッドの定義
- 組み込み関数一覧
- ないもの
- TODO
特徴
インタプリタ
内部でソースコードをバイトコードにコンパイルして,それを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
- 何でも入る型
- 結構身近な所にいる
- 実装
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日目やっていきます。
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日現在)のレポートは終わってません。よろしくお願いします。こっちの方が大事件な気がする