การสร้างภาษาโปรแกรมใน Ruby:The Interpreter ตอนที่ 2

ที่มาแบบเต็มบน Github

มีการใช้งานภาษาการเขียนโปรแกรม Stoffle อย่างสมบูรณ์บน GitHub อย่าลังเลที่จะเปิดปัญหาหากคุณพบข้อบกพร่องหรือมีคำถาม

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

ในโพสต์ที่แล้ว เราได้กล่าวถึงวิธีการใช้คุณลักษณะที่ง่ายกว่าของ Stoffle:ตัวแปร เงื่อนไข ตัวดำเนินการ unary และไบนารี ประเภทข้อมูล และการพิมพ์ไปยังคอนโซล ตอนนี้ ถึงเวลาที่จะพับแขนเสื้อขึ้นและจัดการกับบิตที่เหลืออยู่ที่ท้าทายยิ่งขึ้น:การกำหนดฟังก์ชัน การเรียกใช้ฟังก์ชัน การกำหนดขอบเขตตัวแปร และการวนซ้ำ

อย่างที่เราทำก่อนหน้านี้ เราจะใช้โปรแกรมตัวอย่างเดียวกันตั้งแต่ต้นจนจบบทความนี้ เราจะดำเนินการทีละบรรทัด โดยสำรวจการใช้งานที่จำเป็นที่ล่ามเพื่อทำให้โครงสร้างต่างๆ แตกต่างกันในโปรแกรมตัวอย่าง Stoffle ของเรา สุดท้าย เราจะเห็นการทำงานของล่ามและเรียกใช้โปรแกรมโดยใช้ CLI ที่เราสร้างขึ้นในบทความก่อนหน้าของซีรีส์นี้

เกาส์กลับมาแล้ว

หากคุณมีความจำที่ดี คุณอาจจะจำได้ว่าในตอนที่สองของซีรีส์นี้ เราได้พูดถึงวิธีสร้าง Lexer ในโพสต์นั้น เราได้ดูโปรแกรมเพื่อสรุปตัวเลขในชุดข้อมูลเพื่อแสดงรูปแบบไวยากรณ์ของ Stoffle ในตอนท้ายของบทความนี้ ในที่สุดเราก็จะสามารถเรียกใช้โปรแกรมดังกล่าวได้! นี่คือโปรแกรมอีกครั้ง:

fn sum_integers: first_integer, last_integer
  i = first_integer
  sum = 0
  while i <= last_integer
    sum = sum + i

    i = i + 1
  end

  println(sum)
end

sum_integers(1, 100)

ต้นไม้ไวยากรณ์นามธรรม (AST) สำหรับโปรแกรมบวกจำนวนเต็มของเรามีดังต่อไปนี้:

นักคณิตศาสตร์ที่เป็นแรงบันดาลใจให้โปรแกรมตัวอย่าง Stoffle ของเรา

คาร์ล ฟรีดริช เกาส์น่าจะคิดสูตรในการรวมตัวเลขในซีรีส์ด้วยตัวเขาเองเมื่ออายุเพียง 7 ขวบ

อย่างที่คุณอาจสังเกตเห็น โปรแกรมของเราไม่ได้ใช้สูตรที่เกาส์เป็นผู้คิดค้น เนื่องจากเรามีคอมพิวเตอร์ในปัจจุบัน เราจึงมีความหรูหราในการแก้ปัญหานี้ด้วยวิธี "เดรัจฉาน" ให้เพื่อนซิลิคอนทำงานหนักเพื่อเรา

คำจำกัดความของฟังก์ชัน

สิ่งแรกที่เราทำในโปรแกรมของเราคือกำหนด sum_integers การทำงาน. การประกาศฟังก์ชันหมายความว่าอย่างไร คุณอาจเดาได้ว่าเป็นการกระทำที่คล้ายกับการกำหนดค่าให้กับตัวแปร เมื่อเรากำหนดฟังก์ชัน เรากำลังเชื่อมโยงชื่อ (เช่น ชื่อฟังก์ชัน ตัวระบุ) กับนิพจน์อย่างน้อย 1 รายการ (เช่น เนื้อหาของฟังก์ชัน) เรายังลงทะเบียนว่าชื่อใดที่ค่าที่ส่งผ่านในระหว่างการเรียกใช้ฟังก์ชันควรผูกไว้ ตัวระบุเหล่านี้กลายเป็นตัวแปรภายในระหว่างการทำงานของฟังก์ชันและเรียกว่าพารามิเตอร์ ค่าที่ส่งผ่านเมื่อมีการเรียกใช้ฟังก์ชัน (และเชื่อมโยงกับพารามิเตอร์) เป็นอาร์กิวเมนต์

