[CS] 나만의 인터프리터를 만들어보자! (3): 평가

🔊 해당 포스팅은 밑바닥부터 만드는 인터프리터 in go 책을 읽고 개인적인 정리 목적 하에 작성된 글입니다. 본 포스팅에 사용된 자료는 모두 본인이 직접 재구성하여 작성하였음을 알립니다.
 

출처: Yes24

---

저번 포스팅까지 해서 우리는 Monkey 라는 우리만의 프로그래밍 언어를 렉싱하는 렉서와 파싱하는 파서 2가지를 모두 Golang 기반으로 만들어보았다. 그리고 우리는 파서의 결과물로 AST 자료구조까지 만드는 것까지 모두 해보았다. 이제는 렉서와 파서의 입력으로 들어간 Monkey 언어 소스코드 문자열이 실제 의미를 갖도록 해주는 평가(Evaluation)를 하는 방법에 대해 배워볼 것이다.

1. 인터프리터의 마지막 단계: 평가(Evaluation) 프로세스

우리가 처음에 렉서를 만들 때 보았던 그림을 다시 갖고와 보자.

 

렉서 포스팅에서 보았던 그림

 

가장 먼저 소스코드 문자열이 입력으로 들어가면 렉서가 토큰화시킨 뒤 파서가 파싱을 수행해 추상구문트리인 AST 자료구조로 만든다고 했다. 이제 이렇게 만들어진 AST 자료구조는 평가 대상이 된다. 즉, AST 자료구조를 평가함으로써 입력으로 들어간 소스코드가 진짜 의미를 갖게 된다.

 

평가 프로세스가 추가되었다

 

인터프리터의 평가 프로세스는 번역된 언어의 동작 방식을 정의한다. 예를 들어, 아래와 같은 Monkey 언어 소스코드가 있다고 해보자.

 

# Monkey 언어임
let num = 10;
if (num) {
  return a;
} else {
  return b;
}

 

사람의 눈으로 읽으면 당연히 a가 반한될 것임을 알 수 있다. 하지만 이건 우리 사람의 판단이다. 컴퓨터가 우리와 같은 판단을 하기 위해서는 위 소스코드에 대한 평가가 반드시 필요하다. 즉, 평가 프로세스가 num 변수에 할당되어 있는 값 10을 참(true)으로 평가하도록 해야 한다. 또 다른 예시로 아래와 같은 소스코드가 있다고 해보자.

 

# Monkey 언어임
let one = fn() {
  printLine("one");
  return 1;
}

let two = fn() {
  printLine("two");
  return 2;
}

add(one(), two());

 

위 소스코드를 실행했을 때, 콘솔에 one 이라는 문자열이 먼저 등장할까? 아니면 two 라는 문자열이 먼저 등장할까? 이 순서를 결정하는 것은 이 Monkey 언어의 인터프리터가 호출 표현식의 인수를 평가하는 순서가 어떻게 되느지에 따라 달려 있다. 만약 오른쪽에 있는 인수를 먼저 평가한다면 two 라는 문자열이 먼저 콘솔에 등장할 것이다.(시험삼아, Python에서도 해보았는데, CPyhton 구현제 기준의 Python 인터프리터는 왼쪽에 있는 인수를 먼저 평가하는 것으로 보인다)

2. 다양한 평가(Evaluation) 전략

평가 프로세스에 사용되는 평가 전략은 인터프리터 구현체에 따라 다양하게 달라진다. 앞으로 평가를 구현하기에 앞서 우리는 렉서와 파서가 만든 AST 자료구조를 평가하는 전략에는 어떤 것들이 있는지 살펴볼 필요가 있다.

2-1. AST 자료구조를 그대로 번역하자: 트리 순회(Tree-walking) 인터프리터

트리 순회 인터프리터라는 평가 전략은 단순무식(?)한 방식이다. 말 그대로 AST 자료구조를 하나씩 순회하고 각 노드를 방문하면서 노드가 갖는 의미대로 즉시(on the fly) 처리한다. 가장 단순하기 때문에 다른 인터프리터의 원형이 되기도 한다. 다만, 트리 순회 인터프리터라는 전략을 사용해서 평가를 수행하기 전에 몇 가지 최적화를 수행하기도 한다. 첫번째는 정의했지만 안 쓰는 변수를 제거하는 방식으로 AST 자료구조를 재구성한다. 두 번째로는 AST 자료구조를 재귀 혹은 반복 평가에 더욱 적합한 중간 표현물(Intermediate Representation, IR)로 변경하기도 한다.

 

그런데 두 번째 최적화 방법에서 소개하는 중간 표현물 관련해서 좀 더 알아볼 내용이 있다. 어떤 인터프리터들은 똑같이 AST 자료구조를 순횧지만, AST 자료구조를 그대로 번역하는 대신 바이트코드(Bytecode) 라는 것으로 변환한다. 이 바이트코드가 바로 중간 표현물의 유형 중 하나이다. 바이트코드에는 AST 자료구조를 나타내는 정보가 들어가 있다. 이 바이트코드를 구성하는 형식과 명령코드의 유형들은 게스트 언어와 호스트 언어에 따라 달라진다. 게스트 언어란, 인터프리터가 번역할 대상인 언어 즉, 우리의 환경에서는 Monkey 언어가 된다. 반면에 호스트 언어는 인터프리터 자체를 구현하는 데 사용된 언어 즉, 우리의 환경에서는 Go 언어가 된다. 

 

바이트코드에 대해서 좀 더 세부적으로 알아보자. 대부분의 바이트코드에는 스택 연산인 Push, Pop을 하기 위해 이에 대응하는 명령 코드를 정의되어 있다. 하지만 그렇다고 해서 바이트코드가 물리적인 CPU 같은 연산 장치가 이해할 수 있는 기계어는 아니다. 다시 말해, 바이트코드는 사람이 직관적으로 이해할 수 있게 표현되어 있는 언어 중 가장 기계어 수준에 가까운 어셈블리어도 아니고, 기계어도 아니다. 그 어디 중간에 있다.

 

byte code는 어셈블리어와 기계어 사이의 그 중간 어디쯤에 있다

 

그러면 바이트코드라는 중간 결과물을 해석을 누가, 어떻게 하는 걸까? 해석을 하는 주체는 바로 인터프리터의 일부인 가상 머신이다. VMWare나 VirtualBox와 같은 소프트웨어들을 써본 분들이 있을 것이다. 이 소프트웨어들은 실제 머신과 CPU를 가상화(소프트웨어화)한 제품이다. 즉, 실메 머신과 CPU를 모방한 것이다. 이처럼 인터프리터의 가상 머신도 마찬가지다. 인터프리터의 가상머신도 바이트코드 형식을 이해하는 시스템을 모방한다. 일례로, CPython 구현체인 Python 에서는 PVM(Python Virtual Machine)이 바로 인터프리터의 가상머신이다. 

 

이렇게 바이트코드라는 중간 표현물을 사용하는 방식은 성능 상의 이점을 크게 만든다. 대체 어떤 장점이 있길래 성능 상의 이점을 만들었는지 살펴보자.

 

가장 먼저 중간 표현물로 만들어진 바이트코드 덕분에 인터프리터가 입력으로 들어온 소스코드 문자열을 매번 렉싱, 파싱하지 않아도 된다. 이렇게 렉싱하고 파싱하는 과정은 오버헤드가 큰 작업이다. 하지만 바이트코드가 중간 표현물로 만들어지면 최초에만 렉싱, 파싱을 수행하고 그 이후부터는 바이트코드에 나열된 가상머신이 이해할 수 있는 명령어들만 실행하면 되기 때문에 훨씬 빨라진다. 마치 CPU가 어셈블리 명령어를 빠르게 순차 실행하는 것처럼 말이다.

 

두 번째로는 바이트코드를 실행하는 주체인 가상 머신은 단순하고 효율적인 실행 모델을 가지기 때문이다. 가상 머신은 고정된 실행 흐름을 가지기 때문에 오버헤드가 낮고, 가상 머신의 구현체에 따라 연산 처리를 최적화할 수 있다. 

 

세 번재로는 캐시를 활용해서 재사용이 가능하다. 중간 표현물인 바이트코드는 캐싱해둘 수 있다. 일례로, Python으로 만들어진 프로그램을 실행하다 보면 .pyc 라는 확장자의 파일이 어느 순간 생성된 것을 볼 수 있다. 이 .pyc 파일 내부에는 바이트코드가 들어있으며 다음 실행 시에는 .pyc 파일을 사용해서 파싱과 컴파일 과정을 건너 뛰게 된다.

2-2. AST 자료구조도 고려하지 말자: JIT(Just In Time) 인터프리터/컴파일러

그런데 필자는 해당 내용을 공부하면서 궁금한 점이 생겼다. AST 자료구조를 가상머신이 바이트코드라는 중간 표현물로 변환하는 것까지는 이해가 되었는데, 그러면 실질적인 물리적 연산을 수행하는 CPU 같은 장치가 이해할 수 있는 기계어로 변환되고 실행되는 과정까지는 대체 어떻게 진행되는 건지 궁금했다. 결론부터 말하면 인터프리팅 방식이냐 JIT 컴파일 방식이냐에 따라 과정이 약간 달라진다. 일단 아래 순서도부터 보자.

 

평가 시 인터프리팅 방식과 JIT 컴파일 방식

 

두 방식 모두 바이트 코드로 변환하는 과정까지는 동일하다. 먼저 인터프리팅 방식 즉, 트리 순회 인터프리터 전략의 경우를 살펴보자. CPython 구현체인 Python을 예시로 들어보겠다. PVM이 바이트 코드와 대응되는 C 함수를 알아낸다. 그리고 이 C 함수를 호출함으로써 실제 물리적인 CPU 장치가 이해할 수 있는 기계어로 변환이 되고, 이 때 CPU가 해당 기계어로 실질적인 연산을 실행하게 된다.

 

반면에, JIT 컴파일 방식은 바이트 코드에 있는 명령어를 VM에서 직접 실행하지 않는다. VM이 바이트 코드를 분석하여 자주 실행되는 코드 예를 들어, loop 구문이나 함수와 같은 코드들은 즉시 기계어로 바로 변환 즉, 컴파일을 해버린다. 그리고 변환된 기계어를 RAM에 저장한 뒤, 물리적인 CPU 장치는 RAM에 저장된 기계어를 읽어들여 즉시 연산을 수행한다.

 

위 2개 방식을 비교해보았을 때 어떤 방식이 더 성능이 좋아 보일까? 딱 보아도 물리 CPU 연산 장치가 실행되기 전까지 거치는 단계가 간소화된게 보인다. 그래서 JIT 컴파일러 방식이 훨씬 더 빠른 성능을 보인다. JIT 이라는 용어는 Just In Time 의 줄임말로, VM이 실행 직전에 바이트코드를 기계어로 즉석에서 컴파일한다고 하여 Just In Time이라고 부른다.

 

심지어 어떤 평가 전략은 AST 자료구조를 고려하지도 않고 파서가 바로 바이트코드를 생성하는 경우도 있고, 어떤 구현체는 바이트코드로 컴파일 하는 과정을 지나치기도 한다. 모든 평가 전략을 여기서 다 알아볼 수는 없지만 어쨌건 정말 다양한 평가 전략이 있다는 사실은 반드시 알아두도록 하자. 보통은 번역 대상이 되는 언어가 요구하는 성능, 이식성, 구현자가 구현하고자 하는 목표치에 따라 평가 전략을 선택한다. 사실 가상 머신을 이용해서 바이트 코드를 컴파일하고 평가하도록 동작하는 인터프리터는 앞으로 계속 속도가 빨라질 것이다. 다만, 인터프리터의 평가 전략이 복잡해짐에 따라 만들기도 어려워질 뿐더러 인터프리터를 가져다가 사용하는 대부분의 개발자들 입장에서는 내부 동작을 완벽하게 이해하기가 점점 어려워지게 된다. Java의 JVM이나 Python의 PVM만 하더라도 물리 CPU 연산 장치의 원리를 이해해야할 뿐만 아니라 JVM, PVM 과 같은 가상 머신이 바이트 코드를 어떻게 이해하고 동작하는지에 대한 이해도 같이 동반되어야 한다. 물론 대부분의 개발자가 인터프리터를 직접 개발하지는 않는다. 개인적으로 이런 것이 나쁜 현상이라고 절대 생각하지 않는다. 오히려 뛰어난 개발자들이 내가 사용하는 언어의 속도를 가속화시켜준다는 점에서는 큰 감사인사를 전달하고 싶은 맘이다. 다만, 우리가 기억해야 할 것은 인터프리터가 보통 이런식으로 동작한다는 개념을 숙지하는 것이다. 이 개념에 대한 것만은 꼭 머릿속에 넣고 넘어가도록 하자.

