Xây dựng ngôn ngữ lập trình trong Ruby:Trình thông dịch, Phần 2

Nguồn đầy đủ trên Github

Bản triển khai hoàn chỉnh của ngôn ngữ lập trình Stoffle có sẵn trên GitHub. Vui lòng mở vấn đề nếu bạn tìm thấy lỗi hoặc có thắc mắc.

Trong bài đăng trên blog này, chúng tôi sẽ tiếp tục triển khai trình thông dịch cho Stoffle, một ngôn ngữ lập trình đồ chơi được xây dựng hoàn toàn bằng Ruby. Chúng tôi đã bắt đầu trình thông dịch trong một bài viết trước. Bạn có thể đọc thêm về dự án này trong phần đầu tiên của loạt bài này.

Trong bài trước, chúng tôi đã trình bày cách triển khai các tính năng đơn giản hơn của Stoffle:biến, điều kiện, toán tử đơn phân và nhị phân, kiểu dữ liệu và in ra bảng điều khiển. Bây giờ, đã đến lúc xắn tay áo của chúng ta và giải quyết các bit còn lại nhiều thách thức hơn:định nghĩa hàm, gọi hàm, phạm vi biến và vòng lặp.

Như chúng tôi đã làm trước đây, chúng tôi sẽ sử dụng cùng một chương trình ví dụ từ đầu đến cuối của bài đăng này. Chúng tôi sẽ xem xét từng dòng một, khám phá cách triển khai cần thiết ở trình thông dịch để làm sống động từng cấu trúc khác nhau trong chương trình ví dụ Stoffle của chúng tôi. Cuối cùng, chúng ta sẽ thấy trình thông dịch hoạt động và chạy chương trình bằng cách sử dụng CLI mà chúng ta đã tạo trong phần trước của loạt bài này.

Gauss đã trở lại

Nếu bạn có một trí nhớ tốt, bạn có thể nhớ rằng trong phần hai của loạt bài này, chúng ta đã thảo luận về cách chế tạo một chiếc Lexer. Trong bài đăng đó, chúng tôi đã xem xét một chương trình tổng hợp các số trong một chuỗi để minh họa cú pháp của Stoffle. Vào cuối bài viết này, cuối cùng chúng ta sẽ có thể chạy chương trình nói trên! Vì vậy, đây là chương trình một lần nữa:

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)

Cây cú pháp trừu tượng (AST) cho chương trình tổng kết số nguyên của chúng tôi như sau:

Nhà toán học đã truyền cảm hứng cho Chương trình Mẫu Stoffle của chúng tôi

Carl Friedrich Gauss được cho là đã tự mình tìm ra công thức tính tổng các số trong một chuỗi khi mới 7 tuổi.

Như bạn có thể nhận thấy, chương trình của chúng tôi không sử dụng công thức do Gauss nghĩ ra. Kể từ khi chúng ta có máy tính ngày nay, chúng ta có thể giải quyết vấn đề này một cách "thô bạo". Hãy để những người bạn silicon của chúng tôi làm công việc khó khăn cho chúng tôi.

Định nghĩa hàm

Điều đầu tiên chúng tôi làm trong chương trình của mình là xác định sum_integers hàm số. Nó có nghĩa là gì để khai báo một hàm? Như bạn có thể đoán, đó là một hành động tương tự như việc gán giá trị cho một biến. Khi chúng ta xác định một hàm, chúng ta đang liên kết một tên (tức là tên hàm, một định danh) với một hoặc nhiều biểu thức (tức là nội dung của hàm). Chúng tôi cũng đăng ký tên mà các giá trị được truyền vào trong quá trình gọi hàm sẽ được ràng buộc. Các định danh này trở thành các biến cục bộ trong quá trình thực thi hàm và được gọi là tham số. Các giá trị được truyền vào khi hàm được gọi (và được liên kết với các tham số) là các đối số.

Hãy cùng xem qua #interpret_function_definition :

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

