プログラミング言語Palan開発日記

昨年(2017)の7月ごろから衝動的にコンパイラを自作し始めました。完成には程遠く、完全に自己満足の世界なのですが、誰かの為になることも書けるかも(?)知れないので日記・覚書をここにつけてみます。
メインiPhone更新なのでレイアウト変だったらすみません。

Githubリポジトリ: Palanソースコード(C++)

ヒストリ

久々に仕事でコーディング(何年ぶり？楽しい)→Javaの冗長なスタイルとGCの無能さに絶望→Goを味見(新時代？)→GoからGo(Cスタイルでないと辛い)→理想の言語落書き→作れるんちゃうん？(勘違い)→アセンブラ味見(わかった気になる)→cコンパイラ作った人発見→これぐらいなら作れるんちゃうん？(勘違い)→適当構文木からアセンブラ生成で動く→簡単じゃん(大勘違い)→パーサジェネレーター探し(昔よりいいのあるんじゃ？)→やっぱBoostだよね→コンパイル時間とエラーがBoost(・・・)→結局コンフリクトに苦しみつつBison+flexで安定。→いい感じにC++で書けて調子に乗る→Rustを知る→車輪の再発明に感じモチベダウン→LLVM知る→アセンブラ生成は時代遅れ？orz→情報遮断してモチベ維持→Qiita始めればモチベあがる？→イマココ

経緯はこれぐらいしてこれから技術的なネタを順次追記する予定。。

関連技術ネタ

