LISP 엔진 만들기 - 서론

안녕하세요, 첫 포스팅이네요. 아무래도 어떤 주제로 글쓰기를 시작해볼지 고민하고 있었습니다만, 간단하게 지금 하고 있는 토이 프로젝트를 주제로 해보는 것이 좋겠다는 생각이 들어 본 주제를 꺼내들었습니다.

배경

여러 주제도 있겠지만, 왜 프로그래밍 언어 처리기를 만드는 법을 써야할지에 대해서 고민이 많았습니다. 그래서 다음과 같이 Reasoning을 해보고자 합니다.

1) 언어에 대한 이해도를 높인다.

당장 내가 쓰는 프로그래밍 언어가 어떻게 처리되는지 감이 있어야 합니다. 여러 사람들과 일하면서, 기본적인 알고리즘을 짜는 코딩 방법은 잘 알고 있지만, 컴파일러가 해주는 영역과 시스템이 해주는 영역에 대한 구분이 상대적으로 모호하다는 것을 파악할 수 있었습니다. 또한 컴파일러가 해주는 것은 알고 있지만, 어떤 최적화가 어느 시점에 발생하는지 등에 대해서도 모호한 부분이 있음을 알 수 있었습니다.

언어 처리를 이해하는 것은 어찌보면 내가 작성하는 프로그램이 어떻게 처리될 것인지 명확하게 아는 것과 같습니다.

조건문에 대해 예를 들어보겠습니다.

java 예제

if (true) {
  tobe_executed();
} else {
  not_tobe_executed();
}

이 조건문에서는 not_tobe_executed 구문이 실행되지 않습니다. 물론 최적화가 전혀 이루어지지 않는 컴파일러의 경우에는, not_tobe_exectued 구문 또한 컴파일이 이루어집니다. 하지만, 최적화가 발생하는 코드에서는 위의 코드는 아래와 같이 최적화됩니다.

예제 - 최적화

tobe_exectued();

이 최적화가 발생하는 시점은 어느 단계일까요?

컴파일러의 구성을 살펴보도록 합시다.

Code -> [Lexer] -> Tokens -> [Parser] -> AST -> [Optimize] -> Refined AST -> [Engine] -> Execute!

Lexer는 사용자가 작성한 코드의 어휘들을 식별하는 작업을 합니다. 이를테면, 언어로 치면 단어의 형태소 분석을 하는 작업을 말합니다. 명사, 동사, 형용사등을 의미하죠. 프로그래밍 언어에서는 예약어(if, for, def, fn등), 괄호, 연산자, 심볼 등을 의미합니다. 이 시점이 지나고 나면 [Parser]에서 Abstract Syntax Tree라는 문법 구문 구조 분석 결과를 생성합니다. 예를들어, if something then execute else then do nothing 과 같이 컴퓨터가 인식할 수 있는 구문구조의 틀을 생성합니다.

이 시점이 지난 다음, 제가 뭉뜽그려서 [Optimize]라고 표기해둔 부분에서 최적화가 발생합니다. 여기에서는 구문구조상 불필요한 부분들, 실행되지 않을 부분 등을 정리함으로써 프로그램이 실행되는 단계에서 불필요한 공간이나 시간이 낭비되는 일을 좀 더 최소화합니다. 이 때, if(true)구문을 만났을 때 더이상 실행하지 않게 됩니다.

2) 여러 언어를 보다 쉽게 이해할 수 있다.

이렇게 되면, 언어의 이면이 보이기 때문에 다른 언어를 마주치더라도 어떤 맥락에서 이것이 등장하는지, 어떤 것을 표현하고자 하는것인지 등이 파악되면 새로운 언어를 마주하더라도 당황하지 않게 됩니다. 그리고, 각 언어가 지닌 패턴들을 이해하는데 큰 도움이 되죠. 아래를 살펴봅시다.

파이썬 코드

for x in somelist:
  print ("item {}" % x)

스칼라 코드

for (x <- somelist) {
  println(s"item $x")
}

C 코드

for (int i = 0; i < somelistLen; i++) {
  printf("item %s\n", somelist[i]);
}

Lisp - might Lengine

(loop for x in somelist
  (println (concat "item " (str x))))

