Y-combinator.ipynb

Y-combinator.ipynb

{
  "cells": [
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "ラムダ計算の不動点を利用して https://www.youtube.com/watch?v=PNL0-0z40PY のthumbnailを生成してみた"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "using Match\n\nreduce(ex) = ex\nfunction reduce(ex::Expr)\n    @match ex.head begin\n        :->   => Expr(:->, ex.args[1], reduce(ex.args[2]))\n        :call => apply(ex.args[1], ex.args[2])\n    end\nend\n\nreduceinner(func, arg) = Expr(:call, func, reduce(arg))\napply(func, arg) = reduceinner(func, arg)\nfunction apply(func::Expr, arg)\n    func.head == :-> || return reduceinner(func, arg)\n    subst(func.args[2], func.args[1], arg)\nend\n\nsubst(ex, sym, arg) = ex\nsubst(ex::Symbol, sym, arg) = (ex == sym ? arg : ex)\nfunction subst(ex::Expr, sym, arg)\n    @match ex.head begin\n        :-> => if ex.args[1] == sym\n            ex\n        else\n            Expr(:->, ex.args[1], subst(ex.args[2], sym, arg))\n        end\n        :call => Expr(:call, subst(ex.args[1], sym, arg), subst(ex.args[2], sym, arg))\n    end\nend",
      "execution_count": 1,
      "outputs": [
        {
          "data": {
            "text/plain": "subst (generic function with 3 methods)"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "struct Troll end\n\nisfixpointof(ex, func) = false\nfunction isfixpointof(ex::Expr, func)\n    ishalfoffixpoint(ex) = false\n    function ishalfoffixpoint(ex::Expr)\n        (ex.head == :-> && ex.args[1] isa Symbol) || return false\n        body = ex.args[2]\n        Meta.isexpr(body, :call)         &&\n        length(body.args) == 2           &&\n        body.args[1] == func             &&\n        Meta.isexpr(body.args[2], :call) &&\n        ex.args[1] == body.args[2].args[1] == body.args[2].args[2]\n    end\n\n    ex.head == :call &&\n    length(ex.args) == 2 &&\n    ishalfoffixpoint(ex.args[1]) &&\n    ishalfoffixpoint(ex.args[2])\nend\n\nfunction Base.show(io::IO, obj::Expr)\n    if obj.head == :call && obj.args[1] == Troll\n        print(\"TROLL OF THE \")\n        show(io, obj.args[2])\n    elseif isfixpointof(obj, Troll)\n        print(\"TROLL\")\n    else\n        print(io, obj)\n    end\nend",
      "execution_count": 2,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "yf = Expr(:->, :x, Expr(:call, :f, Expr(:call, :x, :x)))\ny = Expr(:->, :f, Expr(:call, yf, yf))\n\nz = Expr(:call, y, Troll)",
      "execution_count": 3,
      "outputs": [
        {
          "data": {
            "text/plain": "((f->((x->f(x(x))))((x->f(x(x))))))(Troll)"
          },
          "execution_count": 3,
          "metadata": {},
          "output_type": "execute_result"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "z = reduce(z)",
      "execution_count": 13,
      "outputs": [
        {
          "data": {
            "text/plain": ""
          },
          "execution_count": 13,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "name": "stdout",
          "output_type": "stream",
          "text": "TROLL OF THE TROLL OF THE TROLL OF THE TROLL OF THE TROLL OF THE TROLL OF THE TROLL OF THE TROLL OF THE TROLL OF THE TROLL"
        }
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "name": "julia-1.6",
      "display_name": "Julia 1.6.0",
      "language": "julia"
    },
    "language_info": {
      "file_extension": ".jl",
      "name": "julia",
      "mimetype": "application/julia",
      "version": "1.6.0"
    },
    "gist": {
      "id": "",
      "data": {
        "description": "Y-combinator.ipynb",
        "public": true
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}