게스트 포스트: RPython 인터프리터에서의 파이널 인코딩

소개¶

이 글은 작은 RPython 인터프리터를 다소 비전형적인 스타일로 다시 작성해 본 최근 실험을 간단히 정리하는 메모에서 출발했습니다. 이미 RPython으로 무언가를 작성해 본 독자들이 인터프리터 아키텍처를 더 깊게 들여다보는 데를 목표로 합니다.

일부 실험은 문제의 해법을 찾는 데 초점을 둡니다. 이번 실험은 이미 잘 알려진 해법을 RPython 문맥에 적용해 새로운 접근을 모색합니다. 보시다시피 기능이나 인터프리터의 분기 수가 실제로 바뀌진 않습니다. 마치 내골격과 외골격을 비교하는 것처럼, 동등한 뼈대와 판을 다른 배치로 배열하는 일에 가깝습니다.

개요¶

어떤 프로그래밍 언어를 위한 RPython 인터프리터는 보통 다음 일을 순서대로 세 가지 혹은 네 가지 수행합니다.

1. 입력 프로그램을 읽고 파싱한다
2. 구문(콘크리트) 트리를 추상 구문으로 인코딩한다
3. 선택적으로, 추상 구문을 최적화하거나 축약한다
4. 추상 구문을 평가한다: 입력을 읽고, 계산하고, 출력한다 등

오늘은 추상 구문에 집중합니다. 대부분의 언어는 구문 트리(콘크리트 파스 트리)를 갖고, 이를 추상 구문 트리(AST)로 쉽게 추상화할 수 있습니다. AST는 보통 초기(Initial) 인코딩으로 표현됩니다. 초기 인코딩은 동일한 AST에 대해 다른 어떤 인코딩으로도 변환 가능하며, 클래스 계층처럼 보이고, 힙의 정적 구조로 구현됩니다.

이에 반해 최종(Final) 인코딩도 존재합니다. 최종 인코딩은 다른 어떤 인코딩으로부터도 변환 가능하며, 인터프리터의 동작을 위한 인터페이스처럼 보이고, 스택 위에서 전개(unwinding)되는 구조로 구현됩니다. RPython 관점에서 보면, os나 sys 같은 파이썬 내장 모듈은 운영체제 기능에 대한 최종 인코딩입니다. 번역 전/후의 내부 구현은 다르지만, 그 기능에 접근하는 데 쓰는 인터페이스는 변하지 않습니다.

RPython에서 초기 인코딩은 클래스 계층으로 구성됩니다. 각 클래스는 콘크리트 파스 트리의 파서 생성 규칙에 대응하는 트리 노드의 종류를 나타냅니다. 각 클래스 인스턴스는 개별 트리 노드를 나타내죠. 클래스의 필드, 특히 .__init__()에서 채워지는 필드는 각 노드의 사전 계산된 속성을 저장합니다. 메서드는 필요 시 노드 속성을 계산하는 데 쓰입니다. 이는 분명하고 간단해 보입니다. 그럼 다른 접근은 무엇이 있을까요? 예제가 필요합니다.

Brainfuck의 파이널 인코딩¶

간단하지만 튜링 완전한 언어인 Brainfuck을 살펴봅시다. 예를 들어 다음 프로그램이 있습니다.

[-]

이 프로그램은 루프와 디크리먼트로 구성되며, 한 셀을 0으로 설정합니다. Brainfuck의 대수적 의미론을 따르는 초기 인코딩에서는, 힙 위에 구조를 만들기 위해 클래스 생성자를 적용해 다음과 같이 표현할 수 있습니다.

Loop(Plus(-1))

최종 인코딩도 비슷하지만, 클래스 생성자는 메서드로 대체되고, 구조는 스택 위에서 만들어지며, 클래스의 선택을 매개변수화합니다.

lambda cls: cls.loop(cls.plus(-1))

일반 파이썬에서는 둘 사이의 변환이 사소하며, 적절한 클래스를 전달하는 문제에 가깝습니다. 실제로 초기와 최종 인코딩은 동등합니다. 이 사실은 뒤에서 다시 언급하겠습니다. 다만 RPython에서는 모든 타입이 일치해야 하고, 클래스는 번역 전(compile-time)에 결정되어야 합니다. 우리는 나중에 몇 가지 RPython 기법으로 최종 인코딩을 단형화(monomorphize)해야 합니다. 그 전에, 최종 인코딩의 모든 어려움을 다루기 위해 실제 Brainfuck 인터페이스가 어떤 모습인지 먼저 봅시다.

