I recently read the little schemer and that got me thinking about recursion and loops.
After starting my programming life with Python, I normally use for-loops to solve problems. But actually they are an inferior mechanism when compared to recursion, if the language provides proper syntactic support for that. Since that claim pretty much damns Python on a theoretical level (even though it is still a very good tool in practice and I still love it!), I want to share a simplified version of the code which made me realize this.
Let’s begin with how I would write that code in Python.
res = "" instring = False for letter in text: if letter = "\"": # special conditions for string handling go here # lots of special conditions # and more special conditions # which cannot easily be moved out, # because we cannot skip multiple letters # in one step instring = not instring if instring: res += letter continue # other cases
Did you spot the comment “special conditions go here”? That’s the point which damns for-loops: You cannot easily factor out these special conditions.1 In this example all the complexity is in the variable
instring. But depending on the usecase, this could require lots of different states being tracked within the loop and cluttering up the namespace as well as entangling complexity from different parts of the loop.
This is how the same could be done with proper let-recursion:
; first get SRFI-71: multi-value let for syntactic support for what I ; want to do use-modules : srfi srfi-71 let process-text : res "" letter : string-take text 1 unprocessed : string-drop text 1 when : equal? letter "\"" let-values ; all the complexity of string-handling is neatly ; confined in the helper-function consume-string : (to-res next-letter still-unprocessed) : consume-string unprocessed process-text string-append res to-res . next-letter . still-unprocessed ; other cases
The basic code for recursion is a bit longer, because the new values in the next step of the processing are given explicitly. But it is almost trivial to shell out parts of the loop to another function. It just needs to return the next state of the recursion.
And that’s what consume-string does:
define : consume-string text let : res "" next-letter : string-take text 1 unprocessed : string-drop text 1 ; lots of special handling here values res next-letter unprocessed
To recite from the Zen of Python:
Explicit is better than implicit.
It’s funny to see how Guile Scheme allows me to follow that principle more thoroughly than Python.
(I love Python, but this is a case where Scheme simply wins - and I’m not afraid to admit that)
PS: Actually I found this technique when thinking about use-cases for multiple return-values of functions.
PPS: This example uses wisp-syntax for the scheme-examples to avoid killing Pythonistas with parens.
While you cannot factor out parts of for loops easily, functions which pass around iterators get pretty close to the expressivity of tail recursion. They might even go a bit further and I already missed them for some scheme code where I needed to generate expressions step by step from a function which always returned an unspecified number of expressions per call. If Python continues to make it easier to use iterators, they could reduce the impact of the points I make in this article. ↩
The European Copyright directive threatens online communication in Europe.
But thanks to massive shared action earlier this year, the European parliament can still prevent the problems. For each of the articles there are proposals which fix them. The parliamentarians (MEPs) just have to vote for them. And since they are under massive pressure from large media companies, that went as far as defaming those who took action as fake people, the MEPs need to hear your voice to know that your are real.
If you care about the future of the Internet in the EU, please Call your MEPs.