서론

동화는 실제보다 더 진실합니다. 용이 존재한다고 말해서가 아니라, 용을 물리칠 수 있다고 말해주기 때문입니다.

G.K. 체스터튼 (닐 게이먼의 『코렐라인』을 통해)

여러분이 이 여정에 함께해 주셔서 정말 기쁩니다. 이 책은 프로그래밍 언어 인터프리터를 구현하는 방법에 대한 책입니다. 또한 구현할 가치가 있는 언어를 설계하는 방법에 대한 책이기도 합니다. 제가 처음 언어를 접했을 때 가졌으면 좋았을 책이며, 거의 10년 동안 제 머릿속으로 쓰고 있었던 책입니다.

이 책에서 우리는 완전한 기능을 갖춘 언어를 위한 두 개의 완전한 인터프리터를 단계별로 따라갈 것입니다. 저는 여러분이 언어 분야에 처음 발을 들이는 것이라고 가정하므로, 완전하고, 사용할 수 있으며, 빠른 언어 구현을 만드는 데 필요한 모든 개념과 코드 한 줄 한 줄을 다룰 것입니다.

한 권의 책에 두 개의 완전한 구현을 담아내면서도 너무 두꺼운 책이 되지 않도록, 이 책은 다른 책들보다 이론에 대한 비중이 낮습니다. 시스템의 각 부분을 구축하면서, 저는 그 뒤에 숨겨진 역사와 개념을 소개할 것입니다. PL (프로그래밍 언어) 연구자들로 가득한 칵테일 파티에 가게 될 경우에도 여러분이 어울릴 수 있도록 용어에 익숙해지도록 노력할 것입니다.

하지만 우리는 대부분의 노력을 언어를 작동시키는 데 집중할 것입니다. 이것이 이론이 중요하지 않다는 말은 아닙니다. 구문과 의미에 대해 정확하고 형식적으로 추론하는 것은 언어 작업 시 필수적인 기술입니다. 하지만 개인적으로 저는 직접 해보면서 가장 잘 배웁니다. 추상적인 개념으로 가득한 문단을 헤쳐나가는 것이 저에게는 정말 흡수하기 어렵습니다. 하지만 뭔가를 코딩하고, 실행하고, 디버깅했다면, 저는 그것을 *이해합니다*.

이것이 여러분을 위한 저의 목표입니다. 저는 여러분이 실제 언어가 어떻게 작동하고 살아 숨 쉬는지에 대한 확고한 직관을 갖기를 바랍니다. 제 희망은 여러분이 나중에 더 이론적인 책들을 읽을 때, 그곳의 개념들이 이 구체적인 기반에 붙어 여러분의 마음에 굳게 자리 잡을 것이라는 점입니다.

1 . 1이것을 왜 배워야 하는가?

모든 컴파일러 책의 모든 서론에는 이 섹션이 있는 것 같습니다. 프로그래밍 언어가 왜 이런 존재론적 의문을 불러일으키는지 모르겠습니다. 조류학 책들이 존재 이유를 정당화하는 것을 걱정할 것이라고 생각하지 않습니다. 독자들이 새를 사랑한다고 가정하고 가르치기 시작합니다.

하지만 프로그래밍 언어는 조금 다릅니다. 우리 중 누군가가 광범위하게 성공적인 범용 프로그래밍 언어를 만들 확률이 희박하다는 것은 사실인 것 같습니다. 세계적으로 널리 사용되는 언어 설계자들은 팝업 캠퍼를 올리지 않아도 폭스바겐 버스 한 대에 다 들어갈 정도입니다. 만약 그 엘리트 그룹에 합류하는 것이 언어를 배우는 *유일한* 이유라면, 정당화하기 어려울 것입니다. 다행히도 그렇지 않습니다.

1 . 1 . 1작은 언어들은 어디에나 있다

모든 성공적인 범용 언어마다, 수천 개의 성공적인 틈새 언어가 존재합니다. 우리는 예전에 그것들을 “작은 언어들”이라고 불렀지만, 전문 용어 경제의 인플레이션으로 인해 “도메인-특화 언어”라는 이름이 붙었습니다. 이들은 특정 작업에 맞춰 특별히 제작된 피진 언어입니다. 애플리케이션 스크립팅 언어, 템플릿 엔진, 마크업 형식, 그리고 설정 파일을 생각해 보세요.