시작하기 전에, 로컬 코드가 cls가 무엇인지 모른다는 점을 기억하세요. 임의의 의미론적 도메인을 타입 안정하게 들여다볼 방법이 없습니다. 초기 인코딩된 버전에서는 isinstance(bf, Loop)로 AST 노드가 루프인지 확인할 수 있지만, 최종 인코딩된 AST에는 이에 상응하는 것이 없습니다. 따라서 묵시적 과제가 있습니다. 임의의 의미론적 도메인에서 프로그램을 어떻게 평가할까요? 보너스로, AST 노드의 타입을 들여다보지 않고 프로그램을 어떻게 최적화할 수 있을까요?

아래는 지정된 리비전의 이 모듈을 해부한 내용입니다. 먼저 전체 인터프리터를 위에서 아래로 쭉 읽어보는 것도 좋습니다. 300줄이 채 되지 않습니다.

핵심 기능¶

파이널 인코딩은 인터페이스의 메서드로 주어집니다. 다음 다섯 메서드는 Brainfuck 대수의 항(합)과 정확히 대응합니다.

python
class BF(object):
    # 다른 메서드는 생략
    def plus(self, i): pass
    def right(self, i): pass
    def input(self): pass
    def output(self): pass
    def loop(self, bfs): pass

.loop() 메서드가 또 다른 프로그램을 인자로 받는다는 점에 주목하세요. 초기 인코딩된 AST는 클래스 인스턴스의 필드로 다른 초기 인코딩된 AST를 갖습니다. 반면 최종 인코딩된 AST는 인터페이스 메서드의 매개변수로 다른 최종 인코딩된 AST를 받습니다. RPython은 모든 타입을 추론하므로, 독자는 i는 보통 정수이고 bfs는 Brainfuck 연산들의 시퀀스라는 것을 알고 있어야 합니다.

우리는 이 기능을 클래스에 구현합니다. 나중에는, 타입 문제를 피하기 위해 이 클래스를 상위 클래스가 아니라 믹스인으로 취급할 것입니다.

모노이드¶

입력 프로그램을 최적화하려면, Brainfuck 프로그램의 모노이드 구조를 표현해야 합니다. 이를 위해 다음 모노이드 시그니처를 추가합니다.

python
class BF(object):
    # 다른 메서드는 생략
    def unit(self): pass
    def join(self, l, r): pass

이는 기술적으로 단위원 마그마(unital magma)입니다. RPython은 대수적 법칙을 지원하지 않지만, 나중에 최적화 단계에서 대수 법칙을 강제할 것입니다. 또한 자유 모노이드는 리스트라는 잘 알려진 민담(?)을 활용해, 호출자가 동작의 리스트를 전달하면 재귀로 축약할 수 있게 합니다.

python
class BF(object):
    # 다른 메서드는 생략
    def joinList(self, bfs):
        if not bfs: return self.unit()
        elif len(bfs) == 1: return bfs[0]
        elif len(bfs) == 2: return self.join(bfs[0], bfs[1])
        else:
            i = len(bfs) >> 1
            return self.join(self.joinList(bfs[:i]), self.joinList(bfs[i:]))

.joinList()는 구현이 약간 번거롭지만, 위르트의 원칙이 적용됩니다. 이 메서드가 있을 때 인터프리터가 더 짧습니다.

관용구¶

마지막으로, 인터페이스에는 앞서 본 제로 프로그램 같은 몇 가지 고수준 관용구가 포함됩니다. 초기 인코딩이라면 모듈 전역 함수로 정의할 수 있겠지만, 여기서는 믹스인 클래스 BF 위에 정의합니다.

python
class BF(object):
    # 다른 메서드는 생략
    def zero(self): return self.loop(self.plus(-1))
    def move(self, i): return self.scalemove(i, 1)
    def move2(self, i, j): return self.scalemove2(i, 1, j, 1)
    def scalemove(self, i, s):
        return self.loop(self.joinList([
            self.plus(-1), self.right(i), self.plus(s), self.right(-i)]))
    def scalemove2(self, i, s, j, t):
        return self.loop(self.joinList([
                self.plus(-1), self.right(i), self.plus(s), self.right(j - i),
                self.plus(t), self.right(-j)]))

