再議型導出

前の理論部分では、静的タイプの導出について話したが、当時は概念に言及しただけで、主にこれが複雑であることを証明するために、もう一度議論する必要があるのは、larvaの効率にとってまだ重要であるためで、実際に私は簡単な導出アルゴリズムを作っただけで、larvaのdhrystoneでの速度を2倍にした.一方で、前にも簡単に説明したので、もう少し突っ込んでみましょう.
前述のリバース演算では、一般的なコンピュータのCPUは整数と浮動小数点計算(アドレスは今回の議論の範囲外)を直接処理するしかなく、アルゴリズムを考慮せず、1つのプログラムの言語面でのスピードアップは、抽象的な計算プロセスをできるだけ少ないCPU命令にコンパイルし、プログラムの原意を修正できないことを最適化することである.だから最適化は「余計なことをしない」ことに等しい.たとえばダイナミックタイプ言語の設計では,直接実現すると,すべてのタイプがobjectのサブクラスであるため,基礎タイプも大きな消費が生じる.
簡単な例を挙げると、例えばlarvaでは、計算a=bがa.op_に相当するeq(b)は、文法的に言えば、これは演算であり、直接実現されるコードは:

LarObj op_eq(LarObj b)
{
    boolean b = ...; //            ，   b
    return b ? TRUE : FALSE; //TRUE FALSE      bool  
}

aおよびb実行時は任意のタイプであり、コンパイル期間もLarObjとしてしか指定できないため、タイプはLarObjであり、問題はこの戻り値である.まず、この関数はどうしてもTRUEおよびFALSEのみを返すので、戻りタイプはLarObjBoolとして指定できる
2つ目は、「==」演算を考慮することです.ほとんどの場合、この演算はif、while判定、または判定のサブ式に使用されますが、LarObjBoolというタイプでは数学計算に参加できないことを規定しています(pythonでは可能です).上記のように実現すれば、if a=bは次のようになります.

if (a.op_eq(b).op_bool())

すなわち、先に計算し、返されたオブジェクトに対してboolean値を取り、上からop_eqは2つのオブジェクトのみを返すので、このような実装に最適化することができる.

boolean op_eq(LarObj b)
{
    return ...; //        
}
if (a.op_eq(b)) ...

これで最適化の目的が達成され,判断文が多ければスピードアップが顕著である.
もちろん、result=a=bという文が発生した場合、コンパイラは次のように処理します.

result = a.op_eq(b) ? TRUE : FALSE;

この場合、1つの判断が多くなるが、上記の元の実装に比べて、1つのメソッド呼び出しが少なく、速度がかなり速く、さらに重要なのは、bool演算の結果が1つの変数に与えられたり計算に参加したりすることは極めて少なく、ほとんどの場合ifやwhileで使用されるため、この特殊な処理は非常に価値がある.同様の処理方式は、cmp、contain、len、hashなどの演算など、他の内蔵操作にも現れている.
P.S.lenとhashの戻りタイプはintで計算に参加し、他の処理をしない場合、len(l)/2のようにコンパイルされます.

(new LarObjInt(l.op_len())).op_div(CONST_INT_2)

の場合、この2つの操作の戻り値を限定することは意味がありませんが、タイプ導出を組み合わせると、直接次のようにコンパイルできます.

l.op_len() / 2

これは後で話します
まず、この実装の詳細を説明することと、ダイナミックタイプ言語におけるタイプの面で大きな最適化空間があることを指摘することである.原則としてすべての変数と参照はobject型であるが,具体的なシーン決定タイプに対して効率を向上させ,コードを書く人から見れば感知できず,原則に反しない.
まず、前の静的タイプの導出の例を見てみましょう.

a = 123
a = "hello"

このコードは静的タイプ言語では一般的に許可されていません.導出がある場合は、aのタイプが決定されているのに、コンパイラが最初の付与値(C++のautoまたはgolangの:=)に準拠していると仮定すると、「aのタイプはintであり、stringをaに付与することは許可されていない」とエラーが発生する可能性があります.
しかし、この例を少し変更します.

class Z
class A extends Z
class B extends A
class C extends A
b = new B()
b = new C()