거의 모든 대규모 소프트웨어 프로젝트는 이들 중 몇 가지를 필요로 합니다. 가능하다면, 직접 만드는 대신 기존의 것을 재사용하는 것이 좋습니다. 문서화, 디버거, 에디터 지원, 구문 강조, 그리고 기타 모든 부수적인 것들을 고려하면, 직접 개발하는 것은 매우 어려운 일이 됩니다.

하지만 기존 라이브러리가 여러분의 요구에 맞지 않을 때 파서나 다른 도구를 급히 만들어야 할 경우가 여전히 많을 것입니다. 심지어 기존 구현을 재사용할 때조차도, 불가피하게 디버깅하고 유지보수하며 그 내부를 들여다볼 필요가 생길 것입니다.

1 . 1 . 2언어는 훌륭한 훈련이다

장거리 달리기 선수들은 때때로 발목에 추를 달고 훈련하거나, 대기가 희박한 고지대에서 훈련합니다. 나중에 그 짐을 벗어던지면, 가벼워진 팔다리와 산소가 풍부한 공기의 새로운 상대적 편안함이 그들이 더 멀리 더 빨리 달릴 수 있게 해줍니다.

언어를 구현하는 것은 프로그래밍 기술의 진정한 시험입니다. 코드는 복잡하고 성능이 중요합니다. 재귀, 동적 배열, 트리, 그래프, 그리고 해시 테이블을 마스터해야 합니다. 여러분은 아마 일상적인 프로그래밍에서 최소한 해시 테이블을 사용할 테지만, 그것들을 *정말로* 이해하고 있나요? 음, 우리가 처음부터 직접 만들고 나면, 제가 장담하건대 이해하게 될 것입니다.

인터프리터가 여러분이 생각하는 만큼 어렵지 않다는 것을 보여주려 하지만, 잘 구현하는 것은 여전히 도전입니다. 도전하여 성공하면, 더 강력한 프로그래머가 되고 일상 업무에서 자료구조와 알고리즘을 사용하는 방법에 대해 더 현명해질 것입니다.

1 . 1 . 3한 가지 더

이 마지막 이유는 제게 매우 중요하기 때문에 인정하기가 어렵습니다. 어릴 적 프로그래밍을 배운 이후로, 저는 언어에 뭔가 마법 같은 것이 있다고 느꼈습니다. 처음으로 BASIC 프로그램을 한 글자씩 타이핑했을 때, BASIC *자체*가 어떻게 만들어졌는지 상상할 수 없었습니다.

나중에, 대학 친구들이 컴파일러 수업에 대해 이야기할 때 그들의 얼굴에 나타난 경외심과 공포감이, 언어 해커들이 뭔가 신비한 기술에 특권적으로 접근할 수 있는 마법사 같은 다른 종류의 인간이라는 것을 저에게 확신시키기에 충분했습니다.

그것은 매력적인 이미지이지만, 어두운 면도 있습니다. 저는 마법사처럼 느껴지지 않았고, 그래서 그 집단에 합류하는 데 필요한 어떤 타고난 자질이 부족하다고 생각하게 되었습니다. 비록 학창 시절 공책에 가상의 키워드를 낙서하며 언어에 매료되었지만, 그것들을 정말로 배우려고 용기를 내는 데 수십 년이 걸렸습니다. 그 “마법 같은” 특성, 그 배타적인 느낌이 *저를* 배제했습니다.

제가 마침내 저만의 작은 인터프리터들을 만들기 시작했을 때, 물론 마법 같은 것은 전혀 없다는 것을 금방 깨달았습니다. 그것은 단지 코드일 뿐이며, 언어를 해킹하는 사람들도 단지 사람일 뿐입니다.

언어 분야 밖에서는 자주 접하지 못하는 몇 가지 기술들이 *있고*, 일부 부분은 다소 어렵습니다. 하지만 여러분이 극복했던 다른 장애물들보다 더 어렵지는 않습니다. 제 희망은 여러분이 언어에 위협감을 느꼈고 이 책이 그 두려움을 극복하는 데 도움이 된다면, 아마도 제가 여러분을 전보다 아주 조금 더 용감하게 만들 수 있지 않을까 하는 것입니다.

그리고 누가 알겠습니까, 아마 여러분이 다음 위대한 언어를 만들 수도 있습니다. 누군가는 해야 합니다.

1 . 2이 책은 어떻게 구성되어 있는가

이 책은 세 부분으로 나뉘어 있습니다. 여러분은 지금 첫 번째 부분을 읽고 있습니다. 이 부분은 여러분이 방향을 잡고, 언어 해커들이 사용하는 몇 가지 용어를 배우며, 우리가 구현할 언어인 Lox를 소개하는 몇 개의 장으로 이루어져 있습니다.

