Anjana Vakil, "Mary had a little lambda", OSCON 2018 (https://conferences.oreilly.com/oscon/oscon-or/public/schedule/detail/67384) & EuroPython 2017 (https://youtu.be/7BsfMMYvGaU)

LilLambda.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Mary had a little lambda\n",
    "\n",
    "[@AnjanaVakil](https://twitter.com/AnjanaVakil)\n",
    "\n",
    "OSCON 2018\n",
    "\n",
    "A gist of this Jupyter Notebook lives at https://gist.github.com/vakila/3d5cebaebf01c4c77b289b9a0388e3c8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Hi! I'm Anjana\n",
    "\n",
    "Engineering Learning & Development Lead at [Mapbox](http://www.mapbox.com)\n",
    "\n",
    "Alumna of \n",
    "* [The Recurse Center](https://www.recurse.com) programming retreat\n",
    "* [Outreachy](http://www.outreachy.org) internship program @ [Mozilla](http://www.mozilla.org)\n",
    "\n",
    "A [Mozilla TechSpeaker](https://wiki.mozilla.org/TechSpeakers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### and... poet 😜\n",
    "\n",
    "```\n",
    "Mary had a little lambda,  𝛌🐑\n",
    "a function pure as snow.   ❄️\n",
    "\n",
    "For every program that Mary wrote,     💻\n",
    "the lambda was all she needed to know. 💡\n",
    "```\n",
    "\n",
    "🐏🐑🐏🐑"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 𝛌 calculus\n",
    "\n",
    "* Mathematical formalism\n",
    "* Invented by this dude (Alonzo Church) starting 1932:\n",
    "  ![Alonzo Church](https://upload.wikimedia.org/wikipedia/en/a/a6/Alonzo_Church.jpg)\n",
    "  <sup>*image via [Wikipedia](https://en.wikipedia.org/wiki/Alonzo_Church#/media/File:Alonzo_Church.jpg), fair use*</sup>\n",
    "* Universal model of computation (Turing-complete) (NBD)\n",
    "* Untyped or typed\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "  | ** 𝛌 ** | ** `lambda` **\n",
    "--- | --- |  ---\n",
    "*used for* | thinking | programming\n",
    "*side effects?* | no way!  | maybe\n",
    "*inputs*   | 1 | 0+\n",
    "*outputs*  | 1 | 0+\n",
    "*making one*<br>*(\"abstraction\")*|  *λx.x* | `lambda x: x`\n",
    "                                 |  *λx.λy.x+y* | `lambda x, y: x + y`<br>`lambda x: lambda y: x + y`\n",
    "*using one*<br>*(\"application\")* | *(λx.x+1) 5*<br>*5+1*<br>*6* | `(lambda x: x+1)(5)`*<br>*`5+1`<br>`6`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### If we use `lambda` like 𝛌, **what can we make**?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "WARNING: Experimentation, sillyness, & learning ahead! 😜\n",
    "    \n",
    "For useful programming tips, please make a U-turn 🖖"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Numbers!\n",
    "\n",
    "Counting is fun!\n",
    "\n",
    "What can we count if all we have are functions?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We can count **function applications** (calls)!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "zero = lambda f: lambda x: x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "one = lambda f: lambda x: f(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "two = lambda f: lambda x: f(f(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "three = lambda f: lambda x: f(f(f(x)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Wait... are you sure these are numbers?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# cheating! but just for sanity checks...\n",
    "\n",
    "to_int = lambda n: n(lambda i: i+1)(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# zero = lambda f: lambda x: x\n",
    "to_int(zero)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# one = lambda f: lambda x: f(x)\n",
    "to_int(one)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# two = lambda f: lambda x: f(f(x))\n",
    "to_int(two)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# three = lambda f: lambda x: f(f(f(x)))\n",
    "to_int(three)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Higher numbers!\n",
    "\n",
    "Successor function: given a number, get the next number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "succ = lambda n: lambda f: lambda x: f(n(f)(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "four = succ(three)\n",
    "to_int(four)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "five = succ(four)\n",
    "six = succ(succ(four))\n",
    "seven = succ(succ(succ(four)))\n",
    "\n",
    "to_int(seven)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eight = seven(succ)(one)\n",
    "to_int(eight)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Yay! We have numbers! \n",
    "\n",
    "aka...\n",
    "\n",
    "### Church Numerals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Arithmetic!\n",
    "\n",
    "How can we add two numbers `n` and `m`, when numbers are call-counters?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Call the function `n` times, then call it `m` more times!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "add = lambda n: lambda m: lambda f: lambda x: m(f)(n(f)(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ten = add(eight)(two)\n",
    "to_int(ten)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_int(add(three)(eight))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Arithmetic!\n",
    "\n",
    "What about multiplying `n` and `m`?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Call the function `n` times, `m` times over!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "mul = lambda n: lambda m: lambda f: lambda x: m(n(f))(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "twelve = mul(four)(three)\n",
    "to_int(twelve)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_int(mul(three)(four))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Arithmetic!\n",
    "\n",
    "What about `n` to the power of `m`?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "power = lambda base: lambda exp: exp(base)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_int(power(two)(three))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Me: \"Excuse me Mr. Church...\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Alonzo's ghost: \"Yes?\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Me: \"What's the answer to life, the universe, and everything?\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "AG: \"Well...\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "answer = add(ten)(power(two)(five))\n",
    "to_int(answer)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "OK cool, we can do some (simple) math!\n",
    "\n",
    "### What else do we need to write programs?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Booleans! Conditionals!\n",
    "\n",
    "These go hand-in-hand "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# if (condition):\n",
    "#     (then do this)\n",
    "# else:\n",
    "#     (else do this)\n",
    "\n",
    "ifthenelse = lambda cond: lambda thn: lambda els: cond(thn)(els)\n",
    "\n",
    "troo = lambda thn: lambda els: thn\n",
    "falz = lambda thn: lambda els: els"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tired = falz\n",
    "\n",
    "coffees_today = ifthenelse(tired)(three)(one)\n",
    "to_int(coffees_today)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Logic!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# aka \"not\"\n",
    "opposite = lambda boolean: lambda thn: lambda els: boolean(els)(thn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# more cheating, just for simplicity's sake...\n",
    "to_bool = lambda boolean: boolean(True)(False)\n",
    "\n",
    "to_bool(troo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_bool(opposite(falz))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Predicates!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_zero = lambda n: n(lambda _: falz)(troo)\n",
    "\n",
    "to_bool(is_zero(zero))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_even = lambda n: n(opposite)(troo)\n",
    "\n",
    "to_bool(is_even(zero))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## More logic!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# and\n",
    "both = lambda boola: lambda boolb: boola(boolb)(boola)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_bool(both(falz)(troo))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_bool(both(troo)(falz))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_bool(both(falz)(falz))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_bool(both(troo)(troo))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## More logic!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# or\n",
    "inc_or = lambda boola: lambda boolb: boola(boola)(boolb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_bool(inc_or(falz)(troo))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_bool(inc_or(troo)(falz))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_bool(inc_or(troo)(troo))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_bool(inc_or(falz)(falz))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Cool, we've got some data!\n",
    "\n",
    "### What about data **structures**?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Lists!\n",
    "\n",
    "What can a list contain?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* Nothing (empty, aka `nil`)\n",
    "* One thing\n",
    "* Multiple things"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We'll build lists out of pairs of two things"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "make_pair = lambda left: lambda right: lambda f: f(left)(right)\n",
    "\n",
    "get_left = lambda pair: pair(troo)\n",
    "get_right = lambda pair: pair(falz)\n",
    "\n",
    "to_int(get_right(make_pair(three)(two)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# the empty list\n",
    "nil = make_pair(troo)(troo)\n",
    "\n",
    "# A list will have the form\n",
    "# (empty, (head, tail))\n",
    "\n",
    "is_empty = get_left\n",
    "\n",
    "# only nil will have troo as left element, i.e. empty == troo\n",
    "\n",
    "to_bool(is_empty(nil))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Lists!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# to add something to a list, we can prepend the item to the list\n",
    "# such that new_list = (empty=falz, (item, old_list))\n",
    "\n",
    "prepend = lambda item: lambda l: make_pair(falz)(make_pair(item)(l))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# non-empty lists will be composed of nested pairs, plus the 'empty' bool\n",
    "# e.g. [3, 2, 1] ==> (empty=falz, (3,(2,(1,nil))))\n",
    "\n",
    "single_item_list = prepend(one)(nil)  # (falz, (1,nil))\n",
    "multi_item_list = prepend(three)(prepend(two)(single_item_list)) # (falz, (3,(2,(1,nil))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# so non-empty lists always have form: (empty=falz, (head,tail))    \n",
    "\n",
    "# to get the head (first item in the list) and tail (rest of the list) of a non-empty list,\n",
    "# we have to unpack the right part of the pair\n",
    "\n",
    "head = lambda l: get_left(get_right(l))\n",
    "tail = lambda l: get_right(get_right(l))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# how can we select the 2 in our multi_item_list?\n",
    "to_int(head(tail(multi_item_list)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Yay, look at all the stuff we've got!\n",
    "\n",
    "* Data\n",
    "    * (natural) numbers\n",
    "    * booleans\n",
    "    * lists\n",
    "* Arithmetic\n",
    "* Logic & Control flow\n",
    "\n",
    "Representing data this way is called...\n",
    "\n",
    "### Church Encoding"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### There's so much more we could do!\n",
    "\n",
    "* Predecessor, subtract, divide\n",
    "* (In)equality\n",
    "* Strings (as lists of characters represented by their ASCII codes)\n",
    "* List manipulations (e.g. map, reduce, filter)\n",
    "* ...y'know, all of computation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Even OBJECTS!\n",
    "\n",
    "... wait, what?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Alan Kay, founding father of OOP, said ([Message to Smalltalk/Squeak mailing list, 1998](http://wiki.c2.com/?AlanKayOnMessaging)):\n",
    "> I'm sorry that I long ago coined the term \"objects\" for this topic because it gets many people to focus on the lesser idea. The big idea is \"messaging\".\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### FP & OOP: BFFs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "*Object* : thing which receives messages (method name + arguments) and gives responses\n",
    "\n",
    "*(Lambda) function* : thing which takes input and returns output\n",
    "\n",
    "\n",
    "Both define data in terms of **behavior**!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### FP & OOP: BFFs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Lambda calculus\n",
    "\n",
    "```\n",
    "TRUE  := λx.λy.x\n",
    "FALSE := λx.λy.y\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Smalltalk (iconic OOP language by Kay et al.)\n",
    "\n",
    "```\n",
    "class True\n",
    "  ifTrue: a ifFalse: b\n",
    "    ^ a value\n",
    "\n",
    "class False\n",
    "  ifTrue: a ifFalse: b\n",
    "    ^ b value\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "This was just a taster...\n",
    "### Go learn more lambdas! 𝛌🐑\n",
    "\n",
    "Check out \"Fun with Lambdas\" by Corey Haines\n",
    "  * [Upcoming book](https://leanpub.com/fun_with_lambdas)\n",
    "  * [Talk at GOTO Chicago 2015](https://youtu.be/QPqoFCHpLF4)\n",
    "\n",
    "\n",
    "#### Here's some other references for you!\n",
    "* Mary Rose Cook, [\"A practical introduction to functional programming\"](https://maryrosecook.com/blog/post/a-practical-introduction-to-functional-programming), \n",
    "* William Cook, [“A Proposal for Simplified, Modern Definitions of ‘Object’ and ‘Object Oriented’”](http://wcook.blogspot.fr/2012/07/proposal-for-simplified-modern.html), 2012"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# 💚Thank you!💚\n",
    "\n",
    "### Speaking opportunity courtesy of Mapbox, O'Reilly & Scott Hanselman\n",
    "\n",
    "### Inspiration courtesy of Corey Haines & Darius Bacon\n",
    "\n",
    "### Slides courtesy of Damian Avila's [RISE](https://github.com/damianavila/RISE) for Jupyter notebook\n",
    "\n",
    "### Lambda calculus courtesy of Alonzo Church \n",
    "\n",
    "## I'm [@AnjanaVakil](https://twitter.com/AnjanaVakil)!"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}