인터페이스 지향 아키텍처¶

인터페이스 적용¶

이제 RPython의 객체 모델을 한바탕 해킹해 번역이 되도록 만들어 봅니다. 먼저, pretty-printing 작업을 생각해 봅시다. Brainfuck의 경우 입력 프로그램을 파이썬 문자열로 그대로 토해내면 충분합니다.

python
class AsStr(object):
    import_from_mixin(BF)
    def unit(self): return ""
    def join(self, l, r): return l + r
    def plus(self, i): return '+' * i if i > 0 else '-' * -i
    def right(self, i): return '>' * i if i > 0 else '<' * -i
    def loop(self, bfs): return '[' + bfs + ']'
    def input(self): return ','
    def output(self): return '.'

rlib.objectmodel.import_from_mixin을 통해 반환 타입의 공변성을 두고 스트레스를 받을 필요가 없습니다. 대신, 자바식의 클래스/객체 관점에서 OCaml식의 사전 구축된 클래스/생성자 관점으로 전환합니다. AsStr는 단형이며, 이를 호출하는 측은 공변성을 스스로 만들어야 합니다. 예를 들어 파싱 함수의 첫 줄은 다음과 같습니다.

python
@specialize.argtype(1)
def parse(s, domain):
    ops = [domain.unit()]
    # 독자의 집중력을 위해 파서 본문은 생략

rlib.objectmodel.specialize.argtype를 호출함으로써 의미론적 도메인의 선택에 따라, 호출 지점당 최대 한 번씩 파싱 함수의 사본을 만들게 됩니다. Oleg은 이를 "symantics"라 부르지만, 저는 코드에서는 "domain(도메인)"을 선호합니다. 또한 파싱 스택이 모노이드의 항등원으로 시작하는 점에 주목하세요. 이는 빈 입력 문자열에 대응하며, 파서는 모노이드 결합을 반복적으로 사용해 파싱된 표현식을 그 내부를 들여다보지 않고도 구축합니다. 예를 조금 보겠습니다.

python
while i < len(s):
    char = s[i]
    if char == '+': ops[-1] = domain.join(ops[-1], domain.plus(1))
    elif char == '-': ops[-1] = domain.join(ops[-1], domain.plus(-1))
    # 이하 유사

독자가 당황하는 것이 정당할 수 있습니다. 이 마법 같은 애너테이션을 붙이지 않으면 무엇이 깨질까요? 번역기가 저수준 타입이 맞지 않아 UnionError를 던집니다. RPython은 parse() 같은 함수의 저수준 표현을 단 하나만 만들고 싶어하며, 각 사본은 단형의 기계어로 컴파일됩니다. 이 인터프리터에서는 최적화된 문자열로의 파싱과 평가기로의 파싱을 모두 지원하려면 parse()의 두 사본이 필요합니다. 처음엔 완전히 이해하지 못해도 괜찮습니다.

인터페이스 합성¶

앞서, 인터프리터가 파싱 후 입력 프로그램을 선택적으로 최적화할 수 있다고 했습니다. 이를 지원하기 위해, 임의의 도메인 앞에 피프홀 최적화기를 전합성(precompose)하겠습니다. 파서를 뒤에 후합성(postcompose)할 수도 있지만 더 어려워 보입니다. 핵심 부분은 다음과 같습니다.

python
def makePeephole(cls):
    domain = cls()
    def stripDomain(bfs): return domain.joinList([t[0] for t in bfs])
    class Peephole(object):
        import_from_mixin(BF)
        def unit(self): return []
        def join(self, l, r): return l + r
        # 실제 정의는... 잠시 뒤에...
    return Peephole, stripDomain

아직 실제 최적화는 걱정하지 마세요. 여기서 중요한 것은 의미론적 도메인의 초기화 패턴입니다. makePeephole은 의미론적 도메인에 대한 SML 스타일의 펑터입니다. Brainfuck의 최종 인코딩을 입력받아, 최적화를 내장한 또 다른 Brainfuck의 최종 인코딩을 만들어냅니다. 보조 함수 stripDomain은 번역 시점에 전달된 기반 cls로 최적화기의 도메인에서 추출을 수행하는 파이널라이저입니다. 예를 들어, pretty-printing을 최적화해 보겠습니다.

