SICP-Spring2018.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 大佬镇楼\n",
    "![大佬](./image/John.png)\n",
    "### 简介\n",
    "伯克利大学CS61系列第一课 ，SICP的Python版本。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "\n",
    "### 1.3 control\n",
    "- 1 python -i 了解一下 interactive\n",
    "- 2 pyton -m 了解一下 -m -i\n",
    "- 3 python -v \n",
    "A statement is:\n",
    "False in Python：False 0 '' None\n",
    "env is a sequence of frames"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from operator import mod,truediv,floordiv\n",
    "mod(2013,5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Quotient"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4 Higher-order function\n",
    "cs98 addtional\n",
    "Fibobacci seq 与贝壳？\n",
    "所有递归均可以用非递归方式实现\n",
    "   自上而下\n",
    "   自下而上的备忘录法\n",
    "   \n",
    "function's domain  边界值\n",
    "function's range  阈值\n",
    "function's behavior\n",
    "one job\n",
    "DRY repeat\n",
    "generally\n",
    "**shared implention：area solution**\n",
    "函数作为从参数传输进去进行 进行generally\n",
    "8/(4k-1)(4k-3) = pi\n",
    "Function are first class:func can be manipulated as a value in program language\n",
    "Higher Order funtion:A function taht takes a function as an arg value or ret a func as a ret value \n",
    "\n",
    "Lambda expression vs def:植物大战僵尸 拉姆达"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "ename": "AssertionError",
     "evalue": " Falee",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-9-2baa5041699e>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[1;32massert\u001b[0m \u001b[1;36m3\u001b[0m \u001b[1;33m<\u001b[0m \u001b[1;36m2\u001b[0m \u001b[1;33m,\u001b[0m\u001b[1;34m' Falee'\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mAssertionError\u001b[0m:  Falee"
     ]
    }
   ],
   "source": [
    "assert 3 < 2 ,' Falee'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def make_adder(n):\n",
    "    def adder(k):\n",
    "        return k+n\n",
    "    return adder"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "make_adder(1)(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "square = lambda x:x*x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.5 Environment for H_O function\n",
    "类似于Python的装饰器？？\n",
    "环境类似于Linux fork()函数\n",
    "frame的概念很重要 关于函数的变量的继承等"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.6 Interation\n",
    "fibnacci seq kth dif = kth+dif,kth\n",
    "\n",
    "A  call staments is: switch back env fx has a value\n",
    "only one ret：fork()??\n",
    "self references\n",
    "\n",
    "WAV Files\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "4\n",
      "9\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<function __main__.print_sum.<locals>.next_sum(y)>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def print_sum(x):\n",
    "    print(x)\n",
    "    def next_sum(y):\n",
    "        return print_sum(x+y)\n",
    "    return next_sum\n",
    "print_sum(1)(3)(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.7  recursive function\n",
    "call himself directly or not\n",
    "different  frames keep diff argument in each call\n",
    "can be tricky:**Iteration is a special case of recursion!**\n",
    "Idea:figure out what state must be cantaintend by the iterative funtion\n",
    "converting iter to recursion: The state can be passed as arguments\n",
    "递归结束条件：\n",
    "    自身满足条件结束\n",
    " Mutual recursion\n",
    " Luhn sum\n",
    " recursion and iteration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def split(n):\n",
    "    return n//10,n%10\n",
    "def sum_digits(n):\n",
    "    if n < 10:\n",
    "        return n\n",
    "    else:\n",
    "        all_but_last, last = split(n)\n",
    "        return sum_digits(all_but_last) + last\n",
    "def luhn_sum():\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum_digits(2013)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.8 Tree recursion\n",
    "![递归注意事项](./image/递归注意事项.png)\n",
    "递归的重复计算太多很影响时间复杂性!以Fobnacci树为例 到35已经挂了\n",
    "by rembering results\n",
    "#### 解决好base case问题 其他交给递归 （感觉很类似于动态规划）\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ucb import trace\n",
    "@trace\n",
    "def cascade(n):\n",
    "    if n < 10:\n",
    "        pass\n",
    "        #print(n)  ## base case  return None\n",
    "    else:\n",
    "        #print(n)\n",
    "        cascade(n//10)\n",
    "        #print(n)\n",
    "def cascade_inverse():\n",
    "    pass\n",
    "\n",
    "@trace\n",
    "def fib(n):\n",
    "    if n<=1:\n",
    "        return n\n",
    "    else:\n",
    "        return fib(n-1) + fib(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "#cascade(12345)\n",
    "#fib(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## countingh partions\n",
    "## description : 把一个数分n为几个数的和 最大数不超过m 求多少种分法\n",
    "def count_partion(n,m):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    elif n < 0:\n",
    "        return 0\n",
    "    elif m == 0 :\n",
    "        return 0\n",
    "    else:\n",
    "        with_m = count_partion(n-m,m)\n",
    "        without_m = count_partion(n,m-1)\n",
    "    return with_m + without_m\n",
    "count_partion(6,4)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.9 Function Examples\n",
    "![If the name is bound to ](./image/function_name.png)\n",
    "函数命名\n",
    "![函数命名](./image/函数命名.png)\n",
    "变量命名\n",
    "![变量命令](./image/变量命名.png)\n",
    "- 1 repeated \n",
    "- 2 names can be long to help depument your code\n",
    "#### Test Driven Development\n",
    "python -m doctest ex.py\n",
    "#### function currying\n",
    "\n",
    "#### Decorators\n",
    "\n",
    "####  Enclosing scope\n",
    "\n",
    "#### "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gcd(m,n):\n",
    "    '''Return the K largest\n",
    "    k , m, n are all pso\n",
    "    >>> gcd(12,8)\n",
    "    4\n",
    "    >>> gcd(16,12)\n",
    "    4\n",
    "    '''\n",
    "    if m == n:\n",
    "        return m\n",
    "    elif m < n:\n",
    "        return gcd(n,m)\n",
    "    else:\n",
    "        return gcd(m-n,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "gcd(4,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.10 Data Abstraction\n",
    "数据抽象的意义 \n",
    "![](./image/Data abstraction.png)\n",
    "#### Pairs\n",
    "#### Abstration Barriers\n",
    "#### Dat a presention\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from operator import getitem\n",
    "pair = [1,2]\n",
    "x, y = pair\n",
    "getitem(pair,0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.11 Containers\n",
    "- List\n",
    "for <name> in <expression>\n",
    "   <suite>\n",
    "索引的左闭右开区间[-2,2)\n",
    "length: 右减左\n",
    "以偏移量作为角标索引\n",
    "- List Comprehensions 推导\n",
    "- sring的元素仍为string\n",
    "- Dict  limitation： key不能为可变的的数据 mutable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 7, 1, 2, 3, 1, 2, 3]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[2,7] + [1,2,3] * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2\n",
      "3 4\n",
      "5 6\n",
      "7 8\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[2, 4]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pairs = [[1,2],[3,4],[5,6],[7,8]]\n",
    "for x,y in pairs:\n",
    "    print(x,y)\n",
    "range(-2,2)\n",
    "y = [1,2,3,4,5]\n",
    "[x for x in y if x%2 == 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 1,\n",
       " 1: 1,\n",
       " 2: 4,\n",
       " 3: 27,\n",
       " 4: 256,\n",
       " 5: 3125,\n",
       " 6: 46656,\n",
       " 7: 823543,\n",
       " 8: 16777216,\n",
       " 9: 387420489}"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{x:x**x for x in range(10)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.12 mutable values\n",
    "\n",
    "#### unicode standard\n",
    "- 109000 charters\n",
    "- 93 scripts\n",
    "enumeration of charter properties\n",
    "\n",
    "#### mutation change\n",
    "dict.pop(key)\n",
    "#### tuples are sequence but they are not mutable sequence\n",
    "tuple 不能被改变 用户保护数据 类似于c const？？\n",
    "**tuple 不能改变 但是元素可以改变！！**\n",
    "\n",
    "#### 'is' and '=='\n",
    "- is evaluate to Ture if both a and b evaluates the same object\n",
    "- == evaluate to True if both a and b evaluates the same value\n",
    "identical object are always the same value\n",
    "#### mutable values as default arg are dangerous\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u0007\u0007\u0007\n",
      "65 0x41\n"
     ]
    }
   ],
   "source": [
    "from datetime import date\n",
    "print('\\a\\a\\a') #bell\n",
    "a = 'A'\n",
    "print(ord(a),hex(65))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "([1, 2, 3], 4, 5)\n"
     ]
    }
   ],
   "source": [
    "from unicodedata import lookup\n",
    "lookup('BABY')\n",
    "a = ([1,2,3],4,5)\n",
    "\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "([1, 6, 3], 4, 5)\n"
     ]
    }
   ],
   "source": [
    "a[0][1] = 6 \n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "def f(s = []):\n",
    "    s.append(1)\n",
    "    return len(s)\n",
    "for i in  range(5):\n",
    "    print(f()) really dangerous"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.14 mutable functions\n",
    "\n",
    "#### nonlocal statement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.15 oriented-object programming\n",
    "invoking methods\n",
    "function and method\n",
    "![](./image/functionandmethod.png)\n",
    "attribute 很奇怪 为什么可以保存不存在的attr\n",
    "![](./image/attribute.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.6 inheriate\n",
    "base class 的attribute 不会拷贝到subclass\n",
    "- attribute lookup\n",
    "![](./image/attribute_lookup.png)\n",
    "- complicated ingeritance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.7 Represention\n",
    "#### str and repr\n",
    "#### polymorphic functions  多态函数\n",
    "- how implement this behavior\n",
    "#### interface\n",
    "#### special method names\n",
    "- always with two underscores\n",
    "- __add__ __str__ __booler__  __float__\n",
    "- 类似于实现多态或者重载 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Fraction(1, 2)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    ">>> from fractions import Fraction\n",
    ">>> half = Fraction(1,2)\n",
    ">>> repr(half)\n",
    "'Fraction(1, 2)'\n",
    ">>> eval(repr(half))\n",
    "Fraction(1, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.18 Growth\n",
    "#### measuring efficency\n",
    "#### idea: remeber the result has been computed\n",
    "- 装饰器太爽吧 好好看一下\n",
    "- The consumption of Tine\n",
    "- 求一个数的因数数目。采用平方根的方法快很多。\n",
    "- Order of Growth\n",
    "  - constant does not affect\n",
    "  - The base of logarithm does not affetx  log2等效log10 \n",
    "  O(b^n)\n",
    "  O(n^2)\n",
    "  O(n)\n",
    "  O(n^0.5)\n",
    "  O(logn)\n",
    "  O(1)\n",
    "- Exponentiation\n",
    "\n",
    "b^n 按照n的奇数偶数来分"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55\n",
      "55 177\n",
      "55 19 188\n"
     ]
    }
   ],
   "source": [
    "### 好好理解一下下面代码\n",
    "def fib(n):\n",
    "    if n <= 1:\n",
    "        return n\n",
    "    else:\n",
    "        return fib(n-1) + fib(n-2)\n",
    "def count(f):\n",
    "    def counted(n):\n",
    "        counted.call_count += 1\n",
    "        return f(n)\n",
    "    counted.call_count = 0\n",
    "    return counted\n",
    "def memo(f):\n",
    "    cache = {}\n",
    "    def memoized(n):\n",
    "        if n not in cache:\n",
    "            cache[n] = f(n)\n",
    "        return cache[n]\n",
    "    return memoized\n",
    "print(fib(10))\n",
    "fib = count(fib)\n",
    "print(fib(10),fib.call_count)\n",
    "counted_fib = fib\n",
    "fib = memo(fib)\n",
    "fib = count(fib)\n",
    "print(fib(10),fib.call_count,counted_fib.call_count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ucb import trace\n",
    "\n",
    "@trace\n",
    "def exp(b,n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return b * exp(b,n-1)\n",
    " \n",
    "@trace\n",
    "def fast_exp(b,n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    elif n % 2 == 0:\n",
    "        return square(fast_exp(b,n//2))\n",
    "    else:\n",
    "        return b * fast_exp(b,n-1)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "exp(10, 5):\n",
      "    exp(10, 4):\n",
      "        exp(10, 3):\n",
      "            exp(10, 2):\n",
      "                exp(10, 1):\n",
      "                    exp(10, 0):\n",
      "                    exp(10, 0) -> 1\n",
      "                exp(10, 1) -> 10\n",
      "            exp(10, 2) -> 100\n",
      "        exp(10, 3) -> 1000\n",
      "    exp(10, 4) -> 10000\n",
      "exp(10, 5) -> 100000\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "100000"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "exp(10,5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.19 composition\n",
    "- Linked  list\n",
    "- property methods\n",
    "- Tree class \n",
    "- Tree Mutation\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert 1 is 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.20 set\n",
    "s.union\n",
    "s.intersection\n",
    "s.add()\n",
    "#### implementing sets\n",
    "#### sets as linked liked list\n",
    " - searching an ordered list\n",
    " - set operations\n",
    " def intersect(set1,set2)\n",
    " - set mutation\n",
    " \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.21 Binary Tree\n",
    "#### Binary search ：check the middle and eliminate half\n",
    "#### Bnary search Trees:\n",
    "- The biggest element in bst :最右\n",
    "- The second biggest Tree\n",
    "![](./image/BiggestElementInTree.png)\n",
    "#### membership in BST\n",
    "每次折半 时间复杂度为logn\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random  import shuffle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.22 Data Examples\n",
    "- List\n",
    "- append extend  addation %slicing\n",
    "- list in list\n",
    "![](./image/list_dataex.png)\n",
    "####  environment diagram  \n",
    "- frame\n",
    "- parent frame\n",
    "#### objects\n",
    "- instance\n",
    "![](./image/objects_john.png)\n",
    "#### recursive link\n",
    "\n",
    "#### morse code\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, [...], 1, [...]] 4\n"
     ]
    }
   ],
   "source": [
    "t = [1,2,3]\n",
    "t[1:3] = [t]\n",
    "t.extend(t)\n",
    "print(t,len(t[1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Worker:\n",
    "    g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.24\n",
    "#### scheme\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.25 Exceptions\n",
    "exceptions\n",
    "![](./image/exceptions.png)\n",
    "#### rasing exception\n",
    "- assert <expression>,<string>\n",
    "    assert \n",
    "    python -0 ex.py\n",
    "    \n",
    "#### TypeErr KeyErr NameErr  RuntimeErr(递归过深等)\n",
    "\n",
    "#### Try statement\n",
    "\n",
    "#### WWPD\n",
    "\n",
    "#### Reduce：\n",
    " - reduce a sequence to a value\n",
    "#### Sierpinski's triangle\n",
    "- "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "Bad",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-38-3b635fc5af21>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[1;32mraise\u001b[0m \u001b[0mTypeError\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"Bad\"\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      2\u001b[0m \u001b[1;32mdef\u001b[0m \u001b[0mf\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      3\u001b[0m     \u001b[0mf\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mTypeError\u001b[0m: Bad"
     ]
    }
   ],
   "source": [
    "raise TypeError(\"Bad\")\n",
    "def f():\n",
    "    f()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'reduce' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-41-6e8e7f9b87a9>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;32mfrom\u001b[0m \u001b[0moperator\u001b[0m \u001b[1;32mimport\u001b[0m \u001b[0madd\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m \u001b[0mreduce\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0madd\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m3\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m4\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mNameError\u001b[0m: name 'reduce' is not defined"
     ]
    }
   ],
   "source": [
    "from operator import add\n",
    "reduce(add,[1,2,3],4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.26 calculator\n",
    "##### Interpreters\n",
    "#### parsing\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.27 Interpreters\n",
    "Base cases:\n",
    "- scheme evaluation\n",
    "- logical special forms\n",
    "- Quotation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.28 Tail calls\n",
    "####  Dynamic scope\n",
    "#### lexical scope\n",
    "#### tail recursion\n",
    "#### functional programming \n",
    "#### 尾调用 linear recursive can always be re-write as tail call\n",
    "\n",
    "### Map and Reduce Google 论文大作\n",
    "\n",
    "#### An analogy: programs specific machine\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4]"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(map(abs,[1,2,3,-4]))\n",
    "reduce()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.29 Macros\n",
    "### 1.30 Iterators\n",
    "#### Data processing\n",
    "- process squeential data\n",
    " - sequence interface\n",
    " - has a finite known lengrh\n",
    " - allows element selection\n",
    "- big data processing\n",
    "- Distributed and parallel computing\n",
    "#### Iterators \n",
    "   - iter return an iterator\n",
    "   - next return the next element in an iterator\n",
    "#### For statements\n",
    "- when exe for statements ,iter  returns an iterator and next provides each item\n",
    "- A StopIteration exception is raised when  next is called on empty iterator\n",
    "#### bulit-in iterator fnctions  注意啊 iterable\n",
    "- map() filter(f,iterable) zip() reversed() \n",
    "![](./image/built-in-iterator.png)\n",
    "![](./image/bulit-in-iter-function.png)\n",
    "\n",
    "\n",
    "#### Generator and generator func\n",
    "- yield\n",
    "#### generator and iterator\n",
    "- genor can Yield from iterator\n",
    "- yield from 语法 \n",
    "\n",
    "   \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "s =[11,2,3]\n",
    "t = iter(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "ename": "StopIteration",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mStopIteration\u001b[0m                             Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-49-1376cbf80061>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mnext\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mt\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      2\u001b[0m \u001b[0mlist\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mt\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "next(t)\n",
    "list(t)  ## 结束迭代"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = {'1':2,'2':'two'}\n",
    "k = iter(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1'"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'two'"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d.pop('2')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False True\n",
      "[('1', 'one'), ('2', 'two')]\n",
      "[2, 4, 6, 8]\n",
      "3\n",
      "2\n",
      "1\n",
      "[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "### attention\n",
    "t = [1,2,3,2,1]\n",
    "print(t == reversed(t),t == list(reversed(t)))\n",
    "\n",
    "d = {'1':'one','2':'two'}\n",
    "items = zip(d.keys(),d.values())\n",
    "print(list(items))\n",
    "\n",
    "\n",
    "## generator\n",
    "def evens(start,end):\n",
    "    even = start + (start % 2)\n",
    "    while even < end:\n",
    "        yield even\n",
    "        even += 2\n",
    "g = evens(2,10)\n",
    "print(list(g))\n",
    "\n",
    "def cntdown(k):\n",
    "    if k > 0:\n",
    "        yield k\n",
    "        yield from cntdown(k-1)\n",
    "for k in cntdown(3):\n",
    "    print(k)\n",
    "print(list(cntdown(10)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.31 streams\n",
    "#### efficent sequence operations\n",
    "#### all() 函数怎么操作的\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all(map(lambda y: 1 % y,range(1,6)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.32 declarative programming\n",
    "#### DataBase Management system DBMS\n",
    " declarrative langusge\n",
    "![](./image/declarative.png)\n",
    "#### arithmetic\n",
    "### 1.33 Tables\n",
    "pass\n",
    "### 1.34 aggregation\n",
    "- SQL专属\n",
    "- pass\n",
    "#### 1.35 DataBase\n",
    "- pass\n",
    "#### 1.36 Distributed Data\n",
    "- Unix\n",
    "- Computer System\n",
    "  - Operate System\n",
    "  - Networks\n",
    "  - DataBase\n",
    "  - Dis sys\n",
    " - Hide complexity but retain flexablity\n",
    " - stdin ----> process -----> stdout\n",
    "            |\n",
    "            | std err   \n",
    "\n",
    "- sys.stdin  sys.std.out\n",
    "- Big Data\n",
    "- Apache Spark\n",
    "\n",
    "![](./image/DistributedDataset.png)\n",
    "\n",
    "- MapReduce\n",
    "   - An important early distributed prossing system developed by google\n",
    "   \n",
    " ![](./image/MapReduceApp.png)\n",
    " ![](./image/MpRe-model.png)\n",
    " \n",
    " \n",
    " \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.37 Natual language\n",
    "#### Ambiguity\n",
    "- **Programs must be written for people to read!** ---> preface of SICP\n",
    "- Syntax Trees\n",
    "  - buffalo \n",
    "- Recursive Tree\n",
    "- Grammars\n",
    "- Parsing\n",
    "- Learning\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*end*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "currying\n",
    "rational\n",
    "odd\n",
    "compound\n",
    "civil\n",
    "Comprehensions\n",
    "closure\n",
    "hierarachical \n",
    "polymorphic\n",
    "arbitrary\n",
    "scheme\n",
    "dialate\n",
    "quotient\n",
    "liberally\n",
    "useless\n",
    "spatial\n",
    "lextical analysis\n",
    "tokens\n",
    "tail\n",
    "middlemen\n",
    "macros\n",
    "evaluation\n",
    "Vote cast\n",
    "declarative\n",
    "imperative\n",
    "arithmetic\n",
    "ambiguity\n",
    "intimidate\n",
    "invoke\n",
    "\n",
    "\n",
    "\n",
    "柯里\n",
    "合理的\n",
    "奇\n",
    "复合\n",
    "国内\n",
    "推导\n",
    "关闭\n",
    "hierarachical\n",
    "多态\n",
    "随意\n",
    "方案\n",
    "dialate\n",
    "商\n",
    "宽松\n",
    "无用\n",
    "空间的\n",
    "lextical分析\n",
    "令牌\n",
    "尾巴\n",
    "中间商\n",
    "宏\n",
    "评测\n",
    "投票\n",
    "陈述\n",
    "势在必行\n",
    "算术\n",
    "歧义\n",
    "威吓\n",
    "调用"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  },
  "widgets": {
   "state": {},
   "version": "1.1.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}