{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# Lambda calculus in Kotlin\n",
    "\n",
    "Hello! Here is a Kotlin Notebook for anyone to learn lambda calculus from the basics to combinators.\n",
    "\n",
    "Kotlin Notebook provides a REPL way to run code, and Kotlin allows you to write lambda calculus in a concise and readable way.\n",
    "\n",
    "If you are not familiar with Kotlin or lambda calculus, it's OK. There will be simple syntaxes.\n",
    "\n",
    "If you want to learn more about Kotlin's lambda, please visit [kotlinlang.org/lambdas](https://kotlinlang.org/docs/lambdas.html#lambda-expressions-and-anonymous-functions)."
   ]
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Background knowledge\n",
    "\n",
    "Lambda calculus is a formal system for expressing computation based on function abstraction and application.\n",
    "I assume you already know what a function is in math and programming. Then Let's start from the basics.\n",
    "\n",
    "In the world of lambda calculus, functions are anonymous, taking a single parameter and returning a single value.\n",
    "Even more, everythings in lambda calculus is a function.\n",
    "\n",
    "Let's define a function:\n",
    "\n",
    "```\n",
    "λx.x\n",
    "```\n",
    "\n",
    "It means `x` is a parameter and `x` is a return value. This function takes a parameter `x` and returns `x` without any difference.\n",
    "\n",
    "We should remember everything in lambda calculus is a function. We can define some other functions:\n",
    "\n",
    "```\n",
    "λx.x(x)(x)\n",
    "λx.λy.x\n",
    "```\n",
    "\n",
    "Confused? The first function's parameter is `x`, which is simple. Because `x` is a function, so `x(x)` means passing `x` itself as a parameter to `x`. Furthermore, `x(x)` is also a function, so `x(x)(x)` means passing `x` as a parameter to `x(x)`.\n",
    "The second function's parameter is `x`. It returns a expression `λy.x`, which is also a function.\n",
    "\n",
    "To make it simpler to write, the example above is often written in:\n",
    "\n",
    "```\n",
    "λx.xxx\n",
    "λxy.x\n",
    "```\n",
    "\n",
    "Let me explain it: `abc` means `(a(b))(c)`, just like `1+2+3` means `((1+2)+3)`.\n",
    "`λabc.xyz` means `λa.λb.λc.xyz`. When it takes a parameter `a`, it returns `λb.λc.xyz`, which is also a function.\n",
    "And the returned function takes a parameter `b` and returns `λc.xyz`.\n",
    "Finally, the returned function takes a parameter `c` and returns `xyz`.\n",
    "\n",
    "After these practices, you can conclude that there are two things in lambda calculus: function and applying."
   ]
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Basic interface definition\n",
    "\n",
    "Since `kotlin.Function1<P0, R>` is not able to express a recursive lambda type, whose parameter and return type are both itself, we define a new interface `Lambda` to express it."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "collapsed": true,
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:25.439631300Z",
     "start_time": "2025-07-15T16:18:25.286770Z"
    }
   },
   "source": [
    "fun interface Lambda {\n",
    "    operator fun invoke(f: Lambda): Lambda\n",
    "}"
   ],
   "outputs": [],
   "execution_count": 1
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Shorthand for defining a lambda expression with currying\n",
    "\n",
    "If we want to write `λab.a` in Kotlin, embedded braces like `{ a -> { b -> a } }` are annoying.\n",
    "Thus, we can use currying to simplify it."
   ]
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:25.978334700Z",
     "start_time": "2025-07-15T16:18:25.464666100Z"
    }
   },
   "cell_type": "code",
   "source": [
    "fun lambda(block: (Lambda) -> Lambda) =\n",
    "    Lambda { p0 -> block(p0) }\n",
    "\n",
    "fun lambda(block: (Lambda, Lambda) -> Lambda) =\n",
    "    Lambda { p0 -> lambda { p1 -> block(p0, p1) } }\n",
    "\n",
    "fun lambda(block: (Lambda, Lambda, Lambda) -> Lambda) =\n",
    "    Lambda { p0 -> lambda { p1, p2 -> block(p0, p1, p2) } }\n",
    "\n",
    "fun lambda(block: (Lambda, Lambda, Lambda, Lambda) -> Lambda) =\n",
    "    Lambda { p0 -> lambda { p1, p2, p3 -> block(p0, p1, p2, p3) } }\n",
    "\n",
    "fun lambda(block: (Lambda, Lambda, Lambda, Lambda, Lambda) -> Lambda) =\n",
    "    Lambda { p0 -> lambda { p1, p2, p3, p4 -> block(p0, p1, p2, p3, p4) } }\n",
    "\n",
    "fun lambda(block: (Lambda, Lambda, Lambda, Lambda, Lambda, Lambda) -> Lambda) =\n",
    "    Lambda { p0 -> lambda { p1, p2, p3, p4, p5 -> block(p0, p1, p2, p3, p4, p5) } }"
   ],
   "outputs": [],
   "execution_count": 2
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Church numbers\n",
    "\n",
    "Then we can define Church numbers.\n",
    "\n",
    "Church number is a way to define natural numbers.\n",
    "It is a function `n` that takes a function `f` and a value `x` and apply `f` for `n` times on `x`.\n",
    "For example:"
   ]
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:26.516784300Z",
     "start_time": "2025-07-15T16:18:25.990331700Z"
    }
   },
   "cell_type": "code",
   "source": [
    "val zero = lambda { f, x -> x }\n",
    "val one = lambda { f, x -> f(x) }\n",
    "val two = lambda { f, x -> f(f(x)) }\n",
    "val three = lambda { f, x -> f(f(f(x))) }\n",
    "val four = lambda { f, x -> f(f(f(f(x)))) }\n",
    "val five = lambda { f, x -> f(f(f(f(f(x))))) }"
   ],
   "outputs": [],
   "execution_count": 3
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "To make it visible, we can define a function to transform from Church numbers to `kotlin.Int`."
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:26.738367600Z",
     "start_time": "2025-07-15T16:18:26.552094300Z"
    }
   },
   "cell_type": "code",
   "source": [
    "val identity = lambda { it -> it }\n",
    "\n",
    "fun Lambda.toInt(): Int {\n",
    "    var count = 0\n",
    "    this { count++; it }(identity)\n",
    "    return count\n",
    "}"
   ],
   "outputs": [],
   "execution_count": 4
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "And the reversed transform:"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:26.965470600Z",
     "start_time": "2025-07-15T16:18:26.764402900Z"
    }
   },
   "cell_type": "code",
   "source": [
    "fun Int.toChurch(): Lambda =\n",
    "    if (this <= 0) zero\n",
    "    else Lambda { f -> Lambda { x -> f((this - 1).toChurch()(f)(x)) } }"
   ],
   "outputs": [],
   "execution_count": 5
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "Let's see the output:"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:27.204891200Z",
     "start_time": "2025-07-15T16:18:26.979109800Z"
    }
   },
   "cell_type": "code",
   "source": [
    "println(zero.toInt())\n",
    "println(one.toInt())\n",
    "println(two.toInt())\n",
    "println(0.toChurch().toInt())\n",
    "println(100.toChurch().toInt())"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\r\n",
      "1\r\n",
      "2\r\n",
      "0\r\n",
      "100\r\n"
     ]
    }
   ],
   "execution_count": 6
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "It matches our expectation."
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Basic arithmetics\n",
    "\n",
    "Let's start from the simplest ones."
   ]
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:27.355673Z",
     "start_time": "2025-07-15T16:18:27.218890300Z"
    }
   },
   "cell_type": "code",
   "source": [
    "val successor = lambda { n, f, x -> f(n(f)(x)) }\n",
    "val multiply = lambda { m, n, f -> m(n(f)) }\n",
    "val pow = lambda { a, b -> b(a) }"
   ],
   "outputs": [],
   "execution_count": 7
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "And let's define operators in Kotlin for them."
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:27.490592300Z",
     "start_time": "2025-07-15T16:18:27.389924700Z"
    }
   },
   "cell_type": "code",
   "source": [
    "operator fun Lambda.plus(other: Lambda): Lambda = this(successor)(other)\n",
    "operator fun Lambda.times(other: Lambda): Lambda = multiply(this)(other)"
   ],
   "outputs": [],
   "execution_count": 8
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "Let's test them."
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:27.589878700Z",
     "start_time": "2025-07-15T16:18:27.512496700Z"
    }
   },
   "cell_type": "code",
   "source": "println((one + two * three).toInt())",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\r\n"
     ]
    }
   ],
   "execution_count": 9
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "When it comes to substraction, things are bit of more complex.\n",
    "\n",
    "We need a pair `(0, 0)`. Then we define a `Φ` combinator, which moves a pair `(a, b)` to `(b, b+1)`.\n",
    "We invoke `Φ` for `n` times on `(0, 0)`, and we get `(n-1, n)` in the end.\n",
    "Finally, we only need to get the first element of the pair. Then we get `n-1` from `n`."
   ]
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:27.815878700Z",
     "start_time": "2025-07-15T16:18:27.625878500Z"
    }
   },
   "cell_type": "code",
   "source": [
    "val pair = lambda { a, b, f -> f(a)(b) }\n",
    "val first = lambda { a, b -> a }\n",
    "val second = lambda { a, b -> b }\n",
    "val fai = lambda { p -> pair(p(second))(successor(p(second))) }"
   ],
   "outputs": [],
   "execution_count": 10
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "Let's test out pair."
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:28.008494700Z",
     "start_time": "2025-07-15T16:18:27.823888400Z"
    }
   },
   "cell_type": "code",
   "source": [
    "{\n",
    "    val myPair = pair(10.toChurch())(20.toChurch())\n",
    "    println(myPair(first).toInt())\n",
    "    println(myPair(second).toInt())\n",
    "    println(fai(myPair)(first).toInt())\n",
    "    println(fai(myPair)(second).toInt())\n",
    "}()"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\r\n",
      "20\r\n",
      "20\r\n",
      "21\r\n"
     ]
    }
   ],
   "execution_count": 11
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "It seems that `pair` and `fai` works correctly.\n",
    "\n",
    "Now we can write the substraction."
   ]
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:28.206850200Z",
     "start_time": "2025-07-15T16:18:28.043818400Z"
    }
   },
   "cell_type": "code",
   "source": [
    "val predecessor = lambda { n -> n(fai)(pair(zero)(zero))(first) }\n",
    "val subtract = lambda { a, b -> b(predecessor)(a) }\n",
    "operator fun Lambda.minus(other: Lambda): Lambda = subtract(this)(other)"
   ],
   "outputs": [],
   "execution_count": 12
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "Let's test it."
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:28.339856900Z",
     "start_time": "2025-07-15T16:18:28.262485600Z"
    }
   },
   "cell_type": "code",
   "source": "println((25.toChurch() - 13.toChurch()).toInt())",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12\r\n"
     ]
    }
   ],
   "execution_count": 13
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Boolean arithmetics\n",
    "\n",
    "We need to define `true` and `false` first."
   ]
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:28.480852600Z",
     "start_time": "2025-07-15T16:18:28.381797900Z"
    }
   },
   "cell_type": "code",
   "source": [
    "val `true` = lambda { a, b -> a }\n",
    "val `false` = lambda { a, b -> b }"
   ],
   "outputs": [],
   "execution_count": 14
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "Have you noticed? `true` is same as `first` of `pair` and `false` is same as `second` of `pair`.\n",
    "\n",
    "Then, we can define basic logic operators."
   ]
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:28.684153400Z",
     "start_time": "2025-07-15T16:18:28.525501100Z"
    }
   },
   "cell_type": "code",
   "source": [
    "val and = lambda { a, b -> a(b)(a) }\n",
    "val or = lambda { a, b -> a(a)(b) }\n",
    "val not = lambda { a -> a(`false`)(`true`) }\n",
    "val xor = lambda { a, b -> a(not(b))(b) }"
   ],
   "outputs": [],
   "execution_count": 15
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "Confused? Me too.\n",
    "\n",
    "They are kind of tricky things, so we need to check if they are right. Make it visible!"
   ]
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:28.807567500Z",
     "start_time": "2025-07-15T16:18:28.692153300Z"
    }
   },
   "cell_type": "code",
   "source": [
    "fun Lambda.toBoolean(): Boolean {\n",
    "    var result = false\n",
    "    this(lambda { it -> result = true;it })(lambda { it -> result = false;it })(identity)\n",
    "    return result\n",
    "}"
   ],
   "outputs": [],
   "execution_count": 16
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:29.369639800Z",
     "start_time": "2025-07-15T16:18:28.819622900Z"
    }
   },
   "cell_type": "code",
   "source": [
    "println(\"--- NOT ---\")\n",
    "println(\"not(true) = ${not(`true`).toBoolean()}\")\n",
    "println(\"not(false) = ${not(`false`).toBoolean()}\")\n",
    "println()\n",
    "\n",
    "println(\"--- AND ---\")\n",
    "println(\"true and true = ${and(`true`)(`true`).toBoolean()}\")\n",
    "println(\"true and false = ${and(`true`)(`false`).toBoolean()}\")\n",
    "println(\"false and true = ${and(`false`)(`true`).toBoolean()}\")\n",
    "println(\"false and false = ${and(`false`)(`false`).toBoolean()}\")\n",
    "println()\n",
    "\n",
    "println(\"--- OR ---\")\n",
    "println(\"true or true = ${or(`true`)(`true`).toBoolean()}\")\n",
    "println(\"true or false = ${or(`true`)(`false`).toBoolean()}\")\n",
    "println(\"false or true = ${or(`false`)(`true`).toBoolean()}\")\n",
    "println(\"false or false = ${or(`false`)(`false`).toBoolean()}\")\n",
    "println()\n",
    "\n",
    "println(\"--- XOR ---\")\n",
    "println(\"true xor true = ${xor(`true`)(`true`).toBoolean()}\")\n",
    "println(\"true xor false = ${xor(`true`)(`false`).toBoolean()}\")\n",
    "println(\"false xor true = ${xor(`false`)(`true`).toBoolean()}\")\n",
    "println(\"false xor false = ${xor(`false`)(`false`).toBoolean()}\")"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--- NOT ---\r\n",
      "not(true) = false\r\n",
      "not(false) = true\r\n",
      "\r\n",
      "--- AND ---\r\n",
      "true and true = true\r\n",
      "true and false = false\r\n",
      "false and true = false\r\n",
      "false and false = false\r\n",
      "\r\n",
      "--- OR ---\r\n",
      "true or true = true\r\n",
      "true or false = true\r\n",
      "false or true = true\r\n",
      "false or false = false\r\n",
      "\r\n",
      "--- XOR ---\r\n",
      "true xor true = false\r\n",
      "true xor false = true\r\n",
      "false xor true = true\r\n",
      "false xor false = false\r\n"
     ]
    }
   ],
   "execution_count": 17
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "After boolean calculations, do you want `if` and `else`? Let's do it!"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:29.521598400Z",
     "start_time": "2025-07-15T16:18:29.439411800Z"
    }
   },
   "cell_type": "code",
   "source": "val `if` = lambda { c, t, f -> c(t)(f) }",
   "outputs": [],
   "execution_count": 18
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:29.651289700Z",
     "start_time": "2025-07-15T16:18:29.529599900Z"
    }
   },
   "cell_type": "code",
   "source": [
    "println(\"if (true) 25 else 10 = ${`if`(`true`)(25.toChurch())(10.toChurch()).toInt()}\")\n",
    "println(\"if (false) 25 else 10 = ${`if`(`false`)(25.toChurch())(10.toChurch()).toInt()}\")"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "if (true) 25 else 10 = 25\r\n",
      "if (false) 25 else 10 = 10\r\n"
     ]
    }
   ],
   "execution_count": 19
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "Since `zero` is `λfx.x`, we can easily define `isZero` and comparators.\n",
    "\n",
    "Please notice that in Church numbers, there's no negative number. `5-10` is `0`."
   ]
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:29.927705100Z",
     "start_time": "2025-07-15T16:18:29.735991700Z"
    }
   },
   "cell_type": "code",
   "source": [
    "val isZero = lambda { n -> n(`true`(`false`))(`true`) }\n",
    "val le = lambda { a, b -> isZero(a - b) }\n",
    "val eq = lambda { a, b -> and(le(a)(b))(le(b)(a)) }"
   ],
   "outputs": [],
   "execution_count": 20
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:30.210222300Z",
     "start_time": "2025-07-15T16:18:29.952741800Z"
    }
   },
   "cell_type": "code",
   "source": [
    "println(\"--- isZero ---\")\n",
    "println(\"isZero(zero) = ${isZero(zero).toBoolean()}\")\n",
    "println(\"isZero(three) = ${isZero(three).toBoolean()}\")\n",
    "println(\"--- Less than or Equal (le) ---\")\n",
    "println(\"2 <= 5 = ${le(two)(five).toBoolean()}\")\n",
    "println(\"5 <= 2 = ${le(five)(two).toBoolean()}\")\n",
    "println(\"3 <= 3 = ${le(three)(three).toBoolean()}\")\n",
    "println(\"--- Equal (eq) ---\")\n",
    "println(\"3 == 5 = ${eq(three)(five).toBoolean()}\")\n",
    "println(\"5 == 3 = ${eq(five)(three).toBoolean()}\")\n",
    "println(\"3 == 3 = ${eq(three)(three).toBoolean()}\")"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--- isZero ---\r\n",
      "isZero(zero) = true\r\n",
      "isZero(three) = false\r\n",
      "--- Less than or Equal (le) ---\r\n",
      "2 <= 5 = true\r\n",
      "5 <= 2 = false\r\n",
      "3 <= 3 = true\r\n",
      "--- Equal (eq) ---\r\n",
      "3 == 5 = false\r\n",
      "5 == 3 = false\r\n",
      "3 == 3 = true\r\n"
     ]
    }
   ],
   "execution_count": 21
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Recursive\n",
    "\n",
    "After mastering these basic operations, it's time to try some high-level things!\n",
    "\n",
    "Let's define a recursive `fibonacci` function.\n",
    "\n",
    "In the world of lambda calculus, every function is anonymous, so we cannot refer to it by name.\n",
    "Luckily, we have parameters. We can pass the lambda it self as a parameter.\n",
    "Thus, we can define a recursive `fibonacci` function that takes 2 parameters: `self` and `n`.\n",
    "Please notice that `self` is also a lambda that need `self` as a parameter."
   ]
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:30.387000400Z",
     "start_time": "2025-07-15T16:18:30.241664700Z"
    }
   },
   "cell_type": "code",
   "source": [
    "val metaFibonacci0 =\n",
    "    lambda { self, n -> if (le(n)(two).toBoolean()) one else self(self)(n - one) + self(self)(n - two) }\n",
    "val fibonacci0 = metaFibonacci0(metaFibonacci0)"
   ],
   "outputs": [],
   "execution_count": 22
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "By this interesting trick, we can define a recursive function in lambda calculus."
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:30.638478100Z",
     "start_time": "2025-07-15T16:18:30.399001600Z"
    }
   },
   "cell_type": "code",
   "source": [
    "for (n in 1..10) {\n",
    "    println(\"fibonacci($n) = ${fibonacci0(n.toChurch()).toInt()}\")\n",
    "}"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "fibonacci(1) = 1\r\n",
      "fibonacci(2) = 1\r\n",
      "fibonacci(3) = 2\r\n",
      "fibonacci(4) = 3\r\n",
      "fibonacci(5) = 5\r\n",
      "fibonacci(6) = 8\r\n",
      "fibonacci(7) = 13\r\n",
      "fibonacci(8) = 21\r\n",
      "fibonacci(9) = 34\r\n",
      "fibonacci(10) = 55\r\n"
     ]
    }
   ],
   "execution_count": 23
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "We noticed some repeats in our code (`self(self)` and `meta(meta)`). Let's wipe them out."
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:30.858243100Z",
     "start_time": "2025-07-15T16:18:30.653840900Z"
    }
   },
   "cell_type": "code",
   "source": [
    "val omega = lambda { r -> r(r) } // this is called K combinator or Ω-combinator\n",
    "val metaFibonacci1 = lambda { self, n ->\n",
    "    val f = omega(self)\n",
    "    if(le(n)(two).toBoolean()) one else f(n - one) + f(n - two)\n",
    "}\n",
    "val fibonacci1 = omega(metaFibonacci1)"
   ],
   "outputs": [],
   "execution_count": 24
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:30.970257100Z",
     "start_time": "2025-07-15T16:18:30.870250700Z"
    }
   },
   "cell_type": "code",
   "source": [
    "for (n in 1..10) {\n",
    "    println(\"fibonacci($n) = ${fibonacci1(n.toChurch()).toInt()}\")\n",
    "}"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "fibonacci(1) = 1\r\n",
      "fibonacci(2) = 1\r\n",
      "fibonacci(3) = 2\r\n",
      "fibonacci(4) = 3\r\n",
      "fibonacci(5) = 5\r\n",
      "fibonacci(6) = 8\r\n",
      "fibonacci(7) = 13\r\n",
      "fibonacci(8) = 21\r\n",
      "fibonacci(9) = 34\r\n",
      "fibonacci(10) = 55\r\n"
     ]
    }
   ],
   "execution_count": 25
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "But it's still repeating. Let's do some more.\n",
    "\n",
    "We want a simpler `metaFibonacci` that can be written as: `λfx.if(x<=2) 1 else f(x-1)+f(x-2)`. Then we need to find a way to make a infinite call like `f(f(f(f(f(...))))`.\n",
    "\n",
    "We can do it by using `Y combinator`. It has a interesting property: `Y(f) = f(Y(f)) = f(f(Y(f)) = f(f(f(f(f(...))))`.\n",
    "\n",
    "Without knowing how we can find it, we can test it with a fake one."
   ]
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:31.165796900Z",
     "start_time": "2025-07-15T16:18:30.993494200Z"
    }
   },
   "cell_type": "code",
   "source": [
    "val metaFibonacci2 =\n",
    "    lambda { f, n -> if (le(n)(two).toBoolean()) one else f(n - one) + f(n - two) }\n",
    "val fakeY = lambda { f -> f(f(f(f(f(f(f(f))))))) } // fake Y combinator, limited to 8 levels\n",
    "val fakefibonacci2 = fakeY(metaFibonacci2)"
   ],
   "outputs": [],
   "execution_count": 26
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:31.289957700Z",
     "start_time": "2025-07-15T16:18:31.190324600Z"
    }
   },
   "cell_type": "code",
   "source": [
    "for (n in 1..10) {\n",
    "    println(\"fibonacci($n) = ${fakefibonacci2(n.toChurch()).toInt()}\")\n",
    "}"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "fibonacci(1) = 1\r\n",
      "fibonacci(2) = 1\r\n",
      "fibonacci(3) = 2\r\n",
      "fibonacci(4) = 3\r\n",
      "fibonacci(5) = 5\r\n",
      "fibonacci(6) = 8\r\n",
      "fibonacci(7) = 13\r\n",
      "fibonacci(8) = 21\r\n",
      "fibonacci(9) = 32\r\n",
      "fibonacci(10) = 40\r\n"
     ]
    }
   ],
   "execution_count": 27
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "fYou can see things going wrong after `fibonacci(8)` because it's not an infinite `f(f(f(f(f(...))))`.\n",
    "\n",
    "To define a real `Y` combinator, we need to use the trick used in `fibonacci0`.\n",
    "If we can't really write `Y = λf.f(Yf)` because we can't refer to `y` by name, we can refer it as a parameter."
   ]
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:31.411967200Z",
     "start_time": "2025-07-15T16:18:31.321957500Z"
    }
   },
   "cell_type": "code",
   "source": [
    "val metaY = lambda { self, f -> f(self(self)(f)) }\n",
    "val y = metaY(metaY)"
   ],
   "outputs": [],
   "execution_count": 28
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "You can expand this `Y` combinator:\n",
    "```\n",
    "Y = metaY(metaY)\n",
    "  = (λab.b((aab))(λab.b(aab)) // Y\n",
    "  = λf.f((λab.b(a(a))(λab.b(a(a)))f) // λf.f(Yf)\n",
    "```\n",
    "It has a more commonly known syntax: `λf.(λx.f(xx))(λx.f(xx))`."
   ]
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:31.560780600Z",
     "start_time": "2025-07-15T16:18:31.436819900Z"
    }
   },
   "cell_type": "code",
   "source": [
    "try {\n",
    "    val fibonacci2 = y(metaFibonacci2)\n",
    "    fibonacci2(3.toChurch())\n",
    "} catch (e: StackOverflowError) {\n",
    "    println(\"Stack overflow!\")\n",
    "}\n"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Stack overflow!\r\n"
     ]
    }
   ],
   "execution_count": 29
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "But when you want to use this `Y` combinator to build an actual `fibonacci` function, you will fail from `StackOverflowError`.\n",
    "The reason is that we have an infinite `f(f(f(f(f(...))))`.\n",
    "\n",
    "To solve this issue, we can use the trick of deferred evaluation, or you can call it a functional parameter.\n",
    "This solution is called `Z` combinator."
   ]
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:31.728058800Z",
     "start_time": "2025-07-15T16:18:31.616448800Z"
    }
   },
   "cell_type": "code",
   "source": [
    "val metaZ = lambda { self, f -> f { x -> self(self)(f)(x) } }\n",
    "val z = metaZ(metaZ)\n",
    "val fibonacci2 = z(metaFibonacci2)"
   ],
   "outputs": [],
   "execution_count": 30
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-07-15T16:18:31.842249900Z",
     "start_time": "2025-07-15T16:18:31.754056100Z"
    }
   },
   "cell_type": "code",
   "source": [
    "for (n in 1..10) {\n",
    "    println(\"fibonacci($n) = ${fibonacci2(n.toChurch()).toInt()}\")\n",
    "}"
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "fibonacci(1) = 1\r\n",
      "fibonacci(2) = 1\r\n",
      "fibonacci(3) = 2\r\n",
      "fibonacci(4) = 3\r\n",
      "fibonacci(5) = 5\r\n",
      "fibonacci(6) = 8\r\n",
      "fibonacci(7) = 13\r\n",
      "fibonacci(8) = 21\r\n",
      "fibonacci(9) = 34\r\n",
      "fibonacci(10) = 55\r\n"
     ]
    }
   ],
   "execution_count": 31
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## References\n",
    "\n",
    "- [Wikipedia](https://en.wikipedia.org/wiki/Lambda_calculus)\n",
    "- [A Tutorial Introduction to the Lambda Calculus](https://personal.utdallas.edu/~gupta/courses/apl/lambda.pdf)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Kotlin",
   "language": "kotlin",
   "name": "kotlin"
  },
  "language_info": {
   "name": "kotlin",
   "version": "2.2.20-dev-4982",
   "mimetype": "text/x-kotlin",
   "file_extension": ".kt",
   "pygments_lexer": "kotlin",
   "codemirror_mode": "text/x-kotlin",
   "nbconvert_exporter": ""
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}