The Hackspace Grand Opening (by )

Those of you who follow me on various social media will have seen the photos of Cheltenham Hackspace new premises being spruced up and that is because tomorrow (well today now!) is the grand opening 😀

Sunday 4th of December - if you are local then please pop along - hackspaces or createspaces are made by and for the community and we'd love to meet you :)

I'll be taking along steam punk and textile stuff to be working on and have plenty of spare so others can have a go! There is plenty to see and people to talk to and skill share with :)

Also I have been making craft videos for Advent as it turns out it is the tenth Christmas of Salaric Crafts How To Blog!!!

Of course I only have 2 vids up and it is now technically day 4 - annoyingly obsolete laptop is obsolete and is being a pain in the backside but I shall continue limping along with it and hopefully get the other two vids to you some time tomorrow!

I also have a craft fayre Monday at the Costa Coffee on Metz Way in Gloucester :) Mainly taking Wiggly Pet Press stuff with a bit of Steam Punk etc...

Cool things I have worked on: Low-latency highly-available NoSQL data store (by )

I've worked on a bunch of cool things in the past; and since I'm always explaining them to people, I realised it'd be good if I just blogged about them so I can just share the link.

I was asked to help design and then build a database to back a social networking system. The main requirement was to be able to satisfy lots of single-record primary-key fetches from a single thread as quickly as possible, because a PHP web app would be requesting lots of data to build the page; we had to do a few hundred of these "random point queries" in a small fraction of a second to get the page rendered in time. It had to be able to scale sideways, by adding more machines to the cluster. It also needed to be able to update this data, but at a much lower load - updates and creations of single records happened when a user went and did them, but people browsing around the site would hit several pages, each of which would request hundreds of records.

And it needed to be highly available. The app was to be spread over two datacentres for redundancy purposes, and as long as at least one server was reachable, the whole thing had to keep working as much as possible. We couldn't use "quorum" systems where a majority of the nodes needed to be reachable to make an update, for instance.

This, combined with the projected dataset size being a few terabytes at most, meant we decided to go for full replication. Every node had a copy of the database, and rather than being a daemon you spoke to over a socket like a conventional database, we'd write a shared library that would be loaded into the PHP process, so as to avoid context switch overheads for each query. The shared library would read the data files directly from disk.

The on-disk format was B-trees, but with a multi version concurrency control setup: update transactions (more on those later) would write all the new data into unused space until it was ready, so reads could still be happening while an update was being prepared, so as not to delay those all-important reads.

Updates were done with a reliable multicast protocol. The shared library would broadcast up dates to all nodes currently reachable from the process sending the update. Those updates were received by a daemon process running on every node, which took updates from the network and applied them to the local disk storage. But there were many devils in the details here.

Because every daemon had to process the entire update load of the system in parallel, they had to try and maximise the use of disk bandwidth. We couldn't afford to be rushing around updating every record with its own transaction, with all the sync overheads; we had to batch them somehow to amortize the overheads of committing them to disk reliably. Also, as updates were handled asynchronously and sent from a large pool of PHP processes, we needed to stop the PHP application from sending updates faster than we could process them and overrunning the network buffers. And just to make matters worse, updates could come from the network in unusual orders for various reasons, but we needed to apply them in a consistent order on every node so multiple updates to the same record all produced the same result in the end.

So, every daemon had an update queue. Its highest priority was pulling updates off the network and into the queue; its second priority was processing updates from the queue. But the queue wasn't just a FIFO. We gave every update a sequence number when it was generated, from a sequence number counter in shared memory on every node; and to ensure global consistency, we implemented Lamport timestamps - when an update was received from another node, we immediately updated the local sequence number counter to make sure it was more than the received sequence number, so that all updates issued from a node with knowledge of a given update would carry later timestamps, thereby ensuring that any transaction which read a current value and then updated that to a new value would be applied "later" than the update that provided the old current value.

So our queue ordered incoming updates by sequence number (using the ID of the issuing node as a tie breaker, to ensure a global ordering). We also stored the update sequence number on every record on disk, and refused to update a record to an "older" value, to deal with re-orderings over a longer time period than those which met in the queue. The queue also noticed updates to the same record group and merged them into a single update, always replacing older data with newer according to the sequence numbers. This meant that a flurry of updates to the same record would, as long as they all arrived before the queue was flushed, all "coalesce" into a single update to the on-disk data.