Khá đơn giản, phải không? Như bạn có thể nhớ từ bài cuối cùng của loạt bài này, khi trình thông dịch của chúng tôi được khởi tạo, chúng tôi tạo ra một môi trường. Đây là một nơi được sử dụng để giữ trạng thái của chương trình, và trong trường hợp của chúng ta, nó chỉ đơn giản là một hàm băm Ruby. Trong bài trước, chúng ta đã biết cách các biến và giá trị liên kết với chúng được lưu trữ trong env . Các định nghĩa hàm cũng sẽ được lưu trữ ở đó. Khóa là tên hàm và giá trị là nút AST được sử dụng để xác định một hàm (Stoffle::AST::FunctionDefinition ). Đây là phần bổ sung về nút AST này:

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

Có tên hàm được liên kết với Stoffle::AST::FunctionDefinition nghĩa là chúng ta có thể truy cập tất cả thông tin cần thiết để thực thi chức năng. Ví dụ, chúng ta có sẵn số lượng đối số dự kiến ​​và có thể dễ dàng phát ra lỗi nếu một lệnh gọi hàm không cung cấp nó. Điều này và các chi tiết khác mà chúng ta sẽ thấy khi khám phá, tiếp theo, mã chịu trách nhiệm diễn giải một lệnh gọi hàm.

Gọi một hàm

Tiếp tục xem qua ví dụ của chúng ta, bây giờ chúng ta hãy tập trung vào lệnh gọi hàm. Sau khi xác định sum_integers , chúng tôi gọi nó là truyền các số 1 và 100 làm đối số:

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)

Việc diễn giải một lệnh gọi hàm xảy ra tại #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

Đây là một chức năng phức tạp, vì vậy chúng tôi sẽ cần dành thời gian ở đây. Như đã giải thích trong bài viết trước, dòng đầu tiên chịu trách nhiệm kiểm tra xem hàm được gọi có phải là println hay không . Nếu chúng ta đang xử lý một hàm do người dùng xác định, đó là trường hợp ở đây, chúng ta tiếp tục và tìm nạp định nghĩa của nó bằng cách sử dụng #fetch_function_definition . Như được hiển thị bên dưới, hàm này là một cánh buồm đơn giản và về cơ bản chúng ta truy xuất Stoffle::AST::FunctionDefinition Nút AST trước đây chúng tôi đã lưu trữ trong môi trường hoặc phát ra lỗi nếu chức năng không tồn tại.

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

Quay lại #interpret_function_call , mọi thứ bắt đầu trở nên thú vị hơn. Khi nghĩ về các chức năng trong ngôn ngữ đồ chơi đơn giản của chúng ta, chúng ta có hai mối quan tâm đặc biệt. Đầu tiên, chúng ta cần một chiến lược để theo dõi các biến cục bộ của hàm. Chúng tôi cũng phải xử lý return biểu thức. Để giải quyết những thách thức này, chúng tôi sẽ khởi tạo một đối tượng mới, mà chúng tôi sẽ gọi là khung , mỗi khi một hàm được gọi. Ngay cả khi cùng một hàm được gọi nhiều lần, mỗi lần gọi mới sẽ khởi tạo một khung mới. Đối tượng này sẽ giữ tất cả các biến cục bộ cho hàm. Vì một hàm có thể gọi một hàm khác, v.v., chúng ta phải có một cách để biểu diễn và theo dõi luồng thực thi của chương trình của chúng ta. Để làm như vậy, chúng tôi sẽ sử dụng cấu trúc dữ liệu ngăn xếp, mà chúng tôi sẽ đặt tên là gọi ngăn xếp . Trong Ruby, một mảng tiêu chuẩn với #push của nó và #pop các phương thức sẽ hoạt động như một triển khai ngăn xếp.

Ngăn xếp cuộc gọi và Khung xếp chồng

Hãy nhớ rằng chúng tôi đang sử dụng các thuật ngữ ngăn xếp và khung ngăn xếp một cách lỏng lẻo. Bộ xử lý và ngôn ngữ lập trình cấp thấp hơn nói chung cũng sẽ có ngăn xếp cuộc gọi và khung ngăn xếp, nhưng chúng không chính xác là những gì chúng ta có ở đây bằng ngôn ngữ đồ chơi của mình.

Nếu những khái niệm này khơi gợi sự tò mò của bạn, tôi thực sự khuyên bạn nên nghiên cứu ngăn xếp cuộc gọi và khung ngăn xếp. Nếu bạn thực sự muốn tiến gần hơn đến kim loại, tôi khuyên bạn nên đặc biệt xem xét các ngăn xếp cuộc gọi của bộ xử lý.