มาดู #interpret_function_definition . กัน :

def interpret_function_definition(fn_def)
  env[fn_def.function_name_as_str] = fn_def
end

ค่อนข้างตรงไปตรงมาใช่มั้ย อย่างที่คุณอาจจำได้จากโพสต์ที่แล้วในซีรีส์นี้ เมื่อล่ามของเราสร้างอินสแตนซ์ เราจะสร้างสภาพแวดล้อม นี่คือสถานที่ที่ใช้ในการเก็บสถานะของโปรแกรม และในกรณีของเรา มันเป็นเพียงแฮชทับทิม ในโพสต์ที่แล้ว เราเห็นว่าตัวแปรและค่าที่ผูกกับตัวแปรเหล่านั้นถูกเก็บไว้ใน env อย่างไร . คำจำกัดความของฟังก์ชันจะถูกเก็บไว้ที่นั่นด้วย คีย์คือชื่อฟังก์ชัน และค่าคือโหนด AST ที่ใช้กำหนดฟังก์ชัน (Stoffle::AST::FunctionDefinition ). นี่คือการทบทวนเกี่ยวกับโหนด AST นี้:

class Stoffle::AST::FunctionDefinition < Stoffle::AST::Expression
  attr_accessor :name, :params, :body

  def initialize(fn_name = nil, fn_params = [], fn_body = nil)
    @name = fn_name
    @params = fn_params
    @body = fn_body
  end

  def function_name_as_str
    # The instance variable @name is an AST::Identifier.
    name.name
  end

  def ==(other)
    children == other&.children
  end

  def children
    [name, params, body]
  end
end

มีชื่อฟังก์ชันที่เชื่อมโยงกับ Stoffle::AST::FunctionDefinition หมายความว่าเราสามารถเข้าถึงข้อมูลทั้งหมดที่จำเป็นในการเรียกใช้ฟังก์ชัน ตัวอย่างเช่น เรามีจำนวนอาร์กิวเมนต์ที่คาดหวังและสามารถปล่อยข้อผิดพลาดได้อย่างง่ายดายหากไม่มีการเรียกใช้ฟังก์ชัน นี้และรายละเอียดอื่นๆ ที่เราจะได้เห็นเมื่อเราสำรวจ ต่อไป โค้ดที่รับผิดชอบในการตีความการเรียกใช้ฟังก์ชัน

การเรียกใช้ฟังก์ชัน

ต่อจากตัวอย่างของเรา ตอนนี้ให้เราเน้นที่การเรียกใช้ฟังก์ชัน หลังจากกำหนด sum_integers ฟังก์ชัน เราเรียกว่าส่งผ่านตัวเลข 1 และ 100 เป็นอาร์กิวเมนต์:

fn sum_integers: first_integer, last_integer
  i = first_integer
  sum = 0
  while i <= last_integer
    sum = sum + i

    i = i + 1
  end

  println(sum)
end

sum_integers(1, 100)

การตีความการเรียกใช้ฟังก์ชันเกิดขึ้นที่ #interpret_function_call :

def interpret_function_call(fn_call)
  return if println(fn_call)

  fn_def = fetch_function_definition(fn_call.function_name_as_str)

  stack_frame = Stoffle::Runtime::StackFrame.new(fn_def, fn_call)

  assign_function_args_to_params(stack_frame)

  # Executing the function body.
  call_stack << stack_frame
  value = interpret_nodes(fn_def.body.expressions)
  call_stack.pop
  value
end

นี่เป็นฟังก์ชันที่ซับซ้อน ดังนั้นเราต้องใช้เวลาที่นี่ ตามที่อธิบายไว้ในบทความที่แล้ว บรรทัดแรกมีหน้าที่ตรวจสอบว่าฟังก์ชันที่ถูกเรียกคือ println . หากเรากำลังจัดการกับฟังก์ชันที่ผู้ใช้กำหนด ซึ่งในกรณีนี้ เราจะดำเนินการต่อไปและดึงคำจำกัดความของฟังก์ชันโดยใช้ #fetch_function_definition . ดังที่แสดงด้านล่าง ฟังก์ชันนี้เป็นแบบธรรมดา และโดยทั่วไปเราจะดึงข้อมูล Stoffle::AST::FunctionDefinition AST node ที่เราจัดเก็บไว้ก่อนหน้านี้ในสภาพแวดล้อมหรือปล่อยข้อผิดพลาดหากไม่มีฟังก์ชัน

def fetch_function_definition(fn_name)
  fn_def = env[fn_name]
  raise Stoffle::Error::Runtime::UndefinedFunction.new(fn_name) if fn_def.nil?

  fn_def
