stackify.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Stackify!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Deep recursion will give you stack errors.\n",
    "\n",
    "Why change the stack limit when you can decorate the function by abusing exceptions and turn the function iterative instead?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class stackify(object):\n",
    "    \"\"\"Wrapper for stack-based recursion with memoisation\n",
    "    \n",
    "    When the function is called and argument is not in cache, push it to stack\n",
    "    Attempt to call the function on the arguments in the stack such that an\n",
    "    exception is raised if the function tries to recurse. In that case, add the\n",
    "    function argument to the stack and continue\n",
    "    \n",
    "    The order of successful arguments also provides a topological sort\n",
    "\n",
    "    Warning:\n",
    "        1. Works only for \"pure\" side-effect-free functions without cycles\n",
    "        2. Immoral use of exceptions\n",
    "    \n",
    "    Attributes:\n",
    "        __cache: Dictionary to memoise based on string representation of args\n",
    "        __primary: Flag to denote whether we are in a primary function call\n",
    "        toposort: Topological sort of the states of the function\n",
    "        log: Flag whether logging is required. Default: False\n",
    "        sort: Flag whether topological sort is required. Default: False\n",
    "    \"\"\"\n",
    "    def __init__ (self, f):\n",
    "        self.__f = f\n",
    "        self.__cache = {}\n",
    "        self.__primary = True\n",
    "        self.toposort = []\n",
    "        self.log = False\n",
    "        self.sort = False\n",
    "    \n",
    "    def __call__(self, *args):\n",
    "        # Before calling the function, check if the argument is present in cache\n",
    "        key=str(args)\n",
    "        if key in self.__cache:\n",
    "            return self.__cache[key]\n",
    "        \n",
    "        if self.__primary:\n",
    "            # We are in a direct call. Initialise the stack\n",
    "            if self.log: print('Primary call on ' + str(args))\n",
    "            self.__primary = False\n",
    "            self.__stack = [args]\n",
    "            if self.log: print('Push ' + str(args) + ' to stack')\n",
    "            while len(self.__stack) > 0:\n",
    "                # Pop an element from the stack and attempt to call the function\n",
    "                arg = self.__stack.pop()\n",
    "                if self.log: print('Pop ' + str(arg) + ' from stack')\n",
    "                try:\n",
    "                    if self.log: print('Attempt to call ' + str(arg))\n",
    "                    value = self.__f(*arg)\n",
    "                    \n",
    "                    # If an exception has not been raised, we have successful evaluation\n",
    "                    # We are guaranteed that any state the f(arg) needs is already\n",
    "                    # present in toposort[], so add arg to the toposort\n",
    "                    if self.sort: self.toposort.append(arg)\n",
    "                    if self.log: print('Attempt to call ' + str(arg) + ' successful')\n",
    "                    self.__cache[str(arg)] = value\n",
    "                except:\n",
    "                    # Tried to recurse to non-cached value\n",
    "                    # Push it to stack after previous argument\n",
    "                    if self.log: print('Attempt to call ' + str(arg) + ' failed')\n",
    "                    self.__stack.append(arg)\n",
    "                    self.__stack.append(self.__nextarg)\n",
    "                    if self.log: print('Push ' + str(arg) + ' to stack')\n",
    "                    if self.log: print('Push ' + str(self.__nextarg) + ' to stack')\n",
    "            self.__primary = True\n",
    "            \n",
    "            # We are guaranteed that the original argument was evaluated last\n",
    "            # So we can just return the value\n",
    "            return value\n",
    "        else:\n",
    "            # Tried to recurse to non-cached value\n",
    "            # Save the argument and crash\n",
    "            if self.log: print('Attempted secondary call on ' + str(args))\n",
    "            self.__nextarg = args\n",
    "            raise Exception()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "534400663"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@stackify\n",
    "def fib(N):\n",
    "    if N<2: return 1\n",
    "    return (fib(N-2) + fib(N-1))%1000000007\n",
    "\n",
    "# This would crash if we were doing memoised recursion without stackify\n",
    "fib(1000000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Primary call on (1, 4)\n",
      "Push (1, 4) to stack\n",
      "Pop (1, 4) from stack\n",
      "Attempt to call (1, 4)\n",
      "Attempted secondary call on (1, 3)\n",
      "Attempt to call (1, 4) failed\n",
      "Push (1, 4) to stack\n",
      "Push (1, 3) to stack\n",
      "Pop (1, 3) from stack\n",
      "Attempt to call (1, 3)\n",
      "Attempted secondary call on (1, 2)\n",
      "Attempt to call (1, 3) failed\n",
      "Push (1, 3) to stack\n",
      "Push (1, 2) to stack\n",
      "Pop (1, 2) from stack\n",
      "Attempt to call (1, 2)\n",
      "Attempted secondary call on (1, 1)\n",
      "Attempt to call (1, 2) failed\n",
      "Push (1, 2) to stack\n",
      "Push (1, 1) to stack\n",
      "Pop (1, 1) from stack\n",
      "Attempt to call (1, 1)\n",
      "Attempted secondary call on (1, 0)\n",
      "Attempt to call (1, 1) failed\n",
      "Push (1, 1) to stack\n",
      "Push (1, 0) to stack\n",
      "Pop (1, 0) from stack\n",
      "Attempt to call (1, 0)\n",
      "Attempted secondary call on (0, 1)\n",
      "Attempt to call (1, 0) failed\n",
      "Push (1, 0) to stack\n",
      "Push (0, 1) to stack\n",
      "Pop (0, 1) from stack\n",
      "Attempt to call (0, 1)\n",
      "Attempt to call (0, 1) successful\n",
      "Pop (1, 0) from stack\n",
      "Attempt to call (1, 0)\n",
      "Attempt to call (1, 0) successful\n",
      "Pop (1, 1) from stack\n",
      "Attempt to call (1, 1)\n",
      "Attempted secondary call on (0, 2)\n",
      "Attempt to call (1, 1) failed\n",
      "Push (1, 1) to stack\n",
      "Push (0, 2) to stack\n",
      "Pop (0, 2) from stack\n",
      "Attempt to call (0, 2)\n",
      "Attempt to call (0, 2) successful\n",
      "Pop (1, 1) from stack\n",
      "Attempt to call (1, 1)\n",
      "Attempt to call (1, 1) successful\n",
      "Pop (1, 2) from stack\n",
      "Attempt to call (1, 2)\n",
      "Attempted secondary call on (0, 3)\n",
      "Attempt to call (1, 2) failed\n",
      "Push (1, 2) to stack\n",
      "Push (0, 3) to stack\n",
      "Pop (0, 3) from stack\n",
      "Attempt to call (0, 3)\n",
      "Attempt to call (0, 3) successful\n",
      "Pop (1, 2) from stack\n",
      "Attempt to call (1, 2)\n",
      "Attempt to call (1, 2) successful\n",
      "Pop (1, 3) from stack\n",
      "Attempt to call (1, 3)\n",
      "Attempted secondary call on (0, 4)\n",
      "Attempt to call (1, 3) failed\n",
      "Push (1, 3) to stack\n",
      "Push (0, 4) to stack\n",
      "Pop (0, 4) from stack\n",
      "Attempt to call (0, 4)\n",
      "Attempt to call (0, 4) successful\n",
      "Pop (1, 3) from stack\n",
      "Attempt to call (1, 3)\n",
      "Attempt to call (1, 3) successful\n",
      "Pop (1, 4) from stack\n",
      "Attempt to call (1, 4)\n",
      "Attempted secondary call on (0, 5)\n",
      "Attempt to call (1, 4) failed\n",
      "Push (1, 4) to stack\n",
      "Push (0, 5) to stack\n",
      "Pop (0, 5) from stack\n",
      "Attempt to call (0, 5)\n",
      "Attempt to call (0, 5) successful\n",
      "Pop (1, 4) from stack\n",
      "Attempt to call (1, 4)\n",
      "Attempt to call (1, 4) successful\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[(0, 1),\n",
       " (1, 0),\n",
       " (0, 2),\n",
       " (1, 1),\n",
       " (0, 3),\n",
       " (1, 2),\n",
       " (0, 4),\n",
       " (1, 3),\n",
       " (0, 5),\n",
       " (1, 4)]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@stackify\n",
    "def ackermann(M,N):\n",
    "    if M == 0: return N+1\n",
    "    if N == 0: return ackermann(M-1,1)\n",
    "    return ackermann(M-1, ackermann(M,N-1))\n",
    "\n",
    "# Show call sequence and topological sort of states for Ackermann function\n",
    "ackermann.log = True\n",
    "ackermann.sort = True\n",
    "ackermann(1,4)\n",
    "ackermann.toposort"
   ]
  },
  {
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}

👍

You might want to define a custom Exception class for this - it looks like the current implementation will confuse KeyboardInterrupt and unrelated functional exceptions as an attempt to recurse.

Next step: tail-recursion optimization

Cool hack, but a-huy is right: a naked except clause? Tsk tsk..

Can't wait for proper recursion now!

👍

🤘

a custom exception is not needed, the exception problem can be fixed by reducing the scope of the try block and using some messy branching or a tidy little goto.

I think you can pass __next_arg via exception params instead of stackify object state.