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

Add small Roman numerals:

$ 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];
  }
  return total;
}

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);
    }
  }
  // Read target
  // target = 0 means no target
  if (sscanf(argv[1],"%d",&target) != 1) {
    cerr << "Invalid target: " << argv[1] << endl;
    exit(0);
  }
  // Read count/weight pairs
  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:

scribble


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…