Đây là mã để triển khai 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

Bây giờ, quay lại #interpret_function_call , bước tiếp theo là gán các giá trị được truyền trong lời gọi hàm cho các tham số dự kiến ​​tương ứng, các tham số này sẽ có thể truy cập được dưới dạng các biến cục bộ bên trong thân hàm. #assign_function_args_to_params chịu trách nhiệm cho bước này:

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

Trước khi chúng ta khám phá #assign_function_args_to_params việc triển khai, trước tiên cần phải thảo luận ngắn gọn về phạm vi biến đổi. Đây là một chủ đề phức tạp và nhiều sắc thái. Đối với Stoffle, chúng ta hãy thật thực dụng và áp dụng một giải pháp đơn giản. Trong ngôn ngữ nhỏ bé của chúng ta, các cấu trúc duy nhất tạo ra phạm vi mới là các hàm. Hơn nữa, các biến toàn cục luôn đi trước. Do đó, tất cả các biến được khai báo (tức là lần sử dụng đầu tiên) bên ngoài một hàm là toàn cục và được lưu trữ trong env . Các biến bên trong các hàm là cục bộ của chúng và được lưu trữ trong env của khung ngăn xếp được tạo trong quá trình diễn giải lệnh gọi hàm. Tuy nhiên, có một ngoại lệ:một tên biến xung đột với một biến toàn cục hiện có. Nếu xung đột xảy ra, biến cục bộ sẽ không được tạo và chúng tôi sẽ đọc và gán cho biến toàn cục hiện có.

Được rồi, bây giờ chiến lược xác định phạm vi thay đổi của chúng ta đã rõ ràng, hãy quay lại #assign_function_args_to_params . Trong phân đoạn đầu tiên của phương thức, trước tiên chúng ta truy xuất định nghĩa hàm và các nút gọi hàm từ đối tượng khung ngăn xếp đã được truyền vào. Có những đối số này, thật dễ dàng để kiểm tra xem số lượng đối số được cung cấp có khớp với số lượng tham số của không. hàm được gọi là kỳ vọng. Chúng tôi đưa ra lỗi khi có sự không khớp giữa các đối số đã cho và các tham số mong đợi. Trong phần cuối cùng của #assign_function_args_to_params , chúng tôi gán các đối số (tức là các giá trị) được cung cấp trong quá trình gọi hàm cho các tham số tương ứng của chúng (tức là các biến cục bộ bên trong hàm). Lưu ý rằng chúng tôi kiểm tra xem tên tham số có xung đột với một biến toàn cục hiện có hay không. Như đã giải thích trước đây, trong những trường hợp này, chúng tôi không tạo biến cục bộ bên trong khung ngăn xếp của hàm và thay vào đó chỉ áp dụng giá trị được truyền vào cho biến toàn cục hiện có.

Quay lại #interpret_function_call , cuối cùng chúng ta đẩy khung ngăn xếp mới tạo của mình vào ngăn xếp cuộc gọi. Sau đó, chúng tôi gọi cho người bạn cũ của mình là #interpret_nodes để bắt đầu diễn giải phần thân hàm:

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

Thông dịch phần thân hàm

Bây giờ chúng ta đã diễn giải chính lời gọi hàm, đã đến lúc diễn giải phần thân của hàm:

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)

Hai dòng đầu tiên của sum_integers của chúng tôi hàm là các phép gán biến. Chúng tôi đã đề cập đến chủ đề này trong bài đăng trên blog trước của loạt bài này. Tuy nhiên, bây giờ chúng ta có phạm vi thay đổi, và do đó, mã liên quan đến việc gán đã thay đổi một chút. Hãy cùng chúng tôi khám phá nó:

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

