Closed6

DenTaku Advent Calendar 2021

DenTakuDenTaku

DenTakuのアドベントカレンダー2021

これは何なのか

電タクが12/25までに何かを作る一人アドベントカレンダーです.
(特に意味のないADVENTARへのリンクはこちら)

ルール

  1. 12/25までに何かを作ります
  2. 投稿タイトルは日付です
  3. 何もしない日があっても良いことにします

よろしくお願いします

参考文献リスト
DenTakuDenTaku

12/01 (厳密には11/24~11/30)

したこと

  1. コンパイラと開発補助ツールを作ることに決めた
  2. 周辺知識のインプット
詳細

1. コンパイラと開発補助ツールを作ることに決めた

最近困りごとがほとんどなく,何を作るか結構迷いました.

どうせ何もないならと前々からしたいとは思っていたコンパイラ作りにします.
去年はハードやったし,今年のセキュキャンはコンパイラコースなかったし.

電タクの環境とか

  • maxOS Big Sur version 11.5.2
  • (多分) Rust 使います.rustc 1.56.1

自分のレベル

  • 字句解析,構文解析の入口の話はわかる
    • LL(1)で構文解析表の手計算とか院試でやったので
  • Lexer,Parserを使ったインタプリタは作ったことがある
    • 簡単な型推論とかもあるやつ
  • マイコン上で簡単なアセンブリを書いたことはある

身につけたい

  • ASTから実際のアセンブリや実行ファイルを作る
    • ある程度最適化もしたい
  • その他手を動かして初めて身に付くあれこれ

正直自作言語の仕様とか考えててもRustでいいじゃんになるんですが,開発補助ツールを自分用にチューンナップしてなんとか価値を見出したいです.

2. 周辺知識のインプット

  1. プログラミング言語処理系の講義資料を復習しました.(自分のコード)
  2. 低レイヤを知りたい人のためのCコンパイラ作成入門のオート変数の実装まで(自分のコード)
  3. 同記事を最後まで目を通した

TODO:

  • 仕様を切る

ひとこと

卒論との兼ね合いなのでなんとも言えませんが,自作言語に型推論までつけて自作エディタか自作プラグインでいい感じにできるところまで持っていきたいです.

DenTakuDenTaku

12/02

したこと

  1. 独習アセンブラ読んだ
  2. μ再帰関数の定義とか確認した
  3. 仕様として入れたい概念について考えている
詳細

1. 独習アセンブラ読んだ

今回はアセンブリを吐き出そうと思っているので,結局いい感じにアセンブリで書ける必要があるなと思って読みました.

読んで解決できていない疑問点

  • スタックは簡単に使えるけどヒープってやっぱり自分で allocate するんですよね?
  • 吐き出されたアセンブリのレベルでの最適化の方法
  • 高階関数やカリー化の方法(普通に関数へのポインタとか使えば実装できる...よね?)

ここら辺を解決しようと思って気づいたんですが,手持ちにコンパイラ関係の本が一冊もなかったので明日にでも本屋に行ってきます.この記事とか参考にさせてもらいます.

2. μ再帰関数の定義とか確認した

高橋計算論で復習しました.良い本なのでまた一から読みたくなったんですが,流石に脱線が過ぎるのでやめておきます.

オレオレ機能だけで構成したらベンチマークを取る段階で Ackermann関数が計算できないことに気付くとか悲し過ぎるのでちゃんとμ再帰関数を帰着させられるミニマムな機能を優先的に考えようと思います.
まあ普通に関数の再帰呼び出しを制限なくできるようにすれば最小解関数がどうとか気にしなくても良い気はしますが.

3. 仕様として入れたい概念について考えている

考えている途中で今日はタイムアップです.
自分が好きな概念をとりあえず列挙中です.

  • ラムダ計算
    • 関数適用や関数抽象みたいな方
    • 型もつけやすそう(適当言っています)
  • ブロック単位の意味論が関数型プログラミング like
  • イテレータ
  • トレイト
  • 代数的データ構造 (struct は組み込まない方向で考えている)
  • データの所有権
  • 参照,可変参照
  • 並列計算
    • 特に fork-join

