이전 글에서 간단한 프로그래밍 언어를 위한 파서parser를 구현했습니다. 여기서는 파서의 파싱 결과인 추상 문법 트리를 값으로 평가하는 인터프리터interpreter를 만들 것입니다. 이것으로 다음과 같은 코드를 실행시키는 인터프리터가 완성됩니다.

g = 98/10
y = t -> y0 -> g*t*t/2 + y0
y(10)(5)

이것은 첫 글에서 목표로 했던 간단한 함수형 프로그래밍 언어 코드입니다. 다시 말해, 처음에 말뿐이었던 문법을 실제로 따르는 언어를 새로 만들어낸 것입니다.

앞으로의 내용을 통해, 변수의 할당과 함수의 호출이 어떻게 동작하는지 구현을 통해 알아보게 될 것입니다. 그 과정에서 클로저closure 또한 직접 만들게 될 것이고, 이를 통해 y(10)(5)와 같은 함수의 커링currying을 지원할 수 있게 됩니다.

숫자 값 평가

처음에는 다음과 같이 아주 간단한 코드를 실행하는 것이 목표입니다. 숫자만 있을 뿐이지만 이것도 소스 코드이긴 합니다.

인터프리터는 입력한 숫자 값이 나오게끔 만들어야 합니다.

먼저, 평가한 값의 타입을 내부적으로 관리하기 위한 일종의 래퍼wrapper 클래스를 준비합니다. 여기서는 kind가 그 타입을 가질 것입니다.

class Value:
    def __init__(self, kind, value):
        self.kind = kind
        self.value = value

    def __repr__(self):
        return f"[Value: {self.kind}, {self.value}]"

물론 여기서 만들 프로그래밍 언어는 변수가 명시적인 타입을 가지지는 않습니다. 하지만 a+b와 같은 코드가 숫자끼리의 덧셈이 아닌 경우, 오류로 처리하기 위한 준비입니다. 다시 말해, 각 값의 kind를 검사함으로써 ‘올바른’ 덧셈 외의 코드를 막으려는 것입니다. 이런 오류를 파서가 문법적으로syntactically 확인하기보다는, 값을 평가하는 시점에서 의미적으로semantically 파악하도록 만듭니다.

이번엔 노드를 값으로 평가하는 클래스를 만들 차례입니다. 이것을 만들면 인터프리터가 완성됩니다.

class Evaluator:
    def __init__(self, nodes: list[Node]):
        self.nodes = nodes

    def evaluate(self) -> Value:
        return self.evaluateNode(self.nodes[0])

    def evaluateNode(self, node) -> Value:
        if node.kind == "number":
            return Value("number", node.children[0])

        raise Exception(f"bad node '{node.kind}'")

이 클래스는 평가할 트리로 인스턴스를 만듭니다. 지금은 첫 노드만 평가하도록 만들었지만, 곧 모든 노드로 확장할 것입니다.

이 간단한 인터프리터는 처음에 목표한대로 숫자 값을 평가합니다.

input = "1"
tokens = Tokenizer(input).getTokens()
nodes = Parser(tokens).parse()
evaluated = Evaluator(nodes).evaluate()
print(evaluated)
# result: [Value: number, 1]

변수 대입 평가

대입 연산을 평가하면 변수에 값을 대입하고, 평가 값은 그 대입한 값으로 만들 것입니다. 예를 들어, 다음과 같은 코드를 실행한다고 해봅시다.

a = 1

그러면 대입을 실행하고, 평가 값은 1이 됩니다.

즉 연산 결과는 1과 같이 되지만, 부수 효과side effect로서 a와 같은 식별자는 변수가 되는 것입니다. 이를 변수 바인딩variable binding이라고 부릅니다.

이 변수 바인딩은 소스 코드를 실행하는 도중에 일어납니다. 그래서 어떤 변수 이름이 어떤 값으로 존재하는지 관리할 필요가 있습니다. 이를 위한 자료 구조를 인바이런먼트environment라고 부를 것입니다.