Bạn có nhớ khi chúng tôi đẩy khung ngăn xếp được tạo cho lệnh gọi hàm vào call_stack ? Điều này trở nên hữu ích ngay bây giờ vì chúng tôi có thể kiểm tra xem chúng tôi có đang ở bên trong một hàm hay không bằng cách xác minh rằng call_stack có độ dài lớn hơn 0 (tức là có ít nhất một khung ngăn xếp). Nếu chúng ta đang ở bên trong một hàm, đó là trường hợp trong đoạn mã mà chúng ta hiện đang diễn giải, chúng ta kiểm tra xem chúng ta đã có một biến toàn cục với cùng tên của biến mà chúng ta hiện đang cố gắng liên kết một giá trị hay chưa. Như bạn đã biết, nếu xung đột xảy ra, chúng tôi sẽ chỉ định giá trị cho biến toàn cục hiện có và biến cục bộ sẽ không được tạo. Khi tên không được sử dụng, chúng tôi tạo một biến cục bộ mới và gán giá trị dự định cho nó. Kể từ call_stack là một ngăn xếp (tức là, cuối cùng trong cấu trúc dữ liệu xuất đầu tiên), chúng tôi biết rằng biến cục bộ này nên được lưu trữ trong env trong số cuối cùng khung xếp chồng (tức là khung được tạo cho hàm hiện đang được xử lý). Cuối cùng, phần cuối cùng của #interpret_var_binding giải quyết các nhiệm vụ xảy ra bên ngoài chức năng. Vì chỉ các hàm tạo phạm vi mới trong Stoffle nên không có gì thay đổi ở đây, vì các biến được tạo bên ngoài hàm luôn là toàn cục và được lưu trữ tại biến cá thể env .

Quay trở lại chương trình của chúng ta, bước tiếp theo là diễn giải vòng lặp chịu trách nhiệm tính tổng các số nguyên. Hãy để chúng tôi làm mới bộ nhớ của mình và xem lại AST của chương trình Stoffle của chúng tôi:

Nút đại diện cho vòng lặp là 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

Lưu ý rằng nút AST này về cơ bản tập hợp các khái niệm mà chúng ta đã khám phá trong các bài viết trước. Đối với điều kiện của nó, chúng ta sẽ có một biểu thức thường sẽ có ở gốc của nó (hãy nghĩ về nút gốc AST của biểu thức) a Stoffle::AST::BinaryOperator (ví dụ:'>', 'hoặc', v.v.). Đối với phần nội dung của vòng lặp, chúng ta sẽ có Stoffle::AST::Block . Điều này có ý nghĩa, phải không? Dạng cơ bản nhất của vòng lặp là một hoặc nhiều biểu thức (một khối ) được lặp lại trong khi một biểu thức là trung thực (tức là, trong khi điều kiện đánh giá một giá trị trung thực).

Phương thức tương ứng trong trình thông dịch của chúng tôi là #interpret_repetition :

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

Đến đây, bạn có thể ngạc nhiên vì sự đơn giản (và, tôi dám nói là đẹp) của phương pháp này. Chúng ta có thể thực hiện việc giải thích các vòng lặp bằng cách kết hợp các phương pháp mà chúng ta đã khám phá trong các bài viết trước. Bằng cách sử dụng while của Ruby vòng lặp, chúng tôi có thể đảm bảo rằng chúng tôi tiếp tục diễn giải các nút tạo vòng lặp Stoffle của chúng tôi (bằng cách gọi liên tục #interpret_nodes ) trong khi đánh giá của điều kiện là đúng. Công việc đánh giá điều kiện dễ dàng như gọi nghi phạm thông thường, #interpret_node phương pháp.

Trả về từ Hàm

Chúng tôi gần như về đích! Sau vòng lặp, chúng tôi tiến hành và in kết quả tổng kết ra bảng điều khiển. Chúng tôi sẽ không xem xét lại nó vì chúng tôi đã trình bày nó trong phần cuối cùng của loạt bài này. Tóm tắt nhanh, hãy nhớ rằng println hàm được cung cấp bởi chính Stoffle và nội bộ trong trình thông dịch, chúng tôi chỉ đơn giản là sử dụng puts của riêng Ruby phương pháp.

Để hoàn thành bài đăng này, chúng tôi phải truy cập lại #interpret_nodes . Phiên bản cuối cùng của nó hơi khác so với phiên bản mà chúng ta đã thấy trong quá khứ. Bây giờ, nó bao gồm mã để xử lý việc trả về từ một hàm và giải nén ngăn xếp cuộc gọi. Đây là phiên bản hoàn chỉnh của #interpret_nodes trong vinh quang đầy đủ của nó:

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

Như bạn đã biết, #interpret_nodes được sử dụng mỗi khi chúng ta cần giải thích một loạt các biểu thức. Nó được sử dụng để bắt đầu diễn giải chương trình của chúng tôi và bất cứ khi nào chúng tôi gặp các nút có khối liên kết với chúng (chẳng hạn như Stoffle::AST::FunctionDefinition ). Cụ thể, khi xử lý các hàm, có hai tình huống:diễn giải một hàm và nhấn return biểu thức hoặc diễn giải một hàm ở cuối nó và không đánh vào bất kỳ return nào biểu thức. Trong trường hợp thứ hai, điều đó có nghĩa là hàm không có bất kỳ return rõ ràng nào biểu thức hoặc đường dẫn mã mà chúng tôi đã đi qua không có return .

Hãy để chúng tôi làm mới ký ức của chúng tôi trước khi tiếp tục. Như bạn có thể nhớ từ một vài đoạn ở trên, #interpret_nodes được gọi khi chúng tôi bắt đầu diễn giải sum_integers hàm (tức là khi nó được gọi trong chương trình của chúng tôi). Một lần nữa, đây là mã nguồn của chương trình mà chúng ta đang xem qua:

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)

