การสร้าง Ruby Interpreter สำหรับภาษา Stoffle

Full Source on Github

การนำภาษาโปรแกรมมิ่ง Stoffle ไปใช้งานอย่างสมบูรณ์มีให้ที่ GitHub โปรดเปิด issue หากพบ bugs หรือมีคำถาม

ในบล็อกนี้ เราจะเริ่ม implement interpreter สำหรับ Stoffle ภาษาโปรแกรมมิ่งเล็กๆ ที่สร้างขึ้นทั้งหมดด้วย Ruby คุณอ่านเพิ่มเติมได้จากภาคแรกของซีรีส์นี้

Interpreter ที่เราจะสร้าง มักเรียกว่า tree-walk interpreter ในบทความก่อนหน้าของซีรีส์ เราสร้าง parser เพื่อแปลง flat sequence of tokens เป็น tree data structure (abstract syntax tree หรือ AST) ตามที่คุณจินตนาการ interpreter ของเรามีหน้าที่เดินผ่าน AST ที่ parser สร้าง และให้น้ำชีพกับ Stoffle program ผมคิดว่าขั้นตอนสุดท้ายนี้ exciting ที่สุดของ language implementation journey ตอนสร้าง interpreter ทุกอย่าง finally clicks และเราสามารถเห็น Stoffle programs running จริง!

ผมจะ show และ explain interpreter implementation ในสองส่วน ในส่วนแรกนี้ เราจะทำ basics ให้ทำงาน: variables, conditionals, unary และ binary operators, data types และ printing to console เราส่วนที่ meaty (function definition, function calling, loops ฯลฯ) ไว้สำหรับโพสต์ที่สองและสุดท้ายเกี่ยวกับการ implement interpreter

A Quick Recap of the Lexer and Parser (สรุป Lexer และ Parser แบบรวดเร็ว)

ก่อนจะ dive in และเริ่ม implement interpreter มาทบทวนสิ่งที่เราทำในโพสต์ก่อนหน้าของซีรีส์ ก่อนอื่น เราสร้าง lexer ซึ่งแปลง raw source code เป็น tokens จากนั้นเรา implement parser component ที่รับผิดชอบ morph tokens เป็น tree structure (AST) สรุป transformations ที่เราสังเกต:

State 0: Source

my_var = 1 

State 1: Lexer transforms raw source code into tokens

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

State 2: Parser transforms tokens into an Abstract Syntax Tree

It's All About Walking (ทั้งหมดเกี่ยวกับการเดิน)

ตอนนี้เรามี AST หน้าที่ของเราคือเขียนโค้ดเดินโครงสร้างนี้ เราต้องเขียน Ruby code ที่ให้ชีวิตกับสิ่งที่แต่ละ node ใน AST ของเราอธิบาย หากเรามี node ที่อธิบาย variable binding ตัวอย่าง โค้ด Ruby ของเราต้องสามารถ store result ของ right-hand side ของ variable binding expression และมี storage space associated with (และ accessible through) ชื่อที่ให้กับตัวแปร

เหมือนที่เราทำในส่วนก่อนหน้าของซีรีส์ เราจะสำรวจ implementation โดยเดินผ่าน all important lines of code ที่เกี่ยวข้องกับ example program ชิ้นของ Stoffle code ที่เราต้อง interpret คือ:

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 ที่ผลิตสำหรับโปรแกรมเดียวกัน:

The First Step in Our Walk (ขั้นตอนแรกในการเดินของเรา)

เหมือนที่คุณจำได้จากโพสต์ล่าสุดในซีรีส์ Stoffle AST เสมอมี root เป็น AST::Program node Root นี้โดยทั่วไปมี multiple children บางอันจะเป็น shallow (คิดถึง AST ที่ผลิตสำหรับ simple variable assignment) อื่นๆ อาจเป็น root ของ deep subtrees (คิดถึง loop พร้อมหลายบรรทัดภายใน body) นี่คือ Ruby code ที่เราต้องการเริ่มเดินผ่าน AST ที่ส่งเข้า interpreter:

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 ใหม่ถูก instantiate เริ่มจาก get-go เราสร้างสอง instance variables: @output และ @env หน้าที่ของ former คือ store ใน chronological sequence ทุกอย่างที่โปรแกรมพิมพ์ออกมา ข้อมูลนี้ useful มากเมื่อเขียน automated tests หรือ debugging หน้าที่ของ @env แตกต่างออกไป เราตั้งชื่อว่า "environment" ตามที่ชื่อบ่งชี้ ฟังก์ชันคือ hold state ของ running program หนึ่งในฟังก์ชันคือ implement binding ระหว่าง identifier (เช่น variable name) และ current value