3. 평가(Evaluation)기 만들기

평가에 대한 개념 뿐만 아니라 평가 전략에 대해서 이론적인 부분까지 배워보았으니 이제 직접 평가기를 구현해볼 차례다. 평가기의 입력으로는 (파서가 만들어낸) AST 자료구조의 노드가 들어간다. 그리고 평가기의 출력은 평가된 구문이 나온다. 소스코드로 표현하면 다음과 같다.

 

leftEvaluated = eval(astNode.Left)
rightEvaluated = eval(astNode.Right)

 

eval 이라는 메소드가 바로 평가기의  역할을 하는 것이다. 그러면 eval 메소드가 반환하는 것은 무엇일까? 이 말을 바꿔 말하면 우리가 구현하는 인터프리터가 어떤 내부 객체 시스템을 정의하는지와 같다. 현재 우리는 호스트 언어를 Go 언어로 하여 게스트 언어인 Monkey 언어를 해석하는 인터프리터를 개발하고 있다. 결국, Monkey 언어로 표현되는 타입(ex. 정수, Bool, Null, 실수, 문자열 등..)들에 대한 구현을 Go 언어로 표현해야 한다는 것이다. 그래서 보통 게스트 언어의 인터프리터를 구현하는 데 호스트 언어에 매우 의존적이게 된다.

 

일례로, Python은 인터프리터 언어이다. CPython 구현체 기준으로, Python이라는 게스트 언어를 개발한 호스트 언어는 C언어이다. 그렇기 때문에 Python의 타입은 C언어의 타입에 매우 의존적일 수 밖에 없다는 것이다. 

 

다시 우리의 상황으로 돌아와서 우리는 Monkey 언어를 평가하기 위해서 Monkey 언어의 객체 시스템을 Go 언어로 구현해야 한다. 이 구현에 대해서 한 발씩 내딛어보자.

3-1. 객체 표현하기: 정수(integer)

AST 노드를 구현할 때와 마찬가지로 객체를 구현하기 위해서 Go 언어의 인터페이스를 활용한다. 소스코드를 보자.

 

// object/object.go

package object

type ObjectType string

type Object interface {
	Type() ObjectType
	Inspect() string
}

 

Object 라는 인터페이스를 정의했고, 이 인터페이는 Type(), Inspect() 라는 2가지 메소드 구현을 충족시켜야 한다. Type() 메소드는 또 다른 새로운 타입인 ObjectType을 반환해야 하는데, 이는 소스코드에서 정의된 것처럼 단순히 문자열 타입을 의미한다. 그리고 Inspect() 메소드는 반환 타입이 문자열이다.

 

우리는 위 인터페이스를 기반으로 해서 Monkey 언어에서 정수 객체 타입을 구현해볼 것이다.

 

// object/object.go

const (
	INTEGER_OBJ = "INTEGER"
)

type Integer struct {
	Value int64
}

func (i *Integer) Inspect() string  { return fmt.Sprintf("%d", i.Value) }
func (i *Integer) Type() ObjectType { return INTEGER_OBJ }

 

Integer 라는 구조체를 정의했고, 해당 구조체는 Value 라는 멤버를 갖는다. 이 Value 멤버의 타입이 실질적으로 integer를 갖도록 한다. Integer 라는 구조체가 Object 인터페이스를 만족시키기 위해 2가지 메소드를 정의했다. Inspect 메소드는 문자열을 반환해야 하므로, Integer 구조체의 Value 멤버 변수를 반환하되 Sprintf 함수를 이용해서 문자열로 변환시키도록 한다. 다음은 Type 메소드는 ObjectType을 반환한다고 했다. 그런데 ObjectType 이라는 타입은 문자열이었다. ObjectType이 앞으로 여러가지일 것이기 때문에 상수로 정의해두도록 하자.

 

이게 끝이다. 우리는 Monkey 언어의 정수 객체를 구현했다. 

3-2. 객체 표현하기: Booleans

다음으로 표현해볼 객체는 true 또는 false를 갖는 Bool 타입이다. 방금 정수를 구현한 것과 거의 동일하다. 소스코드는 다음과 같다.

 

// object/object.go

const (
	INTEGER_OBJ = "INTEGER"
	BOOLEAN_OBJ = "BOOLEAN"
)

type Boolean struct {
	Value bool
}

func (b *Boolean) Inspect() string  { return fmt.Sprintf("%t", b.Value) }
func (b *Boolean) Type() ObjectType { return BOOLEAN_OBJ }

3-3. 객체 표현하기: Null

다음으로 표현해볼 객체는 바로 아무것도 없음을 의미하는 null 이다. 포인터를 사용하는 프로그래밍 언어를 조금이라도 사용해본 개발자라면 null 참조라는 상황을 한 번 쯤이라도 경험해보았을 것이다. null 참조란, 말 그대로 아무것도 없는 대상을 참조하려고 하는 것이다. 우리의 Monkey 언어는 null 참조도 표현할 수 있도록 하기 위해 null 객체도 구현하기로 했다. 

 

// object/object.go

const (
	INTEGER_OBJ = "INTEGER"
	BOOLEAN_OBJ = "BOOLEAN"
	NULL_OBJ    = "NULL"
)

type Null struct{}

func (n *Null) Inspect() string  { return "null" }
func (n *Null) Type() ObjectType { return NULL_OBJ }

 

null는 이전에 구현했던 정수, Boolean 과 다르게 구조체를 정의할 때 말 그대로 정말 아무것도 없는 빈 구조체를 정의했다. 이것만 차이점이고 나머지는 모두 동일하다.

3-4. 표현식 평가하기

방금까지 정수, Booleans, Null 이라는 3가지 종류의 객체를 구현했다. 이제 우리는 이 3가지 종류의 객체 시스템을 이용해서 평가하는 함수 즉, Eval 함수를 구현해볼 차례다. 먼저 Eval 함수의 시그니처는 다음과 같이 생겼다.

 

func Eval(node ast.node) object.Object

 

인자는 node로 우리가 이전에 파서를 구현할 때 만든 ast.Node 타입이다. 그리고 반환하는 타입은 우리가 정의한 Object 타입이다. 주목할 점은 인자를 ast.Node 라는 인터페이스를 충족시키는 타입이어야 하기 때문에 이로 인해 Eval 메소드를 재귀적으로 호출 할 수 있게 된다. 이러한 점은 여러가지 명령문들을 여러 번의 재귀적인 호출로 모두 평가할 수 있음을 의미한다.

3-4-1. 자체평가 표현식(1): 정수 리터럴

가장 먼저 해볼 표현식 평가는 자체평가 표현식이다. 자체평가 표현식이란, 평가를 하는 관점에서 리터럴을 부르는 것이다. 정수 리터럴, Bool 리터럴 등 말이다. 예를 들면, 5를 입력하면 5가 나오고, true를 입력하면 true가 나오는 것 말이다. 

 

먼저 정수 리터럴이라는 자체평가 표현식을 평가할 수 있도록 구현해보자. 그에 앞서 이를 위한 테스트 코드부터 살펴보자.

 

// evaluator/evaluator_test.go

package evaluator

import (
	"monkey/lexer"
	"monkey/object"
	"monkey/parser"
	"testing"
)

func TestEvalIntegerExpression(t *testing.T) {
	tests := []struct {
		input    string
		expected int64
	}{
		{"5", 5},
		{"10", 10},
	}
	for _, tt := range tests {
		evaluated := testEval(tt.input)
		testIntegerObject(t, evaluated, tt.expected)
	}
}

func testEval(input string) object.Object {
	l := lexer.New(input)
	p := parser.New(l)
	program := p.ParseProgram()
	return Eval(program)
}

func testIntegerObject(t *testing.T, obj object.Object, expected int64) bool {
	result, ok := obj.(*object.Integer)
	if !ok {
		t.Errorf("object is not Integer. got=%T (%+v)", obj, obj)
		return false
	}
	if result.Value != expected {
		t.Errorf("object has wrong value. got=%d, want=%d", result.Value, expected)
		return false
	}
	return true
}

 

테스트 코드 자체는 간단하다. 문자 5를 입력했을 때, 5로 평가되도록 하고, 문자 10을 입력했을 때, 10으로 평가되도록 하는 것이다.  그리고 testEval 이라는 메소드를 호출하는데, 이 메소드 안에서는 그동안 우리가 배웠던 문자열 소스코드를 입력 받으면 렉서를 생성하고, 이 렉서를 인자로 주어 파싱을 수행한다. 파싱이 수행된 결과인 AST 노드들이 program 변수에 담겨있고, 이에 대한 실질적인 평가를 수행하는 Eval 메소드를 호출한다. 물론 아직 우리는 Eval 메소드를 정의하지 않았다. 이제 정의해볼 차례다.

 

// evaluator/evaluator.go

package evaluator

import (
	"monkey/ast"
	"monkey/object"
)

func Eval(node ast.Node) object.Object {
	// type switch
	switch node := node.(type) {
	
	// 명령문
	case *ast.Program:
		return evalStatements(node.Statements)
		
	case *ast.ExpressionStatement:
		return Eval(node.Expression)
	
	// 표현식 
	case *ast.IntegerLiteral:
		return &object.Integer{Value: node.Value}
	}
	return nil
}

func evalStatements(stmts []ast.Statement) object.Object {
	var result object.Object
	
	for _, statement := range stmts {
		result = Eval(statement)
	}
	return result
}

 

Eval 메소드의 인자는 파서의 수행 결과물인 AST 노드라고 했다. 그러므로 ast.Node 인터페이스 타입이다. switch 구문에는 타입 스위치를 활용해서 ast.Node의 실제 타입을 추출해 확인한다. 실제 타입이 만약 여러가지 명령문들로 구성된 ast.Program 타입이라면 evalStatements 라는 새로운 메소드를 또 호출한다. evalStatements 메소드의 생김새를 보면 Eval 메소드를 재귀적으로 호출하는 것을 볼 수 있다. 복잡한 것은 아니고, 여러 명령문으로 구성된 것을 loop를 돌면서 명령문 하나씩 평가를 수행하는 것이다. 재귀적으로 계속 호출되면서 결국에는 object.Object 인터페이스 타입의 데이터가 반환된다. 

 

여러 개의 명령문으로 구성되어 있지 않고, 단일 명령문일 수도 있을 것이다. 그럴 경우는 즉시 Eval 메소드를 호출한다. 그리고 마지막으로 지금 우리가 집중하고 있는 자체평가 표현식일 경우, 즉시 정수면 object.Integer 라는 object.Object 인터페이스를 충족하는 타입을 반환한다.

 

이렇게 한 뒤, 아래 명령어를 실행하면 방금 작성한 테스크 코드는 통과한다.

 

go test ./evaluator

 

우리는 정수 리터럴이라는 자체평가 표현식 종류 중 하나를 평가할 수 있도록 구성했다. 다른 종류의 자체평가 표현식도 평가할 수 있도록 해보기에 앞서, 우리가 만들어온 REPL의 E(Evaluation) 기능을 마저 추가해보자. 이에 대한 코드 설명은 생략하겠다.

 

// repl/repl.go

package repl

import (
	"bufio"
	"fmt"
	"io"
	"monkey/evaluator"
	"monkey/lexer"
	"monkey/parser"
)

const PROMPT = ">> "

func Start(in io.Reader, out io.Writer) {
	scanner := bufio.NewScanner(in)

	for {
		fmt.Fprintf(out, PROMPT)
		scanned := scanner.Scan()
		if !scanned {
			return
		}
		line := scanner.Text()
		l := lexer.New(line)
		p := parser.New(l)

		program := p.ParseProgram()
		if len(p.Errors()) != 0 {
			printParserErrors(out, p.Errors())
			continue
		}

		evaluated := evaluator.Eval(program)
		if evaluated != nil {
			io.WriteString(out, evaluated.Inspect())
			io.WriteString(out, "\n")
		}
	}
}

