স্টফল ভাষার জন্য রুবি ইন্টারপ্রেটার গড়ে তোলা

গিটহাবে ফুল সোর্স (Full Source on Github)

স্টফল প্রোগ্রামিং ভাষার সম্পূর্ণ ইমপ্লিমেন্টেশন GitHub-এ উপলব্ধ। বাগ খুঁজলে বা প্রশ্ন থাকলে ইস্যু খুলতে পারেন।

এই ব্লগ পোস্টে, আমরা স্টফলের ইন্টারপ্রেটার বাস্তবায়ন শুরু করব, একটি টয় প্রোগ্রামিং ভাষা যা সম্পূর্ণ রুবিতে তৈরি। এই প্রজেক্ট সম্পর্কে আরও জানতে এই সিরিজের প্রথম পার্ট পড়ুন।

আমরা যে ইন্টারপ্রেটার বানাব সেটাকে সাধারণত ট্রি-ওয়াক ইন্টারপ্রেটার (tree-walk interpreter) বলা হয়। এই সিরিজের পূর্বের পোস্টে, আমরা একটি পার্সার বানালাম যা টোকেনের একটি ফ্ল্যাট সিকোয়েন্সকে একটি ট্রি ডেটা স্ট্রাকচারে রূপান্তর করে (অবস্ট্রাক্ট সিনট্যাক্স ট্রি, সংক্ষেপে AST)। আপনি কল্পনা করতে পারছেন, আমাদের ইন্টারপ্রেটার এর কাজ হলো আমাদের পার্সার তৈরি করা AST-র মাধ্যমে ঘুরে ঘুরে স্টফল প্রোগ্রামে প্রাণ ফूंকা। আমি এই শেষ ধাপটাকেই এই ভাষা বাস্তবায়ন যাত্রার সবচেয়ে এক্সাইটিং ধাপ মনে করি। ইন্টারপ্রেটার বিল্ড করার সময় সব কিছু শেষে ক্লিক করে, এবং আমরা সত্যিকারের স্টফল প্রোগ্রাম রান করতে দেখি!

আমি ইন্টারপ্রেটার ইমপ্লিমেন্টেশন দুটি পার্টে দেখাব এবং এক্সপ্লেইন করব। এই প্রথম পার্টে, আমরা বেসিকগুলো কাজ করাব: ভেরিয়েবল, কন্ডিশনাল, ইউনারি এবং বাইনারি অপারেটর, ডেটা টাইপ, এবং কনসোলে প্রিন্ট করা। বাকি জটিল বিষয়গুলো (ফাংশন ডেফিনিশন, ফাংশন কলিং, লুপ, ইত্যাদি) অনগामी দ্বিতীয় এবং শেষ পোস্টের জন্য রক্ষা করলাম।

লেক্সার এবং পার্সার দ্রুত রিক্যাপ

ইন্টারপ্রেটার বাস্তবায়নে ডুবানোর আগে, আসুন দ্রুত মনে করি আমরা এই সিরিজের পূর্বের পোস্টগুলোতে কী করলাম। প্রথমে, আমরা লেক্সার বানালাম, যা র-Source কোডকে টোকেনে রূপান্তর করে। তারপর, আমরা পার্সার বাস্তবায়ন করলাম, কম্পোনেন্টটি যা টোকেনগুলোক একটি ট্রি স্ট্রাকচারে রূপান্তর করে (AST)। সংক্ষেপে, এখানে আমরা যে রূপান্তরগুলো দেখেছি:

State 0: Source

my_var = 1 

State 1: লেক্সার র-Source কোডকে টোকেনে রূপান্তর করে

[:identifier, :'=', :number] 

State 2: পার্সার টোকেনগুলোক Abstract Syntax Tree-তে রূপান্তর করে

সব কিছুর ওয়াকিং (Walking) সম্পর্কে