인바이런먼트

인바이런먼트는 a = 1 같은 변수의 대입이 일어날 때 값을 기억합니다. 그리고 a + 2 처럼 변수 이름을 사용할 때 값을 돌려줍니다.

variable binding — 그림 1. 변수 바인딩의 구현. 변수 대입 표현식을 평가하면, 오른쪽처럼 인바이런먼트를 만듭니다. 이후 식별자의 값을 인바이런먼트에서 찾습니다.

지금은 다음과 같이 평범한 해시 테이블hash table로 만듭시다. 변수를 설정하는 메소드 setVar()와 변수 값을 가져오는 메소드 getVar()로 구성합니다.

class Environment:
    def __init__(self):
        self.bindings = dict()

    def getVar(self, name: str) -> Value | None:
        if name in self.bindings:
            return self.bindings[name]

        return None

    def setVar(self, name: str, value: Any) -> None:
        self.bindings[name] = value

변수 바인딩을 위한 준비가 끝났습니다.

변수 대입 구현

이제 대입 연산을 구현해봅시다. 값을 평가하는 메소드가 인바이런먼트를 받도록, 그리고 모든 노드를 평가하도록 고칩니다.

    def evaluate(self) -> Value:
        return self.evaluateNode(self.nodes[0])
    def evaluate(self, env: Environment) -> Value:
        lastEvaluated = Value("null", None)
        for node in self.nodes:
            lastEvaluated = self.evaluateNode(node, env)
        
        return lastEvaluated

평가 결과는 마지막으로 평가한 표현식의 값이 됩니다.

노드를 평가하는 메소드 evaluateNode()는 인바이런먼트를 받습니다. 그리고 식별자와 대입 연산을 평가하기 위해 조건문을 다음과 같이 추가합니다.

    def evaluateNode(self, node) -> Value:
        if node.kind == "number":
            return Value("number", node.children[0])
    def evaluateNode(self, node: Node, env: Environment) -> Value:
        if node.kind == "number":
            return Value("number", node.children[0])
        if node.kind == "identifier":
            return self.evaluateIdentifier(node, env)
        if node.kind == "infix":
            return self.evaluateInfix(node, env)

        raise Exception(f"bad node '{node.kind}'")

식별자 평가를 구현하는 evaluateIdentifier() 메소드는 인바이런먼트에서 변수 값을 가져옵니다. 이 메소드 덕분에 변수 값이 얼마인지 평가할 수 있게 됩니다.

    def evaluateIdentifier(self, node: Node, env: Environment) -> Value:
        name = node.children[0]
        value = env.getVar(name)

        if value is None:
            raise Exception(f"variable '{name}' not found")

        return value

evaluateInfix() 메소드는 대입 연산을 평가하는 evaluateAssignment() 메소드를 부릅니다. 이렇게 분리하는 이유는 사칙연산을 비롯한 다른 것도 나중에 추가할 것이기 때문입니다.

    def evaluateInfix(self, node: Node, env: Environment) -> Value:
        infix = node.children[0]
        left = node.children[1]
        right = node.children[2]

        if infix == "=":
            return self.evaluateAssignment(left, right, env)

        raise Exception(f"bad infix '{infix}'")

다음 메소드는 인바이런먼트에 변수 값을 넣어둡니다. 이 메소드 덕분에 변수 바인딩이 일어나게 됩니다.

    def evaluateAssignment(self, left: Node, right: Node, env: Environment) -> Value:
        value = self.evaluateNode(right, env)

        name = left.children[0]
        env.setVar(name, value)

        return value

이제 변수를 대입하고 사용할 수 있게 됐습니다. 실행 결과는 a+2의 값인 3이 됩니다.

input = "a=1 a+2"
tokens = Tokenizer(input).getTokens()
nodes = Parser(tokens).parse()
evaluated = Evaluator(nodes).evaluate(Environment())
print(evaluated)
# result: [Value: number, 3]

