Random Lists

As kin has support for pattern matching and sequences at its heart, it's natural to formulate a random number generator as a generator of a sequence of random numbers.

For example, this is the same linear congruent shift register as used in java.util.Random:

    type lcsr ( seed : uint64 ) : seq [ uint32 ]
        def head : uint32 => uint32 ( self.seed >> 16 )
        def tail : lcsr => lcsr ( ( self.seed * 0x0005_deec_e66d + 0x0000_0000_000b ) & 0xffff_ffff_ffff )
    

You can wrap it in an actor if you want the same behaviour as a random function with hidden state:

    type @actor random_source ( sequence : seq[uint32] )
        def next_uint32 ( self ) : uint32
            let r = self.sequence.head
            self become ( sequence = self.sequence.tail )
            => r
        
        def next_real64 ( self ) : real64 
            => real64 ( natural ( self.next_uint32() ) ) / real64 ( natural ( uint32.max ) )

But you couldn't optimise matching on the value reported by a random function like you can with a pure sequence:

        let rnd_seq = lcsr ( 0x12345 )
        
        match rnd_seq
            0x00000001 :: 0xadfc5fc8 :: 0x22222222 :: 0x33333333 :: _ =>
                out <- "match one" <- endl
            0x00000001 :: 0xadfc5fc8 :: 0x9d1a5de6 :: 0xf6b685cf :: _ =>
                out <- "match two" <- endl
            _ => 
                out <- "no match" <- endl

The cons'd patterns are compiled to combinations of calls to seq.head or seq.tail. The first two matches get combined as the first couple of terms in the pattern are the same; if seq.head or seq.tail were not pure functions, the second match case would fail as the hidden state would change.


Tim Bray describes using this technique is "a sideways dance" in Haskell. I've always found Haskell a bit too 'stiff' and like to 'feel the bits between my toes' too much for it, but compared to the amount of messing around Java has to do with atomic longs (JDK7) or synchronized methods (GNU classpath) in the implementation of the random source, and then as an Iterable<Integer> if you want a sequence of random numbers, it doesn't seem too bad. In the Java case, either the runtime has to deduce that the interlocks are not required and remove them, or it has to process them; if the code is used in more than one place you may have to have more than one machine code compiled form of the method, or fall back to conservative locking always. For a pure sequence, no interlocks are required. Wrapping a sequence in a actor ( or a lazy list in a monad in Haskell ) gives you hidden variable behaviour if you want it without polluting the code of the sequence generator with synchronisation primitives.

Language-level Immutablity and Shared Memory Concurrency

I've been a fan of Bartosz Milewski’s Programming Café ( or possibly Bartosz Milewski’s Programming Caff; I'm not sure if lack of an accent implies greasy chips and tea outside of the UK ). He's exploring the options of applying the leverage of type checking to concurrency problems within shared-memory systems. In a different camp, there's the Erlang crowd, typified by Steve Vinoski which says that language-level immutability and message passing is the way to go. A third perspective, probably closer to what I would like to see, are CSP based approaches such as Limbo and stackless Python, which are shared nothing and use channels to pass messages by value. The channels and pass-by-value approach I'm experimenting with in kin is close to the Limbo model, except that channels are objects with support different messages. Apart from the D extensions by Bartosz Milewski, these techniques require the language integrates with a scheduler, usually a green threads system rather than the OS scheduler.

One thing which bothers me about Erlang and pure-functional languages in general is the assumption that language level immutability has some bearing on concurrency.

It's fairly obvious that any message shared by machines on a network will be unlikely to include memory addresses in one of the processes, other than possibly as opaque values. In other words, if it's on the net, it's pass by value. Similarly most inter-process communication is pass by value, and the sharing of messages containing values and names of channels is well understood using CSP and pi-calculus. The net is unconcerned about what paradigm the languages which implement the processes communicating by message passing; it only cares that the messages are values and names. It doesn't follow at all that the implementation language for a process which operates on messages needs to present immutable variables to the programmer.

The other area functional languages have been touted has been for problems where there are shared memory concurrency within a process.

A trivial counterexample is given by lazy evaluation - in trivial implementations, expressions are passed around as thunks, consisting of a place to store the value of the expression, and a function to evaluate the value. The expression is evaluated lazily by calling the function the 'first' time the value is needed. Being a pure function, it doesn't matter as far as the value is concerned whether the function is called multiple times in different cores, but if the value returned is a non-primitive there are still write order issues with sharing the value. So you end up with similar barrier ordering problems that you have in non-pure languages, and barriers cost performance.

For strict functional languages, you still need the barriers, and other synchronisation points, if you are going to communicate values between cores. If you are passing messages by value, then it is necessary that the sender or receiver of a message cannot change the value of the message. This isn't necessarily the same as language level immutability - in a shared memory space, values sent on a channel should not change, but that can be achieved by copy-on-send or copy-on-write approaches as well as by general immutability. Having a shared memory space between threads requires synchronisation with the garbage collector - otherwise memory can be reclaimed and rewritten, breaking the immutability. None of this is particularly surprising, and the implementation of any SMP shared-memory language with automatic memory allocation will have to deal with it.

The presence of immutability at the language level allows the optimisation that a message can be passed as an immutable reference rather than by value. This introduces the pessimisation that any garbage collection of the arena that the messages' storage is allocated from has to be coordinated between all threads. If the optimisation of mostly-concurrent memory management is made, where each thread has its own arena, memory for messages is either allocated from a special shared arena when constructed, requiring some synchronisation, or messages are copied when sent.

