[Edu-sig] Re: Py310: recursion with match-case
https://docs.python.org/3/whatsnew/3.10.html#pep-634-structural-pattern-matching "PEP 636 -- Structural Pattern Matching: Tutorial" https://www.python.org/dev/peps/pep-0636/ "Computational Fairy Tales: Computer science concepts as told through fairy tales." http://computationaltales.blogspot.com/ There's a book: https://www.goodreads.com/en/book/show/15891129-computational-fairy-tales On Sat, Nov 20, 2021, 13:17 kirby urner wrote: > > I've since done it in hoon, taught as "martian computing" at University of > Illinois. > > https://github.com/davis68/martian-computing > > Hoon version: > https://flic.kr/p/2mKTPas > > (base) Kirbys-MacBook-Pro:base mac$ cd gen > (base) Kirbys-MacBook-Pro:gen mac$ cat crystalball.hoon > !: > :: Crystal Ball Numbers > :: https://oeis.org/A005902 > :: > |= n=@ud > ^- @ud > ?: =(n 0) > 1 > (add (add (mul 10 (mul n n)) 2) $(n (dec n))) > (base) Kirbys-MacBook-Pro:gen mac$ > > In my world, it's the crystal ball sequence that's front and center, > orthogonal to the computer language. Maybe that's because OEIS > https://oeis.org/A005901 and https://oeis.org/A005902 both link back to > my website and I tend to use my own websites to teach my stuff (imagine > that). > > I don't think my Hoon version is tail recursive, but it could be, by a > more experienced hand. I just heard of Hoon a couple days ago. Hoon is a > functional system language that compiles to a LISP (nock) and does know the > difference between tail call vs stack deepening. Python doesn't. > > Python points out you often don't need recursion at all (including in this > case) and that recursion isn't maybe as super cool as it thinks it is. > I've got the non-recursive versions on REPL. > > Anyway, the computer science angle is important, not just the Blender / > CAD / CAM. > > Kirby > > > On Tue, Nov 16, 2021 at 5:58 PM kirby urner wrote: > >> >> So are we encouraged to use match-case in recursion instead of if-else? >> >> It's more readable this way maybe: >> >> cubocta310.py: >> >> def cubocta(n): >> """ >> https://oeis.org/A005902 >> """ >> match n: >> case 0: return 1 >> case _: return (10*n*n + 2) + cubocta(n - 1) >> >> print([cubocta(i) for i in range(10)]) >> >> (py310) Kirbys-MacBook-Pro:School_of_Tomorrow mac$ python cubocta310.py >> [1, 13, 55, 147, 309, 561, 923, 1415, 2057, 2869] >> >> https://flic.kr/p/2mKh2nd >> (image version) >> >> Kirby >> >> ___ > Edu-sig mailing list -- edu-sig@python.org > To unsubscribe send an email to edu-sig-le...@python.org > https://mail.python.org/mailman3/lists/edu-sig.python.org/ > Member address: wes.tur...@gmail.com > ___ Edu-sig mailing list -- edu-sig@python.org To unsubscribe send an email to edu-sig-le...@python.org https://mail.python.org/mailman3/lists/edu-sig.python.org/ Member address: arch...@mail-archive.com
[Edu-sig] Re: Py310: recursion with match-case
I've since done it in hoon, taught as "martian computing" at University of Illinois. https://github.com/davis68/martian-computing Hoon version: https://flic.kr/p/2mKTPas (base) Kirbys-MacBook-Pro:base mac$ cd gen (base) Kirbys-MacBook-Pro:gen mac$ cat crystalball.hoon !: :: Crystal Ball Numbers :: https://oeis.org/A005902 :: |= n=@ud ^- @ud ?: =(n 0) 1 (add (add (mul 10 (mul n n)) 2) $(n (dec n))) (base) Kirbys-MacBook-Pro:gen mac$ In my world, it's the crystal ball sequence that's front and center, orthogonal to the computer language. Maybe that's because OEIS https://oeis.org/A005901 and https://oeis.org/A005902 both link back to my website and I tend to use my own websites to teach my stuff (imagine that). I don't think my Hoon version is tail recursive, but it could be, by a more experienced hand. I just heard of Hoon a couple days ago. Hoon is a functional system language that compiles to a LISP (nock) and does know the difference between tail call vs stack deepening. Python doesn't. Python points out you often don't need recursion at all (including in this case) and that recursion isn't maybe as super cool as it thinks it is. I've got the non-recursive versions on REPL. Anyway, the computer science angle is important, not just the Blender / CAD / CAM. Kirby On Tue, Nov 16, 2021 at 5:58 PM kirby urner wrote: > > So are we encouraged to use match-case in recursion instead of if-else? > > It's more readable this way maybe: > > cubocta310.py: > > def cubocta(n): > """ > https://oeis.org/A005902 > """ > match n: > case 0: return 1 > case _: return (10*n*n + 2) + cubocta(n - 1) > > print([cubocta(i) for i in range(10)]) > > (py310) Kirbys-MacBook-Pro:School_of_Tomorrow mac$ python cubocta310.py > [1, 13, 55, 147, 309, 561, 923, 1415, 2057, 2869] > > https://flic.kr/p/2mKh2nd > (image version) > > Kirby > > ___ Edu-sig mailing list -- edu-sig@python.org To unsubscribe send an email to edu-sig-le...@python.org https://mail.python.org/mailman3/lists/edu-sig.python.org/ Member address: arch...@mail-archive.com
[Edu-sig] Re: Py310: recursion with match-case
Actually what does that look like with a stack within one function call? Is it always possible to write recursive functions with a stack (in order to avoid and the function call overhead (which includes a locals() dict on a stack anyway for every function call)) "Why is a function/method call in python expensive?" https://stackoverflow.com/questions/22893139/why-is-a-function-method-call-in-python-expensive "Python max recursion, question about sys.setrecursionlimit()" https://stackoverflow.com/questions/7081448/python-max-recursion-question-about-sys-setrecursionlimit > sys.setrecursionlimit(limit)¶ > Set the maximum depth of the Python interpreter stack to limit. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python. > > The highest possible limit is platform-dependent. A user may need to set the limit higher when she has a program that requires deep recursion and a platform that supports a higher limit. This should be done with care, because a too-high limit can lead to a crash https://docs.python.org/3/library/sys.html#sys.setrecursionlimit Python doesn't have Tail Call Optimization, so there's no *performance* benefit to the recursive form with CPython: >From https://en.wikipedia.org/wiki/Tail_call : > Tail calls can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is no longer needed, and can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail-call elimination or tail-call optimization. >From https://github.com/kachayev/fn.py#trampolines-decorator : ```rst Trampolines decorator - ``fn.recur.tco`` is a workaround for dealing with TCO without heavy stack utilization. Let's start from simple example of recursive factorial calculation: .. code-block:: python def fact(n): if n == 0: return 1 return n * fact(n-1) This variant works, but it's really ugly. Why? It will utilize memory too heavy cause of recursive storing all previous values to calculate final result. If you will execute this function with big ``n`` (more than ``sys.getrecursionlimit()``) CPython will fail with .. code-block:: python >>> import sys >>> fact(sys.getrecursionlimit() * 2) ... many many lines of stacktrace ... RuntimeError: maximum recursion depth exceeded Which is good, cause it prevents you from terrible mistakes in your code. How can we optimize this solution? Answer is simple, lets transform function to use tail call: .. code-block:: python def fact(n, acc=1): if n == 0: return acc return fact(n-1, acc*n) Why this variant is better? Cause you don't need to remember previous values to calculate final result. More about `tail call optimization < http://en.wikipedia.org/wiki/Tail_call>`_ on Wikipedia. But... Python interpreter will execute this function the same way as previous one, so you won't win anything. ``fn.recur.tco`` gives you mechanism to write "optimized a bit" tail call recursion (using "trampoline" approach): .. code-block:: python from fn import recur @recur.tco def fact(n, acc=1): if n == 0: return False, acc return True, (n-1, acc*n) ``@recur.tco`` is a decorator that execute your function in ``while`` loop and check output: - ``(False, result)`` means that we finished - ``(True, args, kwargs)`` means that we need to call function again with other arguments - ``(func, args, kwargs)`` to switch function to be executed inside while call ``` But to your actual question, what does %timeit say when you benchmark match-case vs if-else? From https://jakevdp.github.io/PythonDataScienceHandbook/01.07-timing-and-profiling.html : ```quote Here we'll discuss the following IPython magic commands: - %time: Time the execution of a single statement - %timeit: Time repeated execution of a single statement for more accuracy - %prun: Run code with the profiler - %lprun: Run code with the line-by-line profiler - %memit: Measure the memory use of a single statement - %mprun: Run code with the line-by-line memory profiler The last four commands are not bundled with IPython–you'll need to get the line_profiler and memory_profiler extensions, which we will discuss in the following sections. ``` That being said, recursive syntax is good to learn especially for languages with Tail Call Optimization: https://en.wikipedia.org/wiki/Recursion_(computer_science) > Most computer programming languages support recursion by allowing a function to call itself from within its own code. Some functional programming languages (for instance, Clojure)[4] do not define any looping constructs but rely solely on recursion to repeatedly call code. It is proved in computability theory that these recursive-only languages are
