0910 Interpreter with variables and conditionals - copy.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 인터프리터에서 변수, 조건문 다루기\n",
    "\n",
    "덧셈만 하던 언어에 이름(변수)와 조건문을 추가해 보자. 더많이 추가해 보고 싶으면 나머지 사칙연산을 나름대로 추가해 보아도 된다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "data Expr = Var String         -- x\n",
    "          | Val Int            -- n\n",
    "          | Add Expr Expr      -- e1 + e2\n",
    "          -- | Sub Expr Expr      -- e1 - e2\n",
    "          -- | Mul Expr Expr      -- e1 * e2\n",
    "          -- | Div Expr Expr      -- e1 / e2\n",
    "          | If Expr Expr Expr  -- if e then e1 else e0\n",
    "          deriving Show\n",
    "\n",
    "-- 실행시 이름에 대응되는 값을 찾아볼 수 있는 (실행)환경(environment)\n",
    "type Env = [ (String, Int) ]  \n",
    "\n",
    "eval :: Env -> Expr -> Int\n",
    "eval env (Var x) = case lookup x env of\n",
    "                     Nothing -> error (x ++ \" not found\") \n",
    "                     Just n  -> n\n",
    "eval env (Val n) = n\n",
    "eval env (Add e1 e2) = eval env e1 + eval env e2\n",
    "eval env (If e e1 e0) = case eval env e of\n",
    "                          0 -> eval env e0\n",
    "                          _ -> eval env e1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`lookup`이라는 함수는 찾으면 데이터 생성자 `Just`로 포장된 값을, 없으면 데이터 상수 `Nothing`을 돌려준다.\n",
    "참고로 `Just`와 `Nothing`은 아래와 같이 표준라이브러리에 정의되어 있는 `Maybe` 타입의 데이타 생성자 및 상수이다.\n",
    "```haskell\n",
    "data Maybe a = Nothing | Just a\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1,1,2,2,3,3,4,4]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "[1,1,2,2] ++ [3,3,4,4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "display: block;\n",
       "padding-bottom: 1.3em;\n",
       "padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "display: block;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "display: block;\n",
       "margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "font-weight: bold;\n",
       "font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "font-weight: bold;\n",
       "}\n",
       ".get-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "white-space: pre-wrap;\n",
       "}\n",
       ".show-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "margin-left: 1em;\n",
       "}\n",
       ".mono {\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "}\n",
       ".err-msg {\n",
       "color: red;\n",
       "font-style: italic;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "display: block;\n",
       "}\n",
       "#unshowable {\n",
       "color: red;\n",
       "font-weight: bold;\n",
       "}\n",
       ".err-msg.in.collapse {\n",
       "padding-top: 0.7em;\n",
       "}\n",
       ".highlight-code {\n",
       "white-space: pre;\n",
       "font-family: monospace;\n",
       "}\n",
       ".suggestion-warning { \n",
       "font-weight: bold;\n",
       "color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "font-weight: bold;\n",
       "color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "font-weight: bold;\n",
       "}\n",
       "</style><span class='get-type'>lookup :: forall a b. Eq a => a -> [(a, b)] -> Maybe b</span>"
      ],
      "text/plain": [
       "lookup :: forall a b. Eq a => a -> [(a, b)] -> Maybe b"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Just 3"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Just 4"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    ":type lookup\n",
    "lookup \"x\" []\n",
    "lookup \"x\" [(\"x\",3),(\"y\",4)]\n",
    "lookup \"y\" [(\"x\",3),(\"y\",4)]\n",
    "lookup \"z\" [(\"x\",3),(\"y\",4)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Just 3"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Just 4"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "Nothing"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "mylookup y []         = Nothing\n",
    "mylookup y ((x,v):ps) = if x==y then Just v\n",
    "                                else mylookup y ps\n",
    "mylookup \"x\" []\n",
    "mylookup \"x\" [(\"x\",3),(\"y\",4)]\n",
    "mylookup \"y\" [(\"x\",3),(\"y\",4)]\n",
    "mylookup \"z\" [(\"x\",3),(\"y\",4)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "우리 장난감 언어의 추상 문법 구조와 인터프리터를 정의한\n",
    "위 하스켈 코드를 프로그래밍언어 관련 교과서나 논문 및 기술문서 등에서\n",
    "많이 볼 수 있는 수식 기호 표기로 옮겨놓자면 다음과 같다.\n",
    "\n",
    "###### 문법 syntax\n",
    "$ x,y,z,\\ldots \\in \\textit{String} $\n",
    "\n",
    "$ n,m \\in \\textit{Int} $\n",
    "\n",
    "$ e \\in \\textit{Expr} ::= x ~\\mid~ n ~\\mid~ e_1+e_2 ~\\mid~ \\texttt{if}\\,~e~\\,\\texttt{else}\\,~e_1~\\,\\texttt{else}\\,~e_0 $\n",
    "\n",
    "###### 환경 environment\n",
    "$ \\textit{Env} = \\textit{String} \\xrightarrow{\\textrm{fin}} \\textit{Int} \\\\\n",
    "  \\sigma \\in \\textit{Env} ::= \\{ x_1 \\mapsto n_1,~\\ldots,~x_k\\mapsto n_k \\}$\n",
    "\n",
    "###### 실행규칙 evaluation rules\n",
    "\n",
    "$\\displaystyle\n",
    "\\frac{~~}{\n",
    "      x \\Downarrow_\\sigma \\sigma(x)}\n",
    "\\qquad\n",
    "\\frac{~~}{\n",
    "      n \\Downarrow_\\sigma n}\n",
    "$\n",
    "\n",
    "$~$\n",
    "\n",
    "$\\displaystyle\n",
    "\\frac{e_1 \\Downarrow_\\sigma n_1 \\quad e_2 \\Downarrow_\\sigma n_2 \\quad n = n_1+n_2}{\n",
    "      e_1 + e_2 \\Downarrow_\\sigma n}\n",
    "$\n",
    "\n",
    "$~$\n",
    "\n",
    "$\\displaystyle\n",
    "\\frac{e\\Downarrow_\\sigma 0 \\quad e_1 \\Downarrow_\\sigma n}{\n",
    "      \\texttt{if}\\,~e~\\,\\texttt{else}\\,~e_1~\\,\\texttt{else}\\,~e_0 \\Downarrow_\\sigma n}\n",
    "\\qquad\n",
    "\\frac{e\\Downarrow_\\sigma m \\quad e_1 \\Downarrow_\\sigma n \\quad m\\neq0}{\n",
    "      \\texttt{if}\\,~e~\\,\\texttt{else}\\,~e_1~\\,\\texttt{else}\\,~e_0 \\Downarrow_\\sigma n}\n",
    "$\n",
    "\n",
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`if b then (x + 3) else y`와 같은 코드를 `Expr` 타입의 하스켈 데이터로 다음과 같이 나타낼 수 있다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "e = If (Var \"b\") (Add (Var \"x\") (Val 3)) (Var \"y\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "이 코드를 실행하려면 $\\sigma = \\{ x \\mapsto 2, y \\mapsto 4, b \\mapsto 0 \\}$과 같은 환경이 필요하다.\n",
    "인터프리터 함수에 환경과 식을 같이 넘겨 ($\\texttt{eval}~\\,\\sigma\\,~\\texttt{e}$) 실행하면 된다. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "eval [(\"x\",2), (\"y\",4), (\"b\",0)] e"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "이번에는 $\\{ x \\mapsto 2, y \\mapsto 4, b \\mapsto 0 \\}$ 환경으로 실행해 보자."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "eval [(\"x\",2), (\"y\",4), (\"b\",1)] e  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "실행 환경은 코드에 나타나는 이름에 대한 값을 모두 포함하고 있어야 한다.\n",
    "그렇지 않을 경우 예컨대 $\\{ x \\mapsto 2, y \\mapsto 4 \\}$ 같은 환경으로 실행한다면 ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "header": "MessageHeader {mhIdentifiers = [\"c061ebff-4a18-40e5-ac00-bc901bad3a6d\"], mhParentHeader = Just (MessageHeader {mhIdentifiers = [\"c061ebff-4a18-40e5-ac00-bc901bad3a6d\"], mhParentHeader = Nothing, mhMetadata = Metadata (fromList [(\"deletedCells\",Array []),(\"cellId\",String \"f7d8c605-b3ab-40f5-883e-4125bc511e9c\")]), mhMessageId = UUID {uuidToString = \"0c5b3eb6-2643-4db4-b7f0-b3723a4c2c68\"}, mhSessionId = UUID {uuidToString = \"c061ebff-4a18-40e5-ac00-bc901bad3a6d\"}, mhUsername = \"\", mhMsgType = ExecuteRequestMessage}), mhMetadata = Metadata (fromList []), mhMessageId = UUID {uuidToString = \"a47d1623-4a9a-4633-a18b-ef58374772bd\"}, mhSessionId = UUID {uuidToString = \"c061ebff-4a18-40e5-ac00-bc901bad3a6d\"}, mhUsername = \"\", mhMsgType = ExecuteErrorMessage}",
     "output_type": "error",
     "traceback": [
      "b not found\nCallStack (from HasCallStack):\n  error, called at <interactive>:12:33 in interactive:Ghci3"
     ]
    }
   ],
   "source": [
    "eval [(\"x\",2), (\"y\",4)]          e -- 에러 발생"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## HW1-compiler2019\n",
    "제출기한: 2019-09-19 목요일 밤 11:59까지\n",
    "\n",
    "점수: 5점. 하지만 이 점수는 임시로 받아 둔 점수일 뿐이고 중간고사에 관련 문제가 출제되어 그 문제를 제대로 해결한 정도에 따라 과제에서 받은 점수의 일정 비율만 실제 과제 점수로 책정된다. 과제는 맞게 제출했으나 중간고사에 관련 문제를 전혀 풀지 못할 정도로 실제 이해하지 못하고 있는 경우는 음의 비율 즉 중간고사 결과에 따라서는 과제 점수가 마이너스 점수로 책정될 수도 있다.\n",
    "\n",
    " * 이름: ???\n",
    " * 학번: 201?????\n",
    "\n",
    "아래 `vars :: Expr -> [String]` 함수는 주어진 식에 나타난 변수들을 모두 모은 리스트를 돌려준다.\n",
    "이 함수를 이용해 어떤 환경이 주어진 식에 나타난 변수를 모두 정의하고 있는지 검사하는 `closedBy :: Expr -> Env -> Bool`를 작성하라."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "import Data.List (union)\n",
    "\n",
    "vars :: Expr -> [String]\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": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[\"b\",\"x\",\"y\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "e = If (Var \"b\") (Add (Var \"x\") (Val 3)) (Var \"y\")\n",
    "\n",
    "vars e"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "allfirst []           = []\n",
    "allfirst ((x,y) : ps) = x : allfirst ps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[\"x\",\"y\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "allfirst [(\"x\",3),(\"y\",4)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"x\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[\"x\",\"y\",\"z\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fst (\"x\",1)\n",
    "\n",
    "map fst [(\"x\",3), (\"y\",4), (\"z\",5)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "-- 정답은 아니고 e를 if b then (x+3) else y 고정했다면 이런 식으로 가능\n",
    "closedBy'' :: Expr -> Env -> Bool\n",
    "closedBy'' e env = elem \"b\" envVars && elem \"x\" envVars && elem \"y\" envVars\n",
    "                 {- eVars안에 있는 모든 x에 대해서\n",
    "                    elem x envVars 가 모두 True가 되어야 한다\n",
    "                 -}\n",
    "  where\n",
    "    envVars = map fst env\n",
    "\n",
    "-- 항상 e = If (Var \"b\") (Add (Var \"x\") (Val 3)) (Var \"y\")\n",
    "\n",
    "closedBy'' undefined [(\"x\",2), (\"y\",4), (\"z\",6), (\"b\",0)] -- True\n",
    "closedBy'' undefined [(\"x\",2), (\"y\",4), (\"b\",0)]          -- True\n",
    "closedBy'' undefined [(\"x\",2), (\"y\",4)]                   -- False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "header": "MessageHeader {mhIdentifiers = [\"c061ebff-4a18-40e5-ac00-bc901bad3a6d\"], mhParentHeader = Just (MessageHeader {mhIdentifiers = [\"c061ebff-4a18-40e5-ac00-bc901bad3a6d\"], mhParentHeader = Nothing, mhMetadata = Metadata (fromList [(\"deletedCells\",Array []),(\"cellId\",String \"c976ec7c-1a2d-4752-a43b-6c188283358a\")]), mhMessageId = UUID {uuidToString = \"9a916872-dbbe-46ad-9ab8-0480e2ff70c1\"}, mhSessionId = UUID {uuidToString = \"c061ebff-4a18-40e5-ac00-bc901bad3a6d\"}, mhUsername = \"\", mhMsgType = ExecuteRequestMessage}), mhMetadata = Metadata (fromList []), mhMessageId = UUID {uuidToString = \"f7207f00-498d-4633-8896-4c7d2cc2e126\"}, mhSessionId = UUID {uuidToString = \"c061ebff-4a18-40e5-ac00-bc901bad3a6d\"}, mhUsername = \"\", mhMsgType = ExecuteErrorMessage}",
     "output_type": "error",
     "traceback": [
      "Prelude.undefined\nCallStack (from HasCallStack):\n  error, called at libraries/base/GHC/Err.hs:78:14 in base:GHC.Err\n  undefined, called at <interactive>:2:18 in interactive:Ghci553"
     ]
    }
   ],
   "source": [
    "closedBy :: Expr -> Env -> Bool\n",
    "closedBy e env = undefined\n",
    "  where\n",
    "    eVars = vars e\n",
    "    envVars = map fst env\n",
    "\n",
    "-- e3 = If (Var \"b\") (Add (Var \"x\") (Val 3)) (Var \"y\")\n",
    "\n",
    "closedBy undefined [(\"x\",2), (\"y\",4), (\"z\",6), (\"b\",0)] -- True\n",
    "closedBy undefined [(\"x\",2), (\"y\",4), (\"b\",0)]          -- True\n",
    "closedBy undefined [(\"x\",2), (\"y\",4)]                   -- False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[\"b\",\"x\",\"y\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[\"z\",\"b\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "ename": "",
     "evalue": "",
     "header": "MessageHeader {mhIdentifiers = [\"c061ebff-4a18-40e5-ac00-bc901bad3a6d\"], mhParentHeader = Just (MessageHeader {mhIdentifiers = [\"c061ebff-4a18-40e5-ac00-bc901bad3a6d\"], mhParentHeader = Nothing, mhMetadata = Metadata (fromList [(\"deletedCells\",Array []),(\"cellId\",String \"fcbd647a-a3f6-4ea4-bf91-d552f9594228\")]), mhMessageId = UUID {uuidToString = \"18efef7b-40e7-4648-82d3-0bd853610655\"}, mhSessionId = UUID {uuidToString = \"c061ebff-4a18-40e5-ac00-bc901bad3a6d\"}, mhUsername = \"\", mhMsgType = ExecuteRequestMessage}), mhMetadata = Metadata (fromList []), mhMessageId = UUID {uuidToString = \"266cadc0-48d4-4188-a099-075557b03b26\"}, mhSessionId = UUID {uuidToString = \"c061ebff-4a18-40e5-ac00-bc901bad3a6d\"}, mhUsername = \"\", mhMsgType = ExecuteErrorMessage}",
     "output_type": "error",
     "traceback": [
      "Prelude.undefined\nCallStack (from HasCallStack):\n  error, called at libraries/base/GHC/Err.hs:78:14 in base:GHC.Err\n  undefined, called at <interactive>:2:18 in interactive:Ghci553"
     ]
    }
   ],
   "source": [
    "e3 = If (Var \"b\") (Add (Var \"x\") (Val 3)) (Var \"y\")\n",
    "env3 = [(\"z\",3),(\"b\",5)] \n",
    "\n",
    "vars e3      -- eVars\n",
    "map fst env3 -- envVars\n",
    "\n",
    "closedBy e3 env3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "header": "MessageHeader {mhIdentifiers = [\"c061ebff-4a18-40e5-ac00-bc901bad3a6d\"], mhParentHeader = Just (MessageHeader {mhIdentifiers = [\"c061ebff-4a18-40e5-ac00-bc901bad3a6d\"], mhParentHeader = Nothing, mhMetadata = Metadata (fromList [(\"deletedCells\",Array []),(\"cellId\",String \"62c2a32d-d03b-495f-9598-bc199deb4e45\")]), mhMessageId = UUID {uuidToString = \"4a9ad3b2-70f9-4d12-9a39-9d53d8f05d8f\"}, mhSessionId = UUID {uuidToString = \"c061ebff-4a18-40e5-ac00-bc901bad3a6d\"}, mhUsername = \"\", mhMsgType = ExecuteRequestMessage}), mhMetadata = Metadata (fromList []), mhMessageId = UUID {uuidToString = \"2c89f4ea-80b6-48bf-8e8f-f63adc512891\"}, mhSessionId = UUID {uuidToString = \"c061ebff-4a18-40e5-ac00-bc901bad3a6d\"}, mhUsername = \"\", mhMsgType = ExecuteErrorMessage}",
     "output_type": "error",
     "traceback": [
      "Prelude.undefined\nCallStack (from HasCallStack):\n  error, called at libraries/base/GHC/Err.hs:78:14 in base:GHC.Err\n  undefined, called at <interactive>:2:18 in interactive:Ghci553"
     ]
    }
   ],
   "source": [
    "e = If (Var \"b\") (Add (Var \"x\") (Val 3)) (Var \"y\")\n",
    "\n",
    "closedBy e [(\"x\",2), (\"y\",4), (\"z\",6), (\"b\",0)] -- True\n",
    "{-  elem \"b\" [\"b\",\"x\",\"y\",\"z\"] &&\n",
    "    elem \"x\" [\"b\",\"x\",\"y\",\"z\"] &&\n",
    "    elem \"y\" [\"b\",\"x\",\"y\",\"z\"]     -}\n",
    "closedBy e [(\"x\",2), (\"y\",4), (\"b\",0)]          -- True\n",
    "{-  elem \"b\" [\"b\",\"x\",\"y\"] &&\n",
    "    elem \"x\" [\"b\",\"x\",\"y\"] &&\n",
    "    elem \"y\" [\"b\",\"x\",\"y\"]     -}\n",
    "closedBy e [(\"x\",2), (\"y\",4)]                   -- False\n",
    "{-  elem \"b\" [\"x\",\"y\"] &&\n",
    "    elem \"x\" [\"x\",\"y\"] &&\n",
    "    elem \"y\" [\"x\",\"y\"]     -}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "{- 또다른 방법\n",
    "closedBy :: Expr -> Env -> Bool\n",
    "closedBy (Var x)      []            = False\n",
    "closedBy (Var x)      ((y,_) : env) = if x == y then True else ...\n",
    "closedBy (Val n)      _             = True\n",
    "closedBy (Add e1 e2)  env           = ...\n",
    "closedBy (If e e1 e0) env           = ...\n",
    "-}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "아래는 과제에 참고가 될 수도 있는 내용이다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"x\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fst (\"x\",2)\n",
    "snd (\"x\",2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[\"x\",\"y\"]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "map fst [(\"x\",2), (\"y\",4)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "-- \"y\"가 [\"b\",\"x\",\"y\"] 있는지 없는지\n",
    "\n",
    "elem 2 [1,2,3]\n",
    "elem 4 [1,2,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "-- 환경 [\"b\",\"x\",\"y\"]가   [\"x\",\"y\"]를 포함하나?\n",
    "\n",
    "elem \"x\" [\"b\",\"x\",\"y\"]\n",
    "elem \"y\" [\"b\",\"x\",\"y\"]\n",
    "\n",
    "elem \"x\" [\"b\",\"x\",\"y\"] && elem \"y\" [\"b\",\"x\",\"y\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "-- 환경 [\"b\",\"x\",\"y\"]가   [\"x\",\"y\",\"z\"]를 포함하나?\n",
    "elem \"x\" [\"b\",\"x\",\"y\"]\n",
    "elem \"y\" [\"b\",\"x\",\"y\"]\n",
    "elem \"z\" [\"b\",\"x\",\"y\"]\n",
    "\n",
    "elem \"x\" [\"b\",\"x\",\"y\"] && elem \"y\" [\"b\",\"x\",\"y\"] && elem \"z\" [\"b\",\"x\",\"y\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "-- f [b1,b2,b3,...] = b1 && b2 && b3 && ...\n",
    "f :: [Bool] -> Bool\n",
    "f []     = True\n",
    "f (b:bs) = b && f bs\n",
    "\n",
    "f [True,True,True] \n",
    "f [True,False,True]\n",
    "\n",
    "and [True,True,True]\n",
    "and [True,False,True]\n",
    "\n",
    "-- and = foldr (&&) True 와 같다"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "-- g [b1,b2,b3,...] = b1 || b2 || b3 || ...\n",
    "g :: [Bool] -> Bool\n",
    "g []     = False\n",
    "g (b:bs) = b || g bs\n",
    "\n",
    "g [False,False,False]\n",
    "g [False,True,False]\n",
    "\n",
    "or [False,False,False]\n",
    "or [False,True,False]\n",
    "\n",
    "-- or = foldr (||) False 와 같다"
   ]
  },
  {
   "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
}