เมธอด #interpret_nodes loop ผ่าน all children ของ root node (AST::Program) แล้วเรียก #interpret_node สำหรับแต่ละ node

#interpret_node เรียบง่ายแตน่าสนใจ ที่นี่เราใช้ Ruby metaprogramming เล็กน้อยเพื่อเรียก method ที่เหมาะสมสำหรับ handle node type ปัจจุบัน ตัวอย่าง สำหรับ AST::VarBinding node #interpret_var_binding method คือที่ถูกเรียก

Invariably, We Have to Talk About Variables (ไม่ว่าจะอย่างไร เราต้องพูดถึงตัวแปร)

Node แรกที่เราต้อง interpret ใน AST ของ example program คือ AST::VarBinding @left เป็น AST::Identifier และ @right เป็น AST::UnaryOperator มาดู method ที่รับผิดชอบ interpret variable binding:

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

เห็นได้ว่ามัน straightforward เรา add (หรือ overwrite) key-value pair ให้ @env Hash

Key คือชื่อตัวแปร (#var_name_as_str เป็น helper method เทียบเท่า var_binding.left.name) ในขณะนี้ ตัวแปรทั้งหมดเป็น global เราจะ handle scoping ในโพสต์ถัดไป

Value คือ result ของการ interpret expression ด้านขวาของ assignment เพื่อทำนั้น เราใช้ #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 

Semantics ของ Stoffle's supported unary operators (- และ !) เหมือน Ruby ดังนั้น implementation ไม่ได้ simpler: เรา apply Ruby's - operator ไป result ของการ interpret operand ปกติ #interpret_node 出现อีกครั้ง ตามที่คุณจำได้จาก AST ของโปรแกรม operand สำหรับ - คือ AST::Number (ตัวเลข 2) หมายถึง next stop คือ #interpret_number:

def interpret_number(number) number.value end 

Implementation ของ #interpret_number เป็น piece of cake การตัดสินใจใช้ Ruby float แทน number literals (เกิดใน lexer!) ให้ผลที่นี่ @value ของ AST::Number node เก็บ internal representation ของ numbers ที่เราต้องการแล้ว ดังนั้นเราแค่ retrieve it

ด้วยนั้น เรา interpret direct child แรกของ AST::Program เสร็จ ตอนนี้เพื่อ conclude interpreting โปรแกรม เราต้อง handle child อีกตัวที่ hairy: node type AST::Conditional

Terms and Conditions May Apply (เงื่อนไขและข้อกำหนดอาจใช้ได้)

กลับไปที่ #interpret_nodes เพื่อนสนิท #interpret_node ถูกเรียกอีกครั้งเพื่อ interpret direct child ถัดไปของ AST::Program

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

Method ที่รับผิดชอบ interpret AST::Conditional คือ #interpret_conditional ก่อนดูมัน มาทบทวน implementation ของ 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 

Ok @condition เก็บ expression ที่จะเป็น truthy หรือ falsey @when_true เก็บ block พร้อม expressions หนึ่งหรือหลาย เพื่อ execute หาก @condition truthy และ @when_false (ELSE clause) เก็บ block รันหาก @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 ใน Stoffle เหมือน Ruby กล่าวคือ ใน Stoffle มีแค่ nil และ false เป็น falsey Input อื่นๆ ให้ condition เป็น truthy

เรา evaluate condition โดย interpret expression ที่ conditional.condition เก็บ มาดู AST ของโปรแกรมอีกครั้งเพื่อ 알아 node ที่เรา deal:

พบว่าเรามี AST::BinaryOperator (คือ > ใช้ใน num > 0) Ok same path อีกครั้ง: #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 

Logical operators (and และ or) ถือเป็น binary operators ดังนั้นเราจัดการที่นี่ด้วย เนื่องจาก semantic เทียบเท่า Ruby's && และ || implementation จึง plain sailing

ต่อไปคือ section ที่เราสนใจที่สุด section นี้ handle binary operators อื่นๆ (รวม >) ที่นี่เราสามารถ leverage Ruby's dynamism เพื่อ solution ที่ concise ใน Ruby binary operators available as methods ใน objects ที่ participate ใน operation:

-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) 

A Verbose Implementation of Binary Operators (การนำ Binary Operators ไปใช้งานแบบ Verbose)

