ماشین پشته‌ای

در مهندسی کامپیوتر و پیاده‌سازی زبان‌های برنامه‌نویسی، ماشین پشته‌ای (به انگلیسی: Stack machine) یک کامپیوتر واقعی یا شبیه‌سازی شده‌است که به جای استفاده از ثبات‌های تکی، از یک پشته برای ارزیابی زیردستورها در برنامه استفاده می‌کند. کامپیوتر پشته‌ای با مجموعه دستورالعمل‌هایی که به روش نشانه‌گذاری لهستانی معکوس (نشانه‌گذاری پسوندی) نوشته‌شده‌اند، برنامه‌نویسی شده‌است.

جایگزین متداول ماشین پشته‌ای، ماشین ثبات است که در آن هر دستور به روشنی ثبات مشخصی را نام می‌برد که از آن برای مقدار عملوندها و نتیجه استفاده کند.

ماشین پشته‌ای به بیان عملی

ماشین پشته‌ای، ثبات‌ها را با یک پشته پیاده‌سازی می‌کند. عملوندهای واحد محاسبه و منطق همواره دو ثبات بالایی موجود در پشته هستند و نتیجهٔ واحد محاسبه و منطق در ثبات بالایی پشته ذخیره می‌شود. مجموعه دستورالعمل تقریباً تمام عملیات واحد محاسبه و منطق را با نشانه‌گذاری پسوندی (روش لهستانی معکوس)، که فقط در پشته به کار می‌آید نه در رجیسترها و سلول‌های حافظه، پیش می‌برد.

مزایای مجموعه دستورالعمل‌های ماشین پشته‌ای

کد شی بسیار جمع‌وجور

ماشین‌های پشته‌ای از انواع دیگر ماشین‌ها دستورهای کوتاه‌تری دارند. اما بارگذاری عملوندها جداگانه صورت می‌گیرد و بنابراین کد پشته تقریباً به دو برابر دستورالعمل نسبت به کد معادل برای ماشین ثبات نیاز دارد. به‌طور کلی سایز کد (از نظر تعداد بایت) برای ماشین پشته‌ای کمتر است.

مترجم‌های ساده

کامپایلرهای برای ماشین پشته‌ای ساده‌تر و سریع‌تر از کامپایلرها برای سایر ماشین‌ها هستند. تولید کد بسیار جزئی و مستقل از کد اولیه یا کد بعدی است. برای مثال، برای دستور x+y*z+u، درخت معادل به صورت روبرو است:

Binary tree - stack

کد ترجمه شده برای یک ماشین پشته‌ای ساده فرم زیر را می‌گیرد:

 push x
 push y
 push z
 multiply
 add
 push u
 add

به خاطر سادگی، چنین ترجمه‌هایی به سادگی با روند تجزیه ادغام می‌شوند. هیچ مدیریت ثباتی نیاز نیست، و هیچ بهینه‌سازی برای ثابت‌ها و ارجاع‌های تکراری به حافظه نه لازم است و نه اجازه داده شده‌است. آپ‌کد مشابهی که از پس مورد تکراری مشترک یک عملیت جمع، یا بارگذاری، یا فراخوانی تابع برمی‌آید، موردهای کلی‌تری مثل زیردستورهای پیچیده و فراخوانی‌های تودرتو را هم کنترل می‌کند.

مفسرهای ساده

بعضی از مجموعه دستورالعمل‌های ماشین پشته‌ای به منظور اجرای مفسری یک ماشین مجازی هستند، تا اجرای مستقیم سخت‌افزار. ساخت مفسرها برای ماشین پشته‌ای مجازی آسان‌تر است از ساخت آن‌ها برای ماشین‌های حافظه به حافظه یا ثبات‌ها. ماشین‌های پشته‌ای همچنین تمایل دارند اشتقاق‌های کمتری از یک آپ‌کد داشته باشند.

وضعیت پردازش حداقلی

