Sunday, June 17, 2018

Lazy evaluation and list random access in Haskell

Lazy evaluation and list random access in Haskell

Today I learned about the :sprint command in GHCi, which prints the value bound to given identifier without forcing its evaluation. The unevaluated part, if any, is printed as an underscore.

Here, we can see that the value bound to s is entirely unevaluated at first:

λ> s = "0123456789"
λ> :sprint s
s = _

Now let’s peek at the first character in the string:

λ> head s
λ> :sprint s
s = '0' : _

We can see that only the first character in the string (i.e. the first element of a list of characters) was evaluated. Now, let’s use the !! operator to print the fourth character in s:

λ> s !! 3
λ> :sprint s
s = '0' : '1' : '2' : '3' : _

Interesting – we can see that this caused all of the intervening elements to be consumed, which demonstrates that random access of a list with the !! operator must walk along the cons cells and therefore can be expected to require linear time to complete.

If we print the whole string, then :sprint shows the entire string with no unevaluated component:

λ> s
λ> :sprint s
s = "0123456789"

Sunday, February 04, 2018

Controlling test execution in ExUnit

Controlling test execution in ExUnit

The Elixir programming language comes with a nice, simple testing library called ExUnit, and you can run all of your tests with mix test.

But sometimes you don’t want to run all your tests. Maybe you added integration tests or for whatever reason have a test that gives useful information but takes a long time to execute. In these situations, you can add the “skip” tag by adding an annotation before a test which shouldn’t be executed by mix test:

@tag :skip
test "should be skipped..." do

This way, a normal mix test run will be fast (and won’t break your continuous integration system), and when you want to actually run that test locally, you can:
mix test --include skip

However, this will run all tests marked skip. A more flexible approach is to add your own tag and use it to name your slow tests.

First, modify test/test_helper.exs to look like this, to prevent those tests from running by default:

ExUnit.start(exclude: :slow_test)

Next, annotate your slow tests with names:

  @tag slow_test: "backtest"
  test "Backtest should take ages" do

  @tag slow_test: "optimiser"
  test "Optimiser should waste a lot of time" do

Now mix test will still run your normal unit tests, and you can run one of the slow tests with mix test --trace --only slow_test:optimiser (the addition of the --trace option means ExUnit will let the test run as long as is necessary rather than killing it after 60 seconds).

Wednesday, August 30, 2017

Should we fine cyclists for breaking red lights?

(This was a comment I made in a discussion on Facebook that seemed worth saving. You be the judge.)

I don’t think cyclists should be fined for breaking red lights unless they clearly and avoidably place other people at risk, because it discourages casual cyclists and drives them back to… driving, which is of course much more likely to cause death and injury to others.

But if we insist upon it, then the fine should be proportional to the amount of damage you’re likely to do if you hit someone – this is based on many factors, so probably the most reasonable approach is a fine proportional to kinetic energy, which is the mass of vehicle and rider times the square of their speed.

Let’s do a worked example:

  • 80kg rider + 15kg bike + 5kg gear, travelling at 25km/h (just under 7 m/s)

    • = 0.5 * 100 * (6.944…)^2 = 2,411 joules
  • 80kg driver + 1180kg car (2017 Volkswagen Golf, 1.4L manual), travelling at 30km/h (city centre speed limits, just over 8 m/s)

    • = 0.5 * 1260 * (8.3…)^2 = 43,750 joules
  • 80kg driver + 3365kg van (2012 Ford Transit, 2.0L diesel), travelling at 50km/h

    • = 0.5 * 3445 * (13.8…)^2 = 332,272 joules.

So if we charged people 1 cent per joule of kinetic energy involved in these infractions, it would cost a cyclist €24.11 to break a red light, or €437.50 for a driver of a Golf doing 30, or €3322.72 for a driver of a Transit doing 50.

Or maybe we could acknowledge the fact that cyclists pose so little threat to life compared to cars and vans that we should stop discouraging them from cycling and stop focusing so much effort on blaming them for being “a menace” given that cars travelling at even low speeds carry 20 times as much kinetic energy, take more space, cause more pollution, cause more health problems, damage more bridges and lampposts, and of course cause almost all road deaths.

With this in mind, why are we even having articles in newspapers or radio discussions about the dangers posed by cyclists? Why aren’t our papers and radio discussions filled with appeals to the public to get on their bikes?

Thursday, March 19, 2015

(Linux/Ubuntu) Frequent 802.11g/WPA2 connection drops with brcmsmac/BCM4313 driver

My Samsung laptop running Ubuntu 14.10 has been dropping its WiFi connection a lot. A cursory examination of the system log reveals that it usually happens once every 20-40 minutes, with a few suspicious cases where it dropped and re-established the connection after exactly 25 minutes:
$ grep "wlan0: associated" /var/log/syslog.1
Mar 17 20:45:48 gravitycat kernel: [101379.946156] wlan0: associated
Mar 17 21:10:48 gravitycat kernel: [102880.685412] wlan0: associated
Mar 17 21:33:32 gravitycat kernel: [104244.524634] wlan0: associated
Mar 17 21:43:03 gravitycat kernel: [104815.501396] wlan0: associated
Mar 17 22:08:03 gravitycat kernel: [106316.384463] wlan0: associated
Mar 17 22:11:23 gravitycat kernel: [   35.255877] wlan0: associated
Mar 17 22:46:55 gravitycat kernel: [ 2167.317562] wlan0: associated
Mar 17 23:29:08 gravitycat kernel: [ 4701.239455] wlan0: associated
Mar 17 23:54:08 gravitycat kernel: [ 6201.802957] wlan0: associated
Mar 18 00:00:26 gravitycat kernel: [ 6579.424244] wlan0: associated
Mar 18 00:25:26 gravitycat kernel: [ 8080.034656] wlan0: associated

