fall23_lambda_calculus.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## λ calculus\n",
    "\n",
    "\n",
    "The λ calculus is discussed in  [Chapter 8: Equivalent Models of Computation](http://introtcs.org/public/lec_07_other_models.html)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "%%html\n",
    "<style>\n",
    ".rise-enabled .cell .input_prompt {\n",
    "    display: none;\n",
    "}\n",
    "</style>\n",
    "<!--- <style>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "This Python notebook provides a way to play with the lamdba calculus and  evaluate lambda expressions of the form `λvar1(exp1) λvar2(exp2) ...`. If you don't know Python you can safely ignore the Ptyhon code and skip below to where we actually talk about the λ calculus itself.\n",
    "\n",
    "To better fit with python there are two main differences:\n",
    "\n",
    "* Instead of writing `λvar.exp` we write `λvar(exp)`\n",
    "\n",
    "* Instead of simply concatenating two expressions `exp1 exp2` we use the `*` operator and write `exp1 * exp2`. We can also use `exp1, exp2` if they are inside a function call or a variable binding parenthesis.\n",
    "\n",
    "* To reduce an expression `exp`, use `exp.reduce()`\n",
    "\n",
    "* Since Python does not allow us to override the default `0` and `1` we use `_0` for `λx(y(y))` and `_1` for `λx(y(x))`. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "# λ calculus introduction\n",
    "\n",
    "* Invented by Church in the 1930s\n",
    "* Computation by applying functions - pure functions, no side effect\n",
    "* Inspiration for LISP, ML, OCaml, Haskell, and all functional programming languages\n",
    "* Extensions of λ calculus crucial to modern programming languages and type systems, proof asistant."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "$\\lambda x. f$ defines the function $x \\mapsto f(x)$. \n",
    "\n",
    "__Example:__ $\\lambda x. x^2$ defines the function $x \\mapsto x^2$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Equivalent to $\\lambda y. y^2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "25"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# What will be printed?\n",
    "F = lambda x: x**2 \n",
    "F(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "64"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# What will be printed?\n",
    "H = lambda g: g(8)\n",
    "H(F)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "256"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# what will be printed\n",
    "J = lambda g: (lambda x: g(g(g(x))) )\n",
    "J(F)(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "$\\lambda x. exp$ defines a function that maps any argument $z$ to $exp[x \\rightarrow z]$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We sometimes use `λx(exp)` instead of $\\lambda x.exp$ below"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "* Every $\\lambda$ expression defines a function. $\\lambda x.exp$ is the function $z \\mapsto exp[x\\rightarrow z]$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* Can simulate functions with many arguments by \"currying\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "add = lambda a: (lambda b: a+b)\n",
    "add(5)(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "__Shorthand:__ $\\lambda a,b. exp$ is $\\lambda a. (\\lambda b.exp)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "* $\\lambda$ expressions can be inputs to other $\\lambda$ expressions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "40"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "( (lambda f: lambda x: f(f(x))) (lambda x: x*2)  ) (10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "__Conventions:__ To reduce parenthesis, use $f x$ for $f(x)$. \n",
    "\n",
    "Evaluate from left so $f a b = (f a) b$. \n",
    "\n",
    "In Python we use `f(a)` for $f a$ (in this notebook sometimes also `f*a')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "###  λ calculus is Turing Complete \n",
    "\n",
    "(A 42 page proof on [woodrush.github.io/blog/lambdalisp.html](https://woodrush.github.io/blog/lambdalisp.html) )\n",
    "\n",
    "![](https://i.imgur.com/xowmMIt.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<center><font size=\"+3\"><b>...</b></font></center> \n",
    "\n",
    "![](https://i.imgur.com/EVD22lz.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "```lisp\n",
    ";; From lambda calculus compiler in Lisp by Hikaru Ikuta\n",
    "(defun curry (expr)\n",
    "  (labels\n",
    "    ((normalize-app (ret l)\n",
    "       (if (not l) ret (normalize-app (list ret (curry (car l))) (cdr l))))\n",
    "     (curry-lambda (args body)\n",
    "       `(lambda (,(car args))\n",
    "          ,(if (= 1 (length args))\n",
    "               (curry body)\n",
    "               (curry-lambda (cdr args) body)))))\n",
    "    (cond ((atom expr)\n",
    "             expr)\n",
    "          ((islambda expr)\n",
    "             (curry-lambda (lambdaargs expr) (lambdabody expr)))\n",
    "          ((= 1 (length expr))\n",
    "             (curry (car expr)))\n",
    "          (t\n",
    "             (normalize-app (curry (car expr)) (cdr expr))))))\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "# Major issue: Recursion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We don't have loops and we don't seem to have recursion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "__Not allowed:__ \n",
    "```python\n",
    "Factorial = lambda n. 1 if n==0 else n*Factorial(n-1)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "No `let rec` allowed either"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Sneak preview"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Define **non-recursive** `RECURSE(f : Function)->Function` s.t. if `f` takes two arguments `me`, `x` then  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "source": [
    "`g = RECURSE(f)` satisfies `g(x)=f(g,x)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "def RECURSE(f):\n",
    "    def ftemp(me,x): return f(lambda x: me(me,x),x)\n",
    "    return lambda x: ftemp(ftemp,x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 2, 6, 24)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Example:\n",
    "def factorial_equation(g,n): \n",
    "    if n==0: return 1\n",
    "    return n*g(n-1)\n",
    "# equivalently:\n",
    "factorial_equation = lambda g,n: 1 if n==0 else n*g(n-1)\n",
    "h = RECURSE(factorial_equation)\n",
    "h(1),h(2),h(3),h(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "# Example through XOR :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# XOR of 2 bits\n",
    "def xor2(a,b): return 1-b if a else b\n",
    "\n",
    "# XOR of a list - recursive definition\n",
    "def xor(L): return xor2(L[0],xor(L[1:])) if L else 0\n",
    "\n",
    "xor([1,0,0,1,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Making this non recursive "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# non recursive function, instead of calling itself recursively, \n",
    "# it takes a second argument which is a function\n",
    "def myxor(me,L): return 0 if not L else xor2(L[0],me(L[1:]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "__First attempt:__ `xor(L)= myxor(myxor,L)` "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def xor(L): return myxor(myxor,L)\n",
    "xor([])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "myxor() missing 1 required positional argument: 'L'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[11], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m xor([\u001b[38;5;241m1\u001b[39m])\n",
      "Cell \u001b[0;32mIn[10], line 1\u001b[0m, in \u001b[0;36mxor\u001b[0;34m(L)\u001b[0m\n\u001b[0;32m----> 1\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mxor\u001b[39m(L): \u001b[38;5;28;01mreturn\u001b[39;00m myxor(myxor,L)\n",
      "Cell \u001b[0;32mIn[9], line 3\u001b[0m, in \u001b[0;36mmyxor\u001b[0;34m(me, L)\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[38;5;66;03m# non recursive function, instead of calling itself recursively, \u001b[39;00m\n\u001b[1;32m      2\u001b[0m \u001b[38;5;66;03m# it takes a second argument which is a function\u001b[39;00m\n\u001b[0;32m----> 3\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mmyxor\u001b[39m(me,L): \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[38;5;241m0\u001b[39m \u001b[38;5;28;01mif\u001b[39;00m \u001b[38;5;129;01mnot\u001b[39;00m L \u001b[38;5;28;01melse\u001b[39;00m xor2(L[\u001b[38;5;241m0\u001b[39m],me(L[\u001b[38;5;241m1\u001b[39m:]))\n",
      "\u001b[0;31mTypeError\u001b[0m: myxor() missing 1 required positional argument: 'L'"
     ]
    }
   ],
   "source": [
    "xor([1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The issue is that `myxor` takes _two_ arguments, while in `me` we only supply one.\n",
    "Thus, we will modify `myxor` to `tempxor` where we replace the call `me(x)` with `me(me,x)`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from typing import Callable, List\n",
    "# Creating an alias for Callable\n",
    "Function = Callable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def myxor(me : Function  ,L: List)-> int: return 0 if not L else xor2(L[0],me(L[1:]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "__Second attempt:__ Recall\n",
    "```python\n",
    "def myxor(me : Function ,L: List)-> int: \n",
    "    return 0 if not L else xor2(L[0],me(L[1:]))\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# we define\n",
    "def tempxor(temp : Function ,L: List)->int: \n",
    "    return myxor(lambda x: temp(temp,x),L)\n",
    "# If temp takes Function & List then x ↦ temp(temp,x) has the right type as an argument to myxor\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def xor(L): return tempxor(tempxor,L)\n",
    "\n",
    "xor([1,0,1,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "xor([1,0,0,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "```python\n",
    "def myxor(me,L): return 0 if not L else xor2(L[0],me(L[1:]))\n",
    "\n",
    "def tempxor(temp,L): return myxor(lambda x: temp(temp,x),L)\n",
    "\n",
    "```\n",
    "__Claim:__ For every list `L`, `tempxor(tempxor,L)= xor(L)`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "__Proof:__ Induction on `L`. __Base:__ If `L==[]`, `myxor(f,L)=0` regardless of `f`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "__Inductive step:__ If `myxor` gets the function `x ↦ tempxor(tempxor,x)` and applies it to `L[1:]` then by induction this is `XOR(L[1:])`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Generalization \n",
    "\n",
    "The `RECURSE` operator will take a function `f` that takes two arguments `me` and `x` and return a function `g`  satisfying `g(x) = f(g,x)` "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factorial_eq = lambda me,n: 1 if n==0 else me(n-1)*n\n",
    "\n",
    "def RECURSE(f):\n",
    "    def ftemp(me,x): return f(lambda x: me(me,x),x)\n",
    "    return lambda x: ftemp(ftemp,x)\n",
    "\n",
    "fact = RECURSE(factorial_eq)\n",
    "\n",
    "fact(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "RECURSE(myxor)([0,1,1,1,0,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "```python\n",
    "def RECURSE(f):\n",
    "    def ftemp(me,x): return f(lambda x: me(me,x),x)\n",
    "    return lambda x: ftemp(ftemp,x)\n",
    "```\n",
    "__Claim:__ For all `f`, if `g =RECURSE(f)` then  for all `x`, `g(x)=f(g,x)`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "__Proof:__ `g(x)= RECURSE(f)(x) =  ftemp(ftemp, x)`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "`= f(lambda x: ftemp(ftemp,x), x)`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "`f(g,x)` ∎"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "```python\n",
    "def RECURSE(f):\n",
    "    def ftemp(me,x): return f(lambda x: me(me,x),x)\n",
    "    return lambda x: ftemp(ftemp,x)\n",
    "```\n",
    "In $\\lambda$ calculus: `RECURSE` = λf.( (λm. f(m m)) λm.f(m m) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "![](https://i.imgur.com/VY4Yzc7.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "# Python implementation of $\\lambda$ calculus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "slideshow": {
     "slide_type": "skip"
    },
    "tags": []
   },
   "source": [
    "## Lambda calculus implementation in Python (can skip at first read)\n",
    "\n",
    "If you don't know Python feel free to skip ahead to the part where we play with the $\\lambda$ calculus itself.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# We define an abstract base class Lambdaexp for lambda expressions\n",
    "# It has the following subclasses:\n",
    "# Applicableexp: an expression of the form λx.exp\n",
    "# Combinedexp: an expression of the form (exp,exp')\n",
    "# Boundvar: an expression corresponding to a bounded variable\n",
    "# Unboundvar: an expression corresponding to a free variable\n",
    "#\n",
    "# The main operations in a Lambdaexp are:\n",
    "# 1. Replace: given exp,x and exp', obtain the expression exp[x-->exp']\n",
    "# 2. Reduce: continuously evaluate expressions to obtain a simpler form\n",
    "# 3. Apply: given exp,exp', if exp is applicable then apply it to exp', otherwise combine the two \n",
    "# (we also use the * operator for it)\n",
    "\n",
    "\n",
    "\n",
    "import operator ,functools\n",
    "\n",
    "class Lambdaexp:\n",
    "    \"\"\"Lambda expressions base class\"\"\"\n",
    "    \n",
    "    counter = 0\n",
    "    call_by_name = True  # if False then do normal form evaluation.\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.mykey = {}\n",
    "    \n",
    "    def apply(self,other): \n",
    "        \"\"\"Apply expression on an argument\"\"\"\n",
    "        return self*other\n",
    "        \n",
    "    def _reduce(self,maxlevel=100): \n",
    "        \"\"\"Reduce expression\"\"\"\n",
    "        return self\n",
    "    \n",
    "    def replace(self,old,new): \n",
    "        \"\"\"Replace all occurences of old with new\"\"\"\n",
    "        raise NotImplementedError\n",
    "\n",
    "    \n",
    "    def bounded(self): \n",
    "        \"\"\"Set of bounded variables inside expression\"\"\"\n",
    "        return set()\n",
    "\n",
    "    def asstring(self, m,pretty=False):\n",
    "        \"\"\"Represent self as a string mapping bounded variables to particular numbers.\"\"\"\n",
    "        raise NotImplementedError\n",
    "\n",
    "    #------------------------------------------------------------------------------#\n",
    "    # Ignore this code  in first read: Python specific details\n",
    "\n",
    "    lambdanames = {}\n",
    "    reducedstrings = {}\n",
    "   \n",
    "    def reduce(self,maxlevel=100):\n",
    "        if not maxlevel: return self\n",
    "        #m = {b:b for b in self.bounded() }\n",
    "        #t = Lambdaexp.reducedstrings.get((self.asstring(m),maxlevel),None)\n",
    "        #if t: return t\n",
    "        return self._reduce(maxlevel)\n",
    "        #k = t.asstring(m)\n",
    "        #for i in range(maxlevel+1):  \n",
    "        #    Lambdaexp.reducedstrings[(k,i)] = t\n",
    "        #return t\n",
    "            \n",
    "            \n",
    "        \n",
    "    def __mul__(self,other):\n",
    "        \"\"\"Use * for combining.\"\"\"\n",
    "        return Combinedexp(self,other) if other else self\n",
    "    \n",
    "    def __call__(self,*args): \n",
    "        \"\"\"Use function call for application\"\"\"\n",
    "        return functools.reduce(operator.mul,args,self)\n",
    "    \n",
    "    def _key(self,maxlevel=100): \n",
    "        #if maxlevel not in self.mykey: \n",
    "        return self.reduce(maxlevel).__repr__()\n",
    "            # for i in range(maxlevel+1): self.mykey[i] = s \n",
    "        # return self.mykey[maxlevel]\n",
    "\n",
    "    def __eq__(self,other): return self._key()==other._key() if isinstance(other,Lambdaexp) else False\n",
    "    def __hash__(self): return hash(self._key())\n",
    "    \n",
    "        \n",
    "        \n",
    "    def __repr__(self,pretty=False):\n",
    "        B = sorted(self.bounded())\n",
    "        m ={}\n",
    "        for v in B: m[v] = len(m)\n",
    "        return self.asstring(m,pretty)\n",
    "    \n",
    "    \n",
    "    def _repr_pretty_(self, p, cycle):\n",
    "        if cycle: p.text( self._repr())\n",
    "        p.text( self.reduce().__repr__(True))     \n",
    "        \n",
    "    def addconst(self,srep):\n",
    "        \"\"\"Return either exp.string or replaced with a keyword if it's in table.\"\"\"\n",
    "        if self in Lambdaexp.lambdanames:  return blue(Lambdaexp.lambdanames[self])\n",
    "        return srep\n",
    "\n",
    "      #------------------------------------------------------------------------------#\n",
    "\n",
    "\n",
    "    \n",
    "    \n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "#-------------------------------------------------#\n",
    "# Utility functions: print color\n",
    "def bold(s,justify=0):\n",
    "    return \"\\x1b[1m\"+s.ljust(justify)+\"\\x1b[21m\"\n",
    "\n",
    "def underline(s,justify=0):\n",
    "    return \"\\x1b[4m\"+s.ljust(justify)+\"\\x1b[24m\"\n",
    "\n",
    "def red(s,justify=0):\n",
    "    return  \"\\x1b[31m\"+s.ljust(justify)+\"\\x1b[0m\"\n",
    "\n",
    "\n",
    "def green(s,justify=0):\n",
    "    return  \"\\x1b[32m\"+s.ljust(justify)+\"\\x1b[0m\"\n",
    "\n",
    "\n",
    "def blue(s,justify=0):\n",
    "    return  \"\\x1b[34m\"+s.ljust(justify)+\"\\x1b[0m\"\n",
    "#--------------------------------------------------#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "  \n",
    "    \n",
    "    \n",
    "\n",
    "        \n",
    "class Applicableexp(Lambdaexp):\n",
    "    \"\"\"Lambda expression that can be applied\"\"\"\n",
    "    \n",
    "    def __init__(self,exp,name):\n",
    "        Lambdaexp.counter += 1\n",
    "        self.arg =  Lambdaexp.counter\n",
    "        self.inner = exp.replace(name,Boundvar(self.arg))\n",
    "        super().__init__()    \n",
    "    \n",
    "    def apply(self,other): \n",
    "        return self.inner.replace(self.arg,other)\n",
    "    \n",
    "    def replace(self,old,new): \n",
    "        if self.arg==old: \n",
    "            if not isintance(new,Boundvar): \n",
    "                raise TypeError(f\"Can't replace {old} in {self} since {new} is not instance of Boundvar\")\n",
    "            self.arg = new.myid\n",
    "        return Applicableexp(self.inner.replace(old,new),self.arg)\n",
    "    \n",
    "    def bounded(self): return self.inner.bounded()|{self.arg}\n",
    "    \n",
    "    def _reduce(self,maxlevel=100):\n",
    "        if Lambdaexp.call_by_name: return self \n",
    "        # in call by name there are no reductions inside abstractions\n",
    "        inner = self.inner.reduce(maxlevel-1)\n",
    "        return Applicableexp(inner,self.arg)\n",
    "    \n",
    "    def asstring(self, m,pretty=False):\n",
    "        if not pretty: return \"λ\"+Boundvar(self.arg).asstring(m,False)+\".(\"+self.inner.asstring(m)+\")\"\n",
    "        return self.addconst(green(\"λ\")+Boundvar(self.arg).asstring(m,True)+\".(\"+self.inner.asstring(m,True)+\")\")\n",
    "        \n",
    "        \n",
    " \n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "class Boundvar(Lambdaexp):\n",
    "    \"\"\"Bounded variable\"\"\"\n",
    "    def __init__(self,arg): \n",
    "        self.myid = arg\n",
    "        super().__init__()\n",
    "        \n",
    "    def replace(self,argnum,exp): return exp if argnum==self.myid else self\n",
    "    \n",
    "    def bounded(self): return { self.myid }\n",
    "\n",
    "    def asstring(self, m,pretty=False):\n",
    "        arg = m.get(self.myid,self.myid) \n",
    "        return chr(ord('α')+arg)\n",
    "    \n",
    "\n",
    "class Unboundvar(Lambdaexp):\n",
    "    \"\"\"Unbounded (free) variable.\"\"\"\n",
    "    def __init__(self,name): \n",
    "        self.name = name\n",
    "        super().__init__()\n",
    "        \n",
    "    def replace(self,name,arg): return arg if name==self.name else self\n",
    "    \n",
    "    def asstring(self, m,pretty=False):\n",
    "        return self.addconst(self.name) if pretty else self.name\n",
    "\n",
    "   \n",
    "    \n",
    "class Combinedexp(Lambdaexp):\n",
    "    \"\"\"Combined expression of two expressions.\"\"\"\n",
    "    def __init__(self,exp1,exp2):\n",
    "        self.exp1 = exp1\n",
    "        self.exp2 = exp2\n",
    "        super().__init__()\n",
    "    \n",
    "    def replace(self,arg,exp): \n",
    "        return Combinedexp(self.exp1.replace(arg,exp),self.exp2.replace(arg,exp))\n",
    "    \n",
    "    def bounded(self): return self.exp1.bounded()|self.exp2.bounded()\n",
    "    \n",
    "    \n",
    "    def _reduce(self,maxlevel=100):\n",
    "        if not maxlevel: return self\n",
    "        e1 = self.exp1.reduce(maxlevel-1)\n",
    "        if isinstance(e1,Applicableexp): \n",
    "            return  e1.apply(self.exp2).reduce(maxlevel-1)\n",
    "        return Combinedexp(e1,self.exp2)\n",
    "    \n",
    "    def asstring(self, m,pretty=False):\n",
    "        s = f\"({self.exp1.asstring(m,False)} {self.exp2.asstring(m,False)})\"\n",
    "        if not pretty: return s\n",
    "        return f\"({self.exp1.asstring(m,True)} {self.exp2.asstring(m,True)})\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "class λ:\n",
    "    \"\"\"Binds a variable name in a lambda expression\"\"\"\n",
    "\n",
    "    def __init__(self,*varlist): \n",
    "        \"\"\"\n",
    "        Get list of unbounded variables (for example a,b,c) and returns an operator that binds an expresion exp to\n",
    "        λa(λb(λc(exp))) and so on.\"\"\"\n",
    "        if not varlist: raise ValueError(\"Need to bind at least one variable\")\n",
    "        self.varlist = varlist[::-1]\n",
    "        \n",
    "    \n",
    "    def bindexp(self,exp):\n",
    "        res = exp\n",
    "        for v in self.varlist: \n",
    "            res = Applicableexp(res,v.name)\n",
    "        return res\n",
    "    \n",
    "    #------------------------------------------------------------------------------#\n",
    "    # Ignore this code  in first read: Python specific details\n",
    "\n",
    "    \n",
    "    def __call__(self,*args):\n",
    "        exp = functools.reduce(operator.mul,args[1:],args[0])\n",
    "        return self.bindexp(exp)\n",
    "    #------------------------------------------------------------------------------#"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "### Initalization \n",
    "\n",
    "The above is all the code for implementing the λ calculus. We now add some convenient global variables: \n",
    "λa .... λz and a ... z for variables, and 0 and 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "Lambdaexp.lambdanames  = {}\n",
    "import string\n",
    "\n",
    "def initids(g):\n",
    "    \"\"\"Set up parameters a...z and correpsonding Binder objects λa..λz\"\"\"\n",
    "    lcase = list(string.ascii_lowercase)\n",
    "    ids = lcase + [n+\"_\" for n in lcase]\n",
    "    for name in ids:\n",
    "        var =  Unboundvar(name)\n",
    "        g[name] = var\n",
    "        g[\"λ\"+name] = λ(var)\n",
    "        Lambdaexp.lambdanames[var] = name"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "initids(globals())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[32mλ\u001b[0mα.(α)"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# testing...\n",
    "λy(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[32mλ\u001b[0mα.(\u001b[32mλ\u001b[0mβ.(α))"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "λ(a,b)(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def setconstants(g,consts):\n",
    "    \"\"\"Set up constants for easier typing and printing.\"\"\"\n",
    "   \n",
    "    for name in consts:\n",
    "        Lambdaexp.lambdanames[consts[name]] = name\n",
    "        if name[0].isalpha(): \n",
    "            g[name]=consts[name]\n",
    "            \n",
    "        else: # Numeric constants such as 0 and 1 are replaced by _0 and _1\n",
    "            g[\"_\"+name] = consts[name]\n",
    "    \n",
    "\n",
    "def register(g,*args):\n",
    "    for name in args:\n",
    "        Lambdaexp.lambdanames[g[name]] = name"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[32mλ\u001b[0mα.(\u001b[32mλ\u001b[0mβ.(α))"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# testing\n",
    "λa(λz(a))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Demonstration of $\\lambda$ calculus in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[32mλ\u001b[0mα.(α)"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ID = λx(x)\n",
    "ID"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[32mλ\u001b[0mα.(α)"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ID(ID)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## True/False or 1/0 in $\\lambda$ calculus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "T = λa(λb(a))\n",
    "F = λa(λb(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[34my\u001b[0m"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F(x,y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[34mx\u001b[0m"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "T(x,y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "IF = λ(a,b,c)( (a(b))(c) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[34mx\u001b[0m"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# What will be printed?\n",
    "IF(T,x,y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[34my\u001b[0m"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# can also write it as\n",
    "IF =  λ(a,b,c)(a*b*c)\n",
    "IF(F,x,y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "We define $1 = T =  \\lambda a,b.a$ and $0 = F =  \\lambda a,b.b$. We define $IF = \\lambda a,b,c. a b c$ "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# We identify 1 with True and 0 with False\n",
    "_1 = T\n",
    "_0 = F"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "setconstants(globals(),{\"1\" : λ(x,y)(x) , \"0\" : λ(x,y)(y)  })"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "λa(λb(b))==_0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "__Question:__ Suppose that $F = \\lambda f. (\\lambda x. (f x)f)$, $1 = \\lambda x.(\\lambda y.x)$ and $0=\\lambda x.(\\lambda y.y)$.\n",
    "What is $F \\; 1\\; 0 = (F 1) 0$?\n",
    "\n",
    "__a.__ $1$\n",
    "\n",
    "__b.__ $0$\n",
    "\n",
    "__c.__ $\\lambda x.1$\n",
    "\n",
    "__d.__ $\\lambda x.0$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "F= λf( λx( f(x)(f) ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[32mλ\u001b[0mα.(((\u001b[34m1\u001b[0m α) \u001b[34m1\u001b[0m))"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F(_1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[34m0\u001b[0m"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F(_1)(_0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "### Reminders: \n",
    "\n",
    "$\\lambda x. exp$ corresponds to the function that maps any argument $z$ to the expression $exp[x\\rightarrow z]$. \n",
    "\n",
    "We use \"Currying\" for two argument functions, and so $\\lambda a,b. f(a,b)$ is the same as $\\lambda a. (\\lambda b.(f(a))(b) )$. We drop parenthesis for function application and evaluate from the left and so also write the latter as $\\lambda a. (\\lambda b. f\\; a\\;b)$\n",
    "\n",
    "We define $1 = \\lambda a,b.a$ and $0=\\lambda a,b.b$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Some useful functions\n",
    "\n",
    "Let us now add some of the basic functions in the λ calculus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "PAIR =λx(λy(λf(f(x,y)))) # given x,y returns the function f --> f(x,y)\n",
    "HEAD = λp(p(_1) )\n",
    "TAIL  =λp(p(_0) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def slist(L, maxrec=100):\n",
    "    if maxrec<0: return red(\"TOO LONG\")\n",
    "    if ISEMPTY(L)==_1: return red(\"NIL\")\n",
    "    return HEAD(L).reduce().__repr__(True)+\", \"+slist(TAIL(L),maxrec-1)\n",
    "def plist(L): print(\"[\"+slist(L)+\"]\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "__Lemma:__ If $P = \\text{PAIR}\\; a\\; b$ then $\\text{HEAD}\\; P = a$ and $\\text{TAIL}\\; P\\;= b$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "__Proof:__ $\\text{PAIR}\\; a\\; b = \\lambda f.f(a,b)$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "The function mapping $f$ to $f(a,b)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Hence $P 1 = a$ and $P 0 = b$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "Hence $(\\lambda p. p 1) P = a$ and $(\\lambda p. p 0) P = b$  ▮"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[34mx\u001b[0m"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "HEAD(PAIR(x,y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[34my\u001b[0m"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# What will be printed?\n",
    "L = PAIR(x, PAIR(y, z))\n",
    "HEAD( TAIL( L ))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Lists\n",
    "We can construct list by repeatedly using `PAIR`. We define a special term `NIL` for the empty list. If $L$ is the list $[b,c,d]$ then $PAIR(a,L)$ is the list $[a,b,c,d]$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[34m1\u001b[0m"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "NIL= λf(_1)\n",
    "ISEMPTY= λp(p(λx(λy(_0))))\n",
    "ISEMPTY(NIL)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "register(globals(),\"NIL\", \"PAIR\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[34m0\u001b[0m"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ISEMPTY(PAIR(_1,_1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[32mλ\u001b[0mα.(((α \u001b[34mx\u001b[0m) ((\u001b[34mPAIR\u001b[0m \u001b[34my\u001b[0m) \u001b[34mNIL\u001b[0m)))"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L = PAIR(x, PAIR(y,NIL))\n",
    "L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[\u001b[34mx\u001b[0m, \u001b[34my\u001b[0m, \u001b[31mNIL\u001b[0m]\n"
     ]
    }
   ],
   "source": [
    "plist(L)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "We can make lists of bits as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def makelist(*L):\n",
    "    \"\"\"Construct a λ list of _0's and _1's.\"\"\"\n",
    "    if not L: return NIL\n",
    "    h = _1 if L[0]   else _0\n",
    "    return PAIR(h,makelist(*L[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[\u001b[34m1\u001b[0m, \u001b[34m0\u001b[0m, \u001b[34m1\u001b[0m, \u001b[34m1\u001b[0m, \u001b[34m0\u001b[0m, \u001b[31mNIL\u001b[0m]\n"
     ]
    }
   ],
   "source": [
    "L=makelist(1,0,1,1,0)\n",
    "plist(L)\n",
    "#L.__repr__()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[\u001b[34m0\u001b[0m, \u001b[34m1\u001b[0m, \u001b[34m1\u001b[0m, \u001b[34m0\u001b[0m, \u001b[31mNIL\u001b[0m]\n"
     ]
    }
   ],
   "source": [
    "plist(TAIL(L))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[34m0\u001b[0m"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "HEAD(TAIL(L))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Recursion: λ version\n",
    "\n",
    "We now repeat the same arguments we did before with the λ calculus:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# XOR of two bits\n",
    "XOR2 = λ(a,b)(IF(a,IF(b,_0,_1),b))\n",
    "\n",
    "# Recursive XOR with recursive calls replaced by m parameter\n",
    "myXOR = λ(m,l)(IF(ISEMPTY(l),_0,XOR2(HEAD(l),m(TAIL(l)))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Recall Python RECURSE:\n",
    "```python\n",
    "def RECURSE(f):\n",
    "    def ftemp(me,x): return f(lambda x: me(me,x),x)\n",
    "    return lambda x: ftemp(ftemp,x)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# Recurse operator (aka Y combinator)\n",
    "# ftemp(me) = λx( f(me(me))(x)  ) = f(me(me))\n",
    "# ftemp(ftemp,x) = ftemp(ftemp)(x)  \n",
    "RECURSE = λf(  λm(f(m(m)))   (λm(f(m(m)))) )\n",
    "# XOR function\n",
    "XOR = RECURSE(myXOR)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Let's test this out:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[34m0\u001b[0m"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XOR(PAIR(_0,NIL)) # List [0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[34m1\u001b[0m"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XOR(PAIR(_1,PAIR(_1,PAIR(_1,NIL)))) # List [1,1,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[34m1\u001b[0m"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XOR(makelist(1,0,1,1,1,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[34m0\u001b[0m"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XOR(makelist(1,0,1,1,1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "```python\n",
    "RECURSE = λf(  λm(f(m(m)))   (λm(f(m(m)))) )\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<img src=\"https://i.imgur.com/1I1XL9f.png\" width=\"400px\"></img>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "# Restore definition to the Python one\n",
    "def RECURSE(f):\n",
    "    def ftemp(me,x): return f(lambda x: me(me,x),x)\n",
    "    return lambda x: ftemp(ftemp,x)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "tcs",
   "language": "python",
   "name": "tcs"
  },
  "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.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}