Chúng ta đang ở phần cuối của việc giải thích hàm. Như bạn có thể đoán, hàm của chúng tôi không có return rõ ràng . Đây là đường dẫn dễ nhất của #interpret_nodes . Về cơ bản, chúng tôi lặp lại qua tất cả các nút chức năng, trả về giá trị của biểu thức được giải thích cuối cùng ở cuối (nhắc nhở nhanh:Stoffle có các kết quả trả về ngầm định). Điều này đưa chúng ta đến đích, kết thúc phần diễn giải chương trình của chúng ta.

Mặc dù chương trình của chúng tôi hiện đã được thông dịch đầy đủ, mục đích chính của bài viết này là giải thích việc triển khai trình thông dịch, vì vậy chúng ta hãy dành thêm một chút thời gian ở đây và xem trình thông dịch xử lý như thế nào với các trường hợp mà chúng ta nhấn trả về return bên trong một hàm.

Đầu tiên, return biểu thức được đánh giá khi bắt đầu hoạt động. Giá trị của nó sẽ là đánh giá những gì đang được trả lại. Đây là mã cho 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

Sau đó, chúng ta có một điều kiện đơn giản sẽ phát hiện return Các nút AST. Sau khi thực hiện điều này, trước tiên chúng tôi thực hiện kiểm tra độ tỉnh táo để xác minh rằng chúng tôi đang ở bên trong một hàm. Để làm như vậy, chúng ta có thể chỉ cần kiểm tra độ dài của ngăn xếp cuộc gọi. Độ dài lớn hơn 0 có nghĩa là chúng ta thực sự đang ở bên trong một hàm. Trong Stoffle, chúng tôi không cho phép sử dụng return các biểu thức bên ngoài các hàm, vì vậy chúng tôi sẽ đưa ra lỗi nếu việc kiểm tra này không thành công. Trước khi trả về giá trị mà người lập trình dự định, trước tiên chúng ta lưu giữ bản ghi độ dài hiện tại của ngăn xếp cuộc gọi, lưu trữ nó tại biến cá thể unwind_call_stack . Để hiểu tại sao điều này lại quan trọng, hãy xem lại #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

Đây, ở cuối #interpret_function_call , lưu ý rằng chúng ta bật khung ngăn xếp từ ngăn xếp cuộc gọi sau khi diễn giải hàm. Do đó, độ dài của ngăn xếp cuộc gọi sẽ giảm đi một. Vì chúng tôi đã bảo toàn độ dài của ngăn xếp tại thời điểm chúng tôi phát hiện thấy kết quả trả về, chúng tôi có thể so sánh độ dài ban đầu này mỗi khi chúng tôi diễn giải một nút mới tại #interpret_nodes . Hãy xem phân đoạn thực hiện điều này bên trong trình lặp nút của #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