The connection drops usually looked like this:
Mar 17 22:08:03 gravitycat NetworkManager[785]:  Connection disconnected (reason -4)

But were sometimes preceded by this:
Mar 18 01:09:43 gravitycat kernel: [10736.798220] wlan0: cannot understand ECSA IE operating class 33, disconnecting

It alternates between "class 33" and "class 12". After a tiny bit of digging, I found a suggestion here to try switching from Gnome's NetworkManager to WICD. At first, that seemed to make things better, but it started happening again after about an hour, with the same really frustrating behaviour (having to repeatedly queue the same videos on my Chromecast when it sees me "leave" due to the laptop dropping and reconnecting to the router).

Next port of call is to check the driver. Here's what lspci says is installed in my laptop:
$ lspci -vvnn | grep -A 9 Network 
03:00.0 Network controller [0280]: Broadcom Corporation BCM4313 802.11bgn Wireless Network Adapter [14e4:4727] (rev 01)
 Subsystem: Askey Computer Corp. Device [144f:7179]

For this device, Ubuntu defaults to the "brcmsmac" open source driver, which is always preferable to a closed-source proprietary driver, all other things being equal. This issue is so frustrating, however, that I'll take the closed-source "bcmwl" driver if it works, following these steps:
$ sudo apt-get install bcmwl-kernel-source
$ sudo modprobe -r brcmsmac bcma
$ sudo modprobe wl

After manually reconnecting with WICD, things seem stable and the ChromeCast hasn't bailed over the past day or so. It's a shame the open source driver isn't working well with the BCM4313 chipset. It'd be nice if there was a simple way to get started debugging/testing the driver – i.e. not having to download a massive tarball of the latest kernel source and spend hours tweaking with build scripts and the like. Unless things have changed in the last few years and now this is easy...?

Monday, February 09, 2015

OpenCV 2.4.10 and Macports

Every time I've needed to build OpenCV on my work Mac, it's been a bit of a struggle. I have Macports installed which helps make some things easier, but throws up problems of its own:
(using "mp-gcc49")
/Users/oisin/Documents/code/vision/opencv-2.4.10/modules/highgui/src/ In function 'void cvDestroyAllWindows()':
/Users/oisin/Documents/code/vision/opencv-2.4.10/modules/highgui/src/ error: expected ';' before 'in'
     for(NSString *key in list) {

(using "apple-gcc42")
/System/Library/Frameworks/QTKit.framework/Headers/QTMovieModernizer.h:123:46: error: expected ')' before '(' token
- (void)modernizeWithCompletionHandler:(void (^)(void))handler AVAILABLE_QTKIT_VERSION_7_7_3_AND_LATER;
/System/Library/Frameworks/QTKit.framework/Headers/QTMovieModernizer.h:123:46: error: expected identifier before '(' token

The problem appears to be Objective-C stuff in QTKit and in OpenCV's HighGUI code. This time, the solution was to revert to the system-default C/C++ compiler, Clang:
$ sudo port select gcc none
Warning: port definitions are more than two weeks old, consider updating them by running 'port selfupdate'.
Selecting 'none' for 'gcc' succeeded. 'none' is now active.

It's slightly counterintuitive that "port select gcc none" is how you go back to the system compiler with Macports, and it doesn't appear to be stated in the docs, so... well here it is!

Sunday, July 27, 2014

A tiny line-editing trick for Bash (or any REPL using Readline/emacs bindings)

A lot of shells (e.g. Bash) and interactive console programs (e.g. mysql, sqlite, ghci, irb) provide a line-editing interface based on Emacs bindings, either via the Readline library or similar.

These key bindings mostly take the form of ESC-<key> which is either an uncomfortable stretch or (on a full-size keyboard) takes your left hand away from the home row and slows you down. Here's a handy tip though: pressing Ctrl+[ is equivalent to hitting escape, but allows you to keep your hands on the keyboard's home row. And if you're lucky, you can hold the Alt key instead (so you can jump backwards with Alt-b and delete the next word with Alt-d — this works on Gnome Terminal for me at least, except where the key is one of the menu accelerator characters (f, e, v, s, t or h). Seriously though, until today I was hitting ESC then the desired key...

Thursday, September 26, 2013

Ralink RF3070 USB wireless support finally added to Linux

For a long time, these cheap Chinese USB wifi adapters didn't work in Linux. Believe it or not, I wiped my old laptop's Linux partition and tried FreeBSD and OpenBSD just to see if they supported it - but they didn't either.
So I reinstalled Linux and eventually produced a patch back in June to add support for the device, but for whatever reason it was ignored.

Now, though, one of the maintainers has implemented a proper patch and it looks like the RF3070 will soon work out-of-box in Linux.