13_2_About_The_Lambda_Calculus.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "13_2_About_The_Lambda_Calculus.ipynb",
      "provenance": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/LivesayMe/AlpacaTrader/blob/main/13_2_About_The_Lambda_Calculus.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "z6S3fs7Ia2rm"
      },
      "source": [
        "# About The Lambda Calculus\n",
        "## Readiness Assurance Test\n",
        "### Due: Wednesday, 31 March 2021, 2:45pm"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LYmfBBPdxwlh"
      },
      "source": [
        "## TODO Define gcd"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Wz0_Shc8yFgO"
      },
      "source": [
        "Euclid's method to compute the greatest common divisor of two natural numbers can be specified in the Lambda syntax as:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lSm4IRKqx65i"
      },
      "source": [
        "gcd = lambda x: lambda y: y if (x==y) else gcd(x-y)(y) if (x>y) else gcd(x)(y-x)"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4fDpfrvpVjjw"
      },
      "source": [
        "Much like Chapter 18 shows how to compute ```fact``` to be ```Ye(prefact)```, show how to compute ```pregcd``` using a ```Ye``` application."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Qa67gbR4Vk_J"
      },
      "source": [
        "Ye = lambda f: (lambda x: x(x))(lambda y: f(lambda v: y(y)(v)))"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NC5NbP5etGCg"
      },
      "source": [
        "\n",
        "Note that ```pregcd``` is *curried* (see page 311); but that does not matter yet --- computing ```gcd``` from ```pregcd``` works the same despite having a curried function of two arguments. So, define ```pregcd``` in this manner, and then ```gcd```.\n",
        "    \n",
        "Then, using your ```gcd``` function, evaluate these:\n",
        "* ```gcd(450)(6000)```\n",
        "* ```gcd(450)(6001)```\n",
        "* ```gcd(450)(6002)```\n",
        "* ```gcd(450)(6003)```\n",
        "* ```gcd(453)(6003)```"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "AAQD6DA_xjKg"
      },
      "source": [
        "Your answers go here."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "NsPf7cZG5gMo",
        "outputId": "37db5ab0-93c6-453c-8a89-a263baa28c15"
      },
      "source": [
        "print(gcd(450)(6000))\n",
        "print(gcd(450)(6001))\n",
        "print(gcd(450)(6002))\n",
        "print(gcd(450)(6003))\n",
        "print(gcd(453)(6003))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "150\n",
            "1\n",
            "2\n",
            "9\n",
            "3\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "d6dWC5B1xk6T"
      },
      "source": [
        "## The Ye Combinator"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WJ_L5XKQxnTB"
      },
      "source": [
        "Study how to show that $Y_e$ is indeed a **fixed point** combinator. This means that for any $G$, we get\n",
        "\n",
        "$Y_e\\; G = G(Y_e\\: G)$\n",
        "\n",
        "Remember, a combinator is just a function with no free variables.\n",
        "\n",
        "For visual clarity, the following steps use $()$ or $[]$ interchangeably.\n",
        "\n",
        "1. $Y_e G = (\\lambda f. (\\lambda x. (xx) [\\lambda y. f(\\lambda v. ((yy)v))])G$ --- Apply Beta reduction to pull in $G$, and get\n",
        "2. $ = (\\lambda x. (xx) [\\lambda y. G(\\lambda v. ((yy)v))])$ --- Apply Beta reduction once again.\n",
        "3. $ = [\\lambda y. G(\\lambda v. ((yy)v))] [\\lambda y. G(\\lambda v. ((yy)v))]$ --- This is $Y_e G$, which we will use later!\n",
        "4. $ = G(\\lambda v. (( [\\lambda y. G(\\lambda v. ((yy)v))] [\\lambda y. G(\\lambda v. ((yy)v))]  )v ))$ --- Apply Beta reduction once again.\n",
        "5. $ = G(\\lambda v. (( Y_e G  )v ))$ --- Using (3) from above.\n",
        "6. $ = G( Y_e G )$ --- Using Eta reduction.\n",
        "\n",
        "Or, as Ganesh [shows more colorfully](https://drive.google.com/file/d/1ikri1pU4LkiNzlkCQW5AdpoanwC0HS5q/view) --- the trick is to see what a previous step, i.e. (3) --- designated as (*) in his document --- had already calculated!\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_gKXLEemePS9"
      },
      "source": [
        "Compare with [Hai (Paul) Liu’s step-by-step Lambda Viewer](http://projectultimatum.org/cgi-bin/lambda). Just copy and paste into the text box in the Lambda Viewer the lambda expression\n",
        "   \n",
        "(\\f.(\\x.(x x)) (\\y.f(\\v.((y y) v)))) g\n",
        "\n",
        "Play around with different modes of evaluation from the drop-down menu."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UKCrefyTz4-2"
      },
      "source": [
        "## TODO Now You Try It"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8I91Vioyz7XE"
      },
      "source": [
        "Define the $L$ function as follows:\n",
        "\n",
        "$L = \\lambda{}abcdefghijklmnopqstuvwxyzr.r(thisisafixedpointcombinator)$\n",
        "\n",
        "Your task is to show that $L^{26}$ ($L$ applied to itself 26 times --- treated as a single function) is a fixed point combinator.\n",
        "\n",
        "So, you must show that for any function $G$, $L^{26} G = G (L^{26} G)$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "D-5IbFm7NxVs"
      },
      "source": [
        "As L is called on itself, it replaces the letters in the output with L istelf. After bing called on itself 26 times it will reduce to L(LLLLLLLLLLLLLLLLLLLLLLLLLLLL) when it is called the final time it is replaced with G."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nLqXts2FbOz6"
      },
      "source": [
        "### Hint"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "roFhubAcbRq4"
      },
      "source": [
        "$L^2 = L L = \\lambda{}bcdefghijklmnopqstuvwxyzr.r(thisisLfixedpointcombinLtor)$\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "HvvMeRx98LeA",
        "outputId": "f00f3879-6e2d-4ec9-bd01-0ebad0cf16d8"
      },
      "source": [
        "len(\"thisisafixedpointcombinator\")"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "27"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 12
        }
      ]
    }
  ]
}