사칙 연산 평가

여기서 사칙 연산은 간단히 구현할 수 있습니다. 트리의 노드를 재귀적으로 방문해 값을 계산하면 되기 때문입니다.

evaluating arithmetic expression — 그림 2. 사칙 연산 구현. 트리를 재귀적으로 방문하며 값으로 평가합니다. 숫자 노드는 가진 값 그대로, 사칙 연산 노드는 자식 노드의 값을 이용해 계산하여 평가합니다.

대입 연산을 평가하는 부분에 사칙 연산의 경우를 추가합니다.

    def evaluateInfix(self, node: Node, env: Environment) -> Value:
        # ...

        if infix == "=":
            return self.evaluateAssignment(left, right, env)
        if infix in "+-*/": 
            return self.evaluateArithmetic(infix, left, right, env) 

        # ...

사칙 연산을 실제로 수행하는 부분에서는 자식 노드를 재귀적으로 평가해 값을 가져옵니다.

    def evaluateArithmetic(self, infix: str, left: Node, right: Node, env: Environment) -> Value:
        evalLeft = self.evaluateNode(left, env)
        evalRight = self.evaluateNode(right, env)

        if evalLeft.kind != "number":
            raise Exception(f"bad left value '{evalLeft.kind}")
        if evalRight.kind != "number":
            raise Exception(f"bad right value '{evalRight.kind}")

        if infix == "+":
            return Value("number", evalLeft.value + evalRight.value)
        if infix == "-":
            return Value("number", evalLeft.value - evalRight.value)
        if infix == "*":
            return Value("number", evalLeft.value * evalRight.value)
        if infix == "/":
            return Value("number", evalLeft.value / evalRight.value)

        raise Exception(f"bad infix '{infix}'")

이를 통해 인터프리터는 사칙 연산도 가능해졌습니다.

input = "1+2*3/4-5"
tokens = Tokenizer(input).getTokens()
nodes = Parser(tokens).parse()
evaluated = Evaluator(nodes).evaluate(Environment())
print(evaluated)
# result: [Value: number, -2.5]

함수 정의 평가

함수 정의 표현식은 다음과 같은 문법이었습니다.

f = b -> a+b

여기서 만드는 언어는 함수도 값이므로, 함수 값을 구현할 필요가 있습니다. 이 함수 값은 나중에 f(2)와 같은 함수 호출이 사용할 것입니다.

function definition and call — 그림 3. 함수의 정의와 호출 구현. `b -> a+b`와 같은 함수 정의는 매개변수와 본문, 인바이런먼트를 가지는 함수 값으로 평가됩니다. `f(2)`와 같은 함수 호출은 이 함수 값에 있는 매개변수 식별자 `b`에 호출 인자 `2`를 바인딩하여 함수 인바이런먼트를 만들고, 기존 함수의 인바이런먼트를 상위로 둡니다. 이를 바탕으로 함수 본문 `a+b`가 평가됩니다.

예시의 a+b와 같은 함수 본문은 호출 시에 평가됩니다. 그리고 b와 같은 함수의 매개변수parameter 또한, 함수 호출 시 2와 같은 호출 인자argument의 값으로 바인딩이 일어날 것입니다. 여기서 매개변수와 호출 인자를 구분해 부르고 있다는 점을 참고하세요.

한편, 이후 구현할 클로저를 위해, 함수가 현재의 인바이런먼트를 기억해야할 필요가 있습니다. 정리하면, 함수 값은 매개변수와 본문, 그리고 인바이런먼트를 가지는 것입니다.

class FunctionValue:
    def __init__(self, param: Any, body: Node, env: Environment):
        self.param = param
        self.body = body
        self.env = env

    def __repr__(self):
        return f"[Function: {self.param} -> ...]"

