Hindley–Milner type system
হিন্ডলি-মিলনার (এইচ. এম) টাইপ সিস্টেম হল প্যারামেট্রিক পলিমরফিজম সহ ল্যাম্বডা ক্যালকুলাসের জন্য একটি ধ্রুপদী টাইপ সিস্টেম। এটি দামাস-মিলনার বা দামাস-হিন্ডলি-মিলনার নামেও পরিচিত। এটি প্রথমে জে. রজার হিন্ডলি বর্ণনা করেছিলেন এবং পরে রবিন মিলনার পুনরায় আবিষ্কার করেছিলেন। লুইস দামাস তাঁর পিএইচডি থিসিসে পদ্ধতির একটি ঘনিষ্ঠ আনুষ্ঠানিক বিশ্লেষণ এবং প্রমাণের অবদান রেখেছেন। এইচএম-এর আরও উল্লেখযোগ্য বৈশিষ্ট্যগুলির মধ্যে রয়েছে এর সম্পূর্ণতা এবং প্রোগ্রামার-সরবরাহকৃত টাইপ টীকা বা অন্যান্য ইঙ্গিত ছাড়াই প্রদত্ত প্রোগ্রামের সবচেয়ে সাধারণ প্রকার অনুমান করার ক্ষমতা। অ্যালগরিদম ডাব্লু অনুশীলনে একটি দক্ষ ধরণের অনুমান পদ্ধতি এবং এটি সফলভাবে বড় কোড বেসে প্রয়োগ করা হয়েছে, যদিও এটির একটি উচ্চ তাত্ত্বিক জটিলতা রয়েছে। কার্যকরী ভাষার জন্য এইচ. এম ব্যবহার করা ভালো। এটি প্রথম প্রোগ্রামিং ভাষা এমএল-এর টাইপ সিস্টেমের অংশ হিসাবে প্রয়োগ করা হয়েছিল। তারপর থেকে, এইচ. এম-কে বিভিন্ন উপায়ে প্রসারিত করা হয়েছে, বিশেষ করে হাস্কেলের মতো টাইপ শ্রেণীর সীমাবদ্ধতার সঙ্গে। একটি প্রকার অনুমান পদ্ধতি হিসাবে, হিন্ডলি-মিলনার সম্পূর্ণ অপ্রচলিত শৈলীতে লেখা প্রোগ্রামগুলি থেকে ভেরিয়েবল, এক্সপ্রেশন এবং ফাংশনের ধরনগুলি অনুমান করতে সক্ষম। সুযোগ সংবেদনশীল হওয়ায়, এটি কেবল সোর্স কোডের একটি ছোট অংশ থেকে নয়, বরং সম্পূর্ণ প্রোগ্রাম বা মডিউল থেকে প্রকারগুলি আহরণ করার মধ্যে সীমাবদ্ধ নয়। প্যারামেট্রিক প্রকারের সঙ্গে মোকাবিলা করতে সক্ষম হওয়ায়, এটি অনেক কার্যকরী প্রোগ্রামিং ভাষার টাইপ সিস্টেমের মূল বিষয়। এটি প্রথম এম. এল প্রোগ্রামিং ভাষায় এই পদ্ধতিতে প্রয়োগ করা হয়েছিল। এর উৎপত্তি হল 1958 সালে হাস্কেল কারি এবং রবার্ট ফেইস দ্বারা উদ্ভাবিত সহজভাবে টাইপ করা ল্যাম্বডা ক্যালকুলাসের জন্য টাইপ ইনফারেন্স অ্যালগরিদম। 1969 সালে, জে. রজার হিন্ডলি এই কাজটি প্রসারিত করেন এবং প্রমাণ করেন যে তাদের অ্যালগরিদম সর্বদা সবচেয়ে সাধারণ ধরনের অনুমান করে। 1978 সালে, রবিন মিলনার, স্বাধীনভাবে হিন্দলির কাজ থেকে, একটি সমতুল্য অ্যালগরিদম, অ্যালগরিদম ডব্লিউ প্রদান করেন। 1982 সালে, লুইস দামাস অবশেষে প্রমাণ করেন যে মিলনারের অ্যালগরিদম সম্পূর্ণ এবং পলিমরফিক রেফারেন্স সহ সিস্টেমগুলিকে সমর্থন করার জন্য এটি প্রসারিত করেন। মনোমরফিজম বনাম পলিমরফিজম সহজভাবে টাইপ করা ল্যাম্বডা ক্যালকুলাসে, প্রকারগুলি হয় পারমাণবিক প্রকারের ধ্রুবক বা ফাংশনের প্রকার। এই ধরনের প্রজাতিগুলি মনোমরফিক। সাধারণ উদাহরণগুলি হল গাণিতিক মানগুলিতে ব্যবহৃত প্রকারগুলিঃ 3: সংখ্যা যোগ 3 4: সংখ্যা যোগঃ সংখ্যা-> সংখ্যা-> সংখ্যা এর বিপরীতে, টাইপ না করা ল্যাম্বডা ক্যালকুলাস টাইপ করার ক্ষেত্রে একেবারেই নিরপেক্ষ, এবং এর অনেকগুলি ফাংশন অর্থপূর্ণভাবে সমস্ত ধরনের আর্গুমেন্টে প্রয়োগ করা যেতে পারে। তুচ্ছ উদাহরণ হল আইডেন্টিটি ফাংশন আইডি ষ্ণ λx। x যা কেবল যে কোনও মান প্রয়োগ করা হয় তা ফেরত দেয়। কম তুচ্ছ উদাহরণের মধ্যে রয়েছে তালিকার মতো প্যারামেট্রিক প্রকার। যদিও সাধারণভাবে পলিমরফিজমের অর্থ হল অপারেশনগুলি একাধিক ধরনের মান গ্রহণ করে, এখানে ব্যবহৃত পলিমরফিজম প্যারামেট্রিক। সাহিত্যে টাইপ স্কিমের স্বরলিপিও পাওয়া যায়, যা পলিমরফিজমের প্যারামেট্রিক প্রকৃতির উপর জোর দেয়। উপরন্তু, ধ্রুবকগুলি (কোয়ান্টিফাইড) ধরনের ভেরিয়েবল দিয়ে টাইপ করা যেতে পারে। ই. জি। : কনসঃ ফরাল এ। a-> তালিকা a-> তালিকা a শূন্যঃ মোটামুটি a। একটি আইডি তালিকাভুক্ত করুনঃ forall a। a-> একটি পলিমরফিক প্রকার তাদের চলকগুলির সামঞ্জস্যপূর্ণ প্রতিস্থাপনের মাধ্যমে মনোমরফিক হয়ে উঠতে পারে। মনোমরফিক দৃষ্টান্তের উদাহরণগুলি হলঃ আইডি ': স্ট্রিং-> স্ট্রিং নিল': তালিকা সংখ্যা আরও সাধারণভাবে, প্রকারগুলি পলিমরফিক হয় যখন তাদের টাইপ ভেরিয়েবল থাকে, যখন তাদের ছাড়া প্রকারগুলি মনোমরফিক হয়। উদাহরণস্বরূপ পাস্কাল (1970) বা সি (1972)-তে ব্যবহৃত টাইপ সিস্টেমের বিপরীতে, যা শুধুমাত্র মনোমরফিক প্রকারকে সমর্থন করে, এইচ. এম প্যারামেট্রিক পলিমরফিজমের উপর জোর দিয়ে ডিজাইন করা হয়েছে। উল্লিখিত ভাষাগুলির উত্তরসূরীরা, যেমন সি + + (1985), বিভিন্ন ধরনের পলিমরফিজমের উপর দৃষ্টি নিবদ্ধ করেছিলেন, যেমন অবজেক্ট-ওরিয়েন্টেড প্রোগ্রামিং এবং ওভারলোডিংয়ের সাথে সম্পর্কিত সাবটাইপিং। যদিও সাবটাইপিং এইচ. এম-এর সাথে সামঞ্জস্যপূর্ণ নয়, তবে এইচ. এম-ভিত্তিক হাস্কেল পদ্ধতিতে পদ্ধতিগত ওভারলোডিংয়ের একটি রূপ পাওয়া যায়। সরল-টাইপযুক্ত ল্যাম্বডা ক্যালকুলাসকে পলিমরফিজমের দিকে প্রসারিত করার সময়, একটি মানের উদাহরণ কখন গ্রহণযোগ্য তা নির্ধারণ করতে হবে। আদর্শভাবে, এটি একটি আবদ্ধ চলকের যে কোনও ব্যবহারের সাথে অনুমোদিত হবে, যেমনঃ (λ আইডি। . (আইডি 3). (আইডি "টেক্সট").) (λx। x) দুর্ভাগ্যবশত, পলিমরফিক ল্যাম্বডা ক্যালকুলাসে টাইপ অনুমান নির্ণয়যোগ্য নয়। পরিবর্তে, এইচএম আইডি = λx ফর্মের একটি লেট-পলিমরফিজম প্রদান করে। x in. (আইডি 3). (আইডি "টেক্সট"). অভিব্যক্তি বাক্যবিন্যাসের একটি সম্প্রসারণে বাঁধাই প্রক্রিয়াকে সীমাবদ্ধ করে। শুধুমাত্র একটি লেট কনস্ট্রাকশনে আবদ্ধ মানগুলি তাৎক্ষণিককরণের সাপেক্ষে, অর্থাৎ। এগুলি পলিমরফিক, অন্যদিকে ল্যাম্বডা-বিমূর্তির পরামিতিগুলিকে মনোমরফিক হিসাবে বিবেচনা করা হয়। সংক্ষিপ্ত বিবরণ এই নিবন্ধের বাকি অংশটি নিম্নরূপঃ এইচএম টাইপ সিস্টেমটি সংজ্ঞায়িত করা হয়েছে। এটি একটি ডিডাকশন সিস্টেম বর্ণনা করে করা হয় যা সুনির্দিষ্ট করে যে কোন ধরনের এক্সপ্রেশন রয়েছে, যদি থাকে। সেখান থেকে, এটি টাইপ ইনফারেন্স পদ্ধতির বাস্তবায়নের দিকে কাজ করে। উপরের অবরোহী পদ্ধতির একটি বাক্য গঠন-চালিত রূপ প্রবর্তনের পর, এটি একটি দক্ষ বাস্তবায়নের (অ্যালগরিদম জে) স্কেচ করে, যা বেশিরভাগ পাঠকের ধাতবগতির অন্তর্দৃষ্টিকে আকৃষ্ট করে। যেহেতু এটি উন্মুক্ত থাকে যে অ্যালগরিদম জে প্রকৃতপক্ষে প্রাথমিক ডিডাকশন সিস্টেমটি উপলব্ধি করে কিনা, একটি কম দক্ষ বাস্তবায়ন (অ্যালগরিদম ডাব্লু) চালু করা হয় এবং একটি প্রমাণের ক্ষেত্রে এর ব্যবহারের ইঙ্গিত দেওয়া হয়। পরিশেষে, অ্যালগরিদম সম্পর্কিত আরও বিষয় নিয়ে আলোচনা করা হয়। এইচ. এম পদ্ধতিটি সরাসরি তুলনীয়ভাবে উপস্থাপন করা হয় এমন বিভিন্ন রূপ তৈরি করতে এমনকি দুটি অ্যালগরিদমের জন্যও ডিডাকশন সিস্টেমের একই বিবরণ ব্যবহার করা হয়। হিন্ডলি-মিলনার টাইপ সিস্টেম টাইপ সিস্টেমটি আনুষ্ঠানিকভাবে সিনট্যাক্স নিয়ম দ্বারা বর্ণনা করা যেতে পারে যা অভিব্যক্তি, প্রকার ইত্যাদির জন্য একটি ভাষা নির্ধারণ করে। এখানে এই ধরনের বাক্যবিন্যাসের উপস্থাপনা খুব বেশি আনুষ্ঠানিক নয়, কারণ এটি পৃষ্ঠ ব্যাকরণ অধ্যয়নের জন্য নয়, বরং গভীর ব্যাকরণ অধ্যয়নের জন্য লেখা হয়েছে এবং কিছু বাক্যবিন্যাসগত বিবরণ উন্মুক্ত রাখে। এই ধরনের উপস্থাপনা স্বাভাবিক। এর উপর ভিত্তি করে, অভিব্যক্তি এবং প্রকারগুলি কীভাবে সম্পর্কিত তা নির্ধারণ করতে টাইপিং নিয়মগুলি ব্যবহার করা হয়। আগের মতোই, ব্যবহৃত ফর্মটি কিছুটা উদার। বাক্যবিন্যাস টাইপ করা অভিব্যক্তিগুলি ঠিক ল্যাম্বডা ক্যালকুলাসের মত যা একটি লেট-এক্সপ্রেশন সহ প্রসারিত করা হয়েছে যা সংলগ্ন টেবিলে দেখানো হয়েছে। একটি অভিব্যক্তি অস্পষ্ট করতে প্যারেন্থেসিস ব্যবহার করা যেতে পারে। অ্যাপ্লিকেশনটি বাম-বাঁধাই এবং বিমূর্ততা বা লেট-ইন নির্মাণের চেয়ে শক্তিশালী বাঁধাই। প্রকারগুলি বাক্যবিন্যাসগতভাবে দুটি গ্রুপে বিভক্ত, মনোটাইপ এবং পলিটাইপ। মনোটাইপগুলি সর্বদা একটি নির্দিষ্ট প্রকারকে নির্দেশ করে। মনোটাইপগুলি বাক্যবিন্যাসগতভাবে পদ হিসাবে উপস্থাপিত হয়। মনোটাইপগুলির উদাহরণগুলির মধ্যে রয়েছে টাইপ ধ্রুবক যেমন বা, এবং প্যারামেট্রিক প্রকার যেমন। পরের প্রকারগুলি টাইপ ফাংশনের প্রয়োগের উদাহরণ, উদাহরণস্বরূপ, সেট থেকে, যেখানে সুপারস্ক্রিপ্ট টাইপ পরামিতিগুলির সংখ্যা নির্দেশ করে। এইচএম-এ টাইপ ফাংশনের সম্পূর্ণ সেটটি স্বেচ্ছাচারী, তবে এটিতে কমপক্ষে, প্রকারের ফাংশন থাকতে হবে। এটি প্রায়শই সুবিধার জন্য ইনফিক্স নোটেশনে লেখা হয়। উদাহরণস্বরূপ, একটি ফাংশন ম্যাপিং ইন্টিজার থেকে স্ট্রিং-এ টাইপ থাকে। আবার, বন্ধনী একটি প্রকার অভিব্যক্তি অস্পষ্ট করতে ব্যবহার করা যেতে পারে। অ্যাপ্লিকেশনটি ইনফিক্স তীরের চেয়ে শক্তিশালীভাবে বাঁধে, যা ডান-বাঁধাই। টাইপ ভেরিয়েবলগুলিকে মনোটাইপ হিসাবে গ্রহণ করা হয়। মনোটাইপগুলিকে মনোমর্ফিক প্রকারের সাথে বিভ্রান্ত করা উচিত নয়, যা চলকগুলিকে বাদ দেয় এবং শুধুমাত্র স্থল পদগুলিকে অনুমতি দেয়। দুটি মনোটাইপ সমান হয় যদি তাদের অভিন্ন পদ থাকে। পলিটাইপস পলিটাইপস (বা টাইপ স্কিম) হল এমন প্রকার যা শূন্য বা সমস্ত কোয়ান্টিফায়ারের জন্য আরও বেশি দ্বারা আবদ্ধ ভেরিয়েবল ধারণ করে, যেমন। । পলিটাইপ সহ একটি ফাংশন একই ধরনের যে কোনও মান নিজের সাথে ম্যাপ করতে পারে এবং আইডেন্টিটি ফাংশন এই ধরনের জন্য একটি মান। আরেকটি উদাহরণ হল, একটি ফাংশনের ধরন যা সমস্ত সসীম সেটকে পূর্ণসংখ্যায় ম্যাপিং করে। একটি ফাংশন যা একটি সেটের কার্ডিনালিটি প্রদান করে তা এই ধরনের একটি মান হবে। কোয়ান্টিফায়ার শুধুমাত্র শীর্ষ স্তরে উপস্থিত হতে পারে। উদাহরণস্বরূপ, প্রকারের বাক্যবিন্যাস দ্বারা একটি প্রকার বাদ দেওয়া হয়। এছাড়াও মনোটাইপগুলি পলিটাইপে অন্তর্ভুক্ত করা হয়, এইভাবে একটি প্রকারের সাধারণ রূপ থাকে, যেখানে এটি একটি মনোটাইপ। বহুবৃত্তের সমতা হল পরিমাপের পুনর্বিন্যাস এবং পরিমাপযোগ্য চলকগুলির নাম পরিবর্তন করা (-রূপান্তর)। উপরন্তু, মনোটাইপে না ঘটে যাওয়া পরিমাণগত চলকগুলি বাদ দেওয়া যেতে পারে। প্রসঙ্গ এবং টাইপিং অর্থবহভাবে এখনও বিচ্ছিন্ন অংশগুলিকে (বাক্যবিন্যাস অভিব্যক্তি এবং প্রকার) একত্রিত করার জন্য একটি তৃতীয় অংশ প্রয়োজনঃ প্রসঙ্গ। শব্দার্থগতভাবে, একটি প্রসঙ্গ হল জোড়াগুলির একটি তালিকা, যাকে অ্যাসাইনমেন্ট, অনুমান বা বাইন্ডিং বলা হয়, প্রতিটি জোড়া বলে যে মান পরিবর্তনশীলের প্রকার রয়েছে তিনটি অংশই মিলিতভাবে ফর্মটির একটি টাইপিং রায় দেয়, যা বলে যে অনুমানের অধীনে, অভিব্যক্তিটির প্রকার রয়েছে। মুক্ত প্রকারের চলক একটি প্রকারের মধ্যে, প্রতীকটি হল মানোটাইপে প্রকারের চলকগুলিকে আবদ্ধকারী পরিমাণক। ভেরিয়েবলগুলিকে কোয়ান্টিফাইড বলা হয় এবং একটি কোয়ান্টিফাইড টাইপ ভেরিয়েবলের যে কোনও ঘটনাকে বাউন্ড বলা হয় এবং সমস্ত আনবাউন্ড টাইপ ভেরিয়েবলকে মুক্ত বলা হয়। পলিটাইপে পরিমাপের পাশাপাশি, টাইপ ভেরিয়েবলগুলি প্রসঙ্গে ঘটার দ্বারাও আবদ্ধ হতে পারে, তবে এর ডানদিকে বিপরীত প্রভাবের সাথে। এই ধরনের চলকগুলি সেখানে টাইপ ধ্রুবকের মতো আচরণ করে। পরিশেষে, একটি টাইপ ভেরিয়েবল আইনত একটি টাইপিং-এ সীমাহীনভাবে ঘটতে পারে, যে ক্ষেত্রে সেগুলি অন্তর্নিহিতভাবে সর্ব-পরিমাণযুক্ত। প্রোগ্রামিং ভাষাগুলিতে বাউন্ড এবং আনবাউন্ড উভয় ধরনের ভেরিয়েবলের উপস্থিতি কিছুটা অস্বাভাবিক। প্রায়শই, সমস্ত ধরনের চলকগুলি অন্তর্নিহিতভাবে সর্ব-পরিমাণযুক্ত বলে বিবেচিত হয়। উদাহরণস্বরূপ, প্রোলগে ফ্রি ভেরিয়েবল সহ কোনও ধারা নেই। একইভাবে হাস্কেলে, যেখানে সমস্ত ধরনের চলক অন্তর্নিহিতভাবে পরিমাপ করা হয়, অর্থাৎ। এখানে একটি হাস্কেল টাইপ করুন a-> a মানে। অ্যাসাইনমেন্টের ডান দিকের বাঁধাই প্রভাব সম্পর্কিত এবং খুব অস্বাভাবিক। সাধারণত, আবদ্ধ এবং সীমাহীন উভয় ধরনের চলকের মিশ্রণ একটি অভিব্যক্তিতে মুক্ত চলকের ব্যবহার থেকে উদ্ভূত হয়। ধ্রুবক ফাংশন K = একটি উদাহরণ প্রদান করে। এর মনোটাইপ রয়েছে। এর দ্বারা পলিমরফিজমকে বাধ্য করা যেতে পারে। এখানে, টাইপ আছে। মুক্ত মনোটাইপ পরিবর্তনশীল পার্শ্ববর্তী পরিসরে আবদ্ধ পরিবর্তনশীলের ধরন থেকে উদ্ভূত হয়। টাইপ আছে। কেউ কল্পনা করতে পারে যে মুক্ত প্রকারের পরিবর্তনশীলটি কিসের প্রকারের দ্বারা আবদ্ধ হবে। কিন্তু এই ধরনের পরিধি এইচ. এম-এ প্রকাশ করা যায় না। বরং, বন্ধন প্রসঙ্গ দ্বারা উপলব্ধি করা হয়। টাইপ অর্ডার পলিমরফিজম মানে হল যে এক এবং একই অভিব্যক্তি (সম্ভবত অসীম) অনেক ধরনের হতে পারে। কিন্তু এই ধরনের ব্যবস্থায়, এই প্রকারগুলি সম্পূর্ণরূপে সম্পর্কিত নয়, বরং প্যারামেট্রিক পলিমরফিজম দ্বারা অর্কেস্ট্রেটেড। উদাহরণস্বরূপ, পরিচয়টির প্রকারের পাশাপাশি বা এবং আরও অনেক কিছু থাকতে পারে, তবে তা নয়। এই ফাংশনের জন্য সবচেয়ে সাধারণ প্রকারটি হল, অন্যগুলি আরও নির্দিষ্ট এবং টাইপ প্যারামিটারের জন্য অন্য প্রকারকে ধারাবাহিকভাবে প্রতিস্থাপন করে সাধারণ থেকে উদ্ভূত করা যেতে পারে, অর্থাৎ। পরিমাপযোগ্য পরিবর্তনশীল। পাল্টা উদাহরণটি ব্যর্থ হয় কারণ প্রতিস্থাপনটি সামঞ্জস্যপূর্ণ নয়। লিখিত একটি ধরনের মেয়াদের বিকল্প প্রয়োগ করে সামঞ্জস্যপূর্ণ প্রতিস্থাপনকে আনুষ্ঠানিক করা যেতে পারে। যেমন উদাহরণ থেকে বোঝা যায়, প্রতিস্থাপন শুধুমাত্র একটি আদেশের সাথে দৃঢ়ভাবে সম্পর্কিত নয়, যা প্রকাশ করে যে একটি প্রকার কমবেশি বিশেষ, তবে সমস্ত-পরিমাণের সাথেও যা প্রতিস্থাপন প্রয়োগ করার অনুমতি দেয়। আনুষ্ঠানিকভাবে, এইচএম-এ, একটি প্রকার আনুষ্ঠানিকভাবে, যদি কিছু পরিমাণগত পরিবর্তনশীলকে ধারাবাহিকভাবে প্রতিস্থাপিত করা হয় যাতে একটি লাভ হয় যেমন পার্শ্ব বারে দেখানো হয়েছে। এই ক্রমটি টাইপ সিস্টেমের টাইপ সংজ্ঞার অংশ। আমাদের পূর্ববর্তী উদাহরণে, প্রতিস্থাপন প্রয়োগের ফলাফল হবে। একটি কোয়ান্টিফাইড ভেরিয়েবলের জন্য একটি মনোমরফিক (গ্রাউন্ড) টাইপ প্রতিস্থাপন করা সোজা এগিয়ে, একটি পলিটাইপ প্রতিস্থাপনের মুক্ত ভেরিয়েবলের উপস্থিতির কারণে কিছু সমস্যা রয়েছে। বিশেষ করে, আনবাউন্ড ভেরিয়েবলগুলি প্রতিস্থাপন করা উচিত নয়। এগুলিকে এখানে ধ্রুবক হিসাবে বিবেচনা করা হয়। উপরন্তু, পরিমাপ শুধুমাত্র শীর্ষ স্তরের ঘটতে পারে। একটি প্যারামেট্রিক প্রকার প্রতিস্থাপন করে, একজনকে তার কোয়ান্টিফায়ারগুলি তুলতে হবে। ডানদিকের টেবিলটি নিয়মটিকে সুনির্দিষ্ট করে তোলে। বিকল্পভাবে, কোয়ান্টিফায়ার ছাড়া পলিটাইপের জন্য একটি সমতুল্য স্বরলিপি বিবেচনা করুন যেখানে কোয়ান্টিফাইড ভেরিয়েবলগুলি প্রতীকগুলির একটি ভিন্ন সেট দ্বারা প্রতিনিধিত্ব করা হয়। এই ধরনের স্বরলিপিতে, বিশেষীকরণ এই ধরনের চলকগুলির সরল সামঞ্জস্যপূর্ণ প্রতিস্থাপনে হ্রাস পায়। সম্পর্কটি একটি আংশিক ক্রম এবং এটি এর ক্ষুদ্রতম উপাদান। যদিও একটি টাইপ স্কিমের বিশেষীকরণ অর্ডারের একটি ব্যবহার, এটি টাইপ সিস্টেমে একটি গুরুত্বপূর্ণ দ্বিতীয় ভূমিকা পালন করে। পলিমরফিজমের সাথে টাইপ ইনফারেন্স একটি অভিব্যক্তি হতে পারে এমন সমস্ত সম্ভাব্য প্রকারের সংক্ষিপ্তসার করার চ্যালেঞ্জের মুখোমুখি হয়। আদেশটি নিশ্চিত করে যে এই ধরনের একটি সারসংক্ষেপ অভিব্যক্তিটির সবচেয়ে সাধারণ প্রকার হিসাবে বিদ্যমান। টাইপিং-এ প্রতিস্থাপন উপরে সংজ্ঞায়িত টাইপ ক্রমটি টাইপিং-এ প্রসারিত করা যেতে পারে কারণ টাইপিং-এর অন্তর্নিহিত সর্ব-পরিমাণ সামঞ্জস্যপূর্ণ প্রতিস্থাপনকে সক্ষম করেঃ বিশেষত্বের নিয়মের বিপরীতে, এটি সংজ্ঞার অংশ নয়, বরং অন্তর্নিহিত সর্ব-পরিমাণের মতো, বরং পরবর্তী সংজ্ঞায়িত প্রকারের নিয়মের একটি পরিণতি। একটি টাইপিং-এ ফ্রি টাইপ ভেরিয়েবলগুলি সম্ভাব্য পরিমার্জনের জন্য স্থানধারক হিসাবে কাজ করে। এর ডানদিকে মুক্ত প্রকারের ভেরিয়েবলের সাথে পরিবেশের বাঁধাই প্রভাব বিশেষত্বের নিয়মে তাদের প্রতিস্থাপনকে নিষিদ্ধ করে যে একটি প্রতিস্থাপনকে সামঞ্জস্যপূর্ণ হতে হবে এবং পুরো টাইপিং অন্তর্ভুক্ত করতে হবে। এই নিবন্ধটি চারটি ভিন্ন নিয়ম সেট নিয়ে আলোচনা করবেঃ ডিক্লারেটিভ সিস্টেম সিনট্যাক্টিকাল সিস্টেম অ্যালগরিদম জে অ্যালগরিদম ডাব্লু ডিডাক্টিভ সিস্টেম এইচএম-এর সিনট্যাক্সকে সিদ্ধান্ত হিসাবে টাইপিং ব্যবহার করে আনুষ্ঠানিক সিস্টেমের মূল অংশ গঠনকারী অনুমান নিয়মগুলির সিনট্যাক্সে এগিয়ে নিয়ে যাওয়া হয়। প্রতিটি নিয়ম নির্ধারণ করে যে কোন পরিসর থেকে কোন সিদ্ধান্ত নেওয়া যেতে পারে। রায়ের পাশাপাশি, উপরে প্রবর্তিত কিছু অতিরিক্ত শর্তও প্রাঙ্গণ হিসাবে ব্যবহার করা যেতে পারে। নিয়মগুলি ব্যবহার করে একটি প্রমাণ হল বিচারের একটি ক্রম যাতে কোনও সিদ্ধান্তের আগে সমস্ত পরিসর তালিকাভুক্ত করা হয়। নীচের উদাহরণগুলি প্রমাণের একটি সম্ভাব্য বিন্যাস দেখায়। বাম থেকে ডানে, প্রতিটি লাইন উপসংহার, প্রয়োগ করা নিয়মের এবং প্রাঙ্গণটি দেখায়, হয় পূর্ববর্তী লাইন (সংখ্যা) উল্লেখ করে যদি ভিত্তিটি একটি রায় হয় বা বিধেয়টি স্পষ্ট করে। টাইপিং নিয়ম আরও দেখুন টাইপিং নিয়ম পার্শ্ব বাক্সটি এইচ. এম টাইপ সিস্টেমের ছাড়ের নিয়মগুলি দেখায়। মোটামুটিভাবে নিয়মগুলিকে দুটি গ্রুপে ভাগ করা যেতে পারেঃ প্রথম চারটি নিয়ম (পরিবর্তনশীল বা ফাংশন অ্যাক্সেস), (অ্যাপ্লিকেশন, অর্থাৎ। একটি পরামিতি সহ ফাংশন কল), (বিমূর্ততা, অর্থাৎ। ফাংশন ঘোষণা) এবং (পরিবর্তনশীল ঘোষণা) বাক্যবিন্যাসকে কেন্দ্র করে, প্রতিটি অভিব্যক্তি ফর্মের জন্য একটি নিয়ম উপস্থাপন করে। তাদের অর্থ প্রথম নজরে সুস্পষ্ট, কারণ তারা প্রতিটি অভিব্যক্তি বিচ্ছিন্ন করে, তাদের উপ-অভিব্যক্তিগুলি প্রমাণ করে এবং অবশেষে প্রাঙ্গনে পাওয়া পৃথক প্রকারগুলিকে উপসংহারের প্রকারের সাথে একত্রিত করে। দ্বিতীয় গ্রুপটি বাকি দুটি নিয়ম এবং দ্বারা গঠিত হয়। তারা প্রকারের বিশেষীকরণ এবং সাধারণীকরণ পরিচালনা করে। যদিও উপরের বিশেষত্বের বিভাগ থেকে নিয়মটি স্পষ্ট হওয়া উচিত, তবে বিপরীত দিকে কাজ করে পূর্ববর্তীটির পরিপূরক। এটি সাধারণীকরণের অনুমতি দেয়, অর্থাৎ। প্রসঙ্গে আবদ্ধ নয় এমন মনোটাইপ ভেরিয়েবলের পরিমাণ নির্ধারণ করা। নিম্নলিখিত দুটি উদাহরণ নিয়ম ব্যবস্থাকে কাজে লাগিয়েছে। যেহেতু অভিব্যক্তি এবং প্রকার উভয়ই দেওয়া হয়েছে, সেগুলি নিয়মগুলির একটি টাইপ-চেকিং ব্যবহার। উদাহরণস্বরূপঃ কোথায় লেখা যেতে পারে তার একটি প্রমাণঃ সাধারণীকরণ প্রদর্শনের জন্য, নীচে দেখানো হয়েছেঃ আসুন-পলিমরফিজম অবিলম্বে দৃশ্যমান না হয়, নিয়ম সেটটি এমন একটি প্রবিধানকে এনকোড করে যার অধীনে কোনও ধরণের সাধারণকরণ করা যেতে পারে বা নাও হতে পারে। এটি মনে রাখবেন এবং যথাক্রমে পলি-এবং মনোটাইপগুলি নির্দেশ করুন। নিয়মে, ফাংশনের প্যারামিটারের মান পরিবর্তনশীলটি ভিত্তির মাধ্যমে একটি মনোমরফিক প্রকারের সাথে প্রসঙ্গে যুক্ত করা হয়, যেখানে নিয়মে, পরিবর্তনশীলটি পলিমরফিক আকারে পরিবেশে প্রবেশ করে। যদিও উভয় ক্ষেত্রেই প্রসঙ্গে এর উপস্থিতি অ্যাসাইনমেন্টের যে কোনও মুক্ত চলকের জন্য সাধারণীকরণ নিয়মের ব্যবহারকে বাধা দেয়, তবে এই নিয়ন্ত্রণটি একটি-এক্সপ্রেশন-এর প্যারামিটারের ধরণকে মনোমরফিক থাকতে বাধ্য করে, যখন একটি লেট-এক্সপ্রেশন-এ, চলকটি পলিমরফিক প্রবর্তন করা যেতে পারে, যা বিশেষীকরণকে সম্ভব করে তোলে। এই নিয়ন্ত্রণের ফলস্বরূপ, টাইপ করা যায় না, কারণ প্যারামিটারটি একটি মনোমরফিক অবস্থানে রয়েছে, যদিও টাইপ রয়েছে, কারণ এটি একটি লেট-এক্সপ্রেশন-এ প্রবর্তিত হয়েছে এবং তাই পলিমরফিক হিসাবে বিবেচিত হয়। সাধারণীকরণের নিয়ম আরও ঘনিষ্ঠভাবে দেখার জন্য সাধারণীকরণের নিয়মটিও মূল্যবান। এখানে, ভিত্তির মধ্যে অন্তর্নিহিত সমস্ত-পরিমাণ কেবল উপসংহারের ডান দিকে সরানো হয়। এটি সম্ভব, যেহেতু প্রেক্ষাপটে বিনামূল্যে ঘটে না। আবার, যদিও এটি সাধারণীকরণের নিয়মটিকে যুক্তিসঙ্গত করে তোলে, এটি আসলে কোনও পরিণতি নয়। বিপরীতে, সাধারণীকরণের নিয়মটি এইচ. এম-এর টাইপ সিস্টেমের সংজ্ঞার অংশ এবং অন্তর্নিহিত সর্ব-পরিমাণ একটি পরিণতি। একটি অনুমান অ্যালগরিদম এখন যেহেতু এইচএম-এর ডিডাকশন সিস্টেম হাতে রয়েছে, তাই কেউ একটি অ্যালগরিদম উপস্থাপন করতে পারে এবং নিয়মের সাপেক্ষে এটি বৈধ করতে পারে। বিকল্পভাবে, নিয়মগুলি কীভাবে মিথস্ক্রিয়া করে এবং প্রমাণ তৈরি হয় তা ঘনিষ্ঠভাবে দেখে এটি অর্জন করা সম্ভব হতে পারে। টাইপিং প্রমাণ করার সময় যে কোনও সম্ভাব্য সিদ্ধান্তের উপর দৃষ্টি নিবদ্ধ করে এই নিবন্ধের বাকি অংশে এটি করা হয়েছে। একটি প্রমাণের মধ্যে পয়েন্টগুলি পৃথক করে, যেখানে কোনও সিদ্ধান্ত নেওয়া সম্ভব নয়, বাক্যবিন্যাসকে কেন্দ্র করে নিয়মগুলির প্রথম গোষ্ঠী কোনও বিকল্প রাখে না কারণ প্রতিটি বাক্য গঠনমূলক নিয়মের সাথে একটি অনন্য টাইপিং নিয়মের মিল থাকে, যা প্রমাণের একটি অংশ নির্ধারণ করে, যখন উপসংহার এবং এই স্থির অংশগুলির চেইনের প্রাঙ্গনের মধ্যে এবং ঘটতে পারে। প্রমাণের উপসংহার এবং সর্বোচ্চ অভিব্যক্তির নিয়মের মধ্যেও এই ধরনের একটি শৃঙ্খল বিদ্যমান থাকতে পারে। সমস্ত প্রমাণের অবশ্যই স্কেচ করা আকৃতি থাকতে হবে। যেহেতু নিয়ম নির্বাচনের ক্ষেত্রে প্রমাণের একমাত্র পছন্দ হল এবং চেইন, তাই প্রমাণের রূপটি এই প্রশ্নের পরামর্শ দেয় যে এটি আরও সুনির্দিষ্ট করা যেতে পারে কিনা, যেখানে এই চেইনের প্রয়োজন নাও হতে পারে। এটি আসলে সম্ভব এবং এই ধরনের কোনও নিয়ম ছাড়াই নিয়ম ব্যবস্থার একটি বৈকল্পিক দিকে পরিচালিত করে। সিনট্যাক্স-নির্দেশিত নিয়ম ব্যবস্থা এইচ. এম-এর একটি সমসাময়িক চিকিত্সা একটি মধ্যবর্তী পদক্ষেপ হিসাবে ক্লিমেন্টের কারণে একটি বিশুদ্ধ সিনট্যাক্স-নির্দেশিত নিয়ম ব্যবস্থা ব্যবহার করে। এই ব্যবস্থায়, বিশেষীকরণ সরাসরি মূল নিয়মের পরে অবস্থিত এবং এটির সাথে একীভূত হয়, যখন সাধারণীকরণ নিয়মের অংশ হয়ে যায়। সেখানে সাধারণীকরণটি ফাংশনটি প্রবর্তন করে সর্বদা সবচেয়ে সাধারণ প্রকার তৈরি করতে নির্ধারিত হয়, যা আবদ্ধ নয় এমন সমস্ত মনোটাইপ ভেরিয়েবলকে পরিমাপ করে। আনুষ্ঠানিকভাবে, এই নতুন নিয়ম ব্যবস্থাটি মূলটির সমতুল্য কিনা তা প্রমাণ করার জন্য, একজনকে দেখাতে হবে যে, যা দুটি উপ-প্রমাণগুলিতে বিভক্ত হয়ঃ (ধারাবাহিকতা) (সম্পূর্ণতা) যদিও নিয়মগুলিকে বিচ্ছিন্ন করে এবং প্রমাণগুলিতে সামঞ্জস্য দেখা যায়, এটি সম্ভবত দৃশ্যমান যা অসম্পূর্ণ, যেমন উদাহরণস্বরূপ, কেউ দেখাতে পারে না, তবে কেবলমাত্র। সম্পূর্ণতার একটি সামান্য দুর্বল সংস্করণ প্রমাণযোগ্য যদিও, অর্থাৎ, শেষ পর্যন্ত প্রমাণকে সাধারণীকরণ করার অনুমতি দেওয়ার ক্ষেত্রে একটি অভিব্যক্তির জন্য মূল প্রকারটি পাওয়া যেতে পারে। তুলনা করা এবং, এখন সমস্ত নিয়মের বিচারে শুধুমাত্র মনোটাইপ দেখা যায়। উপরন্তু, ডিডাকশন সিস্টেমের সাথে যে কোনও সম্ভাব্য প্রমাণের আকৃতি এখন অভিব্যক্তিটির আকারের অনুরূপ (উভয়ই গাছ হিসাবে দেখা হয়)। এইভাবে অভিব্যক্তিটি সম্পূর্ণরূপে প্রমাণের আকৃতি নির্ধারণ করে। আকারে সম্ভবত এবং ব্যতীত সমস্ত নিয়মের সাপেক্ষে নির্ধারণ করা হবে, যা অন্যান্য নোডের মধ্যে নির্বিচারে দীর্ঘ শাখা (চেইন) নির্মাণের অনুমতি দেয়। স্বাধীনতার ডিগ্রিগুলি নিয়মগুলিকে তাত্ক্ষণিক করে এখন যেহেতু প্রমাণের আকৃতি জানা গেছে, একজন ইতিমধ্যে একটি প্রকারের অনুমান অ্যালগরিদম গঠনের কাছাকাছি। যেহেতু প্রদত্ত অভিব্যক্তিটির জন্য যে কোনও প্রমাণের অবশ্যই একই আকৃতি থাকতে হবে, তাই প্রমাণের বিচারের একক রূপগুলি অনির্ধারিত বলে ধরে নেওয়া যেতে পারে এবং সেগুলি কীভাবে নির্ধারণ করা যায় তা বিবেচনা করা যেতে পারে। এখানে, প্রতিস্থাপন (বিশেষীকরণ) ক্রমটি কার্যকর হয়। যদিও প্রথম নজরে কেউ স্থানীয়ভাবে প্রকারগুলি নির্ধারণ করতে পারে না, তবে আশা করা যায় যে প্রুফ ট্রিটি অতিক্রম করার সময় অর্ডারের সাহায্যে সেগুলিকে পরিমার্জন করা সম্ভব, অতিরিক্তভাবে ধরে নেওয়া যায়, কারণ ফলস্বরূপ অ্যালগরিদমটি একটি অনুমান পদ্ধতিতে পরিণত হবে, যে কোনও ভিত্তির ধরণটি সর্বোত্তম সম্ভাব্য হিসাবে নির্ধারিত হবে। এবং প্রকৃতপক্ষে, কেউ যেমন পরামর্শের নিয়মগুলি দেখতে পারেনঃঃ সমালোচনামূলক পছন্দ হল। এই মুহুর্তে, কিছুই জানা যায় না, তাই কেউ কেবল সবচেয়ে সাধারণ প্রকারটি অনুমান করতে পারে, যা হল। পরিকল্পনাটি হল যদি প্রয়োজন হয় তবে প্রকারটি বিশেষজ্ঞ করা। দুর্ভাগ্যবশত, এই জায়গায় একটি পলিটাইপ অনুমোদিত নয়, তাই কিছু লোককে এই মুহুর্তে করতে হবে। অবাঞ্ছিত ক্যাপচার এড়ানোর জন্য, একটি টাইপ ভেরিয়েবল যা এখনও প্রুফে নেই তা একটি নিরাপদ পছন্দ। উপরন্তু, একজনকে মনে রাখতে হবে যে এই মনোটাইপ এখনও স্থির করা হয়নি, তবে আরও পরিমার্জিত হতে পারে। : পছন্দ হল কিভাবে পরিমার্জন করা যায়। কারণ এখানে যে কোনও ধরনের পছন্দ নির্ভর করে পরিবর্তনশীলের ব্যবহারের উপর, যা স্থানীয়ভাবে জানা যায় না, সবচেয়ে নিরাপদ বাজি হল সবচেয়ে সাধারণ। উপরের মতো একই পদ্ধতি ব্যবহার করে সমস্ত কোয়ান্টিফাইড ভেরিয়েবলকে নতুন মনোটাইপ ভেরিয়েবলের সাথে তাত্ক্ষণিকভাবে সনাক্ত করা যায়, আবার তাদের আরও পরিমার্জন করার জন্য উন্মুক্ত রাখে। : নিয়মটি কোনও বিকল্প রাখে না। সম্পন্ন হয়েছে। : শুধুমাত্র প্রয়োগের নিয়মটি উভয় প্রাঙ্গনের দ্বারা প্রয়োজনীয় হিসাবে এখন পর্যন্ত "খোলা" ভেরিয়েবলগুলিতে একটি পরিমার্জন করতে বাধ্য করতে পারে। প্রথম ভিত্তিটি অনুমানের ফলাফলকে রূপের হতে বাধ্য করে। যদি হয়, তাহলে ঠিক আছে। পরে ফলাফলের জন্য এটি বেছে নেওয়া যেতে পারে। যদি তা না হয়, তবে এটি একটি উন্মুক্ত পরিবর্তনশীল হতে পারে। তারপর এটিকে আগের মতো দুটি নতুন চলক দিয়ে প্রয়োজনীয় আকারে পরিমার্জন করা যেতে পারে। অন্যথায়, টাইপ চেকিং ব্যর্থ হয় কারণ প্রথম ভিত্তিটি এমন একটি প্রকার অনুমান করে যা একটি ফাংশন প্রকার নয় এবং তৈরি করা যায় না। দ্বিতীয় ভিত্তির জন্য অনুমান করা প্রকারটি প্রথম ভিত্তির সমান হওয়া প্রয়োজন। এখন দুটি সম্ভাব্য ভিন্ন প্রকার রয়েছে, সম্ভবত উন্মুক্ত ধরনের চলক সহ, তুলনা করার জন্য এবং সম্ভব হলে সমান করার জন্য। যদি তা হয়, একটি পরিমার্জন পাওয়া যায়, এবং যদি তা না হয়, আবার একটি টাইপ ত্রুটি সনাক্ত করা হয়। একটি কার্যকর পদ্ধতি প্রতিস্থাপনের মাধ্যমে "দুটি পদকে সমান করার" জন্য পরিচিত, তথাকথিত ইউনিয়ন-ফাইন্ড অ্যালগরিদমের সংমিশ্রণে রবিনসনের একীকরণ। ইউনিয়ন-ফাইন্ড অ্যালগরিদমকে সংক্ষেপে সংক্ষিপ্ত করার জন্য, একটি প্রমাণের মধ্যে সমস্ত ধরণের সেট দেওয়া, এটি একটি পদ্ধতির মাধ্যমে তাদের সমতুল্য শ্রেণীতে একত্রিত করতে এবং একটি পদ্ধতি ব্যবহার করে এই ধরনের প্রতিটি শ্রেণীর জন্য একজন প্রতিনিধি বেছে নেওয়ার অনুমতি দেয়। পার্শ্বপ্রতিক্রিয়ার অর্থে পদ্ধতি শব্দের উপর জোর দিয়ে, আমরা একটি কার্যকর অ্যালগরিদম প্রস্তুত করার জন্য স্পষ্টভাবে যুক্তির ক্ষেত্রটি ছেড়ে দিচ্ছি। a-এর প্রতিনিধি এমনভাবে নির্ধারিত হয় যে, যদি উভয়ই এবং প্রকারের চলক হয় তবে প্রতিনিধি নির্বিচারে তাদের মধ্যে একটি, তবে একটি চলক এবং একটি শব্দকে একত্রিত করার সময়, শব্দটি প্রতিনিধি হয়ে যায়। হাতে ইউনিয়ন-ফাইন্ডের বাস্তবায়ন ধরে নিলে, নিম্নলিখিত দুটি একক প্রকারের একীকরণ প্রণয়ন করা যেতে পারেঃ একীভূত (টা, টিবি): টা = ফাইন্ড (টা) টিবি = ফাইন্ড (টিবি) যদি টা, টিবি উভয়ই অভিন্ন ডি, এন সহ ডি p1.pn ফর্মের পদ হয় তবে প্রতিটি সংশ্লিষ্ট ইথ প্যারামিটারের জন্য একীভূত (টা [আই], টিবি [আই]) অন্যথায় যদি কমপক্ষে একটি টা, টিবি একটি টাইপ ভেরিয়েবল হয় তবে ইউনিয়ন (টা, টিবি) অন্য ত্রুটি 'প্রকারগুলি মেলে না' এখন হাতে একটি অনুমান অ্যালগরিদমের স্কেচ রয়েছে, পরবর্তী বিভাগে আরও আনুষ্ঠানিক উপস্থাপনা দেওয়া হয়েছে। মিলনার পি. 370 এফএফ-এ এটি বর্ণনা করা হয়েছে। অ্যালগরিদম জে. অ্যালগরিদম জে হিসাবে অ্যালগরিদম জে-এর উপস্থাপনা যৌক্তিক নিয়মের স্বরলিপির অপব্যবহার, কারণ এতে পার্শ্ব প্রতিক্রিয়া অন্তর্ভুক্ত থাকে তবে একই সময়ে একটি দক্ষ বাস্তবায়ন প্রকাশ করার সময় এর সাথে সরাসরি তুলনা করার অনুমতি দেয়। নিয়মগুলি এখন একটি পদ্ধতি নির্দিষ্ট করে যার পরামিতিগুলি উপসংহারে পৌঁছায় যেখানে প্রাঙ্গনের সম্পাদন বাম থেকে ডানে অগ্রসর হয়। পদ্ধতিটি শব্দটি অনুলিপি করে এবং নতুন মনোটাইপ ভেরিয়েবল দ্বারা ধারাবাহিকভাবে বাউন্ড টাইপ ভেরিয়েবলগুলিকে প্রতিস্থাপন করে পলাইটাইপকে বিশেষজ্ঞ করে। একটি নতুন মনোটাইপ পরিবর্তনশীল তৈরি করে। সম্ভবত, অবাঞ্ছিত ক্যাপচার এড়ানোর জন্য কোয়ান্টিফিকেশনের জন্য নতুন ভেরিয়েবল প্রবর্তনের ধরণটি অনুলিপি করতে হবে। সামগ্রিকভাবে, অ্যালগরিদমটি এখন একীকরণের উপর বিশেষীকরণ ছেড়ে সর্বদা সবচেয়ে সাধারণ পছন্দ করে এগিয়ে যায়, যা নিজেই সবচেয়ে সাধারণ ফলাফল তৈরি করে। উপরে উল্লিখিত হিসাবে, একটি প্রদত্ত অভিব্যক্তিটির জন্য সবচেয়ে সাধারণ প্রকার পেতে চূড়ান্ত ফলাফলটি শেষ পর্যন্ত সাধারণীকরণ করতে হবে। যেহেতু অ্যালগরিদমে ব্যবহৃত পদ্ধতিগুলির প্রায় ও (1) খরচ রয়েছে, তাই অ্যালগরিদমের সামগ্রিক খরচ অভিব্যক্তিটির আকারে রৈখিকের কাছাকাছি যার জন্য একটি প্রকার অনুমান করা হবে। এটি টাইপ ইনফারেন্স অ্যালগরিদম অর্জনের অন্যান্য অনেক প্রচেষ্টার বিপরীতে, যা প্রায়শই এনপি-হার্ড হিসাবে বেরিয়ে আসে, সমাপ্তির ক্ষেত্রে অনিশ্চিত না হলেও। এইভাবে এইচএম সর্বোত্তম সম্পূর্ণরূপে জ্ঞাত টাইপ-চেকিং অ্যালগরিদমগুলি সম্পাদন করতে পারে। এখানে টাইপ-চেকিংয়ের অর্থ হল যে একটি অ্যালগরিদমকে কোনও প্রমাণ খুঁজে বের করতে হবে না, তবে শুধুমাত্র একটি প্রদত্ত প্রমাণ যাচাই করতে হবে। দক্ষতা সামান্য হ্রাস করা হয়েছে কারণ প্রসঙ্গে টাইপ ভেরিয়েবলের বন্ধন বজায় রাখতে হবে যাতে গণনার অনুমতি দেওয়া যায় এবং পুনরাবৃত্তিমূলক প্রকারের নির্মাণ রোধ করতে একটি ঘটনা পরীক্ষা সক্ষম করা যায়। এই ধরনের একটি উদাহরণ হল, যার জন্য এইচ. এম ব্যবহার করে কোনও প্রকার বের করা যায় না। ব্যবহারিকভাবে, প্রকারগুলি কেবল ছোট শব্দ এবং প্রসারিত কাঠামো তৈরি করে না। সুতরাং, জটিলতা বিশ্লেষণে, এগুলিকে একটি ধ্রুবক, ও (1) খরচ ধরে রাখার তুলনা হিসাবে বিবেচনা করা যেতে পারে। অ্যালগরিদম প্রমাণ করা পূর্ববর্তী বিভাগে, অ্যালগরিদম স্কেচ করার সময় এর প্রমাণ ধাতব যুক্তির সাথে ইঙ্গিত করা হয়েছিল। যদিও এটি একটি দক্ষ অ্যালগরিদম জে-এর দিকে পরিচালিত করে, তবে অ্যালগরিদমটি ডি বা এস ডিডাকশন সিস্টেমগুলিকে সঠিকভাবে প্রতিফলিত করে কিনা তা স্পষ্ট নয় যা শব্দার্থিক ভিত্তি হিসাবে কাজ করে। উপরের যুক্তির সবচেয়ে গুরুত্বপূর্ণ বিষয় হল প্রসঙ্গ দ্বারা আবদ্ধ মনোটাইপ ভেরিয়েবলের পরিমার্জন। উদাহরণস্বরূপ, অ্যালগরিদমটি অনুমান করার সময় সাহসের সাথে প্রসঙ্গ পরিবর্তন করে। , কারণ প্যারামিটারের প্রসঙ্গে যুক্ত মনোটাইপ ভেরিয়েবলটি পরে অ্যাপ্লিকেশন পরিচালনা করার সময় পরিমার্জন করা প্রয়োজন। সমস্যাটি হল ছাড়ের নিয়মগুলি এই ধরনের সংশোধনের অনুমতি দেয় না। যুক্তি দেওয়া যে পরিমার্জিত প্রকারটি মনোটাইপ পরিবর্তনশীলের পরিবর্তে আগে যোগ করা যেতে পারে এটি সর্বোত্তমভাবে একটি সমীচীন। একটি আনুষ্ঠানিকভাবে সন্তোষজনক যুক্তিতে পৌঁছানোর মূল চাবিকাঠি হল পরিমার্জনের মধ্যে প্রসঙ্গটি সঠিকভাবে অন্তর্ভুক্ত করা। আনুষ্ঠানিকভাবে, টাইপিং ফ্রি টাইপ ভেরিয়েবলের প্রতিস্থাপনের সাথে সামঞ্জস্যপূর্ণ। মুক্ত চলকগুলিকে পরিমার্জন করার অর্থ হল পুরো টাইপিংকে পরিমার্জন করা। অ্যালগরিদম ডাব্লু সেখান থেকে, অ্যালগরিদম জে-এর একটি প্রমাণ অ্যালগরিদম ডাব্লু-এর দিকে নিয়ে যায়, যা কেবল প্রতিস্থাপনের মাধ্যমে তার ক্রমিক গঠন প্রকাশ করে পদ্ধতি দ্বারা আরোপিত পার্শ্ব প্রতিক্রিয়াগুলি স্পষ্ট করে তোলে। সাইডবারে অ্যালগরিদম ডাব্লু-এর উপস্থাপনা এখনও ইটালিক সেট করা ক্রিয়াকলাপে পার্শ্ব প্রতিক্রিয়া ব্যবহার করে, তবে এগুলি এখন নতুন প্রতীক তৈরির মধ্যে সীমাবদ্ধ। বিচারের রূপটি হল, একটি প্রসঙ্গ এবং অভিব্যক্তি সহ একটি ফাংশনকে প্যারামিটার হিসাবে প্রতিস্থাপন সহ একটি মনোটাইপ তৈরি করা। এটি একটি বিকল্প উৎপাদনের একটি পার্শ্বপ্রতিক্রিয়া মুক্ত সংস্করণ যা সবচেয়ে সাধারণ একীকরণকারী। যদিও অ্যালগরিদম ডাব্লু সাধারণত এইচএম অ্যালগরিদম হিসাবে বিবেচিত হয় এবং প্রায়শই সাহিত্যে নিয়ম ব্যবস্থার পরে সরাসরি উপস্থাপিত হয়, মিলনার পি 369-এ এর উদ্দেশ্যটি নিম্নরূপ বর্ণনা করেছেনঃ যেমনটি দাঁড়িয়ে আছে, ডাব্লু খুব কমই একটি দক্ষ অ্যালগরিদম; প্রতিস্থাপনগুলি প্রায়শই প্রয়োগ করা হয়। এটি সুস্থতার প্রমাণকে সহায়তা করার জন্য তৈরি করা হয়েছিল। আমরা এখন একটি সহজতর অ্যালগরিদম জে উপস্থাপন করছি যা একটি সুনির্দিষ্ট অর্থে ডাব্লু অনুকরণ করে। যদিও তিনি ডাব্লু-কে আরও জটিল এবং কম দক্ষ বলে মনে করেছিলেন, তিনি জে-এর আগে তাঁর প্রকাশনায় এটি উপস্থাপন করেছিলেন। পার্শ্বপ্রতিক্রিয়া অনুপলব্ধ বা অবাঞ্ছিত হলে এর উপকারিতা রয়েছে। সম্পূর্ণতা প্রমাণ করার জন্যও ডাব্লু প্রয়োজন, যা তার দ্বারা সুস্থতার প্রমাণ হিসাবে ফ্যাক্টর করা হয়। প্রমাণের বাধ্যবাধকতাগুলি প্রমাণের বাধ্যবাধকতাগুলি প্রণয়নের আগে, নিয়ম সিস্টেম ডি এবং এস এবং উপস্থাপিত অ্যালগরিদমগুলির মধ্যে একটি বিচ্যুতি জোর দেওয়া দরকার। যদিও উপরের উন্নয়নটি মনোটাইপগুলিকে "ওপেন" প্রুফ ভেরিয়েবল হিসাবে অপব্যবহার করেছে, তবে সঠিক মনোটাইপ ভেরিয়েবলগুলি ক্ষতিগ্রস্থ হওয়ার সম্ভাবনাটি নতুন ভেরিয়েবল প্রবর্তন করে এবং সর্বোত্তমের আশা করে সরিয়ে দেওয়া হয়েছিল। কিন্তু একটি বিষয় ধরা পড়েঃ যে প্রতিশ্রুতি দেওয়া হয়েছিল তার মধ্যে একটি ছিল যে এই নতুন পরিবর্তনশীল বিষয়গুলি "মনে রাখা হবে"। এই প্রতিশ্রুতি অ্যালগরিদম দ্বারা পূরণ করা হয় না। একটি প্রসঙ্গ থাকার কারণে, অভিব্যক্তিটি অথবা-এ টাইপ করা যায় না, তবে অ্যালগরিদমগুলি টাইপ নিয়ে আসে, যেখানে ডাব্লু অতিরিক্তভাবে প্রতিস্থাপন সরবরাহ করে, যার অর্থ অ্যালগরিদম সমস্ত ধরণের ত্রুটি সনাক্ত করতে ব্যর্থ হয়। প্রুফ ভেরিয়েবল এবং মনোটাইপ ভেরিয়েবলকে আরও যত্ন সহকারে আলাদা করে এই বাদ দেওয়া সহজেই ঠিক করা যেতে পারে। লেখকরা সমস্যাটি সম্পর্কে ভালভাবে অবগত ছিলেন কিন্তু এটি সমাধান না করার সিদ্ধান্ত নিয়েছিলেন। এর পিছনে একটি বাস্তবসম্মত কারণ অনুমান করা যেতে পারে। যদিও টাইপ ইনফেরেন্স আরও সঠিকভাবে প্রয়োগ করলে অ্যালগরিদমটি বিমূর্ত মনোটাইপগুলি মোকাবেলা করতে সক্ষম হত, তবে এগুলি উদ্দেশ্যমূলক প্রয়োগের জন্য প্রয়োজন ছিল না যেখানে পূর্ববর্তী প্রসঙ্গে কোনও আইটেমেরই মুক্ত ভেরিয়েবল নেই। এই আলোকে, একটি সহজ অ্যালগরিদমের পক্ষে অপ্রয়োজনীয় জটিলতা বাদ দেওয়া হয়েছিল। অবশিষ্ট নেতিবাচক দিকটি হ 'ল নিয়ম ব্যবস্থার ক্ষেত্রে অ্যালগরিদমের প্রমাণ কম সাধারণ এবং শুধুমাত্র পার্শ্ব শর্ত হিসাবে প্রসঙ্গের জন্য তৈরি করা যেতে পারে। সম্পূর্ণতার বাধ্যবাধকতার পার্শ্ব শর্তটি নির্দেশ করে যে কীভাবে ডিডাকশনটি অনেক প্রকারের হতে পারে, যেখানে অ্যালগরিদম সর্বদা একটি তৈরি করে। একই সময়ে, পার্শ্ব শর্তটি দাবি করে যে অনুমান করা প্রকারটি আসলে সবচেয়ে সাধারণ। দায়িত্বগুলি সঠিকভাবে প্রমাণ করার জন্য প্রথমে তাদের শক্তিশালী করতে হবে যাতে এবং এর মাধ্যমে প্রতিস্থাপনের থ্রেডিং প্রতিস্থাপন লেম্মাকে সক্রিয় করার অনুমতি দেওয়া যায়। সেখান থেকে, প্রমাণগুলি অভিব্যক্তিটির উপর আনয়ন দ্বারা হয়। আরেকটি প্রমাণ বাধ্যবাধকতা হল প্রতিস্থাপন লেম্মা নিজেই, অর্থাৎ। টাইপিংয়ের প্রতিস্থাপন, যা অবশেষে সর্ব-পরিমাণ প্রতিষ্ঠা করে। পরেরটি আনুষ্ঠানিকভাবে প্রমাণ করা যায় না, কারণ এই ধরনের কোনও বাক্যবিন্যাস হাতে নেই। এক্সটেনশন পুনরাবৃত্তিমূলক সংজ্ঞা প্রোগ্রামিংকে ব্যবহারিক পুনরাবৃত্তিমূলক ফাংশন করার জন্য প্রয়োজন। ল্যাম্বডা ক্যালকুলাসের একটি কেন্দ্রীয় বৈশিষ্ট্য হল যে পুনরাবৃত্তিমূলক সংজ্ঞাগুলি সরাসরি উপলব্ধ নয়, তবে পরিবর্তে একটি নির্দিষ্ট বিন্দু সংযোজক দিয়ে প্রকাশ করা যেতে পারে। কিন্তু দুর্ভাগ্যবশত, নিচে বর্ণিত পদ্ধতিতে বিপর্যয়কর প্রভাব না ফেলে ফিক্সপয়েন্ট কম্বিনেটরটি ল্যাম্বডা ক্যালকুলাসের টাইপ করা সংস্করণে প্রণয়ন করা যায় না। টাইপিং নিয়ম মূল কাগজ দেখায় যে পুনরাবৃত্তি একজন সমন্বয়কারী দ্বারা উপলব্ধি করা যেতে পারে। একটি সম্ভাব্য পুনরাবৃত্তিমূলক সংজ্ঞা এইভাবে প্রণয়ন করা যেতে পারে। বিকল্পভাবে অভিব্যক্তি বাক্যবিন্যাসের একটি সম্প্রসারণ এবং একটি অতিরিক্ত টাইপিং নিয়ম সম্ভবঃ যেখানে মূলত একত্রীকরণ এবং মনোটাইপ অবস্থানে পুনরাবৃত্তিমূলকভাবে সংজ্ঞায়িত ভেরিয়েবলগুলি অন্তর্ভুক্ত করার সময় যেখানে তারা বাম দিকে ঘটে তবে এর ডানদিকে বহুবিধ হিসাবে। ফলাফল উপরের বিষয়গুলি সরল হলেও এটি একটি দামে আসে। টাইপ তত্ত্ব ল্যাম্বডা ক্যালকুলাসকে গণনা এবং যুক্তির সাথে সংযুক্ত করে। উপরের সহজ পরিবর্তনটি উভয়ের উপরই প্রভাব ফেলেঃ শক্তিশালী স্বাভাবিকীকরণ বৈশিষ্ট্যটি অবৈধ, কারণ অ-সমাপ্তি শর্তাবলী প্রণয়ন করা যেতে পারে। যুক্তিটি ভেঙে যায় কারণ প্রকারটি জনবসতিপূর্ণ হয়ে যায়। ওভারলোডিং মানে হল একই নামে বিভিন্ন ফাংশন সংজ্ঞায়িত এবং ব্যবহার করা যেতে পারে। বেশিরভাগ প্রোগ্রামিং ভাষাগুলি অন্তত অন্তর্নির্মিত গাণিতিক ক্রিয়াকলাপগুলির (+, <, ইত্যাদি) সাথে ওভারলোডিং প্রদান করে। ), প্রোগ্রামারকে একই আকারে গাণিতিক অভিব্যক্তি লেখার অনুমতি দেওয়ার জন্য, এমনকি বিভিন্ন সংখ্যাসূচক প্রকারের জন্য যেমন int বা বাস্তব। যেহেতু একই অভিব্যক্তির মধ্যে এই বিভিন্ন ধরণের মিশ্রণ অন্তর্নিহিত রূপান্তরেরও দাবি করে, বিশেষত এই ক্রিয়াকলাপগুলির জন্য ওভারলোডিং প্রায়শই প্রোগ্রামিং ভাষায় তৈরি করা হয়। কিছু ভাষায়, এই বৈশিষ্ট্যটি সাধারণীকরণ করা হয় এবং ব্যবহারকারীর জন্য উপলব্ধ করা হয়, যেমন। সি + + এ। যদিও টাইপ চেকিং এবং অনুমান উভয় ক্ষেত্রেই গণনার খরচের জন্য কার্যকরী প্রোগ্রামিংয়ে অ্যাডহক ওভারলোডিং এড়ানো হয়েছে, তবে ওভারলোডিংকে পদ্ধতিগত করার একটি উপায় চালু করা হয়েছে যা ফর্ম এবং অবজেক্ট ওরিয়েন্টেড প্রোগ্রামিংয়ের নামকরণ উভয়ের সাথে সাদৃশ্যপূর্ণ, তবে এক স্তরের উপরের দিকে কাজ করে। এই নিয়মে "দৃষ্টান্ত" বস্তু নয় (অর্থাৎ। মান স্তরে), বরং প্রকার। ভূমিকায় উল্লিখিত কুইকসোর্ট উদাহরণটি অর্ডারে ওভারলোডিং ব্যবহার করে, যার মধ্যে হাস্কেলে নিম্নলিখিত ধরনের টীকা রয়েছেঃ কুইকসোর্টঃঃ অর্ড a => [a]-> [a] এখানে, টাইপ a শুধুমাত্র পলিমরফিক নয়, তবে কিছু টাইপ ক্লাস অর্ডের উদাহরণ হিসাবেও সীমাবদ্ধ, যা ফাংশন বডিতে ব্যবহৃত অর্ডার পূর্বাভাস <এবং> = প্রদান করে। এই ভবিষ্যদ্বাণীগুলির যথাযথ বাস্তবায়নগুলি অতিরিক্ত পরামিতি হিসাবে কুইকসোর্টগুলিতে প্রেরণ করা হয়, যত তাড়াতাড়ি আরও কংক্রিট প্রকারগুলিতে কুইকসোর্ট ব্যবহার করা হয় যা ওভারলোড করা ফাংশন কুইকসোর্টের একক বাস্তবায়ন প্রদান করে। যেহেতু "শ্রেণী" শুধুমাত্র একটি একক প্রকারকে তাদের যুক্তি হিসাবে অনুমতি দেয়, ফলস্বরূপ টাইপ সিস্টেম এখনও অনুমান প্রদান করতে পারে। উপরন্তু, টাইপ ক্লাসগুলি তখন কোনও ধরণের ওভারলোডিং অর্ডার দিয়ে সজ্জিত করা যেতে পারে যা ক্লাসগুলিকে জাল হিসাবে সাজানোর অনুমতি দেয়। উচ্চ-ক্রমের প্রকারগুলি প্যারামেট্রিক পলিমরফিজম বোঝায় যে প্রকারগুলি নিজেরাই প্যারামিটার হিসাবে পাস করা হয় যেন তারা সঠিক মান। একটি যথাযথ ফাংশনে আর্গুমেন্ট হিসাবে পাস করা হয়, তবে "প্যারামেট্রিক" টাইপ ধ্রুবকগুলির মতো "টাইপ ফাংশনগুলিতে" পাস করা হয়, প্রশ্নটির দিকে পরিচালিত করে যে কীভাবে আরও সঠিকভাবে টাইপ করা যায়। উচ্চতর-ক্রমের প্রকারগুলি আরও বেশি অভিব্যক্তিপূর্ণ প্রকারের ব্যবস্থা তৈরি করতে ব্যবহৃত হয়। দুর্ভাগ্যবশত, মেটা প্রকারের উপস্থিতিতে একীকরণ আর নির্ণায়ক নয়, সাধারণতার এই সম্প্রসারণে প্রকারের অনুমানকে অসম্ভব করে তোলে। উপরন্তু, সমস্ত সেটের সেটের মতো নিজেকে টাইপ হিসাবে অন্তর্ভুক্ত করে এমন সমস্ত ধরণের ধরে নেওয়া একটি প্যারাডক্সের দিকে নিয়ে যায়, তাই একজনকে অবশ্যই বিমূর্ততার স্তরের ধাপে এগিয়ে যেতে হবে। দ্বিতীয় ক্রমের ল্যাম্বডা ক্যালকুলাসের গবেষণা, এক ধাপ উপরে, দেখায় যে এই ধরনের অনুমান এই সাধারণতায় অনিশ্চিত। একটি অতিরিক্ত স্তরের অংশ হাস্কেল নামক ধরনের মধ্যে প্রবর্তন করা হয়েছে, যেখানে এটি মোনাড টাইপ করতে সহায়তা করতে ব্যবহৃত হয়। বর্ধিত ধরনের ব্যবস্থার অভ্যন্তরীণ যান্ত্রিকতায় পর্দার আড়ালে কাজ করে প্রকারগুলি অন্তর্নিহিত থাকে। সাব-টাইপিং এবং টাইপ অনুমানকে একত্রিত করার প্রচেষ্টা বেশ কিছুটা হতাশার কারণ হয়ে দাঁড়িয়েছে। উপপ্রকারের সীমাবদ্ধতাগুলি সংগ্রহ করা এবং প্রচার করা সোজা (প্রকারের সমতা সীমাবদ্ধতার বিপরীতে), ফলস্বরূপ সীমাবদ্ধতাগুলি অনুমিত টাইপিং স্কিমের অংশ করে তোলে, উদাহরণস্বরূপ, যেখানে প্রকারের পরিবর্তনশীলের উপর একটি সীমাবদ্ধতা রয়েছে। যাইহোক, যেহেতু টাইপ ভেরিয়েবলগুলি আর এই পদ্ধতিতে আগ্রহের সাথে একীভূত হয় না, তাই এটি অনেক অকেজো টাইপ ভেরিয়েবল এবং সীমাবদ্ধতার সমন্বয়ে বড় এবং অপ্রয়োজনীয় টাইপিং স্কিম তৈরি করে, যা তাদের পড়া এবং বোঝা কঠিন করে তোলে। অতএব, অনির্ধারিত সীমাবদ্ধ অটোমেটন (এন. এফ. এ) সরলীকরণের মতো কৌশল ব্যবহার করে (অনুমিত পুনরাবৃত্তিমূলক প্রকারের উপস্থিতিতে দরকারী) এই ধরনের টাইপিং স্কিম এবং তাদের সীমাবদ্ধতাগুলি সহজ করার জন্য যথেষ্ট প্রচেষ্টা করা হয়েছিল। আরও সম্প্রতি, ডোলন এবং মাইক্রফ্ট টাইপিং স্কিম সরলীকরণ এবং এন. এফ. এ সরলীকরণের মধ্যে সম্পর্ককে আনুষ্ঠানিক করে তুলেছেন এবং দেখিয়েছেন যে সাবটাইপিংয়ের আনুষ্ঠানিকতার উপর একটি বীজগাণিতিক গ্রহণ একটি এম. এল-সদৃশ ভাষার (যাকে এম. এল. সাব বলা হয়) জন্য সংক্ষিপ্ত প্রধান টাইপিং স্কিম তৈরি করার অনুমতি দেয়। উল্লেখযোগ্যভাবে, তাদের প্রস্তাবিত টাইপিং স্কিমে স্পষ্ট সীমাবদ্ধতার পরিবর্তে ইউনিয়ন এবং ছেদ প্রকারের একটি সীমাবদ্ধ রূপ ব্যবহার করা হয়েছিল। পরে প্যারিও দাবি করেন যে এই বীজগাণিতিক সূত্রটি অ্যালগরিদম ডব্লিউ-এর অনুরূপ তুলনামূলকভাবে সহজ অ্যালগরিদমের সমতুল্য এবং ইউনিয়ন এবং ছেদ প্রকারের ব্যবহার অপরিহার্য ছিল না। অন্যদিকে, অবজেক্ট-ওরিয়েন্টেড প্রোগ্রামিং ভাষার প্রেক্ষাপটে টাইপ ইনফারেন্স আরও কঠিন প্রমাণিত হয়েছে, কারণ অবজেক্ট পদ্ধতিতে সিস্টেম এফ-এর শৈলীতে প্রথম শ্রেণীর পলিমরফিজমের প্রয়োজন হয় (যেখানে টাইপ ইনফারেন্স অনিবার্য) এবং এফ-বাউন্ডেড পলিমরফিজমের মতো বৈশিষ্ট্যগুলির কারণে। ফলস্বরূপ, কার্ডেলির সিস্টেমের মতো অবজেক্ট-ওরিয়েন্টেড প্রোগ্রামিং সক্ষম করার সাথে টাইপ সিস্টেমগুলি এইচএম-স্টাইলের ধরণের অনুমানকে সমর্থন করে না। কাঠামোগত রেকর্ডের মতো ভাষার বৈশিষ্ট্যগুলিকে সমর্থন করার জন্য উপপ্রকারের বিকল্প হিসাবে সারি বহুরূপতা ব্যবহার করা যেতে পারে। যদিও পলিমরফিজমের এই শৈলীটি কিছু উপায়ে সাবটাইপিংয়ের তুলনায় কম নমনীয়, উল্লেখযোগ্যভাবে প্রকারের সীমাবদ্ধতার দিকনির্দেশনার অভাব মোকাবেলা করার জন্য কঠোরভাবে প্রয়োজনীয়তার চেয়ে বেশি পলিমরফিজমের প্রয়োজন হয়, তবে এর সুবিধা রয়েছে যে এটি খুব সহজেই স্ট্যান্ডার্ড এইচএম অ্যালগরিদমের সাথে সংহত করা যেতে পারে। নোটস রেফারেন্স এক্সটার্নাল লিঙ্কস গিটহাব-এ সোর্স কোড সহ অ্যালগরিদম ডাব্লু-এর একটি সাক্ষর হাস্কেল বাস্তবায়ন। পাইথনে হিন্দলি-মিলনার অ্যালগরিদমের একটি সহজ বাস্তবায়ন। টাইপ সিস্টেমস টাইপ থিওরি টাইপ ইনফারেন্স ল্যাম্বডা ক্যালকুলাস তাত্ত্বিক কম্পিউটার বিজ্ঞান আনুষ্ঠানিক পদ্ধতি 1969 কম্পিউটিংয়ে 1978 কম্পিউটিংয়ে 1985 কম্পিউটিং অ্যালগরিদম