0916 from Interpreters to Compilers.ipynb

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