Wait, I said "record group"; what's that? Well, in the data model, often a bunch of records would represent parts of one object. Imagine an invoice in the traditional SQL format, with an invoice record and a bunch of line item records that are components of it. We encouraged the use of small records, as we updated records by providing a new value for the whole thing, and lots of small records meant that finer-grained bits of a record can be updated in parallel without trashing each other's updates. So as part of the "schema" we defined a mapping from record primary keys to record groups; many records would go in the same group, and was stored as a single entry in the on-disk B-tree, so we wanted to coalesce updates to the same record group into one, thereby getting more records updated in a single read-modify-write cycle.

Under the hood, the queue was two data structures - a priority heap full of record-group update lists, ordered by sequence number; and a hash table from record-group IDs to the same update lists. Incoming updates were mapped to record-group IDs and looked up in the hash; if an update to that group already existed then the update would be merged into it, and if the sequence number was older than the one already in that queue entry, we'd move the entry up the queue by re-inserting it into the priority heap. Otherwise, we'd create a new entry with a single update to the record group, and pop it in the hash and the heap. Keeping the two in synch in all cases was a bit of work, but once we'd covered all the cases, it looked after itself.

The queue also helped us prevent overload, too. Every node measured how big the backlog was, in three different ways: There was a maximum number of record group updates we wanted to hold in the queue, a maximum number of bytes of new record data in the queue, and a maximum average latency (in seconds, between the PHP code requesting the update and it getting written to disk on the node). We tracked the latter by putting wall-clock timestamps in the update messages and keeping an exponentially-weighted moving average of the difference (like a UNIX load average), and the former two came directly from the queue data structure. On each node, we compared each of the three measurables to our target and scaled it to a 0-100% capacity measure; we then took the worst of the three as the backlog score for that node, a measure of how "far behind" it was.

These were broadcast to the other nodes in the network, to compute an overall "worst backlog of any node" for the entire cluster. We were a bit clever with this - if a node's backlog wasn't the worst, then there was no point in it telling any other nodes about it, so only the nodes that were at the worse backlog level in the system were broadcasting their state. Again, there were lots of edge cases in this, which we carefully handled to make sure the system as a whole knew the worst backlog state of any node in the system, with the minimum of network noise.

