:!./install.sh
:opt no-lint
스택변환함수 개념으로 작성된 인터프리터를 다시 살펴보자.
지난 번 노트북에서는 스택 기본 연산을 정의해서 기본 연산을 이용해서 추상적인 스택을 다루는 방식으로 다른 연산을 정의했다.
스택을 꼭 리스트로만 구현하라는 법은 없기 때문에 추상데이타타입으로 접근하는 것이 차후에 코드 유지보수 측면에서도 바람직할 수도 있다.
하지만 우리가 이걸로 지금 진짜 프로그래머들이 사용할 프로그래밍언어를 구현하자는 것도 아니고
인터프리터와 컴파일러 관련 기본 개념을 실행가능한 코드를 통해 구체적으로 이해하기 위한 것이 주목적이므로,
여기서는 그냥 코드 길이를 좀 짧게 줄이기 위해서 addK같은 연산을 그냥 리스트에 대한 패턴 매칭으로 편하게 작성했다.
0909강의 노트북에서는 연산자 왼쪽부터 먼저 계산되었다는 걸 강조하기 위해 addLK라고 했지만 이것도 그냥 짧게 addK라고 했다. 함수 이름도 evalL' 대신 그냥 eval이라고 했다.
data Expr = Val Int
| Add Expr Expr
deriving Show
type Stack = [Int]
type Kont = Stack -> Stack
haltK s = s
pushK :: Int -> Kont
pushK n s = n : s
addK :: Kont
addK (n2:n1:s) = (n1 + n2) : s
eval :: Expr -> Kont
eval (Val n) = pushK n
eval (Add e1 e2) = addK . eval e2 . eval e1
eval (Add (Add (Val 2) (Val 3)) (Val 4)) [] -- (2 + 3) + 4
[9]
일반적으로 s0라는 스택으로 위 식을 실행했다면 다음과 같이 eval 함수의 계산 과정을 전개해 볼 수 있다.
eval (Add (Add (Val 2) (Val 3)) (Val 4)) s0
= ( addK . eval (Val 4) . eval (Add (Val 2) (Val 3)) ) s0
= ( addK . eval (Val 4) . eval (Add (Val 2) (Val 3)) ) s0
= ( addK . pushK 4 . (addK . pushK 3 . pushK 2) ) s0
= ( addK . pushK 4 . addK . pushK 3 . pushK 2 ) s0
= addK (pushK 4 (addK (pushK 3 (pushK 2 s0))))
= addK (pushK 4 (addK (pushK 3 (2 : s0))))
= addK (pushK 4 (addK (3 : 2 : s0)))
= addK (pushK 4 (addK (5 : s0))
= addK (5 : 4 : s0)
= 9 : s0
여기까지는 지난번에 했던 거 복습이다.
위와 같이 정리된 계산 과정에서 한 가지 주목해볼 점은 중간까지는 addK나 pushK와 같은 하스켈 함수로 표현된 연산의 합성함수를 생성하는 단계와 그 다음에 각각의 연산을 실행해서 최종 결과로 9를 얻는 단계로 나누어 생각해볼 수 있다는 점이다.
첫째 단계에서 addK와 pushK같은 스택 연산을 하는 하스켈 함수를 생성하는 대신 그러한 스택 연산을 나타내는 저급언어를 정의하여 덧셈식으로부터 저급언어 명령으로 이루어진 코드를 생성해 데이터의 형태로 저장해 놓는 것을 컴파일러로 이해할 수 있다.
-- 덧셈식을 처리하기 위한 기본 2가지 명령만으로 이루어진 저급언어
data Inst = ADD | PUSH Int deriving Show
type Code = [Inst] -- 코드는 명령으로 이루어진 리스트
compile :: Expr -> Code
compile (Val n) = [PUSH n]
compile (Add e1 e2) = compile e1 ++ compile e2 ++ [ADD]
-- 명령 한 개의 실행 의미를 스택변환함수로 대응
step :: Inst -> Kont
step (PUSH n) = pushK n
step ADD = addK
-- 여러 명령으로 이루어진 코드의 실행
run :: Code -> Kont
run [] = haltK
run (c:cs) = run cs . step c
compile (Add (Add (Val 2) (Val 3)) (Val 4)) -- (2 + 3) + 4
[PUSH 2,PUSH 3,ADD,PUSH 4,ADD]
run [PUSH 2,PUSH 3,ADD,PUSH 4,ADD] []
[9]
아래는 위에서 run 함수로 코드를 한꺼번에 실행하는 대신 각각의 명령 전후로 스택이 어떻게 바뀌는지 자세히 살펴보기 위해 step 함수를 한번씩 호출하며 직후 상태 s1,...,s5의 값을 알아본 본 것이다.
s0 = []
s1 = step (PUSH 2) s0
s2 = step (PUSH 3) s1
s3 = step ADD s2
s4 = step (PUSH 4) s3
s5 = step ADD s4
s0
s1
s2
s3
s4
s5
[]
[2]
[3,2]
[5]
[4,5]
[9]