1+1が必要だったので、関数型言語を構築しました

contents データ構造の課題 変数も追加できます。大きな変更にはならないでしょう。 Cでの実装 アリーナallocator 環境テーブルの構築 メモリallocatorのアップグレード ガベージコレクタの構築 次のパートで期待できること これまでに達成したこと 待て。しかし、それは1+1を評価するのか？ 私は、算術式を二分木に変換するというデータ構造の問題を与えられました。当然、評価器を構築することにしました。数日後、C言語でクロージャ、ガベージコレクタ、カスタムメモリallocator、REPL、FFI、その他多くのものを実装しました。 graphLang データ構造の課題 問題はこうでした: 1+1+1 を二分木を使って3に評価する。どうすればそこにたどり着けるでしょうか？ まず、1+1+1の木を形成します。 (+) / \ (+) / \ (1) (1) 演算子がルートになり、その2つのオペランドが子になります。 では、この木を評価してみましょう。まず、ルートの左オペランドを評価します。それは別の+式なので、外側の+が実行される前に値を崩す必要があります。 (+) / \ (+) / \ (2) (1) そして、もう一度評価します。 (3) <--- これが結果です これは、(+ (+ 1 1) 1) の等価なものを実行したことになります。 | v (+ 2 1) | v (3) しかし、評価器がこれを行うために知る必要があったことに注意してください: + が何を意味するか。 これを表現する1つの方法は、各操作を式タイプで異なるケースにすることです。 Expr ::= Add Expr Expr | Sub Expr Expr | Mul Expr Expr | Div Expr Expr | Val しかし、これらの異なるケースは実際には何を意味するのでしょうか？そして、評価器はAddとSubの違いを知る必要があるのでしょうか？ それから、和型 (sum types) の実装を始めました。 そして、構造を見たとき: Add: Expr x Expr → Expr Sub: Expr x Expr → Expr Mul: Expr x Expr → Expr Div: Expr x Expr → Expr すべて2つの式を受け取り、1つの式を生成します。なぜ評価器は、操作がAdd、Sub、Mul、またはDivであるかに関係があるのでしょうか？関係ないようです。 したがって、式を次のように表すことができます。 Expr ::= Func Expr Expr | Val 評価器は関数が何をするかを知る必要はありません。それはただそれを適用する方法を知っているだけで十分です。 変数も追加できます。大きな変更にはならないでしょう。 これは小さな追加であるべきで、問題は全くありません。 つまり、変数は単なるハッシュテーブルのルックアップであり、Exprを返します。 ああ、待て。 Cには組み込みのハッシュテーブルがありません。 うーん。(´-`).｡oO( … ) ハッシュテーブルを実装しましょう。これは小さな変更です！m9(・∀・) それで…どうなるのでしょうか？以前に実装したことはありません。 洞窟人のようにGoogleで検索し、この素晴らしいテキストを見つけました。 C言語でハッシュテーブルを実装する方法 これで、Exprに小さな変更が加わりました。 Expr ::= Func Expr Expr | Val | Var 見てください！関数に渡すことができる変数ができました。 (+ 1 1) のように Cでの実装 さて、この計画でC言語でコーディングする時間です。単純なタグ付きユニオンです。 typedef enum { LITERAL, VAR, FUNC, } NodeType; struct Node { struct Node *left; struct Node *right; union { int literal; char *var; char *func; } data; NodeType type; }; 現在、各ノードのメモリサイズは（64ビットシステムを想定）: +------------------------+----------+ | フィールド | サイズ | +------------------------+----------+ | 左ポインタ | 8 バイト | | 右ポインタ | 8 バイト | | データ | 8 バイト | | タイプ | 4 バイト | | パディング | 4 バイト | +------------------------+----------+ | 合計 | 32 バイト | +------------------------+----------+ 32バイトは多くないように思えるかもしれませんが、どのように使用されているかを考える必要があります。 1+1を評価するために、3つのノードが必要になります。 演算子1つ、オペランド2つ これは、1+1を評価するために32 x 3 = 96バイトになります。 しかし、ここで重要なことがあります。私のシステムでは、ノードをmalloc()すると、メタデータが追加され、メモリを16バイト消費します！これにより、ノードあたりの合計は32（ノードサイズ）+ 16（mallocヘッダー）= 48バイトになります！ したがって、(+)を評価するための3つのノードには144バイトが必要になります！ そして、私たちは多くの小さな個別の割り当てを行うことになることに注意してください。ノードを割り当てるには、より良い方法が必要です。 明らかにカスタムallocatorが必要です。 そこで、どのallocatorを使用できるか調べました。再び洞窟人のように、アリーナallocatorを自分で書くことにしました。 アリーナallocator アリーナallocatorのアイデアは非常にシンプルです。 最初に大きなメモリチャンクを取得し、自分で何かを割り当て、最後にブロック全体を解放するだけです。 したがって、私のアリーナallocatorは次のようになります。 #define SIZE 1024 Node arena[SIZE] ノードを割り当てる際には、トップを次のように追跡し続けることができます。 int top = 0; ノードを割り当てたいときは、次のように返します。 &arena[top++]; allocatorを書き、ノードを割り当てるC関数を定義しました。 Node *allocNode(); それは素晴らしかったです！次に、実際にこれらの関数を呼び出すことに移りました。 それから気づきました。 変数と関数を同じ環境に格納できます！ つまり、関数も値になり得ます (°◇°) 前に作成したハッシュテーブルを覚えていますか？それをアップグレードする時が来ました。 環境テーブルの構築 環境テーブルには2つのものを格納しています。 変数と関数。 しかし、関数とは何でしょうか？ 私たちの評価器にとって、それは片側から引数を取り、もう片側から結果を吐き出すものです。 (func node) / \ (arg 1) (arg 2) 最初のアイデアは、それらが単なるC関数のポインタであることでした。単純に思えます。 しかし、これには大きな問題があります: ユーザーは独自の関数をどのように書くのでしょうか？ しかし、もう1つの問題があります。 ユーザーが私たちの言語にコードを入力すると、それは魔法のようにネイティブC関数ポインタになることはできません。 それはAST（ノードのツリー）を構築することしかできません。 関数がCポインタである場合、それらはすぐに不透明な値になります。 関数が別の関数を返す場合はどうなりますか？ その関数をグラフに戻して後で評価できるようにする必要があります。 しかし、C関数ポインタは、私たちの評価器がたどることができるものではありません。 したがって、評価器に「おい、私は関数だが、私のコードはCポインタではなく、このツリーだ」と伝えるタイプのノードが必要です。 評価器が複数ステップで評価できるように、関数の本体をツリーとして格納する必要があります。 そして、私たちの目的のために、それは私たちのクロージャ表現です。 ブラックボックスのC関数ではなく、クロージャはグラフ内の実際のノードです。 それはパラメータを片側に、操作のツリー（本体）をもう片側に保持します。 (closure) / \ (parameter) (body) / \ (math) (literal) （技術的にはクロージャも環境を持っていますが、ローカル変数にはまだ到達していません） 関数を実際のノードにすることで、それを渡したり、他の関数から返したり、いつでもステップバイステップで評価したりできます！ これで、Cコードに触れることなく、ユーザーが自分で定義できる関数ができました！！！ さて、これをC言語で実装しましょう。 では、何が必要でしょうか？ 変数と関数が両方とも値である場合、環境は名前をノードにマッピングする必要があります。 したがって、環境エントリを次のように作成できます。 typedef struct EnvEntry { char *key; Node *val; struct EnvEntry *next; } EnvEntry; これで、ハッシュテーブルは名前（キー）をNode *（値）にマッピングします。 しかし、valは何でしょうか？ValはNodeです！ しかし、私たちのNodeはまだクロージャやネイティブ関数について知りません。 そこで、前のノード定義にそれらを追加しましょう。 struct Node { struct Node *left; struct Node *right; union { int literal; char *var; int index; // For function calls char *call; // For function names struct Node *closure; // User-defined functions struct Node *nativeFunc; // C functions } data; NodeType type; }; nativeFuncsはC関数を表すノードであり、closuresはノードで構成されるユーザー定義関数です。 ネイティブ関数 = 不透明なC実装 クロージャ = 言語レベルのグラフ表現 したがって。私たちはピースを組み立てました。 メモリallocator 変数、C関数、ユーザー定義関数を保持する環境テーブル プログラムをたどり、関数を適用する評価器 最初のプログラムを実行しましょう！！ 現在、lexer/parserがないため、ASTを手動で構築できます。 テストするのにこれ以上のプログラムは何でしょうか？フィボナッチ数列です！ そこでプログラムを書きました。 fib(5)と入力しました。 そして…クラッシュしました。 メモリallocatorのアップグレード なぜでしょうか？ 私たちのfib(5)は13kノードを生成したからです。 しかし、allocatorのサイズは合計1024ノードしかありません！