이번엔 함수 정의를 함수 값으로 평가하도록 만들 차례입니다. 먼저 함수 정의도 사칙연산과 같은 연산자로 처리합니다.

    def evaluateInfix(self, node: Node, env: Environment) -> Value:
        # ...

        if infix in "+-*/":
            return self.evaluateArithmetic(infix, left, right, env)
        if infix == "->": 
            return self.evaluateFunction(left, right, env) 

        # ...

실제 함수 값을 평가하는 메소드는 방금 만들었던 함수 값 인스턴스를 리턴합니다.

    def evaluateFunction(self, left, right, env):
        param = left.value
        body = right

        return Value("function", FunctionValue(param, body, env))

이제 인터프리터가 함수 값을 평가할 수 있게 됐습니다.

input = "a->b"
tokens = Tokenizer(input).getTokens()
nodes = Parser(tokens).parse()
evaluated = Evaluator(nodes).evaluate(Environment())
print(evaluated)
# result: [Value: function, [Function: a -> ...]]

함수 호출 평가

함수 호출은 호출 인자로 넘긴 값으로 새로운 인바이런먼트를 만들고, 함수 호출이 끝나면 버릴 것입니다. 새로운 인바이런먼트란 곧 변수를 기억하는 새로운 공간이므로, 변수의 새로운 스코프scope를 만든다고 할 수 있습니다. 여기서 만드는 언어는 함수 단위로 스코프가 생깁니다.

그러면 Environment 클래스를 고쳐서, 기존 인바이런먼트를 확장할 수 있도록 만들어봅시다. 이를 통해 인바이런먼트는 단방향 링크드 리스트singly linked list로 연결될 것입니다. 이 중에 시작 노드에 가까울 수록 더 중첩된 스코프 역할을 맡게 됩니다.

class Environment:
    def __init__(self): 
        self.bindings = dict() 
    def __init__(self, super = None): 
        self.super = super
        self.bindings = dict() 

    def getVar(self, name: str):
        if name in self.bindings:
            # ...

        if self.super is not None: 
            return self.super.getVar(name) 

        # ...

getVar() 메소드는 현재 인바이런먼트에서 값을 찾고, 없으면 상위 인바이런먼트에서 시도합니다. 다시 말해, 바깥쪽 스코프에서 찾아보는 것입니다. 이 메소드는 재귀적으로 호출되어 맨 위에 있는 인바이런먼트까지 탐색합니다.

이를 통해 함수 호출 평가를 구현해봅시다.

    def evaluateNode(self, node: Node, env: Environment) -> Value:
        # ...
        if node.kind == "identifier":
            return self.evaluateIdentifier(node, env)
        if node.kind == "call": 
            return self.evaluateCall(node, env) 

        raise Exception(f"bad node '{node.kind}'")

실제로 평가를 맡는 메소드 evaluateCall()은 기존 인바이런먼트에서 함수 매개변수의 바인딩을 추가한 새 인바이런먼트를 만들 것입니다.

    def evaluateCall(self, node: Node, env: Environment) -> Value:
        func = self.evaluateNode(node.children[0], env)
        arg = self.evaluateNode(node.children[1], env)

        funcEnv = func.value.env
        funcParam = func.value.param
        funcBody = func.value.body

        extendedEnv = Environment(funcEnv)
        extendedEnv.setVar(funcParam, arg)

        value = self.evaluateNode(funcBody, extendedEnv)
        return value

즉 ‘그림 3’에서 보았던 것처럼, b를 매개변수로 갖는 함수를 f(2)로 호출하면, 변수 b에 호출 인자 2를 바인딩한 인바이런먼트를 새로 만듭니다.

인터프리터가 함수 호출을 할 수 있게 됐습니다.

input = "f = a -> a+1 f(2)"
tokens = Tokenizer(input).getTokens()
nodes = Parser(tokens).parse()
evaluated = Evaluator(nodes).evaluate(Environment())
print(evaluated)
# result: [Value: number, 3]

변수 섀도잉

앞서 구현한 대로, 식별자를 평가할 때 변수 값을 찾기 위해 먼저 현재 인바이런먼트에서 찾아보고, 없으면 상위 인바이런먼트에서 찾아봅니다.

