スタックレス言語はどのように機能するのでしょうか?

https://stackoverflow.com/questions/1016218

06-07-2019
|

質問

スタックレス言語について聞いたことがあります。ただし、そのような言語がどのように実装されるかはわかりません。誰か説明してもらえますか？

解決

私たちが使用している最新のオペレーティングシステム (Windows、Linux) は、私が「ビッグスタックモデル」と呼ぶもので動作します。そして、そのモデルは間違っていることがあり、それが「スタックレス」言語の必要性を動機付けています。

「ビッグスタックモデル」は、コンパイルされたプログラムが、スタックポインター (およびオプションのスタックフレームポインター) を含むレジスターを非常に迅速に調整する機械命令を使用して、メモリの連続領域内の関数呼び出しに「スタックフレーム」を割り当てることを前提としています。これにより、スタックに大きな連続領域が必要になりますが、関数の呼び出しと戻りが高速になります。これらの最新の OS で実行されるすべてのプログラムの 99.99% はビッグスタックモデルで適切に動作するため、コンパイラ、ローダー、さらには OS さえもこのスタック領域について「認識」しています。

このようなアプリケーションすべてに共通する問題の 1 つは次のとおりです。 「スタックはどのくらいの大きさにすべきですか?」. 。メモリが非常に安価であるため、ほとんどの場合、大きなチャンクがスタック用に確保され (MS のデフォルトは 1Mb)、典型的なアプリケーション呼び出し構造ではそれを使い切ることはありません。しかし、アプリケーションがそれをすべて使い切ると、スタックの最後に手を伸ばすことにより、不正なメモリ参照 (「ごめんなさい、デイブ、それはできません」) で終了します。

いわゆる「スタックレス」言語のほとんどは、実際にはスタックレスではありません。これらのシステムが提供する連続したスタックを使用しないだけです。代わりに、関数呼び出しごとにヒープからスタックフレームを割り当てます。関数呼び出しあたりのコストは若干増加します。通常、関数が複雑である場合、または言語が解釈型である場合、この追加コストは重要ではありません。(プログラムコールグラフ内のコール DAG を決定し、DAG 全体をカバーするヒープセグメントを割り当てることもできます。これにより、ヒープ割り当てと、呼び出し DAG 内のすべての呼び出しに対する従来のビッグスタック関数呼び出しの速度の両方が得られます)。

スタックフレームにヒープ割り当てを使用する理由はいくつかあります。

1）プログラムが解決している特定の問題に依存して深い再帰を行う場合、必要なサイズが不明でないため、「大きなスタック」領域を事前に事前に表現することは非常に困難です。関数呼び出しをぎこちなく配置して、十分なスタックが残っているかどうかを確認し、残っていない場合は、より大きなチャンクを再割り当てし、古いスタックをコピーして、すべてのポインタをスタックに再調整することができます。それは非常に厄介なので、実装については知りません。スタックフレームを割り当てるということは、文字通り割り当て可能なメモリが残っていないまで、アプリケーションが残念に言わなければならないことを意味します。

2) プログラムはサブタスクをフォークします。各サブタスクには独自のスタックが必要なため、提供されている 1 つの「大きなスタック」を使用することはできません。したがって、サブタスクごとにスタックを割り当てる必要があります。考えられるサブタスクが何千もある場合、何千もの「大きなスタック」が必要になる可能性があり、メモリ需要が突然途方もないものになります。スタックフレームを割り当てることで、この問題は解決されます。多くの場合、サブタスク「スタック」は親タスクを参照して字句スコープを実装します。サブタスクがフォークすると、「サボテンスタック」と呼ばれる「サブスタック」のツリーが作成されます。

3) あなたの言語には継続性があります。これらでは、現在の関数から見える字句スコープ内のデータが、後で再利用できるように何らかの方法で保存される必要があります。これは、親スタックフレームをコピーし、サボテンスタックを登って続行することで実装できます。

のパーランセ私が実装したプログラミング言語は 1) と 2) を実行します。3)に取り組んでいます。

他のヒント

スタックレスPython にはまだPythonスタックがあります（ただし、末尾呼び出しの最適化やその他の呼び出しフレームのマージトリックがある場合があります））、しかしインタプリタのCスタックから完全に離婚しています。