python
AsStr, finishStr = makePeephole(AsStr)

이제 힙에 AST를 만들지 않고도, 단 한 줄로 파싱하고 최적화된 AST를 출력 문자열로 만들 수 있습니다. 엄밀히 말하면 출력 문자열 조각들은 힙에 할당될 것이지만, AST의 노드 구조는 오직 스택에만 할당됩니다. 덤으로, 파서는 악의적인 입력이 스택 오버플로를 유발하지 않도록 작성되어 있으며, 그 때문에 루프 안에서 중간 연산들의 RPython 리스트를 힙에 유지해야 합니다.

python
print finishStr(parse(text, AsStr()))

성능¶

그런데 빠를까요? 네. 초기 인코딩을 쓰던 이전 버전보다 빠르고, Andrew Brown의 고전적 버전(1부, 2부)보다도 빠릅니다. Brown의 인터프리터는 큰 최적화를 수행하지 않으므로, 여기서는 최종 인코딩이 어떻게 초기 인코딩을 능가하는지에 집중하겠습니다.

JIT¶

먼저, 같은 인터프리터를 초기 인코딩으로 썼을 때보다 왜 더 빠를까요? 사실 JIT의 관점에서는 여전히 초기 인코딩이 있기 때문입니다! 개별 동작을 구현하는 서브클래스 계층을 가진 Op 클래스가 존재합니다. 진지한 태글리스-파이널 수련자나, Stop Writing Classes (2012, Pycon US)를 기억하는 분은 다음 클래스들이 그냥 평범한 함수일 수 있음을 알아차릴 것입니다. 이 클래스들은 RPython이 클로저가 있는 람다를 지원하지 않기 때문에 치르는 양보이지, 초기 인코딩을 위한 것이 아닙니다. 우리는 어떤 Op도 직접 타입검사하지 않지만, JIT는 어차피 타입가드를 생성하므로, 사실상 각 JIT 트레이스에 완전히 승격(promote)된 AST가 인라인됩니다. 먼저 간단한 동작들입니다.

python
class Op(object):  _immutable_  = True

class _Input(Op):
     _immutable_  = True
    def runOn(self, tape, position):
        tape[position] = ord(os.read(0, 1)[0])
        return position
Input = _Input()

class _Output(Op):
     _immutable_  = True
    def runOn(self, tape, position):
        os.write(1, chr(tape[position]))
        return position
Output = _Output()

class Add(Op):
     _immutable_  = True
     _immutable_fields_  = "imm",
    def  __init__ (self, imm): self.imm = imm
    def runOn(self, tape, position):
        tape[position] += self.imm
        return position

JIT가 이전보다 정보가 적긴 합니다. 불변 연산의 시퀀스가 언롤링(unrolling)할 가치가 있을 만큼 충분히 불변임을 더는 스스로 알지 못합니다. 하지만 약간의 rlib.jit.unroll_safe로 보완할 수 있습니다.

python
class Seq(Op):
     _immutable_  = True
     _immutable_fields_  = "ops[*]",
    def  __init__ (self, ops): self.ops = ops
    @unroll_safe
    def runOn(self, tape, position):
        for op in self.ops: position = op.runOn(tape, position)
        return position

마지막으로, JIT 진입점은 이전 인터프리터들과 마찬가지로 각 루프의 헤드에 있습니다. Brainfuck은 루프 중간 점프를 지원하지 않으므로, 합류 지점을 루프 헤드로만 제한해도 불이익이 없습니다.

python
class Loop(Op):
     _immutable_  = True
     _immutable_fields_  = "op",
    def  __init__ (self, op): self.op = op
    def runOn(self, tape, position):
        op = self.op
        while tape[position]:
            jitdriver.jit_merge_point(op=op, position=position, tape=tape)
            position = op.runOn(tape, position)
        return position

