Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
{
"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
}
@gauthamzz

This comment has been minimized.

Copy link

commented Feb 26, 2018

👍

@a-huy

This comment has been minimized.

Copy link

commented Feb 27, 2018

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.

@ProgVal

This comment has been minimized.

Copy link

commented Feb 28, 2018

Next step: tail-recursion optimization

@petiepooo

This comment has been minimized.

Copy link

commented Feb 28, 2018

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

@tchoutri

This comment has been minimized.

Copy link

commented Feb 28, 2018

Can't wait for proper recursion now!

@LukeB42

This comment has been minimized.

Copy link

commented Feb 28, 2018

👍

@Aristarhys

This comment has been minimized.

Copy link

commented Feb 28, 2018

🤘

@jasen-b

This comment has been minimized.

Copy link

commented Feb 28, 2018

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.

@skliarpawlo

This comment has been minimized.

Copy link

commented Mar 3, 2018

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.