const MONKEY_FACE = `            __,__
   .--.  .-"     "-.  .--.
  / .. \/  .-. .-.  \/ .. \
 | |  '|  /   Y   \  |'  | |
 | \   \  \ 0 | 0 /  /   / |
  \ '- ,\.-"""""""-./, -' /
   ''-' /_   ^ ^   _\ '-''
       |  \._   _./  |
       \   \ '~' /   /
        '._ '-=-' _.'
           '-----'
`

func printParserErrors(out io.Writer, errors []string) {
	io.WriteString(out, MONKEY_FACE)
	io.WriteString(out, "Woops! We ran into some monkey business here!\n")
	io.WriteString(out, " parser errors:\n")
	for _, msg := range errors {
		io.WriteString(out, "\t"+msg+"\n")
	}
}

3-4-2. 자체평가 표현식(2): Bool 리터럴

다음으로 추가해볼 자체평가 표현식은 true/false를 나타내는 Bool 리터럴이다. 먼저 테스트 코드부터 살펴보자. 정수 리터럴 때와 크게 달라지는 점은 없고, Bool 타입을 테스트 하기 위한 코드로만 살짝 변경된 것 뿐이다.

 

// evaluator/evaluator_test.go

func TestEvalBooleanExpression(t *testing.T) {
	tests := []struct {
		input    string
		expected bool
	}{
		{"true", true},
		{"false", false},
	}
	for _, tt := range tests {
		evaluated := testEval(tt.input)
		testBooleanObject(t, evaluated, tt.expected)
	}
}

func testBooleanObject(t *testing.T, obj object.Object, expected bool) bool {
	result, ok := obj.(*object.Boolean)
	if !ok {
		t.Errorf("object is not Boolean. got=%T (%+v)", obj, obj)
		return false
	}
	if result.Value != expected {
		t.Errorf("object has wrong value. got=%t, want=%t", result.Value, expected)
		return false
	}
	return true
}

 

Bool 리터럴 이라는 자체평가 표현식을 평가할 수 있도록 우리는 Eval 함수에 다음과 같이 추가하기만 하면 된다.

 

// evaluator/evaluator.go