나머지 두 부분 각각은 하나의 완전한 Lox 인터프리터를 만듭니다. 그 부분들 안에서, 각 장은 동일한 방식으로 구성됩니다. 각 장은 하나의 언어 기능을 다루고, 그 뒤에 있는 개념들을 가르치며, 구현 과정을 안내합니다.

저의 시행착오가 많았지만, 저는 두 개의 인터프리터를 이전 장들을 기반으로 하면서도 이후 장의 내용을 필요로 하지 않는 장 크기의 덩어리로 잘라낼 수 있었습니다. 첫 장부터 여러분은 실행하고 가지고 놀 수 있는 작동하는 프로그램을 갖게 될 것입니다. 각 장이 진행될수록, 여러분이 결국 완전한 언어를 갖게 될 때까지 점점 더 많은 기능이 추가될 것입니다.

풍부하고 번뜩이는 영어 산문 외에도, 각 장은 몇 가지 다른 즐거운 측면을 가지고 있습니다:

1 . 2 . 1코드

우리는 인터프리터를 *만드는* 것에 대해 이야기하므로, 이 책은 실제 코드를 포함합니다. 필요한 모든 코드 한 줄 한 줄이 포함되어 있으며, 각 코드 조각은 여러분의 계속 성장하는 구현에 어디에 삽입해야 하는지 알려줍니다.

다른 많은 언어 책과 언어 구현은 Lex와 Yacc 같은 도구, 즉 소위 **컴파일러-컴파일러**를 사용하는데, 이 도구들은 더 높은 수준의 설명에서 구현을 위한 일부 소스 파일을 자동으로 생성합니다. 그러한 도구들에는 장단점이 있으며, 양쪽 모두 강한 의견—어떤 사람들은 종교적인 신념이라고까지 말할 수 있는—이 있습니다.

우리는 여기에서 그것들을 사용하지 않을 것입니다. 마법과 혼란이 숨을 수 있는 어두운 구석이 없도록 하고 싶어서, 모든 것을 손으로 직접 작성할 것입니다. 보시다시피, 생각만큼 나쁘지 않으며, 여러분이 각 코드 라인과 두 인터프리터가 어떻게 작동하는지 정말로 이해하게 될 것임을 의미합니다.

책은 "실제 세계"와 다른 제약 조건을 가지고 있으므로, 여기의 코딩 스타일이 항상 유지보수 가능한 프로덕션 소프트웨어를 작성하는 최선의 방법을 반영하지 않을 수도 있습니다. 제가 예를 들어 `private`을 생략하거나 전역 변수를 선언하는 것에 대해 다소 무관심해 보인다면, 코드의 가독성을 높이기 위해 그렇게 한다는 것을 이해해 주십시오. 이 책의 페이지는 여러분의 IDE만큼 넓지 않으며, 모든 문자가 중요합니다.

또한, 코드에는 주석이 많지 않습니다. 그 이유는 몇 줄의 코드가 그것을 설명하는 여러 단락의 진심 어린 산문으로 둘러싸여 있기 때문입니다. 여러분이 자신의 프로그램을 동반하는 책을 쓸 때는, 주석을 생략해도 좋습니다. 그렇지 않다면, 저보다 `//`를 조금 더 많이 사용해야 할 것입니다.

이 책은 모든 코드 라인을 포함하고 각 라인이 무엇을 의미하는지 가르치지만, 인터프리터를 컴파일하고 실행하는 데 필요한 메커니즘은 설명하지 않습니다. 저는 여러분이 코드를 실행하기 위해 여러분이 선택한 IDE에서 메이크파일이나 프로젝트를 만들 수 있다고 가정합니다. 그러한 종류의 지침은 빠르게 구식이 되므로, 저는 이 책이 저급 술이 아니라 XO 브랜디처럼 오래도록 가치를 유지하기를 바랍니다.

1 . 2 . 2코드 조각

이 책은 구현에 필요한 말 그대로 모든 코드 라인을 포함하고 있기 때문에, 코드 조각들은 매우 정확합니다. 또한, 주요 기능이 누락된 상태에서도 프로그램을 실행 가능한 상태로 유지하려고 노력하기 때문에, 때때로 나중에 다른 코드 조각으로 대체될 임시 코드를 추가하기도 합니다.

모든 기능이 포함된 코드 조각은 다음과 같습니다:

      default:

        if (isDigit(c)) {
          number();
        } else {
          Lox.error(line, "Unexpected character.");
        }

        break;

