500行以内で自作言語作ってみた

はじめに

昨今、Rustの登場によりプログラミング言語は複雑化しつつあります。（彼にRustを貶す意図はありません）
この現状を打破するため、私は最高にシンプルで完璧な言語作りに取り組みました。（彼は冗談を言っています）
最終的に当初の目論見とはかけ離れた言語になりましたが、その過程で苦労したことなどを綴っていこうと思います。

完成品はこちらになります

一応GCCでコンパイルして実行すれば乱数生成器が動くようになっています。
https://github.com/sxclij/sxcscript

特徴

C言語かつ500行以内のソースコード。（C言語を触ったことのある人なら無茶振り度合いがわかってくれるはず...）
動的メモリ確保なし（多分）固定長配列最高！
3種類の記号で記述可能。（なんというシンプル！
使用ライブラリはfcntl.h,stdint.h,unistd.hのみ

500行で収めるために

トークナイザを限界まで小さくした

実物を見てもらったほうが早いと思います。

void sxcscript_tokenize(const char* src, struct sxcscript_token* token) {
    struct sxcscript_token* token_itr = token;
    *token_itr = (struct sxcscript_token){src, 0};
    for (const char* src_itr = src; *src_itr != '\0'; src_itr++) {
        if (*src_itr == ' ' || *src_itr == '\n') {
            if (token_itr->size != 0) {
                token_itr++;
            }
        } else if (*src_itr == '(' || *src_itr == ')' || *src_itr == ',' || *src_itr == '.') {
            if (token_itr->size != 0) {
                token_itr++;
            }
            *(token_itr++) = (struct sxcscript_token){src_itr, 1};
        } else {
            if (token_itr->size == 0) {
                token_itr->data = src_itr;
            }
            token_itr->size++;
        }
    }
}

はじめは100行程度ありましたが、あらゆる機能（文字リテラルなど）を省くことで21行に収めることができました。

右辺値、左辺値の評価を省いた

変数が左辺に来たときはそのアドレス、右辺に来たときはその値として評価する必要がありますが、それを省くことで100行近く短縮できました。

プリプロセッサを削除した

プリプロセッサだけで200行を超えてました。
というかdefineとかいる...?関数定義で良くない...?
「プリプロセッサをこのパーティーから追放する！」

データ構造を連結リストから単純な配列に切り替えた

rui氏のchibiccにならって連結リストを採用していましたが、プリプロセッサを導入しないことで実装がシンプルになり、削除や挿入に弱い単純な配列でも何不自由なく実装できました。

struct sxcscript_node {
    enum sxcscript_kind kind;
    struct sxcscript_token* token;
    union sxcscript_node_val val;
};

演算子を関数っぽい文法にした

これにより、パーサがものすごく短くなりました。具体的には、300行から100行にまで短縮できました。
その代わり、大量の括弧を書く羽目になるわけですが...

if (sxcscript_token_eq_str(*token_itr + 1, "(")) {
    (*token_itr)++;
    sxcscript_parse_expr(sxcscript, node_itr, token_itr, break_i, continue_i);
    sxcscript_parse_push(node_itr, sxcscript_kind_call, token_this, (union sxcscript_node_val){0});
}

苦労したこと（と挫折したこと）

そもそも縛り無しで言語を書くことすら難しかった

最低限動作する言語が完成するまで丸１週間かかりました。
一応数年前に一度書いたことがあるはずなんですけどね...

loopのcontinueとbreak

配列を使って管理しようとしましたが、行数が増えてしまい挫折。結局スタックに積んでいくことに。

関数呼び出し

以下は関数呼び出しに関するコードになります。
はい、どうして動いているのか本当に謎です。ありがとうございました。（実装半ばでゲシュタルト崩壊。想定通り動くまで力技で色々試した）

case sxcscript_kind_call:
    sxcscript->mem[(sxcscript->mem[sxcscript_global_sp].val) + 0].val = sxcscript->mem[sxcscript_global_ip].val;
    sxcscript->mem[(sxcscript->mem[sxcscript_global_sp].val) + 1].val = sxcscript->mem[sxcscript_global_sp].val;
    sxcscript->mem[(sxcscript->mem[sxcscript_global_sp].val) + 2].val = sxcscript->mem[sxcscript_global_bp].val;
    sxcscript->mem[sxcscript_global_ip].val = sxcscript->mem[sxcscript->mem[sxcscript_global_ip].val + 1].val - 1;
    sxcscript->mem[sxcscript_global_bp].val = sxcscript->mem[sxcscript_global_sp].val + 3;
    sxcscript->mem[sxcscript_global_sp].val += 128;
    break;
case sxcscript_kind_return:
    result = sxcscript->mem[sxcscript->mem[sxcscript_global_sp].val - 1].val;
    sxcscript->mem[sxcscript_global_ip].val = sxcscript->mem[sxcscript->mem[sxcscript_global_bp].val - 3].val;
    sxcscript->mem[sxcscript_global_sp].val = sxcscript->mem[sxcscript->mem[sxcscript_global_bp].val - 2].val;
    sxcscript->mem[sxcscript_global_bp].val = sxcscript->mem[sxcscript->mem[sxcscript_global_bp].val - 1].val;
    sxcscript->mem[(sxcscript->mem[sxcscript_global_sp].val)++].val = result;
    break;

