{"author":"","author_email":"code.danielk@gmail.com","bugtrack_url":null,"classifiers":["Development Status :: 3 - Alpha","Intended Audience :: Developers","License :: OSI Approved :: MIT License","Natural Language :: English","Operating System :: OS Independent","Programming Language :: Python :: 3.5","Programming Language :: Python :: 3.6","Programming Language :: Python :: 3.7"],"description":"================================\ntrampoline - unlimited recursion\n================================\nSimple and tiny yield-based trampoline implementation for python.\n-----------------------------------------------------------------\n\nThis trampoline allows recursive functions to recurse virtually (or literally)\ninfinitely. Most existing recursive functions can be converted with simple\nmodifications.\n\nThe implementation is tiny: the gist of the module consists of a single\nfunction with around 30 lines of simple python code.\n\nConversion from simple recursion\n''''''''''''''''''''''''''''''''\n\nTrampolined functions are generators: Instead of recursing into other functions\ndirectly, they yield the generator of the call they want to recurse into. The\ngenerator of the first call is invoked using the ``trampoline()`` function.\n\nThis is easiest to understand with an example.\nConsider this simple recursive function:\n\n>>> def print_numbers(n):\n... \"Print numbers 0..n (recursive).\"\n... if n >= 0:\n... print_numbers(n - 1)\n... print(n)\n>>>\n>>> print_numbers(2000) # doctest: +IGNORE_EXCEPTION_DETAIL\nTraceback (most recent call last):\nRecursionError: maximum recursion depth exceeded in comparison\n\nThis exhausts the stack when calling it with too large ``n``.\nCompare this with our trampoline version:\n\n>>> from trampoline import trampoline\n>>>\n>>> def print_numbers(n):\n... \"Print numbers 0..n (trampolined).\"\n... if n >= 0:\n... yield print_numbers(n - 1)\n... print(n)\n>>>\n>>> trampoline(print_numbers(2000)) # doctest: +ELLIPSIS\n0\n1\n2\n...\n1999\n2000\n\nWe added a ``yield`` statement to the recursive call, and wrapped the function\ncall with ``trampoline()``.\n\n``trampoline`` takes the generator created by the ``print_numbers(2000)`` call and runs it.\nThe generator then yields another generator of ``print_numbers``, which then\ntakes over, effectively recursing into it.\n\nWhen a generator returns, the yielding generator takes over again.\n\nOf course, the trampolined function doesn't have to call itself. Any other\ntrampolined function generator will do.\n\nReturn values\n'''''''''''''\n\nConsider this recursive factorial:\n\n>>> def factorial(n):\n... \"Get factorial of n (recursive).\"\n... if n <= 1:\n... return 1\n... return factorial(n - 1) * n\n>>>\n>>> print(factorial(2000)) # doctest: +IGNORE_EXCEPTION_DETAIL\nTraceback (most recent call last):\nRecursionError: maximum recursion depth exceeded in comparison\n\nAgain, this exhausts the stack at our ``factorial(2000)`` call.\n\nWe now want to convert it for our trampoline. But how do we get the result of\nthe factorial call? This uses a rarely seen feature of yield: its return value\nas an expression. With this, ``trampoline`` can send the result of the callee\nback to the caller. Here is the trampolined solution:\n\n>>> def factorial(n):\n... \"Get factorial of n (trampolined).\"\n... if n <= 1:\n... return 1\n... return (yield factorial(n - 1)) * n\n>>>\n>>> print(trampoline(factorial(2000))) # doctest: +ELLIPSIS\n3316275092450633241175393380576324038281117208105780394571935437...\n\nThe function is suspended at the ``yield`` expression, ``trampoline`` continues\nexecution with the yielded generator, and afterwards provides us with the\nreturned value. In the end, ``trampoline`` returns the value that was returned\nby our first generator.\n\nPython requires that we add braces around a ``yield`` expression after a\n``return``, making it look a little more ugly. We can circumvent this by adding\na variable:\n\n>>> def factorial(n):\n... \"Get factorial of n (trampolined).\"\n... if n <= 1:\n... return 1\n... value = yield factorial(n - 1)\n... return value * n\n>>>\n>>> print(trampoline(factorial(10)))\n3628800\n\nIn this case, no extra braces are required.\n\nExceptions\n''''''''''\n\nExceptions are handled just as one might expect:\n\n>>> def factorial(n):\n... \"Get factorial of n (trampolined). Unless we don't like the number.\"\n... if n <= 1:\n... return 1\n... if n == 500:\n... raise Exception(\"I don't like this number\")\n... return (yield factorial(n - 1)) * n\n>>>\n>>> print(trampoline(factorial(1000)))\nTraceback (most recent call last):\n File \"/usr/lib/python3.7/doctest.py\", line 1329, in __run\n compileflags, 1), test.globs)\n File \"\", line 1, in \n print(trampoline(factorial(1000)))\n File \"trampoline.py\", line 39, in trampoline\n raise exception\n File \"trampoline.py\", line 21, in trampoline\n res = stack[-1].throw(ex)\n...\n File \"\", line 7, in factorial\n return (yield factorial(n - 1)) * n\n File \"trampoline.py\", line 21, in trampoline\n res = stack[-1].throw(ex)\n File \"\", line 7, in factorial\n return (yield factorial(n - 1)) * n\n File \"trampoline.py\", line 21, in trampoline\n res = stack[-1].throw(ex)\n File \"\", line 7, in factorial\n return (yield factorial(n - 1)) * n\n File \"trampoline.py\", line 25, in trampoline\n res = next(stack[-1])\n File \"\", line 6, in factorial\n raise Exception(\"I don't like this number\")\nException: I don't like this number\n\nAs seen in this example, event tracebacks are preserved, hiding no information\nin error cases. There is just one additional stack frame of the ``trampoline``\nfunction for each generator-yield.\n\nThis also means that yields work just fine inside ``with`` blocks.\n\nTail Calls\n''''''''''\n\nA trampolined function can raise ``TailCall`` (which is an exception) passing\nit the generator of the next function call:\n\n>>> from trampoline import TailCall\n>>>\n>>> def factorial(n, x=1):\n... \"Get factorial of n (trampolined).\"\n... if n <= 1:\n... return x\n... raise TailCall(factorial(n - 1, x * n))\n... yield # just to make this a generator\n>>>\n>>> # This could take some seconds (the numbers are extremely large)\n>>> print(trampoline(factorial(100000))) # doctest: +ELLIPSIS\n282422940796034787429342157802453551847749492609122485057891808654...\n\nThis implementation uses constant memory, and theoretically works with any\n``n`` (until the result gets too large).\n\nBeware that we still need to have a generator function, so there has to be a\n``yield`` in the function, reachable or not. The\n\n::\n\n raise TailCall(...)\n yield\n\nidiom is recommended if the function doesn't yield any other calls.\n\nSuggestions\n'''''''''''\n\nExpose a wrapper\n````````````````\n\nIf you want to hide the trampolined-ness of a function and simplify its usage,\nexpose a wrapper function that calls the trampolined function with\n``trampoline``:\n\n>>> def exposed_factorial(n):\n... \"Get factorial of n.\"\n... return trampoline(factorial(n))\n>>>\n>>> print(exposed_factorial(42))\n1405006117752879898543142606244511569936384000000000\n\nJust make sure to always use the trampolined version from other trampolined\nfunctions. Otherwise it will recurse as usual, taking no advantage of the\ntrampoline.\n\nUse it in classes\n`````````````````\n\n``trampoline`` works just fine with methods.\n\n>>> class Node(object):\n...\n... def __init__(self, name, children=()):\n... self.name = name\n... self.children = children\n...\n... def do_print(self, prefix=\"\"):\n... print(prefix + self.name)\n... for child in self.children:\n... yield child.do_print(prefix=\" \" + prefix)\n>>>\n>>> root = Node(\"root\", [Node(\"first\", [Node(\"one\")]), Node(\"second\", [Node(\"two\"), Node(\"last\")])])\n>>> trampoline(root.do_print())\nroot\n first\n one\n second\n two\n last\n\nSubclasses can extend or override these trampolined methods to provide their\nown implementation. Just make sure to always ``yield`` super calls when\nextending a trampolined method.\n\nCaveats\n'''''''\n\nLastly, there are some downsides to consider.\n\nYield\n`````\n\nAs we use ``yield`` for recursion, we cannot use it to yield actual values.\n\nSimple cases could be rewritten with a callback function or by appending or\nreturning a list.\n\nMemory consumption\n``````````````````\n\nRecursing hundreds of thousands of times allocates a lot of objects for local\nvariables and for the generators themselves, which all need to exist at the\nsame time. When overdoing it, this can easily lead to multiple gigabytes on the\nstack.\n\nOf course, if we mess up our exit condition and recurse infinitely, we will\nexhaust our memory.\n\nUse tail calls if they are an option. Otherwise an iterative approach may be\npreferable.\n\nPerformance\n```````````\n\nAs said above, when recursing extremely deeply, the stack may get rather large.\nThese objects not only have to be allocated, but need to be freed as well when\ndone, which slows down the return path.\n\nFunction call and exception handling overhead may come into play for functions\nthat don't recurse deeply or use a lot of tail calls. This should only matter\nfor functions that don't do a lot of work. A simple tail-calling count-down\nfrom one million takes about one second on a mediocre laptop.\n\nTracebacks\n``````````\n\nWhen an exception occurs at ridiculous recursion depth, displaying the\ntraceback may take a while, depending on the exception handler and formatter.\nReducing ``sys.tracebacklimit`` may help. Of course, the traceback will then be\ncut off. Python's default traceback limit applies here too, printing the last\n1000 frames.\n\nTail calls don't have this problem, as they don't appear in tracebacks.\n\n.. vim:set sw=4 et:\n\n\n","description_content_type":"","docs_url":null,"download_url":"","downloads":{"last_day":-1,"last_month":-1,"last_week":-1},"dynamic":null,"home_page":"https://gitlab.com/ferreum/trampoline","keywords":"trampoline recursion tail call","license":"MIT","license_expression":null,"license_files":null,"maintainer":"","maintainer_email":"","name":"trampoline","package_url":"https://pypi.org/project/trampoline/","platform":"","project_url":"https://pypi.org/project/trampoline/","project_urls":{"Homepage":"https://gitlab.com/ferreum/trampoline"},"provides_extra":null,"release_url":"https://pypi.org/project/trampoline/0.1.2/","requires_dist":null,"requires_python":"","summary":"Simple and tiny yield-based trampoline implementation.","version":"0.1.2","yanked":false,"yanked_reason":null}

Package search

trampoline

project_urls

Dependencies

All package metadata

Releases