{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## λ calculus\n", "\n", "This is code related to the book [\"Introduction to Theoretical Computer Science\"](http://introtcs.org) by Boaz Barak. [![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/boazbk/tcscode/blob/master/lambda_calculus.ipynb)\n", "\n", "The λ calculus is discussed in [Chapter 8: Equivalent Models of Computation](http://introtcs.org/public/lec_07_other_models.html)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This Python notebook provides a way to play with the lamdba calculus and evaluate lambda expressions of the form λvar1(exp1) λvar2(exp2) .... If you don't know Python you can safely ignore the Ptyhon code and skip below to where we actually talk about the λ calculus itself.\n", "\n", "To better fit with python there are two main differences:\n", "\n", "* Instead of writing λvar.exp we write λvar(exp)\n", "\n", "* Instead of simply concatenating two expressions exp1 exp2 we use the * operator and write exp1 * exp2. We can also use exp1, exp2 if they are inside a function call or a variable binding parenthesis.\n", "\n", "* To reduce an expression exp, use exp.reduce()\n", "\n", "* Since Python does not allow us to override the default 0 and 1 we use _0 for λx(y(y)) and _1 for λx(y(x)). " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Python code (can skip at first read)\n", "\n", "If you don't know Python feel free to skip ahead to the part where we play with the $\\lambda$ calculus itself.\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# We define an abstract base class Lambdaexp for lambda expressions\n", "# It has the following subclasses:\n", "# Applicableexp: an expression of the form λx.exp\n", "# Combinedexp: an expression of the form (exp,exp')\n", "# Boundvar: an expression corresponding to a bounded variable\n", "# Unboundvar: an expression corresponding to a free variable\n", "#\n", "# The main operations in a Lambdaexp are:\n", "# 1. Replace: given exp,x and exp', obtain the expression exp[x-->exp']\n", "# 2. Reduce: continuously evaluate expressions to obtain a simpler form\n", "# 3. Apply: given exp,exp', if exp is applicable then apply it to exp', otherwise combine the two \n", "# (we also use the * operator for it)\n", "\n", "\n", "\n", "import operator ,functools\n", "\n", "class Lambdaexp:\n", " \"\"\"Lambda expressions base class\"\"\"\n", " \n", " counter = 0\n", " call_by_name = True # if False then do normal form evaluation.\n", " \n", " def __init__(self):\n", " self.mykey = {}\n", " \n", " def apply(self,other): \n", " \"\"\"Apply expression on an argument\"\"\"\n", " return self*other\n", " \n", " def _reduce(self,maxlevel=100): \n", " \"\"\"Reduce expression\"\"\"\n", " return self\n", " \n", " def replace(self,old,new): \n", " \"\"\"Replace all occurences of old with new\"\"\"\n", " raise NotImplementedError\n", "\n", " \n", " def bounded(self): \n", " \"\"\"Set of bounded variables inside expression\"\"\"\n", " return set()\n", "\n", " def asstring(self, m,pretty=False):\n", " \"\"\"Represent self as a string mapping bounded variables to particular numbers.\"\"\"\n", " raise NotImplementedError\n", "\n", " #------------------------------------------------------------------------------#\n", " # Ignore this code in first read: Python specific details\n", "\n", " lambdanames = {}\n", " reducedstrings = {}\n", " \n", " def reduce(self,maxlevel=100):\n", " if not maxlevel: return self\n", " #m = {b:b for b in self.bounded() }\n", " #t = Lambdaexp.reducedstrings.get((self.asstring(m),maxlevel),None)\n", " #if t: return t\n", " return self._reduce(maxlevel)\n", " #k = t.asstring(m)\n", " #for i in range(maxlevel+1): \n", " # Lambdaexp.reducedstrings[(k,i)] = t\n", " #return t\n", " \n", " \n", " \n", " def __mul__(self,other):\n", " \"\"\"Use * for combining.\"\"\"\n", " return Combinedexp(self,other) if other else self\n", " \n", " def __call__(self,*args): \n", " \"\"\"Use function call for application\"\"\"\n", " return functools.reduce(operator.mul,args,self)\n", " \n", " def _key(self,maxlevel=100): \n", " #if maxlevel not in self.mykey: \n", " return self.reduce(maxlevel).__repr__()\n", " # for i in range(maxlevel+1): self.mykey[i] = s \n", " # return self.mykey[maxlevel]\n", "\n", " def __eq__(self,other): return self._key()==other._key() if isinstance(other,Lambdaexp) else False\n", " def __hash__(self): return hash(self._key())\n", " \n", " \n", " \n", " def __repr__(self,pretty=False):\n", " B = sorted(self.bounded())\n", " m ={}\n", " for v in B: m[v] = len(m)\n", " return self.asstring(m,pretty)\n", " \n", " \n", " def _repr_pretty_(self, p, cycle):\n", " if cycle: p.text( self._repr())\n", " p.text( self.reduce().__repr__(True)) \n", " \n", " def addconst(self,srep):\n", " \"\"\"Return either exp.string or replaced with a keyword if it's in table.\"\"\"\n", " if self in Lambdaexp.lambdanames: return blue(Lambdaexp.lambdanames[self])\n", " return srep\n", "\n", " #------------------------------------------------------------------------------#\n", "\n", "\n", " \n", " \n", " " ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "#-------------------------------------------------#\n", "# Utility functions: print color\n", "def bold(s,justify=0):\n", " return \"\\x1b[1m\"+s.ljust(justify)+\"\\x1b[21m\"\n", "\n", "def underline(s,justify=0):\n", " return \"\\x1b[4m\"+s.ljust(justify)+\"\\x1b[24m\"\n", "\n", "def red(s,justify=0):\n", " return \"\\x1b[31m\"+s.ljust(justify)+\"\\x1b[0m\"\n", "\n", "\n", "def green(s,justify=0):\n", " return \"\\x1b[32m\"+s.ljust(justify)+\"\\x1b[0m\"\n", "\n", "\n", "def blue(s,justify=0):\n", " return \"\\x1b[34m\"+s.ljust(justify)+\"\\x1b[0m\"\n", "#--------------------------------------------------#" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ " \n", " \n", " \n", "\n", " \n", "class Applicableexp(Lambdaexp):\n", " \"\"\"Lambda expression that can be applied\"\"\"\n", " \n", " def __init__(self,exp,name):\n", " Lambdaexp.counter += 1\n", " self.arg = Lambdaexp.counter\n", " self.inner = exp.replace(name,Boundvar(self.arg))\n", " super().__init__() \n", " \n", " def apply(self,other): \n", " return self.inner.replace(self.arg,other)\n", " \n", " def replace(self,old,new): \n", " if self.arg==old: \n", " if not isintance(new,Boundvar): \n", " raise TypeError(f\"Can't replace {old} in {self} since {new} is not instance of Boundvar\")\n", " self.arg = new.myid\n", " return Applicableexp(self.inner.replace(old,new),self.arg)\n", " \n", " def bounded(self): return self.inner.bounded()|{self.arg}\n", " \n", " def _reduce(self,maxlevel=100):\n", " if Lambdaexp.call_by_name: return self \n", " # in call by name there are no reductions inside abstractions\n", " inner = self.inner.reduce(maxlevel-1)\n", " return Applicableexp(inner,self.arg)\n", " \n", " def asstring(self, m,pretty=False):\n", " if not pretty: return \"λ\"+Boundvar(self.arg).asstring(m,False)+\".(\"+self.inner.asstring(m)+\")\"\n", " return self.addconst(green(\"λ\")+Boundvar(self.arg).asstring(m,True)+\".(\"+self.inner.asstring(m,True)+\")\")\n", " \n", " \n", " \n", " " ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "class Boundvar(Lambdaexp):\n", " \"\"\"Bounded variable\"\"\"\n", " def __init__(self,arg): \n", " self.myid = arg\n", " super().__init__()\n", " \n", " def replace(self,argnum,exp): return exp if argnum==self.myid else self\n", " \n", " def bounded(self): return { self.myid }\n", "\n", " def asstring(self, m,pretty=False):\n", " arg = m.get(self.myid,self.myid) \n", " return chr(ord('α')+arg)\n", " \n", "\n", "class Unboundvar(Lambdaexp):\n", " \"\"\"Unbounded (free) variable.\"\"\"\n", " def __init__(self,name): \n", " self.name = name\n", " super().__init__()\n", " \n", " def replace(self,name,arg): return arg if name==self.name else self\n", " \n", " def asstring(self, m,pretty=False):\n", " return self.addconst(self.name) if pretty else self.name\n", "\n", " \n", " \n", "class Combinedexp(Lambdaexp):\n", " \"\"\"Combined expression of two expressions.\"\"\"\n", " def __init__(self,exp1,exp2):\n", " self.exp1 = exp1\n", " self.exp2 = exp2\n", " super().__init__()\n", " \n", " def replace(self,arg,exp): \n", " return Combinedexp(self.exp1.replace(arg,exp),self.exp2.replace(arg,exp))\n", " \n", " def bounded(self): return self.exp1.bounded()|self.exp2.bounded()\n", " \n", " \n", " def _reduce(self,maxlevel=100):\n", " if not maxlevel: return self\n", " e1 = self.exp1.reduce(maxlevel-1)\n", " if isinstance(e1,Applicableexp): \n", " return e1.apply(self.exp2).reduce(maxlevel-1)\n", " return Combinedexp(e1,self.exp2)\n", " \n", " def asstring(self, m,pretty=False):\n", " s = f\"({self.exp1.asstring(m,False)} {self.exp2.asstring(m,False)})\"\n", " if not pretty: return s\n", " return f\"({self.exp1.asstring(m,True)} {self.exp2.asstring(m,True)})\"\n" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "class λ:\n", " \"\"\"Binds a variable name in a lambda expression\"\"\"\n", "\n", " def __init__(self,*varlist): \n", " \"\"\"\n", " Get list of unbounded variables (for example a,b,c) and returns an operator that binds an expresion exp to\n", " λa(λb(λc(exp))) and so on.\"\"\"\n", " if not varlist: raise ValueError(\"Need to bind at least one variable\")\n", " self.varlist = varlist[::-1]\n", " \n", " \n", " def bindexp(self,exp):\n", " res = exp\n", " for v in self.varlist: \n", " res = Applicableexp(res,v.name)\n", " return res\n", " \n", " #------------------------------------------------------------------------------#\n", " # Ignore this code in first read: Python specific details\n", "\n", " \n", " def __call__(self,*args):\n", " exp = functools.reduce(operator.mul,args[1:],args[0])\n", " return self.bindexp(exp)\n", " #------------------------------------------------------------------------------#" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Initalization \n", "\n", "The above is all the code for implementing the λ calculus. We now add some convenient global variables: \n", "λa .... λz and a ... z for variables, and 0 and 1." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "Lambdaexp.lambdanames = {}\n", "import string\n", "\n", "def initids(g):\n", " \"\"\"Set up parameters a...z and correpsonding Binder objects λa..λz\"\"\"\n", " lcase = list(string.ascii_lowercase)\n", " ids = lcase + [n+\"_\" for n in lcase]\n", " for name in ids:\n", " var = Unboundvar(name)\n", " g[name] = var\n", " g[\"λ\"+name] = λ(var)\n", " Lambdaexp.lambdanames[var] = name" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "initids(globals())" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[32mλ\u001b[0mα.(α)" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# testing...\n", "λy(y)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[32mλ\u001b[0mα.(\u001b[32mλ\u001b[0mβ.(α))" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "λ(a,b)(a)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "def setconstants(g,consts):\n", " \"\"\"Set up constants for easier typing and printing.\"\"\"\n", " \n", " for name in consts:\n", " Lambdaexp.lambdanames[consts[name]] = name\n", " if name[0].isalpha(): \n", " g[name]=consts[name]\n", " \n", " else: # Numeric constants such as 0 and 1 are replaced by _0 and _1\n", " g[\"_\"+name] = consts[name]\n", " \n", "setconstants(globals(),{\"1\" : λ(x,y)(x) , \"0\" : λ(x,y)(y) })\n", "\n", "def register(g,*args):\n", " for name in args:\n", " Lambdaexp.lambdanames[g[name]] = name" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34m1\u001b[0m" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# testing\n", "λa(λz(a))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## λ calculus playground\n", "\n", "We can now start playing with the λ calculus\n", "\n", "If you want to use the λ character you can copy paste it from here: λ" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's start with the function λx,y.y, also known as 0 " ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34m0\u001b[0m" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "λa(λb(b))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Our string representation recognizes that this is the 0 function and so \"pretty prints\" it. To see the underlying λ expression you can use __repr__()" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'λα.(λβ.(β))'" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "λa(λb(b)).__repr__()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's check that _0 and _1 behave as expected" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34ma\u001b[0m" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "_1(a,b)" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34mb\u001b[0m" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "_0(a,b)" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34m1\u001b[0m" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "_1" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[32mλ\u001b[0mα.(\u001b[34m0\u001b[0m)" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "_1(_0)" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'λα.(λβ.(α))'" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "_1.__repr__()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here is an exercise:\n", "\n", "__Question:__ Suppose that $F = \\lambda f. (\\lambda x. (f x)f)$, $1 = \\lambda x.(\\lambda y.x)$ and $0=\\lambda x.(\\lambda y.y)$.\n", "What is $F \\; 1\\; 0$?\n", "\n", "__a.__ $1$\n", "\n", "__b.__ $0$\n", "\n", "__c.__ $\\lambda x.1$\n", "\n", "__d.__ $\\lambda x.0$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's evaluate the answer" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "collapsed": true }, "outputs": [ { "data": { "text/plain": [ "\u001b[32mλ\u001b[0mα.(\u001b[32mλ\u001b[0mβ.(((α β) α)))" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "F=λf(λx((f*x)*f))\n", "F" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[32mλ\u001b[0mα.(((\u001b[34m1\u001b[0m α) \u001b[34m1\u001b[0m))" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "F(_1)" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34m0\u001b[0m" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "F(_1,_0)" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [], "source": [ "ID = λa(a)\n", "register(globals(),\"ID\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Some useful functions\n", "\n", "Let us now add some of the basic functions in the λ calculus" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "collapsed": true }, "outputs": [], "source": [ "NIL= λf(_1)\n", "PAIR =λx(λy(λf(f*x*y)))\n", "ISEMPTY= λp(p *(λx(λy(_0))))\n", "HEAD = λp(p(_1))\n", "TAIL =λp(p * _0)\n", "IF = λ(a,b,c)(a * b * c)\n", "\n", "register(globals(),\"NIL\", \"PAIR\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And test them out" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34m1\u001b[0m" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ISEMPTY(NIL)" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34mb\u001b[0m" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "IF(_0,a,b)" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34ma\u001b[0m" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "IF(_1,a,b)" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [], "source": [ "P=PAIR(_0,_1)" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34m0\u001b[0m" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "HEAD(P)" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34m1\u001b[0m" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "TAIL(P)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can make lists of bits as follows:" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [], "source": [ "def makelist(*L):\n", " \"\"\"Construct a λ list of _0's and _1's.\"\"\"\n", " if not L: return NIL\n", " h = _1 if L[0] else _0\n", " return PAIR(h,makelist(*L[1:]))" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[32mλ\u001b[0mα.(((α \u001b[34m1\u001b[0m) ((\u001b[34mPAIR\u001b[0m \u001b[34m0\u001b[0m) ((\u001b[34mPAIR\u001b[0m \u001b[34m1\u001b[0m) \u001b[34mNIL\u001b[0m))))" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "L=makelist(1,0,1)\n", "L" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34m1\u001b[0m" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "HEAD(L)" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[32mλ\u001b[0mα.(((α \u001b[34m0\u001b[0m) ((\u001b[34mPAIR\u001b[0m \u001b[34m1\u001b[0m) \u001b[34mNIL\u001b[0m)))" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "TAIL(L)" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34m0\u001b[0m" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "HEAD(TAIL(L))" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34m1\u001b[0m" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "HEAD(TAIL(TAIL(L)))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Recursion\n", "\n", "We now show how we can implement recursion in the λ calculus. We start by doing this in Python.\n", "Let's try to define XOR in a recursive way and then avoid recursion" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# XOR of 2 bits\n", "def xor2(a,b): return 1-b if a else b\n", "\n", "# XOR of a list - recursive definition\n", "def xor(L): return xor2(L[0],xor(L[1:])) if L else 0\n", "\n", "xor([1,0,0,1,1])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now let's try to make a _non recursive_ definition, by replacing the recursive call with a call to me which is a function that is given as an extra argument:" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [], "source": [ "def myxor(me,L): return 0 if not L else xor2(L[0],me(L[1:]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The first idea is to try to implement xor(L) as myxor(myxor,L) but this will not work:" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "myxor() missing 1 required positional argument: 'L'\n" ] } ], "source": [ "def xor(L): return myxor(myxor,L)\n", "\n", "try: \n", " xor([0,1,1])\n", "except Exception as e:\n", " print(e)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The issue is that myxor takes _two_ arguments, while in me we only supply one.\n", "Thus, we will modify myxor to tempxor where we replace the call me(x) with me(me,x):" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [], "source": [ "def tempxor(me,L): return myxor(lambda x: me(me,x),L)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's check this out:" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def xor(L): return tempxor(tempxor,L)\n", "\n", "xor([1,0,1,1])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This works!\n", "\n", "Let's now generatlize this to any function. The RECURSE operator will take a function f that takes two arguments me and x and return a function g where the calls to me are replaced with calls to g" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def RECURSE(f):\n", " def ftemp(me,x): return f(lambda x: me(me,x),x)\n", " return lambda x: ftemp(ftemp,x)\n", "\n", "xor = RECURSE(myxor)\n", "\n", "xor([1,1,0])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### The λ version\n", "\n", "We now repeat the same arguments with the λ calculus:" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [], "source": [ "# XOR of two bits\n", "XOR2 = λ(a,b)(IF(a,IF(b,_0,_1),b))\n", "\n", "# Recursive XOR with recursive calls replaced by m parameter\n", "myXOR = λ(m,l)(IF(ISEMPTY(l),_0,XOR2(HEAD(l),m(TAIL(l)))))\n", "\n", "# Recurse operator (aka Y combinator)\n", "RECURSE = λf((λm(f(m*m)))(λm(f(m*m))))\n", "\n", "# XOR function\n", "XOR = RECURSE(myXOR)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's test this out:" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34m1\u001b[0m" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "XOR(PAIR(_1,NIL)) # List [1]" ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34m0\u001b[0m" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "XOR(PAIR(_1,PAIR(_0,PAIR(_1,NIL)))) # List [1,0,1]" ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34m0\u001b[0m" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "XOR(makelist(1,0,1))" ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\u001b[34m1\u001b[0m" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "XOR(makelist(1,0,0,1,1))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "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.7" } }, "nbformat": 4, "nbformat_minor": 2 }