It's fairly obvious that if you are allocating from a shared arena, then you're having to serialise some of the requests, so are losing concurrency ( as well as having to do escape analysis so you know what objects constitute the message and so require to be allocated from the shared arena ), and that if you're copying messages into a shared arena when sent then you have lost the pass-by-immutable-reference optimisation. Either way, I've yet to see a truly convincing case that immutability in itself actually gives any performance gain for concurrent code and typical message sizes ( if you have very large messages which are not referenced by the sender, then any copying scheme will be inefficient, but that seems to be a case for escape analysis rather than immutability; copy-on-send would be at a disadvantage there, but Erlang style encourages small messages anyway ).


So the problems in terms of performance are acquiring lock on the memory bus, which takes around 40 cycles for a lock cmpxchg, barriers to order access, and copying. Languages with channels as first-class constructs hide the details of locking and barriers, and can trade various copying or shared memory techniques.

I've not seen anything in Erlang that would suggest that its shared nothing messaging is less prone to programmer error than Limbo's channels. There are other reasons to use pure-functional languages in terms of proving theorems about the program, and below the language level some optimisations are facilitated, and some are harder to perform. But there seems to be a confusion between which bits of a particular combination of facilities in a language are actually supplying the gains, and my opinion is that message passing combining values and channel names ( however implemented or enforced ) is both safe, and open to analysis at the systems level by pi-calculus.

Messing about with X windows

I've spent the last week or so adding bindings to kin for X11 and anti-grain geometry.

X11 gives basic windowing capability, but no widgets ( you run GTK or some other toolkit on top ), AGG gives high-quality software graphics rendering.

This is a window which attempts to draw some buttons:



The window has a transparent background. I've lost track of the number of hacks I've had to do to get transparent backgrounds working in either MFC or Java over the years ( though both now support them ), so making it happen out the box is nice. Just use a colour with a alpha less that 0xff, and the background is transparent.

Thanks to AGG, all the rendering has affine transformations applied to it; the code draws the buttons where they should be, then bigger for debugging, then messes around with rotated text and shading. It's shown running on top of SciTE, the editor I use.

The buttons are all drawn manually - currently the graphics class supports fill rectangles with colours, linear gradients or radial gradients, drawing text and finding the bounding box of text.

The code implements a tiny button_model/button_presenter.

The reason I posted now is that I realised this line of code does the most of the work of the horizontal box layout in Java Swing:

fold ( ( x, btn ) => btn.set_bounds ( x, 0.0, btn.desired_width ( gfx, `normal ), btn.desired_height ( gfx, `normal ) ).x + btn.width + 4.0, 0.0, buttons )

Having done far too much Swing programming, I often find that with what I'm trying to do with it there's nothing that fits. For example, last contract I was trying to make a nice split button with a menu, and the look and feel/ Swing component / MVC distinction meant that you couldn't reliably implement one that was both pluggable and looked good - either you built one out of two buttons, which didn't look or feel like one button with a split, or you did an owner draw and lost the pluggable look-and-feel. That contract also required a column based layout, and containers which lined up like tables - the normal typographic idioms. The intention is that kin's toolkit will be more typographic/infographic in style, rather than widgety - most of the time, it's for reading not clicking.

I'm quite happy that starting from X11 in C rather than with a toolkit such as GTK ( which again may get transparent backgrounds soon ), after a few days there's enough there to see that it'll be much easier to create your own application-specific toolkits.

Comma Quibbling

Link: http://blogs.msdn.com/ericlippert/archive/2009/04/15/comma-quibbling.aspx

An example in kin. This misses the difficulty of the C# problem - as sequences in kin are linear, rather than being the mutating iterator/enumerator pattern used in Java/C#, you can pattern match several elements at once trivially (being able to pattern match sequences and backtrack on failure is one of the main reasons for writing kin in the first place).

module examples::eric_lippert_20090415
    # http://blogs.msdn.com/ericlippert/archive/2009/04/15/comma-quibbling.aspx
    def comma_append ( out, s )
        match s
            h :: [] => 
                out <- h 
            h :: m :: [] => 
                out <- h <- " and " <- m
            h :: t => 
                out <- h <- ", "
                comma_append ( out, t )
            [] =>
                pass
    
    def write_with_commas ( out, s )
        out <- '{'
        comma_append ( out,s )
        out <- '}'
        => out

    def to_comma_string ( s ) => write_with_commas( string_writer(), s ).str()
    
    def main ( in, out, args )
        write_with_commas ( out, args )
        out <- '\n'
        out <- to_comma_string( args ) <- '\n'

A new way to look at networking.

Link: http://video.google.com/videoplay?docid=-6972678839686672840

I find this video incredibly interesting. It's talking about the phase transition that occurred between telecoms networks and packet switched networks, and questioning whether the same can happen between packets and data.

In a routed telecom network, your number 1234 meant move first switch 1, second switch 2 and so on - it described a path between two endpoints. In TCP your packet has an address, and each node in the mesh routes in to the node it thinks is closer to the endpoint with the target address.

