Intro01.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "1.1에는 우리가 보통 고급언어(high-level language)라고 부르는 언어들이 대략 어떤 부류가 있는지 컴퓨터 관련 학과에서\n",
    "풍월로 들었을 만한 이야기를 소개한다.\n",
    "\n",
    "범용(general-purpose) 프로그래밍 언어의 대표적인 4가지 유형은 명령형(imperative), 함수형(functional), 논리(logic), 객체지향(object-oriented)이다.\n",
    "참고로 책의 1장에 굳이 언급되지 않았지만 사족을 달자면, 최근에는 두 가지 이상의 유형을 (특히 객체지향과 함수형을) 같이 잘 지원하겠다는 범용 프로그래밍 언어들이\n",
    "늘어나는 추세이고 이런 언어들을 다중 패러다임 언어라고 부르기도 함.\n",
    "\n",
    "그 외에도 특수목적(special-purpose) 프로그래밍 언어로 볼 수 있는 것들이 있다.\n",
    "예를 들면 하드웨어 기술(hardware description), 운영체제 등에서 명령 실행, 조판 및 마크업 등 특수한 활용 목적을 염두에 두고 설계된 언어들도 있다.\n",
    "참고로 책의 1장에는 굳이 언급되지 않았지만 사족을 달자면, 처음에는 특수목적 언어로 설계되어 쓰이다가 세월이 흘러 지금에 와서는 업계에서 몇손가락 안에 들 정도로 많이 쓰이는 범용 언어가 되어버린 JavaScript 같은 특이한 사례도 있다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "1.2에는 프로그래밍언어를 구현하는 두 가지 방법인 인터프리터(1.2.1)와 컴파일러(1.2.2)의 개념을 정리하여 소개한다.\n",
    "\n",
    "1.2.3에서는 실제 기계(real maachine) 가상머신(virtual machine, VM)의 개념을 소개한다.\n",
    "\n",
    "1.2.4에서는 가상머신을 더욱 효율적으로 실행하기 위한 Just-In-Time (JIT) 컴파일에 대해 간단히 언급한다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "그럼 1.1.2와 1.2.2에 나온 인터프리터와 컴파일러에 대해 우리 나름대로 정리해 보자.\n",
    "\n",
    "* 소스(source) 언어 $L$의 의미를 충실하게 구현한 인터프리터를 $I_L$이라고 표기하자.\n",
    "* 이 $L$ 언어를 컴파일하는 대상(target)이 되는 가상머신 명령어를 $M$이라고 하자.<br>\n",
    "  (참고로 가상머신의 기계어에 해당하는 명령어를 흔히 *bytecode*라 부르기도 함)\n",
    "* 가상머신은 명령어 이루어진 프로그램을 실행시켜주는 인터프리터라고 볼 수 있으므로 가상머신을 $I_M$이라 표기하자.\n",
    "* $L$의 문법에 맞게 작성된 프로그램을 $p_L$로 표기하자. (즉, $p_L\\in L$)\n",
    "* $M$의 문법에 맞게 작성된 프로그램를 $p_M$으로 표기하자. (즉 $p_M\\in M$)\n",
    "\n",
    "책에 오타가 있는데, $I_L$을 함수로 정의한다면 그 형태(혹은 타입)은 아래와 같다.<br>\n",
    "여기서 $D$는 프로그램이 입력으로 받아들이거나 출력으로 내보낼 수 있는 모든 데이터의 집합을 의미한다.\n",
    "\n",
    "$I_L : L \\times D \\to D\\cup\\{\\textit{error}\\}$\n",
    "\n",
    "마찬가지로 가상머신에 대해서도\n",
    "\n",
    "$I_M : M \\times D \\to D\\cup\\{\\textit{error}\\}$\n",
    "\n",
    "컴파일러를 함수 $C$로 나타낸다면 그 타입은 다음과 같다.\n",
    "\n",
    "$C : L \\to M$\n",
    "\n",
    "올바르게 구현된 컴파일러 $C$는 다음과 같은 성질을 만족해야 한다.\n",
    "\n",
    "$C(p_L) = p_M$일 때,<br>\n",
    "$I_L(p_L, d) = a$ 이면 $I_M(p_M, d) = a$\n",
    "\n",
    "이런 컴파일러가 있다면 $I_L(p_L, d)$을 실행하는 대신에,\n",
    "우선 $C(p_L) = p_M$으로 미리 컴파일해 놓고 $I_M(p_M, d)$ 즉 $I_M(C(p_L), d)$ 을 실행하여 같은 결과를 얻을 수 있다.\n",
    "\n",
    "이 때 $p_L$을 소스 프로그램(*원시 코드*라고도 함)이라고 하며 이를 컴파일해 얻은 $p_M$ 대상 프로그램(*목적 코드* 라고도 함)이라고 한다.\n",
    "\n",
    "전통적인 컴파일러는 컴파일 작업 $C(p_L) = p_M$을 끝마치고 난 다음에 결과로 나온  $p_M$을 가지고 $I_M(p_M, d)$을 실행한다. \n",
    "\n",
    "그래서 $C(p_L) = p_M$의 계산이 이루어지는 것을 컴파일 타임이라 하고 $I_M(p_M, d)$을 실행하는 것을 런타임이라고 부른다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "{-# LANGUAGE NoMonomorphismRestriction #-}\n",
    "{-# LANGUAGE FlexibleInstances #-}\n",
    "{-# LANGUAGE FlexibleContexts #-}\n",
    "\n",
    "-- 고급언어\n",
    "data L  = Val Int  -- 정수값 상수\n",
    "        | Add L L  -- p1 + p2\n",
    "        | Mul L L  -- p1 * p2\n",
    "        deriving (Eq, Ord, Show)\n",
    "\n",
    "-- 저급언어\n",
    "type M = [ Instr ] -- 명령어 프로그램은 그냥 명령을 일렬로 나열한 리스트\n",
    "\n",
    "data Instr = LOADc Int | ADD | MUL\n",
    "        deriving (Eq, Ord, Show)\n",
    "\n",
    "type Stack = [ Value ] -- 스택머신의 기계상태는 그냥 스택으로만 표현\n",
    "type Value = Int"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "pL = Mul (Add (Val 3) (Val 4)) (Val 5)  -- (3 + 4) * 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "interpL :: L -> Value\n",
    "interpL (Val v)     = v\n",
    "interpL (Add e1 e2) = interpL e1 + interpL e2\n",
    "interpL (Mul e1 e2) = interpL e1 * interpL e2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "interpL (Val 3)\n",
    "interpL (Val 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "interpL (Add (Val 3) (Val 4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "35"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "interpL pL"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "interpM :: M -> Value\n",
    "interpM = head . foldl (flip step) []\n",
    "-- interpM []     vs = head vs\n",
    "-- interpM (i:is) vs = interpM is (step i)\n",
    "\n",
    "step :: Instr -> Stack -> Stack\n",
    "step (LOADc v)  vs  =     v : vs\n",
    "step ADD (v2:v1:vs) = v1+v2 : vs\n",
    "step MUL (v2:v1:vs) = v1*v2 : vs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[23,13,14,15,16,17]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "step ADD [11,12,13,14,15,16,17]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "step (LOADc 3) []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4,3]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "step (LOADc 4) [3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "step ADD [4,3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "interpM [LOADc 3, LOADc 4, ADD]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[13,14,15,16,17]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "v2:v1:vs = [11,12,13,14,15,16,17]\n",
    "15\n",
    "v2 -- 11\n",
    "v1 -- 12\n",
    "vs -- [13,14,,16,17]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[35]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "-- interpM\n",
    "foldl (flip step) [] [LOADc 3, LOADc 4, ADD, LOADc 5, MUL]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[1,2] ++ [3,4,5] ++ [6,7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "compile :: L -> M\n",
    "compile (Val v)     = [LOADc v]\n",
    "compile (Add e1 e2) = compile e1 ++ compile e2 ++ [ADD]\n",
    "compile (Mul e1 e2) = compile e1 ++ compile e2 ++ [MUL]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "pL = Mul (Add (Val 3) (Val 4)) (Val 5)  -- (3 + 4) * 5\n",
    "pM = compile pL"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Mul (Add (Val 3) (Val 4)) (Val 5)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[LOADc 3,LOADc 4,ADD,LOADc 5,MUL]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "pL\n",
    "pM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "35"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "35"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "interpL pL\n",
    "interpM pM"
   ]
  },
  {
   "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",
   "mimetype": "text/x-haskell",
   "name": "haskell",
   "pygments_lexer": "Haskell",
   "version": "9.4.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}