그런데 동일한 식별자가 다음 코드처럼 여러 레벨의 인바이런먼트에 걸쳐 존재할 수 있습니다.

a = 1
f = a -> a+1

여기서 함수 f의 매개변수 a와 기존에 만든 변수 a는 이름은 같지만 다른 변수로 만들어집니다. 함수의 매개변수 a가 기존의 변수 a를 ‘가린다’고 볼 수 있기 때문에 변수 섀도잉variable shadowing이라고 부릅니다. 이 특징은 사실 파이썬을 비롯한 많은 프로그래밍 언어가 갖고 있는 것이기도 합니다.

정리하면 변수 섀도잉은 변수 값을 인바이런먼트에서 찾는 방식, 즉 상위보다 현재의 인바이런먼트에서 먼저 찾는 순서로 인해 생기는 특징으로 볼 수 있습니다.

커링

여기까지 만들었다면, 자연스럽게 커링도 구현되어있습니다.

f = a -> b -> a+b
f(1)(2)

입력 코드의 함수 정의는 사실상 두 개의 함수를 정의한 것이고, 따라서 호출 또한 두 번 이루어진 것입니다. 하지만 마치 두 개의 매개변수를 쓰는 함수로 다룰 수 있습니다. 이런 함수를 커리된 함수curried function라고 부릅니다.

정말로 구현됐는지 확인해보면 다음과 같은 결과가 나옵니다.

input = "f = a -> b -> a+b  f(1)(2)"
tokens = Tokenizer(input).getTokens()
nodes = Parser(tokens).parse()
evaluated = Evaluator(nodes).evaluate(Environment())
print(evaluated)
# result: [Value: number, 3]

이런 커링의 구현은 클로저 덕분에 가능한 것입니다.

클로저

커링의 예시 코드에서 함수 호출 f(1)(2) 대신 두 부분으로 나눠서 보면, 무슨일이 일어나고 있는지 좀 더 분명하게 볼 수 있습니다.

f = a -> b -> a+b
g = f(1)
g(2)

함수 정의 표현식 a -> b -> a+b은 호출 시 함수를 만들어줍니다. 즉 매개변수 a로 새 함수 b -> a+b를 만드는 것입니다. 따라서 변수 g에는 f(1)를 평가한 값으로서, 함수 b -> 1+b를 갖게 됩니다. 다시 말해, 이 함수 값은 본문이 b -> a+b이고, a는 1로 바인딩된 인바이런먼트를 가집니다.

이런식으로 함수의 인바이런먼트에 함수 본문 바깥의 변수 a를 담을 수 있게 됩니다. 그리고 이런 함수를 클로저라고 부릅니다. 재밌는 점은 함수 외부에서 변수 a에 접근할 방법이 없다는 것입니다. 이렇게 클로저는 일종의 프라이빗private 변수를 가졌다고 볼 수 있습니다. 이 경우 클로저가 변수 a를 캡처capture했다고 말합니다.

closure — 그림 5. 클로저 구현. 변수 `f`에 함수를 만드는 함수를 정의합니다. 따라서 이 함수를 호출하면 새 함수가 만들어집니다. 이 때 새 함수 값은 확장된 인바이런먼트를 가지고, 이는 외부에서 접근할 수 없게 됩니다.

이제 함수 호출 g(2)가 함수 본문 a+b를 평가할 때, 변수 a의 값은 클로저의 인바이런먼트에서 1을, 변수 b는 호출 인자로 넘긴 값에서 2를 가져오게 됩니다.

예시를 인터프리터로 실행해보면 커링의 예시와 똑같은 결과가 나옵니다.

input = "f = a -> b -> a+b  g = f(1)  g(2)"
tokens = Tokenizer(input).getTokens()
nodes = Parser(tokens).parse()
evaluated = Evaluator(nodes).evaluate(Environment())
print(evaluated)
# result: [Value: number, 3]