Currently I have two or three home machines (netbook, desktop and file server) where data lives locally, plus data 'in the cloud' on gmail.com and assembla.com, or on my site here at tincancamera.com . Though as far as I'm concerned, that data isn't in the cloud - it's on whatever server at those addresses resolve to. If instead I google for 'pete kirkham', about half the hits are me. If I put a UUID on a public site, then once indexed I could find that document by that ID by putting it into a web server.

In the semantic web, there's been a bit of evolution from triples without provenance to quads - triples and either an id or some other means of associating that id with the URI of the origin which asserts it. It's considered good form to have the URI for an object resolvable to some representation of that object, so there's a mix of identifier and address. The URI for kin is http://purl.oclc.org/net/kin, which uses HTTP redirection to point it to the current kin site. This depends on OCLC's generous provision of the persistent uniform resource locator service, and maps an address to another address rather than quite mapping an identifier to an address.

There isn't an obvious analogous mechanism for data to the TCP nodes routing the request to a node which might be closer to having the data, though is some ways a caching scheme with strong names might meet many of the requirements. It sort of brings to mind the pub-sub systems I've built in the past, but with a stronger form of authentication. Pub-sub replication isn't caching, as in a distributed system there isn't a master copy which the cached version is a copy of.

There's also a bit of discussion between broadcast and end-to-end messages; I've got to work out how to do zero-config messaging sometime, which again sort of makes sense in such systems - first reach your neighbours, then ask them for the either the data, or the address of a node which might have the data. But there still isn't an obvious mapping of the data space without the sort of hierarchy that TCP addresses have. (although pub-sub topics are often hierarchic, that hierarchy doesn't reflect the network topology even to the limited extent that TCP addresses do.) It also has some relation to p2p networks such as bit-torrent, and by the time you're talking about accessing my mail account in the cloud, to webs of trust. A paper on unique object references in support of large messages in distributed systems just popped up on LtU, which I'll add to my reading list this weekend.

I've also started reading Enterprise Integration Patterns. There's a bit of dissonance between the cocept of channel in these patterns, and I guess in the systems they are implemented in, and the concept of channel in pi-calculus. In EIP, a channel is a buffered pipe for messages, and is a static entity created as part of the system configuration, in pi-calculus a channel is not buffered, and the normal mechanism for a request/response pair is to create a new channel, sent that channel to the server of the request, and receive the response on the channel. The pi-calculus model is the pattern for communication I'm intending for inter-process communication in kin (though I'm not quite sure whether giving explicit support to other parts of pi-calculus is something I want). I'm not sure that having to mark request messages with an ID (as in XMPP IRQ) rather than having cheap channels is a good programming model; though there are reasons that pretending that an unreliable connection isn't a pi-calculus channel is a good idea. I'll see what I think after I've tried coding the channels. Certainly returning a channel from a query given a strong name which lets the requester communicate with an endpoint which has the named data could be a model worth pursuing. REST is a bit different in that the response channel is assumed by the protocol, but the URLs returned by the application are channels for further messages to be sent to, and of course can be addresses anywhere allowing the server for the next request to be chosen to be the one best suited to handle that request (eg, a list of the devices in a home SCADA system could list the URIs of the embedded servers on the sensor net rather than requiring the client to know the topology prior to making the initial request).

Things I didn't know in C

I've been creating an interpreter in C99 for the last six weeks. This is the largest project I've done in C, as normally I get paid for writing C++. I've also read the C99 spec, as I was taught C in '91, and things change.

Here are a couple of things I've discovered which I didn't know before:

You can use field names in struct initialisers, such as
( foo_t ) { .bar = 3, .baz = 8 }
which give you an automatic struct with the named fields filled in. Unfortunately, astyle makes a pig's ear of formatting it.

Unlike all the other printf family, the return value of the snprintf function is not the number of bytes written, but the number of bytes which would have been written had there been space in the buffer. That caused a few bugs in some string building code I'd written before I RTFM. I'd assumed the maximum value returned would be the buffer length, which meant I was assuming this is safe:

size_t max = sizeof(buf);
size_t offs = snprintf ( buf, max, "foo" );
offs += snprintf ( buf + offs, max - offs, "foo" );

But when offs > max, max - offs is a large value.

I also have given up using splint as a checker, as that was exactly the sort of error I was hoping to get detected. The amount of annotation necessary to get splint to work with my allocation scheme was too painful to justify.

SciTE and ctags

I've been using SciTE as editor of choice for some time, and spent a little time today getting a few extra things working for C99 projects. This year I'm refreshing my C a bit, as I haven't done anything which has specifically used C99.

There's support in SciTE for autocompletion of words within the file by hitting Ctrl+Enter, but you can also add .api files which list function prototypes for an API, giving autocompletion via Ctrl+I. You can either use the files provided for C and Java, or use ctags and a bit of Python to build your own.

The C.api file on scintilla.org is a bit small, but I couldn't get ctags to find most of the prototypes from /usr/include/*.h and /usr/include/sys/*.h. So I made a little bash script to pass each header through cpp, then extract it, which worked OK.