end

กลับไปที่ #interpret_function_call สิ่งต่าง ๆ เริ่มมีความน่าสนใจมากขึ้น เมื่อคิดถึงฟังก์ชันในภาษาของเล่นง่ายๆ เรามีข้อกังวลพิเศษสองประการ อันดับแรก เราต้องการกลยุทธ์ในการติดตามตัวแปรท้องถิ่นของฟังก์ชัน เรายังต้องจัดการกับ return นิพจน์ เพื่อจัดการกับความท้าทายเหล่านี้ เราจะยกตัวอย่างวัตถุใหม่ ซึ่งเราจะเรียกว่า เฟรม ทุกครั้งที่มีการเรียกใช้ฟังก์ชัน แม้ว่าจะเรียกใช้ฟังก์ชันเดียวกันหลายครั้ง แต่การโทรใหม่แต่ละครั้งจะสร้างเฟรมใหม่ขึ้นมา วัตถุนี้จะเก็บตัวแปรทั้งหมดไว้ในฟังก์ชัน เนื่องจากฟังก์ชันหนึ่งสามารถเรียกใช้ฟังก์ชันอื่นได้ เราจึงต้องมีวิธีแสดงและติดตามโฟลว์การดำเนินการของโปรแกรมของเรา ในการดำเนินการดังกล่าว เราจะใช้โครงสร้างข้อมูลสแต็ก ซึ่งเราจะตั้งชื่อว่า คอลสแต็ก . ใน Ruby อาร์เรย์มาตรฐานที่มี #push และ #pop วิธีการจะทำเป็นการนำสแต็กไปใช้

เรียกสแต็กและสแต็กเฟรม

โปรดทราบว่าเราใช้คำว่า call stack และ stack frame อย่างอิสระ โดยทั่วไปแล้วโปรเซสเซอร์และภาษาการเขียนโปรแกรมระดับล่างจะมี call stacks และ stack frames แต่ก็ไม่ใช่สิ่งที่เรามีในภาษาของเล่นของเราอย่างแน่นอน

หากแนวคิดเหล่านี้กระตุ้นความอยากรู้ของคุณ เราขอแนะนำให้คุณศึกษา call stacks และ stack frames หากคุณต้องการเข้าใกล้โลหะมากขึ้น ฉันขอแนะนำให้มองหาคอลสแต็กของโปรเซสเซอร์โดยเฉพาะ

นี่คือรหัสสำหรับการติดตั้ง Stoffle::Runtime::StackFrame :

module Stoffle
  module Runtime
    class StackFrame
      attr_reader :fn_def, :fn_call, :env

      def initialize(fn_def_ast, fn_call_ast)
        @fn_def = fn_def_ast
        @fn_call = fn_call_ast
        @env = {}
      end
    end
  end
end

ตอนนี้ กลับไปที่ #interpret_function_call ขั้นตอนต่อไปคือการกำหนดค่าที่ส่งผ่านในการเรียกใช้ฟังก์ชันให้กับพารามิเตอร์ที่คาดหมายที่เกี่ยวข้อง ซึ่งจะสามารถเข้าถึงได้เป็นตัวแปรภายในเนื้อหาของฟังก์ชัน #assign_function_args_to_params เป็นผู้รับผิดชอบในขั้นตอนนี้:

def assign_function_args_to_params(stack_frame)
  fn_def = stack_frame.fn_def
  fn_call = stack_frame.fn_call

  given = fn_call.args.length
  expected = fn_def.params.length
  if given != expected
    raise Stoffle::Error::Runtime::WrongNumArg.new(fn_def.function_name_as_str, given, expected)
  end

  # Applying the values passed in this particular function call to the respective defined parameters.
  if fn_def.params != nil
    fn_def.params.each_with_index do |param, i|
      if env.has_key?(param.name)
        # A global variable is already defined. We assign the passed in value to it.
        env[param.name] = interpret_node(fn_call.args[i])
      else
        # A global variable with the same name doesn't exist. We create a new local variable.
        stack_frame.env[param.name] = interpret_node(fn_call.args[i])
      end
    end
  end
end