এখন আমাদের কাছে একটি AST আছে, আমাদের কাজ হলো এই স্ট্রাকচারটি ওয়াক (walk) করার কোড লিখা। আমাদের রুবি কোড লিখতে হবে যেটা আমাদের AST-এর প্রতিটি নোড বর্ণনা করে সেটাকে জীবন দিতে পারে। যদি আমাদের একটি নোড থাকে যা একটি ভেরিয়েবল বাইন্ডিং বর্ণনা করে, উদাহরণস্বরূপ, আমাদের কাজ হলো রুবি কোড লিখা যেটা ডান দিকের ভেরিয়েবল বাইন্ডিং এক্সপ্রেশনের ফলাফল স্টোর করতে পারে এবং এই স্টোরেজ স্পেসটি ভেরিয়েবলে দেওয়া নামের সাথে অ্যাসোসিয়েটেড এবং অ্যাক্সেসযোগ্য থাকবে।

এই সিরিজের পূর্বের পার্টগুলোতে যেমন করলাম, আমরা একটি উদাহরণ প্রোগ্রামের মাধ্যমে সব গুরুত্বপূর্ণ কোড লাইন এক্সপ্লোর করে ইমপ্লিমেন্টেশন বুঝব। যে স্টফল কোডটি আমাদের ইন্টারপ্রেট করতে হবে সেটা নিচে:

num = -2 if num > 0 println("The number is greater than zero.") else println("The number is less than or equal to zero.") end 

এই প্রোগ্রামের জন্য তৈরি AST:

আমাদের ওয়াকের প্রথম ধাপ

আপনি সম্ভবত পिछले পোস্ট থেকে মনে করছেন, একটি স্টফল AST-র রুট সবসময় একটি AST::Program নোড। এই রুট সাধারণত একাধিক চাইল্ড থাকে। 그중 কিছু শ্যালো (shallow) হবে (সিম্পল ভেরিয়েবল অ্যাসাইনমেন্টের জন্য তৈরি AST ভাবুন)। অন্য চাইল্ডগুলো গভীর সাবট্রির রুট হতে পারে (অনেক লাইন থাকা লুপের বডি ভাবুন)। এখানে রুবি কোড যা আমাদের দরকার AST-র মাধ্যমে ওয়াক করার জন্য যেটা ইন্টারপ্রেটারে পাস করা হয়েছে:

module Stoffle class Interpreter attr_reader :program, :output, :env def initialize @output = [] @env = {} end def interpret(ast) @program = ast interpret_nodes(program.expressions) end private def interpret_nodes(nodes) last_value = nil nodes.each do |node| last_value = interpret_node(node) end last_value end def interpret_node(node) interpreter_method = "interpret_#{node.type}" send(interpreter_method, node) end #... end end 

যখন একটি নতুন Interpreter ইনস্ট্যানশিয়েট করা হয়, তখন সেটা একদম শুরু থেকেই দুটি ইনস্ট্যান্স ভেরিয়েবল তৈরি করে: @output এবং @env। প্রথমটির দায়িত্ব হলো ক্রোনোলজিক্যাল ক্রমে সব কিছু স্টোর করা যা আমাদের প্রোগ্রাম প্রিন্ট করেছে। অটোমেটেড টেস্ট লিখতে বা ডিবাগ করার সময় এই ইনফরমেশন খুব কাজে লাগে। @env-র দায়িত্ব একটু ভিন্ন। আমরা এটাকে "environment" রেফারেন্স হিসেবে নাম দিয়েছি। নামটার সাজেশন অনুযায়ী, এর ফাংশন হলো আমাদের রানিং প্রোগ্রামের স্টেট ধরে রাখা। এর ফাংশনগুলোর মধ্যে একটি হলো একটি আইডেন্টিফায়ার (যেমন, একটি ভেরিয়েবল নাম) এবং তার বর্তমান মান এর মাঝপথে বাইন্ডিং ইমপ্লিমেন্ট করা।

#interpret_nodes মেথড রুট নোড (AST::Program)র সব চাইল্ডের মাধ্যমে লুপ করে। তারপর, প্রতিটি ইনডিভিজুয়াল নোডের জন্য #interpret_node কল করে।

#interpret_node সিম্পল কিন্তু ননদেজু আকর্ষণীয়। এখানে, আমরা একটু রুবি মেটা-প্রোগ্রামিং ব্যবহার করি সঠিক মেথড কল করার জন্য যেটা বর্তমানে হাতের নোড টাইপ হ্যান্ডেল করে। উদাহরণস্বরূপ, একটি AST::VarBinding নোডের জন্য, #interpret_var_binding মেথডই কল হয়।

অনিবার্যভাবে, আমাদের ভেরিয়েবল নিয়ে কথা বলতে হবে

