Gazing at the numbers: the Collatz sequence

I've been obsessing on this problem for a couple weeks. While thinking on it I made some observations on my own, so it's worth a post on my blog. Note that I'm not a mathematician, so there's more English than Math here (which, for people like me, could in fact make it easier to read). I don't have proofs for the most interesting observations I made, and they might be known already for the trained mind.

If you studied the Collatz conjecture, then you might want to jump to the TL;DR.

The problem

The Collatz conjecture defines a sequence of positive integers that starts with any number $n > 1$, and at each step, in order to get the next number, you apply this simple logic, depending on the parity of the current number $n$:

  • When $n$ is even, the next number is $n / 2$
  • When $n$ is odd, the next number is $3n + 1$

The conjecture states that any such sequence eventually reaches $1$ (of course, we could continue after $1$ but it will loop). For an example, let's start with $n = 6$: 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1.

[ read more... ]

Don't sudo gnome-disks after beers

So yesterday I was repartitioning an USB stick and I was, say, less vigilant than I usually am when I play with these tools: the wrong disk was selected. I clicked through the confirmation dialogs without thinking too much, and gnome-disks happily removed my /boot and swap partitions. About the third partition, however, it complained with a “can't unmount it” message! (that was the root partition). As I was re-reading the message in horror, I realized I was messing with the wrong disk. Holy shmoly, so it did try to unmount it! "Thanks" goes to whoever made it impossible to remove a mounted partition, and "Thanks NOT!" goes to gnome-disks for not displaying a big fat warning when I try to remove a mounted partition that it can unmount.

[ read more... ]

Pull Request based development (sucks)

Does this workflow sound familiar? The “master” branch is considered sacred, and it's therefore locked so nobody can push directly to it. Before you even start coding, there has to be a task opened in JIRA, and a branch also created from JIRA and linked to that task, and you then start pushing commits to that branch. And when you're done, you submit a Pull Request via Stash, and wait for at least two colleagues to review and approve your patch, and only then can it be merged to master.

As a developer who has been around for almost two decades, I'm going to argue why this workflow sucks. You tell me to run, and then you tie my legs.

[ read more... ]

Tweeg: a Twig to JS compiler

Tweeg is a compiler for the popular PHP template engine Twig. It converts templates to JavaScript. Not being a PHP fan, to say the least, I don't particularly like Twig. But it does the job. At eMAG we're using PHP + Symfony on the server, and Twig is pretty much non-negotiable at this point.

Sometimes we need to render the same template on the server (on initial page load) and also on the client (when we update stuff via AJAX requests). So far, such cases were rare, so we wrote separate templates for JS using a slightly modified version of John Resig's micro-templating. It sucks, but it did the job. However, we will soon face the situation that we'll have to duplicate dozen of templates, just because Twig was not supported in JavaScript. So I took upon myself the lovely task of writing a Twig parser and compiler.

Halfway through, a colleague pointed out a similar package (twig.js). Tweeg was already better in a number of ways, so I didn't give up:

  • Tweeg is a compiler, which twig.js is not. (issue)
  • Tweeg supports string interpolation, which twig.js doesn't
  • Tweeg is much smaller.

eMAG kindly agreed to open-source this package under the MIT license, so here it is. Usage details in the README.

PS: I would welcome a Gulp plugin for it. ;-)

A little JavaScript problem

In fact, this isn't about JavaScript, but that's the context I've discussed it in. I encourage you to think about it in more programming languages. (are there languages in which this can't be done?)

The problem: define functions range, map, reverse and foreach, obeying the restrictions below, such that the following program works properly. It prints the squares of numbers from 1 to 10, in reverse order.

var numbers = range(1, 10);
numbers = map(numbers, function (n) { return n * n });
numbers = reverse(numbers);
foreach(numbers, console.log);