ก่อนที่เราจะสำรวจ #assign_function_args_to_params การนำไปปฏิบัติ จำเป็นอย่างยิ่งที่จะต้องหารือเกี่ยวกับขอบเขตตัวแปรโดยสังเขปก่อน นี่เป็นเรื่องที่ซับซ้อนและเหมาะสมยิ่ง สำหรับ Stoffle ขอให้เราปฏิบัติอย่างจริงจังและใช้วิธีแก้ปัญหาง่ายๆ ในภาษาเล็ก ๆ ของเรา โครงสร้างเดียวที่สร้างขอบเขตใหม่คือฟังก์ชัน นอกจากนี้ ตัวแปรส่วนกลางมักจะมาก่อนเสมอ ด้วยเหตุนี้ ตัวแปรทั้งหมดที่ประกาศ (เช่น การใช้งานครั้งแรก) นอกฟังก์ชันจะเป็นโกลบอลและจัดเก็บไว้ใน env . ตัวแปรภายในฟังก์ชันนั้นอยู่ในเครื่องและเก็บไว้ใน env ของสแต็กเฟรมที่สร้างขึ้นระหว่างการตีความการเรียกใช้ฟังก์ชัน มีข้อยกเว้นประการหนึ่งคือ:ชื่อตัวแปรที่ชนกับตัวแปรส่วนกลางที่มีอยู่ หากเกิดการชนกัน ตัวแปรโลคัลจะ ไม่ ถูกสร้างขึ้น และเราจะอ่านและกำหนดตัวแปรส่วนกลางที่มีอยู่

เอาล่ะ เมื่อกลยุทธ์การกำหนดขอบเขตตัวแปรของเราชัดเจนแล้ว กลับไปที่ #assign_function_args_to_params . ในส่วนแรกของเมธอด ก่อนอื่นเราจะดึงนิยามฟังก์ชันและโหนดการเรียกใช้ฟังก์ชันจากอ็อบเจ็กต์สแต็กเฟรมที่ส่งผ่านเข้ามา เมื่อมีสิ่งเหล่านี้อยู่ในมือ เป็นการง่ายที่จะตรวจสอบว่าจำนวนอาร์กิวเมนต์ที่ให้มาตรงกับจำนวนพารามิเตอร์ที่ ฟังก์ชั่นที่เรียกว่าคาดหวัง เราแจ้งข้อผิดพลาดเมื่อมีความขัดแย้งระหว่างอาร์กิวเมนต์ที่กำหนดและพารามิเตอร์ที่คาดไว้ ในส่วนสุดท้ายของ #assign_function_args_to_params เรากำหนดอาร์กิวเมนต์ (เช่น ค่า) ที่ให้ไว้ระหว่างการเรียกใช้ฟังก์ชันให้กับพารามิเตอร์ที่เกี่ยวข้อง (เช่น ตัวแปรท้องถิ่นภายในฟังก์ชัน) โปรดทราบว่าเราจะตรวจสอบว่าชื่อพารามิเตอร์ชนกับตัวแปรส่วนกลางที่มีอยู่หรือไม่ ดังที่ได้อธิบายไว้ก่อนหน้านี้ ในกรณีเหล่านี้ เราจะไม่สร้างตัวแปรโลคัลภายในสแต็กเฟรมของฟังก์ชัน แต่ใช้ค่าที่ส่งผ่านไปยังตัวแปรโกลบอลที่มีอยู่แทน

กลับไปที่ #interpret_function_call ในที่สุด เราก็ผลักเฟรมสแต็กที่สร้างขึ้นใหม่ของเราไปที่ call stack จากนั้นเราก็เรียกเพื่อนเก่าว่า #interpret_nodes เพื่อเริ่มตีความเนื้อหาของฟังก์ชัน:

def interpret_function_call(fn_call)
  return if println(fn_call)

  fn_def = fetch_function_definition(fn_call.function_name_as_str)

  stack_frame = Stoffle::Runtime::StackFrame.new(fn_def, fn_call)

  assign_function_args_to_params(stack_frame)

  # Executing the function body.
  call_stack << stack_frame
  value = interpret_nodes(fn_def.body.expressions)
  call_stack.pop
  value
end

การตีความเนื้อความของฟังก์ชัน

ตอนนี้เราได้ตีความการเรียกฟังก์ชันแล้ว ได้เวลาตีความเนื้อหาของฟังก์ชัน:

fn sum_integers: first_integer, last_integer
  i = first_integer
  sum = 0
  while i <= last_integer
    sum = sum + i

    i = i + 1
  end

  println(sum)
end

sum_integers(1, 100)

สองบรรทัดแรกของ sum_integers . ของเรา ฟังก์ชันคือการกำหนดตัวแปร เราได้กล่าวถึงหัวข้อนี้ในโพสต์บล็อกก่อนหน้าของชุดนี้ อย่างไรก็ตาม ตอนนี้เรามีการกำหนดขอบเขตตัวแปร และด้วยเหตุนี้ โค้ดที่เกี่ยวข้องกับการกำหนดจึงเปลี่ยนไปเล็กน้อย ให้เราสำรวจมัน:

def interpret_var_binding(var_binding)
  if call_stack.length > 0
    # We are inside a function. If the name points to a global var, we assign the value to it.
    # Otherwise, we create and / or assign to a local var.
    if env.has_key?(var_binding.var_name_as_str)
      env[var_binding.var_name_as_str] = interpret_node(var_binding.right)
    else
      call_stack.last.env[var_binding.var_name_as_str] = interpret_node(var_binding.right)
    end
  else
    # We are not inside a function. Therefore, we create and / or assign to a global var.
    env[var_binding.var_name_as_str] = interpret_node(var_binding.right)
  end
end

คุณจำได้ไหมว่าเมื่อเราผลักเฟรมสแต็กที่สร้างขึ้นสำหรับการเรียกใช้ฟังก์ชันลงใน call_stack ? สิ่งนี้มีประโยชน์แล้ว เนื่องจากเราสามารถตรวจสอบว่าเราอยู่ในฟังก์ชันหรือไม่โดยตรวจสอบ call_stack มีความยาวมากกว่าศูนย์ (เช่น มี อย่างน้อย หนึ่งสแต็กเฟรม) หากเราอยู่ในฟังก์ชัน ซึ่งเป็นกรณีในโค้ดที่เรากำลังแปลอยู่ เราจะตรวจสอบว่าเรามีตัวแปรส่วนกลางที่มีชื่อเดียวกันกับตัวแปรที่เรากำลังพยายามผูกค่าอยู่หรือไม่ ดังที่คุณทราบแล้ว หากเกิดการชนกัน เราจะกำหนดค่าให้กับตัวแปรส่วนกลางที่มีอยู่ และจะไม่มีการสร้างตัวแปรภายในเครื่อง เมื่อไม่ได้ใช้ชื่อ เราจะสร้างตัวแปรโลคัลใหม่และกำหนดค่าที่ต้องการให้กับชื่อนั้น ตั้งแต่ call_stack เป็นสแต็ก (เช่น โครงสร้างข้อมูลเข้าก่อนออกก่อน) เรารู้ว่าตัวแปรโลคัลนี้ควรเก็บไว้ใน env ของ สุดท้าย เฟรมซ้อน (เช่น เฟรมที่สร้างขึ้นสำหรับฟังก์ชันที่กำลังประมวลผลอยู่) สุดท้ายนี้ ส่วนสุดท้ายของ #interpret_var_binding เกี่ยวข้องกับการมอบหมายงานที่เกิดขึ้นนอกหน้าที่ เนื่องจากมีเพียงฟังก์ชันเท่านั้นที่สร้างขอบเขตใหม่ใน Stoffle จึงไม่มีอะไรเปลี่ยนแปลงที่นี่ เนื่องจากตัวแปรที่สร้างภายนอกฟังก์ชันจะเป็นส่วนกลางเสมอและเก็บไว้ที่ตัวแปรอินสแตนซ์ env .

กลับไปที่โปรแกรมของเรา ขั้นตอนต่อไปคือการตีความลูปที่รับผิดชอบในการสรุปจำนวนเต็ม ให้เรารีเฟรชหน่วยความจำของเราและดู AST ของโปรแกรม Stoffle ของเราอีกครั้ง:

โหนดที่เป็นตัวแทนของลูปคือ Stoffle::AST::Repetition :

class Stoffle::AST::Repetition < Stoffle::AST::Expression
  attr_accessor :condition, :block

  def initialize(cond_expr = nil, repetition_block = nil)
    @condition = cond_expr
    @block = repetition_block
  end

  def ==(other)
    children == other&.children
  end

  def children
    [condition, block]
  end
end

โปรดทราบว่าโดยทั่วไปแล้วโหนด AST จะรวบรวมแนวคิดที่เราได้สำรวจในบทความก่อนหน้านี้ สำหรับเงื่อนไขของมัน เราจะมีนิพจน์ที่โดยทั่วไปจะมีที่รูทของมัน (ลองนึกถึงโหนดรูท AST ของนิพจน์) a Stoffle::AST::BinaryOperator (เช่น '>', 'หรือ' เป็นต้น) สำหรับเนื้อความของลูป เราจะมี Stoffle::AST::Block . มันสมเหตุสมผลแล้วใช่ไหม รูปแบบพื้นฐานที่สุดของลูปคือนิพจน์หนึ่งหรือหลายนิพจน์ (a block ) ให้ทำซ้ำในขณะที่นิพจน์เป็นความจริง (เช่น ในขณะที่ conditional ประเมินเป็นค่าความจริง)

วิธีการที่สอดคล้องกันที่ล่ามของเราคือ #interpret_repetition :

