Below are the five most recent posts in my weblog. You can also see a chronological list of all posts, dating back to 1999.

This year I want to write much more about my PhD work on my blog, and here's my first effort. Most of this material has been languishing as a draft for over a year, so it's past time to get it out!


1 + 2

As part of my PhD work, I've been looking at data structures for representing stream-processing programs. The intention for our system is to take a user-supplied stream-processing program, rewrite it in order to alter its behaviour and partition it up into sub-programs which could be deployed and executed on different computers, connected together via TCP/IP.


1 * 2

To help familiarise myself with the existing system, when I started working on this I begun to explore different ways of representing both a stream-processing program and a set of interconnected, partitioned programs. Graph data structures seem like a natural fit for these, with stream-processing programs as a graph and interconnected programs as a graph-of-graphs1.


1 * (2 + 3)

There are a number of different graph libraries for Haskell. The most common approach they use for representation is "tabular": lists of edges as pairs of vertices, or similar. This isn't the only approach. One of the older, more established libraries — fgl — uses inductive types. But the one I have initially settled on is Algebra.Graph, which defines an algebra of graphs with which you can construct your instances2.

The USP for Algebra.Graph is that the four provided constructors are all total functions, so certain types of invalid graph are impossible to represent with the library (such as those where an edge does not point to a vertex).

The four basic constructors are3:

  • Vertex x, a single vertex, containing x
  • Overlay x y, which overlays one graph upon another
  • Connect x y, which connects all the vertices from Graph x to all of the vertices in Graph y.
  • Empty, for an empty graph

The Graph type implements the Num type-class, so Overlay can be abbreviated to + and connect to *. I've included some example graph definitions, encoded using + and * for brevity, and images of their corresponding renderings within this blog post.

I didn't perform an exhaustive search — nor evaluation — of all the available graph libraries. There's no definitive "right" answer to the question of which to choose: the graphs I will be dealing with are relatively small, so raw performance is not a major consideration.

So, what does a stream-processing program look like, encoded in this way? Here's a real example of a simple 5-node path graph (from here), simplified a little for clarity:

λ> foldg Empty (Vertex . vertexId) Overlay Connect graph
Overlay (Connect (Vertex 1) (Vertex 2)) (Overlay (Connect (Vertex 2)
(Vertex 3)) (Overlay (Connect (Vertex 3) (Vertex 4)) (Connect (Vertex 4)
(Vertex 5))))

Rendering it graphically is more clear:

simple 5-node stream graph


  1. Graphs are not the only data-type that could be used, of course. I've started out using a graph representation in order to bootstrap the implementation and get further along with a proof-of-concept, but there are shortcomings that might be addressed by other approaches. I'll write more about those in another blog post.
  2. By coincidence, Andrey Mokhov, the author of Algebra.Graph was a Senior Lecturer at Newcastle University, where I am a student, and was also co-author of a draft paper that was responsible for me getting interested in pursuing this work in the first place. Later, Andrey briefly became my second supervisor, but has now moved on to work for Jane Street. He remains a visiting fellow at Newcastle.
  3. Different variants of the grammar can vary these constructors to achieve different results. For example, you can forbid empty graphs by removing the Empty constructor. An adjustment to the types is made to support edge-labelling.
Tags:

Happy New Year!

It's been over two years since writing back on the Linux desktop, and I've had this draft blog post describing my desktop setup sitting around for most of that time. I was reminded of it by two things recently: an internal work discussion about "the year of the linux desktop" (or similar), and upon discovering that the default desktop choice for the current Debian release ("Buster") uses Wayland, and not the venerable X. (I don't think that's a good idea).

GNOME 3 Desktop

I already wrote a little bit about my ethos and some particulars, so I'll not repeat myself here. The version of GNOME I am using is 3.30.2. I continue to rely upon Hide Top Bar, but had to disable TopIcons Plus which proved unstable. I use the Arc Darker theme to shrink window title bars down to something reasonable (excepting GTK3 apps that insist on stuffing other buttons into that region).

Although I mostly remove or hide things, I use one extension to add stuff: Suspend Button, to add a distinct "Suspend" button. The GNOME default was, and seem to remain, to offer only a "Power off" button, which seems ludicrous to me.

I spend a lot of time inside of Terminals. I use GNOME terminal, but I disable or hide tabs, the menubar and the scrollbar. Here's one of my top comfort tips for working in terminals: I set the default terminal size to 120x32, up from 80x24. It took me a long time to realise that I habitually resized every terminal I started.

