10 September, 2017

Unix exit codes as an indicator of tooling (im)maturity.

If your compiler for your new language, or your test running, or whatever, doesn't return a unix exit code when it exits with an error - that's something that annoys me - and it's an indicator that no one is using your tool for serious - for example in an automated build system.

I've hit this a couple of times at least in the last year. grr.

01 September, 2017

Pattern matching in Idris `do` notation has surprising reliance on type checking the action.

Idris is syntactically quite Haskell-like, and especially it has do notation for sequencing "actions".

Like (traditional) Haskell, do blocks are desugared to a sequence of >>= (bind) operators. But, unlike (traditional) Haskell, that >>= is not always the monadic >>= : m a -> (a -> m b) -> m b. (This can also happen in Haskell using rebindable syntax)

In Idris, you can use different "better-than-monad" types to statically (at compile time) reason about a computation beyond using the monad laws. For example, an effect system might track which effects are in scope.

Total parsing

In the case of Text.Parser (in the Idris contrib/ package) the type signature of actions (Grammar _ _ _ indicates whether a parser consumes any characters so that the compiler can tell if a parser might loop forever. (see http://www.cse.chalmers.se/~nad/publications/danielsson-parser-combinators.html)

I was trying to write a new JSON parser for idris-todaybot using Text.Parser. Previously JSON was parsed using lightyear, but Text.Parser has more gratuitous dependent types so was an obvious way to proceed.

A problem.

I ran into a surprising compile error which initially made no sense to me at all.

This code compiles:

objectValuePair : Grammar Char True (List Char, ())
-- definition elided

jsonObject : Grammar Char True (List Char, ())
jsonObject = do
  llll <- objectValuePair
  pure llll

where llll is a tuple; but the following version of jsonObject, which desconstructs that tuple and reassembles it, does not compile:

jsonObject : Grammar Char True (List Char, ())
jsonObject = do
  (k,v) <- objectValuePair
  pure (k,v)

It gives this error:

When checking right hand side of Main.case block
in jsonObject at bug-bind.idr:55:14 with expected type
        Grammar Char c2 (List Char, ())

Type mismatch between
        Grammar Char False (List Char, ()) (Type of pure (k, v))
and
        Grammar Char c2 (List Char, ()) (Expected type)

Specifically:
        Type mismatch between
                False
        and
                c2

Another attempt to deconstruct llll also fails:

  jsonObject : Grammar Char True (List Char, ())
  jsonObject = do
    llll <- objectValuePair
    let (k,v) = llll
    pure (k,v)

but the following deconstruction by function application rather than pattern matching succeeds:

jsonObject : Grammar Char True (List Char, ())
  jsonObject = do
    llll <- objectValuePair
    let k = fst llll
    let v = snd llll
    pure (k,v)

That type error

Let's dig into that type error:

Type mismatch between
        Grammar Char False (List Char, ()) (Type of pure (k, v))
and
        Grammar Char c2 (List Char, ()) (Expected type)

Grammer _ _ _ is the type of parser actions, where the first parameter Char is the type of symbols we're consuming, the final parameter (List Char, ()) is the type that the parser will return on success, and the middle parameter (False or c2) represents whether the parser will definitely consume input (True) or might succeed without consuming anything (False - for example, a parser which removes whitespace, or pure which never even looks at the input stream).

This "consumes" parameter contains the main novelty in Text.Parser beyond monadic parser combinators: Text.Parser combinators manipulate and use this value at compile time to help check that parsers really will consume things: for example, a parser that definitely consumes followed by a parser that might not, results in a parser that definitely consumes; while sequencing two parsers that might not consume results in a parser that might not consume. (See: the source)

So what on earth has this parameter, manipulated by >>=, got to do with pattern matching pure values after they've already been returned by an action?

Desugaring

It turns out we can forget that our troublesome tuple is being returned from an action; let (a,b) = (1,2) breaks in the same way when run inside a Text.Parser do block.

Let's (very roughly) desugar some of the examples above, and then look at the types involved:

jsonObject : Grammar Char True (List Char, ())
jsonObject = do
  llll <- objectValuePair
  pure llll

-- becomes:
jsonObject = objectValuePair >>= (\v => pure v)

jsonObject = do
  (k,v) <- objectValuePair
-- becomes: 
    objectValuePair >>= (\(k,v) => pure (k,v))
-- becomes: 
    objectValuePair >>= (\llll => case llll of
      (k,v) => pure (k,v)
     )

So in the second fragment, there's an extra case expression in there to deconstruct llll using pattern matching.

Apparently that gets in the way of type inference/checking:

  • On the one hand, that pure has type: Grammar Char False (List Char, ()) - false because it may (actually, will always) succeed without consuming input.
  • On the other hand, >>= doesn't care whether the right hand side consumes or not - it will take either, as shown by the compile time variable c2 appearing in the error message.
Idris doesn't manage to unify c2 = False.

With further pinning of types using the, an uglier form of pattern matching does work:


export jsonObject : Grammar Char True (List Char, ())
  jsonObject = 
   do
    llll <- objectValuePair
    the (Grammar Char False (List Char, ())) $ do
        let (k,v) = llll
        pure (k, v)

Ugh

Thanks

Thanks to Melvar on #idris for explaining this.

highlight.js in blogger

Syntax highlighting is pretty. highlight.js can do it in a browser. I just added it to this blog.

  1. In Blogger, click "Theme" then "Edit HTML"
  2. Find the <head> section of the theme.
  3. Insert the following at the end, before the closing <head> tag:
    <link href='//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/styles/default.min.css' rel='stylesheet'/>
    <script src='//cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/highlight.min.js'/>
    <script src='https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/languages/haskell.min.js'/>
    
  4. Add as many copies of the third line as you want, modifying haskell to the additional languages that you want to be able to highglight.
  5. When writing code, wrap it in <pre><code class="haskell"> YOUR CODE </code><pre>

31 August, 2017

Raspberry Pi Zero W + cam timelapse

I got a Raspberry Pi Zero W and a camera module.

I wanted a timelapse video.

This is how I did it:

Capture a sequence of image frames

This will capture a sequence of images (forever) approximately every minute, with the filename being a unix timestamp.

while true; do raspi-still -o $(date +%s).jpeg ; sleep 60s; done

Leave this to run for as long as you want to collect frames, and you'll end up with a bunch of numerically named files, like this:

$ ls
1504014800.jpeg
1504014866.jpeg
1504014931.jpeg
...

Combine the sequence of image frames into a jpeg

After you've got all the frames you want, use ffmpeg to join the frames together. I do this on a different Linux box (my laptop) but you should be able to do it on the Pi too.

First make a command file listing all the jpeg files:

ls *jpeg | while read a ; do echo file $a; done > e.cmd

Next, feed that command file into ffmpeg to generate a video:

ffmpeg -f concat -i e.cmd -b:v 1500000 -r 24 -c:v libx264 e8.mp4

As a result, the output video should be in e8.mpg which is in a form suitable for playing with vlc or uploading to YouTube.

20 August, 2017

An income tax explorer, using R and Shiny

I got carried away with my R code for plotting income tax rates, and now it is an interactive webapp https://benc.shinyapps.io/r-income-tax/ using Shiny, a web framework for turning your R code into a website. Thanks Tom Nielsen for convincing me (in this talk about making a Haskell port of Shiny) to try it out.

18 August, 2017

A first project in R / UK income tax graphs

The UK income tax system has a progressive tax rate that gets higher as your income is higher. However it has a few quirks. I've been meaning to graph the effective rates, and today I felt like learning a bit more R to do it. I've included income related student loan repayments and National Insurance because they are, to some extent, income-tax-like.

The code at https://github.com/benclifford/r-income-tax can generate the following three graphs:

Marginal income tax rates, coloured by component, for varying income:

Total tax, for varying income:

Fraction of income taken as tax, for varying income:

24 July, 2017

WinTec GRays 2 GPS device feeding to NTP

USB driver

When I got a wintec g-rays2, it didn't work on USB out of the box with whatever laptop I had (probably a macbook), but was OK on Bluetooth, so that's what I stuck with.

Now, eight years later, I plugged it into one of my Raspberry Pis and it appears as /dev/ttyUSB1 by magic!

Getting NMEA sentences in minicom

minicom --device=/dev/ttyUSB1 --baud=4800 gives some garbled stuff every second, so I'm receiving the NMEA sentences but at the wrong serial port settings.

The manual didn't give any help but a bit of fiddling reveals sensible looking output at 57600 baud, 8N1 (here you can see where I live).

$GPRMC,121815.000,A,5130.3697,N,00003.7216,W,0.00,148.43,240717,,,A*72     
$GPGGA,121815.000,5130.3697,N,00003.7216,W,1,05,2.9,46.2,M,47.0,M,,0000*70 
$GPGSA,A,3,21,26,31,27,16,,,,,,,,4.3,2.9,3.2*38                            
$GPGSV,3,1,12,05,03,021,28,10,08,157,19,21,67,086,34,26,69,175,39*7C       
$GPGSV,3,2,12,29,12,083,,07,08,333,,31,06,193,26,20,27,059,24*72           
$GPGSV,3,3,12,49,,,35,27,43,274,31,16,72,283,39,18,26,132,23*4D 

These lines are spewed out once a second without needing to send any start command to the GPS unit.

Getting ntpd to pay attention

$GPRMC and $GPGGA are the relevant sentences for ntpd, according to the manual.

I already have ntpd runnning on this Pi, with an MSF receiver configured already.

This gives a /dev/gps0 (at least until reboot):

cd /dev
sudo ln -s ttyUSB1 gps0

and this line in /etc/ntpd.conf makes ntpd look for NMEA time sentences on /dev/gps0:

server 127.127.20.0 mode 67

The mode, decimal 67, means hexadecimal 0x43: 0x01 listen for GPRMC, 0x02 listen for GPGGA, 0x40 use 57600 baud.

And after a restart, tada! (although apparently a 160ms delay compared to all my other time sources. ick)

pi@faeroe /dev $ ntpq --peers
     remote           refid      st t when poll reach   delay   offset  jitter
==============================================================================
 2001:8b0:1638:9 81.2.122.172     2 u   39   64   17    0.952  157.794   0.783
 ntp2.aa.net.uk  195.66.241.2     2 u   41   64   17   14.923  162.505   0.671
 SHM(2)          .MSF.            0 l    -   64    0    0.000    0.000   0.000
*GPS_NMEA(0)     .GPS.            0 l   55   64    7    0.000   -5.660   0.819
 tyne.cqx.ltd.uk 81.2.122.172     2 u   46   64   17    0.674  157.858   0.759

03 July, 2017

/etc/hosts - the gift that keeps on giving

/etc/hosts

The gift that keeps on giving, when you're paid on an hourly rate to do tech support. It is like the regexps of DNS: "I know, I'll modify /etc/hosts" ... now you have two problems.

  • You modify /etc/hosts because you want to override the global DNS view of name N.
  • Things works!
  • Because things work, you don't undo your change in /etc/hosts. After all, things work.
  • A year passes.
  • You forget that you made the change.
  • Suddenly on your machine only, but no one else's, you can't access the website at N any more.
  • Hours of debugging!

Why modify /etc/hosts? Testing a new version of a site under real name (only on your own machines though), or because DNS is broken and you don't know why, or because you didn't plan your DNS change so now the caches are not updating fast enough and you are impatient.

/etc/hosts doesn't have an "eventual consistency" mehanism in place - DNS caches eventually expire and at least give vaguely consistent behaviour across the whole internet over a long enough period of time. /etc/hosts will never converge.

26 June, 2017

ffmpeg animated gif custom palettes

I used ffmpeg to make the animated gifs for my gallery of NeoPixel goggles patterns.

In the process I discovered that as well as the expected fairly straightforward conversion mode, ffmpeg -i mymovie.mov mymovie.gif, there is another mode which can generate a custom palette. Because apparently by default, a default palette is used.

That is a slightly more awkward two step process, described for example here, but at least for my goggles GIFs looks way better (to me) although turning out to be four times the size:

17 June, 2017

Galois LFSR PRNG in NeoPixel goggles

I've been playing with software to run on my Adafruit Neopixel Goggles. The software gets to make pretty patterns on 32 x 24-bit RGB LEDs arranged in two rings.

One of the modes picks random colours to change each ring to. The Arduino stack supplies a random() function to do this, but it seemed to take up about 600 bytes of the limited 5kb flash program memory on the in-goggles microcontroller.

I wondered if I could make a smaller-but-less-random generator. After all, the colour pattern does not need to be cryptographically secure. I'm just trying to avoid getting the same sequence of colours every time.

Someone pointed me at Linear Feedback Shift Register PRNGs and I implemented one based around a description in Wikipedia. I chose the Galois one because pistols at dawn.

That seemed to work well for the basic generation of random numbers, but the Arduino always started up with the same seed, and so gave the same sequence of colours each time. Luckily, there are 512 bytes of EEPROM on this microcontroller and so I used two other those to generate and store a seed to be used next time.

Initially, I generated two random bytes at power-on, and stored those into the EEPROM. However, this rapidly proved to have a really short period: there were only two different patterns being displayed by the goggles in this mode!

So, next, which seems to work better, the code now initialises the PRNG from EEPROM, takes a single bit from it (and discards it) and then writes out the PRNG state into the EEPROM. That means that the start state advances by one bit every boot.

Code for the goggles is here on github: https://github.com/benclifford/goggles.

14 June, 2017

An Idris implementation of a reddit bot.

I wrote and host lsc-todaybot, a bot that moves the [TODAY] flair around on reddit.com/r/LondonSocialClub, a subreddit dedicated to social activities in London. I wrote it in Haskell, and over the last year or so have used it as a simple application for experimenting with different Haskell libraries and techniques. For example, I used it to learn about extensible effects (and gave a talk about it at the London Haskell meetup).

I've been interested in the dependently typed programming language Idris and someone claimed it was pacman-complete - that is, you can write Pacman in it. So rather than playing round with proofs and all that dependent-type gubbins, I set out to rewrite todaybot in Idris.

It's here: https://github.com/benclifford/idris-todaybot

It's not beautiful. But it works well enough to be running alongside the Haskell implementation.

I've littered the source with QUESTION/DISCUSSION blocks, but basically I had to patch up an existing JSON library, interface an HTTP library (I chose libcurl), and struggle with a whole new style of error message (possibly the hardest bit as I'm used to error messages really leading you to the right answer).

There's almost no use of dependent types, but I did find a straightforward place to make use of them, in the parameters to this libcurl function:

CURLcode curl_easy_setopt(CURL *handle, CURLoption option, parameter);

where the type of the supplied parameter depends on the particular option chosen: for example a pointer to a callback function, or a boolean verbosity level.

07 June, 2017

Fixing up my MSF radio clock

One of the first hardware things I did with a Raspberry Pi (sometime around March 2013) was interface it to a cheap 60kHz radio clock board, and write some driver software to interface it to ntpd. That was in one house, then in another, and then got dismantled, put in a box, and smashed up a bit. Based on the

I spent a few hours yesterday fixing it up: resoldering the antenna onto the circuit board, getting rid of the dodgy soldering and putting it on a prototype board, putting a capacitor across the power supply because I heard rumour that might make it receive better (it doesn't seem to), and implementing parity checking in the decoder.

It's still terribly awkward to position: I have it velcroed up on top of a curtain rail to try to get it high and away from all my other electronics and it is still very sensitive to antenna positioning; and it is still estimated by ntpd to be less accurate than getting time off the internet; and even with parity checking it is still fairly common for it to decode a time that is wrong.

But it has a nice flashing red LED.

Software: https://github.com/benclifford/msf

05 March, 2017

toad.com open mail server

So there was some controversy decades ago the past about John Gilmore's public open SMTP relay server. I wondered if it still existed.

It does!

benc@dogger:~$ telnet new.toad.com 25
Trying 209.237.225.253...
Connected to new.toad.com.
Escape character is '^]'.
220 new.toad.com ESMTP Sendmail 8.12.9/8.12.9; Sun, 5 Mar 2017 08:12:44 -0800
EHLO dogger.cqx.ltd.uk
250-new.toad.com Hello dynamic-91.hawaga.org.uk [90.155.94.91] (may be forged), pleased to meet you
250-ENHANCEDSTATUSCODES
250-PIPELINING
250-8BITMIME
250-SIZE 89000000
250-DSN
250-ETRN
250-AUTH GSSAPI
250-STARTTLS
250-DELIVERBY
250 HELP
MAIL FROM:benc@hawaga.org.uk
250 2.1.0 benc@hawaga.org.uk... Sender ok
RCPT TO:benc@hawaga.org.uk
250 2.1.5 benc@hawaga.org.uk... Recipient ok
DATA
354 Enter mail, end with "." on a line by itself
Subject: test 1

test
.
250 2.0.0 v25GCiXw019546 Message accepted for delivery
221 2.0.0 new.toad.com closing connection

Return-Path: 
Received: from new.toad.com (new.toad.com [209.237.225.253])
    by smtp-in.biscay.cqx.ltd.uk (8.14.4/8.14.4/Debian-2ubuntu2.1) with ESMTP id v25F9dpo009917
    for <benc@hawaga.org.uk>; Sun, 5 Mar 2017 15:09:40 GMT
Received: from dogger.cqx.ltd.uk (dynamic-91.hawaga.org.uk [90.155.94.91] (may be forged))
    by new.toad.com (8.12.9/8.12.9) with ESMTP id v25F96Xw016104
    for benc@hawaga.org.uk; Sun, 5 Mar 2017 07:09:28 -0800
Date: Sun, 5 Mar 2017 07:09:06 -0800
From: benc@hawaga.org.uk
Message-Id: <201703051509.v25F96Xw016104@new.toad.com>
Subject: test 1

02 February, 2017

Why a US dollar and a Euro are roughly the same value.

A US dollar and a Euro are roughly the same value: 1 USD is about 1 EUR, very roughly (rather than, say, 1 USD = 1000 ITL = 10^25 ZWD = 60 RUR).

There is history behind that which I've not seen presented in one place. Here is my vague understanding of it.

For a few decades before the early 1970s, the Bretton Woods system fixed USD and gold (at $35 = 1oz) and many other currencies were pegged to gold/USD.

This ended in 1971, when the USD would no longer freely converted into gold by the US government, and major world currencies became free floating.

Around that time, although at little bit before, the IMF Special Drawing Right came into existence. This was defined, at the start, to equal 1 USD, which it did until the end of Bretton Woods, but it wa. The only time I've really encountered this in real life was in small print on the back of aeroplane tickets, where compensation amounts were denominated in SDRs.

The SDR was composed of a basket of different world currencies (at time of writing, USD, EUR, CNY, JPY, GBP in defined ratios) so as the USD-value of those component currencies change, so does the USD-value of 1 SDR, rather than being fixed to the initial 1 SDR = 1 USD ratio. Over time, though, the exchange rate has stayed very roughly 1:1

In Europe, they invented the European Unit of Account which was a basket of specifically European currencies. This was scaled so that at the start, 1 unit of account was equal to 1 SDR (and so inherited the property of being roughly 1 USD). Being composed of a different based from the SDR, it varied in value with respect to both the SDR and the USD.

Next came the ECU (which was invented just before I was born), another basket of European currencies which replaced the European unit of account at 1:1

Finally, along came the Euro, an actual currency with paper notes and metal coins. This replaced the ECU again at 1:1, but again was a different basket: While the ECU basket had included GBP (British pounds), DKK (Danish crowns) and GRD (Greek Drachmas), the Euro did not include those.

So the Euro has the US dollar as its great-great-grandfather through a series of basket currencies, each branched from the previous at a 1:1 ratio.

Of course, all that 1:1 substition could have gone very differently: the Zimbabwe dollar was equivalent to a Rhodesian Dollar which was equivalent to half a Rhodesian Pound (as happened with most pound decimalisations) which replaced the Rhodesia and Nyasaland pound which replaced the Southern Rhodesian Pound, equivalent to a pound sterling - but the GBP:ZWD exchange rate at the very end was something like 1:10^25.