위를 보시면 아시겠지만, 반복문을 표현하는 방식들이 매우 다양합니다. 언어들이 다르더라도 반복문의 핵심은 somelist라는 리스트에서 원하는 것들을 꺼내어 적당한 작업을 하고 되돌려주는 일을 합니다.

3) 사고력 향상

이상의 것들은 사고력을 기르는데 한몫을 합니다. 생각하는 방식을 바꾼다는 말이 매우 거창하게 들릴 수 있지만, 프로그래머 입장에서는 한가지 문제를 다양한 방식으로 풀어볼 수 있다는 것이 매우 중요합니다. 마치, 수학문제, 과학문제, 심지어 사회문제들도 한가지 방식으로 해결하지 않음을 알 수 있습니다.

아래의 예는 1부터 30까지 더하는 연산입니다.

C++ or Java

int sum = 0;
for (int i = 1; i <= 30; i++) {
  sum += i;
}

Functional approach, Scala

def sum(until: Int) = {
  @tailrec
  def loop(acc: Int, num: Int) = if (num == 0) acc else loop(acc + num, num - 1)
  loop(0, until)
}
// or
(1 to 30).foldLeft(0)(_ + _)
//

본 게시글은 함수형언어의 소개가 아니기 때문에 foldLeft에 대한 자세한 설명은 하지 않겠습니다. 간략하게 설명드리자면, 위 구문은, (1 to 30).foldLeft(0)((acc, elem) => acc + elem) 입니다. 의미는 1부터 30까지의 range sequence가 있을 때, acc에 1부터 30까지의 시퀀스 안에 있는 엘리먼트들을 모두 더하는 것입니다. sum 함수 안의 loop함수와 같다고 보시면 될 것 같습니다.

한편, C언어에서도 tail recursion 방식을 사용할 수도 있습니다.

C with tail recursion

int sum(int acc, int elem) {
  if (elem == 0) return acc;
  else return sum(acc + elem, elem - 1);
}

int main () {
  sum(0, 30);
}

4) 요약

이상에서 말씀드리고자 하는 것이 사실상 3인데, 언어에 대한 이해를 높이면, 그 언어가 가진 프로그래밍 패러다임을 이해하는데 도움이 되고, 문제를 푸는데 한가지 방식만이 아닌, 여러 방식으로 표현하는 법을 배움으로써, 어떤 문제를 어떻게 풀어야 효과적으로 접근할 수 있는지를 결정하는데 큰 도움이 됩니다. 그리고 그 언어의 이해를 높이는 한가지 방법으로, 이 언어들이 어떻게 처리되는지를 알게 됨으로써, 각 언어들이 가진 어떤 표현의 한계등을 파악하는데 매우 효과적일 수 있다는 점이 있습니다.

접근방법

LISP 언어 처리기를 만드는데, 다음의 접근 방법을 활용해보고자 합니다. 우선, 이 글에서는 주어진 LISP구문을 실행하는 실행기를 만들어볼 것입니다. 컴퓨터가 이해할 수 있는 컴파일 언어로의 생성은 다른 포스팅에서 다뤄보도록 하겠습니다. 이 글에서는 그냥 실행 가능한 프로그램입니다. 그리고, 실행만 하면 아까우니, REPL을 만들어봄으로써, 좀 더 interactive하게 해당 구문 처리기를 활용하는 방법에 대해서도 논의해보겠습니다.

언어 처리기의 구조는 다음과 같습니다.

Lisp code -> [Lexer] -> Tokens -> [Parser] -> AST -> [Execution Engine] -> Execute!

그리고, 시간이 된다면, 그리고 제가 만약 만들게 된다면 Optimize를 넣는 작업도 해볼 것입니다만, 우선 대괄호 안의 Lexer, Parser, Execution Engine만을 만들어보도록 하겠습니다.

시리즈 구성

이번 시리즈에서는 리습 엔진을 만들어볼 예정입니다. 본 시리즈에서는 Scala를 주 언어로 활용할 것이며, 크게 다음의 세 파트로 나뉩니다.

• Lexer
• Parser
• Execution

본 시리즈의 예제들을 따라하다보면, Lisp 실행기가 만들어지도록 본문을 구성해보겠지만… 자세한 사항은 소스코드 의 소스코들 살펴보시면 될 것 같습니다.

참고

LISP 강좌를 하진 않습니다. LISP에 대해 조금 익숙해지고 싶으시다면 tutorials point도 좋은 진입 지점일 것 같습니다.