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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در مهندسی کامپیوتر و پیاده‌سازی زبان‌های برنامه‌نویسی، ماشین پشته‌ای (به انگلیسی: 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 ۲۰۱۳).