News aggregator
Philip Wadler: Bike lanes, fewer accidents, better for business
A study conducted in New York City last year shows that bike lanes decrease accidents by up to 58%, while increasing retail business by up to 49%. Spotted via Boing Boing. Edinburgh has plans to install a bike lane on George Street downtown. I hope it will be the first of many.
A new study from the New York Department of Transportation shows that streets that safely accommodate bicycle and pedestrian travel are especially good at boosting small businesses, even in a recession.
NYC DOT found that protected bikeways had a significant positive impact on local business strength. After the construction of a protected bicycle lane on 9th Avenue, local businesses saw a 49% increase in retail sales. In comparison, local businesses throughout Manhattan only saw a 3% increase in retail sales.
list comprehension doesn't work
Trouble with Debug.Trace when using a library
Monoid, Monad, and more in C++ [x-post from /r/cpp]
(original post here)
Long time lurker, first time poster here. For a while now, I've worked on a re-implementation of a bunch of Haskell type classes, data types, and related functions in C++.
It basically started out as a simple "just for fun"-experiment--to see how much was possible--but it proved interesting enough that I just kept adding to it.
The FTL (Functional Template Library), as I came to call the library, still does not cover all that much, but it does some of the basics fairly well (Monad, Monoid, Maybe, ...), I think. In fact, at this point I think some of the results are actually quite neat and might just be useful to someone.
Anyway, leaving it here because I feel the code has reached a stage where some outside input would be nice, and reddit seemed as good a place as any.
submitted by abeark[link] [10 comments]
Reasons Haskell might not be the best imperative programming language
Some people like to say that Haskell, in addition to being a function programming language, is the worlds best (or finest) imperative programming language. The link above are some reasons it's not. I'd love to hear what other Haskellers think about these reasons that it's not. Did I miss something?
submitted by tailcalled[link] [39 comments]
ACM SIGPLAN Erlang Workshop 2013 Second Call For Papers
I want to create a personalised mug with some Haskell code on it: suggestions?
My original idea was to create a pun about the fact we italian people drink almost exclusively coffee, and I whipped up this; is not meant to be formal (the monad laws are pretty "useless" in the way they are defined), the aim was to create something which typechecks and that can be ready more or less in natural language. My attempt so far:
https://gist.github.com/adinapoli/5577889
What I don't like is that "drink = id" thing. Bear also in mind should be compact enough to fit on a mug.
Any suggestion would be appreciated :) I will then create some graphic and once my mug arrives I'll post a screenshot of the final result!
submitted by CharlesStain[link] [25 comments]
Assistant Professor in Software Systems
whats with cabal and libgmp.so.3
5outh.blogspot.com.es
newartisans.com
Philip Wadler: Elixir and prettier printing
Elixir is a functional meta-programming aware language built on top of the Erlang VM. It is a dynamic language with flexible syntax with macros support that leverages Erlang's abilities to build concurrent, distributed, fault-tolerant applications with hot code upgrades.Jonn Mostovoy kindly requested my permission to name the pretty printing module Wadler.ex, after my work on prettier printing, which extends John Hughes's work, and appears in Richard Bird's festschrift. See also Dan Leijen's Haskell version.
Functional Jobs: Test Engineer at Klarna (Full-time)
For us QA should be part of the entire development process, from concept to execution. We believe in agile methodologies and believe that to be able to build largescale, world class systems we need to focus on the users, their needs and how we can make sure that we deliver what they want. Now we are looking for Test Engineers that share our view on how to do QA in product development. As a Test Engineer, you will be part of creating a world class agile software development organisation where QA is at the center. We are not there today, but that is of course just another challenge.
As a Test Engineer you are part of an agile development team that consists of around 5-8 members. You work closely to the developers and will develop the ways you work with testing within your team. The developers do unit tests and you will mostly focus on white-box testing but also some black-box testing. The test Engineer also creates tools and test frameworks when needed to be used inside the team.
We believe that you should automate what can be automated. This means that your mission is to implement test cases, automate tests and make sure we deliver in accordance to our high demands. Since we are forming our future test organisation it is a great opportunity to help setting up and develop our ways of testing. Make your ideas be part of our overall plan.
Requirements:
- Degree in Computer science or similar degree with focus on programming
- 3+ Years of experience in testing in medium- or largescale software development
- Experience of agile software development (TDD / Scrum / Kanban)
- Broad skills in programming (preferably functional programming such as Erlang, Lisp, Scala, Scheme, F#, Haskell etc)
- Great skills in automation and scripting (Perl, Bash, Python etc)
- Broad experience in white-box testing frameworks such as xUnit
Preferred skills:
- ISTQB-certificate (or ISEB, CSTE)
- Experience of BDD, Behaviour-driven Development, or ATDD, Acceptance Test Driven Development
- Experience in different higher level testing frameworks (Selenium, Cucumber etc)
We offer you an international working environment filled with smart and ambitious colleagues. As an employee at one of Sweden’s fastest growing companies, you will play an important role in taking Klarna to the next level. You won’t work for Klarna, you’ll work with Klarna.
For questions please contact Philip Andrén at philip [dot] andren [at] klarna [dot] com or +46 (0) 76-526 00 70. We recommend you to apply as soon as possible, selection and interviews are held continuously.
Location Stockholm, Sweden
Get information on how to apply for this position.
Comparison of Enumerator / Iteratee IO Libraries?
Hi!
So I still kinda suck at Haskell, but I'm getting better.
While reading the discussion about Lazy I/O in Haskell that was revolving around this article, I got thinking about building networking applications. After some very cursory research, I saw that Yesod uses the Conduit library, and Snap uses enumerator. I also found a haskell wiki page on this different style of I/O.
That wiki lists several libraries, and none seem very canonical. My question is: as someone between the beginner and intermediate stages of haskell hacker development how would I know which of these many options would be right for writing an http server, a proxy, etc? I've been playing around with Conduit tonight as I found the Conduit overview on fpcomplete
Suggestions for uses of these non-lazy libraries? Beautiful uses that I should look at?
Thanks!
submitted by codemac[link] [31 comments]
fromIntegral not enough?
Edward Z. Yang: HotOS “Unconference” report:Verifying Systems
Ariel Rabkin has some code he'd like to verify, and at this year’s HotOS he appealed to participants of one “unconference” (informal breakout sessions to discuss various topics) to help him figure out what was really going on as far as formal verification went.
He had three questions: "What can we verify? What is impossible to verify? How can we tell that the verification is correct?" They seemed like impossibly large questions, so we drilled in a little bit, and found that Ariel had the very understandable question, "Say I have some C++ code implementing a subtle network protocol, and I'd like to prove that the protocol doesn't deadlock; how do I do that?"
I wish the formal verification community had a good answer to a question like this, but unfortunately we don't. The largest verification projects include things like verified kernels, which are written in fully specified subsets of C; which assume the translation performed by the compiler is correct, formalize C in a theorem prover, and then verify there. This is the "principled approach". It's just not feasible to take C or C++ in its entirety and try to formalize it; it's too complicated and too ill-specified. The easiest thing to do is formalize a small fragment of your algorithm and then make a hand-wavy argument that your implementation is adequate.
Martin Abadi remarked that before you embark on a verification project, you have to figure out where you'll get the most bang for your buck. Most of the time, a formalization won't get you "full correctness"; the "electrons may be faulty", as the case may be. But even a flawed verification forces you to state your assumptions explicitly, which is a good thing.
We then circled around to the subject of, well, what can be verified. Until the 90s, the formal verification community limited itself to only complete and sound analyses—and failed. The relaxation of this restriction lead to a renaissance of formal verification work. We talked about who was using formal verification, and the usual suspects showed up: safety critical software, cache coherence protocols (but one participant remarked that this was only a flash in the pan, as far as applications goes—he asserted that these companies are likely not going to use these methods any longer in the future), etc. Safety critical software is also likely to use coprocessors (since hardware failure is a very real issue), but Gernot Heiser noted that these folks are trying to get away from physical separation: it is expensive in terms of expense, weight and energy. Luckily, the costs of verification, as he recounted, are within a factor of two of normal industrial assurance, and half the cost of military assurance (though, he cautioned that this was for a specific project, and for a specific size of code.) He also remarked that as far as changes to code requiring changes to the proofs, the changes in the proofs seemed to be linear in the complexity (conceptual or implementation-wise) of the change, which is a good sign!
Well, supposing that you decide that you actually want to verify your software, how do you go about doing it? Unfortunately, it takes a completely different set of skills to build verified software versus normal software. Everyone agreed, "Yes, you need to hire a formal methods guy" if you're going to make any progress. But that's just not enough. The formal methods guy has to talk to the systems guy. Heiser recounted a very good experience hiring a formal methods person who was able to communicate with the other systems researchers working on the project; without this line of communication, he said, the project likely would have failed. And he mentioned another project, which had three times as much funding, but didn't accomplish nearly as much their team had. (Names not mentioned to protect the guilty.)
In the end, it seemed that we didn’t manage to give Ari a quite satisfactory answer. As one participant said, “You’ll probably learn the most by just sitting down and trying to formalize the thing you are interested in.” This is probably true, though I fear most will be scared off by the realization of how much work it actually takes to formalize software.
Hey guys, I’m liveblogging HotOS at my research Tumblr. The posts there are likely to be more fragmented than this, but if people are interested in any particular topics I can inflate them into full posts.
Alson Kemp: Go experiment: de-noising
CoffeeScript is a great example of how to de-noise a language like Javascript. (Of course, I know people that consider braces to be a good thing, but lots of us consider them noise and prefer significant whitespace, so I’m speaking to those folks.) What would Go code look like with some of CoffeeScript’s denoising?
TL;DR : the answer is that de-noised Go would not look much different than normal Go…
As an experiment, I picked some rules from CoffeeScript and re-wrote the Mandelbrot example from The Computer Benchmarks Game. Note: this is someone else’s original Go code, so I can’t vouch for the quality of the Go code….
Here’s the original Go code:
/* targeting a q6600 system, one cpu worker per core */ const pool = 4 const ZERO float64 = 0 const LIMIT = 2.0 const ITER = 50 // Benchmark parameter const SIZE = 16000 var rows []byte var bytesPerRow int // This func is responsible for rendering a row of pixels, // and when complete writing it out to the file. func renderRow(w, h, bytes int, workChan chan int,iter int, finishChan chan bool) { var Zr, Zi, Tr, Ti, Cr float64 var x,i int for y := range workChan { offset := bytesPerRow * y Ci := (2*float64(y)/float64(h) - 1.0) for x = 0; x < w; x++ { Zr, Zi, Tr, Ti = ZERO, ZERO, ZERO, ZERO Cr = (2*float64(x)/float64(w) - 1.5) for i = 0; i < iter && Tr+Ti <= LIMIT*LIMIT; i++ { Zi = 2*Zr*Zi + Ci Zr = Tr - Ti + Cr Tr = Zr * Zr Ti = Zi * Zi } // Store the value in the array of ints if Tr+Ti <= LIMIT*LIMIT { rows[offset+x/8] |= (byte(1) << uint(7-(x%8))) } } } /* tell master I'm finished */ finishChan <- trueMy quick de-noising rules are:
- Eliminate var since it can be inferred.
- Use ‘:’ instead of const (a la Ruby’s symbols).
- Eliminate func in favor of ‘-> and variables for functions.
- Replace braces {} with significant whitespace
- Replace C-style comments with shell comments “#”
- Try to leave other spacing along to not fudge on line count
- Replace simple loops with an “in” and range form
The de-noised Go code:
# targeting a q6600 system, one cpu worker per core :pool = 4 :ZERO float64 = 0 # These are constants :LIMIT = 2.0 :ITER = 50 # Benchmark parameter :SIZE = 16000 rows []byte bytesPerRow int # This func is responsible for rendering a row of pixels, # and when complete writing it out to the file. renderRow = (w, h, bytes int, workChan chan int,iter int, finishChan chan bool) -> Zr, Zi, Tr, Ti, Cr float64 x,i int for y := range workChan offset := bytesPerRow * y Ci := (2*float64(y)/float64(h) - 1.0) for x in [0..w] Zr, Zi, Tr, Ti = ZERO, ZERO, ZERO, ZERO Cr = (2*float64(x)/float64(w) - 1.5) i = 0 while i++ < iter && Tr+Ti <= LIMIT*LIMIT Zi = 2*Zr*Zi + Ci Zr = Tr - Ti + Cr Tr = Zr * Zr Ti = Zi * Zi # Store the value in the array of ints if Tr+Ti <= LIMIT*LIMIT rows[offset+x/8] |= (byte(1) << uint(7-(x%8))) # tell master I'm finished finishChan <- trueThat seems to be a pretty small win in return for a syntax adjustment that does not produce significantly enhanced readability. Some bits are nice: I prefer the significant whitespace, but the braces just aren’t that obtrusive in Go; I do prefer the shell comment style, but it’s not a deal breaker; the simplified loop is nice, but not incredible; eliding “var” is okay, but harms readability given the need to declare the types of some variables; I do prefer the colon for constants. Whereas Coffeescript can dramatically shorten and de-noise a Javascript file, it looks as though Go is already pretty terse.
Obviously, I didn’t deal with all of Go in this experiment, so I’ll look over more of it soon, but Go appears to be quite terse already given its design…
Tom Moertel: Tricks of the trade: Recursion to Iteration, Part 2: Eliminating Recursion with the Time-Traveling Secret Feature Trick
This is the second post in a series on converting recursive algorithms into iterative algorithms. If you haven’t read the previous post, you probably should. It introduces some terms and background that will be helpful.
Last time, if you’ll recall, we discussed The Simple Method of converting recursive functions into iterative functions. The method, as its name implies, is straightforward and mostly mechanical. The only potential trouble is that, for the method to work, you must convert all of the recursive calls in your function into tail calls.
This task can be tricky. So we also discussed the Secret Feature trick for putting recursive calls into tail-call form. That trick works well for simple recursive calls, but when your calls aren’t so simple, you need a beefier version of the trick.
That’s the subject of this post: the Time-Traveling Secret Feature trick. It’s like sending a T-800 back in time to terminate a function’s recursiveness before it can ever offer resistance in the present.
Yeah.
But we’ll have to work up to it. So stick with the early examples to prepare for the cybernetic brain augmentations to come.
Enough talk! Let’s start with a practical example.
Computing binomial coefficientsThe binomial coefficient <mfenced>nk</mfenced> for integers n and k gives the number of ways to choose k items from a set of n items. For this reason, it’s often pronounced “n choose k.” It’s very common in combinatorics and statistics and often pops up in the analysis of algorithms. A whole chapter, in fact, is dedicated to them in Graham, Knuth, and Patashnik’s Concrete Mathematics.
Math textbooks define the coefficient like this: <mfenced>nk</mfenced>=n!k!(n−k)!, but that form causes all sorts of problems for computers. Fortunately, Concrete Mathematics helpfully points out a lifesaving absorption identity: <mfenced>nk</mfenced>=nk<mfenced>n−1k−1</mfenced>, and we know what that is, don’t we? That’s a recursive function just waiting to happen!
And that identity, along with the base case <mfenced>n0</mfenced>=1, gives us today’s running example:
def binomial(n, k): if k == 0: return 1 return n * binomial(n - 1, k - 1) // kBefore going further, a cautionary point. Math math and computer math are not the same. In math math, nxk=nkx=xkn, but in computer math the equation does not necessarily hold because of finite precision or, in our case, because we’re dealing with integer division that throws away remainders. (By the way, in Python, // is the division operator that throws away remainders.) For this reason, I have been careful to use the form
n * binomial(n - 1, k - 1) // kinstead of the more literal translation
(n // k) * binomial(n - 1, k - 1)which, if you try it, you’ll see often produces the wrong answer.
Okay, our challenge is set before us. Ready to de-recursivify binomial?
Once again, the Secret Feature trickFirst, however, we must put the function’s recursive call into tail-call form. And you remember how to do that, right? With the Secret Feature trick, of course! As a refresher from last time, here’s the trick in a nutshell:
- Find a recursive call that’s not a tail call.
- Identify what work is being done between that call and its return statement.
- Extend the function with a secret feature to do that work, as controlled by a new accumulator argument with a default value that causes it to do nothing.
- Use the secret feature to eliminate the old work.
- You’ve now got a tail call!
- Repeat until all recursive calls are tail calls.
Let’s go through it, by the numbers.
Find a recursive call that’s not a tail call.
Well, there’s only three lines of logic. We’re not talking rocket science here.
def binomial(n, k): if k == 0: return 1 return n * binomial(n - 1, k - 1) // k # ^^^^^^^^^^^^^^^^^^^^^^ # right here!Identify what work is being done between that call and its return statement.
In our mind’s eye, let’s lift the recursive call out of the return statement and replace it with the variable x.
x = binomial(n - 1, k - 1) return n * x // kNow we can visualize the additional work as a separate function operating on x: multiplying it on the left by one number and dividing it on the right by another:
def work(x, lmul, rdiv): return lmul * x // rdivFor functions this simple, you can just hold them in your head and inline them into your code as needed. But for more-complicated functions, it really does help to break them out like this. For this example, I’m going to pretend that our work function is more complicated, just to show how to do it.
Extend the function with a secret feature to do that work, as controlled by a new accumulator argument – in this case a pair (lmul, rdiv) – with a default value that causes it to do nothing.
def work(x, lmul, rdiv): return lmul * x // rdiv def binomial(n, k, lmul=1, rdiv=1): if k == 0: return work(1, lmul, rdiv) return work(n * binomial(n - 1, k - 1) // k, lmul, rdiv)Note that I just mechanically converted all return {whatever} statements into return work({whatever}, lmul, rdiv).
Use the secret feature to eliminate the old work.
Watch what happens to that final line.
def work(x, lmul, rdiv): return lmul * x // rdiv def binomial(n, k, lmul=1, rdiv=1): if k == 0: return work(1, lmul, rdiv) return binomial(n - 1, k - 1, lmul * n, k * rdiv)You’ve now got a tail call!
Indeed, we do! All that’s left is to inline the sole remaining work call:
def binomial(n, k, lmul=1, rdiv=1): if k == 0: return lmul * 1 // rdiv return binomial(n - 1, k - 1, lmul * n, k * rdiv)And to simplify away the needless multiplication by 1 in the return statement:
def binomial(n, k, lmul=1, rdiv=1): if k == 0: return lmul // rdiv return binomial(n - 1, k - 1, lmul * n, k * rdiv)Repeat until all recursive calls are tail calls.
There was only one, so we’re done! Yay!
With all the recursive calls (just the one) converted into tail calls, we can easily convert the function into iterative form by applying the Simple Method. Here’s what we get after we load the function body into a one-shot loop and convert the tail call into an assignment-and-continue pair.
def binomial_iter(n, k, lmul=1, rdiv=1): while True: if k == 0: return lmul // rdiv (n, k, lmul, rdiv) = (n - 1, k - 1, lmul * n, k * rdiv) continue breakAs a final touch, we can tidy up and in the process tuck the accumulators inside the function body to keep them completely secret:
def binomial_iter(n, k): lmul = rdiv = 1 while k > 0: (n, k, lmul, rdiv) = (n - 1, k - 1, lmul * n, k * rdiv) return lmul // rdivAnd now we have an iterative version of our original binomial function!
A short, cautionary lessonThis next part is subtle but important. To understand what’s going on, you first need to see it. So, once again, let’s use the Online Python Tutor’s excellent Python-runtime visualizer. Open the link below in a new tab if you can, and then read on.
Visualize the execution of binomial(39, 9).
Click the Forward button to advance through each step of the computation. When you get to step 22, where the recursive version has fully loaded the stack with its nested frames, click slowly. Watch the return value (in red) carefully as you advance. See how it gently climbs to the final answer of 211915132, never exceeding that value?
Now continue stepping through to the iterative version. Watch the value of lmul as you advance. See how it grows rapidly, finally reaching a whopping 76899763100160?
This difference matters. While both versions computed the correct answer, the original recursive version would do so without exceeding the capacity of 32-bit signed integers.1 The iterative version, however, needs a comparatively hoggish 47 bits to faithfully arrive at the correct answer.
Python’s integers, lucky for us, grow as needed to hold their values, so we need not fear overflow in this case, but not all languages for which we might want to use our recursion-to-iteration techniques offer such protections. It’s something to keep in mind the next time you’re taking the recursion out of an algorithm in C:
typedef int32_t Int; Int binomial(Int n, Int k) { if (k == 0) return 1; return n * binomial(n - 1, k - 1) / k; } Int binomial_iter(Int n, Int k) { Int lmul = 1, rdiv = 1; while (k > 0) { lmul *= n; rdiv *= k; n -= 1; k -= 1; } return lmul / rdiv; } int main(int argc, char* argv[]) { printf("binomial(39, 9) = %ld\n", (long) binomial(39, 9)); printf("binomial_iter(39, 9) = %ld\n", (long) binomial_iter(39, 9)); } /* Output with Int = int32_t: binomial(39, 9) = 211915132 binomial_iter(39, 9) = -4481 <-- oops! */In any case, bigger integers are slower and consume more memory. In one important way, the original, recursive algorithm was better. We have lost something important.
Now let’s get it back.
The importance of respecting associativity and commutativityIt turns out that our iterative version of binomial is the original’s evil twin. Its stack usage looks charming and all, but something else about it is off. Something hard to put our finger on. What is the difference?
It all comes down to grouping and ordering decisions. Implicit grouping and ordering decisions that we overlooked during our code transformations.
Consider how both versions compute <mfenced>52</mfenced>.
First, the recursive version. We start out with n=5,k=2 and then recursively expand the expression n<mfenced>n−1k−1</mfenced>/k until we hit the base case of k=0. The series of expansions proceeds like so:
<mfenced>52</mfenced>=5<mfenced>41</mfenced>/2=5⋅(4<mfenced>30</mfenced>/1)/2=5⋅(4⋅(1)/1)/2=10.
At every step (except for the base case) we perform a multiplication by n and then a division by k. It’s that division by k that keeps intermediate results from getting out of hand.
Now lets look at the iterative version. It’s not so obvious what’s going on. (Score another point for recursion over iteration!) But we can puzzle it out. We start out with both accumulators at 1 and then loop over the decreasing values of k, building up the accumulators until k=0, at which point we return the quotient of the accumulators.
So the calculation is given by
<mfenced>52</mfenced>=lmulrdiv=((1)⋅5)⋅4((1)⋅2)⋅1=10.
Both the numerator and denominator grow and grow and grow until the final division. Not a good trend.
So why did the Secret Feature trick work great for factorial in our previous article but fail us, albeit subtly, now? The answer is that in factorial the extra work being done between each recursive call and its return statement was multiplication and nothing more. And multiplication (of integers that don’t overflow) is commutative and associative. Meaning, grouping and ordering don’t matter.
The lesson, then, is this: Think carefully about whether ordering and grouping matter before using the Secret Feature trick. If it matters, you have two options: One, you can modify your algorithm so that ordering and grouping don’t matter and then use the Secret Feature trick. (But this option is often intractable.) Two, you can use the Time-Traveling Secret Feature trick, which preserves ordering and grouping. And that trick is what we’ve been waiting for.
It’s time.
The Time-Traveling Secret Feature trickWhat’s about to happen next is so mind-bendingly awesome that you should probably get a drink to prepare yourself. It’s like combining a T-800 from The Terminator, with the dreams-within-dreams layering from Inception, with the momentary inversion of reality that occurs when the quantum field surrounding an inductive proof collapses and everything snaps into place.
It’s. Really. Cool.
Got your drink? Okay, let’s do this.
Let’s go back to our original, recursive binomial function:
def binomial(n, k): if k == 0: return 1 return n * binomial(n - 1, k - 1) // kOur goal is to create an equivalent iterative version that exactly preserves the properties of the original. Well, how the hell are we going to do that?
Hold that thought for a sec.
Let’s just stop for a moment and think about what that recursive function is doing. We call it to compute some answer xt. But that answer depends on some earlier answer xt−1 that the function doesn’t know, so it calls itself to get that answer. And so on. Until, finally, it finds one concrete answer x0 that it actually knows and, from which, it can build every subsequent answer.
So, in truth, our answer xt is just the final element in a whole timeline of needed earlier answers xi:
(x0,x1,…xt)=(xi∣i=0,1,…t).
Well, so what? Why should we care?
Because we’ve watched The Terminator about six hundred times! We know how to get rid of a problem in the present when we’ve seen its timeline: We send a Terminator into the past to rewrite that timeline so the problem never gets created in the first place.
And our little recursive problem with binomial here? We’ve seen its timeline.
That’s right. It’s about to get real.
One more thing. Every single one of these steps preserves the original function’s behavior. You can run your unit tests after every step, and they should all pass.
Let’s begin.
Send a T-800 terminator unit into the function’s timeline, back to the time of x0.
Oh, we don’t have a T-800 terminator unit? No problem. We’ll just invoke an induction hypothesis: Assume we’ve sent a T-800 terminator unit into the function’s timeline, back to the time of x0.
That was easy. What’s next?
Move the recursive call and surrounding work into a helper function.
This might seem like overkill but prevents mistakes. Do you make mistakes? Then just make the helper function already. I’m calling it step for reasons that will shortly become obvious.
def step(n, k): return n * binomial(n - 1, k - 1) // k def binomial(n, k): if k == 0: return 1 return step(n, k)Partition the helper function into its 3 fundamental parts.
They are:- the recursive call to get the previous answer xi−1,
- the work to compute the current answer xi from xi−1, and
- a return statement applied to xi alone:
Secretly prepare to receive communications from the T-800 terminator unit.
You see, once the T-800 gets its cybernetic hands on earlier values in the timeline, we can use its knowledge to eliminate the recursion. We just need some way to get that knowledge from the T-800, now stuck in the past, to us, stuck in the present.
Fortunately, we’ve seen time-travel movies, so we know exactly how this problem is solved. We just use a dead drop! That’s a prearranged secret location where the T-800 will drop values in the past and where we will check for them in the future.
So, per prior arrangement with the T-800, we’ll extend our helper function with a secret feature that checks the dead drop for a previous value xi−1 and, if one’s there, uses it to – muahahahaha! – break the recursive call chain:
def step(n, k, previous_x=None): # <- new stuff if previous_x is None: # < previous_x = binomial(n - 1, k - 1) # < x = n * previous_x // k return x def binomial(n, k): if k == 0: return 1 return step(n, k)Ordinarily, we would think of the helper as a function of ni and ki that computes xi. That’s because the xi−1 argument can safely be ignored. It has no effect unless the T-800 drops a value into it.
But if the T-800 does drop a value into it, we can see it as a function representing the transformation
(ni,ki,xi−1)→xi
And from that little kernel of power we do some seriously crazy stuff. For example: reverse the flow of time.
Yeah.
Read on.
Modify the helper’s return statement to also pass through its non-secret arguments.
def step(n, k, previous_x=None): if previous_x is None: previous_x = binomial(n - 1, k - 1) x = n * previous_x // k return (n, k, x) # <-- here def binomial(n, k): if k == 0: return 1 return step(n, k)[2] # <-- note alsoNow our helper represents the transformation
(ni,ki,xi−1)→(ni,ki,xi)
Interesting.
Apply, to the non-secret arguments in the helper’s return statement, the opposite of the transformations applied to them for the recursive call.
Since we passed n−1,k−1 for the recursive call, in the return statement we’ll pass n+1,k+1:
def step(n, k, previous_x=None): if previous_x is None: previous_x = binomial(n - 1, k - 1) # <-- look here x = n * previous_x // k return (n + 1, k + 1, x) # <-- apply opposite here def binomial(n, k): if k == 0: return 1 return step(n, k)[2]Now our helper represents the transformation
(ni,ki,xi−1)→(ni+1,ki+1,xi)
And now we can reverse the flow of time.
When we started out with our original recursive function, if we asked it for xt, the function had to go back in the timeline to get xt−1. And to get xt−1, it had to go back even further to get xt−2. And so on, chewing up stack every backward step of the way to x0. It was heartbreaking, watching it work like that.
But now, we can step the other way. If we have any (ni,ki,xi−1) we can get xi straight away, no recursion required. In goes xi−1, out comes xi. We can go forward.
Why, if we knew n1, k1, and x0, we could compute the entire series x0,x1,…xt with zero recursion by starting at i=0 and working forward.
So let’s get those values!
Determine the initial conditions at the start of the timeline.
For this simple example, most of you can probably determine the initial conditions by inspection. But I’m going to go through the process anyway. You never know when you might need it. So:
What’s the start of the timeline? It’s when the recursive binomial function calls itself so many times that it finally hits one of its base cases, which defines the first entry in the timeline, anchoring the timeline at time i=0. The base cases in this example are easy to find since we’ve already split out the step logic; all that’s left in binomial is the base-case logic. It’s easy to see that there is only one base case, and it’s when k=0:
def step(n, k, previous_x=None): if previous_x is None: previous_x = binomial(n - 1, k - 1) x = n * previous_x // k return (n + 1, k + 1, x) def binomial(n, k): if k == 0: # <-- base case return 1 return step(n, k)[2]From this base case we know that at the very start of the timeline we must have i=0, k=0, and x=1. Thus we know that k0=0 and x0=1. And because the timeline ends at time i=t, and we know that (nt,kt)=(n,k), the original arguments binomial was called with.
Let’s visualize what we know about the timeline so far as a table:
time i: 0 1 2 … t ni: – – – … n ki: 1 – – … k xi: 0 – – … ?The answer we ultimately seek is xt, marked by a question mark in the timeline.
Now to determine n1 and k1. To do that, we must answer this question: How do we go from (ni,ki) to (ni+1,ki+1)?
We already know the answer! Our step helper computes (ni,ki,xi−1)→(ni+1,ki+1,xi). So look at its logic: How does it transform its n and k arguments? It adds one to them. Thus,
ni+1=ni+1,ki+1=ki+1.
Therefore, k1=k0+1=0+1=1. Since ki is i steps from k0=0 and each step adds +1 we have ki=k0+i(+1)=i. And when i=t we know that t=i=ki=t=kt=k. Therefore t=k.
Finally, we can compute n1, which is t−1 reverse steps from nt=n, the only ni that we know so far: n1=nt−(t−1)(+1)=n−k+1.
And now we have our initial conditions:
(n1,k1,x0)=(n−k+1,1,0).
So now our knowledge of the timeline looks like this:
time i: 0 1 2 … t=k ni: n−k n−k+1 – … n ki: 0 1 – … k xi: 1 – – … ?And with this knowledge, we can step forward through the timeline, from time i=1 to time i=2, and so on, until finally, at the last step when i=t we will have determined xt, our desired answer!
Let’s do it!
In the main function, iterate the step helper t times, starting from the initial conditions. Then return xt.
def step(n, k, previous_x=None): if previous_x is None: previous_x = binomial(n - 1, k - 1) x = n * previous_x // k return (n + 1, k + 1, x) def binomial(n, k): if k == 0: return 1 t = k # <- new (n, k, previous_x) = (n - k + 1, 1, 1) # for _i in xrange(1, t + 1): # (n, k, previous_x) = step(n, k, previous_x) # return previous_x # = x_t #Boom! That’s 100% iterative. But there’s more!
Remove the base cases from the original function.
Since our iterations start from a base case, the base cases are already incorporated into our new, iterative logic.
def step(n, k, previous_x=None): if previous_x is None: previous_x = binomial(n - 1, k - 1) x = n * previous_x // k return (n + 1, k + 1, x) def binomial(n, k): # if k == 0: # <- remove these lines # return 1 # t = k (n, k, previous_x) = (n - k + 1, 1, 1) for _i in xrange(1, t + 1): (n, k, previous_x) = step(n, k, previous_x) return previous_x # = x_tBoom! That’s 100% iterative. But there’s more!
Remove the secret feature from the step function.
Since previous_x always gets a value now, make it a required part of the function and not an optional secret feature.
def step(n, k, previous_x): # <- remove default value for previous_x # if previous_x is None: # <- remove these 2 lines # previous_x = binomial(n - 1, k - 1) # x = n * previous_x // k return (n + 1, k + 1, x) def binomial(n, k): t = k (n, k, previous_x) = (n - k + 1, 1, 1) for _i in xrange(1, t + 1): (n, k, previous_x) = step(n, k, previous_x) return previous_x # = x_tInline the step function.
We’re on it!
def binomial(n, k): t = k (n, k, previous_x) = (n - k + 1, 1, 1) for _i in xrange(1, t + 1): x = n * previous_x // k (n, k, previous_x) = (n + 1, k + 1, x) return previous_x # = x_tApply finishing touches.
This example is pretty tight already, but we can substitute away the x variable.
And, because ki=i, we can replace the for loop’s induction variable _i with ki and correspondingly eliminate ki from the step logic.
And, while we’re making stuff better, there’s an obvious optimization. One property of binomial coefficients is that <mfenced>nk</mfenced>=<mfenced>nn−k</mfenced>. One property of our code is that it runs for t=k steps. So when k>n−k, we can reduce the number of steps by solving for <mfenced>nn−k</mfenced> instead. Let’s add a couple of lines at the start of the logic to claim this optimization.
And, of course, let’s add a docstring – we’re nice like that.
The final result:
def binomial(n, k): """Compute binomial coefficient C(n, k) = n! / (k! * (n-k)!).""" if k > n - k: k = n - k # 'pute C(n, n-k) instead if it's easier t = k (n, previous_x) = (n - k + 1, 1) for k in xrange(1, t + 1): (n, previous_x) = (n + 1, n * previous_x // k) return previous_x # = x_t
Let’s review what we just did. It’s mind blowing:
- We sent an imaginary T-800 terminator unit back into the function’s timeline.
- Then we added a secret feature to our function that allowed the T-800 to send us values from the timeline’s past.
- Then we used those values to break the recursive chain, reverse the flow of time, and compute the timeline forward and iteratively instead of backward and recursively.
- The function being fully iterative then, we removed the secret feature, and the imaginary T-800 winked out of existence, because we had in effect written the need for them both out of history.
- And now we have a fast, efficient, and property-preserving iterative version of our original recursive function, and it’s about as good as anything we could hope to conjure up from scratch. (See it in action – just one stack frame and easy on the ints, too.)
- And – most importantly – we did it all using a mechanical, repeatable process!
Well, that’s it for this installment. I hope you enjoyed reading it as much as I did writing it. If you liked it (or didn’t), or if you found a mistake, or especially if you can think of any way to help make my explanations better, let me know. Just post a comment or fire me a tweet at @tmoertel.
Until next time, keep your brain recursive and your Python code iterative.
In the visualization, you can’t actually see the largest integer produced by the recursive version’s computation. It’s produced between steps 32 and 33, when the return value from step 32 is multiplied by step 33’s n=39 to arrive at an integer of log2(39⋅48903492)≈30.8 bits, which is then immediately divided by k=9 to produce the final answer.↩