উদাহরণ প্রোগ্রামের AST-এ আমাদের যে প্রথম নোড ইন্টারপ্রেট করতে হবে সেটা একটি AST::VarBinding। এর @left একটি AST::Identifier, এবং এর @right একটি AST::UnaryOperator। ভেরিয়েবল বাইন্ডিং ইন্টারপ্রেট করার জন্য দায়বদ্ধ মেথডটি দেখি:

def interpret_var_binding(var_binding) env[var_binding.var_name_as_str] = interpret_node(var_binding.right) end 

আপনি দেখছেন, এটা খুব সিম্পল। আমরা @env Hash-এ একটি কি-ভ্যালু পেয়ার যোগ করি (বা ওভাররাইট করি)।

কি (key) হলো ভেরিয়েবলের নাম (#var_name_as_str শুধু একটি হেল্পার মেথড যেটা var_binding.left.name-এর সমতুল্য)। এই মুহূর্তে, সব ভেরিয়েবল গ্লোবাল। আমরা স্কোপিং (scoping) পরবর্তী পোস্টে হ্যান্ডেল করব।

মান (value) হলো অ্যাসাইনমেন্টের ডান দিকের এক্সপ্রেশন ইন্টারপ্রেট করার ফলাফল। সেটা করার জন্য, আমরা আবার #interpret_node ব্যবহার করি। যেহেতু ডান দিকে একটি AST::UnaryOperator আছে, পরবর্তী কল হবে #interpret_unary_operator:

def interpret_unary_operator(unary_op) case unary_op.operator when :'-' -(interpret_node(unary_op.operand)) else # :'!' !(interpret_node(unary_op.operand)) end end 

স্টফল সাপোর্টেড ইউনারি অপারেটর (- এবং !)র সেমান্টিক্স রুবির মতোই। ফলস্বরূপ, ইমপ্লিমেন্টেশন এর চেয়ে সহজ হতে পারে না: আমরা রুবির - অপারেটর অ্যাপ্লাই করি অপারেন্ড ইন্টারপ্রেট করার ফলাফলে। সেটা আবার #interpret_node। আপনি আমাদের প্রোগ্রামের AST থেকে মনে করছেন, --এর অপারেন্ড হলো একটি AST::Number (নাম্বার 2)। এর মানে আমাদের পরবর্তী पड़াব #interpret_number:

def interpret_number(number) number.value end 

#interpret_number-র ইমপ্লিমেন্টেশন একদম সহজ। নাম্বার লিটেরেলের রিপ্রেজেন্টেশন হিসেবে রুবি ফ্লোট (Ruby float) ব্যবহার করার সিদ্ধান্ত (এটা লেক্সারে হয়!) এখানে ফল দিচ্ছে। AST::Number নোডের @value ইতিমধ্যে আমাদের ডিজায়ার্ড ইন্টারন্যাল রিপ্রেজেন্টেশন ধরে রেখেছে, তাই আমরা শুধু সেটা রিট্রিভ করি।

এভাবে, আমরা AST::Program-র প্রথম ডায়রেক্ট চাইল্ড ইন্টারপ্রেট করা শেষ করলাম। এখন, আমাদের প্রোগ্রাম ইন্টারপ্রেট করা শেষ করার জন্য, আমাদের এর অন্য, আরও জটিল চাইল্ড হ্যান্ডেল করতে হবে: একটি AST::Conditional টাইপের নোড।

শর্ত এবং নিয়ম লাগতে পারে (Terms and Conditions May Apply)

#interpret_nodes-এ ফিরে, আমাদের বেস্ট ফ্রেন্ড #interpret_node আবার কল হয় AST::Program-র পরবর্তী ডায়রেক্ট চাইল্ড ইন্টারপ্রেট করতে।

def interpret_nodes(nodes) last_value = nil nodes.each do |node| last_value = interpret_node(node) end last_value end 

AST::Conditional ইন্টারপ্রেট করার জন্য দায়বদ্ধ মেথড হলো #interpret_conditional। সেটা দেখার আগে, তবে, আসুন মনে করি AST::Conditional-র নিজস্ব ইমপ্লিমেন্টেশনটি রিভিউ করে:

class Stoffle::AST::Conditional < Stoffle::AST::Expression attr_accessor :condition, :when_true, :when_false def initialize(cond_expr = nil, true_block = nil, false_block = nil) @condition = cond_expr @when_true = true_block @when_false = false_block end def ==(other) children == other&.children end def children [condition, when_true, when_false] end end 

ওকে, তাহলে @condition একটি এক্সপ্রেশন ধরে রাখে যেটা হয় truthy হবে নাকি falsey; @when_true এক বা একাধিক এক্সপ্রেশন সহ একটি ব্লক ধরে রাখে যেটা এক্সিকিউট হবে যদি @condition truthy হয়, এবং @when_false (ELSE ক্লজ) সে ব্লক ধরে রাখে যেটা রান হবে যদি @condition falsey হয়।

এখন, #interpret_condition দেখি:

def interpret_conditional(conditional) evaluated_cond = interpret_node(conditional.condition) # We could implement the line below in a shorter way, but better to be explicit about truthiness in Stoffle. if evaluated_cond == nil || evaluated_cond == false return nil if conditional.when_false.nil? interpret_nodes(conditional.when_false.expressions) else interpret_nodes(conditional.when_true.expressions) end end 

স্টফলে truthiness রুবির মতোই। অন্য কথায়, স্টফলে শুধু nil এবং false falsey। কন্ডিশনে যেকোনো অন্য ইনপুট truthy।

আমরা প্রথমে কন্ডিশন ইভ্যালুয়েট করি conditional.condition ধরে থাকা এক্সপ্রেশন ইন্টারপ্রেট করে। আবার আমাদের প্রোগ্রামের AST দেখি কী নোড হ্যান্ডেল করছি:

দেখতে পাচ্ছি, আমাদের একটি AST::BinaryOperator আছে (> যেটা num > 0-এ ব্যবহার হয়েছে)। ঠিক একই পথ: প্রথম #interpret_node, যা এই বার #interpret_binary_operator কল করে:

def interpret_binary_operator(binary_op) case binary_op.operator when :and interpret_node(binary_op.left) && interpret_node(binary_op.right) when :or interpret_node(binary_op.left) || interpret_node(binary_op.right) else interpret_node(binary_op.left).send(binary_op.operator, interpret_node(binary_op.right)) end end 

আমাদের লজিক্যাল অপারেটর (and এবং or) বাইনারি অপারেটর হিসেবে বিবেচনা করা যায়, তাই আমরা সেগুলো এখানেই হ্যান্ডেল করি। যেহেতু তাদের সেমান্টিক্স রুবির && এবং ||-এর সমতুল্য, ইমপ্লিমেন্টেশন একদম স্মুথ, আপনি উপরে দেখতে পাচ্ছেন।

পরবর্তী সেকশনটি আমাদের সবচেয়ে বেশি আগ্রহের; এই সেকশন অন্যান্য সব বাইনারি অপারেটর হ্যান্ডেল করে (এবং > সহ)। এখানে, আমরা রুবির ডাইনামিজম (dynamism) আমাদের পার সাইডে ব্যবহার করতে পারি এবং একটি খুব সংক্ষিপ্ত সমাধান বের করতে পারি। রুবিতে, বাইনারি অপারেটর অবজেক্টগুলোর মেথড হিসেবে উপলব্ধ থাকে যেগুলো একটি অপারেশনে অংশগ্রহণ করে:

-2 > 0 # is equivalent to -2.send(:'>', 0) # this # and the following line would be a general solution, # very similar to what we have in the interpreter operand_1.send(binary_operator, operand_2) 

বাইনারি অপারেটরverbose ইমপ্লিমেন্টেশন

আপনি দেখলেন, আমাদের বাইনারি অপারেটর ইমপ্লিমেন্টেশন খুব সংক্ষিপ্ত। যদি রুবি এত ডাইনামিক ভাষা না হত, অথবা অপারেটরদের সেমান্টিক্স রুবি এবং স্টফলে ভিন্ন হত, তবে আমরা এই ফ্যাশনে কোড করতে পারতাম না।

আপনি যদি কখনো এমন পজিশনে পড়েন একটি ল্যাঙ্গুয়েজ ডিজাইনার/ইমপ্লিমেন্টর হিসেবে, তবে আপনি সবসময় ফলব্যাক করতে পারেন একটি সিম্পল (তবে এত elegante নয়) সমাধানে: একটি সوییচ কনস্ট্রাক্ট ব্যবহার করে। আমাদের কেসে, ইমপ্লিমেন্টেশন এরকম দেখত:

# ... inside #interpret_binary_operator ... case binary_op.operator when :'+' interpret_node(binary_op.left) + interpret_node(binary_op.right) # ... other operators end 

#interpret_conditional-এ ফিরার আগে, একটু বিচলন করি নিশ্চিত করার জন্য কিছু ছুটে নয়। আপনি যদি মনে করেন যে প্রোগ্রামটি আমরা ইন্টারপ্রেট করছি, num ভেরিয়েবলটি কমপোরিজনে ব্যবহার হয়েছে (বাইনারি অপারেটর > দিয়ে) যা আমরা এখন এক্সপ্লোর করলাম। আমরা কিভাবে বাম অপারেন্ড (অর্থাৎ num ভেরিয়েবলে স্টোর করা মান) রিট্রিভ করলাম সেটা কমপোরিজনের? সেটার জন্য দায়বদ্ধ মেথড হলো #interpret_identifier, এবং এর ইমপ্লিমেন্টেশন সহজ-সহজ:

def interpret_identifier(identifier) if env.has_key?(identifier.name) env[identifier.name] else # Undefined variable. raise Stoffle::Error::Runtime::UndefinedVariable.new(identifier.name) end end 

এখন, আবার #interpret_conditional-এ। আমাদের ছোট প্রোগ্রামের কেসে, কন্ডিশন ইভ্যালুয়েট হয়ে রুবি false ভ্যালুতে। আমরা এই ভ্যালু ব্যবহার করি নির্ধারণ করতে যে আমাদের IF ব্রাঞ্চ এক্সিকিউট করতে হবে নাকি ELSE ব্রাঞ্চ। আমরা ELSE ব্রাঞ্চ ইন্টারপ্রেট করতে যাই, যেটার অ্যাসোসিয়েটেড ব্লক কোড conditional.when_false-এ স্টোর করা আছে। এখানে, আমাদের একটি AST::Block আছে, যা আমাদের AST-র রুট নোড (AST::Program)র সাথে খুব সাদৃশ্য। ব্লকটিও, একইভাবে, পটেনশিয়ালি একাধিক এক্সপ্রেশন ধরে রাখে যেগুলো ইন্টারপ্রেট করতে হবে। এই উদ্দেশ্যে, আমরা একইভাবে #interpret_nodes ব্যবহার করি।

def interpret_conditional(conditional) evaluated_cond = interpret_node(conditional.condition) # We could implement the line below in a shorter way, but better to be explicit about truthiness in Stoffle. if evaluated_cond == nil || evaluated_cond == false return nil if conditional.when_false.nil? interpret_nodes(conditional.when_false.expressions) else interpret_nodes(conditional.when_true.expressions) end end 

আমাদের যে পরবর্তী AST নোড হ্যান্ডেল করতে হবে সেটা একটি AST::FunctionCall। ফাংশন কল ইন্টারপ্রেট করার জন্য দায়বদ্ধ মেথড হলো #interpret_function_call:

def interpret_function_call(fn_call) return if println(fn_call) end 

আর্টিকেলের শুরুতে আলোচনা করা হয়েছে, ফাংশন ডেফিনিশন এবং ফাংশন কলিং পরবর্তী পোস্টে কভার হবে। তাই, আমরা শুধু ফাংশন কলিং এর একটি স্পেশাল কেস ইমপ্লিমেন্ট করছি। আমাদের ছোট টয় ল্যাঙ্গুয়েজে, আমরা println রানটাইমের অংশ হিসেবে প্রদান করি এবং সেটা সরাসরি ইন্টারপ্রেটারে ইমপ্লিমেন্ট করি এখানে। আমাদের প্রজেক্টের উদ্দেশ্য এবং স্কোপ বিবেচনা করলে এটা যথেষ্ট ভালো সমাধান।

def println(fn_call) return false if fn_call.function_name_as_str != 'println' result = interpret_node(fn_call.args.first).to_s output << result puts result true end 

আমাদের AST::FunctionCall-র প্রথম এবং একমাত্র আর্গুমেন্ট হলো একটি AST::String, যেটা #interpret_string হ্যান্ডেল করে:

def interpret_string(string) string.value end 

#interpret_string-এ, আমাদের একদম #interpret_number-এর মতো কেস। একটি AST::String ইতিমধ্যে একটি রেডি-টু-ইউজ রুবি স্ট্রিং ভ্যালু ধরে রাখে, তাই আমাদের শুধু সেটা রিট্রিভ করতে হয়।

আবার #println-এ:

def println(fn_call) return false if fn_call.function_name_as_str != 'println' result = interpret_node(fn_call.args.first).to_s output << result puts result true end 

ফাংশন আর্গুমেন্ট (রুবি স্ট্রিং-এ কনভার্টেড) result-এ স্টোর করার পর, আমাদের আরো দুটি ধাপ বাকি। প্রথম, আমরা যা কনসোলে প্রিন্ট করতে যাচ্ছি সেটা @output-এ স্টোর করি। পূর্বে এক্সপ্লেইন করা হয়েছে, এখানে আইডিয়া হলো সহজে ইন্সপেক্ট করা যা প্রিন্ট হয়েছে (এবং কোন ক্রমে)। ডিবাগ বা টেস্ট করার সময় এটা আমাদের জীবন সহজ করে। শেষে, কনসোলে কিছু প্রিন্ট করতে, আমরা রুবির puts ব্যবহার করি।

এক্সিকিউশন ম্যাটার্স (Execution Matters)

এখন যেহেতু আমরা স্টফলের বেয়ার-বোনস (bare-bones) ইমপ্লিমেন্ট করার সব কিছু এক্সপ্লোর করলাম, চলুন একটি ভাবেজ এক্সিকিউটেবল বানাই আমাদের ইন্টারপ্রেটার একশনে দেখতে।

#!/usr/bin/env ruby require_relative '../lib/stoffle' path = ARGV[0] source = File.read(path) lexer = Stoffle::Lexer.new(source) parser = Stoffle::Parser.new(lexer.start_tokenization) interpreter = Stoffle::Interpreter.new interpreter.interpret(parser.parse) exit(0) 

টিপ: সিস্টেমের যেকোনো জায়গা থেকে স্টফলের ইন্টারপ্রেটার ব্যবহার করতে, এক্সিকিউটেবলকে আপনার PATH-এ যোগ করা মনে রাখবেন।

এখন আমাদের প্রোগ্রাম রান করার পালা। সব ঠিক থাকলে, আমরা স্ট্রিং "The number is less than or equal to zero" কনসোলে প্রিন্ট হয়ে দেখব। এটা ঠিকই যা হয় যখন আমরা ইন্টারপ্রেটার রান করি:

টিপ: আপনার ইন্টারপ্রেটার ইনস্টলড থাকলে, আমাদের স্যাম্পল প্রোগ্রামে num ভেরিয়েবল পরিবর্তন করুন যাতে সেটা শূন্য থেকে বড় একটি নাম্বার ধরে। প্রত্যাশা অনুযায়ী, এখন IF ব্রাঞ্চ এক্সিকিউট হবে, এবং স্ট্রিং "The number is greater than zero" প্রিন্ট আউট হবে।

শেষ বন্দনা (Wrapping Up)

এই পোস্টে, আমরা স্টফলের ইন্টারপ্রেটার শুরু দেখলাম। আমরা ইন্টারপ্রেটারের পর্যাপ্ত অংশ ইমপ্লিমেন্ট করলাম যাতে এটা ভাষার কিছু বেসিক হ্যান্ডেল করতে পারে: ভেরিয়েবল, কন্ডিশনাল, ইউনারি এবং বাইনারি অপারেটর, ডেটা টাইপ, এবং কনসোলে প্রিন্ট করা। পরবর্তী এবং শেষ পার্টে ইন্টারপ্রেটারের ওপর, আমরা বাকি বিটস ট্যাকল করব যাতে আমাদের ছোট টয় ল্যাঙ্গুয়েজ ডিজাইন অনুযায়ী কাজ করে: ভেরিয়েবল স্কোপিং, ফাংশন ডেফিনিশন, ফাংশন কলিং, এবং লুপ। আশা করি আর্টিকেলটি পড়তে মজা পেয়েছেন (আমি লিখতে মজা পেলাম!), এবং সিরিজের পরবর্তী পোস্টে দ্রুত দেখা হবে!