Haskell（一般的に実装されている）には呼び出しスタックがありません。評価は、グラフの縮小に基づいています。

http：// wwwに、言語フレームワークParrotに関する素晴らしい記事があります。 .linux-mag.com / cache / 7373 / 1.html 。 Parrotは呼び出しにスタックを使用しません。この記事では、この手法について少し説明します。

私がある程度慣れているスタックレス環境（チューリングマシン、アセンブリ、およびBrainfuck）では、独自のスタックを実装するのが一般的です。言語にスタックを構築することに関して基本的なことは何もありません。

これらの最も実用的なアセンブリでは、使用可能なメモリ領域を選択し、スタックレジスタを下を指すように設定してから、プッシュまたはポップを実装するためにインクリメントまたはデクリメントします。

編集：一部のアーキテクチャには専用のスタックがありますが、必ずしも必要ではありません。

この記事の継続についてのわかりやすい説明があります： http：// www。 defmacro.org/ramblings/fp.html

継続は、スタックベースの言語で関数に渡すことができるものですが、言語自体のセマンティクスによって使用して「スタックレス」にすることもできます。もちろん、スタックはまだありますが、Ira Baxterが説明したように、それは1つの大きな連続したセグメントではありません。

スタックレスCを実装するとします。最初に実現することは、これにはスタックが必要ないことです。

a == b

しかし、これですか？

isequal(a, b) { return a == b; }

いいえ。スマートコンパイラは isequal の呼び出しをインライン化するため、それらを a == b に変換します。では、なぜすべてをインライン化しないのですか？もちろん、より多くのコードを生成しますが、スタックを削除する価値がある場合、これは簡単なトレードオフで簡単です。

再帰はどうですか？問題ない。次のような末尾再帰関数：

bang(x) { return x == 1 ? 1 : x * bang(x-1); }

実際にはインライン化されたforループにすぎないため、インライン化できます：

bang(x) {
    for(int i = x; i >=1; i--) x *= x-1;
    return x;
}

理論的には、本当に賢いコンパイラーがあなたのためにそれを見つけ出すことができます。しかし、あまり賢くない人は、それをgotoとして平らにすることができます：

ax = x;
NOTDONE:
if(ax > 1) {
    x = x*(--ax);
    goto NOTDONE;
}

小さなトレードオフを行う必要がある場合が1つあります。これはインライン化できません：

fib(n) { return n <= 2 ? n : fib(n-1) + fib(n-2); }

Stackless Cは単にこれを行うことができません。あなたはたくさんあきらめていますか？あんまり。これは、通常のCでもうまくできないことです。信じられない場合は、 fib（1000）を呼び出して、あなたの大切なコンピューターに何が起こるかを見てください。

古くから電話してください。しかし、FORTRAN標準とCOBOLが再帰呼び出しをサポートしていなかったため、スタックを必要としなかった時期を覚えています。実際、スタックがないCDC 6000シリーズマシンの実装を思い出します。サブルーチンを再帰的に呼び出そうとすると、FORTRANは奇妙なことをします。

レコードの場合、コールスタックの代わりに、CDC 6000シリーズの命令セットはRJ命令を使用してサブルーチンを呼び出しました。これにより、呼び出し先の場所に現在のPC値が保存され、その後に続く場所に分岐します。最後に、サブルーチンは呼び出しターゲット位置への間接ジャンプを実行します。これにより、保存されたPCがリロードされ、事実上呼び出し元に戻ります。

明らかに、再帰呼び出しでは機能しません。（私の記憶では、再帰を試みた場合、CDC FORTRAN IVコンパイラは壊れたコードを生成します...）

間違っている場合はお気軽に修正してください。ただし、関数呼び出しフレームごとにヒープにメモリを割り当てると、極端なメモリスラッシングが発生すると思います。オペレーティングシステムは、結局このメモリを管理する必要があります。このメモリスラッシングを回避する方法は、コールフレームのキャッシュになると思います。とにかくキャッシュが必要な場合は、メモリ内で連続させてスタックと呼ぶこともできます。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow