{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Little Schemer\n",
    "\n",
    "## 1) Toys"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`atom`是什么?\n",
    "- 字符串\n",
    "- 符号\n",
    "- 数字\n",
    "- 字符"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(atom? 'atom)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(atom? 123)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(atom? (quote a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(atom? \"abc\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`list`是什么? \n",
    "- 括号包围?\n",
    "- 一组括号包围的`atom`?\n",
    "- 一组括号包围的`S-expression`\n",
    "\n",
    "`car`, 列表第一个元素\n",
    "`cdr`, 列表除第一个外的元素列表\n",
    "\n",
    "`(cons a. b)`, `a`为任一`S-expression`, `b`为任一列表."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(list? '(atom))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(list? '(atom turkey or))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(list? '())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(atom? '()) ;; '() 表示空, 和空列表的意义重叠了"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(list? '(() () () ()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((hotdogs))"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(car '(((hotdogs)) (and) (pickle) relish))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\u001b[0;31m\n",
      "Traceback (most recent call last):\n",
      "  File \"In [16]\", line 1, col 1, in 'car'\n",
      "  File \"In [16]\", line 1, col 1\n",
      "RunTimeError: car called on non-pair ()\n",
      "\n",
      "\u001b[0m"
     ]
    }
   ],
   "source": [
    "(car '()) ;; car处理非空列表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\u001b[0;31m\n",
      "Traceback (most recent call last):\n",
      "  File \"In [17]\", line 1, col 1, in 'cdr'\n",
      "  File \"In [17]\", line 1, col 1\n",
      "RunTimeError: cdr called on non-pair ()\n",
      "\n",
      "\u001b[0m"
     ]
    }
   ],
   "source": [
    "(cdr '()) ;; cdr处理非空列表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(x y z)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(cdr '((a b c) x y z))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(((help) this) is very ((hard) to learn))"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(define s '((help) this))\n",
    "(define l '(is very ((hard) to learn)))\n",
    "(cons s l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`S-expression`是什么?\n",
    "- `atom`\n",
    "- `list`\n",
    "\n",
    "`Scheme`里的所有东西都是`S-expression`?\n",
    "\n",
    "https://www.quora.com/In-Scheme-is-everything-an-expression\n",
    "\n",
    "什么为空, 空的判定:\n",
    "\n",
    "- `'()`代表空\n",
    "- `(null? ..)`判定是否为空"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(null? '())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`(eq? ..)`的定义: 比较两个参数是否相等, 参数必须都是非数值的`atom`.\n",
    "\n",
    "实际中不做这个严格定义. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(eq? 1 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(eq? '() '())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#f"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(eq? '(a b) '(a b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(eq? 'a 'a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2) Do it, Do it again, and again..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义`(lat? )`方法, 用于判断列表元素是否都是`atom`. \n",
    "\n",
    "用到了递归, 递归的核心是发现一个问题内在的结构, 逐步缩小问题规模, 直到停止条件."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (lat? l)\n",
    "  (cond\n",
    "   ((null? l) #t)\n",
    "   ((atom? (car l)) \n",
    "    (lat? (cdr l)))\n",
    "   (else #f)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(lat? '(a b c))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#f"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(lat? '((Jack) tom sprat)) ;; '(Jack) 是列表, 不是atom"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义`(member? a lat)`方法, 用来判断一个`atom`是否是一个列表的元素. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (member? a lat)\n",
    "  (cond\n",
    "   ((null? lat) #f)\n",
    "   ((eq? a (car lat)) #t)\n",
    "   (else (member? a (cdr lat)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(member? 'a '(b a c))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3) Cons the Magnificent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义`(rember a lat)`方法, 从一个列表中移除一个元素. \n",
    "\n",
    "`cons`加递归, 不断构建新列表的时候, 在原始列表元素等于查询`a`时, 跳过它, 从而在最终生成的列表中移除了`a`.\n",
    "\n",
    "这里实际实现的是后面的`multirember`方法. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (rember a lat)\n",
    "  (cond\n",
    "    ((null? lat) lat)\n",
    "    ((eq? a (car lat)) (rember a (cdr lat)))\n",
    "    (else\n",
    "     (cons (car lat) (rember a (cdr lat))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(b c d)"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(rember 'a '(b a c d))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(b c d)"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(rember 'a '(b a c a d a))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义`(first l)`, 从一个元素均为列表的列表中, 提取每个元素的第一个元素, 组成一个新的列表.\n",
    "\n",
    "缺点是对与`(() (..) (..))`之类存在空列表元素的情况没有处理.\n",
    "\n",
    "这里一个所谓重要\"教条\"是, `cons`构建列表时, 第一个参数是典型基本元素, 第二个参数是一个递归过程. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (first l)\n",
    "  (cond\n",
    "   ((null? l) l)\n",
    "   (else\n",
    "    (cons (car (car l)) (first (cdr l))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(five four eleven)"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(first '((five plums) (four) (eleven green oranges)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(() 1)"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(cons '() '(1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义`(insertR new old lat)`方法, 在old右侧, 插入new.\n",
    "\n",
    "两个步骤:\n",
    "\n",
    "- 找到old, 找到后插入new, 然后终止递归程序.\n",
    "- 构建新列表\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (insertR new old lat)\n",
    "  (cond\n",
    "   ((null? lat) lat)\n",
    "   ((eq? old (car lat)) \n",
    "    (cons \n",
    "     (cons (car lat) new)\n",
    "     (cdr lat)))\n",
    "   (else\n",
    "    (cons (car lat) (insertR new old (cdr lat))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a b c (d . e) f g d h)"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(insertR 'e 'd '(a b c d f g d h))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对应的也能写出`insertL`, 略."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4) Numbers Games"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "数值是什么?\n",
    "\n",
    "- 整数\n",
    "    - `14`\n",
    "    - `-3`\n",
    "- 实数\n",
    "    - `3.14159`\n",
    "   \n",
    "数值是`atom`. \n",
    "\n",
    "假设我们有两个基本操作`add1`, `sub1`, 依靠这两个基本操作构建自然数计算系统."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (add1 x)\n",
    "  (+ x 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (sub1 x)\n",
    "  (- x 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(zero? 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (plus n m)\n",
    "  (cond \n",
    "   ((zero? m) n)\n",
    "   (else\n",
    "    (plus (add1 n) (sub1 m)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(plus 1 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (minus n m)\n",
    "  (cond\n",
    "   ((zero? m) n)\n",
    "   (else\n",
    "    (minus (sub1 n) (sub1 m)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(minus 3 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`plus`, `minus`方法都不能处理负数的情况, 终止条件不对.\n",
    "\n",
    "给出`tuple`的定义, 一个元素都是相同类型的列表. 其它语言中, `tuple`可能还有不可变等特点, scheme中list本身是不变的, 因此不用强调.\n",
    "\n",
    "此处`tuple`和`list`本质上是一类东西, 操作, 和递归条件的判定都是一致的.\n",
    "\n",
    "定义`(addtup tup)`方法, 将tuple中的数字加和. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (addtup tup)\n",
    "  (cond\n",
    "   ((null? tup) 0)\n",
    "   (else\n",
    "    (+ (car tup) (addtup (cdr tup))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(addtup '(1 2 3 4 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义乘法."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (multiply n m)\n",
    "  (cond\n",
    "   ((zero? m) 0)\n",
    "   ((eq? m 1) n)\n",
    "   (else\n",
    "    (+ n (multiply n (- m 1))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(multiply 3 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义`(tup+ t1 t2)`方法, 计算两个tuple相加的结果. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (tup+ t1 t2)\n",
    "  (cond \n",
    "   ((null? t1) t2)\n",
    "   ((null? t2) t1)\n",
    "   (else\n",
    "    (cons (+ (car t1) (car t2))\n",
    "          (tup+ (cdr t1) (cdr t2))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(5 7 9 8)"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(tup+ '(1 2 3 8) '(4 5 6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (gt? n m)  ;; > \n",
    "  (cond\n",
    "   ((zero? n) #f)\n",
    "   ((zero? m) #t)\n",
    "   (else (gt? (sub1 n) (sub1 m)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#f"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(gt? 3 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (lt? n m)\n",
    "  (cond\n",
    "   ((zero? m) #f)\n",
    "   ((zero? n) #t)\n",
    "   (else (lt? (sub1 n) (sub1 m)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(lt? 3 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (eq_? n m)\n",
    "  (cond\n",
    "   ((gt? n m) #f)\n",
    "   ((lt? n m) #f)\n",
    "   (else #t)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(eq_? 3 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (pow n m)\n",
    "  (cond\n",
    "   ((eq? m 0) 1)\n",
    "   ((eq? m 1) n)\n",
    "   (else\n",
    "    (multiply n (pow n (sub1 m))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(pow 2 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义除法`(divide n m)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (divide n m)\n",
    "  (cond\n",
    "   ((lt? n m) 0)\n",
    "   (else\n",
    "    (add1 (divide (- n m) m)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(divide 10 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(length '(1 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义函数`(eqan? s1 s2)`, 用于添加比较两个数相等的逻辑."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (eqan? s1 s2)\n",
    "  (cond\n",
    "   ((and (number? s1) (number? s2))\n",
    "    (= s1 s2))\n",
    "   ((or (number? s1) (number? s2))\n",
    "    #f)\n",
    "   (else\n",
    "    (eq? s1 s2))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(eqan? \"1\" \"1\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5) Oh My Gawd: It's Full of Stars"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`rember*`表示遍历整个结构, 去掉`a`, 而非`rember`,只是去掉首层的`a`.\n",
    "\n",
    "对一个子结构递归, 就是深入到了其中.\n",
    "\n",
    "相比较之前的`rember`等递归函数.\n",
    "\n",
    "检查条件由:\n",
    "\n",
    "1. `(null? )`\n",
    "2. `(else cdr)`\n",
    "\n",
    "变成了:\n",
    "\n",
    "1. `(null? )`\n",
    "2. `(atom? car)`\n",
    "3. `(else cdr)`\n",
    "\n",
    "这个结构大体是通用的."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (rember* a lat)\n",
    "  (cond \n",
    "   ((null? lat) lat)\n",
    "   ((atom? (car lat))\n",
    "    (cond\n",
    "     ((eq? (car lat) a) (rember* a (cdr lat)))\n",
    "     (else\n",
    "      (cons (car lat) (rember* a (cdr lat))))))\n",
    "   (else\n",
    "    (cons \n",
    "     (rember* a (car lat))\n",
    "     (rember* a (cdr lat))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((b) b d e (e f))"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(rember* 'a '((a b) a b d e a (e a f)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (leftmost lat)\n",
    "  (cond\n",
    "   ((atom? (car lat)) (car lat))\n",
    "   (else \n",
    "    (leftmost (car lat)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "foo"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(leftmost '((((foo) bar) test) all)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "回头看如何比较两个列表相等:\n",
    "\n",
    "- 都为空, #t\n",
    "- 一个为空, #f\n",
    "- 第一个元素都是`atom`时\n",
    "- 有一个第一个元素是`atom`, #f\n",
    "- 第一个元素都是列表时"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (eqlist? l1 l2)\n",
    "  (cond\n",
    "   ((and (null? l1) (null? l2)) #t)\n",
    "   ((or (null? l1) (null? l2)) #f)\n",
    "   ((and (atom? (car l1)) (atom? (car l2)))\n",
    "    (and (eqan? (car l1) (car l2))\n",
    "         (eqlist? (cdr l1) (cdr l2))))\n",
    "   ((or (atom? (car l1)) (atom? (car l2))) #f)\n",
    "   (else\n",
    "    (and\n",
    "     (eqlist? (car l1) (car l2))\n",
    "     (eqlist? (cdr l2) (cdr l2))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#f"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(eqlist? '((1 2) \"a\") '((1 3) \"b\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(eqlist? '((1 2) \"a\") '((1 2) \"a\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "复习`S-expression`的语法定义: `atom`或是包含`S-expression`的`list`.\n",
    "\n",
    "这种结构定义可以用文字描述, 也可以用`BNF`等语言来表达. \n",
    "根据这个结构, 可以写出对应语法的解析器, 也可以写出一般的功能函数. 这些程序的结构也是类似的,  使用递归自上而下的遍历.\n",
    "\n",
    "现在定义函数`(equal_? s1 s2)`, 用来比较两个`S-expression`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (equal_? s1 s2)\n",
    "  (cond\n",
    "   ((and (atom? s1) (atom? s2))\n",
    "    (eqan? s1 s2))\n",
    "   ((or (atom? s1) (atom? s2)) #f)\n",
    "   (else\n",
    "    (eqlist? s1 s2))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(equal_? 'a 'a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(equal_? '(a b 1) '(a b 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6) Shadows"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "首先定义`算数表达式`:\n",
    "\n",
    "- `atom`\n",
    "- 使用`+`, `*`, `^`两两组合的算数表达式.\n",
    "\n",
    "定义函数`(numbered? aexp)`, 用于判断`aexp`是否是一个算数表达式."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (numbered? aexp)\n",
    "  (cond\n",
    "   ((atom? aexp) (number? aexp))\n",
    "   (else\n",
    "    (and (numbered? (car aexp))\n",
    "         (numbered? (car (cdr (cdr aexp))))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(numbered? '(1 + (3 * 2) + a)) ;; 连加/乘的形式不处理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义求值函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (value aexp)\n",
    "  (cond \n",
    "   ((atom? aexp) aexp)\n",
    "   ((eq? (car (cdr aexp)) '+) \n",
    "    (+ \n",
    "     (value (car aexp))\n",
    "     (value (car (cdr (cdr aexp))))))\n",
    "   ((eq? (car (cdr aexp)) '*)\n",
    "    (*\n",
    "     (value (car aexp))\n",
    "     (value (car (cdr (cdr aexp))))))\n",
    "   ((eq? (car (cdr aexp)) '^)\n",
    "    (pow\n",
    "     (value (car aexp))\n",
    "     (value (car (cdr (cdr aexp))))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(value '(1 + (2 ^ 3)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一种新的数字表示形式:\n",
    "\n",
    "- `'()`代表0, `'(())`代表1, `'(() ())`代表2, 依次类推.\n",
    "- 四个基本操作\n",
    "    - `zero?`\n",
    "    - `number?`\n",
    "    - `add1`\n",
    "    - `sub1`\n",
    "\n",
    "就可以构建计算系统, 代码与前面的`plus`, `minus`, `pow`, `gt?`, `lt?`, `eq_?`等类似. 这表现了抽象的威力.\n",
    "\n",
    "另一种Church Encoding, 也类似, 用Lambda表达式和函数调用层次表示数字. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7) Friends and Relations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`集合`是什么? 一组互不相同的元素组成的列表.\n",
    "\n",
    "集合, 元素与集合, 集合与集合."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (set? lat)\n",
    "  (cond\n",
    "   ((null? lat) #t)\n",
    "   ((member? (car lat) (cdr lat)) #f)\n",
    "   (else\n",
    "    (set? (cdr lat)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(set? '(1 2 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#f"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(set? '(1 1 2 3 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "复杂度比较高$O(n^2)$, 使用`hashmap`可以降到$O(n)$, 使用排序, 能到$O(nlogn)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (makeset lat)\n",
    "  (cond\n",
    "   ((null? lat) lat)\n",
    "   ((member? (car lat) (cdr lat)) (makeset (cdr lat)))\n",
    "   (else\n",
    "    (cons (car lat) (makeset (cdr lat))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2 1 3 4 5)"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(makeset '(1 3 2 1 3 4 5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (subset? s1 s2)\n",
    "  (cond\n",
    "   ((null? s1) #t)\n",
    "   ((member? (car s1) s2) (subset? (cdr s1) s2))\n",
    "   (else #f)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#f"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(subset? '(1 2 4) '(1 2 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(subset? '(1 2) '(1 2 3 4 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "两个集合相等, 当且仅当它们互为对方的子集."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (eqset? s1 s2)\n",
    "  (and (subset? s1 s2)\n",
    "       (subset? s2 s1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(eqset? '(1 3 2) '(1 2 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "两个集合相交是指, 存在共有元素.\n",
    "两个集合的交集是, 两个集合共有元素的集合."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (intersect? s1 s2)\n",
    "  (cond\n",
    "   ((null? s1) #f)\n",
    "   ((member? (car s1) s2) #t)\n",
    "   (else\n",
    "    (intersect? (cdr s1) s2))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#f"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(intersect? '(1 2 3) '(6 4 5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(intersect? '(1 2 3) '(3 4 5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (intersect s1 s2)\n",
    "  (cond\n",
    "   ((null? s1) s1)\n",
    "   ((member? (car s1) s2) \n",
    "    (cons (car s1) (intersect (cdr s1) s2)))\n",
    "   (else\n",
    "    (intersect (cdr s1) s2))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2)"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(intersect '(1 2 3) '(2 7 9))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4 6)"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(intersect '(1 2 3 4 5 6 7 8) '(6 9 11 32 4 55))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (intersectall l-set) ;; 主要是发现问题结构上的特点, 发现结构后, 就比较容易解决\n",
    "  (cond\n",
    "   ((null? (cdr l-set)) (car l-set))\n",
    "   (else\n",
    "    (intersect (car l-set)\n",
    "               (intersectall (cdr l-set))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3)"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(intersectall '((1 2 3) (3 4 5 7 7) (3 1 11 34 9)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "并集是两个集合出现的共有元素."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (union s1 s2)\n",
    "  (cond\n",
    "   ((null? s1) s2)\n",
    "   ((member? (car s1) s2) (union (cdr s1) s2))\n",
    "   (else\n",
    "    (cons (car s1) (union (cdr s1) s2)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1 2 3 4 5 6)"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(union '(1 2 3) '(3 4 5 6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "关系(`rel`)是什么:\n",
    "\n",
    "一组`Pair`组成的列表.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (a-pair? x)\n",
    "  (cond\n",
    "   ((atom? x) #f)\n",
    "   ((null? x) #f)\n",
    "   ((null? (cdr x)) #f)\n",
    "   ((null? (cdr (cdr x))) #t)\n",
    "   (else #f)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(a-pair? '(1 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "函数是什么?\n",
    "\n",
    "集合A到集合B的多(一)对一映射. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (firsts lat)\n",
    "  (cond\n",
    "   ((null? lat) lat)\n",
    "   (else\n",
    "    (cons (car (car lat))\n",
    "          (firsts (cdr lat))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1 3 5 8)"
      ]
     },
     "execution_count": 101,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(firsts '((1 2) (3 4) (5 7) (8)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (fun? rel)\n",
    "  (set? (firsts rel)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(fun? '((1 2) (3 4) (5 6) (7 8)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面的关系, 就是函数$f(x)=x+1, x\\in\\{1, 3, 5, 8\\}$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "逆关系(`revrel`)是什么?\n",
    "\n",
    "关系的每个`Pair`, 第一个元素和第二个元素互换, 即是. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (revrel rel)\n",
    "  (cond\n",
    "   ((null? rel) rel)\n",
    "   (else\n",
    "    (cons (cons (car (cdr (car rel)))\n",
    "                (car (car rel)))\n",
    "          (revrel (cdr rel))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((2 . 1) (4 . 3) (6 . 5) (8 . 7))"
      ]
     },
     "execution_count": 105,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(revrel '((1 2) (3 4) (5 6) (7 8)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 8) Lambda the Ultimate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "涉及到函数作为值这一点.\n",
    "\n",
    "定义`(rember-f test? a l)`, 将谓词函数作为参数传进去, 而不是写死在代码中."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define rember-f\n",
    "  (lambda (test?)\n",
    "      (lambda (a l)\n",
    "          (cond\n",
    "           ((null? l) l)\n",
    "           ((test? a (car l)) (rember-f test? a (cdr l)))\n",
    "           (else\n",
    "            (cons (car l) ((rember-f test?) a (cdr l))))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1 2 3)"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "((rember-f eq?) 'a '(1 2 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`(define (f args..) ...)` 实际是`(define f (lambda (args..) ...))`的语法糖, 而后者, 又是下面代码的语法糖:\n",
    "```scheme\n",
    "(define f \n",
    "  (lambda (a0)\n",
    "    (lambda (a1)\n",
    "      ...\n",
    "      (lambda (an)\n",
    "        ...))))\n",
    "```\n",
    "\n",
    "`f(x0)`就会返回`(lambda (a1) ...)`这个partial function, 依次类推, 我们把这个过程叫做curry-ing, 即柯里化."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define rember-eq? (rember-f eq?))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "考虑我们之前定义的`value`函数:\n",
    "\n",
    "```scheme\n",
    "(define (value aexp)\n",
    "  (cond \n",
    "   ((atom? aexp) aexp)\n",
    "   ((eq? (car (cdr aexp)) '+) \n",
    "    (+ \n",
    "     (value (car aexp))\n",
    "     (value (car (cdr (cdr aexp))))))\n",
    "   ((eq? (car (cdr aexp)) '*)\n",
    "    (*\n",
    "     (value (car aexp))\n",
    "     (value (car (cdr (cdr aexp))))))\n",
    "   ((eq? (car (cdr aexp)) '^)\n",
    "    (pow\n",
    "     (value (car aexp))\n",
    "     (value (car (cdr (cdr aexp))))))))\n",
    "```\n",
    "\n",
    "其中, 判断算符进行计算的过程, 有一个明显的公共模式. 我们可以建立一个符号->算符的映射函数, 通用的解决它."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (atom->fun x)\n",
    "  (cond\n",
    "   ((eq? x '+) +)\n",
    "   ((eq? x '*) *)\n",
    "   ((eq? x '^) pow)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (value-1 aexp)\n",
    "  (cond\n",
    "   ((atom? aexp) aexp)\n",
    "   (else\n",
    "    ((atom->fun (car (cdr aexp)))\n",
    "     (value-1 (car aexp))\n",
    "     (value-1 (car (cdr (cdr aexp))))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(value-1 '(1 + (2 * 3)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义$eq?-c^1$函数, `(eq?-c1 k), k=\"salad\"`调用的结果是, 一个函数, 判断参数是否`eq?`\"salad\"这个值."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define eq?-c1\n",
    "  (lambda (a)\n",
    "    (lambda (x)\n",
    "      (eq? x a))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#<procedure>"
      ]
     },
     "execution_count": 113,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(eq?-c1 \"salad\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "((eq?-c1 'salad) 'salad)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define eq?-salad (eq?-c1 'salad))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(eq?-salad 'salad)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define insertL-f\n",
    "  (lambda (test?)\n",
    "    (lambda (new old l)\n",
    "      (cond\n",
    "       ((null? l) '())\n",
    "       ((test? (car l) old)\n",
    "        (cons new (cons old (cdr l))))\n",
    "       (else\n",
    "        (cons (car l)\n",
    "              ((insertL-f test?) new old (cdr l))))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a a b c d e)"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "((insertL-f eq?) 'a 'b '(a b c d e))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define insert-g0\n",
    "  (lambda (is-left-side)\n",
    "    (lambda (test?)\n",
    "      (lambda (new old l)\n",
    "        (cond\n",
    "         ((null? l) '())\n",
    "         ((test? (car l) old)\n",
    "          (cond \n",
    "           ((= is-left-side #t)\n",
    "            (cons new (cons old (cdr l))))\n",
    "           (else\n",
    "            (cons old (cons new (cdr l))))))\n",
    "         (else\n",
    "          (cons (car l)\n",
    "                (((insert-g0 is-left-side) test?) new old (cdr l)))))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a a b c d e)"
      ]
     },
     "execution_count": 120,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(((insert-g0 #t) eq?) 'a 'b '(a b c d e))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "比较\"土\"的方式.\n",
    "\n",
    "定义`seqL`, `seqR`, 接收`(new old l)`, 分别生成:\n",
    "\n",
    "- `seqL`\n",
    "    - `new old (cdr l)`\n",
    "- `seqR`\n",
    "    - `old new (cdr l)`\n",
    "    \n",
    "将`insert-g`中的`is-left-side`开关, 替换成对应的`seq`方法.\n",
    "\n",
    "```scheme\n",
    "(define insertL (insert-g seqL))\n",
    "(define insertR (insert-g seqR))\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (seqL new old l)\n",
    "  (cons new (cons old l)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (seqR new old l)\n",
    "  (cons old (cons new l)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define insert-g\n",
    "  (lambda (seq)\n",
    "    (lambda (new old l)\n",
    "      (cond\n",
    "       ((null? l) '())\n",
    "       ((eq? (car l) old)\n",
    "        (seq new old (cdr l)))\n",
    "       (else\n",
    "        (cons (car l)\n",
    "              ((insert-g seq) new old (cdr l))))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a a b c d e)"
      ]
     },
     "execution_count": 124,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "((insert-g seqL) 'a 'b '(a b c d e))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define subst0  ;; 替换一次\n",
    "  (lambda (new old l)\n",
    "    (cond\n",
    "     ((null? l) '())\n",
    "     ((eq? (car l) old)\n",
    "      (cons new (cdr l)))\n",
    "     (else\n",
    "      (cons (car l)\n",
    "            (subst0 new old (cdr l)))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a a c d e)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(subst0 'a 'b '(a b c d e))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "观察发现, `subst0`和`insert-g`有着相似的结构. 因此可以重写`subst`如下:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (seqS new old l)\n",
    "  (cons new l))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define subst (insert-g seqS))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a a c d e)"
      ]
     },
     "execution_count": 129,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(subst 'a 'b '(a b c d e))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面的`rember-f`程序, 实际上是`multirember-f`, 略过了`rember`的实现.\n",
    "\n",
    "下面引入`continuation`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define multirember&co \n",
    "  (lambda (a lat col)\n",
    "    (cond \n",
    "     ((null? lat) \n",
    "      (col '() '()))\n",
    "     ((eq? (car lat) a)\n",
    "      (multirember&co a\n",
    "                      (cdr lat)\n",
    "                      (lambda (newlat seen)\n",
    "                        (col newlat (cons (car lat) seen)))))\n",
    "     (else\n",
    "      (multirember&co a\n",
    "                      (cdr lat)\n",
    "                      (lambda (newlat seen)\n",
    "                        (col (cons (car lat) newlat) seen)))))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这里的`col`的作用, 通过递归的调用, 将中间数据存储在各级的闭包中. col的作用是一个`collector`, 一般被称作`continuation`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (a-friend x y)\n",
    "  (null? y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#f"
      ]
     },
     "execution_count": 132,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(multirember&co 'tuna '(strawberries tuna and swordfish) a-friend)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "展开上面调用的执行过程:\n",
    "\n",
    "`col = (lambda (x y) (null? y))`\n",
    "\n",
    "```scheme\n",
    ";; 1)\n",
    "(m&c 'tuna '(strawberries tuna and swordfish) col)\n",
    ";; 2) else\n",
    "(m&c 'tuna \n",
    "     '(tuna and swordfish) \n",
    "     (col (cons 'strawberries x) y))\n",
    ";; 3) match\n",
    "(m&c 'tuna \n",
    "     '(and swordfish) \n",
    "     (col (cons 'strawberries x) (cons 'tuna y)))\n",
    ";; 4) else\n",
    "(m&c 'tuna\n",
    "     '(swordfish)\n",
    "     (col (cons 'strawberries x) (cons 'and (cons 'tuna y))))\n",
    ";; 5) else\n",
    "(m&c 'tuna\n",
    "     '()\n",
    "     (col (cons 'strawberries x) (cons 'swordfish (cons 'and (cons 'tuna y)))))\n",
    "\n",
    ";; 6) null? #t\n",
    "(col '() '())\n",
    "(null? \n",
    " '(strawberries)\n",
    " '(swordfish and tuna))\n",
    ">>> #f\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 133,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(multirember&co 'tuna '() a-friend)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#f"
      ]
     },
     "execution_count": 134,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(multirember&co 'tuna '(tuna) a-friend)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```scheme\n",
    ";; 1) match\n",
    "(m&c 'tuna\n",
    "     '()\n",
    "     (col x (cons 'tuna y)))\n",
    ";; 2) null? #t\n",
    "(col '() '())\n",
    "(null? \n",
    " '()\n",
    " '(tuna))\n",
    ">>> #f\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "回头看, `(col x y)`的两个参数, `x`是不满足条件的一组集合, `y`是满足条件的一组集合. 根据上面的结论, 我们设计`cnt-friend`, 分别统计两个集合的大小.\n",
    "\n",
    "这里的`collector`, 类似于`reduce`或者`fold`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (cnt-friend x y)\n",
    "  (cons (length x) (length y)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3 . 1)"
      ]
     },
     "execution_count": 136,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(multirember&co 'tuna '(strawberries tuna and swordfish) cnt-friend)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TODO 练习:\n",
    "\n",
    "- `multiinsertL/multiinsertR/multiinsertLR`\n",
    "- `multiinsertLR&co`\n",
    "- `evens-only*`\n",
    "- `evens-only*&co`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 9) ...and Again, and Again, and Again, ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "函数`looking`, 从输入列表的第一个位置找起, 如果元素是数字, 表示列表索引, 继续查找, 如果非数字, 判断是否等于要找的元素, 是`#t`, 否`#f`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (pick i lat)\n",
    "  (cond\n",
    "   ((null? lat) '())\n",
    "   ((= i 1) (car lat))\n",
    "   (else\n",
    "    (pick (- i 1) (cdr lat)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 138,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(pick 3 '(1 2 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (keep-looking a i lat)\n",
    "  (cond\n",
    "   ((null? lat) #f)\n",
    "   ((number? i) \n",
    "    (keep-looking a (pick i lat) lat))\n",
    "   (else (eq? i a))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (looking a lat)\n",
    "  (keep-looking a (pick 1 lat) lat))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#t"
      ]
     },
     "execution_count": 141,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(looking 'caviar '(6 2 4 caviar 5 7 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "#f"
      ]
     },
     "execution_count": 142,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(looking 'caviar '(6 2 grits caviar 5 7 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`keep-looking`与以前的递归不同的地方, 在于`lat`的数据规模一直没有缩小. \n",
    "\n",
    "它的结束, 依赖于输入数据, 输入`(7 2 4 7 5 6 3)`, 永远停不下来.\n",
    "\n",
    "\n",
    "- `total function`\n",
    "    - 对所有输入都能在有限步后给出结果\n",
    "- `partial function`\n",
    "    - 只对部分输入能在有限步后给出结果\n",
    "    - `looking`就是这类函数\n",
    "   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (eternity x)  ;; 对任何输入都不能停, 也是一个`partial function`\n",
    "  (eternity x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (shift pair)\n",
    "  (build (fst (fst pair))\n",
    "         (build (snd (fst pair))\n",
    "                (snd pair))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (fst pair)\n",
    "  (car pair))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (snd pair)\n",
    "  (cond\n",
    "   [(null? pair) '()]\n",
    "   [else (car (cdr pair))]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 185,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (third lat)\n",
    "  (car (cdr (cdr lat))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (build a b)\n",
    "  (cons a (cons b '())))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a (b (c d)))"
      ]
     },
     "execution_count": 148,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(shift '((a b) (c d)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a (b c))"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(shift '((a b) c))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (align pora)\n",
    "  (cond\n",
    "   [(atom? pora) pora]\n",
    "   [(a-pair? (fst pora)) (align (shift pora))]\n",
    "   [else (build (fst pora)\n",
    "                (align (snd pora)))]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a (b (c (d e))))"
      ]
     },
     "execution_count": 151,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(align '((a b) (c (d e))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a (b (c (d e))))"
      ]
     },
     "execution_count": 152,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(shift '((a b) (c (d e))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (length* pora)\n",
    "  (cond\n",
    "   [(atom? pora) 1]\n",
    "   [else\n",
    "    (+ (length* (fst pora))\n",
    "       (length* (snd pora)))]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 154,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(length* '((a b) (c (d (e f)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (revpair p)\n",
    "  (build (snd p) (fst p)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(b a)"
      ]
     },
     "execution_count": 156,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(revpair '(a b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (shuffle pora)\n",
    "  (cond\n",
    "   [(atom? pora) pora]\n",
    "   [(a-pair? (fst pora)) \n",
    "    (shuffle (revpair pora))]\n",
    "   [else\n",
    "    (build (fst pora)\n",
    "           (shuffle (snd pora)))]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a (b c))"
      ]
     },
     "execution_count": 158,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(shuffle '(a (b c)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(a b)"
      ]
     },
     "execution_count": 159,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(shuffle '(a b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`(shuffle '((a b) (c d)))`不能结束, `shuffle`函数是`partial`的."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (C n)\n",
    "  (cond\n",
    "   [(= n 1) 1]\n",
    "   [(even? n) (C (/ n 2))]\n",
    "   [else\n",
    "    (C (add1 (* 3 n)))]))\n",
    "\n",
    ";; (C 0) 不能结束, partial的"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (A n m)\n",
    "  (cond\n",
    "   [(zero? n) (add1 m)]\n",
    "   [(zero? m) (A (sub1 n) 1)]\n",
    "   [else (A (sub1 n) (A n (sub1 m)))]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 162,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(A 1 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 163,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(A 2 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`Ackermann function`, \n",
    "\n",
    "$$\n",
    "A(m,n)=\\begin{cases}\n",
    "n+1 & \\quad \\text{if } m=0 \\\\\n",
    "A(m-1,1) & \\quad \\text{if } m>0 \\text{ and } n=0 \\\\\n",
    "A(m-1,A(m,n-1)) & \\quad \\text{if } m>0 \\text{ and } n>0\n",
    "\\end{cases}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "停机判定问题, 这里`will-stop?`函数是定义不出来的, 因为围绕它的假设, 可以构造出一个悖论来.停机问题是遇到的第一个可以被精确描述, 但是不能在程序中定义的问题.\n",
    "\n",
    "图灵停机问题和哥德尔不完备定理.\n",
    "\n",
    "停机问题涉及`自我指涉`(递归就是种自指), 本质是一阶逻辑的不自洽和不完备. \n",
    "\n",
    "回头看`length`函数:\n",
    "```scheme\n",
    "(define (length lat)\n",
    "  (cond \n",
    "   [(null? lat) 0]\n",
    "   [else (add1 (length (cdr lat)))]))\n",
    "```\n",
    "\n",
    "我们不再使用`define`绑定, 定义一个只能处理空列表的$length_0$(输入非空因为`eternity`的原因, 会不\"停机\").\n",
    "\n",
    "```scheme\n",
    "(lambda (lat)\n",
    "  (cond \n",
    "   [(null? lat) 0]\n",
    "   [else (add1 (eternity (cdr lat)))]))\n",
    "```\n",
    "\n",
    "利用$length_0$, 我们可以定义一个能处理空列表, 单元素列表的$length_{\\leq1}$:\n",
    "\n",
    "```scheme\n",
    "(lambda (lat)\n",
    "  (cond\n",
    "   [(null? lat) 0]\n",
    "   [else (add1 (length0 (cdr l)))]))\n",
    "```\n",
    "\n",
    "不存在$length_0$绑定, 所以展开. \n",
    "\n",
    "```scheme\n",
    "(lambda (lat)\n",
    "  (cond\n",
    "   [(null? lat) 0]\n",
    "   [else (add1 (lambda (lat)\n",
    "                 (cond\n",
    "                  [(null? lat) 0]\n",
    "                  [else (add1 (eternity (cdr lat)))]))\n",
    "               (cdr lat)]))\n",
    " ```\n",
    " \n",
    " 同理, 我们用相同的结构不断替换`eternity`,就可以得到不同的$\\leqN$版本`length`函数. 那么能否定义一个无限的函数, 来求解$length_{\\leq\\infty}$? 不能.\n",
    " 但是存在的这个函数的重复结构, 怎样表达?\n",
    " \n",
    "```scheme\n",
    "((lambda (length)\n",
    "   (lambda (lat)\n",
    "     (cond\n",
    "      [(null? lat) 0]\n",
    "      [else (add1 (length (cdr lat)))])))\n",
    " eternity)\n",
    "```\n",
    "\n",
    "按这种形式重写$length_{\\leq1}$, \n",
    "\n",
    "```scheme\n",
    "((lambda (f)\n",
    "   (lambda (lat)\n",
    "     (cond\n",
    "      [(null? lat) 0]\n",
    "      [else (add1 (f (cdr lat)))])))\n",
    " ((lambda (g)\n",
    "    (lambda (lat)\n",
    "      (cond\n",
    "       [(null? lat) 0]\n",
    "       [else (add1 (g (cdr lat)))]))))\n",
    " eternity))\n",
    "```\n",
    "\n",
    "定义$length_{\\leq2}$还需要再加一组`(lambda (k) ...)`, 还是代码上重复. 怎么办? 定义一个函数, 输入是`length`, 输出还是`length`.\n",
    "\n",
    "定义$length_0$:\n",
    "\n",
    "```scheme\n",
    "((lambda (mk-length)\n",
    "   (mk-length eternity))\n",
    " (lambda (length)\n",
    "   (lambda (lat)\n",
    "     (cond\n",
    "      [(null? lat) 0]\n",
    "      [else (add1 (length (cdr lat)))]))))\n",
    "```\n",
    "\n",
    "定义$length_{\\leq1}$:\n",
    "\n",
    "```scheme\n",
    "((lambda (mk-length)\n",
    "   (mk-length\n",
    "    (mk-length eternity)))\n",
    " (lambda (length)\n",
    "   (lambda (lat)\n",
    "     (cond\n",
    "      [(null? lat) 0]\n",
    "      [else (add1 (length (cdr lat)))]))))\n",
    "```\n",
    "\n",
    "如此类推, 只需增加`(mk-length (mk-length ...)`层次, 就可以表示函数的反复. \n",
    "\n",
    "application-order `Y combinator`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define Y\n",
    "  (lambda (le)\n",
    "    ((lambda (f) (f f))\n",
    "     (lambda (f)\n",
    "       (le (lambda (x) ((f f) x)))))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10) What is the Value of All of This? \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`entry`是这样一个`pair`:\n",
    "\n",
    "- 每个元素都是长度相同的`list`\n",
    "- 第一个列表是`set`\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 208,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define new-entry build)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (lookup-in-entry name entry entry-f)\n",
    "  (lookup-in-entry-help name (fst entry) (snd entry) entry-f))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (lookup-in-entry-help name names values entry-f)\n",
    "  (cond\n",
    "   [(null? names) (entry-f name)]\n",
    "   [(eq? (car names) name) (car values)]\n",
    "   [else\n",
    "    (lookup-in-entry-help name\n",
    "                          (cdr names)\n",
    "                          (cdr values)\n",
    "                          entry-f)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "boy"
      ]
     },
     "execution_count": 166,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(lookup-in-entry 'tom '((lucy lily tom) (girl girl boy)) (lambda (x) x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define extend-table cons)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (lookup-in-table name table table-f)\n",
    "  (cond\n",
    "   [(null? table) (table-f name)]\n",
    "   [else\n",
    "    (lookup-in-entry name \n",
    "                     (car table)\n",
    "                     (lambda (name)\n",
    "                       (lookup-in-table name\n",
    "                                        (cdr table)\n",
    "                                        table-f)))]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "找出值的类型, 定义`expr->action`, `atom->action`方法."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (expr->action e)\n",
    "  (cond\n",
    "   [(atom? e) (atom->action e)]\n",
    "   [else (list->action e)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (atom->action e)\n",
    "  (cond\n",
    "   [(number? e) *const]\n",
    "   [(eq? e #t) *const]\n",
    "   [(eq? e #f) *const]\n",
    "   [(eq? e 'cons) *const]\n",
    "   [(eq? e 'car) *const]\n",
    "   [(eq? e 'cdr) *const]\n",
    "   [(eq? e 'null?) *const]\n",
    "   [(eq? e 'eq?) *const]\n",
    "   [(eq? e 'atom?) *const]\n",
    "   [(eq? e 'zero?) *const]\n",
    "   [(eq? e 'add1) *const]\n",
    "   [(eq? e 'sub1) *const]\n",
    "   [(eq? e 'number?) *const]\n",
    "   [else *identifier]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (list->action e)\n",
    "  (cond\n",
    "   [(atom? (car e)) \n",
    "    (cond\n",
    "     [(eq? (car e) 'quote) *quote]\n",
    "     [(eq? (car e) 'lambda) *lambda]\n",
    "     [(eq? (car e) 'cond) *cond]\n",
    "     [else *application])]\n",
    "   [else *application]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (meaning e table)\n",
    "  ((expr->action e) e table))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (value e) (meaning e '()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (*const e table) ;; action for constants\n",
    "  (cond\n",
    "   [(number? e) e]\n",
    "   [(eq? e #t) #t]\n",
    "   [(eq? e #f) #f]\n",
    "   [else (build 'primitive e)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (*quote e table) ;; action for (quote ..)\n",
    "  (text-of e))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 181,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define text-of snd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (*identifier e table)\n",
    "  (lookup-in-table e table initial-table))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (initial-table name)  ;; 不应该被用到\n",
    "  (car '()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`primitive`和`non-primitive`的区别, `non-primitive`需要记住它的形参和body. \n",
    "\n",
    "```scheme\n",
    "(non-primitive\n",
    " ( (((y z) ((8) 9)))     (x)       (cons x y) ))\n",
    "   |--- table ----| |- formals -|  |-- body --|\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 184,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (*lambda e table)\n",
    "  (build 'non-primitive\n",
    "         (cons table (cdr e))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 186,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define table-of fst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 187,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define formals-of snd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 188,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define body-of third)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义`cond`语句, 首先定义一组辅助函数."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 190,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (else? x)\n",
    "  (cond\n",
    "   [(atom? x) (eq? x 'else)]\n",
    "   [else #f]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 191,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define question-of fst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 192,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define answer-of snd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 193,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (evcon lines table)\n",
    "  (cond\n",
    "   [(else? (question-of (car lines))) \n",
    "    (meaning (answer-of (car lines)) table)]\n",
    "   [(meaning (question-of (car lines)) table)\n",
    "    (meaning (answer-of (car lines)) table)]\n",
    "   [else (evcon (cdr lines) table)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 194,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define cond-lines-of cdr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 195,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (*cond e table)\n",
    "  (evcon (cond-lines-of e) table))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`*application`的结构:\n",
    "\n",
    "- 一个列表\n",
    "- 第一个元素的值是一个函数\n",
    "- apply时,所有参数的值需要求到\n",
    "\n",
    "定义`evlis`(eval list), 输入一个列表和table, 得到所有值组成列表.\n",
    "\n",
    "然后得到`function`的值, `(meaning-of-function meaning-of-args)`得到这个`*application`的值."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 196,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (evlis args table)\n",
    "  (cond\n",
    "   [(null? args) '()]\n",
    "   [else\n",
    "    (cons (meaning (car args) table)\n",
    "          (evlis (cdr args) table))]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 197,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define function-of car)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 198,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define arguments-of cdr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 199,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (*application e table)\n",
    "  (apply (meaning (function-of e) table)\n",
    "         (evlis (arguments-of e) table)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "程序中包含2种函数:\n",
    "\n",
    "1. `(primitive name)`\n",
    "2. `(non-primitive (table formals body))`\n",
    "    1. 这里`(table formals body)`被称作一条闭包记录(`closure record`)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 200,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (primitive? l)\n",
    "  (eq? (fst l) 'primitive))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 201,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (non-primitive? l)\n",
    "  (eq? (fst l) 'non-primitive))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "求值函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 202,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (apply fun vals)\n",
    "  (cond\n",
    "   [(primitive? fun) \n",
    "    (apply-primitive (snd fun) vals)]\n",
    "   [(non-primitive? fun)\n",
    "    (apply-closure (snd fun) vals)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 204,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (apply-primitive name vals)\n",
    "  (cond\n",
    "   [(eq? name 'cons) (cons (fst vals) (snd vals))]\n",
    "   [(eq? name 'car) (car (fst vals))]\n",
    "   [(eq? name 'cdr) (cdr (fst vals))]\n",
    "   [(eq? name 'null?) (null? (fst vals))]\n",
    "   [(eq? name 'eq?) (eq? (fst vals) (snd vals))]\n",
    "   [(eq? name 'atom?) (:atom? (fst vals))]\n",
    "   [(eq? name 'zero?) (zero? (fst vals))]\n",
    "   [(eq? name 'add1) (add1 (fst vals))]\n",
    "   [(eq? name 'sub1) (sub1 (fst vals))]\n",
    "   [(eq? name 'number?) (number? (fst vals))]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 205,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (:atom? x)\n",
    "  (cond\n",
    "   [(atom? x) #t]\n",
    "   [(null? x) #f]\n",
    "   [(eq? (car x) 'primitive) #t]\n",
    "   [(eq? (car x) 'non-primitive) #f]\n",
    "   [else #f]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 207,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (apply-closure closure vals)\n",
    "  (meaning (body-of closure)\n",
    "           (extend-table \n",
    "            (new-entry (formals-of closure) vals)\n",
    "            (table-of closure))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 210,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(6 a b c)"
      ]
     },
     "execution_count": 210,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(meaning '(cons z x) '(((x y)\n",
    "                        ((a b c) (d e f)))\n",
    "                       ((u v w)\n",
    "                        (1 2 3))\n",
    "                       ((x y z)\n",
    "                        (4 5 6))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 211,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(6 a b c)"
      ]
     },
     "execution_count": 211,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(apply '(primitive cons) '(6 (a b c)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(完)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Calysto Scheme 3",
   "language": "scheme",
   "name": "calysto_scheme"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "scheme"
   },
   "mimetype": "text/x-scheme",
   "name": "scheme",
   "pygments_lexer": "scheme"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}