Structured program theorem
اسٹرکچرڈ پروگرام تھیوریم، جسے بوہم-جیکوپینی تھیوریم بھی کہا جاتا ہے، پروگرامنگ زبان کے نظریہ کا نتیجہ ہے۔ اس میں کہا گیا ہے کہ کنٹرول فلو گراف کی ایک کلاس (تاریخی طور پر اس تناظر میں فلو چارٹ کہا جاتا ہے) کسی بھی کمپیوٹیبل فنکشن کا حساب لگا سکتی ہے اگر یہ ذیلی پروگراموں کو صرف تین مخصوص طریقوں (کنٹرول ڈھانچے) میں جوڑتی ہے۔ یہ ہیں ایک ذیلی پروگرام کو انجام دینا، اور پھر دوسرا ذیلی پروگرام (ترتیب) بولین اظہار کی قدر کے مطابق دو ذیلی پروگراموں میں سے ایک کو انجام دینا (انتخاب) ایک ذیلی پروگرام کو بار بار انجام دینا جب تک کہ بولین اظہار درست ہو (تکرار) ان رکاوٹوں کے تابع منظم چارٹ، خاص طور پر لوپ کی رکاوٹ جس سے ایک ہی اخراج کا اشارہ ہوتا ہے (جیسا کہ اس مضمون میں بعد میں بیان کیا گیا ہے)، تاہم بٹس کی شکل میں اضافی متغیرات کا استعمال کر سکتا ہے (اصل ثبوت میں ایک اضافی عدد متغیر میں محفوظ کیا گیا ہے) تاکہ ان معلومات پر نظر رکھی جا سکے جو اصل پروگرام پروگرام کے مقام سے ظاہر کرتا ہے۔ تعمیر بوہم کی پروگرامنگ زبان پی پر مبنی تھی۔ تھیوریم اسٹرکچرڈ پروگرامنگ کی بنیاد بناتا ہے، ایک پروگرامنگ پیراڈائم جو گوٹو کمانڈز کو چھوڑتا ہے اور خصوصی طور پر سبروٹینز، سیکوینسز، سلیکشن اور تکرار کا استعمال کرتا ہے۔ ابتدا اور متغیرات تھیوریم کو عام طور پر کورراڈو بوہم اور جیوسیپی جیکوپینی کے 1966 کے مقالے کا سہرا دیا جاتا ہے۔ ڈیوڈ ہیرل نے 1980 میں لکھا کہ بوہم-جیکوپینی کے مقالے کو "عالمگیر مقبولیت" حاصل ہے، خاص طور پر منظم پروگرامنگ کے حامیوں کے ساتھ۔ ہیرل نے یہ بھی نوٹ کیا کہ "اس کے بجائے تکنیکی انداز [1966 کے بوہم-جیکوپینی مقالے] کی وجہ سے بظاہر تفصیل سے پڑھنے سے زیادہ حوالہ دیا جاتا ہے" اور، 1980 تک شائع ہونے والے بڑی تعداد میں مقالے کا جائزہ لینے کے بعد، ہیرل نے استدلال کیا کہ بوہم-جیکوپینی ثبوت کے مندرجات کو عام طور پر ایک لوک نظریہ کے طور پر غلط انداز میں پیش کیا گیا تھا جس میں بنیادی طور پر ایک آسان نتیجہ ہوتا ہے، جس کا نتیجہ خود وان نیومن اور کلین کے کاغذات میں جدید کمپیوٹنگ تھیوری کے آغاز سے معلوم کیا جا سکتا ہے۔ ہیرل یہ بھی لکھتے ہیں کہ زیادہ عام نام ایچ ڈی نے تجویز کیا تھا۔ 1970 کی دہائی کے اوائل میں "ساخت نظریہ" کے طور پر ملز۔ تھیوریم کا سنگل وہیل لوپ، لوک ورژن تھیوریم کا یہ ورژن تمام اصل پروگرام کے کنٹرول فلو کو ایک واحد گلوبل وہیل لوپ سے بدل دیتا ہے جو اصل غیر ساختہ پروگرام میں تمام ممکنہ لیبلز (فلو چارٹ باکسز) پر جانے والے پروگرام کاؤنٹر کی تقلید کرتا ہے۔ ہیرل نے اس لوک نظریہ کی ابتدا کا سراغ کمپیوٹنگ کے آغاز کو نشان زد کرنے والے دو کاغذات سے لگایا۔ ایک 1946 میں وان نیومن فن تعمیر کی تفصیل ہے، جس میں بتایا گیا ہے کہ ایک پروگرام کاؤنٹر وائل لوپ کے لحاظ سے کیسے کام کرتا ہے۔ ہیرل نوٹ کرتا ہے کہ ساختی پروگرامنگ تھیوریم کے لوک ورژن کے ذریعہ استعمال ہونے والا واحد لوپ بنیادی طور پر صرف وان نیومن کمپیوٹر پر فلو چارٹ کے نفاذ کے لیے آپریشنل سیمنٹکس فراہم کرتا ہے۔ ایک اور، اس سے بھی پرانا ذریعہ جو ہیرل نے تھیوریم کے لوک ورژن کا سراغ لگایا ہے وہ 1936 سے اسٹیفن کلین کا نارمل فارم تھیوریم ہے۔ ڈونلڈ نوتھ نے ثبوت کی اس شکل پر تنقید کی، جس کے نتیجے میں نیچے کی طرح سیڈو کوڈ ہوتا ہے، اس بات کی نشاندہی کرتے ہوئے کہ اس تبدیلی میں اصل پروگرام کا ڈھانچہ مکمل طور پر ختم ہو گیا ہے۔ اسی طرح، بروس ایان ملز نے اس نقطہ نظر کے بارے میں لکھا ہے کہ "بلاک ڈھانچے کی روح ایک انداز ہے، زبان نہیں۔ وان نیومن مشین کی تقلید کرکے، ہم بلاک ساختہ زبان کی حدود میں کسی بھی اسپیگیٹی کوڈ کا طرز عمل تیار کر سکتے ہیں۔ یہ اسے اسپگیٹی بننے سے نہیں روکتا۔ " p: = 1 جبکہ p> 0 کریں اگر p = 1 ہے تو فلو چارٹ سے مرحلہ 1 انجام دیں: = فلو چارٹ سے مرحلہ 1 کا نتیجہ خیز جانشین مرحلہ نمبر (0 اگر کوئی جانشین نہیں ہے) اختتام اگر p = 2 ہے تو فلو چارٹ سے مرحلہ 2 انجام دیں: = فلو چارٹ سے مرحلہ 2 کا نتیجہ خیز جانشین مرحلہ نمبر (0 اگر کوئی جانشین نہیں ہے) اختتام اگر۔ اگر p = n ہے تو فلو چارٹ سے مرحلہ n انجام دیں p: = فلو چارٹ سے مرحلہ n کا نتیجہ خیز جانشین مرحلہ نمبر (0 اگر کوئی جانشین نہیں ہے) اختتام اگر ختم ہوتا ہے جبکہ بوہم اور جیکوپینی کا ثبوت بہم اور جیکوپینی کا کاغذ بہاؤ چارٹ کی ساخت پر انڈکشن کے ذریعے آگے بڑھتا ہے۔ چونکہ اس نے گراف میں نمونوں کے ملاپ کو استعمال کیا، بوہم اور جیکوپینی کا ثبوت واقعی پروگرام ٹرانسفارمیشن الگورتھم کے طور پر عملی نہیں تھا، اور اس طرح اس سمت میں اضافی تحقیق کا دروازہ کھول دیا۔ اثرات اور اصلاحات بوہم-جیکوپینی ثبوت نے اس سوال کو حل نہیں کیا کہ آیا سافٹ ویئر ڈویلپمنٹ کے لیے اسٹرکچرڈ پروگرامنگ کو اپنایا جائے، جزوی طور پر اس وجہ سے کہ تعمیر سے کسی پروگرام کو بہتر بنانے کے بجائے غیر واضح ہونے کا امکان زیادہ تھا۔ اس کے برعکس، اس نے بحث کے آغاز کا اشارہ دیا۔ ایڈسگر ڈیکسٹرا کا مشہور خط، "نقصان دہ سمجھے جانے والے بیان پر جائیں"، 1968 میں آیا۔ کچھ ماہرین تعلیم نے بوہم-جیکوپینی کے نتیجے پر ایک خالص نقطہ نظر اختیار کیا اور استدلال کیا کہ لوپس کے بیچ سے وقفہ اور واپسی جیسی ہدایات بھی برا عمل ہیں کیونکہ بوہم-جیکوپینی ثبوت میں ان کی ضرورت نہیں ہے، اور اس طرح انہوں نے اس بات کی وکالت کی کہ تمام لوپس میں ایک ہی خارجی نقطہ ہونا چاہیے۔ یہ خالص نقطہ نظر پاسکل پروگرامنگ زبان (1968-1969 میں ڈیزائن کیا گیا) میں مجسم ہے، جو 1990 کی دہائی کے وسط تک اکیڈمیا میں تعارفی پروگرامنگ کلاسوں کی تعلیم کے لیے ترجیحی ٹول تھا۔ ایڈورڈ یورڈن نوٹ کرتے ہیں کہ 1970 کی دہائی میں غیر ساختہ پروگراموں کو خودکار ذرائع سے ساختہ پروگراموں میں تبدیل کرنے کی فلسفیانہ مخالفت بھی تھی، اس دلیل کی بنیاد پر کہ کسی کو شروع سے ہی ساختہ پروگرامنگ کے انداز میں سوچنے کی ضرورت ہے۔ عملی جوابی نقطہ یہ تھا کہ اس طرح کی تبدیلیوں سے موجودہ پروگراموں کے ایک بڑے حصے کو فائدہ پہنچا۔ خودکار تبدیلی کی پہلی تجاویز میں ایڈورڈ ایشکرافٹ اور جوہر منا کا 1971 کا مقالہ تھا۔ بوہم-جیکوپینی تھیوریم کے براہ راست اطلاق کے نتیجے میں ساختی چارٹ میں اضافی مقامی متغیرات متعارف کرائے جا سکتے ہیں، اور اس کے نتیجے میں کچھ کوڈ کی نقل بھی ہو سکتی ہے۔ اس تناظر میں مؤخر الذکر مسئلے کو لوپ اینڈ ہاف مسئلہ کہا جاتا ہے۔ پاسکل ان دونوں مسائل سے متاثر ہوتا ہے اور ایرک ایس رابرٹس کے حوالہ کردہ تجرباتی مطالعات کے مطابق، طلباء پروگرامرز کو پاسکل میں کئی آسان مسائل کے درست حل وضع کرنے میں دشواری کا سامنا کرنا پڑا، بشمول صف میں کسی عنصر کو تلاش کرنے کے لیے فنکشن لکھنا۔ 1980 میں ہنری شاپیرو کے ایک مطالعے کا حوالہ رابرٹس نے دیا کہ صرف پاسکل کے فراہم کردہ کنٹرول ڈھانچے کا استعمال کرتے ہوئے، صرف 20 فیصد مضامین نے صحیح حل دیا، جبکہ کسی بھی مضمون نے اس مسئلے کے لیے غلط کوڈ نہیں لکھا اگر اسے لوپ کے وسط سے ریٹرن لکھنے کی اجازت دی جائے۔ 1973 میں، ایس راؤ کوسراجو نے ثابت کیا کہ اسٹرکچرڈ پروگرامنگ میں اضافی متغیرات کو شامل کرنے سے بچنا ممکن ہے، جب تک کہ لوپس سے من مانی گہرائی، کثیر سطحی وقفوں کی اجازت ہو۔ مزید برآں، کوسراجو نے ثابت کیا کہ پروگراموں کا ایک سخت درجہ بندی موجود ہے، جسے آج کل کوسراجو درجہ بندی کہا جاتا ہے، اس میں ہر عدد n کے لیے، گہرائی n کے کثیر سطحی وقفے پر مشتمل ایک پروگرام موجود ہے جسے n سے کم گہرائی کے کثیر سطحی وقفوں کے ساتھ پروگرام کے طور پر دوبارہ نہیں لکھا جا سکتا (اضافی متغیرات متعارف کرائے بغیر)۔ کوسراجو BLISS پروگرامنگ زبان میں کثیر سطحی وقفے کی تعمیر کا حوالہ دیتے ہیں۔ کثیر سطح کے وقفے، ایک رخصت کے لیبل کے مطلوبہ الفاظ کی شکل میں دراصل اس زبان کے BLISS-11 ورژن میں متعارف کرائے گئے تھے۔ اصل BLISS میں صرف ایک سطح کے وقفے تھے۔ زبانوں کے BLISS خاندان نے غیر محدود گوٹو فراہم نہیں کیا۔ جاوا پروگرامنگ زبان بعد میں بھی اس نقطہ نظر کی پیروی کرے گی۔ کوسراجو کے مقالے کا ایک آسان نتیجہ یہ ہے کہ ایک پروگرام ایک منظم پروگرام (متغیرات کو شامل کیے بغیر) کے لیے قابل تخفیف ہے اگر اور صرف اس صورت میں جب اس میں دو الگ الگ اخراج کے ساتھ لوپ نہ ہو۔ کوسراجو نے تخفیف کی تعریف کی تھی، جو کہ ایک ہی فنکشن کا حساب لگانے اور وہی "ابتدائی اعمال" استعمال کرنے کے طور پر تھی اور اصل پروگرام کی طرح پیش گوئی کرتی ہے، لیکن ممکنہ طور پر مختلف کنٹرول فلو ڈھانچے کا استعمال کرتے ہوئے۔ (یہ تخفیف کا ایک تنگ تصور ہے جو بوہم-جیکوپینی نے استعمال کیا تھا۔) اس نتیجے سے متاثر ہو کر، اپنے انتہائی حوالہ شدہ مقالے کے سیکشن VI میں جس نے سائکلومیٹک پیچیدگی کے تصور کو متعارف کرایا، تھامس جے میک کیب نے غیر ساختہ پروگراموں کے کنٹرول فلو گراف (سی ایف جی) کے لیے کوراتووسکی کے تھیوریم کا ایک ینالاگ بیان کیا، جس کا مطلب ہے، کم سے کم ذیلی گراف جو کسی پروگرام کے سی ایف جی کو غیر ساختہ بناتے ہیں۔ ان ذیلی گرافوں کی قدرتی زبان میں بہت اچھی وضاحت ہے۔ وہ یہ ہیں: ایک لوپ سے باہر شاخ بنانا (لوپ سائیکل ٹیسٹ کے علاوہ) ایک لوپ میں شاخ بنانا جو کسی فیصلے میں شاخ بناتا ہے (یعنی۔ میک کیب نے ایک فیصلے سے باہر نکلتے ہوئے پایا کہ یہ چار گراف ذیلی گراف کے طور پر ظاہر ہونے پر آزاد نہیں ہیں، جس کا مطلب ہے کہ کسی پروگرام کے غیر ساختہ ہونے کے لیے ایک ضروری اور کافی شرط یہ ہے کہ اس کے سی ایف جی کا ان چار گرافوں میں سے تین کے کسی بھی ذیلی سیٹ میں سے ایک ذیلی گراف کے طور پر ہو۔ انہوں نے یہ بھی پایا کہ اگر غیر ساختہ پروگرام ان چار ذیلی گرافوں میں سے کسی ایک پر مشتمل ہے، تو اس میں چار کے سیٹ سے ایک اور الگ گراف ہونا چاہیے۔ یہ مؤخر الذکر نتیجہ اس بات کی وضاحت کرنے میں مدد کرتا ہے کہ غیر ساختہ پروگرام کا کنٹرول فلو کس طرح اس میں الجھ جاتا ہے جسے "اسپگیٹی کوڈ" کہا جاتا ہے۔ میک کیب نے ایک عددی پیمائش بھی وضع کی جو، ایک صوابدیدی پروگرام کو دیکھتے ہوئے، اس بات کی مقدار طے کرتا ہے کہ یہ ایک منظم پروگرام ہونے کے آئیڈیل سے کتنا دور ہے۔ میک کیب نے اپنی پیمائش کو لازمی پیچیدگی قرار دیا۔ میک کیب کی ساختہ پروگرامنگ کے لیے ممنوعہ گراف کی خصوصیت کو نامکمل سمجھا جا سکتا ہے، کم از کم اگر ڈیجسٹرا کے ڈی ڈھانچے کو بلڈنگ بلاکس سمجھا جائے۔ 1990 تک موجودہ پروگراموں سے گوٹو کو ختم کرنے کے لیے کافی مجوزہ طریقے تھے، جبکہ ان کی زیادہ تر ساخت کو محفوظ رکھا گیا تھا۔ اس مسئلے کے مختلف طریقوں نے مساوات کے کئی تصورات بھی پیش کیے، جو کہ صرف ٹورنگ مساوات سے زیادہ سخت ہیں، تاکہ اوپر بیان کردہ لوک تھیوریم کی طرح آؤٹ پٹ سے بچا جا سکے۔ مساوات کے منتخب کردہ تصور کی سختی کنٹرول کے بہاؤ کے ڈھانچے کے کم سے کم سیٹ کا تعین کرتی ہے۔ لائیل رامشا کے 1988 کے جے اے سی ایم کے مقالے میں اس مقام تک کے میدان کا جائزہ لینے کے ساتھ ساتھ اس کا اپنا طریقہ تجویز کیا گیا ہے۔ رامشا کا الگورتھم مثال کے طور پر کچھ جاوا ڈکمپیلرز میں استعمال کیا گیا تھا کیونکہ جاوا ورچوئل مشین کوڈ میں آفسیٹ کے طور پر ظاہر کردہ اہداف کے ساتھ برانچ ہدایات ہوتی ہیں، لیکن اعلی سطحی جاوا زبان میں صرف کثیر سطحی وقفہ اور جاری بیانات ہوتے ہیں۔ عمارگوئلاٹ (1992) نے ایک تبدیلی کا طریقہ تجویز کیا جو سنگل ایگزٹ کو نافذ کرنے پر واپس جاتا ہے۔ 1980 کی دہائی میں آئی بی ایم کے محقق ہارلن ملز نے کوبول اسٹرکچرنگ فیسیلٹی کی ترقی کی نگرانی کی، جس نے کوبول کوڈ پر ایک اسٹرکچرنگ الگورتھم کا اطلاق کیا۔ ملز کی تبدیلی میں ہر طریقہ کار کے لیے درج ذیل اقدامات شامل تھے۔ طریقہ کار میں بنیادی بلاکس کی شناخت کریں۔ ہر بلاک کے داخلے کے راستے پر ایک منفرد لیبل لگائیں، اور ہر بلاک کے باہر نکلنے کے راستوں کو ان داخلی راستوں کے لیبل سے لیبل کریں جن سے وہ جڑے ہوئے ہیں۔ طریقہ کار سے واپسی کے لیے 0 اور طریقہ کار کے داخلے کے راستے کے لیے 1 کا استعمال کریں۔ طریقہ کار کو اس کے بنیادی بلاکس میں تقسیم کریں۔ ہر بلاک کے لیے جو صرف ایک باہر نکلنے کے راستے کی منزل ہے، اس بلاک کو اس باہر نکلنے کے راستے سے دوبارہ مربوط کریں۔ طریقہ کار میں ایک نئے متغیر کا اعلان کریں (حوالہ کے لیے L کہا جاتا ہے)۔ ہر باقی غیر منسلک باہر نکلنے کے راستے پر، ایک بیان شامل کریں جو L کو اس راستے پر لیبل ویلیو پر سیٹ کرتا ہے۔ نتیجے میں آنے والے پروگراموں کو سلیکشن سٹیٹمنٹ میں جوڑیں جو پروگرام کو ایل کے اشارہ کردہ انٹری پاتھ لیبل کے ساتھ انجام دیتا ہے۔ ایک لوپ بنائیں جو اس سلیکشن سٹیٹمنٹ کو اس وقت تک انجام دیتا ہے جب تک کہ ایل 0 نہ ہو۔ ایک ایسی ترتیب بنائیں جو L کو 1 سے شروع کرے اور لوپ کو انجام دے۔ نوٹ کریں کہ سلیکشن سٹیٹمنٹ کے کچھ معاملات کو ذیلی طریقوں میں تبدیل کر کے اس تعمیر کو بہتر بنایا جا سکتا ہے۔ مزید پڑھنے کا مواد جس کا ابھی اوپر احاطہ نہیں کیا گیا ہے: پروگرامنگ لینگویج تھیوری کمپیوٹیشنل پیچیدگی تھیوری میں کمپیوٹیشن تھیوریمز کے ماڈل