# Quaternions and Reflections

It’s well known that quaternions can be used to represent rotations in 3- and 4-dimensional space. It seems less well known that they can also be used to represent reflections and, in fact, we can derive the representation of rotations from this in a straightforward way (since all rotations can be constructed as a sequence of rotations).

We shall write quaternions `p` and `q` as:

`p = x+X`
`q = y+Y`

where `x` and `y` are scalars and `X` and `Y` are 3-vectors. Now quaternion multiplication can be defined as:

`pq = (x+X)(y+Y) = (xy - X.Y) + (xY + yX + XxY)`

with brackets in the result indicating the scalar and vector parts (and where `X.Y` and `XxY` are the usual dot and cross product). Quaternion multiplication is associative: `p(qr) = (pq)r = pqr` but not commutative (in fact, `pq = qp` just when `XxY` is zero).

We also define conjugation, the conjugate of `p`, which we write as `p'` (overbar `p̅` is conventional, but I think is harder to read onscreen), is `p` with the vector part negated:

`p' = x-X`

Combining multiplication and conjugation we have:

`pq' = (x+X)(y-Y) = (xy + X.Y) + (-xY + yX - XxY)`
`qp' = (y+Y)(x-X) = (xy + X.Y) + (+xY - yX + XxY)` (since `YxX = -XxY`)

and adding both equations, the vector parts cancel and we have:

`pq' + qp' = 2(xy + X.Y)`

But `xy + X.Y` is just the dot product of `p` and `q`, considered as normal 4-dimensional vectors, so we can write:

`pq' + qp' = 2p.q`

This nicely relates quaternion algebra directly to the geometry of 4-space and we can now rewrite expressions using dot product purely in terms of quaternion arithmetic (quaternion addition and subtraction and operations with scalars are the same as for ordinary vectors, of course).

So, the usual definition, valid in any dimension, for a reflection in a (hyper)plane with normal `n` (assumed to be a unit vector) is:

`p → p - 2(p.n)n`

we can rewrite as:

`p → p - (pn' + np')n = p - pn'n - np'n = p - p - np'n = -np'n`

ie. reflection of `p` in `n` is just `-np'n`. Note that a 4-dimensional reflection is in a 3-dimensional hyperplane (or perhaps it is clearer to think of the reflection as being along the normal vector), so vectors parallel to the normal are reversed, vectors orthogonal to the normal (ie. in the normal hyperplane) are unchanged.

Interestingly, the relation `pq' + qp' = 2p.q` is also true for complex numbers (with the usual complex multiplication and conjugation) and we have exactly the same represention for a 2-dimensional reflection, but we can further simplify using the commutativity of complex multiplication:

`z → z - 2(z.n)n = -nz'n = -n²z'`

Returning to quaternions, we can combine two reflections, with normals n and m, say, to get a (simple) rotation:

`p → -m(-np'n)'m = mn'pn'm`

and geometry tells us that the rotation is about an angle twice that between the the planes of reflection.

In 4-space, this rotation can be thought of as in the plane spanned by `n` and `m` (ie. vectors in that plane rotate to other vectors in the plane), or around an axis of another plane, orthogonal to the first, in fact the intersection of the two hyperplanes normal to `n` and `m`.

A general 4-dimensional rotation needs 4 reflections:

`p → j(l(mn'pn'm)'l)'j = jl'mn'pn'ml'j`

and we lose any simple relation between the left and right quaternion – in fact `p → qpr` is a rotation for any unit quaternions `q` and `r` (an interesting case arises if `q` or `r` is the identity – a Clifford translation).

We can derive expressions for reflections and rotations in 3-space from this, with 3-space points represented as pure quaternions, ie. with zero scalar part, so if `n` and `m` are pure, then `n' = -n` and `nm = (mn)'`

A reflection now is:

`p → -np'n = npn`

and a rotation is:

`p → mn'pn'm = mnp(mn)'`

and we have the usual definition of a rotation in 3-space:

`p → qpq'`

Representing rotations as compositions of reflections also has practical uses. Consider the problem of finding a rotation to take a vector `p` to a vector `q` (assumed to both be of unit length) – we can do this as two reflections, first reflect `p` in the (hyper)plane normal to `p+q`, this aligns `p` with `q`, but in the opposite direction, so reflect again in the plane orthogonal to `q` (it may help to sketch a picture – the construction makes sense in 2 or more dimensions). Using the 3-space formulation above, and the fact that `qq = -1` for pure `q`, we have:

`p → qpq'` where `q = -q(p+q)/|p+q| = (-qp-qq)/|p+q| = (1-qp)/|p+q|`

and since we know that the result is of unit length, we can just use:

`p → normalize(1-qp)`

(with a special case when `qp = 1`, ie when `q = -p`, when the rotation is not uniquely defined).

Also, if we have two vectors `x0`,`y0` and wish to rotate them to new vectors `x1`,`y1` (assume `|x0| = |x1|, |y0| = |y1|`, and `|x0-y0| = |x1-y1|`, first reflect `x0` to `x1` along `x1-x0` (ie. in the plane orthogonal to `x1-x0`), this also reflects `y0` to a new point `y2`, but we can then reflect `y2` to `y1` along `y2-y1` (this leaves `x1` unchanged as it is equidistant from from `y1` and `y2`):

`n = x1-x0`
`y2 = y1 - 2(y1.n/n.n)n`
`m = y2-y1`
`r = normalize(mn)`

There is always a unique rotation, but two special cases are: if `x0 = x1`, then swap `x0` with `y0` and `x1` with `y1` (if `y0 = y1` as well, there is nothing to do); and if `y2 = y1`, then reflect along `cross(x1,y1)` rather than y2-y1.

A similar construction is also possible in 4-dimensional space: 3 point pairs define a general rotation (the first three reflections map the 3 points, the last reflection, in the hyperplane containing those points, ensures we have a proper rotation).

Much of this is taken from Coxeter’s 1946 paper, “Quaternions and Reflections”, https://www.jstor.org/stable/2304897, which of course goes into much more depth and with much greater rigour.

# Markov Computation

Markov computation is an attractively simple definition of universal computability.

A program is a list of rewrite rules:

```xxx => yyy
```

or a terminal rule:

```xxx =>. yyy
```

where `xxx` and `yyy` are arbitrary strings over some alphabet.

A computation takes a string over that alphabet and repeatedly rewrites it until termination: each rewrite uses the first rule with a LHS occuring anywhere in the string, which is then replaced by the RHS of the rule. If the rule is terminal the computation stops, it also stops if no rule matches.

Since I had a need to brush up on my Perl recently, I came up with this:

```#!/usr/bin/perl -w
use strict;

my \$line = shift @ARGV;
my @rules;

while (<>) {
if (/^\s*(\S*)\s*=>(\.?)\s*(\S*)/) {
push @rules,[\$1,length \$1,\$3,\$2 ne ""];
}
}

print "\$line\n";
for (my \$i = 0; \$i < @rules; ) {
my (\$lhs,\$len,\$rhs,\$term) = @{\$rules[\$i++]};
my \$ix = index \$line,\$lhs;
if (\$ix >= 0) {
substr(\$line,\$ix,\$len) = \$rhs;
print "\$line\n";
\$i = \$term?@rules:0;
}
}
```

The line to rewrite is given as a command line argument and the program is read from input (either stdin or from files given on the command line). We use some regexps to match the program lines and, while it’s tempting to use regexp rewriting for running the program, we want to avoid any string characters being interpreted specially – we can use `quotemeta` for this but here we just use the non-regexp string operators (note the slightly wacky Perl use of `substr` as an l-value).

Now we have our evaluator, let’s write some programs:

Here is a multiplication program:

```\$ cat mult.mkv
x1 => 1x
x| => |1
x => |1
+| => |
+1 => 1+x
1* => *+
*1 => *
*| =>

\$ ./markov '111*11' mult.mkv
111*11
11*+11
11*1+x1
11*1+1x
11*1+1|1
11*11+x|1
11*11+|11
11*11|11
1*+11|11
1*1+x1|11
1*1+1x|11
1*1+1|111
1*11+x|111
1*11+|1111
1*11|1111
*+11|1111
*1+x1|1111
*1+1x|1111
*1+1|11111
*11+x|11111
*11+|111111
*11|111111
*1|111111
*|111111
111111
```

```\$ cat roman.mkv
# Final change to subtractive form
@X => X@
@IIII =>. IV
@VIIII =>. IX
@ =>.
# Initial expansion of subtractive form
IV => IIII
IX => VIIII
# Simplification
IIIII => V
VV => X
# Rules for *
I*X => XI*
I*V => VI*
V*X => XV*
* =>
# Move from LHS to RHS
I+I => II
V+I => VI
V+V => X
X+ => X
I+ => +I*
V+ => +V*
# Go to finish
+ => @

\$ ./markov I+II+III+IV+V+VI+VII+VIII+IX+X < roman.mkv
I+II+III+IV+V+VI+VII+VIII+IX+X
I+II+III+IIII+V+VI+VII+VIII+IX+X
I+II+III+IIII+V+VI+VII+VIII+VIIII+X
III+III+IIII+V+VI+VII+VIII+VIIII+X
IIIIII+IIII+V+VI+VII+VIII+VIIII+X
VI+IIII+V+VI+VII+VIII+VIIII+X
VIIIII+V+VI+VII+VIII+VIIII+X
VV+V+VI+VII+VIII+VIIII+X
X+V+VI+VII+VIII+VIIII+X
X+XI+VII+VIII+VIIII+X
XXI+VII+VIII+VIIII+X
XX+I*VII+VIII+VIIII+X
XX+VI*II+VIII+VIIII+X
XX+VIII+VIII+VIIII+X
XXVIII+VIII+VIIII+X
XXVII+I*VIII+VIIII+X
XXVII+VI*III+VIIII+X
XXVII+VIIII+VIIII+X
XXVI+I*VIIII+VIIII+X
XXVI+VI*IIII+VIIII+X
XXVI+VIIIII+VIIII+X
XXVI+VV+VIIII+X
XXVI+X+VIIII+X
XXVI+XVIIII+X
XXV+I*XVIIII+X
XXV+XI*VIIII+X
XXV+XVI*IIII+X
XXV+XVIIIII+X
XXV+XVV+X
XXV+XX+X
XXV+XXX
XX+V*XXX
XX+XV*XX
XX+XXV*X
XX+XXXV*
XX+XXXV
XXXXXV
```

And here is one for checking the Collatz conjecture:

```\$ cat collatz.mkv
>11 => 1>
>1 => <111
> =>
1< => <111111
< => 1
11 => >11

\$ ./markov 11111 collatz.mkv
11111
>11111
1>111
11>1
11<111
1<111111111
1111111111111111
1>11111111111111
11>111111111111
111>1111111111
1111>11111111
11111>111111
111111>1111
1111111>11
11111111>
11111111
>11111111
1>111111
11>1111
111>11
1111>
1111
>1111
1>11
11>
11
>11
1>
1
```

See the 1st edition of Mendelson’s excellent book on Mathematical Logic for a full treatment, including a demonstration of equivalence with other notions of computability.

# Subbag Enumeration

A bag or multiset is just a map from some base set X to the natural numbers, so we can represent such a bag by a sequence of (non-negative) integers. Subbags are defined in the obvious way (and if s is subbag of t, t is a superbag of s). Given a subbag s of m, we can find the next subbag (in reverse lexicographic order) with this function:

```bool nextbag(vector<int> &s,
const vector<int> &m,
size_t start = 0)
{
for (size_t i = start; i < s.size(); i++) {
if (s[i] == m[i]) {
s[i] = 0;
} else {
s[i]++;
return true;
}
}
return false;
}
```

This sets the subsequence [start..] of s to the (reverse) lexicographically next sequence. m gives maximum values for each field of s and we return false if we have cycled back round to the zero sequence. Note that if m[i] < 0 then effectively there is no maximum value for each element.

We might also want to skip from s to the next subbag that is not a superbag of s. This is accomplished by:

```bool nextnonsuper(vector<int> &s, const vector<int> &m)
{
for (size_t i = 0; i < s.size(); i++) {
if (s[i] != 0) {
s[i] = 0;
return nextbag(s,m,i+1);
}
}
return false;
}
```

Here we see why we wanted the start parameter in nextbag. For example, we go from:

`[0,0,0,3,4,...] => [0,0,0,0,5,...]`

Given f: bag -> A where A is an ordered set and where f is monotonic (if s is a subbag of t, then f(s) <= f(t)), if we want to find all (sub)bags where f(s) <= x, we can use nextnonsuper to skip some of the enumeration:

```while (true) {
if (f(s) >= t) s = nextnonsuper(s)
else s = nextbag(s)
...
}
```

For an example, we can use a weighted sum over the bag elements (we will assume that the weights are positive).

```int weights(const vector<int> &s, const vector<int> &w)
{
int total = 0;
for (size_t i = 0; i < s.size(); i++) {
total += s[i]*w[i];
}
}
```

and we can add some boiler plate to make the whole thing into a nice standalone application:

```// Print out our vector, include weights if required
// Optionally print in reverse order
void print(const vector<int> &s,
const vector<int> *w = NULL,
bool printreverse = false)
{
int sz = s.size();
for (int i = 0; i < sz; i++) {
int index = printreverse?sz-i-1:i;
cout << s[index];
if (w != NULL) cout << ":" << (*w)[index];
cout << (i < sz-1?" ":"\n");
}
}

int main(int argc, char *argv[])
{
int target;    // The sum we are aiming for
vector<int> s; // Where we build the sequence
vector<int> m; // The number of each items available
vector<int> w; // The weight of each item
bool printreverse = false; // Print sequences in reverse
bool printweight  = false; // Print the weights as well
bool printless    = false; // Print sequences less than target
bool printgreater = false; // Print those greater than target

// Crude but effective argument processing
while (argv[1][0] == '-') {
if (strcmp(argv[1],"-r") == 0) {
printreverse = true;
argv++; argc--;
} else if (strcmp(argv[1],"-l") == 0) {
printless = true;
argv++; argc--;
} else if (strcmp(argv[1],"-g") == 0) {
printgreater = true;
argv++; argc--;
} else if (strcmp(argv[1],"-w") == 0) {
printweight = true;
argv++; argc--;
} else {
cerr << "Invalid flag: " << argv[1] << endl;
exit(0);
}
}
// target = 0 means no target
if (sscanf(argv[1],"%d",&target) != 1) {
cerr << "Invalid target: " << argv[1] << endl;
exit(0);
}
for (int i = 2; i < argc; i++) {
int a,b;
if (sscanf(argv[i],"%d:%d",&a,&b) != 2) {
cerr << "Invalid arg: " << argv[i] << endl;
exit(0);
}
m.push_back(a);
w.push_back(b);
}
// Initialize result sequence.
s.resize(m.size());
while(true) {
int total = weights(s,w);
// Print result if desired
if (target == 0 ||
total == target ||
(total < target && printless) ||
(total > target && printgreater)) {
print(s, printweight?&w:NULL, printreverse);
}
if (target > 0 && total >= target) {
// Have hit or exceeded target, so skip superbags
if (!nextnonsuper(s,m)) break;
} else {
if (!nextbag(s,m)) break;
}
}
}
```

Compiling all this as bagenum.cpp, we can now do some enumerations. All the ways to make 5 from the bag {1,1,1,2,2,3}:

```\$ ./bagenum 5 3:1 2:2 1:3 3 1 0 1 2 0 2 0 1 0 1 1```

We can specify a target of 0 to get all the subbags of the input, and the -w flag prints the weight out as well:

```\$ ./bagenum -w 0 3:1 2:2 0:1 0:2 1:1 0:2 2:1 0:2 3:1 0:2 0:1 1:2 1:1 1:2 2:1 1:2 3:1 1:2 0:1 2:2 1:1 2:2 2:1 2:2 3:1 2:2```

We can enumerate bitstrings with a given number of bits set

```\$ ./bagenum 2 1:1 1:1 1:1 1:1 1 1 0 0 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 0 0 1 1```

Or with at most a given number set:

```\$ ./bagenum -l 2 1:1 1:1 1:1 1:1 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 1 1 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 1```

Or the ways of rolling 4 with 3 dice numbered 0-5 – much the same as rolling 7 with 3 normal dice (the -r parameter prints the results in reverse order, ie. normal lexicographic order):

```\$ ./bagenum -r 4 5:1 5:1 5:1 0 0 4 0 1 3 0 2 2 0 3 1 0 4 0 1 0 3 1 1 2 1 2 1 1 3 0 2 0 2 2 1 1 2 2 0 3 0 1 3 1 0 4 0 0 ```

All this works quite nicely with unlimited multiplicities, provided we also set an upper bound, so we can enumerate the solutions to the classic Polya problem of the ways to make 50c with usual US coins (50 as it happens):

```\$ ./bagenum -w 50 -1:1 -1:5 -1:10 -1:25 -1:50 50:1 0:5 0:10 0:25 0:50 45:1 1:5 0:10 0:25 0:50 40:1 2:5 0:10 0:25 0:50 35:1 3:5 0:10 0:25 0:50 30:1 4:5 0:10 0:25 0:50 25:1 5:5 0:10 0:25 0:50 20:1 6:5 0:10 0:25 0:50 15:1 7:5 0:10 0:25 0:50 10:1 8:5 0:10 0:25 0:50 5:1 9:5 0:10 0:25 0:50 0:1 10:5 0:10 0:25 0:50 40:1 0:5 1:10 0:25 0:50 35:1 1:5 1:10 0:25 0:50 ...```

Finally, the -g flag prints the subbags found that are greater than the target – but only the ones all of whose subbags are less than the target (if you see what I mean):

```./bagenum -g -w 8 1:2 1:3 1:4 1:5 1:2 1:3 1:4 0:5 0:2 1:3 0:4 1:5 0:2 0:3 1:4 1:5```

(So the complement of subbags are the ones whose sum is less than or equal to a target but every superbag is greater, as in the classic knapsack problem).

Once again, this works fine with unlimited multiplicities:

```\$ ./bagenum -g -w 8 -1:2 -1:3 -1:4 -1:5 4:2 0:3 0:4 0:5 3:2 1:3 0:4 0:5 1:2 2:3 0:4 0:5 0:2 3:3 0:4 0:5 2:2 0:3 1:4 0:5 1:2 1:3 1:4 0:5 0:2 2:3 1:4 0:5 0:2 0:3 2:4 0:5 2:2 0:3 0:4 1:5 0:2 1:3 0:4 1:5 0:2 0:3 1:4 1:5 0:2 0:3 0:4 2:5```

All in all, a nice little combinatorial Swiss Army knife and useful when trying to understand the stuff in:

http://www.amazon.co.uk/The-Computer-Programming-Volume-Fascicle/dp/0201853949/

for example (I like the TAOCP fascicles, they are much more convenient to read in the bar, in the bath or on the bus). This one has lots more about this sort of problem: special cases with more efficient solutions, as well as more general algorithms for more general combinatorial problems.

# Finally, a new laptop

It was high time I got a new laptop, the old Dell Inspiron 2200 had done quite well over the years, but was starting to fall apart and increasingly was just not up to the demands placed on it. I spent a while mulling over the options (don’t need too much raw power, but want some reasonable features), and ended up going for an Acer v5-171, this is the entry level model with the Core i3 processor, some sort of Ivy Bridge, whatever these silly names mean, more than adequate for my needs – doesn’t have the AES encryption I’d get with an i5, but I can probably live without that, and it doesn’t have Turbo Boost, but I don’t even know what that is. What it does have is a 0.5TB disk, 6GB of memory, and is clocked at 1.9GHz. There are 3 USB ports, one is USB 3.0, and a dinky little card reader on the front that I didn’t notice for a while. The keyboard is small, but quite usable, in fact it’s only a little narrower than the keyboard on my old Inspiron. It’s got those modern, flat keys that I didn’t think I liked, but actually, it’s quite pleasant to type on.

Here’s what Intel say about the CPU:

http://ark.intel.com/products/72057/Intel-Core-i3-3227U-Processor-3M-Cache-up-to-1_90-GHz

And what PCWorld say about the laptop. I wasn’t swayed by the “As Advertised on TV”, I hardly ever watch it, and in fact, the spec is better than what is describe here:

http://www.pcworld.co.uk/gbuk/acer-aspire-v5-171-11-6-laptop-silver-19414897-pdt.html#longDesc

The main alternative was the Asus S200 with a touch screen, though I hate fingerprints, and with either a rather inferior processor or a rather superior price.

I was intending to have a dual booting system with the Windows 8 it came preinstalled with (I bought it for the handsome price of £329 from the local PC World, who tried to hit me for an extra £30 for their setup service, I explained that I really didn’t want or need that, or the extended warranty, or a copy of Office, just the computer please… The helpful assistant Maya was very pleasant about all this and worked out that she should tick the “No Marketing” box without having to ask) but it didn’t take long to give up on that idea; I can’t say my quick sojourn round Windows 8 filled me with much joy, and I’ve been happily using Linux (and Android) for everything for some time now, so after spending 10 mins or so failing to work out how to set up UEFI dual booting (or even how to boot off the Live USB stick in UEFI mode), I flipped over to BIOS Legacy Mode on and told Ubuntu (12.10) to wipe the disk with extreme prejudice. I used to like playing around with partitioners, mulling over how big my swap partitition should be, or if I should keep system files and user data separate, these days I just let the installer get on with it.

After that, pretty much everything just went through just as it should. A deja vu moment of having to add “acpi_backlight=vendor” to the boot options to get the brightness control to work (one day I’ll find out what it means), but apart from that, everything works just fine, straight out of the box.

The screen is a little smaller (physically) than I’m used to, everything these days seems to be 1366×768, but in this case it’s all within a 10.1″ display, so the detail is lovely and crisp, but some things are a bit small for my poor old eyes so some investigation of accessibility options is called for (I recommend the NoSquint Firefox extension). There is a pixel stuck at red (played with `lcdnurse` to no avail) and the touchpad is a bit sticky (seems better after fiddling with the sensitivity). The sound is pretty poor (though we now seem to have a Spinal Tap-style volume control that goes way beyond 100%, which helps a little). Haven’t tried headphones yet.

Assuming the Power Statistics tool can be trusted, it uses 4W with screen off, 6W with minimum visible brightness level, going up to 8W for a normal level and nearly 10 on maximum. Heavy graphics & CPU use pushes things up to 16 or 17W. Wifi doesn’t seem to make much difference. The battery is reckoned to be 36Wh, so that should be a little over 4 hours, not much by modern standards, but enough for my modest needs. Not too much of a heat problem, the base of the laptop is a little warm but nothing too uncomfortable.

Out of curiosity, I investigated UEFI a bit more: to fiddle with any of the secure boot options in the BIOS you have to set the “Supervisor Password” it seems (I suppose that should have been obvious – initially, it’s the only modifiable field on the secure boot screen). Having done this, in the same BIOS screen, one can select the .efi files from the Ubuntu installation USB stick to be bootable from (/EFI/BOOT/ seems to be required directory) and then, mirabile dictu, we can boot into Live USB installation. I tried “Boot Repair” but got a warning about not having an EFI partition and would I like to add one (presumably if I had done the original installation in UEFI mode, this would have been created for me, I’m not sure I can really be bothered right now though).

Resetting to Legacy Mode and rebooting, we get back to the original installation and all is still well (it always amazes me when things still work after fiddling around, from the time I pulled the CPU out of my Sinclair Spectrum and put it back, and it Still Worked – I had less appreciation then of how easy it is to break the pins on DIL ICs). Only thing not working is that stuck pixel (not visible with light colours though) and though Bluetooth looks like its working, it won’t detect my phone. I wonder if this is related to this in dmesg:

```[ 0.952921] WARNING: at /build/buildd/linux-3.5.0/arch/x86/mm/ioremap.c:102 __ioremap_caller+0x335/0x380() [ 0.952925] Hardware name: V5-171 [ 0.952928] Modules linked in: [ 0.952932] Pid: 1, comm: swapper/0 Not tainted 3.5.0-17-generic #28-Ubuntu [ 0.952935] Call Trace: [ 0.952943] [] warn_slowpath_common+0x7f/0xc0 [ 0.952948] [] warn_slowpath_null+0x1a/0x20 [ 0.952952] [] __ioremap_caller+0x335/0x380 [ 0.952958] [] ? bgrt_init+0x47/0x126 [ 0.952964] [] ? acpi_get_table_with_size+0x5f/0xbe [ 0.952969] [] ? acpi_hed_init+0x30/0x30 [ 0.952974] [] ioremap_nocache+0x17/0x20 [ 0.952978] [] bgrt_init+0x47/0x126 [ 0.952984] [] do_one_initcall+0x12a/0x180 [ 0.952990] [] kernel_init+0x140/0x1c9 [ 0.952995] [] ? loglevel+0x31/0x31 [ 0.953000] [] kernel_thread_helper+0x4/0x10 [ 0.953005] [] ? start_kernel+0x3c4/0x3c4 [ 0.953009] [] ? gs_change+0x13/0x13 [ 0.953015] ---[ end trace d285ec97245f6911 ]--- [ 0.953064] GHES: HEST is not enabled! ```

That last one sounds like one of those cryptic lovers notes that used to be in the classified ads of The Times.

I love boot messages:

```[ 9.573227] cfg80211: Calling CRDA to update world regulatory domain # I expect they were staying up late, waiting for that call. [ 9.574528] pci 0000:00:00.0: >detected 131072K stolen memory # I thought stealing RAM had gone out of fashion, now it's so cheap [ 9.980692] init: failsafe main process (758) killed by TERM signal # Doesn't sound very failsafe ```

Enough lame attempts at computer humour, back to the laptop. Being an old stick in the mud, this is my first time with Ubuntu 12.x with Unity and all that. I’m not convinced I want my laptop to look like a phone, but I’m prepared to go with it for the moment and give it my best shot, though it’s tempting to just find whatever the modern equivalent of TWM is and use that. There are some nice features for sure, it seems that now Thunderbird runs in the background because on rebooting I find an envelope icon that it turns out is telling me that Gaylord Madrid is now fully funded: go Gaylord, go (if you’ve got a few bob to spare, I recommend parking it with http://www.lendwithcare.org). And I’ve just discovered that the Windows key (which Linux seems to be calling Super – it would be nice to have a real Space Cadet keyboard of course) actually does something useful. The trackpad of the Acer is a bit of weak point, so making more use of keyboard shortcuts could be a good idea – as a long-time Emacs user, I really ought to get used to using Ctrl-T in Firefox to start up a new tab, for example.

So, pretty happy all in all, a nice bit of kit, some shortcomings, but we aren’t exactly high end here so that’s to be expected. Next time I’ll know what to do with UEFI, but going single boot from the start has got to be the right thing.

For the record:

```\$ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 Thread(s) per core: 2 Core(s) per socket: 2 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 58 Stepping: 9 CPU MHz: 779.000 BogoMIPS: 3791.51 Virtualisation: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 3072K NUMA node0 CPU(s): 0-3```

``` \$ cat /proc/cpuinfo processor : 0 vendor_id : GenuineIntel cpu family : 6 model : 58 model name : Intel(R) Core(TM) i3-3227U CPU @ 1.90GHz stepping : 9 microcode : 0x15 cpu MHz : 779.000 cache size : 3072 KB physical id : 0 siblings : 4 core id : 0 cpu cores : 2 apicid : 0 initial apicid : 0 fpu : yes fpu_exception : yes cpuid level : 13 wp : yes flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer xsave avx f16c lahf_lm ida arat epb xsaveopt pln pts dtherm tpr_shadow vnmi flexpriority ept vpid fsgsbase smep erms bogomips : 3791.51 clflush size : 64 cache_alignment : 64 address sizes : 36 bits physical, 48 bits virtual power management: \$ glxinfo | grep -i opengl OpenGL vendor string: Intel Open Source Technology Center OpenGL renderer string: Mesa DRI Intel(R) Ivybridge Mobile OpenGL version string: 3.0 Mesa 9.0.2 OpenGL shading language version string: 1.30 \$ lspci 00:00.0 Host bridge: Intel Corporation 3rd Gen Core processor DRAM Controller (rev 09) 00:02.0 VGA compatible controller: Intel Corporation 3rd Gen Core processor Graphics Controller (rev 09) 00:14.0 USB controller: Intel Corporation 7 Series/C210 Series Chipset Family USB xHCI Host Controller (rev 04) 00:16.0 Communication controller: Intel Corporation 7 Series/C210 Series Chipset Family MEI Controller #1 (rev 04) 00:1a.0 USB controller: Intel Corporation 7 Series/C210 Series Chipset Family USB Enhanced Host Controller #2 (rev 04) 00:1b.0 Audio device: Intel Corporation 7 Series/C210 Series Chipset Family High Definition Audio Controller (rev 04) 00:1c.0 PCI bridge: Intel Corporation 7 Series/C210 Series Chipset Family PCI Express Root Port 1 (rev c4) 00:1c.1 PCI bridge: Intel Corporation 7 Series/C210 Series Chipset Family PCI Express Root Port 2 (rev c4) 00:1c.2 PCI bridge: Intel Corporation 7 Series/C210 Series Chipset Family PCI Express Root Port 3 (rev c4) 00:1d.0 USB controller: Intel Corporation 7 Series/C210 Series Chipset Family USB Enhanced Host Controller #1 (rev 04) 00:1f.0 ISA bridge: Intel Corporation HM77 Express Chipset LPC Controller (rev 04) 00:1f.2 SATA controller: Intel Corporation 7 Series Chipset Family 6-port SATA Controller [AHCI mode] (rev 04) 00:1f.3 SMBus: Intel Corporation 7 Series/C210 Series Chipset Family SMBus Controller (rev 04) 03:00.0 Network controller: Atheros Communications Inc. AR9462 Wireless Network Adapter (rev 01) 04:00.0 Ethernet controller: Broadcom Corporation NetLink BCM57785 Gigabit Ethernet PCIe (rev 10) 04:00.1 SD Host controller: Broadcom Corporation NetXtreme BCM57765 Memory Card Reader (rev 10) ```

```\$ lsusb Bus 001 Device 002: ID 8087:0024 Intel Corp. Integrated Rate Matching Hub Bus 002 Device 002: ID 8087:0024 Intel Corp. Integrated Rate Matching Hub Bus 001 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub Bus 002 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub Bus 003 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub Bus 004 Device 001: ID 1d6b:0003 Linux Foundation 3.0 root hub Bus 001 Device 003: ID 064e:e330 Suyin Corp. ```

# Graphics Bugs

One of the nice things about graphics programming is that even the bugs can be fun, here’s a picture I made earlier, it wasn’t quite what I’d intended, and I don’t think it’s going to be in the Tate Modern any time soon, but I rather like it:

# Yin Yang

An old puzzle about call/cc in Scheme. Don’t know the original source, possibly that place with the dome near the Charles River:

```(let* ((yin ((lambda (cc)
(display #\@) cc)
(call-with-current-continuation (lambda (c) c))))
(yang ((lambda (cc)
(display #\*) cc)
(call-with-current-continuation (lambda (c) c)))))
(yin yang))
```

First thing is to simplify somewhat, we don’t seem to lose anything essential by getting rid of the outer lambdas:

```(let ((yin (call-with-current-continuation (lambda (c) c))))
(display #\@)
(let ((yang (call-with-current-continuation (lambda (c) c))))
(display #\*)
(yin yang)))
```

OK, still seems to work. Let’s try and work this out informally – yin is bound to a continuation that sets yin to its argument, prints something, then binds yang to a continuation that prints something else and whatever the first continuation was applied to is applied to the argument of the second continuation. Hmmm, so far, as clear as mud, sounds like that Marx brothers sketch.

Let’s try and write down what the continuations are, to do that properly we need to convert to continuation passing style, CPS. Every function has an extra argument, its continuation and instead of returning a value, it calls its continuation on the value in a tail call. So, without further ado:

```(define (id x) x)
(define ((id2 x) k) (k x))
(define (((throw k) x) k2) (k x))
(define ((ccc f) k) ((f (throw k)) k))

((ccc id2)
(lambda (k)
(display #\@)
((ccc id2)
(lambda (x)
(display #\*)
((k x) id)))))
```

Here, `id2` is a CPS-style identity function – it just applies the continuation `k` to its main argument `x`. `throw` can be used to replace the current continuation, `ccc` is our CPS style `call-with-current-continuation`, and uses `throw` to replace the current continuation.

`id` is our ‘top-level’ continuation, it doesn’t really matter what it is – it doesn’t ever get called.

Still as clear as mud, simplifying a bit more might help. Let’s give names to the continuation functions and pull them out to the top level as combinators:

```(define ((g k) x)
(display #\*)
((k x) id))

(define (f k)
(display #\@)
((ccc id2) (g k)))

((ccc id2) f)
```

Now, running through our definition of `ccc`, we get:

```((ccc id2) k) => ((id2 (throw k)) k) => (k (throw k))
```

Sort of what we expect, we call the current continuation with the current continuation (wrapped in `throw`, which essentially converts a continuation into a normal function that itself takes a continuation as a parameter). So now we have:

```(define ((g k) x)
(display #\*)
((k x) id))

(define (f k)
(display #\@)
((g k) (throw (g k))))

(f (throw f))
```

Maybe some more inlining would help:

```(define ((g k) x)
(display #\*)
((k x) id))

(define (f k)
(display #\@)
(display #\*)
((k (throw (g k))) id))

(f (throw f))
```

Or maybe we can get some insight by omitting the IO and just writing:

```(define ((g k) x) ((k x) id))
(define (f k) ((g k) (throw (g k))))
(f (throw f))
```

Now:

```(f (throw f)) =>
((g (throw f)) (throw (g (throw f)))) =>
(((throw f) (throw (g (throw f)))) id) =>
(f (throw (g (throw f)))) =>
((g (throw (g (throw f)))) (throw (g (throw (g (throw f)))))) =>
(((throw (g (throw f))) (throw (g (throw (g (throw f)))))) id) =>
((g (throw f))(throw (g (throw (g (throw f)))))) =>
(((throw f)(throw (g (throw (g (throw f)))))) id) =>
(f (throw (g (throw (g (throw f)))))) => ...
```

I’m sure you get the picture.

We can do a similar evaluation more succinctly by defining:

```Tkxy = kx
Gkx = kxI
Fk = Gk(T(Gk))
```

And now:

```F(TF) =>
G(TF)(T(G(TF)) => TF(T(G(TF))I =>
F(T(G(TF))) =>
G(T(G(TF)))(T(G(T(G(TF))))) => T(G(TF))(T(G(T(G(TF)))))I =>
G(TF)(T(G(T(G(TF))))) => TF(T(G(T(G(TF)))))I =>
F(T(G(T(G(TF))))) => ...
F(T(G(T(G(T(G(TF))))))) => ...
```

All the Ts and Is do here is cancel one another out, so we can define, even more succinctly (and inlining G a little):

```Fk = k(Gk)
Gkx = kx
```

```FF =>
F(GF) => GF(G(GF)) =>
F(G(G(F))) => G(G(F))(G(G(G(F)))) => G(F)(G(G(G(F)))) =>
F(G(G(G(F)))) => ...
...
```

It’s curious that here, `F = λk.k(Gk) = λk.k(λx.kx)` and `λx.kx` is eta-convertible to just `k`, so `FF = (λk.k(λx.kx))(λk.k(λx.kx))` is eta-convertible to `Ω = YI = (λx.xx)(λx.xx)`.

Returning to scheme, we can do a similar trick and get:

```(define ((g k) x) (display #\*) (k x))
(define (f k) (display #\@) ((g k) (g k)))
(f f)
```

or inlining the first call to g in f:

```(define (f k) (display #\@) (display #\*) (k (g k)))
```

Now our evaluation is:

```(f f) => (f (g f)) =>
(f (g f)) => ((g f) (g (g f))) =>
(f (g (g f))) => ...
```

Simplifying further, we end up with the equivalent program:

```((lambda(k)(display #\@)(display #\*)(k (lambda(x)(display #\*)(k x))))
(lambda(k)(display #\@)(display #\*)(k (lambda(x)(display #\*)(k x)))))
```

and if that isn’t cute, I don’t know what is…