{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Finding Fibonacci Numbers Using Lambda Calculus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Inspired by this article on github (posted on HN): https://gitlab.com/snippets/1879264, I, as a kind of experiment, did something different: wrote a Fibonacci numbers function using Lambda Calculus on it's own. \n",
    "So, no numbers, no data structures, just anonymous functions. I have to do it in some language, for the sake of convenience I've choosen Python. The lambda function is a function of one variable (this variable could be also a function). That's how it looks: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<function __main__.<lambda>(x)>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lambda x: x + 41"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's used in stright forward way:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(lambda x: x + 41)(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We bring the original, famous, Fibonacci function, and start to refactor it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fibo(n):\n",
    "    if n < 2:\n",
    "        return 1\n",
    "    else:\n",
    "        return fibo(n - 1) + fibo (n - 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a sanity check, we will be checking that: fibo(5) == 8:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fibo(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Refactoring\n",
    "The first task: a few changes to functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "ONE = 1\n",
    "SUB1 = lambda x: x - 1\n",
    "SUB2 = lambda x: x - 2\n",
    "ADD = lambda x, y: x + y\n",
    "LESS_TWO = lambda x: x < 2\n",
    "\n",
    "def fibo(n):\n",
    "    if LESS_TWO(n):\n",
    "        return ONE\n",
    "    return ADD(fibo(SUB1(n)), fibo(SUB2(n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fibo(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We're changing ```if``` now, definining it as a function which takes three expressions: cond, true_exp, false_exp and evaluates it similar to Python's ```if```."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "IF = lambda cond, true_exp, false_exp: true_exp if cond else false_exp\n",
    "\n",
    "def fibo(n):\n",
    "    return IF(\n",
    "        LESS_TWO(n),\n",
    "        ONE,\n",
    "        ADD(fibo(SUB1(n)), fibo(SUB2(n)))\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "ename": "RecursionError",
     "evalue": "maximum recursion depth exceeded in comparison",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mRecursionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-8-403c66400374>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mfibo\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m5\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;31m# -> !$%!@\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-7-0ab9f522b0e0>\u001b[0m in \u001b[0;36mfibo\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m      5\u001b[0m         \u001b[0mLESS_TWO\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m         \u001b[0mONE\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 7\u001b[0;31m         \u001b[0mADD\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfibo\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mSUB1\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mfibo\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mSUB2\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      8\u001b[0m         )\n",
      "... last 1 frames repeated, from the frame below ...\n",
      "\u001b[0;32m<ipython-input-7-0ab9f522b0e0>\u001b[0m in \u001b[0;36mfibo\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m      5\u001b[0m         \u001b[0mLESS_TWO\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m         \u001b[0mONE\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 7\u001b[0;31m         \u001b[0mADD\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfibo\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mSUB1\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mfibo\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mSUB2\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      8\u001b[0m         )\n",
      "\u001b[0;31mRecursionError\u001b[0m: maximum recursion depth exceeded in comparison"
     ]
    }
   ],
   "source": [
    "fibo(5) # -> !$%!@"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Unfortunately this function blow up stack (RecursionError), because of Python's default parameter evaluation - before function computes it's body the all parameters are evaluated; but there is, in the third parameter, recurrence passed, so we ends in infinite loop. Normally Python's ```if``` (like many other imperative languages) doesn't work like that, it has a short circuit evaluation: parameters are evaluated only if necessery, here in the case of ```cond = true```, only the ```true_exp``` is evaluated. \n",
    "The solution would be simulate in some way lazy evaluation, make thunks from parameters passed (i.e. surround them by lambdas) and functions from formal parametrs. Now the ```IF``` will call ```true_fun``` and ```false_fun``` if needed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "IF = lambda cond, true_fun, false_fun: true_fun() if cond else false_fun()\n",
    "\n",
    "def fibo(n):\n",
    "    return IF(\n",
    "        LESS_TWO(n),\n",
    "        lambda: ONE,\n",
    "        lambda: ADD(fibo(SUB1(n)), fibo(SUB2(n)))\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fibo(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's get rid of two argument functions; now we have:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "add = lambda x, y: x + y\n",
    "add(40, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Refactoring in that way:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<function __main__.<lambda>.<locals>.<lambda>(y)>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "add = lambda x: lambda y: x + y;\n",
    "add(40)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "add(40)(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Time to add it to ```fibo```:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "ONE = 1\n",
    "SUB1 = lambda x: x - 1\n",
    "SUB2 = lambda x: x - 2\n",
    "ADD = lambda x: lambda y: x + y\n",
    "LESS_TWO = lambda x: x < 2\n",
    "IF = lambda cond, true_fun, false_fun: true_fun() if cond else false_fun()\n",
    "\n",
    "def fibo(n):\n",
    "    return IF(\n",
    "        LESS_TWO(n),\n",
    "        lambda: ONE,\n",
    "        lambda: ADD(fibo(SUB1(n)))(fibo(SUB2(n)))\n",
    "    )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fibo(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Refactoring ```IF``` in that way gives:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "ONE = 1\n",
    "SUB1 = lambda x: x - 1\n",
    "SUB2 = lambda x: x - 2\n",
    "ADD = lambda x: lambda y: x + y\n",
    "LESS_TWO = lambda x: x < 2\n",
    "IF = lambda cond: lambda true_fun: lambda false_fun: true_fun(None) if cond else false_fun(None)\n",
    "\n",
    "def fibo(n):\n",
    "    return IF(\n",
    "        LESS_TWO(n)\n",
    "    )(\n",
    "        lambda _: ONE\n",
    "    )(\n",
    "        lambda _: ADD(fibo(SUB1(n)))(fibo(SUB2(n)))\n",
    "    )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fibo(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Function ```fibo```, still works, good. In the meantime, I've changed ```lambda expr``` to ```lambda _: expr``` - there is no \"zero argument lambda\" in Lambda Calcullus (underscore is not used variable in Python) and following, I'm calling functions from ```None``` - ```Null``` in Python in lambda definition.\n",
    "\n",
    "Now ```def``` keyword (if all we have are lambdas, what's the point to edfine anything?:)), we change to simple assignment:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "fibo = lambda n: (\n",
    "    IF(\n",
    "        LESS_TWO(n)\n",
    "    )(\n",
    "        lambda _: ONE\n",
    "    )(\n",
    "        lambda _: ADD(fibo(SUB1(n)))(fibo(SUB2(n)))\n",
    "    )\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course, there is not assignemnt in Lambda Calculus, i.e. we can't save name and call it later, the only way to create a new name is: ```lambda name```. So, we create a function and another function ```fibo``` inside it and double calls - now ```fibo``` calls function ```fibo```:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "fibo = lambda fibo: (\n",
    "    lambda n: (\n",
    "    IF(\n",
    "        LESS_TWO(n)\n",
    "    )(\n",
    "        lambda _: ONE\n",
    "    )(\n",
    "        lambda _: ADD(fibo(fibo)(SUB1(n)))(fibo(fibo)(SUB2(n)))\n",
    "    )\n",
    "  )\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fibo(fibo)(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We don't need name ```fibo```. let's change it, to, for example, ```Y```:-)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "fibo = lambda Y: (\n",
    "    lambda n: (\n",
    "    IF(\n",
    "        LESS_TWO(n)\n",
    "    )(\n",
    "        lambda _: ONE\n",
    "    )(\n",
    "        lambda _: ADD(Y(Y)(SUB1(n)))(Y(Y)(SUB2(n)))\n",
    "    )\n",
    "  )\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fibo(fibo)(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I've deleted name ```fibo```, so I don't need assignment now, the only thing is classical refactoring: body of a function in the place of it's name:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(\n",
    "lambda Y: (\n",
    "    lambda n: (\n",
    "    IF(\n",
    "        LESS_TWO(n)\n",
    "    )(\n",
    "        lambda _: ONE\n",
    "    )(\n",
    "        lambda _: ADD(Y(Y)(SUB1(n)))(Y(Y)(SUB2(n)))\n",
    "    )\n",
    "  )\n",
    ")\n",
    "    )(\n",
    "lambda Y: (\n",
    "    lambda n: (\n",
    "    IF(\n",
    "        LESS_TWO(n)\n",
    "    )(\n",
    "        lambda _: ONE\n",
    "    )(\n",
    "        lambda _: ADD(Y(Y)(SUB1(n)))(Y(Y)(SUB2(n)))\n",
    "    )\n",
    "  )\n",
    ")\n",
    "    )(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nice, works, looks less like programming - that's what we aim for:) But still many things to get rid of: booleans, numbers, arithmetic and logic operators...\n",
    "\n",
    "We focus on numbers first, switching attention to Church Numerals, it's nothing wrong with it, the same like binary numbers in Python, they satisfy Peano Arithmetic axioms - means they are equally good to express arithmetic. \n",
    "This what we see on screen: ```1, 3, 42, 1000``` are just numerals, under the hood, in Python are binary, here will be lambdas.\n",
    "So, numbers from scratch (from functions): number will be: function, which takes function and element (of course there is no two valued functions - it's function from function) and returns that function appriopriate number of times - zero for zero, one for one, etc..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "ZERO = lambda f: lambda x: x\n",
    "ONE = lambda f: lambda x: f(x)\n",
    "TWO = lambda f: lambda x: f(f(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also need a trick to compel Python to print it as a number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ZERO(lambda x: x + 1)(0)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cool, so we define more numbers and some functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "ZERO = lambda f: lambda x: x\n",
    "ONE = (lambda f: lambda x: f(x))\n",
    "TWO = (lambda f: lambda x: f(f(x)))\n",
    "THREE = lambda f: lambda x: f(f(f(x)))\n",
    "FIVE = lambda f: lambda x: f(f(f(f(f(x)))))\n",
    "EIGHT = lambda f: lambda x: f(f(f(f(f(f(f(f(x)))))))) \n",
    "IDENTITY = lambda n: (lambda f: lambda x: n(f)(x))\n",
    "INCREMENT = (lambda n: (lambda f: lambda x: f(n(f)(x))))\n",
    "ADD = (lambda n: lambda m: n(INCREMENT)(m))  # use increment on m n times\n",
    "SUBSTRACT = (lambda m: lambda n: n(DECREMENT)(m))\n",
    "MULT = lambda n: lambda m: n(lambda a: ADD(m)(a))(ZERO)\n",
    "DECREMENT = \\\n",
    "    (\n",
    "    (lambda n:\n",
    "     lambda f:\n",
    "     lambda x: n(lambda g: lambda h: h(g(f)))\n",
    "     (lambda u: x)\n",
    "     (lambda u: u))\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is crucial and looking odd function ```IDENTITY```, but it's correct: when applied to one numeral returns it as we want, cause ```n``` and ```f``` will just passed, but appllied to more arguments returns different result:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IDENTITY(TWO)(lambda x: x + 1)(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IDENTITY(TWO)(TWO)(lambda x: x + 1)(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, OK, ```IDENTITY``` changes easily to incrementation (by 1): to make 2 from 1, etc... we need to wrap the body of a function with ```f```.\n",
    "Having the incrementation we have the addition: ```m + n``` is incrementation of ```m``` ```n``` times.\n",
    "Alsa, we have multiplication: it's ```n``` times addition:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ADD(ONE)(TWO)(lambda x: x + 1)(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The same from the ```DECREMENT``` we have the substraction:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "SUBSTRACT(ADD(ONE)(ONE))((ONE))(lambda x: x + 1)(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's great, we have the arithmetic, time for boolean, true and false first:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "NONE = (lambda a: a)\n",
    "TRUE = (lambda m: lambda n: m(NONE))\n",
    "FALSE = (lambda m: lambda n: n(NONE))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "True and False are just conditionals retrurns their, appriopriate, the first and the second element, called on ```NONE``` it's Python, will refactor later. \n",
    "We have, also, ```to_bool``` function to cooperate with Python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def to_bool(p):  \n",
    "    return IF(p)(lambda _: True)(lambda _: False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_bool(TRUE)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Time to ```IF```:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "IF = lambda b: lambda x: lambda y: b(x)(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Works as intended:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IF(TRUE)(lambda _ : 1)(lambda _: 2)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cool, switch to predicates, we change less than to less or equal, build first:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "IS_ZERO = lambda a: a(lambda x: FALSE)(TRUE)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And, base on it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "LESS_OR_EQ = lambda m: lambda n: IS_ZERO(SUBSTRACT(m)(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Substraction returns zero if we substract greater number from smaller:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "SUBSTRACT(ONE)(TWO)(lambda x: x + 1)(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```IS_ZERO``` called from zero returns true, from everything else false, so ```LESS_OR_EQ```works correct: check if difference is not zero:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "to_bool(LESS_OR_EQ(ONE)(TWO))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Final Refactorings\n",
    "So now, we have all blocks:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n"
     ]
    }
   ],
   "source": [
    "print(\n",
    "    (\n",
    "lambda Y : (\n",
    "    lambda n:\n",
    "    IF(\n",
    "        LESS_OR_EQ(n)(ONE)\n",
    "    )(\n",
    "        lambda _: ONE\n",
    "    )(\n",
    "        lambda _: ADD(Y(Y)(SUBSTRACT(n)(ONE)))(Y(Y)(SUBSTRACT(n)(TWO))))\n",
    ")\n",
    "    )(\n",
    "lambda Y : (\n",
    "    lambda n:\n",
    "    IF(\n",
    "        LESS_OR_EQ(n)(ONE)\n",
    "    )(\n",
    "        lambda _: ONE\n",
    "    )(\n",
    "        lambda _: ADD(Y(Y)(SUBSTRACT(n)(ONE)))(Y(Y)(SUBSTRACT(n)(TWO))))\n",
    ")\n",
    "    )\n",
    "    (FIVE)\n",
    "    (lambda x: x + 1)(0)\n",
    ") "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cool, but there is no names in Lambda Calculus (```ONE = lambda f: lambda x: f(x)```), so simply putting, again, function body instead of the name, we, finally have:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n"
     ]
    }
   ],
   "source": [
    "print(\n",
    "    (\n",
    "lambda Y : (\n",
    "    lambda n:\n",
    "    (lambda b: lambda x: lambda y: b(x)(y))(\n",
    "    (lambda m: lambda n: (lambda a: a(lambda x: (lambda m: lambda n: n((lambda a: a))))\n",
    "    ((lambda m: lambda n: m((lambda a: a)))))((lambda m: lambda n: n((\n",
    "    (lambda n:\n",
    "     lambda f:\n",
    "     lambda x: n(lambda g: lambda h: h(g(f)))\n",
    "     (lambda u: x)\n",
    "     (lambda u: u))\n",
    "))(m))(m)(n)))(n)((lambda f: lambda x: f(x)))\n",
    "    )(\n",
    "        lambda _: (lambda f: lambda x: f(x))\n",
    "    )(\n",
    "        lambda _: (lambda n: lambda m: n((lambda n: (lambda f: lambda x: f(n(f)(x)))))(m))(Y(Y)((lambda m: lambda n: n((\n",
    "    (lambda n:\n",
    "     lambda f:\n",
    "     lambda x: n(lambda g: lambda h: h(g(f)))\n",
    "     (lambda u: x)\n",
    "     (lambda u: u))\n",
    "))(m))(n)\n",
    "        ((lambda f: lambda x: f(x)))))(Y(Y)((lambda m: lambda n: n((\n",
    "    (lambda n:\n",
    "     lambda f:\n",
    "     lambda x: n(lambda g: lambda h: h(g(f)))\n",
    "     (lambda u: x)\n",
    "     (lambda u: u))\n",
    "))(m))(n)\n",
    "        ((lambda f: lambda x: f(f(x)))))))\n",
    ")\n",
    "    )(\n",
    "lambda Y : (\n",
    "    lambda n:\n",
    "    (lambda b: lambda x: lambda y: b(x)(y))(\n",
    "        (lambda m: lambda n: (lambda a: a(lambda x: (lambda m: lambda n: n((lambda a: a))))\n",
    "        ((lambda m: lambda n: m((lambda a: a)))))((lambda m: lambda n: n((\n",
    "    (lambda n:\n",
    "     lambda f:\n",
    "     lambda x: n(lambda g: lambda h: h(g(f)))\n",
    "     (lambda u: x)\n",
    "     (lambda u: u))\n",
    "))(m))(m)(n)))(n)((lambda f: lambda x: f(x)))\n",
    "    )(\n",
    "        lambda _: (lambda f: lambda x: f(x))\n",
    "    )(\n",
    "        lambda _: (lambda n: lambda m: n((lambda n: (lambda f: lambda x: f(n(f)(x)))))(m))(Y(Y)((lambda m: lambda n: n((\n",
    "    (lambda n:\n",
    "     lambda f:\n",
    "     lambda x: n(lambda g: lambda h: h(g(f)))\n",
    "     (lambda u: x)\n",
    "     (lambda u: u))\n",
    "))(m))(n)\n",
    "        ((lambda f: lambda x: f(x)))))(Y(Y)((lambda m: lambda n: n((\n",
    "    (lambda n:\n",
    "     lambda f:\n",
    "     lambda x: n(lambda g: lambda h: h(g(f)))\n",
    "     (lambda u: x)\n",
    "     (lambda u: u))\n",
    "))(m))(n)\n",
    "        ((lambda f: lambda x: f(f(x)))))))\n",
    ")\n",
    "    )\n",
    "    (lambda f: lambda x: f(f(f(f(f(x))))))\n",
    "    (lambda x: x + 1)(0)\n",
    ") "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I've added ```print``` instruction in the last two, due to some Python indentation mess (but it's not invalidate the main  argument). \n",
    "Job's done, building from something small, like lambda functions, we have fairly complicated function (Fibonacci). \n",
    "Salute to Lambda Calculus!\n",
    "Thanks for reading!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}