func Eval(node ast.Node) object.Object {
	// type switch
	switch node := node.(type) {

	// 명령문
	case *ast.Program:
		return evalStatements(node.Statements)

	case *ast.ExpressionStatement:
		return Eval(node.Expression)

	// 표현식
	case *ast.IntegerLiteral:
		return &object.Integer{Value: node.Value}
	case *ast.Boolean:  // Bool에 대한 case 문 추가
		return &object.Boolean{Value: node.Value}
	}
	return nil

 

그런데 여기서 한 가지 개선할 포인트가 있다. 바로 Bool 값인 true/false는 언제든 동일하게 true/false 라는 점이다. 이전에 추가했던 정수의 경우 정수가 5일때도, 10일때도, 15일 때도, 999일 때도 존재한다. 즉, 매번 정수의 값이 달라진다는 점이다. 그렇기 때문에 우리는 매번 object.Integer 라는 구조체를 새로 생성했다. 하지만 true/false의 경우는 언제나 동일한 true/false이다. 따라서 위 소스코드처럼 매번 object.Boolean 이라는 구조체를 새로 생성할 필요가 없다는 것이다. 다시 말해서, 매번 새로운 구조체를 생성해 쓸데없는 메모리 낭비를 할 필요가 없다는 것이다.

 

결과적으로, true/false에 대한 구조체는 고정된 값이기에 전역 변수로 정의해놓고, 이를 가져다 사용해도 될 것이다. 이로 인해 개선된 코드는 다음과 같다.

 

// evaluator/evaluator.go

var (
	TRUE  = &object.Boolean{Value: true}
	FALSE = &object.Boolean{Value: false}
)

func Eval(node ast.Node) object.Object {
	// type switch
	switch node := node.(type) {

	// 명령문
	case *ast.Program:
		return evalStatements(node.Statements)

	case *ast.ExpressionStatement:
		return Eval(node.Expression)

	// 표현식
	case *ast.IntegerLiteral:
		return &object.Integer{Value: node.Value}
	case *ast.Boolean:
		return nativeBoolToBooleanObject(node.Value) // 개선된 방식
	}
	return nil
    
func nativeBoolToBooleanObject(input bool) *object.Boolean {
	if input {
		return TRUE
	}
	return FALSE
}

3-4-3. 자체평가 표현식(3): Null

다음으로 추가해볼 자체평가 표현식 종류로는 Null 이다. Null도 마찬가지로 Bool 값인 true/false 처럼 참조 가능한 객체를 하나만 만들어도 무방하다. 따라서 아래처럼 전역변수에 Null 용 구조체를 전역적으로 정의하고 case 구문에 추가해준다.

 

// evaluator/evaluator.go

var (
	NULL  = &object.Null{}
	TRUE  = &object.Boolean{Value: true}
	FALSE = &object.Boolean{Value: false}
)

 

자, 이제 지금까지 만든 타입 객체들을 REPL 기능을 활용해서 맘껏 입력해보자. 우리의 의도대로 평가까지 잘 동작하는 것을 볼 수 있다. 참고로 null 을 입력하면 아무것도 출력되지 않는 것이 맞다. 실제 파이썬 인터프리터에서도 null을 의미하는 None을 입력하면 아무것도 출력되지 않는 것을 볼 수 있다.

 

go run main.go

3-4-4. 전위 표현식

다음은 전위 표현식에 대해서 평가해보도록 하자. Monkey 언어에서 지원이 간으한 전위 표현식은 ! 와 - 이다. 우선 전위 표현식이란 무엇인지 다시 복습해조면 피연산자가 1개인 연산자를 의미한다. 우리는 전위 표현식을 적절히 평가하기 위해서는 피연산자에 대해서 먼저 평가를 수행하고 난 뒤, 전위 연산자를 평가하기 위해 직전에 피연산자를 평가한 값을 사용하게 된다.

 

먼저 전위 표현식을 평가하는 테스트 코드부터 작성해보자.

 

// evaluator/evaluator_test.go

func TestBangOperator(t *testing.T) {
	tests := []struct {
		input    string
		expected bool
	}{
		{"!true", false},
		{"!false", true},
		{"!5", false},
		{"!!true", true},
		{"!!false", false},
		{"!!5", true},
	}
	for _, tt := range tests {
		evaluated := testEval(tt.input)
		testBooleanObject(t, evaluated, tt.expected)
	}
}

 

그러면 이제 전위 표현식을 실질적으로 평가하도록 하는 로직을 작성할 차례다. 평가 로직의 엔트리 포인트 메소드 격인 Eval 메소드에 전위 표현식을 평가하도록 switch-case 구문을 추가해보도록 하자.

 

// evaluator/evaluator.go

func Eval(node ast.Node) object.Object {
	// type switch
	switch node := node.(type) {

	(.. 생략 ...)

	// 표현식
	case *ast.IntegerLiteral:
		return &object.Integer{Value: node.Value}
	case *ast.Boolean:
		return nativeBoolToBooleanObject(node.Value)
	case *ast.PrefixExpression:
		right := Eval(node.Right)
		return evalPrefixExpression(node.Operator, right)
	}
	return nil

 

이전에 파서를 구현할 때 정의한 AST 노드 중 전위 표현식에 해당하는 타입이라면 해당 분기를 타도록 한다. 방금 전위 표현식을 평가하기 위해서 피연산자부터 평가한다고 했다. 그래서 right := Eval(node.Right) 라는 코드를 사용해 전위 표현식의 오른쪽에 위치한 피연산자를 먼저 평가하도록 한다. 그리고 난 뒤, evalPrefixExpression 메소드를 사용해서 전위 연산자에 대한 평가를 수행한다. 이제 evalPrefixExpression 메소드에 대해서 살펴볼 차례다.

 

// evaluator/evaluator.go

func evalPrefixExpression(operator string, right object.Object) object.Object {
	switch operator {
	case "!":
		return evalBangOperatorExpression(right)
	default:
		return NULL
	}
}

 

evalPrefixExpression 메소드의 인자 중 operator 에는 전위 연산자가 담겨 넘어온다. ! 나 - 가 되겠다. 우선 ! 연산자부터 평가해보자. operator가 ! 일 경우, 다시 evalBangOperatorExpression 이라는 메소드를 호출한다. 당연히 evalBangOperatorExpression 메소드의 생김새를 봐보자.

 

// evaluator/evaluator.go

func evalBangOperatorExpression(right object.Object) object.Object {
	switch right {
	case TRUE:
		return FALSE
	case FALSE:
		return TRUE
	case NULL:
		return TRUE
	default:
		return FALSE
	}
}

 

지금까지의 코드를 작성하면 우리는 TestBangOperator 라는 이름의 테스트 코드가 성공적으로 수행된다. 동일한 방식으로 이번엔 - 전위 연산자에 대해서 평가를 수행해보자. 이번 테스트 코드는 기존에 작성했던 TestEvalIntegerExpression 이라는 테스트 코드에 테스트 케이스를 다음과 같이 추가해보자.

 

// evaluator/evaluator_test.go

func TestEvalIntegerExpression(t *testing.T) {
	tests := []struct {
		input    string
		expected int64
	}{
		{"5", 5},
		{"10", 10},
		{"-5", -5},    // 전위 연산자 테스트 케이스(1) 추가
		{"-10", -10},  // 전위 연산자 테스트 케이스(2) 추가
	}
	for _, tt := range tests {
		evaluated := testEval(tt.input)
		testIntegerObject(t, evaluated, tt.expected)
	}
}

 

추가된 테스트 케이스를 통과시키려면 방금 작성했던 메소드 중 evalPrefixExpression 메소드를 다음과 같이 확장해야 한다.

 

// evaluator/evaluator.go

func evalPrefixExpression(operator string, right object.Object) object.Object {
	switch operator {
	case "!":
		return evalBangOperatorExpression(right)
	case "-":
		return evalMinusPrefixOperatorExpression(right)
	default:
		return NULL
	}
}

 

그리고 evalMinusPrefixOperatorExpression 메소드라는 것이 새롭게 등장했다. 해당 메소드의 시그니처로 가보자.

 

// evaluator/evaluator.go

func evalMinusPrefixOperatorExpression(right object.Object) object.Object {
	if right.Type() != object.INTEGER_OBJ {
		return NULL
	}
	value := right.(*object.Integer).Value
	return &object.Integer{Value: -value}
}

 

로직 자체는 간단하다. 먼저 Type 이라는 메소드로 정수 객체인지 확인한다. 정수 객체가 아닌 경우 즉시 NULL을 반환하도록 하고, 정수 객체인 경우에는 type assertion을 이용해서 object.Integer 구조체의 Value 멤버를 추출한 후 -를 붙여 다시 object.Integer 구조체를 새롭게 생성해 리턴해준다.

3-4-5. 중위 표현식

다음은 중위 표현식을 평가해보도록 하자. 일단 지금 당장 Monkey 언어에서 중위 표현식을 평가할 수 있는 중위 표현식 예제는 크게 다음과 같다.

 

5 + 5;
5 - 5;
5 * 5;
5 / 5;

1 < 2;
1 > 2;
1 == 1;
1 != 1;

 

위 4가지는 결과값이 Boolean 값이 아닌 것, 아래 4가지는 결과값이 Boolean 값으로 나오게 된다. 우선 위는 결과값이 Boolean 값이 아닌 중위 표현식 즉, 위쪽 4가지의 중위 표현식을 평가할 수 있도록 해볼 것이다. 테스트 코드는 방금 사용했던 TestEvalIntegerExpression 이라는 테스트 코드 메소드를 또 사용할 것이다.

 

// evaluator/evaluator.go

func TestEvalIntegerExpression(t *testing.T) {
	tests := []struct {
		input    string
		expected int64
	}{
		{"5", 5},
		{"10", 10},
		{"-5", -5},
		{"-10", -10},
		{"5 + 5 + 5 + 5 - 10", 10}, // 새롭게 추가된 케이스들
		{"2 * 2 * 2 * 2 * 2", 32},
		{"-50 + 100 + -50", 0},
		{"5 * 2 + 10", 20},
		{"5 + 2 * 10", 25},
		{"20 + 2 * -10", 0},
		{"50 / 2 * 2 + 10", 60},
		{"2 * (5 + 10)", 30},
		{"3 * 3 * 3 + 10", 37},
		{"3 * (3 * 3) + 10", 37},
		{"(5 + 10 * 2 + 15 / 3) * 2 + -10", 50},
	}
	for _, tt := range tests {
		evaluated := testEval(tt.input)
		testIntegerObject(t, evaluated, tt.expected)
	}

 

위에 추가된 테스트 케이스를 커버하기 위해서 가장 먼저 해야할 것은 당연하게도 평가 프로세스의 엔트리 포인트 메소드인 Eval 메소드를 확장해야 한다.

 

// evaluator/evaluator.go

func Eval(node ast.Node) object.Object {
	// type switch
	switch node := node.(type) {

	// 표현식
	(... 생략 ...)
	case *ast.PrefixExpression:
		right := Eval(node.Right)
		return evalPrefixExpression(node.Operator, right)
	case *ast.InfixExpression:
		left := Eval(node.Left)
		right := Eval(node.Right)
		return evalInfixExpression(node.Operator, left, right)
	}
	return nil
}

 

중위 표현식도 전위 표현식 때와 마찬가지로 일단 먼저 피연산자들을 평가한다. 그렇기 때문에 Eval 메소드를 각가 호출해 연산자의 왼쪽, 오른쪽에 있는 각 피연산자들을 먼저 평가한다. 그리고 난 다음 evalInfixExpression 이라는 메소드를 호출한다. evalInfixExpression 메소드로 이동해보자.

 

// evaluator/evaluator.go

func evalInfixExpression(operator string, left, right object.Object) object.Object {
	switch {
	case left.Type() == object.INTEGER_OBJ && right.Type() == object.INTEGER_OBJ:
		return evalIntegerInfixExpression(operator, left, right)
	default:
		return NULL
	}
}

 

먼저 왼쪽, 오른쪽 피연산자들의 타입을 각각 확인한다. 현재 우리는 정수 타입들 간의 중위 표현식에 대해서만 평가하고 있으므로 두 피연산자의 타입이 모두 정수일 때만 evalIntegerInfixExpression 메소드를 호출한다. evalIntegerInfixExpression 메소드로 또 이동해보자.

 

// evaluator/evaluator.go

func evalIntegerInfixExpression(operator string, left, right object.Object) object.Object {
	leftVal := left.(*object.Integer).Value
	rightVal := right.(*object.Integer).Value
	switch operator {
	case "+":
		return &object.Integer{Value: leftVal + rightVal}
	case "-":
		return &object.Integer{Value: leftVal - rightVal}
	case "*":
		return &object.Integer{Value: leftVal * rightVal}
	case "/":
		return &object.Integer{Value: leftVal / rightVal}
	default:
		return NULL
	}
}

 

해당 메소드에서 실질적인 중위 표현식 연산이 이루어지는 것을 볼 수 있다. 먼저 피연산자 2개에 있는 실질적인 값을 추출한 뒤, 연산자 종류에 맞게 계산 후 다시 object.Integer 구조체로 만들어 반환해준다.

 

이제 나머지 4개의 중위 표현식 즉, 결과값이 Boolean으로 나오는 중위 표현식들에 대해서도 평가가 가능하도록 해보자. 지금까지 구현한 메소드의 확장 밖에 없다. 일단 기존 테스트 코드 메소드인 TestEvalBooleanExpression에 아래와 같이 테스트 케이스를 추가해보자.

 

// evaluator/evaluator_test.go

func TestEvalBooleanExpression(t *testing.T) {
	tests := []struct {
		input    string
		expected bool
	}{
		{"true", true},
		{"false", false},
		{"1 < 2", true},  // 새로 추가된 케이스들
		{"1 > 2", false},
		{"1 < 1", false},
		{"1 > 1", false},
		{"1 == 1", true},
		{"1 != 1", false},
		{"1 == 2", false},
		{"1 != 2", true},
	}
	for _, tt := range tests {
		evaluated := testEval(tt.input)
		testBooleanObject(t, evaluated, tt.expected)
	}
}

 

추가된 케이스를 커버하기 위해서 우리는 방금 구현했던 evalIntegerInfixExpression을 다음과 같이 확장하기만 하면 된다.

 

// evaluator/evaluator.go

func evalIntegerInfixExpression(operator string, left, right object.Object) object.Object {
	leftVal := left.(*object.Integer).Value
	rightVal := right.(*object.Integer).Value
	switch operator {
	case "+":
		return &object.Integer{Value: leftVal + rightVal}
	case "-":
		return &object.Integer{Value: leftVal - rightVal}
	case "*":
		return &object.Integer{Value: leftVal * rightVal}
	case "/":
		return &object.Integer{Value: leftVal / rightVal}
	case "<":
		return nativeBoolToBooleanObject(leftVal < rightVal)
	case ">":
		return nativeBoolToBooleanObject(leftVal > rightVal)
	case "==":
		return nativeBoolToBooleanObject(leftVal == rightVal)
	case "!=":
		return nativeBoolToBooleanObject(leftVal != rightVal)
	default:
		return NULL
	}
}

 

기존에 Boolean 리터럴을 평가할 때 만들어두었던 nativeBoolToBooleanObject 메소드를 재사용하면 간편하게 구현할 수가 있어진다.

지금까지는 모두 피연산자가 정수일 때의 중위 표현식이였다. 우리가 추가해주어야 할 것은 바로 Boolean이 피여산자일 때의 중위 표현식이다. 바로 다음과 같이 말이다.

 

true == true
false == false
true != false
true != true

 

Monkey 언어에서는 Boolean이 피연산자일 때의 중위 표현식일 경우, == 와 != 연산자만 지원이 된다. <, > 와 같은 대소비교 연산자는 지원되지 않는다. 따라서 지원이 되는 테스트 케이스를 먼저 추가해보자.

 

// evaluator/evaluator_test.go

func TestEvalBooleanExpression(t *testing.T) {
	tests := []struct {
		input    string
		expected bool
	}{
		{"true", true},
		{"false", false},
		{"1 < 2", true},
		{"1 > 2", false},
		{"1 < 1", false},
		{"1 > 1", false},
		{"1 == 1", true},
		{"1 != 1", false},
		{"1 == 2", false},
		{"1 != 2", true},
		{"true == true", true},
		{"false == false", true},
		{"true == false", false},
		{"true != false", true},
		{"false != true", true},
		{"(1 < 2) == true", true},
		{"(1 < 2) == false", false},
		{"(1 > 2) == true", false},
		{"(1 > 2) == false", true},
	}
	for _, tt := range tests {
		evaluated := testEval(tt.input)
		testBooleanObject(t, evaluated, tt.expected)
	}
}

 

 

이제 위 테스트 케이스를 커버하기 위해서 우리는 단 몇 줄만 evalInfixExpression 메소드에 추가만 해주면 된다.

 

// evaluator/evaluator.go

func evalInfixExpression(operator string, left, right object.Object) object.Object {
	switch {
	case left.Type() == object.INTEGER_OBJ && right.Type() == object.INTEGER_OBJ:
		return evalIntegerInfixExpression(operator, left, right)
	case operator == "==":
		return nativeBoolToBooleanObject(left == right)
	case operator == "!":
		return nativeBoolToBooleanObject(left != right)
	default:
		return NULL
	}
}

 

여기서 우리가 주목할 점은 true, false의 경우 동등성을 포인터 비교로 가능하다는 점이다. 왜냐하면 true, false는 우리가 전역변수로 정의한 것처럼 언제나 동일한 메모리 주소를 갖기 때문이다. NULL도 마찬가지다. 하지만 당연히 정수나 다른 데이터 타입의 경우에는 이런 것이 적용되지 않는다. 왜냐하면 정수는 매번 생성될 때마다 새로운 메모리 주소(포인터 변수)를 갖기 때문이다.

 

그래서 정수와 같이 포인터 변수로 동등성 비교가 안되는 경우에 대비하기 위해서 switch-case 구문 중에 가장 첫번째의 case 구문에 왼쪽, 오른쪽 피연산자의 타입이 모두 정수인 것을 확인한 뒤에 피연산자들이 모두 정수일 때의 중위 표현식을 평가하는 evalIntegerInfixExpression 메소드를 호출하도록 한 것이다.

3-4-6. 조건식

이번에 평가해볼 표현식은 조건식이다.조건식은 보통 if ~ else 구문으로 구성되어 있다. 핵심은 올바른 분기를 어떻게 평가할 것이냐이다. 예를 들어, 다음과 같은 소스코드가 있다고 해보자.

 

if (x > 10) {
    print 'A'
} else {
    print 'B'
}

 

조건식은 x > 10이다. 그러면 if 구문으로 분기시킬 경우는 조건식이 참일 경우에만 해야할까? 아니면 조건식이 참인 것 '같을' 때에도 해야할까? 즉, 정말 말 그대로 조건식 x > 10의 결과가 true일 때만 분기해야 하는지, 아니면 x > 10의 결과가 true가 아니지만 false도 아니고 null도 아닐 경우(이를 truthy 하다라고 함)에도 분기해야 할까? 결론부터 말하면 우리가 개발하고 있는 Monkey 언어에서는 조건식의 결과가 truthy 한 경우라면 모두 if 분기문을 타도록 할 것이다.

 

이제 조건식을 평가해보도록 하자. 다음 코드는 테스트 코드이다.

 

// evaluator/evaluator_test.go

func TestIfElseExpression(t *testing.T) {
	tests := []struct {
		input    string
		expected interface{}
	}{
		{"if (true) { 10 }", 10},
		{"if (false) { 10 }", nil},
		{"if (1) { 10 }", 10},
		{"if (1 < 2) { 10 }", 10},
		{"if (1 > 2) { 10 }", nil},
		{"if (1 > 2) { 10 } else { 20 }", 20},
		{"if (1 < 2) { 10 } else { 20 }", 10},
	}
	
	for _, tt := range tests {
		evaluated := testEval(tt.input)
		integer, ok := tt.expected.(int)
		if ok {
			testIntegerObject(t, evaluated, int64(integer))
		} else {
			testNullObject(t, evaluated)
		}
	}
}

func testNullObject(t *testing.T, obj object.Object) bool {
	if obj != NULL {
		t.Errorf("object is not NULL. got=%T (%+v)", obj, obj)
		return false
	}
	return true
}

 

그런데 위 테스트 코드의 몇 테스트 케이스를 보면 약간 다른 조건식이 있다. 바로 else 구문이 없는 케이스다. 조건식이 항상 if 와 else로만 이루어져 있으란 법은 없다. Monkey 언어에서는 else가 없이 if 구문만 있어도 조건식이 평가될 수 있도록 지원할 것이다. 

 

이제 조건식을 실질적으로 평가하는 함수를 작성해보자. 가장 먼저 평가의 엔트리 포인트 메소드격인 Eval 메소드에 case 구문을 추가해주자. 

 

// evaluator/evaluator.go

func Eval(node ast.Node) object.Object {
	// type switch
	switch node := node.(type) {

	// 명령문
	... (생략) ...

	// 표현식
	... (생략) ...
	case *ast.BlockStatement:
		return evalStatements(node.Statements)
	case *ast.IfExpression:
		return evalIfExpression(node)
	}
	return nil
}

 

그런데 갑자기 BlockStatement가 등장한 것이 의아할 수 있겠다. 이를 이해하기 위해서 우리는 예전에 조건식을 AST 노드로 파싱하기 위해 정의했던 IfExpression 구조체의 형태를 다시 한번 봐야 한다.

 

// ast/ast.go

type IfExpression struct {
	Token       token.Token
	Condition   Expression
	Consequence *BlockStatement
	Alternative *BlockStatement
}

type BlockStatement struct {
	Token      token.Token
	Statements []Statement
}

 

그 때 당시 조건식은 조건식과 if 분기문에 해당하는 Consequence 구문, if 분기문를 타지 않는 나머지 구문은 Alternative 구문이라고 불렀다. 그리고 이 Consequence, Alternative 구문은 하나 이상의 명령문으로 구성될 수 있기 때문에 우리는 BlockStatement 라는 구조체로 여러 개의 명령문을 들고 있는 구조체를 정의했었다. 따라서 평가하는 Eval 메소드의 case 구문에 BlockStatement이 추가된 것이다.

 

이제 그러면 evalIfExpression 메소드를 살펴볼 차례다.

 

// evaluator/evaluator.go

func evalIfExpression(ie *ast.IfExpression) object.Object {
	condition := Eval(ie.Condition)
	
	if isTruthy(condition) {
		return Eval(ie.Consequence)
	} else if ie.Alternative != nil {
		return Eval(ie.Alternative)
	} else {
		return NULL
	}
}

 

가장 먼저 조건식을 평가한다. 그리고 이 조건식 평가 결과가 Truthy 한지 체크하고 Truthy 하다고 판단되면 if 분기문인 Consequence 구문을 평가한다. 이 때, else 구문이 존재하는 즉, Alternative가 nil 이 아니라면 else 구문을 평가하도록 한다. Alternative가 nil 이라는 것은 곧 else 구문이 정의되지 않은 if 구문만 있는 조건식이라는 뜻이기 때문에 그러한 경우 즉시 NULL을 반환한다.

 

마지막으로 조건식 평가 결과가 Truthy인지 체크하는 isTruthy 메소드만 살펴보고 조건식 평가를 마무리하자.

 

// evaluator/evaluator.go

func isTruthy(obj object.Object) bool {
	switch obj {
	case NULL:
		return false
	case TRUE:
		return true
	case FALSE:
		return false
	default:
		return true
	}
}

 

아까 위에서 Truthy 하다라는 것이 false도 null도 아닌 값이라고 했다. 따라서 true일 때를 포함해서 false, null이 아닌 경우를 의미한다.

3-4-7. Return 문

다음으로 평가해볼 표현식을 Return 문이다. 우리가 흔히 프로그래밍 언어를 사용해서 함수를 작성하게 되면 반드시 return 문을 사용해서 해당 함수가 특정 값을 반환하도록 하곤 한다. 바로 그 return 문을 우리는 평가해볼 것이다. 우선 return 문은 일련의 명령문들을 평가하는 것을 멈추고, 명령문 안에 포함된 표현식을 남겨두고 나와버린다. 예를 들어, 아래와 같은 소스코드가 있다고 해보자.

 

5 * 5;
return 10;
10 + 1;

 

위 소스코드를 평가할 경우, 10 + 1 이라는 코드는 절대 평가되지 않는다. 왜냐하면 그 전에 return 문을 만나서 평가가 중단되기 때문이다. return 문을 구현하는 데에는 몇 가지 방법이 존재한다. Golang에서의 goto 구문이나 일반적인 프로그래밍 언어에서 사용하는 예외(Exception)를 사용한다. 현재 우리는 게스트 언어인 Monkey 언어를 호스트 언어인 Golang으로 구현하려고 하는 상황이다. Golang 에서는 catch 와 같은 키워드를 지원하지도 않고, goto 를 사용해서 깔끔하게 개발할 수 있는 방안도 갖고 있지 않다. 그래서 우리는 return 문을 구현하기 위해 단순히 반환값을 평가기에 넘길 것이다. 그리고 평가 도중 return 문을 만났을 때 실제 반환해야 할 값을 return 문 전용 객체 하나로 감싸서 처리할 것이다. 이렇게 하는 이유는 그래야 평가기가 이 return 전용 객체를 계속 추적할 수 있게 되고, 추척이 가능하면 평가 도중에 평가를 계속할지 말지 결정할 수 있는 기준이 되기 때문이다.

 

그래서 가장 먼저 할 일은 실제 반환해야 할 값을 return 문 전용 객체를 정의하는 것이다. 코드를 살펴보자.

 

// object/object.go

package object

const (
	... (생략) ...
    
	RETURN_VALUE_OBJ = "RETURN_VALUE"
)

type ReturnValue struct {
	Value Object
}

func (r *ReturnValue) Inspect() string  { return r.Value.Inspect() }
func (r *ReturnValue) Type() ObjectType { return RETURN_VALUE_OBJ }

 

ReturnValue 라는 새로운 구조체는 Value 라는 멤버만을 갖는데, 이 Value 타입이 Object인 것을 볼 수 있다. 결국, ReturnValue는 특별하게 새롭게 만들어진 객체라기 보다는 기존에 우리가 정의했던 Integer, Boolean, Null 등과 같은 Object를 한번 감싼 객체에 불과하다는 것이다. 

 

이제 다음으로는 테스트 코드를 살펴보자.

 

// evaluator/evaluator_test.go

func TestReturnStatements(t *testing.T) {
	tests := []struct {
		input    string
		expected int64
	}{
		{"return 10;", 10},
		{"return 10; 9;", 10},
		{"return 2 * 5; 9;", 10},
		{"9; return 2 * 5; 9;", 10},
	}
	
	for _, tt := range tests {
		evaluated := testEval(tt.input)
		testIntegerObject(t, evaluated, tt.expected)
	}
}

 

주로 return 문을 만났을 때 return 뒤에 있는 데이터를 잘 반환하는지 검증하는 간단한 테스트 코드다. 이제 이 테스트 코드를 통과시킬 수 있도록 하기 위해서 소스코드를 작성해보자. 먼저 Eval 메소드에 return 문에 대한 case 문을 추가하자.

 

// evaluator/evaluator.go

func Eval(node ast.Node) object.Object {
	// type switch
	switch node := node.(type) {

	// 명령문
	... (생략) ...

	// 표현식
	... (생략) ...
    
	case *ast.ReturnStatement:
		val := Eval(node.ReturnValue)
		return &object.ReturnValue{Value: val}
	}
	return nil

 

로직 자체는 간단하다. return 문이 등장할 경우, ReturnStatement 구조체의 ReturnValue 멤버를 평가하도록 한다. 그런 다음 방금 정의했던 object.ReturnValue 라는 새로운 구조체에 다시 평가한 결과 값을 다시 담는다. 다만 여기서 끝이 아니다. 우리는 evalStatements 라는 메소드에도 변경사항을 추가해주어야 한다. 왜냐하면 현재 평가기는 AST 자료구조를 순회하면서 Eval 메소드를  재귀적으로 호출하고 있는 구조이기 때문이다. 따라서 evalStatements 메소드에 다음과 같은 로직을 추가해주자.

 

// evaluator/evaluator.go

func evalStatements(stmts []ast.Statement) object.Object {
	var result object.Object

	for _, statement := range stmts {
		result = Eval(statement)

		if resultValue, ok := result.(*object.ReturnValue); ok {
			return resultValue.Value
		}
	}
	return result
}

 

바로, object.ReturnValue 로 type assertion을 수행해서 해당 메소드에서 실질적으로 반환할 데이터 즉, object.ReturnValue 구조체의 Value 멤버에 있는 데이터 값을 반환하는 것이다. 이런 변경사항이 반영됨에 따라 우리는 인터프리터에서 소스코드를 입력하고 평가되어 반환되는 결과가 Monkey 언어의 구현체가 아닌 실제 데이터만 반환되는 것이다. 일례로, 우리가 python 인터프리터에다가 3 + 3을 입력했을 때 6만 반환되는 것처럼 말이다.

 

그런데 위와 같은 evalStatements 메소드 로직은 한계점이 존재한다. 바로 중첩 구문이 존재할 때이다. 예를 들어, 아래와 같은 테스트 케이스가 추가되면 에러가 발생한다.

 

// evaluator/evaluator_test.go

func TestReturnStatements(t *testing.T) {
	tests := []struct {
		input    string
		expected int64
	}{
		... (생략) ...
		{`if (10 > 1) {
			if (10 > 1) {
			  return 10;
		    }
		  return 1;
		 }`, 10},
	}

	for _, tt := range tests {
		evaluated := testEval(tt.input)
		testIntegerObject(t, evaluated, tt.expected)
	}
}

 

테스트 코드 결과는 다음과 같은 오류를 내뱉는다.

 

--- FAIL: TestReturnStatements (0.00s)
    evaluator_test.go:51: object has wrong value. got=1, want=10
FAIL
FAIL    monkey/evaluator        0.444s
FAIL

 

메세지를 보면 10을 return 해야 하는데, 1을 return 했다. 즉, 중첩된 if 분기문을 타서 10을 반환했어야 했음에도 return 1; 이 평가된 것이다. 이를 해결하기 위해서 evalStatements 메소드를 2개로 분리하도록 하자. 먼저 evalProgram 이라는 메소드를 새롭게 정의하는데, 이 메소드는 evalStatements 메소드와 로직은 동일하다.

 

// evaluator/evaluator.go

func evalProgram(stmts []ast.Statement) object.Object {
	var result object.Object

	for _, statement := range stmts {
		result = Eval(statement)

		if resultValue, ok := result.(*object.ReturnValue); ok {
			return resultValue.Value
		}
	}
	return result
}

func evalBlockStatement(stmts []ast.Statement) object.Object {
	var result object.Object

	for _, statement := range stmts {
		result = Eval(statement)

		if result != nil && result.Type() == object.RETURN_VALUE_OBJ {
			return result
		}
	}
	return result
}

 

우리가 주목할 메소드는 evalBlockStatment 메소드다. 바로 이 메소드가 중첩된 구문이 등장해도 return 구문을 잘 처리할 수 있도록 해준다. 변경된 부분은 for-loop 구문 내의 if 분기문이다. 명령문을 파싱한 결과인 result 변수가 nil 이 아니면서 Type() 메소드를 호출했을 때 타입 값이 RETURN_VALUE_OBJ 라면 object.ReturnValue 구조체를 풀어내지 않고 해당 구조체 형태 그대로 리턴하도록 한다. 이렇게 하게 되면 바깥쪽 블록문 어딘가에서 실행을 멈추게 되고, evalProgram 메소드까지 실행되는 단계에 가서야 object.ReturnValue 구조체의 Value 값을 풀어내어 반환하게 된다.

 

그리고 분리시킨 메소드 evalProgram, evalBlockStatement 메소드를 Eval 메소드 내의 case 문에 적절히 교체해준다.

 

func Eval(node ast.Node) object.Object {
	// type switch
	switch node := node.(type) {

	// 명령문
	case *ast.Program:
		return evalProgram(node.Statements)
    
... (생략) ...

	// 표현식
... (생략) ...
	case *ast.BlockStatement:
		return evalBlockStatement(node.Statements)

... (생략) ...
	}
	return nil
}

3-5. 에러 처리

다음으로 해볼 것은 에러 처리이다. 프로그래밍 언어의 유형마다 내부적으로 에러를 처리하는 구현체가 존재한다. python에서는 Exception 객체가 될 것 같다. python에서의 Exception 객체처럼 우리도 Monkey 언어에서의 Exception 객체와 같은 것을 구현해 볼 것이다. 바로 이를 내부 에러 처리(internal error handling) 이라고도 한다. 이런 내부 에러란, 잘못된 연산자를 쓰거나 지원되지 않는 연산을 한다거나 또는 사용자가 프로그램 중간에 Ctrl + c(키보드 인터럽트)를 눌러 프로그램을 인위적으로 중단시키거나 하는 등 그 밖에 실행 중에 일어날 수 있는 사용자 또는 내부 에러를 의미한다.

 

에러 처리는 직전에 살펴본 return 문 처리 방식과 거의 같은 방식으로 구현할 수 있다. 왜냐하면 에러 처리도 return 문과 마찬가지로 일련의 명령문을 평가하다가 마주하면 도중에 평가를 멈추게 해야 한다는 점이 공통점이기 때문이다.

 

일단 우리만의 에러 구현체를 만들기 위해 다음과 같이 에러 객체를 정의해보자.

 

// object/object.go

const (
	... (생략) ...
    
	ERROR_OBJ = "ERROR"
)

type Error struct {
	Message string
}

func (e *Error) Inspect() string  { return "ERROR: " + e.Message }
func (e *Error) Type() ObjectType { return ERROR_OBJ }

 

에러 객체도 그동안 우리가 정의해왔던 다양한 타입의 객체와 비슷하게 정의했다. 동일하게 Inspect, Type 메소드를 구현하여 Object 라는 인터페이스를 충족시키도록 한다.

 

물론 상용 인터프리터를 목표로 하는 경우, 위와 같은 에러 처리에서 스택 트레이스를 달아볼 수도 있다. 즉, 문제가 발생한 지점의 행과 열 번호를 같이 넣어서 단순한 에러 메세지보다 더 많은 정보를 줄 수 있도록 할 수 있다. 하지만 이를 하기 위해서는 평가 이전에 입력 소스코드 문자열을 토큰화시키는 렉서가 토큰에 행과 열 번호를 달아놓았어야 구현이 쉬워진다. 사실 우리가 구현해온 렉서는 토큰에 행과 열 번호를 달아놓도록 하지는 않았다. 그러므로 우리 예제에서는 구현하지는 않지만, 일반 상용 인터프리터의 경우 이런 과정이 수반되었음을 알고 있는 것도 언젠가는 도움이 될 듯 하다.

 

에러 처리도 똑같이 테스트 코드부터 작성해보자.

 

// evaluator/evaluator_test.go

func TestErrorHandling(t *testing.T) {
	tests := []struct {
		input    string
		expectedMessage string
	}{
		{
			"5 + true;",
			"type mismatch: INTEGER + BOOLEAN",
		},
		{
			"5 + true; 5;",
			"type mismatch: INTEGER + BOOLEAN",
		},
		{
			"-true",
			"unknown operator: -BOOLEAN",
		},
		{
			"true + false;",
			"unknown operator: BOOLEAN + BOOLEAN",
		},
		{
			"5; true + false; 5",
			"unknown operator: BOOLEAN + BOOLEAN",
		},
		{
			"if (10 > 1) { true + false; }",
			"unknown operator: BOOLEAN + BOOLEAN",
		},
		{
			`
if (10 > 1) {
  if (10 > 1) {
    return true + false;
  }

  return 1;
}
`,
			"unknown operator: BOOLEAN + BOOLEAN",
		},
	}
	
	for _, tt := range tests {
		evaluated := testEval(tt.input)
		
		errObj, ok := evaluated.(*object.Error)
		if !ok {
			t.Errorf("no error object returned. got=%T (%+v)", evaluated, evaluated)
			continue
		}
		if errObj.Message != tt.expectedMessage {
			t.Errorf("error object has wrong message. got=%q, want=%q", errObj.Message, tt.expectedMessage)
		}
	}
}

 

위 소스코드 속 여러가지 테스트 케이스는 크게 2가지 동작을 의도하는지를 검증한다. 첫번째로 에러를 만들어내는 동작, 두번째는 평가를 중단하는 동작이다. 

 

이제 실제 평가 코드 내부에서 에러 처리를 해볼 것이다. 그 전에 앞서 우리만의 에러를 만들어보자. 구현은 간단하다. 위에서 정의한 우리만의 에러 객체를 활용하면 된다.

 

// evaluator/evaluator.go

func newError(format string, a ...interface{}) *object.Error {
	return &object.Error{Message: fmt.Sprintf(format, a...)}
}

 

참고로 위 코드를 작성하면서 알게 된 Golang 문법에 대해 소개한다. 우선 ... 이라는 것은 크게 2가지 기능을 하는데, 함수 시그니처에서는 가변 인자를 뜻한다. python에서 *args, *kwargs 라는 키워드로 주로 쓰이는 경우를 생각하면 된다. 그리고 return 구문에서 또 ... 이 등장하는데, 이는 가변인자로 받은 것을 그대로 분해 즉, unpacking을 수행하는 것이다. 위 예시에서는 a 인자가 가변인자로 들어오긴 했지만 만약 a 인자가 슬라이스로 받는다고 했을 때, a... 라고 명시하면 슬라이스 a는 원소들을 unpacking 하게 된다.

 

기존까지 우리는 문제가 되는 지점에 그냥 단순히 NULL을 리턴하도록 되어 있다. 이제 이렇게 하지 말고, 방금 정의한 newError 메소드로 에러를 핸들링 해보도록 하자.

 

// evaluator/evaluator.go

func evalPrefixExpression(operator string, right object.Object) object.Object {
	switch operator {
	case "!":
		return evalBangOperatorExpression(right)
	case "-":
		return evalMinusPrefixOperatorExpression(right)
	default:
		return newError("unknown operator: %s%s", operator, right.Type())
	}
}

func evalInfixExpression(operator string, left, right object.Object) object.Object {
	switch {
	case left.Type() == object.INTEGER_OBJ && right.Type() == object.INTEGER_OBJ:
		return evalIntegerInfixExpression(operator, left, right)
        
	... (생략) ...
    
	case left.Type() != right.Type():
		return newError("type mismatch: %s %s %s", left.Type(), operator, right.Type())
	default:
		return newError("unknown operator: %s %s %s", left.Type(), operator, right.Type())
	}
}

func evalMinusPrefixOperatorExpression(right object.Object) object.Object {
	if right.Type() != object.INTEGER_OBJ {
		return newError("unknown operator: -%s", right.Type())
	}
	value := right.(*object.Integer).Value
	return &object.Integer{Value: -value}
}

func evalIntegerInfixExpression(operator string, left, right object.Object) object.Object {
	leftVal := left.(*object.Integer).Value
	rightVal := right.(*object.Integer).Value
	switch operator {
	case "+":
		return &object.Integer{Value: leftVal + rightVal}
        
	...(생략)...
    
	default:
		return newError("unknown operator: %s %s %s", left.Type(), operator, right.Type())
	}
}

 

그런데 여전히 테스트 케이스 2개가 통과하지 못하고 있다. 여전히 평가를 멈추는 동작은 아직 동작하지 않는다는 점이다. 

 

이를 반영하기 위해서 우리는 evalProgram 과 evalBlockStatement 메소드에 다음과 같은 로직을 추가해준다.

 

// evaluator/evaluator.go

func evalProgram(stmts []ast.Statement) object.Object {
	var result object.Object

	for _, statement := range stmts {
		result = Eval(statement)
		
		switch result := result.(type) {
		case *object.ReturnValue:
			return result.Value
		case *object.Error:
			return result
		}
	}
	return result
}

func evalBlockStatement(stmts []ast.Statement) object.Object {
	var result object.Object

	for _, statement := range stmts {
		result = Eval(statement)

		if result != nil {
			rt := result.Type()
			if rt == object.RETURN_VALUE_OBJ || rt == object.ERROR_OBJ {
				return result
			}
		}
	}
	return result
}

 

두 메소드 보두 중간에 object.Error 타입인지를 체크하고 해당 타입이라면 즉시 평가를 중단하도록 추가했다. 마지막으로 할 일은 Eval 메소드 안에서 재귀적으로 Eval 메소드를 호출할 때마다 에러가 발생했는지 체크해야 한다. 그래야만 에러가 발생한 지점을 명확히 파악할 수 있고, 다른 곳으로 옮겨지지 않도록 해서 에러가 발생한 지점을 잘못된 지점으로 가리키는 문제를 막을 수 있다.

 

// evaluator/evaluator.go

func isError(obj object.Object) bool {
	if obj != nil {
		return obj.Type() == object.ERROR_OBJ
	}
	return false
}

 

위 함수를 Eval 메소드를 재귀적으로 호출하는 부분에다가 추가하여 검증하는 것을 반영하도록 하자.

3-6. 바인딩과 환경(Environment)

다음으로 추가해볼 기능은 바인딩(Bindings)이다. 우리가 지금까지는 let 문, return 문, 중위 표현식, 전위 표현식 등을 평가하는 것까지만 해보았다. 그런데 특정 유형의 표현식을 평가한 뒤에 어떤 변수에 저장을 할 수가 있다. 대표적으로 let 문이 그렇다. 아래처럼 말이다.

 

let x = 5 + 10;

 

일반적인 프로그래밍 언어에서 위와 같이 소스코드를 작성한 뒤, x를 출력하면 모두 15라는 값을 출력할 것이다. 즉, 위와 같은 let 문 표현식이 평가된 뒤, x 라는 값에 표현식 평가의 결과로 얻어지는 값(15)이 할당되는 것이다. 그리고 이를 바로 '바인딩'이라고 한다. 

 

이러한 바인딩 기능은 아직 우리가 만든 인터프리터에 추가되지 않은 상태다. 앞으로 추가해보도록 하자. 우리는 let 문 표현식에 대한 바인딩을 추가해볼 것이다. 이를 위한 테스트 코드는 다음과 같다.

 

// evaluater/evaluator_test.go

func TestLetStatements(t *testing.T) {
	tests := []struct {
		input    string
		expected int64
	}{
		{"let a = 5; a;", 5},
		{"let a = 5 * 5; a;", 25},
		{"let a = 5; let b = a; b;", 5},
		{"let a = 5; let b = a; let c = a + b + 5; c;", 15},,
	}
	
	for _, tt := range tests {
		testIntegerObject(t, testEval(tt.input), tt.expected)
	}
}

func TestErrorHandling(t *testing.T) {
	tests := []struct {
		input           string
		expectedMessage string
	}{
		{
			"foobar",
			"identifier not found: foobar",
		},
	}
    ... 생략 ...
}

 

테스트 케이스는 간단하다. 크게 2가지 기능을 테스트한다. 첫 번째는 let 문 안에 값을 만들어내는 표현식을 평가하는 것이고, 두 번째는 이름에 바인딩된 식별자를 평가하는 것이다. 여기에 한 가지 기능을 추가해본다면 만약 바인딩되어 있지 않은 식별자를 평가하려 할 때 에러를 내뱉도록 하는 것도 추가해 볼 것이다. 이 기능은 기존에 작성한 테스트 코드인 TestErrorHandling 메소드에 위와 같은 테스트 케이스를 추가해보자.

 

이제 위 테스트 케이스들을 통과하도록 만들기 위해 평가기의 엔트리포인트 메소드인 Eval 메소드에 소스코드를 추가해보자.

 

// evaluator/evalutor.go

func Eval(node ast.Node) object.Object {
	// type switch
	switch node := node.(type) {

	... 생략 ...
    
	case *ast.LetStatement:
		val := Eval(node.Value)
		if isError(val) {
			return val
		}
	}
	return nil

 

위 소스코드는 let 문 표현식을 평가하는 것만에서 끝난다. 즉, 바인딩 기능은 추가되지 않은 것이다. 우리는 이제 바인딩을 실질적으로 수행하는 로직을 작성해야 한다.

 

그에 앞서 사전에 알아둘 개념이 하나 있다. 바로 '환경(Environment)' 이라는 것이다. 환경이라는 개념은 인터프리터 분야에서 매우 흔하게 쓰이는 용어인데, 환경이란 인터프리터가 값을 추적할 때 사용하는 객체로, 값(value)을 이름(name)과 연관시키는 것이다. 이렇게 말하면 환경이라는 개념이 되게 낯설고 추상적으로 들릴 수 있지만, 결국 "문자열과 객체를 연관시키는 해시 맵 자료구조"에 불과하다. 이를 이해하기 위해 소스코드로 이해해보자. 우리는 아래와 같이 Environemnt 라는 이름의 새로운 구조체를 정의해보자.

 

// object/environment.go

package object 

type Environment struct {
	store map[string]Object
}

func NewEnvironment() *Environment {
	s := make(map[string]Object)
	return &Environment{s}
}

func (e *Environment) Get(name string) (Object, bool) {
	obj, ok := e.store[name]
	return obj, ok
}

func (e *Environment) Set(name string, val Object) Object {
	e.store[name] = val
	return val
}

 

Environment 구조체의 store 멤버 타입을 보면 단순한 map 자료구조를 래핑한 것에 불과한 것임을 알 수 있다. 이렇게 래핑을 한 이유는 추후에 우리가 코드를 확장하기 위한 준비라고 생각해두고 넘어가자. NewEnvironment 메소드는 방금 소개한 Environment 구조체를 새로 생성하는 역할을 한다. 이게 필요한 이유는 추후에 소개하겠지만 테스트할 때마다 새로운 환경을 만들기 위한 것이다. 그리고 Get 이라는 Pointer Receiver 메소드는 map 자료구조 즉, 환경에 저장되어 있는 특정 값을 가져오는 역할을, Set 메소드는 map 자료구조에 특정 값을 저장하는 역할을 한다.

 

이렇게 구현된 Environment 구조체를 우리는 어디에서 활용할까? 바로 Eval 이라는 엔트리포인트 메소드에 추가 인자로 넣어주어야 한다. 그래서 Eval 이라는 메소드의 시그니처는 다음과 같이 변경된다.

 

// evaluator/evaluator.go 의 Eval 메소드 시그니처 변경 전/후
// as-is
func Eval(node ast.Node) object.Object { 
    ...
}

// to-be
func Eval(node ast.Node, env *object.Environment) object.Object {
    ...
}

 

이제 그동안 작성된 소스코드에서 Eval 메소드가 호출되는 메소드의 시그니처를 모두 to-be 형태로 바꾸어주도록 하자. 그리고 testEval 이라는 테스트 코드 함수에서는 매번 테스트 케이스가 수행될 때마다 새로운 환경(Environment) 즉, 새로운 map 자료구조가 생성되도록 아래처럼 변경해주자.

 

// evaluator/evaluator_test.go

func testEval(input string) object.Object {
	l := lexer.New(input)
	p := parser.New(l)
	program := p.ParseProgram()
	env := object.NewEnvironment()
	return Eval(program, env)
}

 

이제 그러면 Eval 메소드 내부에서 바인딩하는 로직을 작성해보자. 우리가 위에서 정의했던 Environment의 Pointer Receiver 메소드를 사용하면 된다. 

 

// evaluator/evalutor.go

func Eval(node ast.Node) object.Object {
	// type switch
	switch node := node.(type) {

	... 생략 ...
    
	case *ast.LetStatement:
		val := Eval(node.Value)
		if isError(val) {
			return val
		}
        env.Set(node.Name.Value, val)
	}
	return nil

 

이제 env.Set 메소드로 환경에 let 문 표현식의 결과를 담아놓았다. 마지막으로 할 일은 식별자를 평가했을 때, 해당 map 자료구조에서 식별자를 key로 하는 값을 찾아와서 평가할 수 있도록 해야 한다. 예를 들어, let x = 5 + 5; 평가한 뒤, x; 라는 식별자 표현식도 평가를 해서 10 이라는 결과가 출력되도록 해야 한다는 의미이다. 이를 구현하기 위해 Eval 메소드에 식별자 표현식을 평가하는 로직을 추가해보자.

 

// evaluator/evaluator.go

func Eval(node ast.Node, env *object.Environment) object.Object {
	// type switch
	switch node := node.(type) {

	... 생략 ...
    
	case *ast.Identifier:
		return evalIdentifier(node, env)
	}
	return nil
}

func evalIdentifier(node *ast.Identifier, env *object.Environment) object.Object {
	val, ok := env.Get(node.Value)
	if !ok {
		return newError("identifier not found: %s", node.Value)
	}
	return val
}

 

그리고 테스트 코드를 수행하면 잘 성공하는 것을 볼 수 있다. REPL도 수행해서 바인딩이 잘 평가되는지도 수행해보도록 하자.

3-7. 함수와 함수 호출

이제 거의 막바지다. 다음으로 해볼 것은 함수와 함수 호출에 대한 평가이다. 이번 목차를 잘 소화하면 프로그래밍 언어에서 쉽게 이해하기 어려운 클로저라는 개념이 어떤 것인지도 이해해볼 수 있다. 우선 우리가 목표로 하는 기능을 구현하고 나면 REPL에서 다음과 같은 코드 출력이 가능해진다.

 

>>> let add = fn(a, b, c, d) { return a + b + c + d };
>>> add(1, 2, 3, 4);
10

>>> let max = fn(x, y) { if (x > y) { x } else { y } };
>>> max(5, 10)
10

>>> let callTwoTimes = fn(x, func) { func(func(x)) };
>>> callTwoTimes(3, fn(x) { x + 1 });
5

>>> let newAdder = fn(x) { fn(n) { x + n } };
>>> let addTwo = newAdder(2);
>>> addTwo(2);
4

 

위 기능을 구현하기 위해서는 크게 2가지 작업이 필요하다. 첫 번째는 우리가 그동안 구현해온 객체 시스템(object.go)에 함수를 나타내는 내부 표현을 정의해야 한다. 마치 정수를 우리가 object.Integer 구조체로 정의한 것처럼 말이다. 두 번째는 평가를 수행하는 엔트리포인트 함수격인 Eval 메소드가 '함수 호출'을 제대로 평가할 수 있어야 한다.

3-7-1. 함수 표현 정의하기

먼저 해볼 것은 함수 표현을 객체 시스템에 정의해보는 것이다. 객체 시스템에 정의해야만 하는 이유는 그래야 함수를 변수 이름에 바인딩하고, 표현식에 사용하기도 하며, 다른 함수에 특정 함수를 인자로 넘길 수도 있고 함수를 반환값으로 사용할 수도 있다. 

 

함수 표현을 정의하기 위해서 우리는 이전 Parser 관련 포스팅에서 함수 리터럴에 대해서 AST 자료구조를 만들 때 배웠던 FunctionLiteral 구조체를 기반으로 삼아볼 수 있다. FunctionLiteral 구조체에 대한 소스코드를 다시 한번 살펴보자.

 

// ast/ast.go

type FunctionLiteral struct {
	Token      token.Token
	Parameters []*Identifier
	Body       *BlockStatement
}

 

위 구조체를 보고 우리는 object.go 파일 즉, 우리만의 객체 시스템에 Function 이라는 구조체를 정의해보도록 하자.

 

// object/object.go

const (
	... 생략 ...
    
	FUNCTION_OBJ     = "FUNCTION"
)

type Function struct {
	Parameters []*ast.Identifier
	Body       *ast.BlockStatement
	Env        *Environment
}

func (f *Function) Type() ObjectType { return FUNCTION_OBJ }
func (f *Function) Inspect() string {
	var out bytes.Buffer

	params := []string{}
	for _, p := range f.Parameters {
		params = append(params, p.String())
	}

	out.WriteString("fn")
	out.WriteString("(")
	out.WriteString(strings.Join(params, ", "))
	out.WriteString(") {\n")
	out.WriteString(f.Body.String())
	out.WriteString("\n}")

	return out.String()
}

 

우선 객체 시스템에서의 함수도 역시 토큰은 필요하지 않다. 다만, Prameters 와 Body 라는 멤버들이 필요하다. Parameters는 0개 이상의 인자가 들어갈 수 있기 때문에 슬라이싱 형태의 식별자가 타입으로 지정되었다. 그리고 Body는 함수의 바디 스코프를 의미한다. 이 바디 스코프는 이미 우리가 배운 BlockStatement 타입이다. 그리고 마지막으로 Env 라는 필드가 존재하는데, 이 필드에 대해서는 추후에 자세히 배울 예정이다. 우선 여기서는 함수라는 것이 자기 환경과 같이 움직이기 때문에 이러한 특성을 활용해 클로저(Closure)가 동작할 수 있는 근거를 마련하도록 해준다고 알아두도록 하자.

 

우선 가장 간단한 테스트 코드부터 작성해보자. 테스트하려는 케이스는 기본적인 함수 리터럴 코드이다. 테스트 코드 로직은 그동안 한 것들과 동일하니 별다른 설명은 생략하겠다.

 

// evaluator/evaluator_test.go

func TestFunctionObject(t *testing.T) {
	input := "fn(x) { x + 2; };"
	evaluated := testEval(input)
	fn, ok := evaluated.(*object.Function)
	if !ok {
		t.Fatalf("object is not Function. got=%T (%+v)", evaluated, evaluated)
	}

	if len(fn.Parameters) != 1 {
		t.Fatalf("function has wrong number of parameters. got=%d, want=1", len(fn.Parameters))
	}

	if fn.Parameters[0].String() != "x" {
		t.Fatalf("parameter is not 'x'. got=%q, want='x'", fn.Parameters[0])
	}

	expectedBody := "(x + 2)"
	if fn.Body.String() != expectedBody {
		t.Fatalf("body is not %q. got=%q", expectedBody, fn.Body.String())
	}
}

 

이제 Eval 메소드에 파서가 만들어낸 AST 자료구조 중 함수 리터럴 즉, FunctionLiteral이 등장할 경우, Function 객체로 만들어주는 로직을 추가해보자.

 

// evaluator/evaluator.go

func Eval(node ast.Node, env *object.Environment) object.Object {
	// type switch
	switch node := node.(type) {

	... 생략 ...
    
	case *ast.FunctionLiteral:
		params := node.Parameters
		body := node.Body
		return &object.Function{Parameters: params, Body: body, Env: env}
	}
	return nil
}

 

위와 같이 코드를 작성하고 방금 작성한 테스트 코드를 수행하면 통과한다. 현재 목차에서 우리가 하려했던 것은 함수 표현을 우리의 객체 시스템에 정의하는 것이었다. 이 부분은 달성했다. 하지만 우리의 목표는 이정도 수준이 아니다. 다음부터 다룰 주제는 '함수 적용'이다.

3-7-2. 함수 적용(Function Application)

함수 적용이란 말은 인터프리터를 확장해서 함수를 호출할 수 있도록 코드를 수정하겠다는 의미이다. [목차 3-7-1]에서는 단순히 평가기가 함수 리터럴을 평가하는 것에 그쳤다. 하지만 만약 함수를 호출할 경우에는 어떻게 할 것인가? 바로 이 부분을 가능하게 하고자 한다. 테스트 코드 내의 테스트 케이스로 표현하면 아래와 같은 케이스들이 해당된다.

 

// evaluator/evaluator_test.go

func TestFunctionApplication(t *testing.T) {
	tests := []struct {
		input    string
		expected int64
	}{
		{"let identity = fn(x) { x; }; identity(5);", 5},
		{"let identity = fn(x) { return x; }; identity(5);", 5},
		{"let double = fn(x) { x * 2; }; double(5);", 10},
		{"let add = fn(x, y) { x + y; }; add(5, 5);", 10},
		{"let add = fn(x, y) { x + y; }; add(5 + 5, add(5, 5));", 20},
		{"fn(x) { x; }(5)", 5},
	}

	for _, tt := range tests {
		testIntegerObject(t, testEval(tt.input), tt.expected)
	}
}

 

함수 적용을 해보기에 앞서 우리는 과거에 배웠던 AST 자료구조 중 함수 호출 표현식을 파싱했던 내용을 회고할 필요가 있다. 함수 호출 표현식은 ast.CallExpression 이라는 구조체로 정의했고, 이 함수 호출 표현식은 크게 2가지 형태로 케이스가 나뉜다고 했다. 첫 번째 케이스는 식별자일 때이다. 이 식별자일 때의 예시 소스코드는 다음과 같다.

 

>>> add = fn(x, y) { return x + y };
>>> add(1, 2)
3

 

두 번째 케이스는 함수 리터럴 자체일 경우이다.

 

>>> fn(x, y) { return x + y }(1, 2);
3

 

물론 Eval 메소드에서 이 2가지 케이스에 따라 로직이 분기되거나 하지는 않는다. 완벽하게 작성된 Eval 메소드는 아니지만 지금 당장 작성할 수 있는 로직은 다음과 같다.

 

// evaluator/evaluator.go

func Eval(node ast.Node, env *object.Environment) object.Object {
	// type switch
	switch node := node.(type) {

	... 생략 ...
    
	case *ast.FunctionLiteral:
		params := node.Parameters
		body := node.Body
		return &object.Function{Parameters: params, Body: body, Env: env}
	case *ast.CallExpression:
		function := Eval(node.Function, env)
		if isError(function) {
			return function
		}
		// TODO: 작성 예정
	}
	return nil
}

 

이제 본격적으로 함수 호출 표현식을 평가해볼 차례다. 가장 먼저 할 일은 '호출 표현식의 인수를 평가'하는 동작이다. 먼저 예시 소스코드를 보자.

 

>>> let add = fn(x, y) { x + y };
>>> add(2 + 2, 5 + 5);

 

우리가 평가할 부분은 add 뒤에 소괄호가 나오면서 인자로 등장하는 2 + 2 와 5 + 5 이다. 우리는 2 + 2 와 5 + 5를 자체 표현식이 아닌 각 표현식의 결과물들 즉, 4와 10으로 평간한 뒤 넘기고 싶은 것이다. 이것을 바로 호출 표현식의 인수를 평가한다고 한다. 인수를 평가하는 동작은 사실 여러개의 표현식으로 구성된 즉, 표현식 리스트를 평가하는 동작과 동일하다. 왜냐하면 방금 이야기 했듯이 2 + 2 와 5 + 5는 각각 표현식을 의미하고, 2개의 표현식으로 구성된 셈이기 때문이다. 아래 소스코드를 보자.

 

// evaluator/evaluator.go

func Eval(node ast.Node, env *object.Environment) object.Object {
	// type switch
	switch node := node.(type) {

	... 생략 ...
    
	case *ast.CallExpression:
		function := Eval(node.Function, env)
		if isError(function) {
			return function
		}
		args := evalExpressions(node.Arguments, env)
		if len(args) == 1 && isError(args[0]) {
			return args[0]
		}
	}
	return nil
}

func evalExpressions(exps []ast.Expression, env *object.Environment) []object.Object {
	var result []object.Object

	for _, e := range exps {
		evaluated := Eval(e, env)
		if isError(evaluated) {
			return []object.Object{evaluated}
		}
		result = append(result, evaluated)
	}
	return result
}

 

Eval 메소드를 보면 evalExpressions 라는 새로운 메소드가 등장한다. 그리고 이 메소드의 인자로 node.Arguments가 등장한다. 이는 우리가 이전에 배웠다고 한 AST 자료구조 중 함수 호출 표현식을 의미하는 CallExpression 구조체의 멤버를 의미한다. 잠시 상기시키기 위해 CallExpression 구조체 소스코드 부분만 발췌해왔다.

 

// ast/ast.go

type CallExpression struct {
	Token     token.Token
	Function  Expression
	Arguments []Expression
}

 

Arguments를 보면 슬라이싱 형태의 표현식 즉, 표현식 리스트임을 볼 수 있다. 다음으로 evalExpressions 메소드를 살펴보자. 특별한 것이 없다. 표현식 리스트가 들어왔기 때문에 이 리스트에 대해서 루프를 돌면서 표현식 1개씩 Eval 메소드를 또 한번 호출해주면서 1개의 표현식에 대해서 평가를 수행하고 result 변수에 append 하는 로직이다. 여기서 우리가 주목할 부분은 바로 이 표현식 리스트에 대해 루프를 돌면서 평가를 하는 순서가 바로 함수 호출의 인자가 여러 개가 있을 경우, 어떤 쪽의 인자부터 평가되는지 순서를 눈치챌 수 있는 힌트가 된다. 한 번 자신에게 가장 익숙한 인터프리터 언어의 평가기 구현체를 한번 살펴보는 것도 재밌을 것 같다.

 

함수 호출 표현식의 인자를 평가하는 것은 이제 마쳤다. 다음으로는 실질적으로 함수의 로직을 담당한다고 할 수 있는 함수 Body를 평가해야 한다. 함수 Body는 앞서 배워왔던 BlockStatement에 해당하고 이 BlockStatement를 평가하는 로직은 evalBlockStatement로 이미 구현되어 있기 때문에 단순하게 생각하면 Eval 메소드의 인자에 함수 Body만 인자로 집어넣으면 되지 않을까 생각할 수 있다.

 

하지만 이렇게 구현하게 되면 함수 호출 표현식의 인자 부분 때문에 문제가 발생한다. 즉, 함수 Body에서 인자들을 참조해야 하는데, 이렇게 구현하게 되면 함수 Body를 평가할 때 인자들을 알 수 없는 이름을으로 간주하게 된다. 따라서 우리는 함수가 평가될 환경을 바꾸는 동작을 수행함으로써 이 문제를 해결해야 한다. 그래야 함수 Body안에서 참조하는 인자들이 제대로 된 값으로 변환된다. 

 

그렇다고 해서 현재 환경이 전달한 인자를 함수 Body에 그대로 추가하면 또 문제가 발생한다. 바로 이전에 있던 바인딩을 덮어쓰게 된다. 이게 대체 무슨 말인가? 아래 예제 소스코드가 있다고 해보자.

 

let i = 5;
let printNum = fn(i) {
    puts(i);
};

printNum(10);
puts(i);

 

puts 함수는 C언어에서와 동일하게 행을 출력해주는 함수라고 생각하자. 우리가 흔히 사용하는 인터프리터 언어의 경우 위 소스코드 로직이라면 결과물은 각각 10과 5가 나올 것이라고 예상할 수 있다. 하지만 방금 이야기한 '덮어쓰기 문제'가 발생하게 되면 결과는 10과 10을 출력하게 된다. 다시 말해, printNum(10); 이라는 함수 호출 표현식이 평가되면서 10이 인수로 전달된다. 즉, 현재 환경에서 10을 전달하는 것이다. 이 때 printNum 이라는 함수 리터럴을 평가하면서 현재 환경에서 전달된 10이 전역적으로 선언된 i = 5 라고 바인딩된 값을 덮어쓰기 한다는 의미이다.

 

따라서 우리는 이러한 문제를 피하기 위해서 현재 환경을 보존하면서 동시에 새로운 환경을 만들어야 하고, 이러한 것을 '환경 확장'이라고 부르도록 하자.  환경 확장을 우리가 그동안 만든 소스코드 레벨로 이해한다면 [목차 3-6]에서 배운 object.Environment 인스턴스를 만드는데, 해당 인스턴스에 확장할 환경을 가리키는 포인터 변수를 갖도록 하는 것이다. 이렇게 함으로써 우리는 현재 환경을 유지하면서 새로운 환경을 새롭게 생성하게 된다.

 

이렇게 하는 이유는 새로운 환경에서 Environment 구조체의 Get 메소드를 호출했을 때 해당 환경에 존재하지 않는 이름과 값이라면 해당 환경을 감싸하고 있는 환경에서 찾고, 또 존재하지 않으면 감싸고 있는 환경에서 찾고를 반복한다. 그러다가 결국은 찾을 수 없을 때 우리는 Undefined 라는 키워드를 가지면서 선언된 변수를 찾을 수 없다는 에러가 등장하게 된다. 환경을 감싸는 코드는 다음과 같다.

 

// environment/environment.go

package object

type Environment struct {
	store map[string]Object
	outer *Environment
}

func NewEnclosedEnvironment(outer *Environment) *Environment {
	env := NewEnvironment()
	env.outer = outer
	return env
}

func NewEnvironment() *Environment {
	s := make(map[string]Object)
	return &Environment{store: s, outer: nil}
}

func (e *Environment) Get(name string) (Object, bool) {
	obj, ok := e.store[name]
	if !ok && e.outer != nil {
		obj, ok = e.outer.Get(name)
	}
	return obj, ok
}

func (e *Environment) Set(name string, val Object) Object {
	e.store[name] = val
	return val
}

 

위 소스코드로 구현한 매커니즘은 흔히 우리가 사용하는 언어에서 변수 스코프의 개념을 반영하고 있다. 예를 들어, 중첩된 스코프가 있다고 했을 때, 안쪽과 바깥쪽 스코프가 존재한다. 최초에는 안쪽 스코프에서 값을 찾으려고 시도하고 찾지 못한다면 바깥쪽 스코프에서 찾는 사례이다.

 

이제 위에서 구현한 환경 확장이라는 것을 Eval 메소드에 적용해볼 차례다. 수정된 Eval 메소드는 다음과 같다.

 

// evaluator/evaluator.go

func Eval(node ast.Node, env *object.Environment) object.Object {
	// type switch
	switch node := node.(type) {

	... 생략 ...
    
	case *ast.CallExpression:
		function := Eval(node.Function, env)
		if isError(function) {
			return function
		}
		args := evalExpressions(node.Arguments, env)
		if len(args) == 1 && isError(args[0]) {
			return args[0]
		}
		return applyFunction(function, args)
	}
	return nil
}

 

applyFunction 메소드가 새롭게 등장했다. 이 메소드의 생김새를 보자.

 

// evaluator/evaluator.go

func applyFunction(fn object.Object, args []object.Object) object.Object {
	function, ok := fn.(*object.Function)
	if !ok {
		return newError("not a function: %s", fn.Type())
	}
	extendedEnv := extendedFunctionEnv(function, args)
	evaluated := Eval(function.Body, extendedEnv)
	return unwrapReturnValue(evaluated)
}

 

먼저 type assertion을 통해서 Object 타입의 인터페이스에서 구체적인 타입인 Function 타입으로 바꾸어준다. 그런다음 또 새로운 메소드인 extendedFunctionEnv가 등장한다. 이름에서 유추할 수 있다시피 이 메소드가 바로 확장 환경을 만들어주는 것이다. extendedFunctionEnv 메소드로 가보자.

 

// evaluator/evaluator.go

func extendedFunctionEnv(fn *object.Function, args []object.Object) *object.Environment {
	env := object.NewEnclosedEnvironment(fn.Env)
	
	for paramIdx, param := range fn.Parameters {
		env.Set(param.Value, args[paramIdx])
	}
	return env
}

 

주목할 부분은 확장 환경을 새롭게 생성한 뒤, 해당 환경에 인자로 받은 Function의 파라미터들과 해당 파라미터들을 평가한 결과값을 넣어준다는 것이다. 파라미터를 평가한 결과값들은 args 라는 변수에 담겨있고, 이 args 라는 변수는 Eval 메소드 내의 evalExpressions 메소드에 의해 평가되었다.

 

그리고 마지막으로 unwrapReturnValue 라는 메소드가 있다. 해당 메소드는 우리가 이전에 evalProgram 메소드를 구현했을 때와 유사하다. 잘 기억이 나지 않는다면 evalProgram 메소드로 잠시 돌아가보자.

 

// evaluator/evaluator.go

func unwrapReturnValue(obj object.Object) object.Object {
	if returnValue, ok := obj.(*object.ReturnValue); ok {
		return returnValue.Value
	}
	return obj
}

 

이렇게 확장 환경을 사용하는 이유는 바로 클로저 매커니즘을 사용할 때의 케이스 때문이다. 이를 위한 테스트 코드는 다음과 같다.

 

// evaluator/evaluator_test.go

func TestClosures(t *testing.T) {
	input := `
let newAdder = fn(x) {
  fn(y) { x + y };
};}

let addTwo = newAdder(2);
addTwo(2);`

	testIntegerObject(t, testEval(input), 4)
}

 

테스트 코드르 돌려보면 위와 같은 클로저 매커니즘도 잘 동작하는 것을 볼 수 있다. 그런데 아직 클로저라는 게 무엇이고, 왜 이것 때문에 확장 환경을 사용했는지가 잘 와닿지 않는다. 방금 사용했던 테스트 케이스를 보자.

 

let newAdder = fn(x) { fn(y) { x + y } };
let addTwo = newAdder(2);

 

클로저는 그 함수가 정의된 환경을 '담아 내는' 함수이다. 그래서 클로저는 자신의 환경을 담고 움직이다가 호출되었을 때 그 환경에 접근한다. 위 예제 코드에서 newAdder 이라는 변수는 고차(High-order) 함수이다. 고차 함수란, 함수를 반환하거나 다른 함수를 인자로 받는 함수를 말한다. 위 예제 코드의 경우, 함수를 반환하는 유형의 고차 함수이다. 

 

하지만 클로저는 단순한 함수가 아니다. addTwo에 인자 2를 넘겨서 호출했을 때 즉, "addTwo(2)" 라고 했을 때 addTwo에는 반환된 클로저가 바인딩되어 있다. 왜냐하면 "addTwo(2)" 라고 해야 addTwo 함수의 호출 표현식이 평가되기 때문이다. 그러면 addTwo를 클로저로 만드는 것은 무엇일까? 바로 addTwo가 호출되었을 때 즉, "addTwo(2)" 라고 했을 때 갖고 있는 바인딩이 addTwo를 클로저로 만들게 된다. addTwo가 호출되었을 때 addTwo 함수는 호출 인수인 파라미터 y에 접근할 수도 있고, 심지어 newAdder(2)에 호출된 시점에 바인딩된 x에도 접근할 수 있다. 결국, addTwo 함수는 Body 내부에서 x, y를 출력하면 모두 값이 출력된다는 것이다. 

 

다시 말해서, 클로저 함수인 addTwo는 여전히 코드가 정의될 당시의 환경 즉, 위 예제 소스코드로 치면 "let addTwo = newAdder(2)" 라고 정의되는 환경에도 접근할 수 있다는 말이다.

 

이러한 클로저의 특성 때문에 이를 반영하기 위해서 우리는 확장 환경이라는 개념을 도입하고 적용한 것이다. 참고로 고차 함수의 다른 종류로 다른 함수를 인자로 받는 함수도 우리의 인터프리터에서는 동작한다.

 

>> let add = fn(a,b) {a+b};
>> let sub = fn(a,b) {a-b};
>> let applyFunc = fn(a, b, func) { func(a, b) };
>> applyFunc(2, 2, add)
4
>> applyFunc(10, 2, sub);
8