0917 Compilers with variables and conditionals.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 컴파일러에서 변수, 조건문 다루기\n",
    "\n",
    "변수를 다루기 위해서는 기계상태에 메모리를 추가하고 메모리 연산을 위한 저급언어 명령을 추가한다.\n",
    "\n",
    "조건문을 다루기 위해서는 실행코드를 순차적으로만 실행하는 것이 아니라 특정 코드 위치로 이동하여 실행하는 저급언어 명령을 추가한다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "data Expr = Var Name          -- x\n",
    "          | Val Value         -- n\n",
    "          | Add Expr Expr     -- e1 + e2\n",
    "          -- | Sub Expr Expr\n",
    "          -- | Mul Expr Expr\n",
    "          -- | Div Expr Expr\n",
    "          | If Expr Expr Expr -- if e then e1 else e0\n",
    "          deriving Show\n",
    "\n",
    "type Name = String -- 변수의 이름은 문자열로 표현\n",
    "type Value = Int   -- 상수값은 정수\n",
    "\n",
    "type Stack = [Value]\n",
    "\n",
    "data Inst = ADD | PUSH Value      -- 스택 명령\n",
    "          | GOTO Code | JMPZ Code -- 실행코드 명령\n",
    "          | READ Addr             -- 메모리 명령\n",
    "          deriving Show\n",
    "type Code = [Inst]\n",
    "\n",
    "-- type Env = [ (Name, Value) ] 라는 인터프리터 실행 환경을\n",
    "-- 두 단계로 아래와 같이 나눈다\n",
    "type SymTbl = [ (Name, Addr) ]  -- 컴파일 단계에서 사용하는 심볼 테이블\n",
    "type Memory = [ (Addr, Value) ] -- 기계(가상머신) 실행 단계에서 사용하는 메모리\n",
    "\n",
    "type Addr = Int -- 주소는 정수로 표현\n",
    "\n",
    "-- 이제 Kont는 스택만이 아니라 세 요소로 이루어진 기계상태를 변화시키는 함수 타입이다\n",
    "type Kont = (Stack,Memory,Code) -> (Stack,Memory,Code)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "-- 더 이상 실행할 코드가 없는 기계상태로 변화시키는 함수\n",
    "haltK :: Kont\n",
    "haltK (s, mem, _) = (s, mem, [])\n",
    "\n",
    "-- 스택 명령을 실행시키기 위한 기계상태변화 함수들\n",
    "pushK :: Int -> Kont\n",
    "pushK n (s, mem, code) = (n:s, mem, code)\n",
    "\n",
    "addK :: Kont\n",
    "addK (n2:n1:s, mem, code) = ((n1+n2):s, mem, code)\n",
    "\n",
    "-- 실행코드 명령을 실행시키기 위한 기계상태변화 함수들\n",
    "jmpzK :: Code -> Kont\n",
    "jmpzK code (0:s, mem, _) = (s, mem, code) -- 스택 맨 위 값이 0이면 새로운 code 위치로 점프\n",
    "jmpzK _    (_:s, mem, c) = (s, mem, c)    -- 스택 맨 위가 0이 아니면 원래 실행하던 코드 c실행\n",
    "\n",
    "gotoK :: Code -> Kont\n",
    "gotoK code (s, mem, _) = (s, mem, code)   -- 무조건 새로운 code 위치로 이동\n",
    "\n",
    "-- 메모리 명령을 실행시키기 위한 기계상태변화 함수\n",
    "-- (메모리에서 값을 읽어 스택 맨 위에 쌓는다)\n",
    "readK a (s, mem, code) = case lookup a mem of\n",
    "                           Nothing -> error (show a ++ \" uninitialized memory address\")\n",
    "                           Just v  -> (v:s, mem, code)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "compile :: SymTbl -> Expr -> Code\n",
    "compile tbl (Var x) = case lookup x tbl of\n",
    "                        Nothing -> error (x ++ \" not found\")\n",
    "                        Just a  -> [READ a]\n",
    "compile tbl (Val n) = [PUSH n]\n",
    "compile tbl (Add e1 e2) = compile tbl e1 ++ compile tbl e2 ++ [ADD]\n",
    "compile tbl (If e e1 e0) =\n",
    "    compile tbl e ++ [JMPZ c0] ++ c1 ++ [GOTO []] ++ c0\n",
    "    where\n",
    "      c1 = compile tbl e1\n",
    "      c0 = compile tbl e0\n",
    "\n",
    "step :: Inst -> Kont\n",
    "step (PUSH n) = pushK n\n",
    "step ADD      = addK\n",
    "step (GOTO c) = gotoK c\n",
    "step (JMPZ c) = jmpzK c\n",
    "step (READ a) = readK a\n",
    "\n",
    "run :: Kont\n",
    "run (s, mem, []) = (s, mem, [])\n",
    "run (s, mem, c:cs) = run (step c (s, mem, cs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import Data.List (union)\n",
    "\n",
    "vars (Var x) = [x]\n",
    "vars (Val _) = []\n",
    "vars (Add e1 e2) = vars e1 `union` vars e2\n",
    "vars (If e e1 e0) = vars e `union` vars e1 `union` vars e0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Add (Add (Var \"x\") (Var \"y\")) (Val 100)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[READ 102,READ 103,ADD,PUSH 100,ADD]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "([110],[(102,7),(103,3)],[])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "-- 인터프리터에서는 아래 식을 실행하려면 [(\"x\",2),(\"y\",3)]와 같은\n",
    "-- 실행환경을 만들어 한방에 실행하면 되지만 컴파일러에는 두 단계\n",
    "e0 = Add (Add (Var \"x\") (Var \"y\")) (Val 100)\n",
    "e0\n",
    "-- 컴파일할 때는 변수를 메모리 주소에 대응시키는 심볼테이블이 필요\n",
    "code0 = compile [(\"x\",102),(\"y\",103)] e0\n",
    "code0\n",
    "-- 실행할 때는 해당 주소에 적절한 값을 할당한 메모리가 필요\n",
    "vm0 = ([], [(102,7), (103,3)], code0)\n",
    "run vm0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "{- b = 2,  x = 12, y = 123 -}\n",
    "\n",
    "-- if b then (x + 3) else y\n",
    "e1 = If (Var \"b\") (Add (Var \"x\") (Val 3)) (Var \"y\")\n",
    "-- (if b then (x + 3) else y) + 1000\n",
    "e2 = e1 `Add` Val 1000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(\"b\",101),(\"x\",102),(\"y\",103)]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[(101,2),(102,12),(103,123)]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "tbl0 = [(\"b\",101),(\"x\",102),(\"y\",103)]\n",
    "tbl0\n",
    "\n",
    "mem0 = [(101,2), (102,12), (103,123)]\n",
    "mem0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[READ 101,JMPZ [READ 103],READ 102,PUSH 3,ADD,GOTO [],READ 103]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[READ 101,JMPZ [READ 103],READ 102,PUSH 3,ADD,GOTO [],READ 103,PUSH 1000,ADD]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "code1 = compile tbl0 e1\n",
    "code1\n",
    "\n",
    "code2 = compile tbl0 e2\n",
    "code2\n",
    "\n",
    "{-\n",
    "import GHC.HeapView\n",
    "\n",
    "putStr =<< ppHeapGraph <$> buildHeapGraph 15 code2 (asBox code2)\n",
    "-}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([15],[(101,2),(102,12),(103,123)],[])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "([15],[(101,2),(102,12),(103,123)],[])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "-- 예상대로 e1의 계산 결과 스택 맨 위에 15가 나온다\n",
    "run ([], mem0, code1)\n",
    "\n",
    "-- e2의 계산 결과는 1015이어야 하는데 e1과 마찬가지로 15가 되어버린다\n",
    "run ([], mem0, code2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "아래는 e2를 컴파일한 code2를 실행한 결과가 왜 원하는 대로 나오지 않는지 좀더 자세히 살펴보기 위해\n",
    "step 함수를 한단계씩 호출해 가며 각각의 명령 실행 전후의 기계상태 vm0,...,vm6를 알아본 내용이다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([],[(101,2),(102,12),(103,123)],[READ 101,JMPZ [READ 103],READ 102,PUSH 3,ADD,GOTO [],READ 103,PUSH 1000,ADD])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "([2],[(101,2),(102,12),(103,123)],[JMPZ [READ 103],READ 102,PUSH 3,ADD,GOTO [],READ 103,PUSH 1000,ADD])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "([],[(101,2),(102,12),(103,123)],[READ 102,PUSH 3,ADD,GOTO [],READ 103,PUSH 1000,ADD])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "([12],[(101,2),(102,12),(103,123)],[PUSH 3,ADD,GOTO [],READ 103,PUSH 1000,ADD])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "([3,12],[(101,2),(102,12),(103,123)],[ADD,GOTO [],READ 103,PUSH 1000,ADD])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "([15],[(101,2),(102,12),(103,123)],[GOTO [],READ 103,PUSH 1000,ADD])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "([15],[(101,2),(102,12),(103,123)],[])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "vm0@(s0,   _,c0:cs0) = ([], mem0, code2)\n",
    "vm0\n",
    "vm1@(s1,mem1,c1:cs1) = step c0 (s0,mem0,cs0)\n",
    "vm1\n",
    "vm2@(s2,mem2,c2:cs2) = step c1 (s1,mem1,cs1)\n",
    "vm2\n",
    "vm3@(s3,mem3,c3:cs3) = step c2 (s2,mem2,cs2)\n",
    "vm3\n",
    "vm4@(s4,mem4,c4:cs4) = step c3 (s3,mem3,cs3)\n",
    "vm4\n",
    "vm5@(s5,mem5,c5:cs5) = step c4 (s4,mem4,cs4)\n",
    "vm5\n",
    "vm6 = step c5 (s5,mem5,cs5)\n",
    "vm6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "\n",
    "# HW02-compiler2019fall (10점)\n",
    "\n",
    "지금까지 살펴본 `compile` 함수의 문제점을 해결하여\n",
    "제대로 된 컴파일러를 정의하려면 다음과 같은 개념으로 접근하면 된다.\n",
    "\n",
    "> 지금 내가 주목해서 컴파일하는 부분의 목적 코드를 생성해서 \n",
    "> 그 다음에 뒤이어 할 일의 코드 앞에다 이어붙이는\n",
    "> 코드변환함수를 만드는 것이 컴파일러다.\n",
    "\n",
    "그러니까 다음과 같은 타입으로 `compile` 함수를 재작성해야 한다. \n",
    "```haskell\n",
    "type Control = Code -> Code -- 코드변환함수 타입\n",
    "compile :: SymTbl -> Expr -> Control\n",
    "```\n",
    "\n",
    "(테스트 코드 작성조건 안내 추가예정)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "과제에 도움이 될만한 내용 (아래에 추가예정)"
   ]
  },
  {
   "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
}