REPL 만들기

여기까지 인터프리터는 사실상 완성됐습니다. 그런데 여기서 한단계 더 나아가 REPL을 만들 수 있습니다. REPL이란 Read-Evaluate-Print Loop으로, 코드를 그때그때 입력받아 실행하는 프로그램입니다. 파이썬을 비롯한 많은 인터프리터에서 지원하는 것이기도 합니다.

REPL에서는 만들어둔 변수를 앞으로도 계속 쓸 수 있어야 합니다. 따라서 REPL이 새 인바이런먼트와 함께 초기화 되도록 만듭니다.

class Repl:
    def __init__(self):
        self.env = Environment()

    def execute(self, input: str) -> Any:
        tokens = Tokenizer(input).getTokens()
        nodes = Parser(tokens).parse()
        evaluated = Evaluator(nodes, self.env).evaluate()
        return evaluated.value

execute() 메소드는 입력받은 코드 input을 실행합니다. 첫 글에서 인터프리터의 수도코드를 다음과 같이 소개했는데, 이 메소드는 그 수도코드의 구현이기도 합니다.

인터프리터 (코드)

토큰 $\leftarrow$ 토큰화(코드)

문법 트리 $\leftarrow$ 파싱(토큰)

값 $\leftarrow$ 평가(문법 트리)

리턴 값

이제 REPL은 다음과 같이 구현합니다. quit을 입력하면 종료를, 아니면 코드를 실행합니다.

    def run(self) -> None:
        print("to quit, type 'quit'")

        repl = Repl()

        while True:
            try:
                print("> ", end="", flush=True)

                line = stdin.readline().strip()
                if line == "quit":
                    print("bye")
                    break

                print(self.execute(line))
            except Exception as e:
                print(e)

그리고 다음과 같이 인스턴스를 만들어 실행하면 완성입니다.

repl = Repl()
repl.run()

그러면 첫 글에서 목표로 했던 코드를 여기서 실행할 수 있게 됩니다.

to quit, type 'quit'
> g = 98/10
9.8
> y = t -> y0 -> g*t*t/2 + y0
[Function: t -> ...]
> y(10)(5)
495.0
> quit
bye

드디어 간단한 함수형 프로그래밍 언어가 완성되었습니다.

마치며

소스 코드를 토큰화tokenize하는 것부터 시작해, 파서, 그리고 인터프리터를 만들었습니다. 간단한 사칙 연산과 함수 호출만 구현할 수 있을 정도의 프로그래밍 언어를 만들었지만, 여기에 조건문이나 반복문과 같은 기능도 비슷하게 추가할 수 있습니다.

클로저를 간단히 만들 수 있었던 이유는, 구현을 위해 사용한 파이썬에 이미 가비지 컬렉션garbage collection이 구현되어 있기 때문입니다. 구현 과정에서는 인바이런먼트를 새로 만든 뒤 해제release하는 메모리 관리가 따로 없었고, 덕분에 인터프리터의 구현이 간단해졌습니다. 이것이 파이썬을 선택한 이유이기도 합니다.

인바이런먼트라는 데이터 구조는 자바스크립트JavaScript 언어에서도 렉시컬 인바이런먼트lexical environment라는 이름으로 등장합니다. 자바스크립트 또한 클로저가 구현되어있는 언어이기도 합니다.

여기까지 생략된 부분을 포함한 코드는 지스트Gist에서 볼 수 있습니다.

레퍼런스

Writing An Interpreter In Go (Thorsten Ball, 2020), 또는 밑바닥부터 만드는 인터프리터 in Go (2021)
Learn You a Haskell for Great Good! (Miran Lipovaca, 2011), 또는 가장 쉬운 하스켈 책 (2014): 함수형 프로그래밍 언어를 사용해봄으로써 커링과 클로저같은 개념을 접해볼 수 있습니다. 이 책은 그런 대표적인 언어 중 하나인 하스켈Haskell을 소개합니다.