여기까지가 묵시적 과제의 끝입니다. 비밀은 없습니다. 그냥 AST를 평가하면 됩니다. 아래는 평가를 위한 의미론적 도메인의 일부와 이를 최적화하는 "펑터"입니다. 인터프리터 전체에서 오직 AsOps.join() 안에만 isinstance() 호출이 등장합니다! 이는 받아들일 수 있는데, Seq가 사실상 RPython 리스트를 싸는 타입 래퍼이기 때문입니다. 즉, 연산들의 리스트도 하나의 연산입니다. 그 리스트는 초기 인코딩되어 있고, 따라서 관찰 가능합니다.

python
class AsOps(object):
    import_from_mixin(BF)
    def unit(self): return Shift(0)
    def join(self, l, r):
        if isinstance(l, Seq) and isinstance(r, Seq):
            return Seq(l.ops + r.ops)
        elif isinstance(l, Seq): return Seq(l.ops + [r])
        elif isinstance(r, Seq): return Seq([l] + r.ops)
        return Seq([l, r])
    # 다른 메서드는 생략!

AsOps, finishOps = makePeephole(AsOps)

그리고 마지막으로, 입력 프로그램을 평가하는 실제 최상위 코드는 다음과 같습니다. 앞서처럼, 모든 것이 합성되고 나면 실제 호출은 단 한 줄이면 됩니다.

python
tape = bytearray("\x00" * cells)
finishOps(parse(text, AsOps())).runOn(tape, 0)

피프홀 최적화¶

우리의 피프홀 최적화기는 한 명령어의 룩어헤드/리라이트 버퍼를 가진 추상 인터프리터입니다. 이는 앞서 언급한 Brainfuck 모노이드의 대수 법칙을 구현합니다. 또한 루프에 대한 관용구 인식도 구현합니다. 먼저 추상 인터프리터부터 보겠습니다. 추상 도메인은 여섯 개의 원소를 가집니다.

python
class AbstractDomain(object): pass
meh, aLoop, aZero, theIdentity, anAdd, aRight = [AbstractDomain() for _ in range(6)]

또한 모든 것에 정수를 태그로 붙여 anAdd나 aRight를 정밀한 주석(주해)으로 만들겠습니다. 이것이 바로 실제 Peephole.join() 메서드입니다.

python
def join(self, l, r):
    if not l: return r
    rv = l[:]
    bfHead, adHead, immHead = rv.pop()
    for bf, ad, imm in r:
        if ad is theIdentity: continue
        elif adHead is aLoop and ad is aLoop: continue
        elif adHead is theIdentity:
            bfHead, adHead, immHead = bf, ad, imm
        elif adHead is anAdd and ad is aZero:
            bfHead, adHead, immHead = bf, ad, imm
        elif adHead is anAdd and ad is anAdd:
            immHead += imm
            if immHead: bfHead = domain.plus(immHead)
            elif rv: bfHead, adHead, immHead = rv.pop()
            else:
                bfHead = domain.unit()
                adHead = theIdentity
        elif adHead is aRight and ad is aRight:
            immHead += imm
            if immHead: bfHead = domain.right(immHead)
            elif rv: bfHead, adHead, immHead = rv.pop()
            else:
                bfHead = domain.unit()
                adHead = theIdentity
        else:
            rv.append((bfHead, adHead, immHead))
            bfHead, adHead, immHead = bf, ad, imm
    rv.append((bfHead, adHead, immHead))
    return rv

이게 훨씬 더 길어졌다면 DSL을 구현하는 것이 가치가 있었을 텐데, 이 정도면 인라인하기에 충분히 짧습니다. 추상 해석은 결합의 좌변 전체에 대해(마지막 명령을 제외하고) 귀납적으로 가정됩니다. 마지막 명령은 리라이트 레지스터에 적재됩니다. 우변의 각 명령은 정확히 한 번씩만 조사됩니다. anAdd 다음 anAdd, 그리고 aRight 다음 aRight의 로직이 정확히 동일한 이유는, 둘 모두 정수로 주어진 아벨 군을 기반으로 하기 때문입니다. 리라이트 레지스터는 theIdentity를 소거하기 위해 좌변으로 주의 깊게 푸시/팝됩니다. theIdentity 자체는 0인 anAdd 또는 aRight에 대한 통합자(unifier)일 뿐입니다.