/* output:



  • You must not use arrays. The square bracket characters, [ and ], are forbidden, as well as new Array.

  • You must not use objects. The curly braces, { and }, and the dot character (.) are forbidden. You may use curly braces for code blocks, but not for creating JavaScript objects.

  • Should go without saying, these functions must be generic and do what their name implies. They must not be hard-coded for the particular 1..10 example.

Feel free to define utilities; you don't have to restrict your program to these 4 functions. It does not matter how fast, small or elegant it is — if you can do it within the limitations above, I think you're an above-average programmer and I would probably hire you. (however: I'm not hiring)

Just for reference, my implementation (in ES6) is 8 lines of code, and it isn't totally unreadable. :-)

PS: please don't post your solutions, or links, here. I will not publish them. But feel free to email me in private if you really want me to look into it.

QUEEN, chess, and writing fast Lisp code

Back in 2008 I wrote an online chess game. It took me about a month to get it working, and then I gradually fixed bugs and added new features for another 3 months or so. It was online for about three years and I used to play chess there with my dad or friends. Then at some point I had to change my server, and it was a pain to get the server-side dependencies working again so I just dismissed my little service.

This year I've decided to put it back online, so I digged my old hard drives for the sources. As I said, it took like one month to write it -- so productive I was! A quick look at the code explains it, though. The server-side is Perl and it's basically write-only (awful) code. While I probably could sync it with the dependencies and get it back working, the feeling that there are a thousand bugs inside won't let me sleep at night, so I started rewriting the server side in Common Lisp (the client is somewhat OK, I can maintain it).

When you write chess software, even if it's not supposed to play chess but only allow two humans to play chess together, it must still have some notion about the rules of the game, for example to detect checkmate, or to prevent someone from making illegal moves. You need to implement a proper move generator even for something “as simple as” parsing chess moves in algebraic notation -- to read a move like "Ne5", which means “kNight moves to e5”, you must know where on the board is the knight of the current side that can move to e5 (and it better be only one). There's similar pain in generating the SAN notation for a move.

For Perl I wrote Chess::Rep back in 2008, and I knew I'd need something like this in Lisp, so I wrote QUEEN. It's the module I'm writing about here. The full game is not ready yet, but QUEEN is useful in itself so I published it and submitted it for inclusion into Quicklisp.

[ read more... ]

The left-pad case

“Getting tired of people hating npm and JavaScript. Some of those people even make a living through JavaScript.”

— Atanas Korchev (@korchev) March 24, 2016

I felt this was addressed to me, following a number of tweets and retweets. I'm too critic. Point taken. Luckily I don't blog often, otherwise this site would be full of rage and “everything sucks” posts.

I must say I initially sympathised with Azer when I've read his post on “liberating” his modules. I'm a programmer, I love open-source, and I would definitely hate it if somebody asked me to unpublish uglify-js just because. Heck, I've created this trend — I don't remember any packages with the “ify” suffix before Uglify.

[ read more... ]

Minesweeper and interviewing

Today I've read this article on interviewing and I decided to take the challenge:

You have one hour to implement as much of Minesweeper as possible. I've provided a JSBin for you though you're free to use whatever development tools/libraries/frameworks you're most comfortable with. You're allowed to use whatever internet resources you need, excluding plagiarism. I'll be available to answer any questions you may have. You're not expected to finish! In fact, no one ever has. Do your best and we'll chat about how things went afterward.

[ read more... ]

Multiple inheritance and multiple dispatch in JavaScript

Multiple inheritance and multiple dispatch are core features in CLOS. The standard JavaScript object system supports neither, but they can be implemented. I thought I'd write this article, along with working code, for the JavaScript fellows who don't know the concept. Maybe someone smarter than me will come up with an efficient implementation.

[ read more... ]

How to implement a programming language

I wrote a tutorial on how to implement a programming language in JavaScript. It got quite involved, and it took embarrassingly long to write. I wanted to write only about parsing, after a discussion with my dad about this problem; but once I had a parser I thought I'd add in a simple interpreter and once that was in place, I thought I'd turn it into continuation-passing style to show how we can workaround the lack of tail call optimization in JavaScript. But this opened the opportunity to talk about continuations. And of course, it was too slow so I thought I'd discuss compiling as well.

Long story short: I describe how to implement a non-trivial programming language. We get to a language that has decent performance, can interface easily with JavaScript and can offer first class continuations. To hell with the callback hell!

Read on and let me know what you think.

« Before 8 Jun 2014
Fork me on Github