Hugo Estrada's House of Wonder

John Conway explained in an interview that he’s never applied for an academic job.

I am rather proud of the fact that, in some sense, I never applied for an academic position in my life. What happened: I was walking down King’s Parade, the main street in Cambridge, after I received my Ph.D. The chairman of the mathematics department said, “Oh, Conway, what have you done about applying for jobs? And I said, “Nothing.” “I thought that might be the answer,” he said, “Well, we have a position in our department, and I think you should apply.” And I said, “How do I apply?” And he said, “You write a letter to me.” And I said, “What should I put in that letter?” Then he lost his patience, pulled out of his pocket a letter — which had been written on one side — turned it over, and scribbled “Dear Professor Cassels” — that was his name — “I wish to apply for dot-dot-dot.” He handed it to me, and I signed it. It would have been nice if I’d gotten the job. I didn’t that year, but I got the same job the next year with the same letter.

When you expand (x + y)n, the coefficients increase then decrease. The largest coefficient is in the middle if n is even; it’s the two in the middle if n is odd. For example, the coefficients for (1 + x)4 are 1, 4, 6, 4, 1 and the coefficients for (1 + x)5 are 1, 5, 10, 10, 5, 1.

More generally, if a > 0 and b > 0, the coefficients of (ax + by)n can only have one maximum. They may increase, or decrease, or change direction once, but they cannot wiggle more than that. They can’t, for example, increase, decrease, then increase again.

Here’s a proof. The coefficients are

To show that the coefficients are unimodal as a function of k, we’ll show that their logarithms are unimodal. And we’ll do that by showing that they are samples from a concave function.

The log of the kth coefficient is

log Γ(n+1) – log Γ(k+1) – log Γ(n-k+1) + k log a + (n-k) log b.

As a function of k, the terms

log Γ(n+1) + k log a + (n-k) log b

form an affine function. The function log Γ is convex, so -log Γ is concave. The composition of a concave function with an affine function is concave, so – log Γ(k+1) and – log Γ(n-k+1) are concave functions of k. The sum of concave functions is concave. And the sum of a concave function with an affine function is concave. So binomial coefficients are log-concave and they can only have one maximum.

(The fact log Γ(z) is a convex is the easy direction of the Bohr-Mollerup theorem. The harder direction is that Γ(z) is the only way to extend factorials to all reals that is log-convex.)

Next month I'll be giving a talk at the NLCS workshop, on the chiastic lambda-calculi I first presented at NASSLLI 2010 (slides[1]). After working out some of the metatheory for one of my quals, I gave more recent talks at our local PL Wonks and CLingDing seminars (slides). The NASSLLI talk was more about the linguistic motivations and the general idea, whereas the PLWonks/CLingDing talks were more about the formal properties of the calculus itself. For NLCS I hope to combine these threads a bit better— which has always been the challenge with this work. NLCS is collocated with this year's LICS (and MFPS and CSF). I'll also be around for LICS itself, and in town for MFPS though probably not attending. So if you're around, feel free to stop by and chat. [1] N.B., the NASSLLI syntax is a bit different than the newer version: square brackets were used instead of angle brackets (the latter were chosen because they typeset better in general); juxtaposition was just juxtaposition rather than being made explicit; and the left- vs right-chiastic distinction was called chi vs ksi (however, it turns out that ksi already has an important meaning in type theory). comments