เห็นได้ว่า implementation ของ binary operators เรา concise มาก หาก Ruby ไม่ได้เป็น dynamic language หรือ semantics ของ operators แตกต่างระหว่าง Ruby และ Stoffle เราไม่สามารถ code solution ใน fashion นี้ได้

หากคุณพบตัวเองในตำแหน่ง language designer/implementer คุณสามารถ fallback ไป simple (แตไม่ elegant) solution: ใช้ switch construct ในกรณีของเรา implementation จะดูเหมือนนี้:

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

ก่อนกลับไป #interpret_conditional มา quick detour ให้แน่ใจว่าไม่พลาดอะไร หากคุณจำโปรแกรมที่เรา interpret ตัวแปร num ถูกใช้ใน comparison (binary operator >) ที่เราสำรวจไป ตัวเรา retrieve left operand (ค่าที่เก็บใน num) ของ comparison นั้นอย่างไร? Method ที่รับผิดชอบคือ #interpret_identifier และ implementation ง่ายมาก:

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 ในกรณีโปรแกรมเล็กของเรา condition evaluated เป็น Ruby false เราใช้ค่านี้ decide ว่าต้อง execute IF หรือ ELSE branch ของ conditional structure เรา interpret ELSE branch ที่ block of code เก็บใน conditional.when_false ที่นี่เรามี AST::Block ซึ่งคล้าย root node ของ AST (AST::Program) Block เหมือนกัน potentially มี expressions หลายตัวที่ต้อง interpret สำหรับวัตถุประสงค์นี้ เราใช้ #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 node ถัดไปที่เราต้อง handle คือ AST::FunctionCall Method ที่รับผิดชอบ interpret function call คือ #interpret_function_call:

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

เหมือนที่เราพูดในต้นบทความ function definition และ function calling จะครอบคลุมใน next post ในซีรีส์ ดังนั้นเรา implement แค่ special case ของ function calling ในภาษาเล็กของเรา เรา provide println as part of runtime และ implement โดยตรงใน interpreter ที่นี่ มัน good enough solution ถึง objectives และ scope ของโปรเจกต์

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 

Argument แรกและเดียวของ AST::FunctionCall คือ AST::String ซึ่งถูก handle โดย #interpret_string:

def interpret_string(string) string.value end 

ใน #interpret_string เรามี exact same case ของ #interpret_number AST::String เก็บ ready-to-use Ruby string value แล้ว ดังนั้นเราแค่ retrieve it

กลับไป #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 

หลัง store function argument (converted to Ruby string) ใน result เรามีอีกสองขั้นตอน ก่อน เรา store สิ่งที่จะ print ไป console ใน @output ตามที่อธิบายไปแล้ว idea คือ inspect ได้ง่ายว่าพิมพ์อะไรไป (และลำดับ) มีสิ่งนี้ช่วยชีวิตเราตอน debugging หรือ testing interpreter สุดท้าย เพื่อ implement print something to console เราใช้ Ruby's puts

Execution Matters (การ Execute สำคัญ)

ตอนนี้เราสำรวจทุกอย่างที่จำเป็น implement bare-bones ของ Stoffle มาสร้าง basic executable เพื่อเห็น interpreter ใน action

#!/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) 

TIP: เพื่อใช้ Stoffle's interpreter จาก anywhere จำได้ว่า add executable ไป PATH

มาถึงเวลารันโปรแกรม หากทุกอย่างทำงานดี เราควรเห็น string "The number is less than or equal to zero" พิมพ์ออก console นี่คือสิ่งที่เกิดขึ้นเมื่อเรารัน interpreter:

TIP: หากคุณติดตั้ง interpreter ลองเปลี่ยน num variable ใน sample program ให้มันเก็บ number greater than zero ตามคาด IF branch จะ execute และ string "The number is greater than zero" จะพิมพ์ออกมา

Wrapping Up (สรุป)

ในโพสต์นี้ เราเห็น beginnings ของ Stoffle's interpreter เรา implement interpreter ให้เพียงพอ handle language basics: variables, conditionals, unary และ binary operators, data types และ printing to console ใน next และ final part บน interpreter เราจะ tackle remaining bits ที่จำเป็นให้เรามี toy language ทำงาน as designed: variable scoping, function definition, function calling และ loops ผมหวังว่าคุณสนุกอ่านบทความ (ผมสนุกเขียนแน่นอน!) และจะเจอกันเร็วๆ ใน next post ของซีรีส์!