Ruby로 프로그래밍 언어 만들기: 트리 워킹 방식의 인터프리터 구현하기

전체 소스 코드는 GitHub에서 확인하세요

Stoffle 프로그래밍 언어의 완전한 구현체는 GitHub에 공개되어 있습니다. 버그를 발견하거나 궁금한 점이 있다면 이슈를 등록해 주세요.

이번 글에서는 Ruby만으로 만든 장난감 프로그래밍 언어인 Stoffle의 인터프리터 구현을 시작해 보겠습니다. 프로젝트에 대한 자세한 배경은 시리즈의 첫 번째 글에서 확인할 수 있습니다.

우리가 만들 인터프리터는 흔히 트리 워킹(tree-walk) 인터프리터라고 불립니다. 지난 글에서는 파서를 구현해 평평한 토큰 시퀀스를 트리 데이터 구조, 즉 AST(Abstract Syntax Tree, 추상 구문 트리)로 변환했습니다. 짐작하시겠지만, 이제 인터프리터의 임무는 파서가 만든 AST를 순회하며 Stoffle 프로그램에 생명을 불어넣는 것입니다. 개인적으로는 언어 구현 여정에서 이 마지막 단계가 가장 흥미진진하다고 생각합니다. 인터프리터를 만들면 모든 조각이 맞춰지면서 드디어 Stoffle 프로그램이 실제로 동작하는 모습을 볼 수 있거든요!

인터프리터 구현은 두 편으로 나누어 설명합니다. 이 첫 번째 편에서는 기본기를 다룹니다. 변수, 조건문, 단항·이항 연산자, 데이터 타입, 콘솔 출력까지 말이죠. 함수 정의와 호출, 루프 같은 더 알찬 내용은 인터프리터 구현의 마지막 편인 다음 글에서 다루겠습니다.

렉서와 파서 간단 복습

인터프리터 구현으로 본격 들어가기 전에, 지금까지 시리즈에서 해온 작업을 빠르게 되짚어 보겠습니다. 먼저 원본 소스 코드를 토큰으로 변환하는 렉서(lexer)를 만들었고, 그다음 토큰을 트리 구조(AST)로 바꾸는 역할을 담당하는 파서(parser)를 구현했습니다. 요약하면, 지금까지 우리가 목격한 변환 과정은 다음과 같습니다.

상태 0: 소스 코드

my_var = 1

상태 1: 렉서가 원본 소스 코드를 토큰으로 변환

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

상태 2: 파서가 토큰을 추상 구문 트리(AST)로 변환

핵심은 AST 순회입니다

이제 AST가 준비되었으니, 남은 일은 이 구조를 순회하는 코드를 작성하는 것입니다. 즉, AST의 각 노드가 묘사하는 내용에 실질적인 생명을 불어넣는 Ruby 코드를 작성해야 합니다. 예를 들어 변수 바인딩을 나타내는 노드가 있다면, 대입식 우변의 결과값을 어떻게든 저장하고, 그 저장 공간을 변수 이름과 연결해(이름을 통해 접근 가능하게) 관리하는 Ruby 코드를 작성하는 것이 과제입니다.

시리즈의 앞선 글들에서 했던 것처럼, 예제 프로그램을 처리하는 데 관여하는 핵심 코드를 하나씩 살펴보며 구현을 탐구해 보겠습니다. 이번에 인터프리팅할 Stoffle 코드는 다음과 같습니다.

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는 아래와 같습니다.

순회의 첫걸음

기억하시겠지만, Stoffle의 AST는 항상 AST::Program 노드가 루트입니다. 이 루트는 일반적으로 여러 개의 자식을 가집니다. 어떤 자식은 얕습니다(간단한 변수 대입이 만들어내는 AST를 떠올려 보세요). 반면 어떤 자식은 꽤 깊은 서브트리의 루트이기도 합니다(몸통에 많은 줄이 있는 루프를 생각해 보세요). 인터프리터에 전달된 AST를 순회하기 시작하기 위해 필요한 Ruby 코드는 다음과 같습니다.

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가 만들어집니다. 전자인 @output은 프로그램이 출력한 모든 내용을 시간순으로 저장하는 역할을 합니다. 이 정보를 손쉽게 확인할 수 있으면 자동화 테스트 작성이나 디버깅에 매우 유용합니다. 후자인 @env의 역할은 조금 다릅니다. '환경(environment)'을 참조한다는 의미로 이렇게 명명했는데요, 이름에서 짐작할 수 있듯 실행 중인 프로그램의 상태를 보관하는 것이 임무입니다. 그중 하나가 식별자(예: 변수 이름)와 현재 값 사이의 바인딩을 구현하는 것입니다.

#interpret_nodes 메서드는 루트 노드(AST::Program)의 모든 자식을 순회하면서 각 노드마다 #interpret_node를 호출합니다.

#interpret_node는 단순하지만 그만큼 흥미로운 메서드입니다. 여기서는 Ruby 메타프로그래밍을 활용해 현재 처리 중인 노드 타입에 맞는 적절한 메서드를 호출합니다. 예컨대 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 해시에 키-값 쌍을 추가(또는 덮어쓰기)할 뿐입니다.