가운데에는 추가할 새 코드가 있습니다. 기존 주변 코드에서 어느 위치에 들어가는지 보여주기 위해 위아래에 몇 줄의 흐릿한 선이 있을 수 있습니다. 또한 어떤 파일의 어디에 이 코드 조각을 배치해야 하는지 알려주는 짧은 설명도 있습니다. 만약 그 설명에 “_줄 교체”라고 쓰여 있다면, 흐릿한 선들 사이에 있는 기존 코드를 제거하고 새 코드 조각으로 교체해야 합니다.

1 . 2 . 3추가 설명

추가 설명은 인물 약력, 역사적 배경, 관련 주제에 대한 참조, 그리고 탐색할 다른 영역에 대한 제안을 담고 있습니다. 이 책의 뒷부분을 이해하기 위해 여러분이 *반드시* 알아야 할 내용은 없으므로, 원한다면 건너뛸 수 있습니다. 제가 여러분을 비난하지는 않겠지만, 조금은 슬플지도 모릅니다.

1 . 2 . 4도전 과제

각 장은 몇 가지 연습 문제로 끝납니다. 이미 다룬 내용을 복습하는 경향이 있는 교과서 문제집과는 달리, 이 문제들은 여러분이 장에 있는 내용보다 *더 많이* 배우도록 돕기 위한 것입니다. 이것들은 여러분을 정해진 길에서 벗어나 스스로 탐색하도록 이끌 것입니다. 다른 언어를 연구하거나, 기능을 구현하는 방법을 알아내거나, 또는 여러분의 안락한 영역 밖으로 나가도록 할 것입니다.

도전 과제들을 정복하면, 더 넓은 이해와 함께 약간의 어려움을 겪을 수도 있습니다. 아니면, 안락한 투어 버스 안에서 편안하게 머무르고 싶다면 건너뛰세요. 이것은 여러분의 책입니다.

1 . 2 . 5설계 노트

대부분의 “프로그래밍 언어” 책은 엄밀히 말해 프로그래밍 언어 *구현* 책입니다. 그들은 구현되는 언어를 어떻게 *설계*할 수 있는지에 대해서는 거의 논의하지 않습니다. 구현은 매우 정밀하게 정의되어 있기 때문에 재미있습니다. 우리 프로그래머들은 흑백논리, 즉 1과 0처럼 명확한 것들에 대한 친화력을 가지고 있는 것 같습니다.

개인적으로 저는 세상에 FORTRAN 77 구현은 충분히 많다고 생각합니다. 어느 시점에는 여러분이 *새로운* 언어를 설계하고 있는 자신을 발견하게 될 것입니다. 그 게임을 시작하게 되면, 방정식의 더 부드러운, 인간적인 측면이 가장 중요해집니다. 어떤 기능이 배우기 쉬운지, 혁신과 익숙함의 균형을 어떻게 맞출지, 어떤 구문이 더 읽기 쉬우며 누구에게 그러한지 같은 것들입니다.

이 모든 것들이 여러분의 새 언어의 성공에 깊이 영향을 미칩니다. 저는 여러분의 언어가 성공하기를 바라므로, 일부 장에서는 프로그래밍 언어의 인간적인 측면 중 일부에 대한 작은 에세이인 “설계 노트”로 마무리합니다. 저는 이 분야의 전문가가 아닙니다—아무도 정말 전문가라고 할 수 있을지 모르겠습니다—그러니 이 내용들을 너무 진지하게 받아들이지 마십시오. 그것이 사고를 위한 더 맛있는 양식이 될 것이며, 그것이 저의 주된 목표입니다.

1 . 3첫 번째 인터프리터

우리는 첫 번째 인터프리터인 jlox를 Java로 작성할 것입니다. 초점은 *개념*에 있습니다. 언어의 의미론을 정확하게 구현하기 위해 우리가 할 수 있는 가장 간단하고 깨끗한 코드를 작성할 것입니다. 이를 통해 우리는 기본 기술에 익숙해지고 언어가 정확히 어떻게 동작해야 하는지에 대한 이해를 깊게 할 것입니다.

Java는 이를 위한 훌륭한 언어입니다. 너무 세부적인 구현 사항에 압도되지 않을 만큼 충분히 고수준이지만, 여전히 매우 명확합니다. 스크립팅 언어와는 달리, 내부적으로 복잡한 메커니즘이 숨어있는 경우가 적고, 정적 타입을 통해 어떤 자료구조를 다루고 있는지 확인할 수 있습니다.