Điều này có thể hơi khó nắm bắt lúc đầu. Tôi khuyến khích bạn kiểm tra việc triển khai đầy đủ trên GitHub và thử với nó nếu bạn nghĩ rằng nó có thể giúp bạn hiểu phần cuối cùng này của trình thông dịch. Điểm quan trọng cần lưu ý ở đây là một chương trình điển hình có nhiều cấu trúc lồng ghép sâu sắc. Ergo, đang thực thi #interpret_nodes thường dẫn đến một lệnh gọi mới tới #interpret_nodes , điều này có thể dẫn đến nhiều cuộc gọi hơn đến #interpret_nodes và như thế! Khi chúng tôi đạt được return bên trong một hàm, chúng ta có thể đang ở bên trong một cấu trúc lồng nhau sâu sắc. Ví dụ, hãy tưởng tượng rằng return nằm bên trong một điều kiện là một phần của vòng lặp. Để trả về từ hàm, chúng ta phải trả về từ tất cả #interpret_nodes cuộc gọi cho đến khi chúng tôi trả về từ cuộc gọi do #interpret_function_call (tức là lệnh gọi đến #interpret_nodes đã bắt đầu diễn giải phần thân hàm).

Ở đoạn mã trên, chúng tôi đánh dấu chính xác cách chúng tôi thực hiện việc này. Bằng cách có giá trị dương tại @unwind_call_stack và một bằng với độ dài hiện tại của ngăn xếp cuộc gọi, chúng tôi biết chắc chắn rằng chúng tôi đang ở bên trong một hàm và chúng tôi vẫn không return từ cuộc gọi ban đầu do #interpret_function_call . Khi điều này cuối cùng xảy ra, @unwind_call_stack sẽ lớn hơn độ dài hiện tại của ngăn xếp cuộc gọi; do đó, chúng tôi biết rằng chúng tôi đã thoát khỏi chức năng trả về và chúng tôi không cần tiếp tục quá trình tạo bọt nữa. Sau đó, chúng tôi đặt lại @unwind_call_stack . Chỉ để sử dụng @unwind_call_stack rõ ràng, đây là các giá trị có thể có của nó:

• -1 , giá trị ban đầu và giá trị trung lập của nó, cho biết rằng chúng tôi không ở bên trong bất kỳ hàm nào được trả về.
• giá trị dương bằng độ dài ngăn xếp cuộc gọi , cho thấy rằng chúng ta vẫn đang ở bên trong một hàm được trả về.
• giá trị dương lớn hơn độ dài ngăn xếp cuộc gọi , cho thấy rằng chúng ta không còn ở bên trong hàm đã trả về.

Chạy chương trình của chúng tôi bằng Stoffle CLI

Trong phần trước của loạt bài này, chúng tôi đã tạo một CLI đơn giản để giúp việc thông dịch các chương trình Stoffle dễ dàng hơn. Bây giờ chúng ta đã khám phá cách triển khai của trình thông dịch, hãy xem nó hoạt động, chạy chương trình của chúng ta. Như được hiển thị ở trên trong nhiều phần khác nhau, mã của chúng tôi xác định và sau đó gọi sum_integers hàm truyền các đối số 1 và 100 . Nếu trình thông dịch của chúng tôi hoạt động bình thường, chúng tôi sẽ thấy 5050.0 (tổng của tập hợp các số nguyên bắt đầu bằng 1 và kết thúc bằng 100) được in ra bảng điều khiển:

Kết thúc các suy nghĩ

Trong bài đăng này, chúng tôi đã triển khai các phần cuối cùng cần thiết để hoàn thiện trình thông dịch của chúng tôi. Chúng tôi giải quyết vấn đề định nghĩa hàm, gọi hàm, phạm vi biến và các vòng lặp. Bây giờ, chúng ta có một ngôn ngữ lập trình đơn giản nhưng hoạt động tốt!

Trong phần tiếp theo và cuối cùng của loạt bài này, tôi sẽ chia sẻ một số tài nguyên mà tôi coi là những lựa chọn tuyệt vời cho những ai muốn tiếp tục nghiên cứu triển khai ngôn ngữ lập trình của họ. Tôi cũng sẽ đề xuất một số thách thức bạn có thể thực hiện để tiếp tục học tập trong khi cải thiện phiên bản Stoffle của mình. Hẹn gặp lại; ciao!