지금까지 알아본 프로그래밍 방식으로 정수의 사칙연산에서 나눗셈을 제외한 3칙 연산만 지원하는 간단한 수식에 대한 인터프리터와 컴파일러를 만들어 볼 수 있다.
실제 인터프리터나 컴파일러는 텍스트 문자열로 된 소스코드를 트리의 형태로 변환하는 문법분석(parsing)이 기본적으로 필요하지만 그것은 고학년에 프로그래밍 언어나 컴파일러 등을 다루는 전공과목 수업을 들을 경우 자세히 배울 수 있으므로 여기서는 이미 문법분석이 다 되어서 트리의 형태로 수식을 다룰 수 있다고 가정하자. 수식 타입을 이진트리와 마찬가지 방식으로 아래와 같은 데이타 타입으로 정의할 수 있다. 수식을 보통 영어로 expression이라고 하므로 그 앞글자를 따서 타입의 이름을 Exp로 붙였다.
data Exp = Num Int -- 상수. 예를 들면 "4"는 (Num 4)
| Plus Exp Exp -- 덧셈식. 예를 들면 "4 + 3"은 (Plus (Num 4) (Num 3))
| Minus Exp Exp -- 뺄셈식. 예를 들면 "4 - 3"은 (Minus (Num 4) (Num 3))
| Times Exp Exp -- 곱셈식. 예를 들면 "4 * 3"은 (Times (Num 4) (Num 3))
deriving Show
-- "3 + (5 - 2)"를 아래와 같이 나타낸다
Plus (Num 3) (Minus (Num 5) (Num 2))
:type Plus (Num 3) (Minus (Num 5) (Num 2))
인터프리터를 eval이라는 함수로 정의하자. 수식의 값을 계산하는 것을 영어로 evaluation이라고 하므로 그 앞부분을 따서 이름을 붙였다.
인터프리터는 Exp 타입의 수식을 받아서 Int 타입 정수값을 돌려주는 함수이다. 귀납기초인 (Num n)은 더 이상 계산할 필요 없이 n을 돌려주면 되고 나머지 연산자로 이루어진 귀납단계의 경우들은 두 부분식 e1과 e2를 계산할 수 있다는 두 개의 귀납가정 eval e1과 eval e2를 이용하여 아래와 같이 정의하면 된다.
eval :: Exp -> Int
eval (Num n) = n
eval (Plus e1 e2) = eval e1 + eval e2
eval (Minus e1 e2) = eval e1 - eval e2
eval (Times e1 e2) = eval e1 * eval e2
-- 3 + (5 - 2) 를 인터프리터로 계산해 보자
eval (Plus (Num 3) (Minus (Num 5) (Num 2)))
인터프리터는 생각보다 매우 간단하지 않은가? 트리에 대한 구조적 귀납법으로 작성된 함수일 뿐이다. 물론 이렇게까지 간단한 것은 우리 언어가 번수도 함수도 없고 조건문도 반복문도 없는 정말 단순한 언어이기 때문이다. 변수, 함수, 조건문, 반복문 등등의 더 많은 기능이 있는 프로그래밍 언어의 인터프리터는 당연히 더 복잡해지겠지만 기본 핵심 원리는 우리가 만들어본 eval과 마찬가지다.
컴파일러는 소스 프로그램(혹은 코드)를 목적 코드로 번역해야 한다. 그렇다면 목적 코드에 해당하는 저수준 언어가 있어야 하는데, 여기서는 우리의 소스 프로그램에 쓰이는 3칙연산을 포함한 최소한의 명령어 셋으로 구성된 간단한 가상의 스택 머신을 정의할 것이다. 그래서 우리가 작성할 컴파일러는 Exp 타입의 수식을 받아 이 스택 머신의 기계어 코드를 돌려주는 함수로 정의될 것이다.
일단 스택 머신에는 스택이 있어야 하는데 우리는 지금 다른 값은 고려할 필요 없이 정수만 스택에 넣으면 되므로 그냥 리스트를 사용해 스택을 표현할 수 있다. 예를 들면 [1,2,3,4]가 네 개의 값이 들어있는 스택을 표현하는 리스트면 1이 맨 위의 값이고 4가 맨 밑의 값이다.
그 다음으로는 명령어 타입인 Inst를 정의하면 된다. 명령어를 영어로 instruction이라고 하므로 그 앞글자들을 따서 이름을 붙였다. 우선 스택머신이므로 PUSH와 POP이 기본적으로 제공되며 덧셈, 뺄셈, 곱셈에 해당하는 ADD, SUB, MUL이 제공된다. ADD, SUB, MUL 명령어에는 아무런 추가 정보가 필요없다. 왜냐하면 스택머신에서 연산은 스택의 제일 위에 있는 값을 소모하여 연산을 한 후 그 결과값을 스택의 맨 위에다 올려놓는 방식으로, 연산에 필요한 인자의 위치와 연산의 결과를 저장할 위치가 이미 정해져 있기 때문이다.
-- 스택을 정수 리스트로 표현한다. 왼쪽이 꼭대기, 오른쪽이 바닥이다.
type Stack = [Int]
-- 가상 머신의 명령어(인스트럭션)
data Inst = PUSH Int | POP | ADD | SUB | MUL deriving Show
-- 기계어 코드란 명령어(인스트럭션)가 한줄로 나열된 리스트, 즉 [Inst] 타입이다
type Code = [Inst]
위에서 Inst라는 타입 정의를 통해 가상머신 명령어의 문법을 정의하였다. 각각의 명령어가 어떤 의미를 가지는지, 즉 가상머신에서 명령어 하나를 실행한다는 것이 구체적으로 무슨 의미인지, 즉 어떤 계산으로 표현할 수 있는지를 각각의 명령어의 의미를 명확하게 정의해야 한다. 이렇게 각가의 명령어의 의미를 정의하고 있는 함수가 바로 아래에 있는 stepVM이다. stepVM 함수는 주어진 가상머신의 스택 상태에서 명령어(인스트럭션) 하나를 실행하고 나면 그 다음 단계에 스택이 어떻게 되어 있을지를 계산하는 함수이다. 즉 스택과 명령어 하나를 받아 스택을 돌려주는 함수인 것이다.
stepVM :: Stack -> Inst -> Stack
stepVM stack (PUSH n) = n : stack -- 스택 맨 위에 주어진 값 n 쌓는다
stepVM (n : stack) POP = stack -- 스택 맨 위의 값을 꺼내어 버린다
stepVM (x:y:stack) ADD = (y+x) : stack -- 맨 위의 값 둘을 스택에서 꺼내 그 덧셈 결과를 맨 위에 쌓는다
stepVM (x:y:stack) SUB = (y-x) : stack -- 맨 위의 값 둘을 스택에서 꺼내 그 뺄셈 결과를 맨 위에 쌓는다
stepVM (x:y:stack) MUL = (y*x) : stack -- 맨 위의 값 둘을 스택에서 꺼내 그 곱셈 결과를 맨 위에 쌓는다
위에서 정의한 함수로 각각의 명령어가 어떻게 동작하는지 테스트해 보자.
stepVM [2,3,4] (PUSH 1)
stepVM [2,3,4] POP
stepVM [2,3,4] ADD
stepVM [2,3,4] SUB
stepVM [2,3,4] MUL
"3 + (5 - 2)"에 해당하는 (Plus (Num 3) (Minus (Num 5) (Num 2)))를 손으로 목적 코드(즉, 스택머신 명령어의 나열)로 번역하면 다음과 같이 될 것이다.
PUSH 3
PUSH 5
PUSH 2
SUB
ADD이렇게 손컴파일한 것을 빈 스택 상태에서 시작해서 한 단계씩 실행시켜 보자.
stepVM [] (PUSH 3)
stepVM [3] (PUSH 5)
stepVM [5,3] (PUSH 2)
stepVM [2,5,3] SUB
stepVM [3,3] ADD
가상머신은 가상머신용 기계어 코드의 인터프리터다. 가상머신은 현재 스택 상태 시작해서 기계어 코드를 실행한다.
기계어 코드는 명령어(인스트럭션)의 나열, 즉 [Inst] 타입의 리스트로 표현할 수 있다.
그러므로 가상머신의 실행이란, 현재 가상머신의 상태인 Stack과 실행시킬 가상머신용 기계어 Code를 받아 실행 후 최종 상태의 Stack을 돌려주는 아래와 같은 함수로 정의할 수 있다. 가상머신의 실행을 정의하는 함수 runVM은 기계어 코드 길이(명렁어 개수)에 대한 수학적 귀납법 구조를 따라 정의되어 있으며, 앞서 정의한 하나의 명령어를 실행시키는 함수 stepVM을 이용하고 있다.
runVM :: Stack -> Code -> Stack
runVM stack [] = stack
runVM stack (inst:code) = runVM (stepVM stack inst) code
runVM [2,3,4] [ADD,ADD]
-- 손컴파일 예제 목적 코드를 runVM으로 한꺼번에 실행
runVM [] [PUSH 3, PUSH 5, PUSH 2, SUB, ADD]
다음 시간에는 Exp 타입의 소스 프로그램을 받아 자동으로 목적 Code를 생성하는 컴파일 함수를 정의해 보겠다.
우선 컴파일러를 정의하기 전에 컴파일러를 정의하는 데 쓸 (++) 연산자에 대한 기억을 되살려 보자. 우리가 직접 정의해 사용하던 List에 대한 함수들 중 두 리스트를 이어붙이는 append라는 함수를 정의했고 이 함수는 Nat 타입의 일진수 자연수의 덧셈과 같은 구조를 갖고 있다는 것이 기억나는가? (안난다면 복습을 ...) 하스켈 표준라이브러리에서 제공하는 리스트에 대해 append 함수와 같은 역할을 하는 연산자가 바로 (++)이다. 일단 하스켈 표준라이브러리 리스트는 (:)가 우리가 직접 만들어 쓰던 List의 Cons에 해당한다. 즉 (:)로 다음과 같이 리스트 맨 앞에 원소를 하나 추가할 수 있다.
1 : [2,3]
그리고 (++)로 두 리스트를 다음과 같이 이어붙일 수 있다.
[2,3] ++ [4,5]
리스트의 맨 뒤에 원소를 추가할 때도 (++) 연산자를 이용할 수 있다. 맨 끝에다 넣을 원소 하나만 들어 있는 리스트를 뒤에다 이어붙이면 된다.
[2,3] ++ [1]
리스트를 이어붙이는 (++) 연산자 뭔지 이제 기억이 났을 것이다. 혹시 기억이 안나더라도 뭐하는 연산자인지 감을 잡았을 것이다.
이제 compile 함수를 정의하자. 컴파일러는 Exp 타입의 소스 프로그램을 받아 목적 Code를 돌려주는 함수이다. 여기서 Code는 명령어가 일렬로 죽 나열된 리스트, 즉 [Inst] 타입을 나타낸다고 앞서 선언했었다. compile 함수의 정의는 다음과 같다.
compile :: Exp -> Code -- Code = [Inst]
compile (Num n) = [PUSH n]
compile (Plus e1 e2) = compile e1 ++ compile e2 ++ [ADD]
compile (Minus e1 e2) = compile e1 ++ compile e2 ++ [SUB]
compile (Times e1 e2) = compile e1 ++ compile e2 ++ [MUL]
compile (Num 3)
compile (Plus (Num 3) (Num 3))
runVM [] [PUSH 3,PUSH 3,ADD]
compile (Plus (Num 3) (Minus (Num 5) (Num 2)))
eval (Plus (Num 3) (Minus (Num 5) (Num 2)))
runVM [] [PUSH 3,PUSH 5,PUSH 2,SUB,ADD]