プリプロセッサ

結局実装しなかったプリプロセッサですが、実はマクロの展開を実装しているときにネストが10重になったので心が折れて諦めました。

サンプルコード

ライブ感を醸し出すためにサンプルコードを置いておきます。

fizzbuzz

main()
end()

fn putc(x) (
    write(0, x.add(global_get(2)), 1)
)
fn endl() (
    putc(10)
)
fn printi(x) (
    a.local_set(1000000)
    loop(
        tmp.local_set(putc(local_get(x).div(local_get(a)).mod(10).add(48)))
        a.local_set(local_get(a).div(10))
        if(local_get(a).eq(0)) break
    )
)

fn main() (
    ch_a.local_set(97)
    ch_b.local_set(98)
    ch_c.local_set(99)
    ch_d.local_set(100)
    ch_e.local_set(101)
    ch_f.local_set(102)
    ch_g.local_set(103)
    ch_h.local_set(104)
    ch_i.local_set(105)
    ch_j.local_set(106)
    ch_k.local_set(107)
    ch_l.local_set(108)
    ch_m.local_set(109)
    ch_n.local_set(110)
    ch_o.local_set(111)
    ch_p.local_set(112)
    ch_q.local_set(113)
    ch_r.local_set(114)
    ch_s.local_set(115)
    ch_t.local_set(116)
    ch_u.local_set(117)
    ch_v.local_set(118)
    ch_w.local_set(119)
    ch_x.local_set(120)
    ch_y.local_set(121)
    ch_z.local_set(122)

    i.local_set(1)
    loop(
        if(local_get(i).eq(100)) break
        if(and(
            local_get(i).mod(3).eq(0),
            local_get(i).mod(5).eq(0).not()
        )) (
            tmp.local_set(putc(local_get(ch_f)))
            tmp.local_set(putc(local_get(ch_i)))
            tmp.local_set(putc(local_get(ch_z)))
            tmp.local_set(putc(local_get(ch_z)))
            tmp.local_set(endl())
        ) else if(and(
            local_get(i).mod(5).eq(0),
            local_get(i).mod(3).eq(0).not()
        )) (
            tmp.local_set(putc(local_get(ch_b)))
            tmp.local_set(putc(local_get(ch_u)))
            tmp.local_set(putc(local_get(ch_z)))
            tmp.local_set(putc(local_get(ch_z)))
            tmp.local_set(endl())
        ) else if(and(
            local_get(i).mod(5).eq(0),
            local_get(i).mod(3).eq(0)
        )) (
            tmp.local_set(putc(local_get(ch_f)))
            tmp.local_set(putc(local_get(ch_i)))
            tmp.local_set(putc(local_get(ch_z)))
            tmp.local_set(putc(local_get(ch_z)))
            tmp.local_set(putc(local_get(ch_b)))
            tmp.local_set(putc(local_get(ch_u)))
            tmp.local_set(putc(local_get(ch_z)))
            tmp.local_set(putc(local_get(ch_z)))
            tmp.local_set(endl())
        ) else (
            tmp.local_set(printi(local_get(i)))
            tmp.local_set(endl())
        )
        local_set(i,local_get(i).add(1))
    )
)

fn end() ()

乱数生成器

main()

fn putc(x) (
    write(0, x.add(global_get(2)), 1)
)
fn puti(x) (
    putc(local_get(x).add(48))
)

fn abs(x) (
    if(lt(local_get(x), 0)) (
        local_get(x).mul(-1)
    ) else (
        local_get(x)
    )
)

fn main() (
    seed.local_set(114514)
    a.local_set(1664525)
    c.local_set(1013904223)
    m.local_set(2147483647)
    x.local_set(local_get(seed))
    t.local_set(0)
    loop (
        i.local_set(0)
        loop (
            if(eq(local_get(i),32)) break
            x.local_set(local_get(x).mul(local_get(a)).add(local_get(c)).mod(local_get(m)))
            t.local_set(puti(local_get(x).abs().div(1000).mod(10)))
            i.local_set(local_get(i).add(1))
        )
        t.local_set(putc(10))
        t.local_set(usleep(1000000))
    )
)

文法

時間があったら書きます。正直、私以外誰もこの言語を使わないだろうと思っているので。
ソースは500行以内に収まっているので興味のある方はソースを読んでいただければと。

展望

サンプルの追加

今のところ、乱数生成器とfizzbuzzしかサンプルがないので他にも色々書いていこうと思っています。

ライブラリ

local_getを殆ど使わずとも演算ができるようにしていこうと思っています。現状かなり酷いことになっているので...

言語モデル

小さめの言語モデルを作ろうと思っています。私は勾配消失などには詳しくないので誰かの手を借りながらになると思われます。誰か...

おわりに

500行以内で自作言語を書いてみました。Rustに代わる、とてもシンプルで初学者におすすめできる言語ができたので安心ですね。（彼は冗談を言っています）