Rust や Haskell でいいじゃんとか言ってはいけない.


TODO

  • 入れたい概念をもう少しブラッシュアップ
  • 仕様を切る
  • コンパイラの本を入手する

ひとこと

このアドカレ,毎日進捗報告会があるみたいで大変です.今日みたいに研究にたくさん時間を割いた日には内容が薄くなる......
あとヒープ領域をどうしようか迷っています.効率を無視してスタックで全部なんとかして誤魔化すのも無しではないのですが,やはりクロージャ的なものの実装に結局ヒープが必要になる気がしているのでとりあえず勉強してみるって感じになりそうです.
余談ですが参考文献リストを自分用に冒頭につけることにしました.

DenTakuDenTaku

12/03

したこと

  1. ドラゴンブックを入手
  2. ヒープをどうするか考えた
  3. 自作言語関係の記事を読んだ
  4. 自作言語の仕様を考え中
詳細

1. ドラゴンブックを入手

コンパイラの構成と最適化が欲しかったんですが,ドラゴンブックも軽くみて悪くなかったので入手しました.まあどうせ必要になればコンパイラの構成と最適化も読めば良いしリファレンスが多いのは良いことなのでいいかなと思っています.

2. ヒープをどうするか考えた

3にも繋がりますが他のコンパイラをセルフホストしている方のレポジトリを見ると大体 musl とかを使って malloc は既存のものを使っている人がほとんどでした.

自分は勉強で実装するのでドラゴンブック等を参考にシステムコール brk などを使いながら自分で実装しようと思います.

3. 自作言語関係の記事を読んだ

QiitaやGitHub等に上がっている自作言語を眺めまていました.

四則演算をする抽象構文木までは構成してそのあとはインタプリタとして実行する言語が多く,次点でLLVM-IRを構成するものが多かったです.アセンブリを吐き出すものは少なかったです.

読んで参考になった記事をまとめておきます

4. 自作言語の仕様を考え中

自分が好きな言語である Rust,Haskell,OCaml などに想いを馳せつつ,自分がプログラムを書くときにどういう機能があると嬉しいかをずっと考えています.

例えば自分は真偽値やOption型などを含め本質的に例外処理的なコードを書くことが多いのでデフォルトでモナディックに書けたら嬉しいかもなとか考えています.

もう少しブラッシュアップしていこうと思います.


TODO

  • 自作言語の仕様を考える

ひとこと

今日は私用でほとんど作業していません.言語仕様の決定が一番大事なパートではあるのでDay07くらいまではかけてもいいかなと思っています.ちなみに自作言語の名前はDACにしようと思っています.(DentakuAdventCalendarです!)

DenTakuDenTaku

12/04

したこと

  1. ドラゴンブックを少し読んだ
  2. 言語仕様考え中
詳細

1. ドラゴンブックを少し読んだ

ドラゴンブックを全て読んでいると12月が終わってしまうので気になるところを掻い摘んで読んでいます.
今日は主に中間コード表現とヒープ管理について読んでいました.

ドラゴンブックは初めヒープの説明をした後手動解放の問題点を指摘してGCの話を始めるのですが,正直RustがRcなどを除いてメモリの安全で静的な自動解放を実現していることを考えると自分はGCが走る時間がもったいなく感じてしまうので自分の言語はGCを使わない実装にしたいという気持ちがあります.

まあ口ではなんとでも言えるので早く仕様を決めきって手を動かしたいです.

2. 言語仕様考え中

考え中です.

方向性的には主要機能は小さく抑えつつ標準ライブラリで厚くサポートする言語にしようと思って設計しています.
Haskell のように筋の良い抽象化を提供しつつそれを利用してサイズは小さく機能はたくさんを目指そうと思います.


TODO

  • 自作言語の仕様を考える

ひとこと

今日は午前に大学で用事があり午後はアルバイトをしたのでほとんど作業していません.
ある私事が片付いたので今後はより時間が取れる気がします.

DenTakuDenTaku

12/05

したこと

  1. hoge
  2. fuga
詳細

1. hoge

hogehoge

2. fuga

fugafuga


TODO

  • ABC

ひとこと

このスクラップは2022/12/14にクローズされました