Software with formal properties at a low cost through monads and co-execution

Not so long ago a good friend of mine mentioned his need for 'formal properties' in his code.  

I asked him if he had already made the code purely monadic. He had. "Good", I said, "because the 'cheap route to formal properties' is first to ‘monadize' your code, and then 'reverse it' by bringing in 'co-execution'".  That last part needs some development. 

Formal properties are not only about execution, actually mostly not about execution, but more about formal properties of state. So while you do need to show execution invariants, you often much more need to show that the ‘results’ happen within stateful invariants (e.g. of the ledger). The easiest way to do this is to  deconstruct / co-execute the state model backwards. This 'backwards' logic must 'match-up' with the 'forward execution' (monadic) model. My view has always been comonads are easiest for this, especially if your stateful model (e.g. a blockchain) is already something that is easy to express as a comonad. 

You might note that my last post is all about combining 'forward' and 'backwards' arrows. One way to interpret these arrows is 'right arrow' for monads, and 'left arrows' for comonads. And sure enough, that is an easy way to sketch out higher order systems where adjoint invariant properties (e.g. rights, expectations, authorizations, ...) are assembled 'with good properties' by design. As mentioned in previous slide, monads are easy to express as CPS, and as are comonads with a bit more 'gymnatics' (see previous post).

All original content copyright James Litsios, 2022.

Why Use Arrows and PowerPoint to Express Software Designs?

Dog Drives Car 

Silly me shared the following picture with my sister-in-law yesterday,

as she was stuck in a massive traffic jam with her dog (in photo) in her mini. 
"How did you make the picture" was the question. "PowerPoint" was my reply.

I used PowerPoint for that photo because it took me three minutes, and I had a slide deck open.

Stop, you might say, this has nothing to do with programming, or software designs! It does if we want to design a software where a dog drives. Yet how would we approach that? Here I tell you how I have designed and communicated designs of 'big and bold' softwares quickly and with good properties. And will also sketch out how to approach exotic requirements, such as dogs driving cars.

Arrows Away!

Let me show you how I work. This how I use to draw design 28 years ago (from my PhD thesis):

This is how I would have drawn that design 18 years ago (~2004):

Here I use arrows to represent flows. Arrows are used to capture the Lagrangian interpretation of flows (e.g. as stream oriented design). In this case: for a given set of inputs, there is one or more sets of models, and for each of these sets there is a solver. If this sounds confusing it is, as it was ambiguous. It is ambiguous as it is not clear which flows we are talking about. Are these flows of the actual simulation calculations (e.g. variables of the simulator, this was a simulator), are these flows of structural data dependencies (e.g. how big each array is), are these flows of types (e.g. real vs complex). The solution to that problem in 2004 was to draw multiple flows. For example, here we have the flow of configuration, and the flow of object hierarchy:

Note here I introduced these flows as Lagrangian, meaning we are 'moving along with the flow'. When implementing flows, there are always a 'outside observer' view of the flow, the Eulerian interpretation (e.g. a CPU core's view). These can also be drawn with arrows (e.g. see my 'old' stream processing video). In 2004, I would have used two different arrow types to show the difference of flow representation. For example in this diagram the 'stream processing solver engine' produces 'a stream of variable data': 

Let's mention the strong influence of multi-stage programming on some of these 'notation concepts' (see Walid Taha ~2000 work referenced here) as one way to think of these arrows would be like this:

However, such a notation implies that the 'telescoping flow' has its own semantics, and that is tricky. An easier approach to draw something like this:

The idea being that the solver 'thing' is specialized with a model 'thing' (returning a new flow thing), which we can then specialize again with a variable 'thing', resulting in a 'fully formed flow thing' that includes the solver, model, and variable details. Importantly, we are no longer 'telescoping' things when we do it this way. Therefore one learning is that 'telescoping' is one representation, others are possible.

Holy Trinity Continuum

The notion of telescoping is much associated to monads. While the concept of 'specializing something with something else' is often implemented with with comonads. Yet this is not critical information to know. The reason being that monadic like logic can be expressed with continuation passing style (CPS), and again can also be expressed in defunctionalized forms (see this early ref).  We have something that looks like this:

Even better, we have something that looks like this (correct me if I wrong, I am writing this fast today):

This last diagram is 'my holy trinity' of programming design belief, as I do not need to worry if a design will be implemented with types, closures or functions, as one can always be mapped into another. Instead, the key concept is that a design should express what is invariant no matter  'how it is implemented'. Said differently, designs are best when they express invariants that hold over multiple variants of implementations.

Notes:

• CPS is really functions + a more or less complex scoping logic implemented across the functions.
• Things are a little bit more tricky when we interpret things backwards. Still similar concepts  hold.

Scoping Invariance

A primal invariant to mention is about 'variable scoping'. (The applicability of the concept is broader, and applicable to containers with access by indices versus access by search). Early languages noted two fundamentally different approaches to 'variable scope' semantics, the so called static and dynamic scoping. Dynamic scoping is still much a curiosity to developers in 2022. However, Richard Stallman writes: "Dynamic scope is useful".  So what gives? The trick is that we need to restrict the dynamic scope semantics to make things scale. A good choice to limit dynamic scoping to have only 'one point of variable access'. With that we have the following symmetry:

• Static scoped variables are 'defined at one place' and possibly used many times.

• Dynamic scoped variables are 'defined possibly many times' used used 'at one place'. 

An 'semi-formal' insight is that dynamic scoping is static scoping 'running backwards' (with the restriction above). In a simplified arrow form, this looks like this, indicating an invariance correspondence between static scope going forward and dynamic scope going backwards:

Inspired by this, my notation rule is: arrows that go left-to-right are symmetric to those going right-to-left. Often just the direction is needed. For example, in the following diagram:

If A has a static scope, B has a symmetric dynamic scope, and vice-versa.

Directional Invariants

There are many software invariants. Many of them have their roots in the notion of 'sequence of effects'. For example, if we write something, then to 'read it' is just like 'to write it but backwards'. Here too we can use arrows to capture these relations, for example:

Again, the idea is: if a left-to-right arrow has a design feature, then there is matching 'reverse logic' right-to-left arrow with a 'complementary design feature'.  I have about 10 of these invariant symmetries that I use 'all the time' to design, and a broader list of over 50 symmetries that I like to refer too.

Arrows and Dimensions to Help Design Software

I have been practicing to 'think backwards' for over ten years. (I sound incoherent when I forget to 'switch that mode off'). You may well wonder what 'running backwards' means. Luckily the following 'equivalence heuristics' help:

• While we 'execute forward' we can accumulate a lazy execution of reverse logic which we can run 'at the end' of the forward execution. At which point the reverse execution will be run forward, yet it will still be the reverse logic. (This is how reverse mode auto-diff is done).

• We go 'up' the call stack, after going 'down'.  Similar to the previous bullet, we might say that we go forward as we go down into function calls, and go backwards as we return out of each function. 

• A two phase commit has 'forward computation' in the first phase, and 'reverse computation' in the second phase.

The important insight here is that reverse logic does not need to be run backwards. Yet it does need to be 'arranged in the design' to have a proper 'reversed logic'. Therefore we do not need to draw reverse logic from right-to-left if we have a way to indicate that it is 'forward execution that manages backward logic'. I use the U-turn arrow for that. The previous example can be drawn as:

Nothing imposes directions, therefore the following is a perfectly valid design sketch:

By which I am saying: the design will verify things, accumulating a reversed execution logic which will be interpreted. 
You may note that I am being 'very one dimensional', limiting myself to a left and right direction. We can in fact introduce as many dimensions as we want. Two dimensions (horizontal and vertical) often suffice to describe large architectures. (Sometime more dimensions are brought in with 45" or 30" and 60" degree arrow directions). For example, we may indicate our I/O logic 'vertically':

When we combine the two, we might indicate the following two designs:

Which one to choose?
Both!
One way to read these designs are as follows:

• 1 top: while we write we accumulate to confirm the overall 'write commit' only when 'all writes' are valid from a 'reverse perspective'.

• 1 bottom: While we read we interpret.

• 2 top: To verify we read 'the past':

• 2 bottom: we can 're-interpret' the past by writing.

A careful reader might note that while we may want 1 and 2, we cannot just have them! The issue is that when combined, we are mixing 'left-to-right' and 'right-to-left' arrows 'of the same thing'. For example, 1 has Verify as a U-turn and 2 as Verify as a left-to-right arrow. That will not work, as one is the 'reverse direction' of the other. 

Further Directional Invariants

There are many important software design concept. Here are three more, expressed with complementary arrows:

In simple terms: A coherent design does not have complementary design concepts 'at the same level'.  What the above is saying is:

• Both a local and global design must be expressed, and both are complementary. 

• Providing authentication allows us to 'look back' with trust.

• If new 'things' are 'freshly' created, then at some point they become 'stale'. And two complimentary design logics must be designed to deal with this. 

With that in mind, the previous two designs can be brought together as as single coherent design:

To note that this is how I was designing software early-2015 (see my pre-Elevence post).
(I leave the reader the reader the exercise to bring in authentication, trust, freshness and staleness).

Semantics, Tools, and Teamwork

Given a team of developers, I might suggest that design 1+2 be implemented with local monads and a global comonad (e.g. as a blockchain). Yet once I do that I lose flexibility. I also lose my audience. Instead I draw arrows, and explain what I mean with these arrows. I say what properties we 'the development team' are looking for, and sure enough we end up with a decent design that is robust and strong.  Drawing design 1+2 takes just a few minutes in PowerPoint, and maybe would have needed a few tens of minutes to sketch out before (e.g. on a sheet of paper). Typically, I duplicate my 'master design slide' many times, to then add annotations to show how we might 'slip in' extra design requirements. For example, the notion of trust and authentication, and here, the logic to deal with 'staleness'. 
I started this post with a picture of a dog driving a car. The important property of a software design is to be 'consistent by design'. Were I to design a 'dog driving car' software design. I would start by sketching out the complementary properties that I would need to bring in to the design. These might me:

Then I would draw these in PowerPoint and iterate and grow to create a good design.

All original content copyright James Litsios, 2022.

Software designs that grow with monads, comonads, and type compatibility

This post is about designing software with internal and external APIs that are robust to future changes. It is therefore about API compatibility, but more importantly it is about the compatibility of a full software design to changes. Not surprisingly, monads and comonads are part of the presented solution, as is a careful approach to use of types.

I had a "aha" moment last year when I watched a video (by Timothy Baldridge)

that showed how an AST for a Clojure compiler was fully based on key-value pairs (nested hash maps), therefore without typed structures nor classes, and was doing very well. The thing is, I have suffered enough times to get the types of the different phases of a compiler to fit together. Therefor the idea of giving up on types and just using key-value pairs, that can easily be added for each compiler phase, seemed really to be an attractive way to write a compiler.

Key-value pairs, duck typing, and many "traditional" functional patterns (think lisp, not Haskell) have all in common their reliance on generic, almost typeless, structures. So while each "atomic element" of these patterns has a type (e.g. int, string, ...), the structures (e.g. struct, list, array, ...) are all generically typed.

Types are what capture the invariants of a design. Giving up on types is in effect giving up on capturing those invariants in a robust manner. Using types normally leads to higher quality software, yet with enough complexity, types no longer capture all the design invariants of a program. Worse, sometime types actually hinder the design by holding it back because they are not powerful enough to capture the desired invariant. This is the case with the difficulty to design an typed AST that "fits" all phases of a compiler. This rigid nature of types is also the hidden problem of API compatibility.

The invariants of APIs are captured with the types of their signatures. When new features or corrections are added to an API, these invariants and associated types evolve. When APIs link different software projects, changing API types is where API compatibility becomes an issue: APIs remain compatible when types change but remain compatible with older types, APIs become incompatible when the types are no longer compatible. An example of type compatibility in OO, is to derive a new class from an existing class, and to add a constructor in this new class from the old class. Unfortunately, that last example is at the source level. At the binary level, compatibility to type change is usually nonexistent, especially when focusing on forward compatibility. Note that API compatibility is not only about types: an API will also become incompatible when the interpretation given to values transferred over the API changes. Therefore to remain compatible, an API can add new value interpretations but must also ensure that past value interpretations never change.

Serializing data for transport and for storage is much about breaking program defined types into language standard basic types, and keeping a strict discipline of interpretation to ensure compatibility. Therefore ensuring both backward and forward compatibility of an API is to maintain a strict growth of value interpretation and to use serializing packages like Protocol Buffers or Thrift. The question is then: how do we ensure the future growth of a complete software design, not just a single API, but a family of APIs? Just like with the single API, the answer also lies in the notion of serialization. The goal is to stitch together the typed lower level design with a higher level untyped design that can change over time.

Data is serialized by walking through it a certain order and breaking it down into its primitive types. Programs can be broken down the same way. Yet to do that, your first need to adopt a functional programming style because it is hard to serialize procedural constructions. In a functional style, only functions need to be "broken down".

In the good old days, scalable software design was about using construction such as data schemas, object patterns, futures, continuation style, etc. Data schemas are still good, but all these other program constructions elements must be revisited with the fact that they can all be implemented with monads and comonads. More importantly, they must be revisited because the bind and cobind operator (and other monadic and comonadic operators) is what serializes functions! Therefore, just like you must serialize your  data schema to ensure future data compatibility, you must "serialize" your functions with monads and comonads to ensure future design compatibility.

Here are few examples of existing designs that do this:

• Injection frameworks are comonadic constructions. 
• Transactional frameworks are monadic constructions.
• Parallel tasks are monadic constructions.
• Embedded queries are monadic constructions.
• Reactive streams are monadic constructions.
• Lenses are comonadic constructions.
• Automatic differentiation (computing analytical derivatives of numerical code) are both monadic (forward differentiation) and comonadic (backward differentiation).

Just like data compatibility is tied to the order in which data is traversed, future design compatibility is tied to the "order" of function serialization. That is to say that each software design is strongly defined by the order in which functions are broken into monadic and comonadic constructions. While monads and comonads have a duality relationship, they fundamentally differ in "character": monads are "trace" centric, while comonads are environment centric. Said differently, conditional expressions can be monadic, while comonadic expressions can abstract away their environment. A design is then a chosen hierarchy of monads and comonads with chosen set of API extension points.

Just like with data compatibility, future design compatibility is tied to the amount in which types can be changed and remain compatible. And again, to differentiate between the need of source compatibility (e.g. for component designs) and binary compatibility (e.g. to design distributed systems). Use strong types to build your design when your programming language offers a type system that ensures that forward design compatibility is supported by forward type compatibility. Limit your reliance on types when these do not provide this forward compatibility. If this limited use of types, or the limits of the type system, do not allow monads and comonads constructions to be expressed with types, then use typeless/generic bind, cobind, and other monadic and comonadic like operators (e.g. duck typing on key-value pairs). 

Finally, use only the language features that allow you to break down your functions into monadic and comonadic constructions. For example, only use destructive assignment if you can model it within your monadic and comonadic design. Also,  do not forget you need also to enforce a "growth" only rule for your interpretation of values.

Now having said all this, you cannot build a design if it costs too much or if you cannot explain it to others. For example,  I wanted once to upgrade an algorithmic trading API around a monadic construction (within a C++ framework). I communicated around prototypes and presentations, (I was CTO), yet failed to get across to my key team members (who where top notch developers), and ended up canning the idea.  And this brings me back to a few important issues:

• Monadic and comonadic constructions are higher order, even if you do not implement them with higher order types, you still need to think of them as higher order invariants hidden in back of your design. This is like a mathematician would "see them", and is not obvious from a classical procedural or OO background.
• The cost to implement typeless/generic monadic and constructions within your language may simply be too high. 

For example, concerning this last point, this week I wanted to implement a duck typing pattern in Java  on top of Protocol Buffers objects (for all the reasons mentioned above), but Protocol Buffers is only efficient if you access fields in a typed manner. So even while I could see how to build a design with a robust algorithmic binary compatibility model, the cost on performance would simply be too high to do it on top of Protocol Buffers.  (Luckily using Protocol Buffers is not a requirement for this project so I can move to another data serialization protocol that supports fast generic field access).

As an end note: I understand that I am not telling you in this post "how" to write monadic and comonad style constructions, especially without a functional language. What I am telling you is that you want to know how to do this if you want your designs to grow well.

All original content copyright James Litsios, 2015.

Introduction to state monads

I went to my first Zurich FSharp meeting the other day and made a presentation on how to program with state monads in F#.

The presentation is designed to pull you off the ground, to a higher order programming style, using the state and maybe monad as stepping stones. It finishes with stateful lifting.

Here is a link to a slightly improved version: youtube .

Link to sources are below but I would recommend that if you really do not know this type of programming and want to learn, then you should type it back in and allow yourself some creative liberty. This is usually a much better way to learn, than to just copy code!

You can watch it here if you want:

ModularStateMonadsInFSharp.pdf
XState1.fs
XState2.fs
Script.fsx

Where is my state?

People often associated functional programming with statelessness. The reality is that there is always a notion of state, functional programming is about stateful programming. The ambiguity is probably the result of state appearing in different ways than in a procedural style.

In a procedural style, state is associated to memory and you change it by using the writable property of memory.

In a functional style, state is still in memory  but the “classical” approach is to disallow yourself from changing it by writing again over memory. This is the immutable programming style. It goes with functional programming because it is very difficult to build on immutability without some functional programming concepts (I have tried!).  So if you have state and you cannot write over it, the only thing you can do is to read it, and if you want to change the state, you need to write a new memory location with your new state value (a non-functional  near immutable approach is to use arrays and grow them). The problem for beginners is “where should that new state be”?  It needs  to be accessable, and while you maybe knew how to access the old state, where should you put the new state so as to be able to work with it, instead of the old state?
Recursiveness is then the first  way  to manage state; The idea is that if you have a function F that works with state, then if you create a new version of the state you can simply call F recursively  with the new state, and again and again with each new version of the state.

Recursiveness is always somewhere nearby if you are using immutability; Yet you do not need to expose it to manage state. Again, suppose a function F uses state, have it return its state after use, if the state has not changed, then  return it unchanged, if the state changed, then return its new version. The trick is then to have a loop that calls F with the state, then takes the returned value to call F again, and so on. As this is immutable code, the loop is a small tail recursive function.

State can be big and heavy, and not for the wrong reasons, your application may be a big thing. The last thing you want to do is to copy that whole structure just to make a small change. The simple approach is to reuse parts of your old state to make a new state, changing only what needs to be changed. Yet  as the state is usually a tree like structure, if what is changing is deep in the original state, then it will cost you to create a new state because you will need to rebuild much of the hierarchy of the state. One way around this is to take the old state, encapsulate it in a “change of state” structure and use this as the new state  This approach is what I call a differential approach: the state change is the difference. By stacking differences you build a complete state. Usually the differential approach is combined with the “normal” partial copy approach. The reason is that if pursued forever, the “stack” of state changes become too big and starts both to consume memory and take time to access.

In the end your new state will either leave your function “onwards” into recursion or backwards by return, and often the same algorithm may use both methods.
When beginning with the functional style, state seems to be forever a pain to drag around. But with time patterns appear. First you may notice that not all states have the same lifetime, and they do not all have the same read write properties. It is a good idea to try to separate states that have different access and update properties.  You may then note that the hierarchy of functions aligns itself to with the access patterns of your state. Yet if you tie state to function in an layered like fashion that is classical to procedural programming you realize that what you have is not so much state as parameters. That is, while you are working in an inner function you have no ability to modify the outer “state”, so it is more a parameter like than state like. Nevertheless, with situation where states have a strict hierarchy, this approach is ok.

At some point, carrying around state becomes such a standardized routine that  it makes sense to look for help to go to the next level. And the next level is… monads. Here is the deal, I said before that states will either exit your function through a further recursion or by return.  That means that there is a set of compatible patterns that can be used to assemble little bits of code that work on state, so that they nicely fit and the state zips around as an argument or as a return value. This pattern appears naturally when your work with states: it is the idea that the state is passed as last argument and that the stateful functions always return a state. As you want the function to do something useful, you systematically return a tuplet with a state and a function specific return value. Before understanding monads,  I wrote whole applications like this. What monads allow you to do is to standardize so much this method of call pattern that it becomes possible to strip the exposed code of these “peripheral” state going in and state going out. The result is code that looks stateless but that isn’t.  The value of monadic state management is that you make much less mistakes and you can specialize your monad further to give it special properties. Still, from a stateful perspective the main gain of monadic states is productivity: hiding the state mean you can focus on more important things.

Stream oriented and parallel programming

Good software design comes to applying simple patterns; for many years now my simple pattern is stream oriented programming, and in the functional programming monads. In this post, I will introduce the concept of stream oriented programming by showing the value it brings to parallel program.
Parallel programming design has three basic patterns:

1. Sequential execution
2. Parallel execution
3. Hierarchical execution (or “compositional”, “encapsulating”; please help with name)

The two first are classic: operations happen sequentially along the execution, operations can happen in parallel along synchronous or unsyncronized execution flows. One way to present the third pattern is through hierarchical state machines (HSM) where each sate can be a yet another HSM, recursively to any depth.

Hierarchical patterns of execution are important because they are really expressing higher order properties of the solution space. Sequential and parallel patterns are good: they do work, they make things more complex; but they do not “shape” the specific nature of an algorithm; hierarchical patterns do. A good way to bring in a notion of stream oriented programming is by describing the same example hierarchical system in two different ways: state machine oriented and stream oriented:

• The “hierarchical state machine” oriented way: the system is a machine, with an application, with a socket connection that transports packets of messages.
• In “stream oriented” way: there is a machine, it starts up, it starts an application, which opens a socket, which sends a packet that contains multiple messages. Later it sends more packets with more messages, the socket closes down, then starts up again, to later close down again with the termination of the application. The application is restarted, the socket start up, etc. Again later, the machine is rebooted, the pattern continues.

Note how the hierarchical stream pattern is built of many sequential pattern used at multiple levels: the messages are sent sequentially, so are the packets; the application is run a multiple number of times, the machine is restarted time after time. Also, the messages, packets, application, etc. can all be seen as happening synchronously in parallel. Yet looking at the system as separate sequences and parallel is not good enough, from a state machine perspective it would be like considering each element of the system as separate state machines, which they are not. What is really happening is that the system is one big sequence and we choose to see this sequence as a structure of levels of hierarchies. It is exactly this notion of sequence “over a hierarchy” that the hierarchical execution pattern captures.

Most classical programming languages are built around the state of data, while “execution” state is implicit and ideally hidden. Indeed, one of the first efforts in program development was to “hide” the program counter first with subroutines and then with structured programming. A side note is that in many ways what separates software from hardware is the notion of “execution state”: hardware makes that execution state explicit.

Execution state is central to the notion of shared access to resources: a locked resource is really defining specific exclusion rule for the execution state. SQL and its variants extend the notion of implicitly managing these exclusion rules for shared resources. Multi-threaded programming is supported by different locks and basic thread operations. Yet still execution state is hidden. And for good reason, anybody who has attempted to use a thread suspension as part of their design know how impossibly difficult it is to reasoning about certain execution states.

Unfortunately, the “hidden” nature of execution state also makes it very hard to structure and scale the execution of multithreaded and parallel programs. So while a good architect may map certain computations to thread resources, it is hard to do this a systematic way; and even then, it is hard to foresee how well a parallel designs will perform. A solution to this problem taken in GPU processors has been to impose very simple execution models on the developer.  The execution state is still implicit but with GPUs it has an imposed structure: we know that multiple states of the threads all “in-line”.  It has to be said that languages like Erlang have also taken a similar approach but they too impose strong restrictions on the execution model, limiting their applicability.

An attentive developer will have noted the steady but sure growth of stream oriented and functional style programming as a “solution” to the difficulties of multi-threaded and parallel programming. Functional programming has been around for fifty years and yet would previously have never been recommended for efficient parallel execution, so clearly there is something more than “just” functional programming in making it a parallel complexity slayer. The answer lies in explicitly managing state of execution! This deserves a little explaining.

One way to define a stream is as follows:

• Repeatedly triggered by an input
• Performs I/O and computation sequentially
• Local readable and writable state
• Within a constant, read only, environment
• Drives an output

(Except the first item and the notion of synchronicity, all of the above are optional.)

Now here is the key insight: A stream has an overall state of execution! To be more precise, both the repeatedly triggered executions on stream events have execution states as well as the overall “bigger” life cycle of each stream. This is just like a socket which can be opened or closed and have individual packets running over it.

The functional style programmer may have noted the notion of stream is not far from the notion of a monad. Indeed, monadic programming shares very much the ability to have two execution states: the state seen as part of each individual monadic expression, and the whole execution state when “running” the monad. It is this property that allows monads to be a basic building block for parallel programming.

Looking again at an overall system, at any given time a stream oriented system can be seen as a hierarchy of stream flows; Each of these streams is associated to an execution state; The key insight is that an optimal use of the parallel resources of a system is found by optimally assigning these execution states to the parallel resources of the system.

You might ask: “Why is it was necessary to introduce streams, can we not write parallel systems with only hierarchical state machines”?  As we have seen in the system description above, HSMs and hierarchical stream patterns are really very similar. In fact the stream pattern can be seen as the edges of the transition graph of the state machine. (It is a form of data differentiation of the hierarchical state machine pattern). A single graph has usually many edges, therefore it by assembling many stream oriented patterns we can build equivalent HSMs. We know now that stream patterns have two levels of state execution, and that good parallel design is about smartly assigning execution state to parallel resources, and finally we know that by combining many stream patterns we can build hierarchical state machines. The result is that stream oriented programming is more modular and flexible than direct HSM type programming:

• Each stream can be assigned locally to execution states,
• The compositional property of streams allow them to adapt both to algorithms as well as to parallel topologies ,
• The dynamical nature of their assmbly allow them to be reconfigured quickly.

 

(A few years later I recorded this presentation on stream oriented development)

Immutable, mutable, higher order designs and monads

One of the great pleasures of programming functionally is to be able to rely on immutable data. With immutability, side effects need to be explicitly defined, either as return values from functions or as encapsulations in monadic states. Immutability allows two important properties: first it increases productivity by diminishing what needs to be cared about (freeing the mind to care about the right things!), then, almost as more importantly, it provides the foundation for higher order programming concepts by preserving an acyclic relationship between functions and data. By higher order, I mean that data is replaced by functions or that functions encapsulated in data; for example, in a context like data differentiation or in the use of monads. By acyclic, I mean that all trace trees are acyclic (trace tree can be seen as dynamic call graph where recursion is not a loop). Let me explain…

It is OK to have cycles in the static call graph. That is because we know how to infer invariants (e.g. like types) from inter-dependent and recursive functions. Likewise, recursive data types are also OK. Nevertheless everything is a bit trickier if we look at things from a data flow dependency point of view. This is the view we need to take if we really want understand how the functions are working on data and producing new data. And the sad reality is that it is generally hard to work out invariants from dependency graphs that have cycles because of mutable data, Nevertheless, there are cyclic dependency graphs that are easier to work with than others. More specifically, the more local, or of limited life span, a part of the dependency graph is, the easier it is to understand it scope and properties.

I mentioned trace trees above because they give me the bridge I need to wrap up this posting. The insight is the following: mutability brings in cycles in dependencies, cycles in dependencies kill invariants that allow higher order code constructions, trace trees are a down to earth way to work with dependencies, monads can seen as redefining call points in the trace tree (nodes), and as a consequence one the safest way to introduce mutability is within the scope of a monad. Again, we know the local trace tree will end up with cycles when we introduce mutability, but if this trace tree is “protected” in a monad, then its impact into the rest of the trace tree is easier to understand because of the intimate relation between monads and trace tree nodes.

You could argue that we do not need mutability. Yet real world I/O is mutable and therefore you you cannot escape working with mutable data. Not to mention that to get performance you may need to go mutable too.

C++ and functional programming

What to say to C++ programmers about functional programming, especially now that many compilers have implemented C++0X features like lambda and auto. I am pretty good at C++, having started using it with the Zortech compiler V1 and the first versions of CFront (the orginal C++ to C translator). I have also written much fancy template code. Therefore thinking about this post leaves me in the dilemma that there is one part of me that likes the features of C++0X that "wrap up" loose ends, and another part of me, the functional programming part, that makes me want to rant! I will not rant today, but part of that reasons for being upset needs to be said, as is relevant. The "magic" of mature functional programming are:

• Statements, expressions, functions and types support each other
• Type inference and polymorphism automate the relation between statements, expressions, functions and types
• Monadic and other "advanced" types are available to define new execution models such as parallelism.

C++ templates can bee seen as a primitive functional language. But I would argue against going into production focusing on C++ templates that way as I have been burnt so many times by C++ compilers failing me with complex templates, not to mention the difficulty to hire for this skill So template functional style is not where the emphasis should be. The real issue is that although C++ expressions have a C++ type counterparty (think operators like + and -), there is no C++ type support for statements. As a result many of the core concepts of functional programming cannot mapped across C++, even with the new C++0X features of lambda, garbage collections, auto, etc. My recommendation is that some concepts should be understood by C++ developers but not necessarily with a functional emphasis. My favorite topic is as always monads. In the C++ terms, monadic concepts define properties on the "traces" of the code. If we say: f(...); g(...); then the execution trace of the program will first have gone through f and therefore when g is called, properties set by f may still be valid. A good C++ architect should understand enough about monads to define invariants that can be used in this type of trace oriented context. For the moment, I would forget about other "functional programming concepts" in C++, even if it is C++0X!