コンパイラは、bのタイプがBであると判断し、2番目の付与でエラーを報告する最初の付与を見て、プログラマー自身の意味はbのタイプがAであることを意味し、その後、Aの2つのサブクラスのインスタンスを相次いで付与し、言語がこのような場合、bに対してタイプを明らかにする必要がある場合、または前にb=new A()を書く必要がある場合、あまりにも不器用に見えます.
したがって、前述の静的タイプ導出は不完全であり、導出プロセスは、1つの付与決定タイプを見つけ、残りを検査したり、すべての付与における一貫性を検査したりするのではなく、すべての付与操作を総合して、上記の例のような最も適切なタイプ割り当てを見つけたりすることであり、bのタイプは、AまたはZであるべきであり、これらはBおよびCのベースクラスである.しかし、最適な割り当てはAであるべきであり、上記の例では、整数と文字列に共通のベースクラスがないため、コンパイラはエラーを報告すべきである.
次に、ダイナミックタイプ言語では、上記のaの例で、ダイナミックタイプ言語では、すべてのタイプがobjectのサブクラスであるため、aは整数と文字列にそれぞれ割り当てられているため、objectタイプであるべきであり、エラーを報告すべきではない.ここで,動的タイプは「すべてのタイプがobjectのサブクラス」という条件下での静的タイプの特例である動的静的タイプ体系の関係を再確認した.
ここでは、あるタイプAのオブジェクト(または値)が別のタイプBの変数に変換せずに値を付与できると仮定した互換性の概念を導入し、B互換性Aと呼ばれ、例えば、ベースクラス互換派生クラス、長整数互換整数などである.
P.S.この2つを一緒にすると、「longはintのベース」という見方が生まれやすくなりますが、この言い方はちょっとおかしいですが、互換性の観点から言えば、正しいです.intはlongの特化と見ることができます
一部のコードでは、タイプの導出は、最も簡単な定数付与から開始できない場合があります.たとえば、次のコードを書きます.
a = b
b = a
もちろん、データ・ストリーム分析を行う場合、この2行のコードは単独で問題があります.初期値が付与されていないためですが、構文にエラーはありません.コード分析からはaとbのタイプが同じか互換性があるかしかわかりません.コンパイラは最適な割り当てを計算する必要がある場合があります.
さらに複雑にすると、listのようなコンテナを考慮して、listの要素タイプも変数と似ていると仮定しますが、これは以前と同じように再帰的な問題を導入します.例えば、

func f(l):
    ...
    l.add(123)
    f([])
    ...
f([])

以前の文章で述べたように、fはテンプレートと見なし、最後のfの呼び出しを見て、f関数を構築し、パラメータタイプはlistであり、その後,このf関数インスタンスのコードを解析してlistであることが分かったが,同時に新しいf関数インスタンスが導入され,このインスタンスは従来とは異なる可能性があり,導出過程は無限ループに陥る.
前述の論文では、このような状況の原因を後続のコード分析の導出としてまとめたが、実際には、C++のテンプレートであっても、このような確定的な導出にはこの問題がある.

template <typename T>
void f(T t)
{
    vector<T> v;
    f(v);
}

このテンプレートは、どんなタイプのパラメータで呼び出されても無限の汎用定義に陥り、最終的にはコンパイラがメモリを消費して失敗し、vsはコンパイラのheap sizeを制限し、大きな結果をもたらすことはなく、gccはメモリをスタックが消費するまで食べ続けるようです
しかし、類似のコードはjavaではコンパイルの問題はありません.javaの汎用性はコード拡張で実現されていないため、テンプレート自体は正常にコンパイルできます.
上記のダイナミックタイプのlistタイプの導出問題に戻り、無限再帰を回避するだけであれば、listがコードに関連することを規定することができます.すなわち、コードの各「[]」をリストとして、固定された要素タイプがあり、コードが拡張されていないので、1つの「[]」から要素を変更する可能性のあるすべての場所を追跡すればいいのです.
コンテナ要素の内容の変更、関数呼び出しパラメータの伝達など、すべての付与値を収集する場所とすべての式は、リレーショナルマップを構築することができるため、タイプ導出の問題は、タイプを決定する必要があるすべての要素に対するタイプ割り当てを見つけ、リレーショナルマップを作成することになります.
ダイナミックタイプシステムの下で、上記の問題にはobjectを割り当てるだけで必ず成立するという簡単な解がありますが、それは意味がありません.しかし残念なことに、この問題はCSPである(制約の満足性の問題)
CSPはこのような問題を指して、いくつかの解く要素があって、これらの要素の間の制約を入力して、1つのこれらの制約を満たす解を見つけて、しかも一般的にある評価条件の下で最も優れていることを要求して、類似の解の方程式、例えばSAT、線形計画など、番図の方程式をなくしても1種のCSPを計算します
CSPは通常NP-hardであるため,入力制約や要求解の要素が多い場合,最適解を見つけることはできないが,一般的にはいくつかのスキームがある.
1具体的に実際に直面するCSP問題まで、NP-hardではないかもしれなくて、これは問題の特徴を結びつけて1つの多項式のアルゴリズムを探す必要があります
2近似アルゴリズムを用いて,できるだけ最適な解を見つける
3許容範囲内でいくつかの制約と条件を増やし、比較的解決しやすい問題(多項式アルゴリズムがあるか、規模が低下している)に変える.
タイプ導出については、いくつかの資料を調べましたが、一般的にはNP-hard問題であり、ダイナミックタイプ言語のタイプ導出についても多項式アルゴリズムが存在するかどうかは分かりません.そのためlarvaを行う際には、上記の第3の案を採用し、いくつかの制限条件を増やすことで、完全導出を放棄し、解決しやすい問題に簡略化しました.また、比較的優れたパフォーマンス向上