یک ماشین با یک پشتهٔ دستورها می‌تواند با تنها دو ثبات، آدرس خانهٔ بالای پشته و آدرس دستور بعدی، پیش برود. پیاده‌سازی سخت‌افزار کمینه از تعداد کمی فلیپ‌فلاپ و رجیستر (ثبات) تشکیل می‌شود. پیاده‌سازی‌های سریع‌تر، برای کاهش گردش حافظه پشته، N خانه بالای پشته را به ثبات‌های غیرقابل مشاهدهٔ موقتی بافر می‌کند.

پاسخ به یک وقفه شامل وارد کردن یک ثبات قابل مشاهده به پشته و چندشاخه کردن کنترل‌کنندهٔ وقفه می‌باشد. این روش سریع‌تر از ذخیرهٔ همه یا اکثر رجیسترهای قابل مشاهدهٔ ماشین ثبات است و به وقفه سریع‌تر پاسخ می‌دهد. بعضی از ماشین‌های رجیستری با استفاده از چندین فایل رجیستری که در لحظه می‌توانند مقادیرشان را جابه‌جا کنند، با این مشکل برخورد می‌کنند. اما این روش هزینه را بالا می‌برد و سرعت فایل رجیستر را هم پایین می‌آورد.

معایب عملکرد ماشین پشته‌ای

ارجاع به حافظهٔ بیشتر

در ماشین پشته‌ای گاهی مقادیر موقتی در حافظه ریخته می‌شود، در حالی که در ماشین‌های با چندین ثبات، این مقادیر موقتی در رجیستر باقی می‌مانند. مقادیری که در حافظه ریخته می‌شوند گردش اطلاعات در حافظه پنهان (cache) را بالا می‌برند.

هزینهٔ بالای حذف زیردستورهای متداول

در ماشین‌های رجیستری، یک زیردستور که چندین بار استفاده شده و نتایج یکسانی را در پی داشته، می‌تواند تنها یک‌بار ارزیابی شود و نتیجهٔ آن در یک ثبات سریع‌تر ذخیره شود. استفاده‌های بعدی هیچ هزینهٔ زمانی و کد، غیر از ارجاع به ثبات که در هر صورت رخ می‌دهد، نخواهد داشت.

در مقایسه، در ماشین پشته‌ای، نتیجهٔ زیردستورها به یکی از دو صورتی که گفته خواهد شد ذخیره می‌شود. اولین را شامل یک متغیر موقتی در حافظه است. ذخیره و بازیابی‌های بعدی، هزینهٔ دستورالعمل‌های اضافی و گردش اضافی اطلاعات در cache را خواهد داشت. این روش تنها در صورتی موفق خواهد شد که هزینهٔ زمانی محاسبهٔ زیردستورها بیشتر از آوردن آن از حافظه باشد، که در پشتهٔ پردازنده‌ها تقریباً همیشه چنین است.

کامپیوترهایی که از پشته فراخوانی استفاده می‌کنند

بیشتر کامپیوترها و مترجم‌های فعلی از یک پشته فراخوانی بزرگ در حافظه برای مدیریت متغیرهای محلی با عمر کم و پیوندهای برگشت برای توابع فعال، استفاده می‌کنند. هر فراخوانی تودرتو، یک فریم پشته در حافظه ایجاد می‌کند که تا وقتی فراخوانی ادامه دارد، پابرجا می‌ماند. این پشتهٔ فراخوانی ممکن است به وسیلهٔ سخت‌افزار و ثبات‌های آدرس تخصیص‌داده شده و وضعیت آدرس در دستورالعمل‌ها مدیریت شود. یا ممکن است مجموعه‌ای از براوردهایی که توسط کامپایلر به وسیلهٍ بات‌های عمومی وٍ ثبات+آف‌ست وضعیت آدرس دنبال می‌شود، باشد. یا ممکن است چیزی بینابین باشد.

از آن‌جایی که الان این تکنیک تقریباً همه‌جایی است، حتی در ماشین‌های رجیستری (ثبات)، سودمند نیست که تمام این ماشین‌ها به ماشین پشته‌ای منسوب شوند. آن کلمه مشترکاً برای ماشین‌هایی هم که از پشته دستور و پشته دستورها محاسبه‌ای برای ارزیابی یک عبارت استفاده می‌کنند، در نظر گرفته می‌شود.

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Stack machine». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۰ December ۲۰۱۳.