{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Continuation Passing Style\n",
    "\n",
    "https://cgi.soic.indiana.edu/~c311/lib/exe/fetch.php?media=cps-notes.scm\n",
    "\n",
    "`(f (g (h i) j) k)` 哪部分先求值? `(h i)`, 然后`(g (h i) j)`才能求值. \n",
    "\n",
    "`(f (g (h i) (j k)))`呢? `scheme`没有规定求值的顺序, 所以可能是`(h i)`或者`(j k)`.\n",
    "\n",
    "假设有`(h i (lambda (hi) ...)`, 其中`hi`是`(h i)`求值的结果, 那么我们重写`(f (g (h i) (j k)))`成下面的形式:\n",
    "`(h i (lambda (hi) (f (g hi (j k)))))`, 其中`(lambda (hi) (f (g hi (j k))))`就是一个`continuation`(有些地方译成延续?). \n",
    "\n",
    "CPS(https://en.wikipedia.org/wiki/Continuation-passing_style)\n",
    "\n",
    "## 以`rember`为例\n",
    "\n",
    "以CPS形式写一个`rember`函数.\n",
    "\n",
    "先看一个最简单形式."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define rember8\n",
    "  (lambda (ls)\n",
    "    (cond\n",
    "     [(null? ls) '()]\n",
    "     [(= (car ls) 8) (cdr ls)]\n",
    "     [else (cons (car ls) (rember8 (cdr ls)))])))\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1 2 3 4 5)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(rember8 '(1 2 3 8 4 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "第一个原则\n",
    "\n",
    "当我们在需要转成CPS形式的代码中, 看见`lambda`, 都需要给它添加一个参数, 然后相应的处理`body`.\n",
    "\n",
    "`(lambda (x ...) ...) => (lambda (x ... k) ...^)`\n",
    "\n",
    "第二个原则\n",
    "\n",
    "不要漏掉每一个`small stuff`, 由`rember`到`rember8*`, 我们需要从`cond`开始, 每行仔细考虑, 进行改动.\n",
    "尤其注意`else`部分, 我们将构建结果的过程全部放进了最后这个`continuation`, 数据存储本身存在这个闭包中, 同时要注意`k`对构造出的结构的应用. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define rember8*\n",
    "  (lambda (ls k)\n",
    "    (cond\n",
    "     [(null? ls) (k '())]\n",
    "     [(= (car ls) 8) (k (cdr ls))]\n",
    "     [else (rember8* (cdr ls) \n",
    "                      (lambda (x) (k (cons (car ls) x))))])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1 2 3 4 4 5)"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(rember8* '(1 2 3 4 8 4 5) (lambda (x) x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`(lambda (x) x)`就是\"identity function\".\n",
    "\n",
    "现在观察`rember8*`, 首先, 所有的分支调用, 都是尾递归.\n",
    "\n",
    "> Small stuff is stuff we know will terminate right away.\n",
    "\n",
    "再次, 所有的参数, 都是`small stuff`. `=`, `car`, `cdr`, `cons`以及`lambda`都是`small stuff`, `lambda`总是`small stuff`.\n",
    "\n",
    "上面被CPSed的程序, 求值时做的所有工作, 就是把`continuation`变成数据结构. 观察`(rember8* '(1 2 8 3 4 6 7 8 5) (lambda (x) x))`的求值过程:\n",
    "\n",
    "| ls | k |\n",
    "| :--- |:--- |\n",
    "| '(1 2 8 3 4 6 8 5) | (lambda (x) x) = id |\n",
    "| '(2 8 3 4 6 8 5) | (lambda (x) (id (cons (car 1) x))) = k2 |\n",
    "| '(8 3 4 6 8 5) | (lambda (x) (k2 (cons (car 2) x))) = k3 |\n",
    "| 开始求值`(k3 (cdr ls))` |\n",
    "| (k3 '(3 4 6 8 5) = (k2 (cons 2 '(3 4 6 8 5)) |\n",
    "| (k2 '(2 3 4 6 8 5) = (id (cons 1 '(2 3 4 5 6 8 5))) |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1 2 3 4 6 8 5)"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(rember8* '(1 2 8 3 4 6 8 5) (lambda (x) x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## `multirember`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define multirember8 \n",
    "  (lambda (ls)\n",
    "    (cond\n",
    "     [(null? ls) '()]\n",
    "     [(= (car ls) 8) (multirember8 (cdr ls))]\n",
    "     [else\n",
    "      (cons (car ls) (multirember8 (cdr ls)))])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1 2 3 4 6 5)"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(multirember8 '(1 2 8 3 4 6 8 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "开始CPSing~, 应用第一原则, 加参数k, 应用第二原则, 对各个分支应用调整."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define multirember8*\n",
    "  (lambda (ls k)\n",
    "    (cond\n",
    "     [(null? ls) (k '())]\n",
    "     [(= (car ls) 8) (multirember8* (cdr ls)\n",
    "                                    (lambda (x) \n",
    "                                      (k x)))]\n",
    "     [else\n",
    "      (multirember8* (cdr ls)\n",
    "                     (lambda (x)\n",
    "                       (k (cons (car ls) x))))])))\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1 2 3 4 6 5)"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(multirember8* '(1 2 8 3 4 6 8 5) (lambda (x) x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`(lambda (x) (k x))`具体做什么, 它的作用是将接收到的东西不做处理, 传给`k`, 表示跳过这个分支(忽略`(car ls)`, 将递归上层的逻辑传到下层去. \n",
    "\n",
    "`(lambda (x) (M x)` = `M`, 如果`x`在`M`中不是自由变量, 且`M`能保证终止. 据此, 化简上面的程序, 得到下面的最终形式."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "(define multirember8**\n",
    "  (lambda (ls k)\n",
    "    (cond\n",
    "     [(null? ls) (k '())]\n",
    "     [(= (car ls) 8) (multirember8** (cdr ls) k)]\n",
    "     [else\n",
    "      (multirember8** (cdr ls)\n",
    "                     (lambda (x)\n",
    "                       (k (cons (car ls) x))))])))\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1 2 3 4 6 5)"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(multirember8** '(1 2 8 3 4 6 8 5) (lambda (x) x))"
   ]
  }
 ],
 "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
}