Last active
March 30, 2024 08:03
-
-
Save razimantv/1b33d4a090a5bc9ed94928012b37c3f0 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "cells": [ | |
| { | |
| "cell_type": "code", | |
| "execution_count": 12, | |
| "metadata": {}, | |
| "outputs": [ | |
| { | |
| "name": "stdout", | |
| "output_type": "stream", | |
| "text": [ | |
| "Primary call on (5,)\n", | |
| "Push (5,) to stack\n", | |
| "Pop (5,) from stack\n", | |
| "Attempt to call fib(5,)\n", | |
| "Attempted secondary call on (3,)\n", | |
| "Attempt to call fib(5,) failed\n", | |
| "Push (5,) to stack\n", | |
| "Push (3,) to stack\n", | |
| "Pop (3,) from stack\n", | |
| "Attempt to call fib(3,)\n", | |
| "Attempted secondary call on (1,)\n", | |
| "Attempt to call fib(3,) failed\n", | |
| "Push (3,) to stack\n", | |
| "Push (1,) to stack\n", | |
| "Pop (1,) from stack\n", | |
| "Attempt to call fib(1,)\n", | |
| "Attempt to call fib(1,) successful\n", | |
| "Pop (3,) from stack\n", | |
| "Attempt to call fib(3,)\n", | |
| "Attempted secondary call on (2,)\n", | |
| "Attempt to call fib(3,) failed\n", | |
| "Push (3,) to stack\n", | |
| "Push (2,) to stack\n", | |
| "Pop (2,) from stack\n", | |
| "Attempt to call fib(2,)\n", | |
| "Attempted secondary call on (0,)\n", | |
| "Attempt to call fib(2,) failed\n", | |
| "Push (2,) to stack\n", | |
| "Push (0,) to stack\n", | |
| "Pop (0,) from stack\n", | |
| "Attempt to call fib(0,)\n", | |
| "Attempt to call fib(0,) successful\n", | |
| "Pop (2,) from stack\n", | |
| "Attempt to call fib(2,)\n", | |
| "Attempt to call fib(2,) successful\n", | |
| "Pop (3,) from stack\n", | |
| "Attempt to call fib(3,)\n", | |
| "Attempt to call fib(3,) successful\n", | |
| "Pop (5,) from stack\n", | |
| "Attempt to call fib(5,)\n", | |
| "Attempted secondary call on (4,)\n", | |
| "Attempt to call fib(5,) failed\n", | |
| "Push (5,) to stack\n", | |
| "Push (4,) to stack\n", | |
| "Pop (4,) from stack\n", | |
| "Attempt to call fib(4,)\n", | |
| "Attempt to call fib(4,) successful\n", | |
| "Pop (5,) from stack\n", | |
| "Attempt to call fib(5,)\n", | |
| "Attempt to call fib(5,) successful\n" | |
| ] | |
| }, | |
| { | |
| "data": { | |
| "text/plain": [ | |
| "8" | |
| ] | |
| }, | |
| "execution_count": 12, | |
| "metadata": {}, | |
| "output_type": "execute_result" | |
| } | |
| ], | |
| "source": [ | |
| "class stackify(object):\n", | |
| " \n", | |
| " def __init__ (self, f):\n", | |
| " self.__f = f\n", | |
| " self.__cache = {}\n", | |
| " self.__primary = True\n", | |
| " \n", | |
| " def __call__(self, *args):\n", | |
| " key=str(args)\n", | |
| " if key in self.__cache:\n", | |
| " return self.__cache[key]\n", | |
| " \n", | |
| " if self.__primary:\n", | |
| " # Direct call. Initialise stack\n", | |
| " print('Primary call on ' + str(args))\n", | |
| " self.__primary = False\n", | |
| " self.__stack = [args]\n", | |
| " print('Push ' + str(args) + ' to stack')\n", | |
| " while len(self.__stack) > 0:\n", | |
| " arg = self.__stack.pop()\n", | |
| " print('Pop ' + str(arg) + ' from stack')\n", | |
| " try:\n", | |
| " print('Attempt to call fib' + str(arg))\n", | |
| " value = self.__f(*arg)\n", | |
| " print('Attempt to call fib' + 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", | |
| " print('Attempt to call fib' + str(arg) + ' failed')\n", | |
| " self.__stack.append(arg)\n", | |
| " self.__stack.append(self.__nextarg)\n", | |
| " print('Push ' + str(arg) + ' to stack')\n", | |
| " print('Push ' + str(self.__nextarg) + ' to stack')\n", | |
| " self.__primary = True\n", | |
| " return value\n", | |
| " else:\n", | |
| " # Tried to recurse to non-cached value\n", | |
| " # Save the argument and crash\n", | |
| " print('Attempted secondary call on ' + str(args))\n", | |
| " self.__nextarg = args\n", | |
| " raise Exception()\n", | |
| "\n", | |
| "@stackify\n", | |
| "def fib(N):\n", | |
| " if N<2: return 1\n", | |
| " return fib(N-2) + fib(N-1)\n", | |
| "\n", | |
| "fib(5)" | |
| ] | |
| }, | |
| { | |
| "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.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
👍