I am working on a quick and dirty Ruby bridge library, that I hope will yield a huge performance gain with template interpolation in the language-puppet library. Right now, it is capable of: Initializing a Ruby interpreter from libruby Calling Ruby methods and functions Registering methods or functions that will be called from Ruby code Converting data between the two Worlds (right now the most complex instance is the JSON one, which means that many complex Ruby types can’t be converted, but it is more than enough for passing data) Embedding native Haskell values that can be passed around in Ruby to the Haskell-provided external functions (I will use this for passing the Puppet catalog state around) There are still a few things to do before releasing it : Making compilation a bit less dependant on the system. This will probably require quite a few flags in the cabal definition … Hunting for memory leaks. I am not sure how to do this with the GHC Runtime in the middle, and I do hope that ruby_finalize frees everything that is managed by the Ruby runtime. After all, restarting processes seems to be the only working garbage collection method for Ruby daemons … Writing stubs for the Puppet library methods that might be needed by templates. I would like to be able to support custom types and functions directly written in Ruby instead of Lua, but this will probably turn into a nightmare … Cleaning things up ! Here is a quick code preview : test.hs 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 {-# LANGUAGE OverloadedStrings, OverloadedStrings #-} module Main where import Foreign.Ruby.Bindings import Data.Aeson import Data.Attoparsec.Number -- this is an external function that will be executed from the Ruby interpreter -- the first parameter to the function is probably some reference to some top object -- my knowledge of ruby is close to nonexistent, so I can't say for sure ... extfunc :: RValue -> RValue -> IO RValue extfunc _ v = do -- deserialize the Ruby value into some JSON Value onv <- fromRuby v :: IO (Maybe Value) -- and display it print onv -- now let's create a JSON object containing all kind of data types let nv = object [ ("bigint" , Number (I 16518656116889898998656112323135664684684)) , ("int", Number (I 12)) , ("double", Number (D 0.123)) , ("null", "Null") , ("string", String "string") , ("true", Bool True) , ("false", Bool False) , ("array", toJSON ([1,2,3,4,5] :: [Int])) , ("object", object [ ("k", String "v") ] ) ] -- turn it into Ruby values, and return this toRuby nv -- this is the function that is called if everything was loaded properly nextThings :: IO () nextThings = do -- turn the extfunc function into something that can be called by the Ruby interpreter myfunc <- mkRegistered2 extfunc -- and bind it to the global 'hsfunction' function rb_define_global_function "hsfunction" myfunc 1 -- now call a method in the Ruby interpreter o <- safeMethodCall "MyClass" "testfunc" [] case o of Right v -> (fromRuby v :: IO (Maybe Value)) >>= print Left r -> putStrLn r main :: IO () main = do -- initialize stuff ruby_init ruby_init_loadpath -- and load "test.rb" s <- rb_load_protect "test.rb" 0 if s == 0 then nextThings else showError >>= putStrLn And here is the ruby program, that calls our external function : test.rb 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class MyClass def self.testfunc hsfunction( [16588, "qsqsd", true, { 'a' => 'b' }, :symbol, 0.432, 5611561561186918918918618789115616591891198189123165165889 ] ).each do |k,v| puts "#{k} => #{v} [#{v.class}]" end 12 end end And the output, showing that data is properly converted from either sides : 1 2 3 4 5 6 7 8 9 10 11 Just (Array (fromList [Number 16588,String "qsqsd",Bool True,Object fromList [("a",String "b")],String "symbol",Number 0.432,Number 5611561561186918918918618789115616591891198189123165165889])) bigint => 16518656116889898998656112323135664684684 [Bignum] int => 12 [Fixnum] double => 0.123 [Float] array => 12345 [Array] true => true [TrueClass] null => Null [String] string => string [String] object => kv [Hash] false => false [FalseClass] Just (Number 12) EDIT: added link to the code.

I have come to realize that I have more ideas for programs than I'll ever have time to write. (This means they're not actually all that significant, on average — see all that's been said on ‘ideas vs. execution’.) But maybe I have the time to scribble a blog post about them, and that's stuff to blog about, if nothing else. So, a video game idea I had today: reverse bullet-hell shooter. A regular bullet-hell shooter is a game where you move in a 2D space dodging an immense number of mostly dumb instant-death projectiles launched in mostly predefined patterns, and trying to shoot back with dinkier, but better aimed, weapons. Instead, here you design the bullet pattern so as to trap and kill AI enemies doing the dodging. The roles seem a bit similar to tower defense, but the space of strategies would be considerably more, ah, bumpy, since you're not doing a little bit of damage at a time and how it plays out depends strongly on the AI's choices. That's probably the downfall of this idea: either the outcome is basically butterfly effect random due to enemy AI decisions and you mostly lose, or there are trivial ways to design undodgeable bullet patterns and you mostly win. I don't immediately see how to make the space of inputs and outcomes “smooth” enough. 2013-05-20T04:56:02Z Kevin Reid (kpreid) kpreid@switchb.org

Adam Belay (of Dune fame) was recently wondering why Haskell’s MVars are so slow. “Slow?” I thought, “aren’t Haskell’s MVars supposed to be really fast?” So I did some digging around how MVars worked, to see if I could explain. Let’s consider the operation of the function takeMVar in Control.Concurrent.MVar. This function is very simple, [...]

We are reaching limits of what is feasible with imperative languages and we should move to declarative languages. When applications written in imperative languages grow, the code becomes convoluted. Why? Imperatively programmed applications contain statements such as if X do Y else do Z. As Y and Z contain invisible side-effects the correctness of the program relies on some implicit invariant. This invariant has to be maintained by the programmer or else the code will break. Thus each time a new feature is added to an application or a bug is fixed the code for the application gets more complex as keeping the invariant intact becomes harder. After a while the code becomes spaghetti-code and bugs are introduced as the programmer fails to maintain the invariant. This is going to happen despite the best intentions of the programmer to keep things clean. Why is this? An imperative language is a type of language that tells the computer what to do and in which order. However, most, if not all, applications are nothing but a translation of some business domain into a computer program. In order to get the imperative code the programmer has to translate the business model to a set of imperative instructions, the business logic. The imperative instructions bear little resemblance to the original description of the business model. When the business model changes the imperative counterpart could change entirely but what happens is that programmers make incremental updates to the code. This is done because either they do not see that a more drastic change is necessary or because they are under pressure to deliver results. Over time this leads to bugs and unmaintainable code. Summarized, bugs are introduced because there is a manual translation step between the business model and the program code. Imagine a system for calculating whether a person should receive a certain allowance. To receive the allowance a person has to meet several criteria such as age > 18 and income < 2400. We can denote this in the following way: 1 2 3 def receives_allowance?(age, income) age > 18 && income < 2400 end There are several remarks to be made for this code. Adding a criteria such as marital status would involve adding a parameter to the function and changing the boolean expression. We could already avoid having to change parameters when we had chosen a parameter of type Person that contains the information about a person. But what if we would introduce time as an aspect in our criteria? We need to change the function again. And what if the age criteria changed? If the programmer erroneously codes something like age > 18 && age < 18 into the condition we would only find the bug during testing, if we are lucky. Additionally when our criteria become more complex we would like to extract criteria to their own functions. In short, it is easy to make mistakes this way. A solution to this is to avoid the translation process by using a declarative language. A declarative language is a language that describes what is to be computed but not how it should be computed.1 In essence: it omits control-flow. By encoding and thereby recording the business model into a set of declarative statements it becomes easier to spot irregularities in the business logic as the business logic reads more like the description of the business model and all invariants are visible. In this manner the programmer no longer tells the computer how to perform a computation but rather what the computation should be. This makes it easier to maintain However, we take it even to an higher level entirely. By just using the declarative language, such as Haskell or Prolog, you are still using a general-purpose language and are thus lacking domain specific checks. It would be advantageous to devise a Domain Specific Language (DSL) instead. This would be a language specifically geared towards your business domain and can be done easily in a language such as Haskell. Creating a DSL has a great benefit: Because the business domain is written down in code the responsibility of translating the business domain into a program shifts from the programmer to the interpreter of the DSL. This has two benefits: the translation is consolidated in one single point (the interpreter) and can be verified or even proven to be correct. It could be checked that no contradicting statements are present. In this sense we can compare the validation to a spell-checker or JSLint but for our specific domain. Secondly the programmer cannot make mistakes in the translation of the business logic to imperative code. A simple DSL embedding the idea of the allowance could look like the text in the examples below. The interpreter / compiler is able to inspect the separate rules and check whether they would cause a tautology or contradiction. We will illustrate this with some examples. Consider the following text below, it is easy to read and it is clear what it means. Each line is a condition that has to hold, so we could read an “AND” at eacht line end. (Whether Income is monthly or annually or weekly is not taken into account here but you get the picture.) 1 2 3 4 5 A person is an adult when his Age is GREATER THAN OR EQUAL TO 18 A person is allegeable for an allowance IF he is an adult A person is allegeable for an allowance IF his Income is NOT GREATER THAN €2400 When we would add a rule as shown below, we could get a warning or error from the interpreter telling us that we have two different conditions on a person’s age. 1 2 3 4 5 6 7 A person is an adult when his Age is GREATER THAN OR EQUAL TO 18 A person is allegeable for an allowance IF he is an adult A person is allegeable for an allowance IF his Income is NOT GREATER THAN €2400 A person is allegeable for an allowance IF his Age is GREATER THAN 21 And when we would add a rule as this it could warn us that no-one will ever get an allowance. 1 2 3 4 5 6 7 A person is an adult when his Age is GREATER THAN OR EQUAL TO 18 A person is allegeable for an allowance IF he is an adult A person is allegeable for an allowance IF his Income is NOT GREATER THAN €2400 A person is allegeable for an allowance IF his Age is LESS THAN 12 Not only would the interpreter be able to spot these kinds of errors but it would also be easier for the writer of these rules to spot whether there is a mistake. The astute reader will have noticed than we have not included any control flow into our language making it a declarative language. Because the business-logic is now represented by the DSL it can be written by domain experts instead of the programmers of the application itself. The compiler can provide feedback when something is wrong in the DSL and there is less chance for errors in the implementation of the business logic. Additionally this frees the programmes for implementing better translations of the DSL or other projects saving time and other resources. To summarise 4 reasons why you should switch to declarative languages: Direct translation of the business model into business logic Better readability of the business logic Better scalability for the program in terms of functionality Less bugs And 3 reasons why you should use DSLs to boot: Free up programmers to do important stuff Let the domain-experts handle the business logic and have it machine-checked! It is just awesome Lloyd, J.W., Practical Advantages of Declarative Programming↩

I just released the latest language-puppet version. For the full list of changes, please take a look at the changelog. Here are the highlights. PuppetDB code reworked The PuppetDB code and API has been completely overhauled. It is now more generic : the resource collection and puppet query functions now work the same. Additionally, a PuppetDB stub has been created for testing use. Better diagnostic facilities As the main use of this library is to test stuff, the following features were added: Several error messages have been reworked so that they are more informative. A dumpvariables built-in function has been added. It just prints all known variables (and facts) to stdout, and can be quite handy. The “scope stack” description is stored with the resources. This turned out to be extremely useful when debugging resource names colisions or to find out where some resource is defined. Here is an example, let’s say you do not remember which package installs the collectd package. Just run this : 1 2 3 4 5 6 7 » puppetresources . default.domain 'Package[collectd]' package { "collectd": #"./modules/collectd/manifests/base.pp" (line 4, column 9) ["::","site::baseconfig","collectd","collectd::client","collectd::base"] ensure => "installed", require => [Class["collectd"], Class["collectd::base"], Class["collectd::client"], Class["site::baseconfig"]]; } You now know exactly where the package resource is declared, and the list of “scopes” that have been traversed in order to do so. Note that this information is displayed when resources names collide. Easier to setup This library doesn’t depend from a newish bytestring anymore, and should build with the package provided with a GHC compiler of the 7.6.x serie. This is not yet done, but I will certainly soon publish a debian-style repository of the compiled puppetresources binary. I am interested in suggestions for an automated building system. Better testing The testing API seems sufficient to write pretty strong tests, but would still benefit from a few more helper functions. The testing “daemon” has been reworked to use the new PuppetDB stub. It makes it possible to test complex interactions between hosts using the exported resource or PuppetDB query features. Work in progress I will probably lensify the code until I get a descent understanding of it. I do not intend to work on Hiera emulation just yet, as I am probably the only user of this library for now and I do not use this feature. One area of improvement would be to embed the ruby interpreter in the library. I am not sure how to do this, but as there are quite a few projects of lightweight interpreters sprouting from the earth, it might be possible in the near future. The only problem would be figuring out how to build a large C project with cabal. Some other considerations I recently ported the code from random.c to Haskell (here). This has been quite tedious, and is quite hard to read. This is an almost naive port of the code found in the Ruby interpreter, without the useless loop variables. For some reason, there are many loops like this : 1 2 3 4 5 6 7 8 9 10 i=1; j=0; k = (N>key_length ? N : key_length); for (; k; k--) { mt->state[i] = (mt->state[i] ^ ((mt->state[i-1] ^ (mt->state[i-1] >> 30)) * 1664525U)) + init_key[j] + j; /* non linear */ mt->state[i] &= 0xffffffffU; /* for WORDSIZE > 32 machines */ i++; j++; if (i>=N) { mt->state[0] = mt->state[N-1]; i=1; } if (j>=key_length) j=0; } As you can see, the value of k is never used in the loop. I am not sure why the author didn’t go for something like : 1 for(i=1;i Anyway, the Haskell code is pretty bad, and will certainly only work for 64-bit builds. I am not sure how I should have written it. I suppose staying in the ST monad would have lead to nicer code, and I am open to suggestions.

I've posted this elsewhere, but neglected to blog before now. We are recruiting for research associate positions in design and implementation of programming languages, and also may have PhD studentships available this year and next. The posts are on the project "From Data Types to Session Types: A Basis for Concurrency and Distribution" which is a programme grant funded by EPSRC for five years from 20 May 2013, joint with Simon Gay at the University of Glasgow and Nobuko Yoshida at Imperial College London.The RA post at Edinburgh for an initial period of 24 months, with possibility of extension, and is on the UE07 scale (£30,424 - £36,298). Deadline for applications for the RA post is Monday 20 May 2013, anyone interested in a PhD studentship should apply as soon as possible.  Glasgow and Imperial are also recruiting.Please contact me if you are interested in either the RA post or a PhD studentship.  Further description of the Edinburgh RA post is below. Project DescriptionJust as data types describe the structure of data, session types describe the structure of communication between concurrent and distributed processes. Our project has particular emphasis on putting theory into practice, by embedding session types in a range of programming languages and applying them to realistic case studies. The research programme is joint between the University of Edinburgh, University of Glasgow, and Imperial College London, and includes collaboration with Amazon, Cognizant, Red Hat, VMware, and the Ocean Observatories Initiative.Principal DutiesThe successful candidate will join a team responsible for extending the functional web programming language Links with session types to support concurrency and distribution. We will test our techniques by providing a library to access Amazon Web Services (AWS) cloud computing infrastructure, and perform empirical experiments to assess how our language design impacts the performance of programmers. You should possess a PhD in a relevant area, or be nearing completion of same, or have comparable experience. You should have a track-record of publication, or other evidence of ability to undertake research and communicate well. You should have a strong background in programming languages, including type systems, and strong programming and software engineering skills. It is desirable for candidates to also have one or more of the following: a combination of theoretical and practical skills; experience of web programming or cloud programming; knowledge of the theory or practice of concurrent and distributed systems; knowledge of linear logic; or training in empirical measurement of programming tasks. We seek applicants at an international level of excellence. The Laboratory for Foundations of Computer Science is internationally renowned, the School of Informatics at Edinburgh is among the strongest in the world, and Edinburgh is known as a cultural centre providing a high quality of life. Further details of the RA post, including how to apply, are here.  

A few months ago, John Papa released a Visual Studio template called Hot Towel SPA, which Scott Hanselman kindly pointed out to me. SPA, as all the hip kids will tell you, stands for Single Page Application. That is, the kind of application that you start by visiting a web page, and you stay on [...]

Aleph Cloud is looking to hire Haskell programmers.

Release notes for Snap 0.12

I have released a new version of the LaTeX ucs package yesterday, which is version 2.2. It fixes the bug that is described in the TeX StackExchange question Conflict between ifxetex and ucs under pdflatex/xelatex – why?. Tagged: CTAN, LaTeX, software release, StackExchange, TeX, ucs (LaTeX package), Unicode

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. 2013-05-14T07:28:33Z

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 [...]

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 [...]

Posted on May 14, 2013 Tags: programming, recursion, iteration, python, google code jam, puzzles, recursion-to-iteration series, tail calls 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 coefficients The binomial coefficient nk 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: nk=n!k!(n−k)!, but that form causes all sorts of problems for computers. Fortunately, Concrete Mathematics helpfully points out a lifesaving absorption identity: nk=nkn−1k−1, 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 n0=1, gives us today’s running example: def binomial(n, k): if k == 0: return 1 return n * binomial(n - 1, k - 1) // k Before 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) // k instead 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 trick First, 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 // k Now 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 // rdiv For 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 break As 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 // rdiv And now we have an iterative version of our original binomial function! A short, cautionary lesson This 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 commutativity It 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 52. First, the recursive version. We start out with n=5,k=2 and then recursively expand the expression nn−1k−1/k until we hit the base case of k=0. The series of expansions proceeds like so: 52=541/2=5⋅(430/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 52=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. Also, note that the order of the multiplications is the opposite of what it is for the recursive version. In the recursive version, the multiplications by decreasing n associate to the right as 5⋅(4⋅(⋯)), but in the iterative version it’s to the left as ((⋯)⋅5)⋅4. So it all comes down to grouping and ordering. Commutation and association. Really? Then here’s a question: 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 multiplication (of integers that don’t overflow) is commutative and associative. Meaning, order and grouping don’t matter. xyz=xzy=yxz=yzx=zxy=xyz=(xy)z=z(yz) But the extra work in binomial includes throw-away-the-remainder division, for which ordering and grouping matter – a lot. It’s rarely true that any of the following equations holds: x/y=y/x(x/y)/z=x/(y/z) The lesson, then, is clear: 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 trick What’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) // k Our 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: def step(n, k): previous_x = binomial(n - 1, k - 1) # part (1) x = n * previous_x // k # part (2) return x # part (3) def binomial(n, k): if k == 0: return 1 return step(n, k) 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 also Now 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_t Boom! 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_t Inline 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_t Apply 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 nk=nn−k. 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 nn−k 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! Thanks! 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.↩ 2013-05-14T00:00:00Z 2013-05-14T00:00:00Z

I’m helping organize a new workshop, FARM, to be held in Boston this September (right after ICFP). Many readers of this blog may have already seen the announcement, but I thought it worth saying a bit more about it here, … Continue reading →

This was on a freshly installed and dist-updated i386 Ubuntu 12.10 Quantal Quetzal .apt-get install --no-install-recommends xmonad libghc-xmonad-contrib-dev gnome-panel indicator-applet-complete indicator-multiloadindicator-multiload is optional, but I like it.~/.xmonad/xmonad.hs:import XMonad import XMonad.Config.Gnome main=xmonad gnomeConfig Logout, the choose the "GNOME with Xmonad" login option available above and to the right of the password field. indicator-multiload fails to start on its own at first. Run it from the command line. It will start correctly, automatically, on future logins.These instructions also seem to work on Ubuntu 13.04 Raring Ringtail i386.See also Using xmonad in Gnome on the Haskell wiki.

There was an interesting question by ‘Fool’ recently on the StackExchange site for Boardgames: How do you play a game like Rock-Paper-Scissors with friends online? Or any other game where players have to simultaneously submit their moves (e.g. Diplomacy, or Rock-Paper-Scissors-Lizzard-Spock), which, as I just learned, are simultaneous action selection games. While there are websites dedicated to playing specific games, such as webdiplomacy.net, we could not find a generic one that you can use if you, for example, invent your own variants of a game. So I created one: At you-say-first.nomeata.de you can enter rooms and share the URL with your friends. On the one hand, you have a regular chat room there. But there is also the possibility to enter moves (whatever a move may be to you) and only when all players have done that and marked the move as final, it is shown to everyone. If you want to try it out: There is an integrated, not very fancy Rock-Paper-Scissors-playing bot. Just enter a room, join and say „I want to play!“ Note that this site can be used for more than just for games. Have you ever observed that persons would often want other to express their preference (e.g. where to dine) first to not reveal their own preference, so that they can (or pretend to) change their mind if they would contradict? In such situations simultaneous action selection can be a fairer method. A technical note: I created this web app using meteor (a JavaScript framework building on node.js and MongoDB that allows for reactive programming), and it is also hosted on meteor.com. I chose Meteor after someone mentioned Firebase to me, which looked very slick, but was not Free Software, so I looked for alternatives. I did not do any cross-browser-testing, and the UI design could be improved, so if you want to help out (or just complain), please use the GitHub code repository and issue tracker.