[밑바닥부터 만드는 인터프리터 in go] 3. 평가기 동작 원리

들어가며

현재까지 렉서와 파서를 구현해보았다. 이제 평가기를 구현해볼 차례이다.

 

https://jihyun-devstory.tistory.com/82

[밑바닥부터 인터프리터 만들기 with go] 1. 렉서 구현하기

 

https://jihyun-devstory.tistory.com/83

[밑바닥부터 인터프리터 만들기 with go] 2. 파서 구현하기

 

---

 

평가기란?

평가기는 파서가 만든 AST를 순회하며 실제로 코드를 실행하는 역할을 한다.

 

 

---

 

Object 시스템

객체 시스템은 평가 결과를 표현하기 위한 내부 표현이 필요하다.

 

---

 

Object 인터페이스

 

object.go

package object

type ObjectType string

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

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

 

구체적인 Object 타입들

Integer

type Integer struct {
    Value int64
}

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

 

 

Boolean

type Boolean struct {
    Value bool
}

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

 

 

Null

type Null struct{}

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

 

---

 

Eval 함수 - 평가의 핵심

기본 구조

func Eval(node ast.Node) object.Object {
    switch node := node.(type) {
    
    // 프로그램 전체
    case *ast.Program:
        return evalProgram(node)
    
    // 표현식
    case *ast.IntegerLiteral:
        return &object.Integer{Value: node.Value}
    
    case *ast.Boolean:
        return nativeBoolToBooleanObject(node.Value)
    }
    
    return NULL
}

 

핵심 아이디어

1. AST 노드를 받는다
2. 노드 타입에 따라 처리
3. Object를 반환

 

---

 

표현식 평가

1. 정수 리터럴

case *ast.IntegerLiteral:
    return &object.Integer{Value: node.Value}

 

예시

입력: 5
AST: IntegerLiteral{Value: 5}
평가: Integer{Value: 5}

 

2. 불리언 리터럴

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

func nativeBoolToBooleanObject(input bool) *object.Boolean {
    if input {
        return TRUE
    }
    return FALSE
}

case *ast.Boolean:
    return nativeBoolToBooleanObject(node.Value)

 

최적화

• TRUE와 FALSE를 전역 변수로 관리
• 매번 새로 생성하지 않음

 

3. 전위 표현식

case *ast.PrefixExpression:
    right := Eval(node.Right)
    return evalPrefixExpression(node.Operator, right)

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

 

 

! 연산자

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

 

예시

입력: !true
평가: FALSE

입력: !5
평가: FALSE (0이 아닌 값은 truthy)

입력: !!true
평가: TRUE

 

 

- 연산자

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

 

 

예시

입력: -5
평가: Integer{Value: -5}

입력: -(-5)
평가: Integer{Value: 5}

 

4. 중위 표현식

case *ast.InfixExpression:
    left := Eval(node.Left)
    right := Eval(node.Right)
    return evalInfixExpression(node.Operator, left, right)

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

 

 

정수 연산

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

 

예시

 입력: 5 + 3
평가: Integer{Value: 8}

입력: 10 > 5
평가: TRUE

입력: 2 * 3 + 4
평가 순서:
    1. 2 * 3 = 6
    2. 6 + 4 = 10

 

---

 

조건문 평가

If Expression

case *ast.IfExpression:
    return evalIfExpression(node)

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

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

예시

입력: if (5 > 3) { 10 }
평가:
    1. 5 > 3 → TRUE
    2. isTruthy(TRUE) → true
    3. Eval(Consequence) → 10

입력: if (5 < 3) { 10 } else { 20 }
평가:
    1. 5 < 3 → FALSE
    2. isTruthy(FALSE) → false
    3. Eval(Alternative) → 20

 

---

 

Return 문 처리

문제 상황

if (10 > 1) {
    if (10 > 1) {
        return 10;
    }
    return 1;
}

 

안쪽 return 10이 실행되면 바깥쪽 if문도 빠져나가야 한다.

 

해결 방법 - ReturnValue Object

type ReturnValue struct {
    Value object.Object
}

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

 

Return 문 평가

case *ast.ReturnStatement:
    val := Eval(node.ReturnValue)
    return &object.ReturnValue{Value: val}

 

프로그램 평가

func evalProgram(program *ast.Program) object.Object {
    var result object.Object
    
    for _, statement := range program.Statements {
        result = Eval(statement)
        
        // ReturnValue를 만나면 즉시 중단
        if returnValue, ok := result.(*object.ReturnValue); ok {
            return returnValue.Value
        }
    }
    
    return result
}

 

블록문 평가