키는 변수의 이름입니다(#var_name_as_str는 var_binding.left.name과 동일한 헬퍼 메서드일 뿐입니다). 참고로 현재 모든 변수는 전역 변수입니다. 스코핑(scoping) 처리는 다음 글에서 다룰 예정입니다.

값은 대입식 우변의 표현식을 해석한 결과입니다. 이를 위해 다시 #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

Stoffle이 지원하는 단항 연산자(-와 !)의 의미론은 Ruby와 동일합니다. 따라서 구현도 더할나위없이 간단합니다. 피연산자를 해석한 결과에 Ruby의 - 연산자를 적용하기만 하면 됩니다. 익숙한 얼굴, #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 타입의 노드를 처리해야 합니다.

조건문, 이렇게 처리합니다

#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 또는 falsy로 평가될 표현식이 담깁니다. @when_true에는 조건이 참일 때 실행할 하나 이상의 표현식을 담은 블록이, @when_false(ELSE 절)에는 조건이 거짓일 때 실행할 블록이 담깁니다.

이제 #interpret_conditional을 살펴보겠습니다.

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

Stoffle에서의 진실성(truthiness) 규칙도 Ruby와 같습니다. 다시 말해, Stoffle에서는 오직 nil과 false만 falsy이고, 조건에 들어가는 그 외 모든 값은 truthy로 취급됩니다.

먼저 conditional.condition이 담고 있는 표현식을 해석해 조건을 평가합니다. 어떤 노드를 다루고 있는지 확인하기 위해 프로그램의 AST를 다시 한번 살펴보겠습니다.

결론부터 말하면 num > 0에 사용된 >, 즉 AST::BinaryOperator입니다. 좋습니다, 익숙한 경로를 다시 걷겠습니다. 먼저 #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 역시 이항 연산자로 볼 수 있으므로 여기서 함께 처리합니다. 의미론이 Ruby의 &&와 ||와 동일하기 때문에 위에서 보듯 구현은 아주 매끄럽습니다.

다음은 이 메서드에서 가장 주목할 부분입니다. 바로 >를 포함한 나머지 모든 이항 연산자를 처리하는 구간입니다. 여기서는 Ruby의 동적 특성을 우리 편으로 만들어 무척 간결한 해법을 도출할 수 있습니다. Ruby에서 이항 연산자는 연산에 참여하는 객체들이 제공하는 메서드이기 때문입니다.

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

이항 연산자의 장황한 구현 방법

앞서 보았듯 우리의 이항 연산자 구현은 상당히 간결합니다. 하지만 Ruby가 이토록 동적인 언어가 아니었거나, 연산자의 의미론이 Ruby와 Stoffle 사이에서 달랐다면 이런 방식으로 코드를 작성할 수 없었을 것입니다.

언어 설계자/구현자로서 그런 상황에 놓인다면, 언제든 단순하긴 하지만 그리 우아하지는 않은 차선책, 즉 switch 문을 활용할 수 있습니다. 우리 경우라면 구현이 대략 다음과 같아질 것입니다.

# ... 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로 돌아갑니다. 우리의 작은 프로그램에서 조건식은 Ruby의 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은 이미 곧바로 사용 가능한 Ruby 문자열 값을 담고 있으므로, 그저 값을 꺼내오면 됩니다.

이제 다시 #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

함수 인자(Ruby 문자열로 변환됨)를 result에 저장한 뒤에는 두 단계가 남습니다. 첫째, 콘솔에 출력할 내용을 @output에 기록합니다. 앞서 설명했듯 이는 무엇이, 어떤 순서로 출력되었는지 손쉽게 검토하기 위함이며, 인터프리터를 디버깅하거나 테스트할 때 큰 도움이 됩니다. 둘째, 실제 콘솔 출력 구현은 Ruby의 puts로 처리합니다.

실행이 곧 증명입니다

이제 Stoffle의 기본 뼈대를 구현하는 데 필요한 모든 것을 살펴봤으니, 아주 기본적인 실행 파일을 만들어 인터프리터가 실제로 동작하는 모습을 확인해 보겠습니다.

#!/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 인터프리터를 사용하려면 실행 파일을 PATH에 추가하는 것을 잊지 마세요.

드디어 프로그램을 실행할 시간입니다. 모든 것이 잘 작동한다면 콘솔에 "The number is less than or equal to zero"라는 문자열이 출력되어야 합니다. 실제로 인터프리터를 실행하면 정확히 그 결과가 나옵니다.

TIP: 인터프리터가 설치되어 있다면, 예제 프로그램의 num 변수를 0보다 큰 숫자로 바꿔 실행해 보세요. 기대한 대로 이번에는 IF 분기가 실행되어 "The number is greater than zero"라는 문자열이 출력됩니다.

마치며

이번 글에서는 Stoffle 인터프리터의 시작점을 살펴보았습니다. 변수, 조건문, 단항·이항 연산자, 데이터 타입, 콘솔 출력 등 언어의 기본기를 처리할 수 있을 만큼 인터프리터를 구현했습니다. 다음이자 마지막 인터프리터 편에서는 우리의 작은 장난감 언어가 설계대로 완전히 동작하도록 만드는 나머지 요소들을 다룰 예정입니다. 변수 스코핑, 함수 정의, 함수 호출, 그리고 루프까지 말이죠. 재미있게 읽으셨기를 바랍니다(저는 글을 쓰는 내내 정말 즐거웠습니다!). 시리즈의 다음 글에서 다시 만나요!