우리가 많은 가비지를 만든다는 점에 주목하세요. 예를 들어, + 문자로 이뤄진 길이 _n_의 문자열을 파싱하면, 피프홀 최적화기는 domain.plus(1)부터 domain.plus(n)까지, 기저 domain.plus() 동작의 인스턴스를 _n_개 할당합니다. 예전의 초기 인코딩 버전은 해시 콘싱(hash consing)을 사용해 루프조차도 동일 연산을 두 번 이상 만들지 않도록 했습니다. 최소한 Brainfuck을 파싱 중에 점진적으로 최적화하는 문맥에서는, 입력을 반복적으로 해시하고 변경 가능한 해시 테이블을 탐색하는 것보다, 불변 가비지를 많이 생성하는 편이 더 효율적인 것으로 보입니다.

마지막으로 관용구 인식을 봅시다. RPython 리스트는 초기 인코딩되어 있으므로, 리스트 길이에 따라 디스패치한 뒤 각 동작의 추상 도메인을 관찰할 수 있습니다.

python
def isConstAdd(bf, i): return bf[1] is anAdd and bf[2] == i

def oppositeShifts(bf1, bf2):
    return bf1[1] is bf2[1] is aRight and bf1[2] == -bf2[2]

def oppositeShifts2(bf1, bf2, bf3):
    return (bf1[1] is bf2[1] is bf3[1] is aRight and
            bf1[2] + bf2[2] + bf3[2] == 0)

def loop(self, bfs):
    if len(bfs) == 1:
        bf, ad, imm = bfs[0]
        if ad is anAdd and imm in (1, -1):
            return [(domain.zero(), aZero, 0)]
    elif len(bfs) == 4:
        if (isConstAdd(bfs[0], -1) and
            bfs[2][1] is anAdd and
            oppositeShifts(bfs[1], bfs[3])):
            return [(domain.scalemove(bfs[1][2], bfs[2][2]), aLoop, 0)]
        if (isConstAdd(bfs[3], -1) and
            bfs[1][1] is anAdd and
            oppositeShifts(bfs[0], bfs[2])):
            return [(domain.scalemove(bfs[0][2], bfs[1][2]), aLoop, 0)]
    elif len(bfs) == 6:
        if (isConstAdd(bfs[0], -1) and
            bfs[2][1] is bfs[4][1] is anAdd and
            oppositeShifts2(bfs[1], bfs[3], bfs[5])):
            return [(domain.scalemove2(bfs[1][2], bfs[2][2],
                                       bfs[1][2] + bfs[3][2],
                                       bfs[4][2]), aLoop, 0)]
        if (isConstAdd(bfs[5], -1) and
            bfs[1][1] is bfs[3][1] is anAdd and
            oppositeShifts2(bfs[0], bfs[2], bfs[4])):
            return [(domain.scalemove2(bfs[0][2], bfs[1][2],
                                       bfs[0][2] + bfs[2][2],
                                       bfs[3][2]), aLoop, 0)]
    return [(domain.loop(stripDomain(bfs)), aLoop, 0)]

이로써 보너스 질문이 끝났습니다. 알려지지 않은 의미론적 도메인을 어떻게 최적화할까요? 도메인의 원소를 기술하는 추상 컨텍스트를 유지해야 합니다. 초기 인코딩에서는 AST에게 스스로를 묻습니다. 최종 인코딩에서는 AST에 관해 필요한 모든 것을 이미 알고 있습니다.

세심한 독자는 JIT 절두에서 처음 질문에 제대로 답하지 않았다는 것을 눈치챌 수 있습니다. JIT가 이전과 동일한 연산들을 여전히 대상으로 삼기 때문에, 더 느릴 이유는 없습니다. 하지만 왜 더 빨라졌을까요? 최적화기가 몇몇 에지 케이스에서 조금 더 좋아졌기 때문입니다. 수행하는 최적화는 예전과 동일하지만, 추상 해석의 엄밀함이 JIT 백엔드로 조금 더 나은 연산을 내보내게 합니다.