This seems to work to generate tags file for conversion to SciTE api file:

    ctags -f - --c-kinds=+p-d --excmd=number  /usr/include/*.h | grep -E "^[^~_]" > tags 

or from the kin project folder:

    ctags -f - --c-kinds=+p-d --excmd=number  src/core/*.h | grep -E "^([^_~]|_[^_])" > tags 

without --excmd=number the python script fails to convert the tags to api, as it uses patterns rather than line numbers.


Also changed some of user properties - to break it up a bit more with files into the ~/.SciTE/ folder. This moves the c and asm highlighing into separate files, a machine.properties file for machine specifics (such as where to put the window and whether to show tabs and status, which depends on screen size).

I also created a 'workbook.sh' script to write the date to today's workbook file and open it.

To get directory properties working, enable them in user properties with

    properties.directory.enable=1

Then the SciTEDirectory.properties file has its local settings for the project. This defines

    # project home
    ProjectHome=$(SciteDirectoryHome)

    # make 
    make.command=cd $(ProjectHome); make $(FileName)

    # go
    command.go.*.c=cd $(ProjectHome);bin/$(FileName)

    # Extend C API with project API
    api.*.c=/home/pete/.SciTE/c99.api;project.api

    # Retag
    command.name.1.*=Retag
    command.subsystem.1.*=2
    command.1.*=cd $(ProjectHome);\
        ctags -f - --c-kinds=+p --excmd=number  src/core/*.h | grep -E "^(kini?|opcode)_" > project.tags; \
        python ~/.SciTE/tags2api.py project.tags > project.api\
        rm project.tags

    # Apropos
    command.name.2.*=Apropos
    command.subsystem.2.*=1
    command.2.*=grep -E $(CurrentWord) /home/pete/.SciTE/c99.api $(ProjectHome)/project.api

    # Info
    command.name.3.*=Info
    command.subsystem.3.*=1
    command.3.*=firefox http://www.opengroup.org/onlinepubs/000095399/functions/$(CurrentWord).html 

This means build and run are performed in the project folder, and adds three extra commands - the first runs ctags to rebuild the project's tag index. The second searches the tag index for a highlighted word as a substring (rather than the built-in popup, which you type the first few letters). The third opens the unix spec for the highlighted function, which includes the C standard library functions too.

I've put the contents of my ~/.SciTE folder here, along with my .SciTEUser.properties file. There's the generated C99.api, asm and cpp properties without bold fonts (which mess up formatting), a version of cleanup.cc which will compile with gcc, protags.sh which preprocesses and ctags include files, and workbook.sh which creates a workbook/TODAY.log file and opens it in SciTE.

The Computational Beauty of Nature/Little things

Link: http://mitpress.mit.edu/books/FLAOH/cbnhtml/

Over the last few weeks, I've been reading The Computational Beauty of Nature an coding up a few of generative algorithms.

I've put them in the examples/java/fractals folder. Not much to them, just written on a netbook running Ubuntu.

I have two main computers - an Asus Eee PC 900 netbook and a Shuttle SX48P2 Deluxe desktop - and tend to use the Eee PC much more, even for programming, despite having a much smaller screen. Maybe it's because I have to sit at a desk all day at work, or maybe its that a full-screen editor on the Eee PC is a manageable chunk of code. I've been given dual monitors at work, and don't really use them - sometimes to have a web session in the one I've not got the editor open in. I use SciTE. It's no harder to Ctrl-Alt-Right arrow to switch a workspace on the Eee PC than to move your head to another screen.

I don't tend to stepwise-debug GUIs that much - which is why I was given two screens at work - I tend to break the code into smaller methods and write tests for them, which records the areas which you had difficulty with and had to pay extra attention too, information which is lost if you use a debugger.

Prolog is not co-operative

XProlog v.1.3, May 2002

?- help.       
> No. 

?- oh, go on.
> No. 

?- please.
> No. 

?- quit.

Why Type

Link: http://blogs.msdn.com/ericlippert/archive/2007/12/06/immutability-in-c-part-three-a-covariant-immutable-stack.aspx

For work, I'm demoing a GUI editor, which means undo would be nice, which is easiest to implement if you enforce purely functional data structures. So I'm doing a bit of reading as to how to implement suitable structures in Java 1.6, as that's the project's target language, and using Eric Lippert's examples as part of my reference material.

There was also yet another thread on forums.java.sun.com about what can be done with generics, erasure and making arrays safe.

I like having something which proves that all possible execution paths don't result in obviously erroneous actions. For many cases, a strong type system supports this.

But the more I look at it, being able to assert any simple thing about any action on an object would make a lot of the proofs simpler. There are better and better proof tools around, and the kinds of things you want to prove about concurrent systems are not easily expressed in a type.

I'm increasingly thinking that a dynamically typed runtime, with a good static model checker, would trump a strongly typed language in performance, productivity, and safety. But creating such a beast is highly non-trivial.

Cedric's challenge, C port and analytic attempt

I was a bit disappointed that the C port of the previous code wasn't quite as fast as another approach which cached more state instead of generating the i'th value. The second attempt, using the bcd lists was comparable to John Wilson's Java version (1.3 seconds rather that 1.5 reported by the Java), and an attempt using bitsets a bit slower. Timings on Eee pc 900, Ubuntu hardy heron. The code is nrnat2.c.

The biggest jumps are between 9(descending digits) and 10(ascending) and 10(descending) and 12(ascending). Generating those four values will give the largest jump in a range.

The number of values will be the total of combinations: 9 + 9 * 9 + 9 * 9 * 8 ... up to the max value.

The total for 1..9 is 9*(9+1)/2 = 45;
For numbers 10 to 98 there are 9 numbers starting with each digit, so you have 450*9 for the first digit, and 9 lots of a odd sum, where there's one digit missing - so 9 * 45 - 45 for taking one digit out each time (the range is 0..9 instead of 1..9).

That gives a total up to 10 of 45

Up to 100 we get the 45 up to 10, 45 * 10 * 9 for the first digit shifted once repeated 9 times, and 40 * 9 for the second digit repeated 9 times (as the first digit is always non-zero, it biases the remaining digit's average by 0.5 from 4.5 to 4). So total for up to 100 is 45 + 45 * 10 * 9 + 40 * 9 = 4455.

Up to 1000 we get the values so far, 45 * 100 * 9 * 8 for the first digit shifted twice repeated 9 * 8 times - the number of combinations of the other digits. The remaining digits occur the same number of times as each other in each position and once for each value of the first digit, so you get 40 * 9 * 8 * 11 from them, so total is (4455 + 45 * 100 * 9 * 8 + 40 * 9 * 8 * 11) = 360135.

Similarly sum up to 10000 is (360135 + 45 * 1000 * 9 * 8 * 7 + 40 * 9 * 8 * 7 * 111) = 25277895

Simplifying, the sum of the values with n digits is (9!/(9-(n-1))!) * ( 45 * pow(10, n-1) + 40 * floor(pow(10, n-1) / 9) ) and the maximum jump is floor( ( 1203456789-1029876543 ) / pow(10, 10-n) )


Pete

A coding challenge

An implementation of the coding challenge of Cedric's.

Somewhat coloured by the fact I normally use python as a prototyping language prior to production coding in C++.

The combinations technique (using a bcd string instead of list) gets faster than the filtering technique for max somewhere between 1,000,0000 and 10,000,0000. As python is bytecode, it may be slower to bit-twiddle than use a dynamic list; IIRC it has to allocate memory to hold longs anyway, but getting it right in Python and then porting to something with good performance is the way I often work, and longs are fast in production programming languages.

import time

def has_repeat_digits(i, available = (1 << 10) - 1):
 digit = i % 10

 if available & (1 << digit):
  if i < 10:
   return False
  else:
   return has_repeat_digits(i // 10, available &~(1< else:
  return True

def brute_force_counter(max):
 for i in range(1, max):
  if not has_repeat_digits(i):
   yield(i)

def test(max, counter, timed_run = False):
 last_i = 0
 biggest_jump = 0,0,0
 total = 0
 start_time = time.time()

 for i in counter(max):
  if not timed_run:
   print i,
  total = total + i
  jump = i - last_i
  if jump > biggest_jump[0]:
   biggest_jump = jump, last_i, i
  last_i = i
 stop_time = time.time()
 print
 print 'total', total
 print 'biggest jump', biggest_jump
 if timed_run:
  print 'time', stop_time - start_time

# select the index'th permutation
# first digit is special case, is in range(1,10) rather than range(0,10)
# otherwise it's a standard permutation. Using BCD encoded value to represent
# remaining digits to select from rather than a list as deleting from a python
# list is O(length) whereas deleting a digit from the BCD is O(1), and I like
# fiddling with bits.
def bcd_select(index):
 if index < 10:
  return index

 pow = 1L
 fact = 1L
 digits_available = 10

 index = index - 1L

 while index >= fact * 9:
  index = index - fact * 9
  digits_available = digits_available - 1
  fact = fact * digits_available
  pow = pow * 10

 #~ print 'fact', fact, 'pow', pow, 'i', index, 'i//fact', index//fact

 # first digit is selected from 1..9
 available = 0x9876543210
 digits_available = 9
 sel = (index // fact)
 index = index - sel * fact
 sel = sel + 1
 available = (( available & ~((1 << ((sel + 1) << 2)) - 1)) >> 4) | ( available & ((1 << (sel << 2)) - 1) )
 acc = sel * pow
 pow = pow // 10
 fact = fact // 9
 #~ print fact
 while pow > 0:
  #~ print digits_available
  #~ print 'fact', fact, 'pow', pow, 'i', index, 'i//fact', index//fact
  #~ print 'available', digits_available, hex(available)
  sel = (index // fact)
  acc = acc + pow * (( available & (0xf << (sel << 2)) ) >> (sel << 2))
  available = (( available & ~((1 << ((sel + 1) << 2)) - 1)) >> 4) | ( available & ((1 << (sel << 2)) - 1) )
  index = index % fact
  pow = pow // 10
  digits_available = digits_available - 1
  fact = fact // digits_available

 return acc

def bcd_counter(max):
 index = 1
 while index < max:
  value = bcd_select(index)
  if value > max:
   break
  yield value
  index = index + 1

On the map

Received a little gps 'mouse' receiver in the post today, and (having installed gpsd and python-gps) have got it running as a local service with my first google maps mashup. The server is here, it just shows a google map centred on the current location. I now need to wait until I get a mobile broadband dongle and the new tiny laptop I've ordered (Asus eee 900) and then can have gps on the road (though I don't really want to be using a laptop in the car unless I'm really lost)

Python and EA

For my current contract, I'm part of a team producing scripts which define interfaces to equipment in a satellite communications system for monitoring and control. Various interfaces, serial, low-level TCP and SNMP.

The application is fairly old - originated on Unix in early 1990s, ported to MFC late 1990s - and there are many links between the various configuration files. It's a high reliability system, so uses the classic pattern of a watchdog process with spawns the active processes, monitors them for liveliness, CPU and memory use, and respawns them or kills them in event of failure.

The goal is to use Enterprise Architect for modelling the system in UML. EA has a limited custom code generation - one file per class, poor tree walking functionality - which is just sufficient to create the interface scripts, but none of the other configuration which is more highly intertwined - for each rack or group of racks of equipment to be monitored, there's a server which runs a set of monitoring processes, each monitoring a set of instances of the equipment. Various parts of the configuration, such as the port ID of each server process, need to be put into different configuration files, so the desired layout of generated files doesn't follow EA's assumptions.

Also, there needs to be a parser for the configurations which reverse engineers a UML model from the configuration files - we don't want to have to generate the UML models for existing equipments by hand.

So I started writing a little parser in Python which generated an XMI file for import into EA. That worked well enough, and impressed the line manager, so have been spending the last couple of days fleshing it out.

EA doesn't quite treat tagged values as first-class citizens of UML, relegating them to a second window (though it's nice to have them docked and always visible, but that could apply to all the panes in the properties dialogs). So I wanted a table view which looked like the config file layout, of all the extra tagged values we're using to define the application specific properities used to implement the attributes of the equipment in the configuration files.

I've been using GTK for that - I've played with GTK a bit in C, and quite like it's level of abstraction and simple event model. It's not too hard to get things working in Python (some of the handling of attributes is a bit counter intuitive), and it mostly looks native (compared to Java or Gecko, or even EA's UI, which I believe is written in C#, but isn't using WinAPI menus).

I quite like Python, but it's a bit too imperitive for my taste, and there's no type system to tell you if you've put a right-handed vector into a left-handed library, or referenced an attribute of an object which doesn't exist. But being able to create a simple dialog with a REPL (read/eval/print/loop) in it to do the initial exploration of the EA COM automation interface was very handy.

The thing I dislike most in Python is that it doesn't actually use indentation to indicate blocks (I read Ken Arnold's chapter in The Best Software Writing over the weekend, and think I agree). It uses the colon character to indicate a block, and following a colon you have to use indentation. I'm always just doing the indentation, and forgetting the colons.

Lambda The Ultimate and Matrix Distractions

I had been reading up a bit on trace-based JIT. I'm not sure that there's any real difference between trace based and method based JIT if each branch is converted to CPS style call with type feedback. Which means removing the optimisation of having jumps and branches from the bytecode, and replacing them with dynamic calls.

But then I got distracted by a discussion of Strassen matrix multiplication, and haven't done anything with it yet. I need to get back reading through Golub & Van Loan too; it's over a decade since I last read it.

Test of syntax highlight

Test of the syntaxhighlighter:

    # generic sequence trait
    trait seq<T>
        def empty : boolean
        def head : T
        def tail : seq<T>
        def to_string => '[' ++ join(self, ', ') ++ ']'
        def concat (other:seq<T>)
            => other.empty ? self : shift(other, reverse)
        def reverse => shift([], self)

Some things I'm thinking about

I've been playing more with my mostly functional modelling and simulation language (kin), here are some ideas which I want to try and profile to see if they offer gains:

Carrying type and data as a tuple:

Some implementation of Scheme and JavaScript use a single void* size datum for each object, and for integers set the lowest bit and encode the value in the rest, and for other objects the lowest bits are zero due to alignment, and the whole is a pointer to object. That doesn't work very well for doubles, and requires that the type is stored in the object's header. Java, C#, and C++ (for object with a vtable) have type information in the object header, which costs in large arrays. I've been thinking about passing the type and the data around separately, which means you can have more tightly packed arrays for non-vtable types.

One-bit markers for escape detection:

Based on One-bit Reference Counting, a marker in the type field to distinguish 'shared' objects you can take a reference to, and 'non shared' which you must not.

Write-once arrays:

As an extension to 'one bit reference counting' style; you maintain a high water mark instead of always copying, for use in structures such as VLists so you don't copy on passing automatically, and it allows you to mutate an array if it can be proven that all accesses happen before writes in matrix multiplications:

        ax[i] <- ax[i] + row[i] * col[i]

Block order arrays for cache sensitive iteration and super compiled functors:

In a simulation, it's not uncommon to have a reduction on some function of a few attributes of an entity:

    let total_force = reduce(array_of_entities, lambda(e:entity, ax) => f.mass * f.acceleration + ax, 0) 

If this is over a homomorphic array, and mass and acceleration are simple double values, this would in C translate to picking 8 bytes here and there from the memory for the array. If instead each field is kept either in 'column order', or in what I'll call block order - so the fields for (cacheline size in bytes) objects are held contiguously. This should both reduce cache misses, and allow the use of SIMD instructions to process the data. The obvious disadvantage is that an object in an array is no longer the same layout as a single object on the heap, and to exploit it you need either a super-compiler or a trace-based JIT.

Effective model for scopes based on lists, symbols and objects:

Trying to build an interpreter in Java, which makes it tempting to use maps for everything, I found that the properties of an object and the properties of a lexical scope are much the same, (the duality of closures and objects is well known) so will try and define the binding model for values in kin using symbols, integers and lists only.

Using CAS for thread safe homogeneous VLists

Similar to the vector implementation in Lock-free Dynamically Resizable Arrays.

Options for compiling Verilog to shader language

Having had an interview last week as a systems modelling engineer with a company who were using C as the modelling language for timing simulations in embedded memory controllers, which is a bit like going for a job as a car mechanic and discovering that you're being quizzed on your wood-working skills, I was thinking about compiling an appropriate modelling language to something which executes efficiently. Though their particulary problem - timing conflicts - I would have though as having an analytic solution.

Something after UML

Speaking of Verilog, Verilog came into existance because even standardized schematic diagrams don't carry strong enough semantics and are not amenable to algebraic analysis, and graphical notations don't scale to large systems without hiding information.
Pi-calculus came into existance as Petri nets don't scale to large systems and are not amenable to algebraic analysis.
UML is very much in the standardised schematic mould, lacks formal semantics, and relies on hiding information to scale.

Often the hidden information in UML is very important - what appears to be a good design is not a good design if its simplicity is achieved by hiding most of the attributes and operations of a class, as often happens when a class gets multiple unrelated responsibilities. The notation allow you to hide details which should indicate that the design should be factored into smaller units, and in fact encourage such behaviour as a mechanism to scale up to showing many classes. For example, in Altova UModel:

You can customize the display of classes in your diagram to show or hide individual class properties and operations. ... This feature lets you simplify the diagram to focus on the properties and operations relevant to the task at hand.

If the class has features which are not relevant, then refactor it. Don't hide it so it doesn't make the documentation more complicated. The classes for well-factored systems have nothing to hide, but require more relations between the classes, which UML tools don't handle well (last time I checked none provided basic auto-routing or anything like good layout engines) and look more complicated, even though they are more simple - in the same way a dry stone wall is simpler than a minimalist plastered white apartment, but is visually more complex.

So what might come after UML then? What would not mitigate against refactoring, but allow a visual overview? What notation might give good analytic properties for software, rather than being a system schematic with loose semantics?

I don't know yet.

Bjarne Stroustrup on the Evolution of Languages

Link: http://msdn2.microsoft.com/en-us/magazine/cc500572.aspx

A few comments on this -

The illustrations in the interview don't appear related other than that they are of an IDE ("I might have a different opinion if a good IDE was universally available", queue Visual Studio, which implies that VS isn't a good IDE) and that the UML is illustrating multiple inheritance, but mechanism for dispatch in the paper is not based on multiple inheritance (at least as shown in the diagram).

It's an interesting paper though, and I would like open methods in a language.

I don't think that DSLs should be just extensions to general purpose languages. Mainly because that implies a specific execution model, and if you have a DSL then execution shouldn't be part of the domain model (unless it's something like Verilog, or the input to a program proof tool, in which case execution is a domain concept). DSLs should allow the modelling of a domain, and lose their benefit - abstraction away from execution - if they are tied to a programming language. If you have a model of the physical domain, then you can state 'F = m * a' and not have that imply that the values named by 'm' and 'a' are multiplied and stored in the location named 'F', as binding to C++ semantics would have it. Otherwise you need at least three models - 'F = m * a', 'm = F/a' and 'a = F/m' - to let you represent everything that the one entity in the domain represents. Which would create a mismatch between the language and the domain, eliminating the benefit of a DSL.


I've also been reading 'Programming Languages Pragmatics' and working on my model-based language kin a lot, and adapting the parser and code model of the modelling language I used to do a state model of some concurrent code to support kin. I was generating Java as a first cut to bootstrap a full compiler, but Java's generics aren't rich enough to support kin's parametric types, and without them it's not easier to generate Java than C. So I will go straight to a C back end, and generate an intermediate form which can be interpreted. It's more important for kin to be able to call C libraries such as the Intel Math Kernal Library than for Java libraries, and I don't really like the sort of compromises you have to make to fit in with Java's libraries, however nice the JVM's HotSpot and garbage collector are to have.

Andy Goldsworthy - Rivers and Tides

We got the DVD as a wedding gift, and watched it last night.

I like Andy Goldsworthy, both for his aesthetic and the humility that lets a work exist within an environment which makes it transient, or fluid.

Watching him create a work, sometimes it would fall. Often it was compromised to fit with the time scale imposed by the environment by tide or light.

At each fall, a discovery. More of the nature of the work is revealed; the more failures, the more effortless and whole the final work becomes.

I really like the idea of a flowing form moving through or around obstacles, adapting to what's there, constructed out of what is available, but maintaining its own identity, a recognised figure.

The hanging works, stalks randomly pinned together with thorns, which then form a coherence to mark a hole. A form emerging from chaos, using the chaos, constructed with the chaos.

The works accept that they are not static, but will be changed after the artist commits them to the environment.

There's something in programming - called the quality without a name - which is what software architecture is about. It isn't about perfection, or locking everything down to nuts and bolts, or about hiding the chaff and chaos under languages and frameworks, but about habitability and fluidity, and coherence. It's what the original pattern movement was about.

Is this work good to live with? Does it fit with the environment? Can it flow and adapt with the rivers and tides?

Plays well with others?

> I know large systems can be built statically...I've also done it dynamically in more than one dynamic language.
That hasn't quite been my experience - every large system I've worked on has ended up getting layered into a static core with dynamic or DSL scripting. Greenspun's tenth rule.

On the other hand, even medium applications I've been involved in which were implemented only in a dynamic language got into difficulty with performance or modularity, and so either evolved into a mixed language system or were reimplemented.

Often I also use dynamic languages or environments to prototype algorithms, and sometimes then have to port to static languages for performance reasons - writing better code generators is rarely cost effective, as the dynamic languages are sufficiently good at the general cases, if you need to optimise you're optimising for a specific requirement. The same happens (albeit more rarely) where you need to add inline assembler code to C or Fortran where you need to go below their abstraction level (CAS or bitwise rotation, integer overflow etc).

Also in large systems you often interface with extant libraries, which may be implemented in diverse languages. You're not going to port half a million lines of a numerical library into Smalltalk so you can call it.

So you end up with interfaces between the user code and the library, and having to specify in a machine processable manner the types at that interface, as you're now below the abstraction barrier of the dynamic language.

Other dynamic languages require definitions for such interfaces, though foreign ones may not be visible in the language's introspection facilities - for example, Mozilla's JavaScript uses IDL for the definition, but the type and arity of functions isn't visible via introspection.

This introduces cost and brittleness to the system; and in the types of systems I've most experience with it also makes it harder to move a prototype algorithm between the dynamic and library codebases than it feels it ought to be - the dynamic runtime usually has the facilities for doing most of the code generation work already, but there's no means of accessing the results and tweaking it. I am looking for mechanisms which make that sort of task easier, and which don't require custom interpreters for DSLs, which are a pain to get right or maintain.

>"What happens in Smalltalk projects where you grow larger? Where you want to divide a system up into components, and some of those components don't exist yet?"
> You have a need; you have an idea to meet the need; you try it; you grow it. I guess I don't understand the question.

In my experience, that only happens up to a certain size. My question was about large systems - systems where you have to subcontract components, either to another individual in your team, to a second local team or to a separate organisation. Bottom up approaches don't scale out to that level, top down approaches introduce brittleness and (code production) inefficiency. The Smalltalk browser appears to be strongly a bottom up tool; I'm curious as to whether it allows that approach to scale out better.

> Semi-formal notations, tests and other examples, documentation, good tools -- these all contribute to success. But if you are looking for some kind of a "static declaration" as they saving mechanism for large systems -- it may work for you, but I doubt you can prove they are necessary and sufficient. I have counter-examples.

I do consider some form of specification of the domain and codomain of a function to be required, and the stronger the specification which can be automatically tested, the better. Verifying natural language specifications by hand is simply not viable for large software projects. What's provided by the type systems of most languages is not sufficient even for that - you can't say the domain of a square root function is the set of positive reals. Specifying pre- and post- conditions helps, but for anything involving concurrency you need 'for all' rather than the 'there exists' specifications given by unit tests. But most of the system doesn't require formal specification, and good design minimises shared state.

So I'm looking for something with the gains of dynamic languages without barriers to performance, and good modularisation. As such, I'm more interested in gradual typing than Smalltalk. But if it does have anything to offer then I'll borrow from it.

> "Can such interfaces be browsed in the same way if the code can't be called?"
> Your question betrays your bias. "There must be some such mechanism as the one I am used to," he thinks.
Yes, I have a bias based on my experience and problem domains.

One project I was involved in was refreshing the library used for airworthiness stress analysis, with a view to improving the performance (it was costing around half a million pounds in CPU time to run the analysis for each design revision, so in the company at that time, making a 10% improvement in the run time would mean someone didn't have to get made redundant). This consisted of a set of Fortran libraries, some OS scripts, and a domain specific scripting language which encoded the models and analysis algorithms. A set of flight states was mapped over the model, and the outputs reduced with a filter to indicate any resonances. The core of the system was mostly unchanged since the late 1970s, only the models used being updated with successive revisions to the aircraft.

There was a large amount of model and library code, so I wrote a quick and dirty call browser to explore data flows in the parts of the system I had access to. Since the code was significantly larger than the memory capacity of the computer I was running the analyses on, let alone expanding that to the AST and call graph, the interactive image and execution based querying as presented in the Smalltalk browser post would not have been suitable. The project ended up going nowhere, as translating the implementation of non-standard dynamic language from the mainframe to PC would take more resources than the team had in the time available.

If the scripting was in a standardised dynamic language, then the maintenance cost would have been much lower, and the chances are the code could have been moved from the costly mainframe to instead run overnight on PCs.

So is there any way such tools can extend for a system of a thousand executables, rather than one? A system which doesn't have everything visible? The types are somewhat irrelevant to this, but most programs people are developing are not whole; the question is of scaling approaches which assume you have a single image which is everything you care about, and all changes to the system are monotonic. If you have a system with multiple teams working on it, if you are developing a library which may be used in a number of ways, or if you have a system which is so big you can't load it without paging, then I'm interested in what happens, since anything you deduce from calls to code you can't inspect is not monotonic - some other use of the function may be a correct use and widen its domain. Partly it's an issue of extensional rather than intentional analysis - some systems you need to prove that the core is correct rather than show it is not incorrect in parts. But an awful lot of the code I work with doesn't need that level of confidence, and as much as possible I write that in dynamic languages. Sometimes I make that judgement wrongly, and so I'm looking for mechanisms which allow 'fixing' of parts of the system more easily, as well as allowing assertions to be made for compatibility between parts of a heterogeneous system.

> Most large systems developed with dynamic languages have not used the kind of mechanism you seek.
I've seen such mechanisms in JavaScript, Lisp, Erlang and Python. Maybe Smalltalk just doesn't play well with others, and is only suitable to monolithic applications.