func evalBlockStatement(block *ast.BlockStatement) object.Object {
    var result object.Object
    
    for _, statement := range block.Statements {
        result = Eval(statement)
        
        // ReturnValue를 만나면 전파 (unwrap하지 않음!)
        if result != nil && result.Type() == object.RETURN_VALUE_OBJ {
            return result
        }
    }
    
    return result
}

 

 

핵심

• evalProgram: ReturnValue를 unwrap (Value만 반환)
• evalBlockStatement: ReturnValue를 그대로 전파

 

---

 

에러 처리

Error Object

type Error struct {
    Message string
}

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

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

 

에러 발생

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 evalProgram(program *ast.Program) object.Object {
    var result object.Object
    
    for _, statement := range program.Statements {
        result = Eval(statement)
        
        switch result := result.(type) {
        case *object.ReturnValue:
            return result.Value
        case *object.Error:
            return result // 에러 발생 시 즉시 중단
        }
    }
    
    return result
}

 

---

 

변수와 환경

Environment

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

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

func (e *Environment) Get(name string) (object.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) object.Object {
    e.store[name] = val
    return val
}

 

Let 문 평가

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

 

식별자 평가

case *ast.Identifier:
    return evalIdentifier(node, env)

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

 

예시

let x = 5;
let y = x + 3;
y;

평가:
    1. x = 5 → env.Set("x", Integer{5})
    2. x + 3 → env.Get("x") → 5 + 3 = 8
    3. y = 8 → env.Set("y", Integer{8})
    4. y → env.Get("y") → Integer{8}

 

---

 

함수

Function Object

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

 

함수 리터럴 평가

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

 

함수 호출 평가

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)

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
}

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 := extendFunctionEnv(function, args)
    evaluated := Eval(function.Body, extendedEnv)
    return unwrapReturnValue(evaluated)
}

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

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

 

예시

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

평가:
    1. 함수 리터럴 → Function{Parameters: [x, y], Body: ..., Env: ...}
    2. add = Function → env.Set("add", Function)
    3. add(5, 3):
        a. function = env.Get("add")
        b. args = [Integer{5}, Integer{3}]
        c. 새 환경 생성 (add의 Env를 outer로)
        d. 새 환경에 x=5, y=3 설정
        e. x + y 평가 → 8

 

 

---

 

클로저

왜 Env를 Function에 저장하는가?

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

let addTwo = newAdder(2);
addTwo(3); // 5가 나와야 함

 

동작 과정

1. newAdder 정의
   Function{
       Parameters: [x],
       Body: fn(y) { x + y },
       Env: 전역 환경
   }

2. addTwo = newAdder(2) 호출
   a. 새 환경 생성 (전역 환경을 outer로)
   b. x = 2 설정
   c. 내부 함수 반환
      Function{
          Parameters: [y],
          Body: x + y,
          Env: x=2가 있는 환경  ← 캡처!
      }

3. addTwo(3) 호출
   a. 새 환경 생성 (x=2 환경을 outer로)
   b. y = 3 설정
   c. x + y 평가
      - y는 현재 환경에서 찾음 → 3
      - x는 outer 환경에서 찾음 → 2
      - 결과: 5

 

---

 

테스트

정수 평가 테스트

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

 

불리언 평가 테스트

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

 

함수 테스트

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 parameters. Parameters=%+v",
            fn.Parameters)
    }
    
    if fn.Parameters[0].String() != "x" {
        t.Fatalf("parameter is not 'x'. got=%q", fn.Parameters[0])
    }
    
    expectedBody := "(x + 2)"
    
    if fn.Body.String() != expectedBody {
        t.Fatalf("body is not %q. got=%q", expectedBody, fn.Body.String())
    }
}

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

 

클로저 테스트

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

let addTwo = newAdder(2);
addTwo(3);`
    
    testIntegerObject(t, testEval(input), 5)
}

 

---

 

 

정리

1. Object 시스템: 평가 결과 표현
2. Eval 함수: AST 노드별 처리
3. Environmen: 변수 저장 및 스코프 관리
4. 클로저: 함수가 환경을 캡처

핵심 구현 내용
- 트리 워킹: AST를 순회하며 즉시 실행
- 재귀 평가: 중첩된 표현식 처리
- 에러 전파: 에러 발생 시 즉시 중단
- 환경 체인: outer 환경으로 스코프 구현

 

---

 

마치며

평가기를 구현하며 프로그래밍 언어가 어떻게 실행되는지 이해할 수 있었다. 토큰 → AST → 실행 과정을 직접 구현하며, 우리가 매일 사용하는 변수, 함수, 클로저가 내부적으로 어떻게 작동하는지 알게 되었다.

 

---

 

참고 자료

아래 링크를 클릭하면 책의 전체 코드를 다운받을 수 있다.

https://interpreterbook.com/waiig_code_1.7.zip