구체적으로, 최적화기를 개선하면 pretty-printed 프로그램이 짧아질 수 있습니다. Busy Beaver Gauge는 수학 문제의 해를 탐색하는 프로그램의 길이를 측정합니다. 최종 인코딩 인터프리터를 구현하고 디버깅한 뒤, Brainfuck용 Busy Beaver Gauge에 올려둔 제 항목 두 개가 약 2%가량 더 짧아졌음을 발견했습니다. (다른 대부분의 항목은 이미 표준 대수에 따라 손수 최적화되어 있어 추가 최적화 여지가 없습니다.)

토의¶

초기와 최종 인코딩이 동등하다는 점, 그리고 RPython의 툴체인이 초기 인코딩을 선호하도록 작성되어 있다는 점을 감안하면, 우리가 실제로 얻은 것은 무엇일까요? 무언가를 얻긴 한 걸까요?

RPython에서 최종 인코딩의 명백한 단점 하나는 인터프리터의 크기입니다. 여기 보인 예제 인터프리터는 초기 인코딩된 인터프리터를 다시 쓴 것인데, 비교를 위해 여기서 볼 수 있습니다. 이 경우 최종 인코딩은 코드 양을 약 20% 늘립니다.

물론 최종 인코딩이 반드시 초기 인코딩보다 코드가 많다는 뜻은 아닙니다. 인터프리터의 모든 AST 인코딩은 표현식 문제(Expression Problem)에 종속됩니다. 일반적으로, 여러 종류의 노드를 가진 AST에 여러 동작을 구현하려면 코드가 제곱적으로 필요하다는 명제죠. 즉, 노드 종류가 m, 동작이 _n_개면 n × m 개의 메서드가 필요합니다. 초기 인코딩은 새로운 노드 종류를 추가하는 비용을 낮추고, 최종 인코딩은 새로운 동작을 추가하는 비용을 낮춥니다. 언어가 자주 변하지 않지만 새로운 동작이 자주 추가되고 오랜 기간 유지되는 성숙한 대규모 코드베이스에서는 최종 인코딩이 이길 가능성이 큽니다.

최종 인코딩에서의 최적화는 약간의 설계를 요구합니다. 추상 해석 접근은 탄탄하지만, 모노이드와 그 대수 법칙에 의존합니다. 최악의 경우, 추상을 인코딩하기 위해 전체 클래스 계층이 필요할 수도 있습니다.

단지 최적화기를 대수 법칙을 존중하는 추상 인터프리터로 재구현했을 뿐인데, 잔여 프로그램 크기가 2% 개선되었다는 점은 주목할 만합니다. 이것이 일반화된다면, 컴파일러 엔지니어에게 가장 중요한 교훈일 수 있습니다.

최종 인코딩은 OCaml과 Scala의 tagless-final 운동을 통해 대중화되었고, 특히 Kiselyov 등의 튜토리얼 연재로 유명합니다. 이 문맥에서의 "태그(tag)"는 객체의 타입/클래스에 대한 런타임 식별자입니다. 태그 없는 인코딩은 사실상 isinstance()를 허용하지 않습니다. 위의 전개에서 태그를 억지로 끼워 넣을 수는 있지만, 대부분 단계에서 물질적으로 중요하지는 않았습니다. 다만 최종 평가 단계에서는 태그가 필요했고, tagless-final의 통찰은 특정 타입 시스템이 그 태그 없이도 타입 안전한 평가를 표현할 수 있다는 것입니다. 우리는 더 나아가진 않겠습니다. 태그가 JIT에 귀중한 정보를 전달하기도 하기 때문입니다.

요약 표¶

감사의 말¶

Libera Chat의 #pypy에 계신 분들께 감사드립니다. 아이디어를 주신 arigato, 글로 정리하도록 독려해 주신 larstiq, 검토와 오류 지적을 해 주신 cfbolz와 mattip께 고맙습니다. 이 블로그 글로 이어진 원래 IRC 대화는 여기에서 볼 수 있습니다.

이 인터프리터는 RPython 인터프리터를 위한 Nix 플레이크인 rpypkgs 모음의 일부입니다. Nix가 설치된 독자는 플레이크에서 바로 이 인터프리터를 실행할 수 있습니다.

bash
$ nix-prefetch-url https://github.com/MG-K/pypy-tutorial-ko/raw/refs/heads/master/mandel.b
$ nix run github:rpypkgs/rpypkgs#bf -- /nix/store/ngnphbap9ncvz41d0fkvdh61n7j2bg21-mandel.b