Essential complexity
ضروری پیچیدگی ایک عددی پیمائش ہے جس کی تعریف تھامس جے میک کیب، سینئر نے اپنے انتہائی حوالہ شدہ، 1976 کے مقالے میں کی ہے جو سائکلومیٹک پیچیدگی کو متعارف کرانے کے لیے مشہور ہے۔ میک کیب نے ضروری پیچیدگی کو کم شدہ سی ایف جی (کنٹرول فلو گراف) کی سائکلومیٹک پیچیدگی کے طور پر بیان کیا ہے جو تمام منظم پروگرامنگ کنٹرول ڈھانچوں کو بار بار تبدیل کرنے (کم کرنے) کے بعد ہے، یعنی۔ جن کے پاس واحد انٹری پوائنٹ اور واحد ایگزٹ پوائنٹ ہے (مثال کے طور پر اگر-تب-دوسرے اور جبکہ لوپس) پلیس ہولڈر سنگل اسٹیٹمنٹ کے ساتھ۔ میک کیب کے تخفیف کے عمل کا مقصد ذیلی روٹین کالز کے ساتھ کنٹرول ڈھانچے (اور ان پر مشتمل اصل بیانات) کے تصوراتی متبادل کی تقلید کرنا ہے، اس لیے کنٹرول ڈھانچے کے لیے ایک ہی اندراج اور ایک ہی خارجی نقطہ ہونا ضروری ہے۔ (آج کل اس طرح کا عمل ری فیکٹرنگ کی چھتری اصطلاح کے تحت آتا ہے۔) تمام اسٹرکچرڈ پروگراموں میں واضح طور پر 1 کی ایک لازمی پیچیدگی ہوتی ہے جیسا کہ میک کیب نے بیان کیا ہے کیونکہ ان سب کو بار بار ٹاپ لیول سبروٹین پر ایک کال تک کم کیا جا سکتا ہے۔ جیسا کہ میک کیب نے اپنے مقالے میں وضاحت کی ہے، ان کی بنیادی پیچیدگی میٹرک کو اس بات کی پیمائش فراہم کرنے کے لیے ڈیزائن کیا گیا تھا کہ یہ آئیڈیل (مکمل طور پر تشکیل شدہ ہونے کا) ایک دیا ہوا پروگرام کتنا دور تھا۔ اس طرح 1 سے زیادہ ضروری پیچیدگی کے اعداد، جو صرف غیر ساختہ پروگراموں کے لیے حاصل کیے جا سکتے ہیں، اس بات کی نشاندہی کرتے ہیں کہ وہ ساختہ پروگرامنگ آئیڈیل سے مزید دور ہیں۔ ساختی پروگراموں میں تخفیف کے مختلف تصورات کے درمیان الجھن سے بچنے کے لیے، یہ نوٹ کرنا ضروری ہے کہ میک کیب کا مقالہ مختصر طور پر بحث کرتا ہے اور پھر ایس راؤ کوسراجو کے 1973 کے مقالے کے تناظر میں کام کرتا ہے، جس نے ساختی پروگرام تھیوریم کی اصلاح (یا متبادل نظریہ) دی۔ بوہم اور جیکوپینی کے 1966 کے بنیادی مقالے سے پتہ چلتا ہے کہ تمام پروگراموں کو صرف منظم پروگرامنگ تعمیرات کا استعمال کرتے ہوئے [دوبارہ] لکھا جا سکتا ہے، (عرف D ڈھانچے: ترتیب، اگر-تب-بصورت دیگر، اور جبکہ-لوپ)، تاہم، بے ترتیب پروگرام کو ایک منظم پروگرام میں تبدیل کرنے میں اضافی متغیرات کو متعارف کرانے کی ضرورت پڑ سکتی ہے (اور ٹیسٹ میں استعمال کیا جاتا ہے) اور کچھ کوڈ کو نقل کیا جا سکتا ہے۔ اپنے مقالے میں، بوہم اور جیکوپینی نے قیاس کیا، لیکن یہ ثابت نہیں کیا کہ بعض قسم کے غیر ساختہ پروگراموں کے لیے اس طرح کے اضافی متغیرات کو متعارف کرانا ضروری تھا تاکہ انہیں منظم پروگراموں میں تبدیل کیا جا سکے۔ پروگرام کی ایک مثال (جسے اب ہم جانتے ہیں) اس طرح کے اضافی متغیرات کی ضرورت ہوتی ہے وہ ایک لوپ ہے جس کے اندر دو مشروط اخراج ہوتے ہیں۔ بوہم اور جیکوپینی کے قیاس آرائی کو حل کرنے کے لیے، کوسراجو نے بوہم اور جیکوپینی کے استعمال کردہ ٹورنگ مساوات کے مقابلے میں پروگرام میں کمی کے زیادہ پابند تصور کی وضاحت کی۔ بنیادی طور پر، کوسراجو کا تخفیف کا تصور اس واضح ضرورت کے علاوہ عائد کرتا ہے کہ دونوں پروگراموں کو ایک ہی ان پٹ کو دیکھتے ہوئے ایک ہی قدر (یا ختم نہیں) کا حساب لگانا چاہیے، کہ دونوں پروگراموں کو ایک ہی ابتدائی اعمال اور پیش گوئیاں استعمال کرنی چاہئیں، مؤخر الذکر کو شرائط میں استعمال ہونے والے تاثرات کے طور پر سمجھا جاتا ہے۔ ان پابندیوں کی وجہ سے، کوسراجو کی کمی اضافی متغیرات کو متعارف کرانے کی اجازت نہیں دیتی ہے۔ ان متغیرات کو تفویض کرنے سے نئے ابتدائی اعمال پیدا ہوں گے اور ان کی اقدار کی جانچ سے شرائط میں استعمال ہونے والی پیش گوئیاں بدل جائیں گی۔ کمی کے اس زیادہ پابند تصور کو استعمال کرتے ہوئے، کوسراجو نے بوہم اور جیکوپینی کے قیاس کو ثابت کیا، یعنی کہ دو باہر نکلنے والے لوپ کو اضافی متغیرات متعارف کرائے بغیر ایک منظم پروگرام میں تبدیل نہیں کیا جا سکتا، لیکن آگے بڑھ کر ثابت کیا کہ کثیر سطحی وقفوں پر مشتمل پروگرام (لوپس سے) ایک درجہ بندی تشکیل دیتے ہیں، جیسے کہ کوئی ہمیشہ گہرائی n کے کثیر سطحی وقفوں والا پروگرام تلاش کر سکتا ہے جسے اضافی متغیرات متعارف کرائے بغیر، n سے کم گہرائی والے کثیر سطحی وقفوں کے پروگرام میں کم نہیں کیا جا سکتا۔ میک کیب نے اپنے مقالے میں نوٹ کیا ہے کہ کوسراجو کے نتائج کے پیش نظر، وہ غیر ساختہ پروگراموں کی ضروری خصوصیات کو ان کے کنٹرول فلو گراف کے لحاظ سے حاصل کرنے کا ایک طریقہ تلاش کرنے کا ارادہ رکھتے تھے۔ وہ سب سے چھوٹے غیر ساختہ پروگراموں سے مطابقت رکھنے والے کنٹرول فلو گرافوں کی شناخت کرکے آگے بڑھتا ہے (ان میں لوپ میں برانچنگ، لوپ سے باہر برانچنگ، اور ان کے اگر پھر دوسرے ہم منصبوں کو شامل کرنا شامل ہے) جسے وہ کوراتووسکی کے تھیوریم سے مشابہت رکھنے والے تھیوریم کو وضع کرنے کے لیے استعمال کرتا ہے، اور اس کے بعد وہ ضروری پیچیدگی کے اپنے تصور کو متعارف کراتا ہے تاکہ اس سوال کے ہاں/نہیں جواب کے بجائے کہ آیا کسی پروگرام کا کنٹرول فلو گراف تشکیل شدہ ہے یا نہیں۔ آخر میں، میک کیب کی طرف سے سی ایف جی کو سکڑنے کے لیے استعمال کیا جانے والا تخفیف کا تصور کوسراجو کے فلو چارٹ کو کم کرنے کے تصور کے جیسا نہیں ہے۔ سی ایف جی پر بیان کردہ کمی پروگرام کے ان پٹ کے بارے میں نہیں جانتی یا پرواہ نہیں کرتی ہے، یہ محض ایک گراف کی تبدیلی ہے۔ مثال کے طور پر، مندرجہ ذیل سی پروگرام کے ٹکڑے میں 1 کی لازمی پیچیدگی ہے، کیونکہ اندرونی آئی ایف بیان اور فار کو کم کیا جا سکتا ہے، یعنی۔ یہ ایک منظم پروگرام ہے۔ کے لیے (i = 0 ؛ i <3 ؛ i + +) {اگر (a [i] = = 0) b [i] + = 2 ؛} مندرجہ ذیل C پروگرام کے ٹکڑے میں چار کی لازمی پیچیدگی ہے ؛ اس کا CFG ناقابل تلافی ہے۔ پروگرام z کی پہلی صف کو تلاش کرتا ہے جو تمام صفر ہے اور اس انڈیکس کو i میں رکھتا ہے۔ اگر کوئی نہیں ہے تو، یہ-1 کو i میں رکھتا ہے۔ (i = 0 ؛ i <m ؛ i + +) {کے لیے (j = 0 ؛ j <n ؛ j + +) {اگر (z [i] [j]! = 0) گوٹو غیر صفر ؛} گوٹو پایا گیا ؛ غیر صفر:} i =-1 پایا گیا: ذیلی گراف کے مسلسل خاتمے سے CFG کی تخفیف کا خیال (بالآخر اچھے سلوک والے CFG کے لیے ایک نوڈ میں) جدید مرتب کی اصلاح میں بھی استعمال ہوتا ہے۔ تاہم سنگل انٹری اور سنگل ایگزٹ کنٹرول ڈھانچے کے منظم پروگرامنگ کے تصور کو نیچرل لوپ سے تبدیل کر دیا گیا ہے، جس کی تعریف "سنگل انٹری، ملٹیپل ایگزٹ لوپ" کے طور پر کی گئی ہے، جس میں صرف ایک شاخ اس کے اندر سے داخلے پر واپس آتی ہے۔ سی ایف جی کے وہ علاقے جنہیں قدرتی لوپس تک کم نہیں کیا جا سکتا انہیں نامناسب علاقے کہا جاتا ہے۔ ان علاقوں میں کافی آسان تعریف ہوتی ہے: ایک سے زیادہ اندراج، سی ایف جی کے مضبوطی سے جڑے ہوئے اجزاء۔ اس طرح سب سے آسان نامناسب علاقہ دو داخلی نکات والا لوپ ہے۔ متعدد اخراج جدید مرتبوں میں تجزیہ کے مسائل کا سبب نہیں بنتے ہیں۔ نامناسب علاقے (لوپس میں متعدد اندراجات) کوڈ کو بہتر بنانے میں اضافی مشکلات کا باعث بنتے ہیں۔ سافٹ ویئر انجینئرنگ کی تاریخ فیصلہ سے فیصلہ کا راستہ سائکلومیٹک پیچیدگی حوالہ جات سافٹ ویئر پروجیکٹ مینجمنٹ سافٹ ویئر میٹرکس بھی دیکھیں۔