{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": []
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
":!./install.sh"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# CEK 기계에 기본제공연산 추가\n",
"CEK 기계는 80년대에 Friedman과 Felleisen이 SECD 기계(Landin 1964)를 더 말끔하게 정리한 것이다.\n",
"\n",
"여기서는 지난번 노트북에서 살펴본 CEK 기계에 기본제공연산(pritivmve operation)을 추가해 보자.\n",
"강의 일정상 지나친 복잡함은 피하기 위해 정수값들에 대한 기본연산만을 고려하기로 하자.\n",
"\n",
"###### 참고자료\n",
"* https://www.cs.bham.ac.uk/~hxt/2015/compilers/compiling-functional.pdf\n",
"* https://en.wikipedia.org/wiki/SECD_machine\n",
"* https://www.brics.dk/RS/03/33/\n",
"* https://pages.cpsc.ucalgary.ca/~robin/FMCS/FMCS2014/Prashant_talk.pdf\n",
"* https://github.com/kseo/secd"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"type Nm = String\n",
"\n",
"data Exp = Var Nm -- x\n",
" | App Exp Exp -- e1 e2\n",
" | Lam Nm Exp -- \\x.e\n",
" | Lit Int -- n\n",
" | Prm Prim [Exp] -- f(x1,...,xn)\n",
" deriving Show\n",
"\n",
"data Prim = Suc | Add deriving Show"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [],
"source": [
"type CEK = (Code,Env,Kont)\n",
"\n",
"data Code = OpE Exp\n",
" | OpV Value\n",
" | OpArg\n",
" | OpCall\n",
" deriving Show\n",
"type Env = [(Nm,Value)]\n",
"type Kont = [Frame]\n",
"\n",
"data Value = Vint Int -- n\n",
" | Clos Exp Env -- < \\x.e, env >\n",
" deriving Show\n",
"\n",
"data Frame = FrV Value -- (v O)\n",
" | FrE Exp Env -- (O e env)\n",
" | FrP Prim [Value] [Exp] Env -- (f [vi,..] O [ei,...] env)\n",
" deriving Show"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [],
"source": [
"lookup' x env = case lookup x env of Just v -> v\n",
" Nothing -> error(\"x is unknown\")\n",
"\n",
"-- 기본제공연산이 호출되었을 때 동작 정의\n",
"callPrim Suc [Vint n] = Vint (n+1)\n",
"callPrim Add [Vint n2, Vint n1] = Vint (n1+n2)\n",
"\n",
"step :: CEK -> Maybe CEK\n",
"step (OpE(Var x), env, k) = Just (OpV(lookup' x env), env, k)\n",
"step (OpE(App e1 e2), env, k) = Just (OpE e1, env, FrE e2 env : k)\n",
"step (OpE(e@Lam{}), env, k) = Just (OpV(Clos e env), env, k)\n",
"step (OpE(Lit n), env, k) = Just (OpV(Vint n), env, k)\n",
"-- step (OpE(Prm f es), env, k) = Just (OpArg, env, FrP f [] es env : k) -- 기본제공연산식 처리 시작\n",
"step (OpV v, env1, FrE e2 env2 : k) = Just (OpE e2, env2, FrV v : k)\n",
"step (OpV v, env1, FrV(Clos (Lam x e) env2) : k) = Just (OpE e, (x,v) : env2, k)\n",
"-- step (OpArg, env1, FrP f vs (e2:es) env2 : k) = undefined -- 다음 인자값 계산\n",
"-- step (OpV v, env1, FrP f vs es env2 : k) = undefined -- 계산된 인자값 프레임에 추가\n",
"-- step (OpArg, env1, FrP f vs [] env2 : k) = undefined -- 다음 인자값 계산 시도하지만 더 이상 인자 없는 경우 처리\n",
"-- step (OpCall, env1, FrP f vs [] env2 : k) = Just (OpV(callPrim f vs), env2, k) -- 모든 인자 계산 후 기본제공연산 호출\n",
"step _ = Nothing"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [],
"source": [
"{-# LANGUAGE FlexibleInstances #-}\n",
"import IHaskell.Display\n",
"import Data.List (intersperse)\n",
"\n",
"class TeX a where\n",
" toTeX :: a -> String\n",
"\n",
"instance TeX Exp where\n",
" toTeX (Var x) = x\n",
" toTeX (App e1 e2) = \"(\"++toTeX e1++\"\\\\;\"++toTeX e2++\")\" \n",
" toTeX (Lam x e) = \"(\\\\lambda{}\"++x++\".\"++toTeX e++\")\"\n",
" toTeX (Lit n) = show n\n",
" toTeX (Prm f es) = \"\\\\textsf{\"++show f++\"}\"++toTeX es\n",
"\n",
"instance TeX Code where\n",
" toTeX (OpE e) = toTeX e\n",
" toTeX (OpV v) = toTeX v\n",
" toTeX (OpArg) = \"\\\\texttt{arg}\"\n",
" toTeX (OpCall) = \"\\\\texttt{call}\"\n",
"\n",
"instance TeX Value where\n",
" toTeX (Vint n) = show n\n",
" toTeX (Clos e env) = \"\\\\langle{}\" ++ toTeX e ++ \",\" ++ revTeX env ++ \"\\\\rangle{}\"\n",
"\n",
"instance TeX Frame where\n",
" toTeX (FrV v) = \"(\"++toTeX v++\"\\\\,\\\\bigcirc{})\"\n",
" toTeX (FrE e env) = \"(\\\\bigcirc{}\\\\,\"++toTeX e++\"\\\\;\"++revTeX env++\")\"\n",
" toTeX (FrP f vs es env) = \"(\\\\textsf{\"++show f++\"}\"++revTeX vs++\"\\\\,\\\\bigcirc{}\\\\,\"++toTeX es++\"\\\\;\"++revTeX env++\")\"\n",
"\n",
"instance TeX (Nm,Value) where\n",
" toTeX (x,v) = x++\"\\\\mapsto{}\"++toTeX v\n",
"\n",
"instance TeX CEK where\n",
" toTeX (c,env,k) = \"\\\\big\\\\langle{}\"\n",
" ++ toTeX c ++ \"\\\\;\\\\big|\\\\;\" ++ revTeX env ++ \"\\\\;\\\\big|\\\\;\" ++ toTeX k\n",
" ++ \"\\\\big\\\\rangle{}\"\n",
"\n",
"instance TeX a => TeX (Maybe a) where\n",
" toTeX (Just x)= \"\\\\texttt{Just}(\"++toTeX x++\")\"\n",
" toTeX Nothing = \"\\\\texttt{Nothing}\"\n",
"\n",
"instance TeX a => TeX [a] where\n",
" toTeX xs = \"[\" ++ (concat . intersperse \",\" $ map toTeX xs) ++ \"]\"\n",
"\n",
"revTeX = toTeX . reverse\n",
"\n",
"newtype LaTeX a = LaTeX a\n",
"\n",
"htmlTeX a = html $ \"$\"++toTeX a++\"$\"\n",
"\n",
"instance TeX a => IHaskellDisplay (LaTeX a) where\n",
" display (LaTeX a) = return $ Display [htmlTeX a]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"이전 예제는 그대로 잘 동작한다."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"App (App (Lam \"x\" (Lam \"y\" (Var \"x\"))) (Lit 1)) (Lit 2)"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"$(((\\lambda{}x.(\\lambda{}y.x))\\;1)\\;2)$"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"$\\textsf{Suc}[3]$"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"fst_1_2 = App (App (Lam \"x\" $ Lam \"y\" $ Var \"x\") (Lit 1)) (Lit 2)\n",
"fst_1_2\n",
"LaTeX fst_1_2\n",
"LaTeX (Prm Suc[Lit 3])"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Just (OpE (App (App (Lam \"x\" (Lam \"y\" (Var \"x\"))) (Lit 1)) (Lit 2)),[],[])\n",
"Just (OpE (App (Lam \"x\" (Lam \"y\" (Var \"x\"))) (Lit 1)),[],[FrE (Lit 2) []])\n",
"Just (OpE (Lam \"x\" (Lam \"y\" (Var \"x\"))),[],[FrE (Lit 1) [],FrE (Lit 2) []])\n",
"Just (OpV (Clos (Lam \"x\" (Lam \"y\" (Var \"x\"))) []),[],[FrE (Lit 1) [],FrE (Lit 2) []])\n",
"Just (OpE (Lit 1),[],[FrV (Clos (Lam \"x\" (Lam \"y\" (Var \"x\"))) []),FrE (Lit 2) []])\n",
"Just (OpV (Vint 1),[],[FrV (Clos (Lam \"x\" (Lam \"y\" (Var \"x\"))) []),FrE (Lit 2) []])\n",
"Just (OpE (Lam \"y\" (Var \"x\")),[(\"x\",Vint 1)],[FrE (Lit 2) []])\n",
"Just (OpV (Clos (Lam \"y\" (Var \"x\")) [(\"x\",Vint 1)]),[(\"x\",Vint 1)],[FrE (Lit 2) []])\n",
"Just (OpE (Lit 2),[],[FrV (Clos (Lam \"y\" (Var \"x\")) [(\"x\",Vint 1)])])\n",
"Just (OpV (Vint 2),[],[FrV (Clos (Lam \"y\" (Var \"x\")) [(\"x\",Vint 1)])])\n",
"Just (OpE (Var \"x\"),[(\"y\",Vint 2),(\"x\",Vint 1)],[])\n",
"Just (OpV (Vint 1),[(\"y\",Vint 2),(\"x\",Vint 1)],[])"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"mapM_ print $ takeWhile isJust $ iterate (step =<<) (Just(OpE fst_1_2,[],[]))"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"$\\texttt{Just}(\\big\\langle{}(((\\lambda{}x.(\\lambda{}y.x))\\;1)\\;2)\\;\\big|\\;[]\\;\\big|\\;[]\\big\\rangle{})$"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"$\\texttt{Just}(\\big\\langle{}((\\lambda{}x.(\\lambda{}y.x))\\;1)\\;\\big|\\;[]\\;\\big|\\;[(\\bigcirc{}\\,2\\;[])]\\big\\rangle{})$"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"$\\texttt{Just}(\\big\\langle{}(\\lambda{}x.(\\lambda{}y.x))\\;\\big|\\;[]\\;\\big|\\;[(\\bigcirc{}\\,1\\;[]),(\\bigcirc{}\\,2\\;[])]\\big\\rangle{})$"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"$\\texttt{Just}(\\big\\langle{}\\langle{}(\\lambda{}x.(\\lambda{}y.x)),[]\\rangle{}\\;\\big|\\;[]\\;\\big|\\;[(\\bigcirc{}\\,1\\;[]),(\\bigcirc{}\\,2\\;[])]\\big\\rangle{})$"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"$\\texttt{Just}(\\big\\langle{}1\\;\\big|\\;[]\\;\\big|\\;[(\\langle{}(\\lambda{}x.(\\lambda{}y.x)),[]\\rangle{}\\,\\bigcirc{}),(\\bigcirc{}\\,2\\;[])]\\big\\rangle{})$"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"$\\texttt{Just}(\\big\\langle{}1\\;\\big|\\;[]\\;\\big|\\;[(\\langle{}(\\lambda{}x.(\\lambda{}y.x)),[]\\rangle{}\\,\\bigcirc{}),(\\bigcirc{}\\,2\\;[])]\\big\\rangle{})$"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"$\\texttt{Just}(\\big\\langle{}(\\lambda{}y.x)\\;\\big|\\;[x\\mapsto{}1]\\;\\big|\\;[(\\bigcirc{}\\,2\\;[])]\\big\\rangle{})$"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"$\\texttt{Just}(\\big\\langle{}\\langle{}(\\lambda{}y.x),[x\\mapsto{}1]\\rangle{}\\;\\big|\\;[x\\mapsto{}1]\\;\\big|\\;[(\\bigcirc{}\\,2\\;[])]\\big\\rangle{})$"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"$\\texttt{Just}(\\big\\langle{}2\\;\\big|\\;[]\\;\\big|\\;[(\\langle{}(\\lambda{}y.x),[x\\mapsto{}1]\\rangle{}\\,\\bigcirc{})]\\big\\rangle{})$"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"$\\texttt{Just}(\\big\\langle{}2\\;\\big|\\;[]\\;\\big|\\;[(\\langle{}(\\lambda{}y.x),[x\\mapsto{}1]\\rangle{}\\,\\bigcirc{})]\\big\\rangle{})$"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"$\\texttt{Just}(\\big\\langle{}x\\;\\big|\\;[x\\mapsto{}1,y\\mapsto{}2]\\;\\big|\\;[]\\big\\rangle{})$"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"$\\texttt{Just}(\\big\\langle{}1\\;\\big|\\;[x\\mapsto{}1,y\\mapsto{}2]\\;\\big|\\;[]\\big\\rangle{})$"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"map LaTeX . takeWhile isJust $ iterate (step =<<) (Just(OpE fst_1_2,[],[]))"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Just (OpE (Prm Suc [Lit 3]),[],[])"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"$\\texttt{Just}(\\big\\langle{}\\textsf{Suc}[3]\\;\\big|\\;[]\\;\\big|\\;[]\\big\\rangle{})$"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"Just(OpE(Prm Suc[Lit 3]),[],[])\n",
"step =<< it\n",
"step =<< it\n",
"step =<< it\n",
"step =<< it\n",
"step =<< it\n",
"step =<< it\n",
"step =<< it\n",
"step =<< it\n",
"\n",
"isJust (Just _) = True\n",
"isJust Nothing = False\n",
"\n",
"map LaTeX . takeWhile isJust . iterate (step =<<) $ Just(OpE(Prm Suc[Lit 3]),[],[])"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Just (OpE (Prm Add [Lit 3,Lit 4]),[],[])"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"$\\texttt{Just}(\\big\\langle{}\\textsf{Add}[3,4]\\;\\big|\\;[]\\;\\big|\\;[]\\big\\rangle{})$"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"Just(OpE(Prm Add[Lit 3,Lit 4]),[],[])\n",
"step =<< it\n",
"step =<< it\n",
"step =<< it\n",
"step =<< it\n",
"step =<< it\n",
"step =<< it\n",
"step =<< it\n",
"step =<< it\n",
"step =<< it\n",
"step =<< it\n",
"step =<< it\n",
"\n",
"isJust (Just _) = True\n",
"isJust Nothing = False\n",
"\n",
"map LaTeX . takeWhile isJust . iterate (step =<<) $ Just(OpE(Prm Add[Lit 3,Lit 4]),[],[])"
]
},
{
"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
}