또한 제가 Java를 특별히 선택한 이유는 객체 지향 언어이기 때문입니다. 그 패러다임은 90년대 프로그래밍 세계를 휩쓸었고, 현재 수백만 프로그래머들의 지배적인 사고방식입니다. 아마 여러분은 이미 코드를 클래스와 메서드로 조직하는 데 익숙할 테니, 그 안락한 영역에 머물도록 할 것입니다.

학계의 언어 전문가들이 때때로 객체 지향 언어를 경시하기도 하지만, 현실은 언어 작업에서도 널리 사용된다는 것입니다. GCC와 LLVM은 C++로 작성되었고, 대부분의 JavaScript 가상 머신도 마찬가지입니다. 객체 지향 언어는 어디에나 있으며, 언어를 위한 도구와 컴파일러는 종종 *그 언어* 자체로 작성됩니다.

그리고 마지막으로, Java는 엄청나게 인기가 많습니다. 이는 여러분이 이미 Java를 알고 있을 가능성이 높으므로, 이 책을 시작하는 데 배워야 할 것이 적다는 의미입니다. 만약 Java에 익숙하지 않더라도, 당황하지 마십시오. 저는 Java의 상당히 최소한의 부분집합에만 고수하려고 노력합니다. Java 7의 다이아몬드 연산자를 사용하여 코드를 조금 더 간결하게 만들었지만, “고급” 기능은 그게 전부입니다. C#이나 C++와 같은 다른 객체 지향 언어를 알고 있다면, 충분히 헤쳐나갈 수 있을 것입니다.

파트 II가 끝날 무렵, 우리는 간단하고 읽기 쉬운 구현을 갖게 될 것입니다. 그것은 그다지 빠르지는 않지만, 정확합니다. 하지만 우리는 Java 가상 머신의 자체 런타임 기능을 기반으로 함으로써만 이를 달성할 수 있습니다. 우리는 Java *자체*가 그러한 것들을 어떻게 구현하는지 배우고 싶습니다.

1 . 4두 번째 인터프리터

그래서 다음 부분에서는 처음부터 다시 시작할 것이지만, 이번에는 C 언어로 할 것입니다. C는 메모리의 바이트와 CPU를 통해 흐르는 코드에 이르기까지, 구현이 *실제로* 어떻게 작동하는지 이해하기에 완벽한 언어입니다.

우리가 C를 사용하는 큰 이유는 C가 특히 잘하는 것들을 여러분에게 보여주기 위함이지만, 그것은 여러분이 C에 상당히 익숙해야 한다는 것을 *의미합니다*. 데니스 리치의 환생일 필요는 없지만, 포인터에 겁먹어서도 안 됩니다.

만약 아직 그 정도가 아니라면, C 언어 입문서를 읽고 완전히 이해한 다음 이곳으로 돌아오십시오. 그 대가로, 이 책을 통해 훨씬 더 강력한 C 프로그래머가 될 것입니다. Lua, CPython, Ruby의 MRI 등 얼마나 많은 언어 구현이 C로 작성되었는지를 고려할 때 이것은 유용합니다.

우리의 C 인터프리터인 clox에서는 Java가 우리에게 공짜로 제공했던 모든 것들을 직접 구현해야 합니다. 우리는 우리만의 동적 배열과 해시 테이블을 작성할 것입니다. 객체가 메모리에 어떻게 표현되는지 결정하고, 그것들을 회수할 가비지 컬렉터를 만들 것입니다.

우리의 Java 구현은 정확성에 중점을 두었습니다. 이제 그것을 마스터했으니, *빠르게* 만드는 쪽으로 전환할 것입니다. 우리의 C 인터프리터는 Lox를 효율적인 바이트코드 표현으로 번역하는 컴파일러를 포함할 것입니다 (걱정 마세요, 곧 그것이 무엇을 의미하는지 설명할 것입니다), 그리고 그것을 실행합니다. 이것은 Lua, Python, Ruby, PHP 및 다른 많은 성공적인 언어의 구현에서 사용되는 것과 동일한 기술입니다.

우리는 심지어 벤치마킹과 최적화도 시도할 것입니다. 마지막에는, 우리 언어에 대한 강력하고, 정확하며, 빠른 인터프리터를 갖게 될 것이고, 이는 다른 전문적인 수준의 구현들과 어깨를 나란히 할 수 있을 것입니다. 한 권의 책과 수천 줄의 코드치고는 나쁘지 않습니다.