So each node now knew how backlogged the cluster as a whole was; and we used that information to apply back pressure to the PHP clients. The backlog score was stored in the shared memory segment, and the function that was called from PHP to send an update consulted it. If the backlog was more than a minimum, then gentle pressure was applied to slow the PHP application down - before sending the message, we would sleep for a duration that depended upon the backlog level. If it was at or more than 100%, we'd actually sleep in a loop until it abated; but otherwise, we'd sleep for a time that increased smoothly from zero to infinity as the backlog went from 0% to 100% (accounting for the situation where the backlog dropped while we were sleeping, to a point where we'd already slept enough). This meant that if the PHP app was trying to generate writes faster than we could get them to disk, there'd be a certain amount of "stretchiness" in the system as the implicit queue in the network and our update queue took up the slack. But if the update queue kept growing, the PHP app would face increasing delays in getting updates applied. This created a negative feedback loop (as there was a finite limit to how many PHP processes could exist across the cluster), and we tuned the shape of the feedback curve such that the system would settle to a stable backlog level (and, thus, a stable sleep duration, and thus a stable write rate) rather than oscillating.

This meant that when the PHP code did an update, it would be some time before that update was visible on every node. For some parts of the system, that was fine, but for other parts, an immediate response to updates was required, so we gave the caller of the read function a choice of "consistency level". At the most basic and fastest level, it would just check the local state, and potentially miss out on updates that were still flying through the network. At the "immediate" level, however, it would first hash the record key and use that to select a "primary node" for that record. That node would be responsible for storing, in-memory, the latest state of that record if it was currently being updated; because the update function also offered a consistency level setting. The most basic one just send the update out onto the network, and the "immediate" level first sent the update to the primary node's in-memory update buffer. The use of specific nodes for this threatened our reliability guarantee; if that node was unavailable, or crashed and restarted while an update was in progress, we'd lose the update from the buffer - but it would still proceed through the normal mechanism. So if updates and reads to a record both requested "immediate" consistency, we would not see update latency (except when nodes failed), but at the cost of network round trips harming the latency.

Updates had a third consistency level, too, which was meant for creating new records with an external primary key (such as a user record, keyed by email address): if this was selected, then a two-phase commit process was used. The record creation would be proposed on every reachable node, which would cause that primary key value to be marked as reserved in the database, or the proposal would be rejected if it already existed or was already reserved. If a majority of the nodes in the system were reachable and OK with the update, then it would be actually performed; otherwise, it would be rejected. These were slow, and we tried to avoid them, but some parts of the application required that level of atomic global consensus.

You might be worrying that these asynchronous updates could get lost between a PHP process sending them to the network and at least one node receiving them, but all updates were received by the local node intrinsically; and once an update is on one node, it'll get to all the others. The reliable multicast protocol lets each node know if it's missed some updates from others (by using a per-node monotonic sequence number on every message, and looking for gaps). If that happens, it would try and retransmit if they were still in the send buffers; if not, then a network break would be declared, and the nodes would know they'd missed some updates from some other nodes. This would start a process by which all nodes that had missed some updates would declare the range of global sequence numbers they seemed to be missing, and the nodes that had updates in that range would then re-transmit them all (by using a special index from update sequence number to record across all tables). They would be retransmitted with the original sequence numbers, not new ones, so no matter what order which nodes got them in, they would eventually get to all nodes and end up in the same global ordering, so every node would end up with the same final state.

A node that starts up from a reboot or from fresh used the same process - the knew the last sequence numbers they'd been fully in synch with the cluster at, so they'd be able to request the latest state of all records updated since then. A totally new node would have seen no updates, so would request all records changed since timestamp zero, which would be all records. In these cases, the node would request that the playback be unicast to it alone, as opposed to the network partition case where nodes would cooperate to request broadcasts of all the missed updates to get the whole network back together.

And so we had a system that could (on my 2008-era laptop in a VM) do several thousand random record reads per second from a single thread, while handling bursty asynchronous updates of a thousand or so records per second (many many more if they all happened to fall into a smaller number of record groups!), while nodes came and went from the cluster, and the cluster was occasionally split into arbitrary sub-clusters due to network link failures. When the cluster was working properly, it would provide a completely consistent view of the database; but when the cluster was in a failure state, all nodes could service reads and updates (except the super-consistent unique primary key creation updates, which would all fail if a quorum of nodes couldn't be contacted to agree), but updates could then be delayed. I've not seen a system since that can provide that level of service.

Failing (by )

I've failed at morning - there is pink tooth paste on our bed and Mary only half dressed in the car for school :( Still I think that is the first proper melt down we have had so far this term with getting ready in the mornings so... getting there - of course Jean has taken the bright turquoise coat to school so I am sure we will be getting a letter or she'll be getting a detention or something about that as she's only allowed black ones :/ To be fair her black one is at the school drying out from yesterday still but she was supposed to take my coat!

My chest is still bad and I've failed to finish decorating the girls rooms. I've now been ill since the 2nd of November and am BORED. Hoping it will sort itself asap.

Yesterday was a System of A Down and Cradle of Filth et al kind of day, Jean came home sans coat and bag as they were too wet and she'd been lent other things in their sted. Which was a relief as I thought she'd gone out in the torrential rain without anything!

Today I wonder if she's remembered her jujitsu bag as she's going straight from school with her friend and I forgot to remind her - I can see the bag from here but that does not mean she hasn't got the trousers and t-shirt with her - the jacket is just too bulky for her to carry in with all her school things.

Maybe I'm letting her down by not sorting it all out, by not driving etc - I hope she is just becoming independent. She's actually pretty epic at organising herself considering she is organising herself and she is mine and Al's daughter and she is only 11.

Rain like this always makes me worry - in 2007 before Gloucester but in Gloucestershire we were flooded and ended up being out of our home for about a year. Rains since have caused issues with the new houses roof etc... and though I know that means it's now a good roof... the fear is there tangled in my brain, if it rains heavy I feel I should go and just check that things aren't flooding - because you know I'd be able to do something about it if it where :/

I'm all mouth ulcery - and run down... thinking it's the aneamia, thinking it's still on running issues of having gotten low levels of gluten etc... over the summer etc... but I don't know.

There are happy things to write about just feeling a little deflated so thought I'd share what was going on. Alaric's new job is great - he's loving it but due to traffic in Cheltenham he is not getting home until gone 7 at night and because he does school run in the mornings he's gone for like 12 hours to do do his 9 hr job. This is the first time I've been on my own on my own in the house everyday since having kids... there has always been a kid about and/or a husband. It's weird because instead of the relief of them having their 2 days in nursery it's like... the house is EMPTY.

I think I'm getting less done but I also think I'm getting more done as I am doing the new rest regime from the doctor to try and get the head bang healing properly.

Tomorrow there is coffee with a friend and at some point I need to go and pick up some bits from another... I have stalls to organise for Salaric Craft and The WigglyPet Press for December and I need to decide weather to shut down my Patreon account due to the fact I think I'm going to end up triple taxed on income that otherwise would be taxed once max.

It's a shame I like the platform... :/

Anyway I will now go and up load pics so I can get back to cutsie blogging and political rants.

Programming with state machines (by )

State machines are a really nice way of thinking about systems with state. As a notation for expressing imperative code, I much prefer this:

To this:

x = readchar();
while(x != EOF) {
   if(x == 'a') {
      doA1();
      x = readchar();
      while(x != EOF && x != 'x') {
        doA2(x);
        x = readchar();
      }
      doA3();
   } else if (x == 'b') {
      doB1();
      x = readchar();
      while(x != EOF && x != 'x') {
        doB2(x);
        x = readchar();
      }
      doB3();
   } else {
      doC();
      x = readchar();
   }
}

I've always wished I could write that sort of code as a state machine rather than a bunch of nested structured programming primitives. Although there is some charm to the idea of drawing a diagram on the computer and having that be compiled as executable code, though, that can also be fiddly and isn't well supported by conventional programming tools; so I'd rather actually describe my state machine in text. What I want is a syntax for writing state machines, rather than writing imperative code that implements the state machine.

For instance, the diagram I put above wasn't drawn by me; it was drawn by a tool called PlantUML from the following source code:

@startuml

state Processing {
      Ready --> A : a/doA1
      Ready --> B : b/doB1
      Ready --> Ready : not a or b/doC

      A --> A : not x/doA2
      A --> Ready : x/doA3

      B --> B : not x/doB2
      B --> Ready : x/doB3
}

[*] --> Ready

Processing --> [*] : EOF

@enduml

But the UML state diagram is meant for abstract modelling of systems, and lacks the precision and detail required for actual executable code. The state diagram doesn't make it clear that doA2 and doB2 need to be passed the character that was read, for instance. PlantUML's syntax, therefore, also lacks that kind of detail, so we can't just use that.

Also, in a programming situation, it would be nice to be able to express types of state machines: to be able to say that a group of state machines has some useful properties in common, defined by the "type". The type of a state machine defines some high-level states and what inputs or outputs are possible in each state; any state machine of that type has to follow that behaviour, even though it might break the states defined in the type into many substates. For instance, the example state machine above always accepts any character until it receives an EOF, then stops; that might be expressed as a type having a single Ready state with two transitions, one mapping an EOF to the end state and another mapping a character back to the Ready state, with no outputs. That type would be suitable for any state machine that accepts characters until they finish, so a generic "character input stream" might accept a state machine of that type to process them, without needing to know anything about As and Bs.

These thoughts have led me to the following model of a state machine that's suitable for use as part of a programming language (although I've not defined an actual syntax yet):

State machine type

A state machine type is a set of states. Each state has a name, and a list of message types which are acceptable in that state (I am assuming that the underlying type system is smart enough to include things like "character equal to a" as a type, rather than merely "character"). This list must be disjoint.

For each input message type, there's a list of possible next states and an output message type (which in our example above would be a void type, as we never output messages).

There is also an initial state. It's impossible for the initial state to be the target of a state transition on a message, so it only has transitions out to other states. Those transitions all represent possible constructors of this state machine, because the initial state represents nonexistance.

For instance, a type" for vending machine controller state machines might be (given a Result type which has two values, success and fail):

Initial state:
   input: (Create) output: (Void) next state: (Idle)

Idle state:
   input: (Coin(Value)) output: (Value) next state: (Credit)

Credit state:
   input: (Coin(Value)) output: (Value) next state: (Credit)
   input: (Refund) output: (Value) next state: (Idle)
   input: (Select(Product)) output: (success::Result) next state: (Idle)
   input: (Select(Product)) output: (fail::Result) next state: (Credit)

The Value objects output in response to Coin or Refund inputs happen to reflect the current credit in the machine, a fact which the state machine type alone can't represent (that would need to be explained in a design-by-contract invariant of some kind).

From this type can be derived the type of the state machine's transition functions, which in this case will be:

coin :: Idle -> Value -> (Credit,Value) |
        Credit -> Value -> (Credit,Value)
refund :: Credit -> (Idle,Value)
select :: Credit -> Product -> (success::Result,Idle)|(fail::Result,Credit)

Note that the Create transition isn't represented here, because this state machine can't actually be instantiated - it doesn't specify the behaviour enough. There's no way of saying which possible select result should happen, or of what values are returned as outputs. But the functions we have are automatically implemented by the state transition definition, and will cause the appropriate transitions to occur in any state machine that's a subtype of this one; every function accepts an instance of the state machine in a given state, and an input value, and returns a new instance of the state machine and the output value.

Subtyping

State machine types can be subtypes of other state machine types. A state in the parent type may be split into several states in the subtype; any transition to a state A in the parent type must be represented by a transition in the subtype to some substate of A, and all transitions possible from state A in the parent type must be represented by transitions from every substate of A in the child.

For instance, a subtype of the vending state machine might have an infinite number of substates of "Idle", one for each possible configuration of available things to vend inside the machine. If it vends three different products, then these substates might be called Idle(A,B,C) where A,B and C are nonnegative integers representing the stock of each item. The only transition out of "Idle" is when a coin is inserted, so every Idle(A,B,C) state must have a transition from a coin being inserted, returning a Value, and taking us into the Credit state.

However, our Credit state also tracks the stock, and also tracks the credit inserted so far - so we need an infinite set of states of the form Credit(A,B,C,X) where A,B,C are the stocks and X is another nonnegative integer for the number of pennies of credit. So the parent-type transition from Idle to Credit has to be replaced by a transition from every Idle(A,B,C) to Credit(A,B,C,X) where X is the Value of the coin inserted. All the transitions from Credit in the parent type need to be represented as transitions from every Credit(A,B,C,X) state to other Credit(A,B,C,X) or Idle(A,B,C) types as appropriate. But with that done, it can be shown that all the states and transitions of the parent type correspond to one or more in the subtype.

The one exception is the initial state - the creation transitions from that in the subtype need not correspond to those of the parent type.

Given an extension to the syntax to create "parameterised states" such as Idle(A,B,C), which are shorthand for a potentially infinite set of "concrete states" such as "Idle(4,0,1)", we might represent that subtype like so:

Initial state:
   input: (Create(a::NonNegativeInteger,b::NonNegativeInteger,c::NonNegativeInteger))
     output: (Void) next state: (Idle(A,B,C))

Idle(a::NonNegativeInteger,b::NonNegativeInteger,c::NonNegativeInteger)
   state implements Idle:
   input: (Coin(x::Value)) output: (x::Value) next state: (Credit(a,b,c,x))

Credit(a::NonNegativeInteger,b::NonNegativeInteger,c::NonNegativeInteger,x::NonNegativeInteger)
   state implements Credit:
   input: (Coin(x'::Value)) output: ((x+x')::Value) next state: (Credit(a,b,c,x+x'))
   input: (Refund) output: (x::Value) next state: (Idle(a,b,c))

   input: (Select(Product==A)) when: a>0 output: (Success) next state: (Idle(a-1,b,c))
   input: (Select(Product==A)) when: a==0 output: (Fail) next state: (Credit(a,b,c,x))

   input: (Select(Product==B)) when: b>0 output: (Success) next state: (Idle(a,b-1,c))
   input: (Select(Product==B)) when: b==0 output: (Fail) next state: (Credit(a,b,c,x))

   input: (Select(Product==C)) when: c>0 output: (Success) next state: (Idle(a,b,c-1))
   input: (Select(Product==C)) when: c==0 output: (Fail) next state: (Credit(a,b,c,x))

(We really should have represented the stock as a Map(Product,NonNegativeInteger) type and then not duplicated the select rules...)

Converting a parent state into a parameterised subtype state is only one way of splitting a state in a subtype, too. The syntax above would permit the creation of separate states that all say "implements Credit", too. A very simple vending machine that can only hold one instance of one product might split Idle into two states, Empty and Full, for instance; and probably split Credit into CreditFull(Value) and CreditEmpty(Value) to represent the Credit state while also parameterising CreditFull and CreditEmpty with the current credit.

The above syntax for parameterised states can get unweildy if there's a lot of parameters, especially if generally only a few of them are changed in any given transition (imagine the above example of there were ten different products to keep track of). Therefore, as syntactic sugar, it makes sense for it to be possible to define parameters shared implicitly by one or more states. Transitions into those states from states outside the group need to explicitly specify all the parameter values, but transitions within that group can use a different syntax to represent the next state, which only specifies what parameters have changed. All the rest are passed in unchanged, automatically. It might look like this:

Initial state:
   input: (Create(a::NonNegativeInteger,b::NonNegativeInteger,c::NonNegativeInteger))
    output: (Void)
    next state: (Idle(A,B,C))

parameters a::NonNegativeInteger,b::NonNegativeInteger,c::NonNegativeInteger {

Idle(a,b,c) state implements Idle:
   input: (Coin(x'::Value)) output: (x'::Value) next state: (Credit(x <- x'))

Credit(a,b,c,x::NonNegativeInteger) state implements Credit:
   input: (Coin(x'::Value)) output: ((x+x')::Value) next state: (Credit(x <- x+x'))
   input: (Refund) output: (x::Value) next state: (Idle())

   input: (Select(Product==A)) when: a>0 output: (Success) next state: (Idle(a <- a-1))
   input: (Select(Product==A)) when: a==0 output: (Fail) next state: (Credit())

   input: (Select(Product==B)) when: b>0 output: (Success) next state: (Idle(b <- b-1))
   input: (Select(Product==B)) when: b==0 output: (Fail) next state: (Credit())

   input: (Select(Product==C)) when: c>0 output: (Success) next state: (Idle(c <- c-1))
   input: (Select(Product==C)) when: c==0 output: (Fail) next state: (Credit())
}

Implementing state machine types

Note that we've suddenly started giving names to the Values flying around, and specifying an output value rather than just a type, and splitting transitions into different cases with disjoint boolean "when:" expressions. This, too, further constrains the type of the state machine; indeed, this machine can actually be implemented and will provide a simple model of a vending machine - although nothing will be vended.

This means that this new state machine's state transition functions will include a "create" function from the initial stock levels to an instance of Idle(NonNegativeInteger,NonNegativeInteger,NonNegativeInteger).

A real implementation could further subtype this, adding a uniquely-typed IO interface to the Idle and Credit states, passed into the create transition. The Success-returning select operations can then also use pure IO functions to mutate the IO context to one in which the physical mechanism of vending has happened.

But the implementation of a state machine exists in the expressions that return the output value, parameterise the next state, and the boolean expressions forming the "when:" guards. These are full expressions in the pure functional language I'm imagining this thing implemented on top of, so are fully Turing complete.

There is no syntactic distinction between a type and an implementation; a state machine type can be instantiated if all of its outputs have expressions giving them values (ok, singleton-typed outputs such as Void can be implied!). This is a bit like concrete versus abstract classes in an object-oriented programming language.

Chaining transitions

So far, we've only looked at transitions that accept an input value, return an output value and move to a new state. This means that state machine behaviour is defined entirely in terms of its reactions to external values. Since the values we generate for the output and the parameters of the new state are Turing-complete expressions, that is sufficient to describe any behaviour, but it's not always convenient to express complicated behaviour in an expression. Sometimes a complicated operation of a compound data structure such as a list would be better defined as a state machine in its own right.

In order to support that kind of thing, we can also support chaining transitions, which can drive state machine behaviour purely based on internal state, and so do not cause the generation of state transition functions. These come in three types.

The first kind is one that starts with an input value, but which then leads to a next state without producing a value. This next state must be a special "transient state", the rules for which are explained below.

The second kind is one from a transient state to another transient state. This has no input value and no output value.

The third kind is a transition from a transient state to a non-transient state, which produces an output value.

Transient states may not have any non-chaining transitions point to and from them. Every transient state must be referenced from at least one non-transient state through a chain of chaining transitions, starting with a kind-1 chaining transition then zero or more kind-2 chaining transitions. Every transient state must also lead to at least one non-transient state through a chain of zero or more kind-2 chaining transitions, then a kind-3 chaining transition.

Every such possible chain from a kind-1, through zero or more kind-2, to a final kind-3, is equivalent to a single transition from the initial to the final non-transient states; with the kind-1 transition defining the input value and the kind-3 transition defining the output value. They might be implemented as a set of state-transition functions that just tail-call each other, but the transient states are therefore "hidden" inside the state machine from external perspectives. Those state-transition functions are lexically local to the exposed state-transition functions implementing the equivalent non-chaining transition.

But although they are hidden from users of the state machine, a subtype of the state machine can indeed "see" them for purposes of splitting them into substates, adding transitions between them, etc.

Termination

The final thing I've not covered above is terminating state machines. There's an implicit "final" state available in every state machine, if at least one transition to it exists; no transitions from that state can exist. Any transition to the final state appears in the state transition functions as a function that returns the output value, but not paired with a new state machine instance, because there isn't one. It's gone.

It is entirely possible for a state machine to have no non-transient states apart from the initial and final states. For instance, a state machine that traverses a tree and sums up the labels on the nodes might be implemented in terms of transient parameterised states for the current position in the tree and the running total, with an kind-1 creation transition that accepts the tree as an input and a kind-3 finalisation transition that returns the count. This machine will therefore have a single state transition function - from Tree to Number. The actual state of the machine is entirely represented as state parameters passed between mutually recursive functions implementing the chaining transitions, and never appears as a value visible outside of that.

Conclusion

I think I've defined a workable semantic model for state machines that can be used as a way to define sets of pure functions between instances of state machines, that can handle both synchronous state machines driven by external events, and those that bumble around a data structure or iterate mathematical operations.

It needs a proper syntax; personally, I'd prefer one based on s-expressions or IRON, but suitably consistent forms could be defined for any language.

On This Night (by )

Like with Brexit I kept saying it was going to happen and people said it couldn't but it did and it's pretty scary - there is a smarmy rapey, racist homophobe who lies and cheats and looses billions of dollars and bales himself out from charities he's supposed to run and HE got into the White House. A man who throws tantrums is in charge of what I think (but maybe wrong) is the larges arsenal of nukes in the world.

This is scary and heart breaking and obviously anyone who who's looked at history can not help but see the similarities as we go round the cycle of violence once more. Of course this is playing havoc with my near near future dystopia series - the Punk's Universe I have been working on for getting on for a decade and some of which actually dates back to when I was like 14!!! ie the 90's!

The current books are near future but it is supposed to be an alternative history thing... this is the Facebook post I whacked out on it last night:

SO when I was planning my zombie quintette based in the Punk Universe I researched various things - one of the stories follows an apocalyptic cult (I made up) they consider themselves to be a direct line via mothers back to Fatima Mohammed's daughter - they are awaiting zombies and the falling dead of the faithful brought about by a pink/orange devil who gets mistaken for the 2nd coming (I think it was 2nd anyway) main issue is the description of the saviour is also of someone with skin and hair of fire... so in my story I chose a Trump faximial and a red headed half celt half arab who takes after his father in looks and has the red blush face is a muslim and one of the heros though the lesbian mother of his child is the main protag. Considering events that I had pre-empting the Z-times were Britain leaving the EU, Trump becoming president, food banks etc.... getting hit by dirty russian radio isoptopes and a targeted terror attack that wipes out the police et al ready for security corp take over - then there is a 5 way zomb-apoc with disease, drugs, mind control and rocks from space.... resulting in humans mainly living on sea steds. I'm kind of a little concerned that perhaps I should stop writing as it's getting all fooo and wooo and did I mention Essex gets flooded due the ice caps melting and the barrier failing... (and yes I did nick alot of it straight out of the dreams I had whilst sparked out from head injury but the main story line events have been in place for almost a decade now I just did not know the details!)

I also wrote a poem because as the news poured in and people started looking at the date and a) it is the mirror date for the terror attacks on the US 9/11 in the US date writing system verses the 11/9 - of course in the UK it was a 9/11... for numerologists and others who do fortune telling this would seem very important and not a good sign. Then the date analysis began to poor in, coincidence and serendipity reigned - 27 years since the Berlin Wall came down - a symbol of oppression, division and what we thought of as the last echo of the consequences of the second world war.

Then it turned out to be the anniversary of Kristallnacht - of the Night of Broken Glass when the Germans raided, vandalised and murdered focusing on the jewish population in their midst. For me this is one of the scarier and more profound dates and marked a turning of events, it marked the beginning of the escalations that lead directly to the death camps and the horrors of war.

Of course as the day progressed more and more dates where thrown into the mix - many Nazi related and though any given date can offer up the same sort of profound relatedness it does set an uneasiness in the heart.

I watched my social media fed in fascinated horror as my side - the "good side" began to undo themselves with shouts of breaking democracy and calls for assassination - and yes most where in jest and if I had a crystal ball or sure way of divining the future then perhaps we could say... yes this is the thing to be done - but we don't so it is just murder and vigilantism and a whole new pandoras box. It also marks a deepening of the divide, as our societies globally become more and more dipoled and that skism is far more dangerous than the buffoonery of politics. They only have the power we give them...

And the apathetic grow - "BORED" of politics - mainly because most people of my gen have never seen anything they've voted for happen. Out numbered and powerless feeling there are two options for the stability of mind - switch it off - politics like the weather is something you can not change if you are working or middle class or become an activist. This too grooves the trenches of the divide wider - interestingly people are not dividing along traditional lines which will need further analysis.

Me and Alaric got heavily grilled by confused 11 yr old girls puzzled as to how someone like Trump could even be considered for leader. I fear for the kids future but have to hope that the US have fail safes in their system (how long before he's impeached?).

What really really sickened me though was a report that our government is considering alining with the US and Russia!!! My god just no... are they looking at the same world I am?

US is playing the Germany of the 30's, we're the Italy and Russia gets to play itself - I wonder who's going to play the part of Japan. And I hope I'm wrong, I hope I'm over reacting. As I said with the Brexit stuff I want to be wrong... for all our sakes :/

Anyway - me being me I wrote a poem:

On The Night

In between wired breaths my lungs choke and spume
Thoughts of ire lost within as I await the gloom
The nights are rolling in once more
This night is a special one for sure
For there an egg of hope was laid
For there an egg of chance was bade

Shell fragments rained in a cascade
As the dreams of life began to fade a
Delirium of life’s serum a sugary syrup coat
Scattered as fine powder residue with one large fragment
Upside down an opalescent boat
Toppled and teetering it was drawn and consumed within
Glittering in the palp and puss of the albumin

Revealing sticky and congealed
A sickly man who’s heart with the heat of hate has filled
He sits enthroned in eagles glory
Adjusting and changing and faking the story
Too tell of things how he sees fit
And the knives and glass shards stick
In the coagulated mess of a hashed meal
Half assed, half done, half baked
And smashed for an omelette for some body builders sake

Shackles move about my wrists and the memories I was spared
Spear me through the heart from generational despair
When faith was used to justify the means
When the mean broke the night with shattered screams
When blood pooled in shallow graves
In those days
In those ways
And people laughed at those who dared to cry
When people win their freedom or when people die
And the cycle spins and on this night on this night

A breaking down of a wall a breaking of a wall
A wall... he with his crown of arian hue
Marks him proud and true, as if his blood is cleaner than mine
As if he is divine
He would build a wall
Build a wall of hate and I fear the mortar and the foundations
For we have been this way before
We know what’s in store as buildings on bone footings rise
In death stained apocalypse skies

They say these are dangerous times
Or interesting depending on where you fall
but the danger is for one and all
Fall out - is fall out - where ever it falls
And the nukes are nestled waiting and staid
Waiting and waiting there are dues to be paid
And Jews or muslims or... who ever to raid
because they are designated “bad guy”.... they...
They look different... they speak different... they wear differences... they...
Monster... other
Smother and crack down
In the pound
Out the pound
Loose the pound
Gold teeth are melted down
Shhhhh the hiss of gas is the only sound

And when midnight comes there is no reprieve
But amnesties day is coming...
Holocaust memorials strengthened against crumbling
Remembrance of the suffering
Marked and marked and marked
Show the long shadow for this is it
trying to solidify on the fears
To grow strong on the tears
To be multi headed python a hydra that sets it scores
Dividing us by our flaws

But remember they are people like us,
With hopes and memories shared by us,
A part of us, Who are us
Remember the battles fought and don’t sink the stone
Of blood letting and pain
The tide has turned but that does not mean it can not turn it back again
With love, with hope
With each little gesture we make

They are coming from the recesses of collective nightmares
Militia, curfews and a heady clown
One show to rule them
Entertain and bind
Humanity is only skin deep for most
Peer to peer to peer they are kept in check
The harsh the barbarous and savage lurks
In all
And to that nature he has called
Prepare yourself for in the end
The greatest enemy of all is self
Selfish self absorbed self
Do not leave your compassion on a shelf
The need grows

Love and love and love is how it should always go
For assassinations call makes you mirror him
Strengthening that which you hate with underpins
Creating idols, myths and martyrs,
Figure heads of examples to follow for starters
Beliefs to bellow and entrench yourself in
In the tomb
Hoping heaven has enough room
Something you’ll fight to the death fore
Something that gives people their core

In between wired breaths my lungs choke and spume
Thoughts of ire lost within as I await the doom
The nights are rolling in once more
This night’s a special one for sure
For an egg of hope is laid
For an egg of chance is bade

Remember second chances are rare
Of third chances....
Please take a care.

WordPress Themes

Creative Commons Attribution-NonCommercial-ShareAlike 2.0 UK: England & Wales
Creative Commons Attribution-NonCommercial-ShareAlike 2.0 UK: England & Wales