2

シンボル テーブルを使用すると、プログラミング言語でのシンボルの検索が最適化されるという話をよく耳にします。現在、私の言語はコンパイラとしてではなく、インタプリタとしてのみ実装されています。コンパイラを構築する時間をまだ割り当てたくないので、インタプリタを最適化しようとしています。この言語は、ほとんどの場合、Scheme のセマンティクスと構文に基づいており、静的スコープです。私は実行時にコードを実行するために AST を使用します (私のインタープリターでは、Write Yourself a Scheme in 48 Hours.

残念ながら、F# マップを使用してシンボルを名前で格納および検索しているため、インタープリターでのシンボル検索が遅くなります。(実際には Trie を使用していますが、パフォーマンスも同様に問題があります)。代わりにシンボル ツリーを使用して、より高速なシンボル ルックアップを実現したいと考えています。ただし、インタープリターでシンボルテーブルを実装できるかどうか、またはどのように実装できるかはわかりません。それらについては、コンパイラのコンテキストでのみ耳にします。

これは可能ですか？実装戦略やパフォーマンスがコンパイラのシンボル テーブルと異なる場合、その違いを説明していただけますか? 最後に、私が調べているインタープリターにシンボル ツリーの既存の参照実装はありますか?

ありがとうございました！

4

1 に答える 1

8

シンボル テーブルは、いくつかの情報をすべてのシンボルに関連付けます。インタープリターでは、おそらく値をシンボルに関連付けます。Mapは、関数型インタープリターに特に適した 1 つの実装です。

インタープリターを最適化したい場合は、実行時にシンボル テーブルの必要性を取り除きます。進むべき 1 つの方法は、De Bruijn idexingです。

関数型インタープリターから最適化されたインタープリター、VM、およびコンパイラーを機械的に導出することに関する優れた文献もあります。たとえば、次のとおりです。

http://www.brics.dk/RS/03/14/BRICS-RS-03-14.pdf

簡単な例として、De Bruijn インデックスでエンコードされた定数を使用したラムダ計算を考えてみましょう。エバリュエーターは、検索に整数を使用できるため、シンボル テーブルがなくても問題なく処理できることに注意してください。 

type exp =
    | App of exp * exp
    | Const of int
    | Fn of exp
    | Var of int

type value =
    | Closure of exp * env
    | Number of int

and env = value []

let lookup env i = Array.get env i
let extend value env = Array.append [| value |] env
let empty () : env = Array.empty

let eval exp =
    let rec eval env exp =
        match exp with
        | App (f, x) ->
            match eval env f with
            | Closure (bodyF, envF) ->
                let vx = eval env x
                eval (extend vx envF) bodyF
            | _ -> failwith "?"
        | Const x -> Number x
        | Fn e -> Closure (e, env)
        | Var x -> lookup env x
    eval (empty ()) exp
于 2012-07-17T14:49:36.210 に答える