def interpret_repetition(repetition)
  while interpret_node(repetition.condition)
    interpret_nodes(repetition.block.expressions)
  end
end

ที่นี่คุณอาจประหลาดใจกับความเรียบง่าย (และกล้าพูดเลยว่าความงาม) ของวิธีนี้ เราสามารถนำการตีความลูปไปใช้โดยผสมผสานวิธีการที่เราได้สำรวจไปแล้วในบทความที่แล้ว โดยใช้ while . ของ Ruby วนซ้ำ เราสามารถตรวจสอบให้แน่ใจว่าเรายังคงตีความโหนดที่เขียน Stoffle loop ของเราต่อไป (โดยการเรียก #interpret_nodes ซ้ำๆ ) ในขณะที่การประเมินเงื่อนไขเป็นจริง งานการประเมินเงื่อนไขนั้นง่ายพอๆ กับการเรียกผู้ต้องสงสัยทั่วไป นั่นคือ #interpret_node วิธีการ

การกลับจากฟังก์ชัน

เราใกล้จะถึงเส้นชัยแล้ว! หลังจากการวนซ้ำเราดำเนินการและพิมพ์ผลลัพธ์ของการรวมไปยังคอนโซล เราจะไม่ผ่านมันอีกเพราะเราได้กล่าวถึงในส่วนสุดท้ายของซีรีส์แล้ว สรุปโดยย่อ โปรดจำไว้ว่า println ฟังก์ชันนี้จัดทำโดย Stoffle เอง และภายในล่าม เราเพียงแค่ใช้ puts ของ Ruby เอง วิธีการ

เพื่อจบบทความนี้ เราต้องกลับมาที่ #interpret_nodes . เวอร์ชันสุดท้ายแตกต่างจากเวอร์ชันที่เราเห็นในอดีตเล็กน้อย ตอนนี้มีโค้ดสำหรับจัดการการกลับจากฟังก์ชันและคลาย call stack นี่คือเวอร์ชันที่สมบูรณ์ของ #interpret_nodes ในรัศมีภาพเต็ม:

def interpret_nodes(nodes)
  last_value = nil

  nodes.each do |node|
    last_value = interpret_node(node)

    if return_detected?(node)
      raise Stoffle::Error::Runtime::UnexpectedReturn unless call_stack.length > 0

      self.unwind_call_stack = call_stack.length # We store the current stack level to know when to stop returning.
      return last_value
    end

    if unwind_call_stack == call_stack.length
      # We are still inside a function that returned, so we keep on bubbling up from its structures (e.g., conditionals, loops etc).
      return last_value
    elsif unwind_call_stack > call_stack.length
      # We returned from the function, so we reset the "unwind indicator".
      self.unwind_call_stack = -1
    end
  end

  last_value
end

อย่างที่คุณรู้อยู่แล้ว #interpret_nodes ใช้ทุกครั้งที่เราต้องตีความนิพจน์จำนวนมาก ใช้เพื่อเริ่มตีความโปรแกรมของเราและทุกครั้งที่เราพบโหนดที่มีบล็อกที่เกี่ยวข้อง (เช่น Stoffle::AST::FunctionDefinition ). โดยเฉพาะเมื่อต้องจัดการกับฟังก์ชัน มีสองสถานการณ์:การตีความฟังก์ชันและการกดปุ่ม return นิพจน์หรือตีความฟังก์ชันจนจบและไม่กด return . ใดๆ นิพจน์ ในกรณีที่สอง หมายความว่าฟังก์ชันไม่มี return . ที่ชัดเจน นิพจน์หรือเส้นทางโค้ดที่เราดำเนินการไม่มี return .

ให้เรารีเฟรชความทรงจำของเราก่อนดำเนินการต่อ อย่างที่คุณอาจจำได้จากสองสามย่อหน้าข้างต้น #interpret_nodes ถูกเรียกเมื่อเราเริ่มตีความ sum_integers ฟังก์ชั่น (เช่น เมื่อมันถูกเรียกในโปรแกรมของเรา) อีกครั้ง นี่คือซอร์สโค้ดของโปรแกรมที่เรากำลังดำเนินการ:

fn sum_integers: first_integer, last_integer
  i = first_integer
  sum = 0
  while i <= last_integer
    sum = sum + i

    i = i + 1
  end

  println(sum)
end

sum_integers(1, 100)

เราอยู่ที่จุดสิ้นสุดของการตีความฟังก์ชัน อย่างที่คุณอาจเดาได้ ฟังก์ชันของเราไม่มี return . ที่ชัดเจน . นี่เป็นเส้นทางที่ง่ายที่สุดของ #interpret_nodes . โดยทั่วไป เราจะวนซ้ำผ่านโหนดฟังก์ชันทั้งหมด โดยคืนค่าของนิพจน์ที่ตีความล่าสุดในตอนท้าย (ตัวเตือนอย่างรวดเร็ว:Stoffle มีการส่งคืนโดยปริยาย) ซึ่งจะนำเราไปสู่เส้นชัย เป็นการสรุปการตีความโปรแกรมของเรา

แม้ว่าโปรแกรมของเราจะได้รับการตีความอย่างสมบูรณ์แล้ว แต่จุดประสงค์หลักของบทความนี้คือเพื่ออธิบายการใช้งานล่าม ดังนั้น มาใช้เวลาอีกสักหน่อยที่นี่และดูว่าล่ามจัดการกับกรณีที่เราพบ return ภายในฟังก์ชัน

ขั้นแรกให้ return นิพจน์ได้รับการประเมินที่จุดเริ่มต้นของการดำเนินการ มูลค่าของมันจะเป็นการประเมินของสิ่งที่จะส่งคืน นี่คือรหัสสำหรับ Stoffle::AST::Return :

class Stoffle::AST::Return < Stoffle::AST::Expression
  attr_accessor :expression

  def initialize(expr)
    @expression = expr
  end

  def ==(other)
    children == other&.children
  end

  def children
    [expression]
  end
end

จากนั้น เราก็มีเงื่อนไขง่ายๆ ที่จะตรวจจับ return โหนด AST เมื่อทำสิ่งนี้แล้ว ขั้นแรกเราจะทำการตรวจสุขภาพจิตเพื่อยืนยันว่าเราอยู่ในฟังก์ชัน ในการทำเช่นนั้น เราสามารถตรวจสอบความยาวของ call stack ได้ ความยาวที่มากกว่าศูนย์หมายความว่าเราอยู่ในฟังก์ชันจริงๆ ใน Stoffle เราไม่อนุญาตให้ใช้ return นิพจน์ภายนอกฟังก์ชัน ดังนั้นเราจึงทำให้เกิดข้อผิดพลาดหากการตรวจสอบนี้ล้มเหลว ก่อนคืนค่าที่โปรแกรมเมอร์ต้องการ ขั้นแรกเราจะเก็บบันทึกความยาวปัจจุบันของ call stack โดยเก็บไว้ในตัวแปรอินสแตนซ์ unwind_call_stack . เพื่อให้เข้าใจว่าเหตุใดสิ่งนี้จึงสำคัญ เรามาทบทวน #interpret_function_call :

def interpret_function_call(fn_call)
  return if println(fn_call)

  fn_def = fetch_function_definition(fn_call.function_name_as_str)

  stack_frame = Stoffle::Runtime::StackFrame.new(fn_def, fn_call)

  assign_function_args_to_params(stack_frame)

  # Executing the function body.
  call_stack << stack_frame
  value = interpret_nodes(fn_def.body.expressions)
  call_stack.pop
  value
end

ที่นี่ ที่ส่วนท้ายของ #interpret_function_call โปรดทราบว่าเราเปิดสแต็กเฟรมจาก call stack หลังจากตีความฟังก์ชัน ด้วยเหตุนี้ ความยาวของ call stack จะลดลงหนึ่ง เนื่องจากเราได้รักษาความยาวของสแต็กไว้ในขณะที่เราตรวจพบการส่งคืน เราจึงสามารถเปรียบเทียบความยาวเริ่มต้นนี้ทุกครั้งที่เราตีความโหนดใหม่ที่ #interpret_nodes . มาดูเซ็กเมนต์ที่ทำสิ่งนี้ภายในตัววนซ้ำโหนดของ #interpret_nodes :

def interpret_nodes(nodes)
  # ...

  nodes.each do |node|
    # ...

    if unwind_call_stack == call_stack.length
      # We are still inside a function that returned, so we keep on bubbling up from its structures (e.g., conditionals, loops etc).
      return last_value
    elsif unwind_call_stack > call_stack.length
      # We returned from the function, so we reset the "unwind indicator".
      self.unwind_call_stack = -1
    end

    # ...
  end

  # ...
end

มันอาจจะเข้าใจยากในตอนแรก ฉันแนะนำให้คุณตรวจสอบการใช้งานแบบเต็มบน GitHub และลองเล่นดู หากคุณคิดว่ามันอาจช่วยให้คุณเข้าใจล่ามส่วนสุดท้ายนี้ จุดสำคัญที่ควรคำนึงถึงในที่นี้คือโปรแกรมทั่วไปมีโครงสร้างที่ซ้อนกันอยู่มากมาย Ergo กำลังดำเนินการ #interpret_nodes โดยทั่วไปจะส่งผลให้มีการเรียกใหม่ไปที่ #interpret_nodes ซึ่งอาจส่งผลให้มีการเรียก #interpret_nodes . มากขึ้น และอื่นๆ! เมื่อเรากด return ภายในฟังก์ชัน เราอาจอยู่ในโครงสร้างที่ซ้อนกันอย่างลึกล้ำ ตัวอย่างเช่น ลองนึกภาพว่า return อยู่ภายในเงื่อนไขที่เป็นส่วนหนึ่งของการวนซ้ำ หากต้องการกลับจากฟังก์ชัน เราต้องกลับจาก #interpret_nodes . ทั้งหมด จนกว่าเราจะกลับจากที่เริ่มต้นโดย #interpret_function_call (เช่น การเรียก #interpret_nodes ที่เริ่มตีความเนื้อหาฟังก์ชัน)

ที่ส่วนของโค้ดด้านบน เราเน้นให้เห็นอย่างชัดเจนว่าเราทำอย่างไร โดยมีค่าบวกที่ @unwind_call_stack และ หนึ่งที่เท่ากับความยาวปัจจุบันของ call stack เรารู้แน่นอนว่าเราอยู่ในฟังก์ชันและเรายังไม่ได้ return จากการโทรเดิมที่เริ่มต้นโดย #interpret_function_call . เมื่อสิ่งนี้เกิดขึ้นในที่สุด @unwind_call_stack จะมากกว่าความยาวปัจจุบันของ call stack ดังนั้นเราจึงรู้ว่าเราได้ออกจากฟังก์ชันที่ส่งคืนแล้ว และเราไม่จำเป็นต้องดำเนินการตามขั้นตอนของการเดือดปุด ๆ อีกต่อไป จากนั้นเราก็รีเซ็ต @unwind_call_stack . เพียงเพื่อใช้ @unwind_call_stack ชัดเจน นี่คือค่าที่เป็นไปได้:

• -1 เป็นค่าเริ่มต้นและเป็นกลาง ซึ่งบ่งชี้ว่าเราไม่ได้อยู่ในฟังก์ชันใดๆ ที่ส่งคืน
• ค่าบวกเท่ากับความยาวสแต็กการโทร แสดงว่าเรายังอยู่ในฟังก์ชันที่ส่งคืน
• ค่าบวกที่มากกว่าความยาวสแต็กการโทร แสดงว่าเราไม่อยู่ในฟังก์ชันที่ส่งคืนอีกต่อไป

การเรียกใช้โปรแกรมของเราโดยใช้ Stoffle CLI

ในบทความก่อนหน้าของซีรีส์นี้ เราได้สร้าง CLI แบบง่ายๆ เพื่อให้การแปลโปรแกรม Stoffle ง่ายขึ้น ตอนนี้เราได้สำรวจการใช้งานล่ามแล้ว มาดูการใช้งานโปรแกรมของเรากัน ดังที่แสดงไว้ข้างต้นในส่วนต่างๆ มากมาย โค้ดของเรากำหนดและเรียก sum_integers ฟังก์ชันส่งผ่านอาร์กิวเมนต์ 1 และ 100 . หากล่ามของเราทำงานอย่างถูกต้อง เราควรจะเห็น 5050.0 (ผลรวมของเซตของจำนวนเต็มเริ่มต้นที่ 1 และสิ้นสุดที่ 100) พิมพ์ไปยังคอนโซล:

ปิดความคิด

ในโพสต์นี้ เราได้ใช้ส่วนสุดท้ายที่จำเป็นในการทำให้ล่ามของเราสมบูรณ์ เราจัดการกับการกำหนดฟังก์ชัน การเรียกใช้ฟังก์ชัน การกำหนดขอบเขตตัวแปร และลูป ตอนนี้ เรามีภาษาโปรแกรมที่เรียบง่ายแต่ใช้งานได้!

ในตอนต่อไปและตอนสุดท้ายของซีรีส์นี้ ฉันจะแบ่งปันแหล่งข้อมูลบางอย่างที่ฉันพิจารณาถึงตัวเลือกที่ยอดเยี่ยมสำหรับผู้ที่ต้องการศึกษาการใช้งานภาษาโปรแกรมต่อไป ฉันจะเสนอความท้าทายบางอย่างที่คุณสามารถทำต่อไปเพื่อเรียนรู้ต่อไปในขณะที่ปรับปรุง Stoffle เวอร์ชันของคุณ แล้วพบกันใหม่ เซียว!