C++でbison(パーサジェネレーター)を使う　(2017/10/25)
[bisonでコンフリクトメッセージが出た時の対処方法(1)]
(https://qiita.com/tosyama/items/1bd4f69fa6fe4ee9494f) (2017/10/29)
bisonでコンフリクトメッセージが出た時の対処方法(2)(2017/10/30)

日記

上の方が最新です。時系列で読みたい人は下から読んでね

7月1日　２年目突入

開発からおよそ1年経ったことと、日記が増えたので2年目の日記記事を立ち上げます。
2年目日記

6月28日 Mangling

本質的な設計になってるかはわからないけど簡易型チェックを実装した。おまけでオーバーロードも実装できてしまった。オーバーロードを実現するにはソースレベルでは同じ関数名であってもアセンブリレベルでは別名をつける(mangling)必要がある。簡易実装だけど、関数名と引数の型をつなげた文字列のハッシュを生成してBase64もどきの文字列をくっつけることで別名を生成した。
ちょっと困ったのがハッシュでBase64もどきの文字列を生成する際、6bit(0-63)を1文字に当てようと思ったけど、A-Za-z0-9_だと63文字であと一文字足りない。エスケープ文字にする手もあったんだけど”.”も使えることがわかったので、.を加えた64文字で生成した。
ハッシュ値の衝突の可能性はないとは言えないけどまぁ大丈夫だと思う。

6月26日 なかった

コンパイルエラー実装してたら気づいてしまった。代入元/先や関数の引数の型チェックがない。そういえば、どのように実装しようかの方針も何も考えてなかった。コンパイラのメインのお仕事の一つである型チェックが無いのは片手落ち感半端ない。今さらだけど、これから考えよう。

6月23日 エラー処理

面倒くさい。でも、プロダクトレベルにしたいなら必須。でも、やっぱりめんどいよー。

6月20日 systemにハマる

エラー強化の自動テスト作ろうとテストコードの作成中。単にsystemでコマンドライン叩いてその結果を検査するだけなんだけど。
そこで、ちょっとミスって出力パス間違えてたら、palanコンパイラのなかのldやasコマンドがコケて失敗で終了したのに、なぜかテストコードが正常で終わる現象が発生。
ldコマンドの結果をそのままreturnしてるだけのつもりだったので、なんで失敗にならないか分からずハマった。
結果からいうと、ldコマンドもsystem関数で実行してるのだが、その戻り値が子プロセスの戻り値だと思い込んでたのが原因。よく調べてみるとLinuxの場合、子プロセスの戻り値は16bit整数の上位8bitに格納されていて、取り出すにはWEXITSTATUSを使えとのこと。
テストコードがsystemでコンパイラ実行 => コンパイラがsystemでld実行 => ld失敗し戻り値1 => systemは256を返却 => コンパイラは256を返却 => systemは下位8bitのみを使うので 0を返却 => テストコードはコマンド成功と判断。
知ってる関数と思って調べずに使ってハマるパターン。

6月17日 masterマージ

パーサを分離してjson形式のASTを出力し、jsonからpalan内部の構文木を構築、ついでに関数の定義が後ろにあっても関数呼び出しできる対応のmasterマージ完了。
次はコンパイルエラー表示の強化を考えている。今はbisonで検出してる構文エラー以外はAssertでとりあえず終了させている。そこを、ちゃんと処理できるようにして、また、ソースのどの位置でエラーかも出したい。ソースの位置は最終的にはアセンブリ出力のとこまで伝達してデバッグ情報出力できるようにしないと、gdb等のデバッガでデバッグが困難になりそうなのでその下地づくりでもある。

6月16日 感覚麻痺

ようやく新パーサのコードが出来てきて以前までのテストが全部通るようになった。罠にハマることもほぼなく、既存のコードやASTの仕様を確認しながら地道に実装していった。
でも、頭の中ではできているのに、あちこち確認するので手が遅くてなかなか進まない感覚。作業としては難しくはないけど性格的に苦手かも。あとはコマンドラインのソースにマージできたら一旦完了してエラーメッセージに着手予定。関数の後定義についても流れで自然にサポートできている。
まあでも、挫折の可能性も高いけどどう設計したらいいのか悩みながら、ちょっと間違うと意味不明に壊れるような精密機械のようなコードをやる方が趣味的には楽しいかも(？)。なんか麻痺してる？

6月12日 const

わかってる、わかってるんだよ。値を変えない参照やポインタにconstをつけないといけないことぐらい。わかっててやってんだよ。これぐらい見逃してくれよー。
↑自前プログラムでやってる分には面倒でつけてなかったconstだが、ライブラリを使い始めるとライブラリの文字列を自前関数に渡せないことが続出してグチる。

6月4日 Parser作り直し

jsonライブラリのおかげで、palanソースコードをパースして、ASTのjsonを出力する子ツールは大体できた。エラー処理など細かいところは残ってるけど、ここまではまぁ簡単。
このASTのjsonを使って、今までbisonから直接構築していたアセンブリ出力用の構文木を構築する機能を開発しないといけない。ここは、これまでのParserを参考にはできるがほぼ作り直しとなる。時間かかってしまうけど実装が完了すれば柔軟性はかなり高まる。
あと1カ月ぐらいで開発始めて1年か。。思ったのの半分くらいしか進まなかった。日記書き始めだったころは1年経てば浮動小数点の演算ぐらいはまでは辿りついてると思ったが甘かったなぁ。

6月1日 配列の配列の宣言

ATSの生成に手を付けたら今の配列の配列の宣言が気になってきた。どこが気になるのかというと、宣言時と実際に使うときの並びが逆になる点。

int32[2,10][5] aa; // intの2次元配列の配列
99 -> aa[3][1,9]; // 使うときは並びが逆

普通に考えたら混乱するのだけど、多次元配列は同じ並びだし、D言語も同じ構文もってるし、何よりパースした際に必ず要素の型から順番にパースできるので構文木の構築にも都合が良かったので納得してた。ただASTを挟むことでこの順番はどうでもよくなるので現在の仕様への疑問が出てきた。D言語以外の言語では逆順は避けているというのが現実。D言語でもC言語の記述スタイルは許容してる。
Java/C#あたりはC言語の並びで後置だった演算子をそのままの順番で宣言に持ってきている。これは分かりやすいようだけどC言語のようにポインタ演算子がないから成り立ってる。ポインタ配列を表現しようと思うと途端に破綻する。なので使うときと逆になるがD言語スタイルの方が柔軟性があるのだ。
でも順番も合わせたいとなるとGo言語のようになる。最初に配列の型がきて後ろが要素の型になる。これはGo以外ではあまり見ないが、Goのこの書き方を知る前から考えてたスタイル。Goは変数の宣言の際に変数名より型の宣言が後ろなのでそんなに違和感はない。型の宣言が前であるPalanで、Goスタイルにするかどうか悩む。

// スタイル検討中
[=5][=2,10]int32 aa; // intの2次元配列の配列 [=は固定長配列の意味
99 -> aa[3][1,9]; // 使うときと同じ

ただ今のPalanのポリシーの一つ、左から右へ流れるようにコードを書けるようにには合ってるかもしれない。
Goみたいに型の宣言を変数名の後ろにしないか？それは絶対ダメ! それが嫌でGoからGoしたのにぃ。

5月28日 Json

ASTの実装用にC++のJsonライブラリを探したところ、nlohmann/jsonが期待した通りかそれ以上の出来で感動すら覚えた。最初はメジャー?なDropBoxのjson11を使おうとしたけどjsonの構築には不向きでどうしたもんかと悩んだが、やってくれる人はいるものだ。nlohmann/jsonを使えば機能が整ってるので、あとは仕様を整えてASTのjsonを出力する実装するのはもはや単純作業。C++はC++98から知識が止まっててC++11については全然追いついてなかったけど、追加された仕様がとても使いやすくて驚く。個人的にはJavaよりも全然使いやすい。

5月27日 AST作戦

ということで、関数の後定義を可能にするために、ずっと後にやろうと思ってたAST生成の方を先に開発することに。作戦としては、まずはパーサーを分離してAST(抽象構文木)を表現するjsonを出力するexeを作成する。
本体コンパイラはAST作成exeを起動、jsonを読み込み、いままでbisonから直接構築していた構文木をjsonから構築するように変更する。
こうすることで後々、定数畳み込み等の最適化や静的解析のfilterを間に挟みやすくなるという作戦。
ASTのデータ構造体は他のコンパイラはNODE型とか定義して使うみたいだけど、なんか面倒だしどうせ専門知識ないし、、なのでpalanではオープンソースのjsonのライブラリを使ってそのままjson型でモダンに？開発するつもり。
時間はかかりそう。。

5月25日　オーバーロード

関数の後定義の仕様について、関数の戻り値が違った場合のオーバーロードも考えてしまっていたから混乱したみたい。オーバーロードは引数の違いだけ見るしかないということに気づいた。引数が同じで戻り値が異なる関数のオーバーロードは禁止でOK、とくにプロトタイプも不要と確信した。
ただ、実装の方が問題。関数コールと、実際の関数を表すインスタンスの関連づけを後回しにすれば簡単にできると思いこんでたが、ちょっと実装してみてわかったことは、関数が確定しないと戻り値も確定しないので、計算式などいろんなところに影響がでる。。結局二度読みみたいなことをしないと難しい。
これは将来的にやろうと思っていたASTの実装の方を先にしてからかなぁ。AST作るときにプロトタイプのようなものを生成するのが効率的と考えている。でも、ASTは詳細考えてないしパーサー部分、ほぼ作り直しだし、大変そう。関数の後定義サクサクできると思ってたのでちょっと気が重い。まぁ、前倒しになるだけといえば、そうだけど。

5月24日 仕様

関数の定義が先になくても関数コールができるようにする実装に手を付けたが、先のこと考えて手が止まる。
問題はコンパイルエラーを正しく出せるのかどうか。将来的に引数の省略や、関数名のオーバーロードを対応した場合に曖昧さを正しく判断できるのか。
今はパース時に関数の定義と合わせて引数の数と戻り値の数が代入先と、合っているかチェックできるけど、これを後回しにした上で判断する必要がある。
オーバーロードをする場合はプロトタイプ宣言必須にしてその場で判断しないと、後から判断は難しそうとか、いやいや利便性落ちるとか、だったやオーバーロード許さないという仕様にしたほうがいいのではとか、とはいえコンストラクタはオーバーロードできないと困るだろうとか、、
と、まぁいろいろ。これまでは細かい仕様はやりながら決めてきたところあるけど、ここである程度上記のような仕様は固めてから進めたほうがよさそう。

5月22日 dump機能削除

構文木のツリーと情報を出力するダンプ機能を削除した。作り始めたころはちゃんと思った通りにツリーが組めているか確認するのに必要だろうと思って機能いれてたけど、結局はほとんど使わず、最近は仮想関数なので実装が必要となる分、生産性の足かせにしかなってなかった。一般的にはどうかわかんないけど、このコンパイラの場合はパーサ→構文木構築の処理はそんなに間違えることはなくて、ほとんど構文木→アセンブリの処理の方でつまづくことが多い。
最終的には何かしらのダンプ機能はいる気はするが、実装はニーズが顕在化してからでいいと思っている。

5月21日 ABI変更

大分前から変更したかったが、PalanのABI(関数呼び出し規約)の変更に対応した。これまでは戻り値と引数のレジスタとかスタックが被らないようにしてたが、戻り値が1つの場合はC同等、戻り値が2つ以上の場合は引き数と同等のレジスタを戻り値に使うようなABIに変更した。これまでは引数と戻り値が被らない方がCから呼べるんじゃないかという何となくの考えでそうしていたけど、ふと、これは意味ないなと思い直した。
このABI変更で、戻り値が一つの場合はCとの互換性を担保しつつ、Palan独自の引数・戻り値が多い関数でも多くのレジスタを有効活用できるので、関数コールの処理速度を保てる。また、あとあと戻り値を次の関数の引数に流用する場合など、いろいろメリットがある気がしてる。

5月18日 配列の配列

やっと配列の配列(ポインタ配列のようなもの)ができた。実装しようとしてから3ヶ月半か、、スキマ時間での開発とは言え長くかかった。最初はちょい修正かと思ったが結局は土台の部分をかなり作り込む事になった。
宣言するだけで子のオブジェクトまでalloc、代入するとdeep copy、スコープ外れるとfreeする仕組みができた。

{
    int32[3][4] aa; // 配列の配列 malloc 5回
    int32[4,3] ma; // こっちは多次元配列 malloc 1回 
    xx -> aa; // aaへdeep copy
}  // スコープ外れると漏れなくfree.

次の実装候補を覚書程度に書いてみる

• ABI変更
• dump機能削除
• 関数宣言が先になくても関数使えるように
• finishフェーズでもコンパイルエラー出せるようにする
• チェーンコール
• 定数

5月17日 今度こそ

ようやく配列の配列の実装漏れとバグが枯れてきた(かも)。後は、ちゃんとしたテスト作って、バグ出たら修正して、リファクタリングしたら、今度こそ終わり。(・・・のはず...)

5月15日 距離感

5月に入って配列の配列の実装のゴールが見えてきた。・・・はずなのに、全然ゴールが近くなってる気がしない。なせだー！？

5月10日 なんとか

昨日の無駄処理部分なんとか直せた。ただどこをどう直したから直ったのかというのが自分でも理解できていない。本来ならこうあるべきかもという修正しては、テストが通らなくなって、通るようにデバックしてたらいつの間にか消えた。Diffでみてもよくわからん。
まだ関数の戻り値あたりが効率悪いコードになってるのでそこも直さないと。

5月9日 動くけど、、

デープコピーのコード部分、簡単に言うと「memcpy(p1[i],p2[i],16);」のような処理をしたいんだけど、下記のようなアセンブリになってしまう。

    movq -16(%rbp), %rbx    # p2 -> base
    movq -24(%rbp), %rdi    # i -> index
    movq (%rbx,%rdi,8), %rsi    # p2[] -> copy src for save
    movq -8(%rbp), %rbx # p1 -> base
    movq -24(%rbp), %rdi    # i -> index
    movq (%rbx,%rdi,8), %r11
    movq %r11, -32(%rbp)    # p1[] -> (save) for save
    movq -32(%rbp), %rdi    # p1[](save) -> copy dst
    cld
    movq $2, %rcx
    rep movsq   # deep copy

-32(%rbp)に書いて読み戻す無駄処理が生成される。ホントは下のようにスマートに出てほしい。

    movq -16(%rbp), %rbx    # p2 -> base
    movq -24(%rbp), %rdi    # i -> index
    movq (%rbx,%rdi,8), %rsi    # p2[] -> copy src
    movq -8(%rbp), %rbx # p1 -> base
    movq -24(%rbp), %rdi    # i -> index
    movq (%rbx,%rdi,8), %rdi    # p1[] -> copy dst
    cld
    movq $2, %rcx
    rep movsq   # deep copy

こんな感じのバグが出ると修正するか迷う。配列とストリング命令を組み合わせた際、レジスタの使用が衝突して退避する条件がちゃんと考えきれてないためなんだけど、直すのはかなり骨が折れそう。結構頑張ってるつもりなのにさらに考えろというのか。思考力が試されてる感じ。

5月4日 甘かった

メモリ確保・解放と同じ仕組みでDeepコピーもいけると思っていたが甘かった。ベースの部分でもう一捻り必要そう。複数の代入をサポートしたい関係上、シンプルな1対多の親子ではない複雑な関係があるのが難しいところ。
その中で設計というか造りのポリシーができるだけブレないように考えるのに時間がかかってる。ポリシーに一貫性がなさすぎると後の機能追加がさらに困難になる気がするので。

5月2日 スタックマシン・レジスタマシン

アセンブリについては大昔に基本を学んだぐらいで、昨年までは実践的なことは全くわからなかった。また、スタックマシン/レジスタマシンの言葉は聞いたことはあるが、何のことだかよくわからなかった。最近気になって調べるとどうもPalanは有限レジスタマシン的な実装になっているようだ。私の知識が無さ過ぎてgccが出力するアセンブリを参考に作ったので自然にそうなったんだと思う。一方@ruiuさんが短期間で作った8ccはスタックマシン的な実装のようだ。アセンブリを見てみると違いがよくわかる。なるほど、これならレジスタの取り扱いについては細かいことを考えなくてよいので、短期間でコンパイラ作成できるような気がする。レジスタマシンは使えるときはレジスタを使い、使用が衝突した場合はメモリに退避するコードを書く必要があり実装は複雑になる。それに比べるとスタックマシンは実装が簡単なのでとにかく動かしたいとか、なるべく環境に依存したくない場合は最適だと思う。逆にギリギリまで最適化して高速に動かしたい用途には不向きなのかなと感じる。
下記に簡単な同じ関数をアセンブルしたコードを示すけど、全然違うのが分かる。

// C言語コード
int64_t square(int64_t num) {
    return num * num;
}

# 8cc出力アセンブリ(スタックマシン的)
square:
        nop
        push %rbp
        mov %rsp, %rbp
        push %rdi
        movslq -8(%rbp), %rax
        push %rax
        movslq -8(%rbp), %rax
        mov %rax, %rcx
        pop %rax
        imul %rcx, %rax
        cltq
        leave
        ret
        leave
        ret

# gcc最適化なし出力アセンブリ(レジスタマシン的)
square(long):
  pushq %rbp
  movq %rsp, %rbp
  movq %rdi, -8(%rbp)
  movq -8(%rbp), %rax
  imulq -8(%rbp), %rax
  popq %rbp
  ret

// Palanコード
func square(int64 num) -> int64
{
        return num * num;
}

# Palan出力アセンブリ
square:
        pushq %rbp
        movq %rsp, %rbp
        subq $16, %rsp
        movq %rdi, -8(%rbp)     # arg -> num
#{
        movq -8(%rbp), %rax     # num -> %accm
        imulq -8(%rbp), %rax    # %accm * num
        leave
        ret
#}

rspレジスタのsubq 等がなければPalanも最適化なしのgccレベルのコードになるんだけど、それをやるには関数の中で何も関数を呼んでいないことを出力前に判断しないといけない。将来的には可能な気がするけど、今の設計でそこまで達するのはちょっと厳しいなぁ。(2019/1/22 最適化追加してgccと同じコードが出るようになりました!)

5月1日 好循環

随分長くかかったが、配列の配列の完成が見えてきた。あとはDeepCopyをAllocと同じ要領でやれば良さそう。アクセス部分の実装は、苦しむかと思いきや機能追加というよりリファクタリングのみとなった。アサートを解除するだけで一応動いて、非効率なアセンブリになってる箇所を確認したら、アドホックなコードになってるところがあったので現在の設計に直すと、正しい出力かつシンプルなコードになるというぐあい。
今のところ新しい設計が上手くはまって好循環になっている。この設計に大分依存してるのではまらないケースが出てくるのが怖いが、そのときはその時で、時間かかっても再設計しなおして乗り換えると思う。古い設計引きずってるとロクなことない。

4月25日 いつやるか？今でしょ！

機能実装中にできの悪いコードが気になってきたときに、某林先生の名言が頭によぎる。仕事だとどうしてもリファクタリングは後回しになるけど、個人プロジェクトはその制約がない。実際すぐにやった方がいいと思う。後回しにしてると忘れたり、ToDoにしておいても、始める際に既存コードを理解するのに時間かかる。すぐやるとコードリーディングの時間とその後のメンテナンス時間を削減できるので長い目で見た場合効率的なはず。という事で、気になった変数宣言、初期化辺りのリファクタリングを今からやろうかな。

4月24日 やってみないと

配列の配列のメモリ確保/解放は、作っては壊しで進めてたけど、結局、型に紐づけて関数とその呼び出し方を登録する形で落ち着きそう。必要であれば型に合わせたメモリ確保と解放の関数を構文木を組み立てて作り、必要な場合はそれを呼び出す。出来てみれば、そんな難しい設計ではないけど最初からなかなか思いつかないんだよね。

4月20日 心臓に悪い

クラスにメンバー追加して自動テストが走ったら下のようなメッセージが、、

"malloc.c:2394: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)' failed. "

ん？どこかメモリ壊した？ネットで対策探すが、どこかでオーバーフローかアンダーフローしている以外ないとの事。どこでミスったか簡単に見つける方法もなさそうで、これからの長いデバッグ地獄を想像して呆然。C++glibのデバッグモードONにすれば何かわかるかもと再コンパイルのためにオブジェクト消したり色々してたら出なくなった。
落ち着いて考えるとmakeのヘッダーの依存関係を更新してなかったので、古いデータ構造のオブジェクトとリンクしたんだろうとわかり安堵。ヘッダーの依存関係の更新をコンパイル時間早くしたいから手動にしてのが仇になった。それにしてもこれでこのプログラムは終わったかもと思ってビビった。

4月19日 サブタイトル

最新が上になっているというのもあり、日付だけだとあまり読む気になりにくいんじゃと思い、各日記にサブタイトルつけてみた。そもそもアクセスが少なくて読まれないというツッコミもあるが。

4月12日 モチベーション

うーん。今度は、今の配列の配列のメモリ確保と解放の実装も行き詰まる気がしてきて、熟考モード。C++のoperator new や deleteみたいに型に関数を関連付けるべきと思ってきたけど、型のデータ構造がいろいろ追いついてない。今度は型の設計の見直しが必要かも。
配列の配列を実装するという具体的な目的を持って進めることで、本来の設計をいろいろ考えられるのはいいことなんだけど、言語的にできることがなかなか増えないのでモチベ維持が問題。ただ、これらの基礎部分ができると、ある時から一気に進む予感はするので、その予感をモチベに変えていくしかないなー。

4月11日 古いビル取り壊し

代入クラスの大規模リファクタリングが完了。隣に新しいビルができて処理の引っ越し完了。最後に古いビルを取り壊すのは(使わなくなったソースコードを一気に削除するのは)、かなり爽快。どう動くのかわからなくなってたコードが整理されて理解しやすくなった。
以前コードレビューするとき、ポリモーフィズムはコードリーディングで処理が追いづらいからあまり好きになれないなぁと感じてた。が、今回のリファクタリングは完全にポリモーフィズムのお世話になりました。疑ってすみません。

4月3日 リファクタリングのコツ

未だ見た目進んでない。。alloc/freeの造りを全展開しようとして、代入の修正で詰まった。他の言語と比較するとpalanは代入がかなり複雑な文法となる。今までは内部データの共用体でやりくりしてた。いつか作り直さないとと思ってたけどさすがに限界。
大規模なリファクタリングは何度かやってるけど自分なりのコツがある。よくテストだけ残して全部書き直す人が多い気がするけどそれは危険と思う。出来上がるまでほとんどのテストがNGになるのはかなりのリスク。挫折の可能性も高い。自分のやり方としては隣にビルを建設するイメージ。部屋ができたところから新しい部屋に引越す。部屋ができていない場合は古い部屋をそのまま使う。全て引っ越しし終わるまではビルが二つになり、さらに引っ越しの道案内の仕組みもいるからリファクタリング途中はコードが2.5倍に。でも古いコードが少しずつ、安全に、新しいコードに入れ替わっていくのはちょっと楽しいかも。

3月26日 コンパイラの難しいとこ

コンパイラ作ってて思うこと。bisonとかあるおかげでパーサとかはそんなに難しくない。それよりも型や式が入れ子になってきた時にレジスタの取り回しとかとかスタックとかどうデータ壊さずに無駄なアセンブリコードを出力しないようにするのかが難しいように思う。よくあるコンパイラ解説はパーサに焦点があたってたり、出力は結局独自VMのものが多くて構文木からリアルなアセンブリの変換の解説はあまり見ない。ドラゴンブックとか読んだことないけどちゃんと書いてあるんかな？独自にやるのが楽しいので買うとか読むとか考えてはないけど。
最近はLLVM使えば解決ってことなのかな。

3月20日 設計メモ作成

細かい設計をあちこち追加したので、だんだん自分がした設計をそらで覚えていられなくなってきた。たまに、自分でここどうなってるっけ？このパラメータなんだっけとコード読まないとわからないことも多くなった。
一旦この辺でハッキングガイドという形で設計をメモっとくことにしよう。。

3月16日 土台づくり

配列の配列の実現の目途は立っているけど、ちゃんとした設計・実装にするのにかなり時間がかかってる。まだまだかかる予定。アドホックなコードにすれば早く先に進めそうな気もするんだけど、後から直すのが大変になりそうなんで今やらねばっ。でも、やってるうちに、ここも今やらねばっっとなって、作業の区切りをつけるのが難しい。
こんな感じで外から見た機能は全然進んでないんだけど、ただ、後でやろう思っていた基礎的な土台が前倒しでだんだん造れている気はする。

3月9日 何言ってるかわからないと思うが

なんか構文木組み立てだけでうまくいってしまった。何言ってるかわからないと思うが、卵だけつくって、このあとどうしようと悩んで歩いていたら、勝手に鶏がうまれてて卵もつくってくれいた。
メモリ確保/解放の実現ができたので、あとはリファクタと漏れをつぶしながら、全体設計を見直して洗練しないと。まだまだ時間はかかる。

3月8日 ハマる

やはり配列の配列実装にはまる。構文木を組み立ててそれを埋め込むことでできると思って、それでやってみているんだけど、微妙にうまく実装できていない。何かキャストみたいな構文を追加すればうまくいく気もするがそれもよくわかってない。
構文木組み立てでやると、レジスタの取り回しは考えなくてよくなるのでそこは楽なんだけど、自動メモリ確保/解放する仕組みが鶏と卵みたいになってきて、わけわからなくなってくる。経験的には試行錯誤しているうちに、突然わかることが多い。
しばらく試行錯誤かな。

2月27日 もとの道

ひと通りLoopができる土台ができたので配列の配列の実装に戻ることに。配列の配列とはいえ構造体やクラスの土台となる重要ポイントと思っている。でも、いい設計がパッと思い浮かばないのでしばらく試行錯誤しそう。

2月26日 論理演算？

ようやく論理演算(論理AND/OR/NOT)のリファクタリングができた。書いてて思うのは&&とか||つて論理演算って呼び方で合ってるのか自信がない。条件演算の方が正しい呼び方なのかね? コード書いててもこれって特殊なif文ぽいアセンブリ出力してるので、いわゆる論理和・論理積などの演算とは全然違う。
でも、まぁいいか。

2月20日 8クイーン問題

論理演算が実装できているので大分プログラムっぽいものが書けるようになってきた。
二次元配列と複数の戻り値を使って、8クイーン問題も書けたよー。答えは92で合ってるよね?

ccall int32 printf();
ccall exit();

func initBoard(byte[8,8] >>board)
    -> byte[8,8] board
{
    int32 x,y = 0,0;
    while y<8 {
        while x<8 {
            0->board[y, x];
            x+1->x;
        }
        y+1->y;
    }
}

func queen(byte[8,8] >>board, int32 x, y)
    -> byte[8,8] board, int32 count
{
    0 -> count;
    int64 xx,yy;

    x-1 -> xx;
    while xx >= 0 {
        if board[y, xx] { return; }
        xx-1 -> xx;
    }

    x-1, y-1 -> xx, yy;
    while xx >= 0 && yy >= 0 {
        if board[yy, xx] { return; }
        xx-1, yy-1 -> xx, yy;
    }

    x-1, y+1 -> xx, yy;
    while xx >= 0 && yy < 8 {
        if board[yy, xx] { return; }
        xx-1, yy+1 -> xx, yy;
    }

    if x >= 0 { 1 -> board[y, x]; }

    if x == 7 {
        count+1 -> count;
    } else {
        0 -> yy;
        while yy < 8 {
            int32 cnt;
            queen(board>>, x+1, yy)->>board, cnt;
            cnt + count -> count;
            yy+1 -> yy;
        }
    }

    if x >= 0 { 0 -> board[y, x]; }
}

int32 count;
byte[8,8] board;
initBoard(board>>)->>board;

queen(board>>, -1, -1)->>board, count;

printf("answer: %d\n", count);
exit(0);

2月19日 最初の構想と心変わり

まだ満足できるコードではないのでリファクタリングは必要だけど論理演算の実装はできてる。論理演算って意外と面倒なのね。
一旦できたのでサンプルコード書いてたら、やはり既存の検討もれバグと、あとで実装しようと思ってそのまま忘れてた実装もれ発見。これは直さんと。。で、デバッグしてて、ふと、多次元配列は今の実装はa[x,y]と書くと、xの一次元配列がy個になるようにしていた仕様を変えることを突然決心。x,yの順で書けた方が数学的には自然かなと思ってそうしてたんだけど、言語、アセンブラレベル見た添字の計算がどうも自然でない。a[y,x]とした方が左から流れるように添字の計算ができ、直感とあって腑に落ちたのでそちらにすることにした。まぁ、C言語も同じような順序なんで書く側も気にしないはずだし。
実装していくと、最初の構想から考えが変わることが結構あるなぁ。

2月12日 クイックソート

論理演算(and/or)はないけど、クイックソートぐらい書けるんじゃないか? と思って書いてみた。

ccall int32 printf();
ccall exit();

func show(int16[10] data, int32 n)
{
	int32 i=0;
	while i<10 {
		printf(" %d",data[i]);
		i+1 -> i;
	}
	printf("\n");
}

func quicksort(int16[10] >>data, int32 left, int32 right)
	-> int16[10] data
{
	int32 i, mid;
	int32 temp;

	if left >= right {
		return;
	}

	left -> mid;
	left+1 -> i;
	while i<=right {
		if data[i] < data[left] {
			mid+1 -> mid;
			data[mid] -> temp;
			data[i] -> data[mid];
			temp -> data[i];
		}
		i+1 -> i;
	}
	data[left] -> temp;
	data[mid] -> data[left];
	temp -> data[mid];

	quicksort(data>>, left, mid-1) ->> data;
	quicksort(data>>, mid+1, right) ->> data;
}

// start
int16[10] data;
int32 i=0;

// init data.
while i<10 {
	i*13 % 9 -> data[i];
	i+1 -> i;
}

// sort
printf("before:");
show(data, 10);
quicksort(data>>, 0, 9) ->> data;
printf("after:");
show(data, 10);

// flush stdout.
exit(0);

再帰ができないバグ発見(汗)。直した後は思った通りに動いてちょっと満足。今のところ、他の言語との目立つ違いは代入演算子と、関数呼び出し時の入力と出力が明確になっているところかな。
">>"って何?と思う人がいるかもしれないので補足すると">>"は所有権の移動(参照渡し)です。所有権を手放した変数はどこからか所有権を取るまでは使えません(っとなる予定)。

2月11日 if文追加

勢いでif文と比較演算子実装完了。これでようやくプログラムっぽいのが書けるよーっと思ったのもつかの間、やっぱり論理演算ないと厳しいことに気づいた。。
ベースの作り直しが発生すると作業量が増えてしまうので、あまり今の時点で文法増やしたくなかったけど、論理演算まではやってしまおうかな。

2月8日 先人

C言語の副作用がありそうな文法を、こうすればいいじゃないかなと考えたものが、最新の言語に全く同じものがあって、そうだよなぁと思うことが多い。例えば if の後の{}の省略はいろいろ議論のネタになるけど、(個人的には省略する派)、ifのあとの()を省略して{}必須にすれば、タイプ量も減ってそんな負担にならないのではと思い始めたら goはそんな仕様になってた。また、今のPalanの作りだと構造体が全てヒープ確保になりそうだけど、スタックのほうがいい場合がありそうなので、参照と値をclassとstrutで分けた方がいいかもと考えていたら、Swiftはそうなっていた。すでに先を越された感はあるけど、考え方はそんな間違っていないとの自信にはなる。

2月5日 安全装置

基礎的なwhile文の実装はできた。実装ミスってテストが無限ループなると困るので、時間がかかったテストは落とす仕組みも入れ込んだ。(2/9 案の定無限ループやらかしたが、この仕組みがちゃんと効いて自分にgoodjob!)配列の実装(動的alloc/copy)に比べると大分実装楽だなぁ。比較文はほぼ空だけど今のうちしっかり作っておいた方がよさそうなので、if文も勢いで実装しようかな。

2月2日 ループ

配列単体はできたので配列の配列をやろうかと思って進めてたけど、結局ループのアセンブリを安全に出すコードを書かないとメモリ確保もできないと気付き、先にループから実装することにしました。
ループができたら、プログラムぽいものがようやく書けるようになるなぁ。

1月22日 ハマる

前回後で痛い目に遭うと書いたが、早々に痛い目に。テストは動いているけど出力アセンブラが怪しいのを調査して10行直すのに1ヶ月かかった。。まぁ仕事が忙しくなったのとiPhoneからssh経由でコーディングという変態的な事(?)をしてるからだけれども。今の環境だとgdbのブレークポイント使えないのでハマると大変。

12月4日 じっくり

多次元配列はおそらくできた。おそらくというのはデータ受け渡しの新設計に穴があって複雑なテストが通らないから。先に早く進みたくなるので、無意識にやばいテストケースを避けがちになるけど、ここは肝なのでじっくり納得するまでリファクタしたい。いい加減にすると後で痛い目に会いそう。

12月1日 簡単に上手くいくと不安

新設計が功を奏したのか、ちょっとの変更で1次元配列が動くようになってしまった。エラー出して直しながら動作を理解する予定だったので何で上手く動いているのか把握できていない。ちょっと不安。次は多次元配列着手かな。

11月29日 設計やり直し

未だに配列実装が終わらない。というかexpression 間のデータ受け渡しの設計が悪くて配列に対応できず、新設計への修正に労力を割く羽目になってた。ようやく既存テストコードと超シンプルな配列テストが通るようになったけどまだまだ道のりは長い気がしてます。。

11月14日 文法大転換

思い立ったら吉日で、代入の文法修正完了。配列対応は苦労してるのに、この文法の大転換はあっという間に直せた。コンフリクト16個出たのは焦ったけど、構文解析というか定義ファイルの書き方には大分慣れたかな。

11月13日 代入に悩む

うーん。配列の左辺値のインデックスを先に評価するやり方を考えていたら、文法を変えて、右辺に持って行きたくなってきてしまった。そもそも代入がなんで等号=なんだというの疑問がでてきて、この代入式の元祖FORTRANの設計がイマイチな気がしてきた。
プログラム初心者がよくはまる a=a+1が理解できないのもそこが原因だし。例えば a+1 => a　など、アロー系の演算子にて、左から右に自然に評価すればいいのにと思う。FORTRANでは => はポインタの代入だし、もう何なのかと思う。変数初期化の　int i = 3　は数学でもあるだろうし、そこは違和感ないのでそれと合わせたんだろうな。左から自然に評価しようとすると、後から使うためにメモリに保存したりとかして出力アセンブリも美しくない。a+1 => a の構文にしてしまうと、マイナー言語まっしぐらと思うけど、どうせ流行るわけないし、理想の言語を追求したい気持ちの方が強いかな。
お、R言語は　<- でも -> でも代入いけるのか。<- は a < -3 のとき比較なのか混乱しそうだけどね。

11月8日 左辺値の評価タイミング

配列の実装考えてたら、左辺値の評価するタイミングに迷ってしまった。例えば下記の時

a[0] = 0; a[1] = 0;
index = 0;
a[index] = (++index);

indexをインクリメントしたあとの1はa[0]にセットするか、a[1]にセットすべきか。調べたところ、Cではコンパイラ依存(gccはa[0]/clはa[1])、Javaでは左辺値を先に評価して確定(gccと同じ)のようなので、先に評価するで決定。実装は後がやり易そうだけど、コーディングする側から見たら、確かに先評価が直観的だよね。うーん、自社のみの開発が楽になる方向に仕様を倒すMicrosoftの社風が垣間見える。。

11月1日 マージ完了

下記masterマージ

• 配列の様な大きなオブジェクト変数の取り扱いのサポート。
• 普通の変数の様に宣言するとヒープからメモリ確保。スコープから外れるとフリーされメモリリークしない(はず)。
• 代入によるコピー。オーナーシップの移動(いわゆるユニークポインタのような仕組み)
• オーナーシップ移動の演算子は&とさんざん迷った結果、<<に決定。こっちの方が直感的なはず。でも、今度はビットシフト演算子どうしよう問題発生。

10月30日 開発スタイル

基本、とにかく動くコードを作る→動いた→自動テスト修正→気のすむまでリファクタリングで進めている。リファクタリングのときは、修正したあと、コンパイル通らないとわかっていても、コンパイルしてエラーになったコードを見直してチェックするスタイルでやってる。最近、C++型推論autoを多用するようになったが、コンパイルでどこか引っかかるだろう思ってたところがコンパイルエラーにならずに通ってしまうコードがあって恐い。autoは使いどころを選んだ方がいいかも。でも型を打つの面倒で使ってまう。

あと、ヒープメモリ不足でmallocからNULLが来た場合の対応入れてないけど、どうするか悩み中。当面対応は大分先になると思う。今はセグって落ちるはず。メモリ不足時の対応って、復帰あきらめてどう安全にプログラム停止させるかしかないよね、きっと。まぁ、いずれにせよ速度落ちたりコード増えることは気にせずに、すべてのmallocにNULLチェックは必須なんでしょうね。

実装済み 10月25日時点

• 整数(符号有/無し)1/2/4/8バイト変数
• ブロックによる変数スコープ
• トップレベルのエントリポイント(main関数はやめた)
• システムコールの呼び出し
• C言語関数の呼び出し(浮動小数点除く)
• Palan関数コール
• 複数の名前付き戻り値
• 戻り値、引数の型宣言の省略(直前と同じ型になる)
• 整数の四則演算
• 複合文 : a,b,c = 1,2,3;やa,b,c = function(x);みたいな書き方できる。
• a,b = c/3; と記述するとbには余りが入る。

覚書

• 実現出来るかわからないけどNULLを使わせないというコンセプトも持ってるが、配列のからコピーせずに要素を取り出す等の用途向けにらswapを演算子<->等を組み込むのは有用かもしれない。
• 数値計算などパフォーマンス上げる為にfreeをしないモードを入れてもいいかもしれない。
• 関数名はソースで使用する名前と実質的な名前二つ管理する必要がある。
• 名前付きブロック。宣言した時点でメモリ確保してしまうので、子のブロックで親のブロックの変数を宣言できる方がいい。ループ内の振る舞いは要検討。