I've saved the best for last: The Put Windows GNOME shell extension allows you to set up keyboard shortcuts for moving and resizing the focussed window to different regions of the desktop. I disable the built-in shortcuts for "view splits" and rely upon "Put Windows" instead, which is much more useful: with the default implementation, once "snapped", you can't resize windows (widen or narrow them) unless you first "unsnap" them. But sometimes you don't want a 50/50 split. "Put Windows" doesn't have that restriction; but it also lets you cycle between different (user-configurable) splits: I use something like 50/50, 30/70, 70/30. It also lets you move things to corners as well as sides, and also top/bottom splits, which is very useful for comparing spreadsheets (as I pointed out eight years ago).

"Put Windows" really works marvels and entirely replaces SizeUp that I loved on Mac.

Tags:

Debian is currently conducting a vote on a General Resolution entitled Init systems and systemd. I had a few brief thoughts about the circumstances around this that I wanted to share.

I like systemd and I use it on all of my systems. That said, I have some concerns about it, in particular the way it's gradually eating up so much other systems software. The opportunity for alternatives to exist and get feedback from interested users seems important to me as a check and balance and to avoid a monoculture. Such an environment should even help to ensure systemd remains a compelling piece of software. The question that this GR poses is really whether Debian should be a place where alternatives can exist. In answering that question I am reminded of the mantra of Extinction Rebellion. I appreciate that is about a far more important topic, but it still seems pertinent: If not us, who? If not now, when?

What is Debian for, anyway? Once upon a time, from a certain perspective, it was all counter-cultural software. Should that change? Perhaps it already has. When I was more actively involved in the project, I watched some factions strive to compete with alternative distributions like Fedora. Fedora achieves a great deal, partly by having a narrow and well-defined focus. With the best will in the world, Debian can't compete at that game. And why should it? If Fedora is what you want, then Fedora is right there, go use it!

In the UK we are also about to vote in a General Election. As happens often in FPTP voting systems, the parties are largely polarized around a single issue, although one side of that issue is more factionalised than the other. And that side stands to lose out, as the vote is diluted. This Debian GR is in a similar situation, although not as bad since Debian doesn't use FPTP. But I could understand fellow developers, not as deeply invested in the issue as those who have proposed options, getting fatigued trying to evaluate them. For pro-systemd/anti-alternative folks, the choice is easy: First-choice the one (or two) positions that express that, and rank the majority under "further discussion". For those at the other pole, this strategy is risky: those folks want their transferable vote to move to the most popular option, and so must not succumb to voter fatigue.

Whatever your position, if you hold the power to vote, please take time to evaluate the options and use it.

Tags:

On Yesterday's Mary Anne Hobbs radio show she debuted a new track by Squarepusher, "Vortrack [Fracture Remix]", which you can now watch/listen to on YouTube:

This track really grabbed my attention. Later that day you you could buy it in a variety of formats and quality levels on Squarepusher's website.

One of the format/quality options was "8-bit Lossless WAV", which I thought was a joke, a poke in the eye of audiophiles. I was aware that he likely used some 8-bit instruments/equipment to write the tracks, but surely it was mixed in a more modern environment, and resampling down to 8-bit would result in something that sounded like mush.

But it seems the jokes on me; I bought the track and it's seemingly indistinguishable to the audio track on that YouTube video. And it really is 8-bit:

Input #0, wav, from 'Vortrack-001-Squarepusher-Vortrack (Fracture Remix).wav':
  Duration: 00:08:02.99, bitrate: 705 kb/s
    Stream #0:0: Audio: pcm_u8 ([1][0][0][0] / 0x0001),
    44100 Hz, 2 channels, u8, 705 kb/s

It even — losslessly — compressed down to a bitrate lower than a typical MP3:

Input #0, flac, from 'Vortrack-001-Squarepusher-Vortrack (Fracture Remix).flac':
  Duration: 00:08:02.99, start: 0.000000, bitrate: 313 kb/s
    Stream #0:0: Audio: flac, 44100 Hz, stereo, s16 (8 bit)
Tags:

Thumbnail of the poster

Thumbnail of the poster

Today the School of Computing organised a poster session for stage 2 & 3 PhD candidates. Here's the poster I submitted. jdowland-phd-poster.pdf (692K)

This is the first poster I've prepared for my PhD work. I opted to follow the "BetterPoster" principles established by Mike Morrison. These are best summarized in his #BetterPoster 2 minute YouTube video. I adapted this LaTeX #BetterPoster template. This template is licensed under the GPL v3.0 which requires me to provide the source of the poster, so here it is.

After browsing around other student's posters, two things I would now add to the poster would be a mugshot (so people could easily determine who's poster it was, if they wanted to ask questions) and Red Hat's logo, to acknowledge their support of my work.

Tags:

Older posts are available on the all posts page.


Comments