DEV Community: Logan Mortimer

Cellular Automata in F#

Logan Mortimer — Thu, 03 Dec 2020 00:50:25 +0000

Rule 90

Simple rules can generate complex behaviour. I'm reading A New Kind of Science by Stephen Wolfram. A key idea of the book is that a simple rule, applied iteratively, can generate complex behaviour. The difference between Rules 222, 90, and 30 are trivial, yet they generate vastly different results.

In this post we explore the principles and implement the Elementary Cellular Automata system in F#.

Rule 222

Rule 30

Cellular Automata

Here's a 7 x 4 grid. The dots represent Empty cells, the X represent Full cells. All of our grids start with a single Full cell in the middle of the top row.

...X...
.......
.......
.......

We then define a rule. A rule is a function which decides whether a single cell is Empty or Full. This rule function takes values of the 3 cells from the row directly above, corresponding to the cells above and to the left (1), directly above (2), and above and to the right (3). We visualise this below. The cell we are trying to calculate is ?.

123....        .123...        ..123..        ...123.        ....123
.?.....        ..?....        ...?...        ....?..        .....?.
.......        .......        .......        .......        .......
.......        .......        .......        .......        .......

The same rule is applied row after row. The rule is not applied to cells in the far left column and far right columns. These cells will always remain Empty. We'll look at the naming convention of rules later on, but for now here's one example.

Below is Rule 222. The first pattern is saying that if cells 1, 2, and 3 are Full, then the cell ? will be Full. And so on, for every possible combination of those 3 cells.

XXX    XX.    X.X    X..    .XX    .X.    ..X    ...
 X      X      .      X      X      X      X      .

This system of rules is as simple as we can get. Each cell can only have two possible states, and the value of the next cell only depends on it's neighbours.

Rules as Code

We just described the Celluar Automata domain. Let's implement it in code.

A Cell can be either Empty or Full.
The Rule type is a function which takes 3 Cells and returns the value of a single Cell.

// A Cell is either Empty or Full
type Cell = Empty | Full

// Rules are functions which take in the values of 3 Cells, and return a single Cell value
type Rule = (Cell * Cell * Cell) -> Cell

// Rule 222 implemented in code
let rule222: Rule = function 
    | (Full, Full, Full) -> Full
    | (Full, Full, Empty) -> Full
    | (Full, Empty, Full) -> Empty
    | (Full, Empty, Empty) -> Full
    | (Empty, Full, Full) -> Full
    | (Empty, Full, Empty) -> Full
    | (Empty, Empty, Full) -> Full
    | (Empty, Empty, Empty) -> Empty

Modelling the Grid

We've just described the Cellular Automata system in its entirety. Patterns and complexity emerge from just those rules. The rules by themselves are abstract and we need to apply them somehow. Here we apply the rule on a simple grid. But the same rule could be applied to any other surface - a 3D surface, mobius strip, or grid where the values wrap around.

Onto the implementing the system on a grid. Let's start off by generating the first row.

let generateStandardFirstRow (width: int) =

    if width % 2 = 0 then invalidArg "width" (sprintf "Value must be an odd number. Value passed was %d." width)

    Seq.init width (function
        | n when n = (width / 2) -> Full
        | _ -> Empty
    )

generateStandardFirstRow 7

Gives us

Empty Empty Empty Full Empty Empty Empty

In order to generate the next row we only need to know the row before it. We take the previous row and apply Seq.windowed. This splits the row of Cells into groups of 3 Cells, which we need in order to calculate the next value.

Recall that our rule requires 3 cells in order to calculate the next value. This is the cell above and to the left, the cell directly above, and the cell above and to the right. This is a problem for the far left and far right columns of the grid. They only have 2 of the 3 cells required. To get around this we enforce a rule that the left column and right column will always remain Empty.

let generateNextRow (rule: Rule) (row: Cell seq) =
    let generatedCells =
        row
        |> Seq.windowed 3
        |> Seq.map (fun v ->
            rule (v.[0], v.[1], v.[2])
        )

    // the first and last Cells of each row are Empty since we didn't generate a value for them above
    seq {
        yield Empty
        yield! generatedCells
        yield Empty
    }

Now let's write a function which generates row after row. Sequences in F# are lazily evaluated. They're the C# IEnumerable type under the hood. By treating everything as a sequence we're essentially defining the rules as to how the grid will be generated.

Seq.unfold iteratively applies the Rule to whatever the previous row was, collecting results. Notice we don't specify how many rows to generate, that's up to the caller of this function.

let generatePattern (rule: Rule) (firstRow: Cell seq) = 
    firstRow
    |> Seq.unfold (fun row ->
        Some(row, (generateNextRow rule row))
        )

Now we can generate the grid!

let firstRow = generateStandardFirstRow 101
let rows = generatePattern rule222 firstRow |> Seq.take 10

But we want to visualise it. Here's a basic ASCII renderer.

let drawCell = function
| Full -> "X"
| Empty -> "."

/// Render the grid to an ASCII string
let drawGrid (grid: Cell seq seq) =
    grid
    |> Seq.map (fun row ->
        row
        |> Seq.map drawCell
        |> String.concat ""
    )
    |> String.concat "\n"

drawGrid rows

..................................................X..................................................
.................................................XXX.................................................
................................................XXXXX................................................
...............................................XXXXXXX...............................................
..............................................XXXXXXXXX..............................................
.............................................XXXXXXXXXXX.............................................
............................................XXXXXXXXXXXXX............................................
...........................................XXXXXXXXXXXXXXX...........................................
..........................................XXXXXXXXXXXXXXXXX..........................................
.........................................XXXXXXXXXXXXXXXXXXX.........................................

Other Rules

Our algorithm works! Let's experiment with other rules.

let rule90: Rule = function
    | (Full, Full, Full) -> Empty
    | (Full, Full, Empty) -> Full
    | (Full, Empty, Full) -> Empty
    | (Full, Empty, Empty) -> Full
    | (Empty, Full, Full) -> Full
    | (Empty, Full, Empty) -> Empty
    | (Empty, Empty, Full) -> Full
    | (Empty, Empty, Empty) -> Empty

let firstRow = generateStandardFirstRow 101
let rows = generatePattern rule90 firstRow |> Seq.take 50
let arrayOfRows = rows |> Seq.toArray

drawGrid rows

..................................................X..................................................
.................................................X.X.................................................
................................................X...X................................................
...............................................X.X.X.X...............................................
..............................................X.......X..............................................
.............................................X.X.....X.X.............................................
............................................X...X...X...X............................................
...........................................X.X.X.X.X.X.X.X...........................................
..........................................X...............X..........................................
.........................................X.X.............X.X.........................................
........................................X...X...........X...X........................................
.......................................X.X.X.X.........X.X.X.X.......................................
......................................X.......X.......X.......X......................................
.....................................X.X.....X.X.....X.X.....X.X.....................................
....................................X...X...X...X...X...X...X...X....................................
...................................X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X...................................
..................................X...............................X..................................
.................................X.X.............................X.X.................................
................................X...X...........................X...X................................
...............................X.X.X.X.........................X.X.X.X...............................
..............................X.......X.......................X.......X..............................
.............................X.X.....X.X.....................X.X.....X.X.............................
............................X...X...X...X...................X...X...X...X............................
...........................X.X.X.X.X.X.X.X.................X.X.X.X.X.X.X.X...........................
..........................X...............X...............X...............X..........................
.........................X.X.............X.X.............X.X.............X.X.........................
........................X...X...........X...X...........X...X...........X...X........................
.......................X.X.X.X.........X.X.X.X.........X.X.X.X.........X.X.X.X.......................
......................X.......X.......X.......X.......X.......X.......X.......X......................
.....................X.X.....X.X.....X.X.....X.X.....X.X.....X.X.....X.X.....X.X.....................
....................X...X...X...X...X...X...X...X...X...X...X...X...X...X...X...X....................
...................X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X...................
..................X...............................................................X..................
.................X.X.............................................................X.X.................
................X...X...........................................................X...X................
...............X.X.X.X.........................................................X.X.X.X...............
..............X.......X.......................................................X.......X..............
.............X.X.....X.X.....................................................X.X.....X.X.............
............X...X...X...X...................................................X...X...X...X............
...........X.X.X.X.X.X.X.X.................................................X.X.X.X.X.X.X.X...........
..........X...............X...............................................X...............X..........
.........X.X.............X.X.............................................X.X.............X.X.........
........X...X...........X...X...........................................X...X...........X...X........
.......X.X.X.X.........X.X.X.X.........................................X.X.X.X.........X.X.X.X.......
......X.......X.......X.......X.......................................X.......X.......X.......X......
.....X.X.....X.X.....X.X.....X.X.....................................X.X.....X.X.....X.X.....X.X.....
....X...X...X...X...X...X...X...X...................................X...X...X...X...X...X...X...X....
...X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.................................X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X...
..X...............................X...............................X...............................X..
.X.X.............................X.X.............................X.X.............................X.X.

Image Output

Here's a graphical renderer for the same grid implementation.

#r "nuget:SixLabors.ImageSharp"
open SixLabors.ImageSharp;
open SixLabors.ImageSharp.PixelFormats;

let cols = 501;
let rows = 250;

let image = new Image<Rgba32>(cols, rows);
let white = new Rgba32(255F, 255F, 100F, 1F);
let black = new Rgba32(0f, 0f, 0f, 1F);

let grid =
    generateStandardFirstRow cols
    |> generatePattern rule90
    |> Seq.take rows

let withIndexes x = x |> Seq.mapi (fun index item -> (index, item))

for (rowIndex, row) in withIndexes grid do

    for (cellIndex, cell) in withIndexes row do

        let colour =
            match cell with
            | Full -> black
            | Empty -> white

        image.[cellIndex, rowIndex] <- colour

image.Save("rule90.png")
image

Rules

So far we've looked at a few specific rules. But how many rules are there and can we generate them dynamically? We've hardcoded rules as functions

let rule222: Rule = function 
    | (Full, Full, Full) -> Full
    | (Full, Full, Empty) -> Full
    | (Full, Empty, Full) -> Empty
    | (Full, Empty, Empty) -> Full
    | (Empty, Full, Full) -> Full
    | (Empty, Full, Empty) -> Full
    | (Empty, Empty, Full) -> Full
    | (Empty, Empty, Empty) -> Empty

All rules must return a value for each pattern. Because the patterns are static we could think of identifying rules by what they return for each case, what is on the right hand side of the ->. We could think of the above rule as:

(Full, Full, Empty, Full, Full, Full, Full, Empty)

So a rule is a identified as a list of 8 boolean values. If we use binary to represent this we need a byte (8 bits) of information. This means there are 2^8 rules, giving us 256 possible rules in the Wolfram automata system.

So there are only 256 rules in this Wolfram automata system, and the rule's name determines what it returns. This is illustrated below. The binary pattern maps 1 to Full and 0 to Empty.

128	64	32	16	8	4	2	1	Written Out	Rule
1	1	0	1	1	1	1	0	128 + 64 + 16 + 8 + 4 + 2 + 1 =	222
0	1	0	1	1	0	1	0	64 + 16 + 8 + 2 =	90

let generateRule(ruleNumber: byte) = 
    let ruleBitString = Convert.ToString(ruleNumber, 2).PadLeft(8, '0');

    let patternToBitStringIndex = function 
        | (Full, Full, Full) -> 0
        | (Full, Full, Empty) -> 1
        | (Full, Empty, Full) -> 2
        | (Full, Empty, Empty) -> 3
        | (Empty, Full, Full) -> 4
        | (Empty, Full, Empty) -> 5
        | (Empty, Empty, Full) -> 6
        | (Empty, Empty, Empty) -> 7

    let ruleFn (cells: Cell * Cell * Cell) = 
        let bitIndex = patternToBitStringIndex cells

        match ruleBitString.[bitIndex] with
        | '0' -> Empty
        | '1' -> Full
        | _ -> raise (Exception("Unexpected input"))

    ruleFn

let rule254 = generateRule(254uy)
rule254 (Empty, Empty, Empty)

And there we have it, our rule function generator. Here are some interesting rules.

Rule 62

Rule 110

Rule 150

Conclusion

F# is a perfect language to implement Cellular Automata. The type system allows us to exactly model the domain, and sequences make the implementation elegant. There's no confusing cruft in our code. From this basic implementation you can easily make modifications to the Cellular Automata system. Here's a few fun things to try out. What if ...

The first row was randomly generated
Cells could have a value other than Full or Empty?
Rules incorporated some degree of randomness when deciding the value of the next cell?
The grid was hexagonal rather than square based?

The Jupyter Notebook and an F# project containing the code for this post is available here.

This is part of F# Advent Calendar 2020. Check out other posts here.

Software Engineering at Google - The Book

Logan Mortimer — Mon, 10 Aug 2020 01:40:54 +0000

What software engineering practices does a company of 30,000 engineers need to develop quality software? Each day over 60,000 commits get made within Google by engineers and automated systems. Software development practices are quantifiable rules, not strong opinions.

Software engineering at Google has been an extraordinary experiment in how to develop and maintain a large and evolving code base - Asim Husain, VP Engineering, Google

Hey, They Wrote a Book About It

Software Engineering at Google - Lessons Learned from Programming Over Time describes how Google approaches software engineering. It's organised into 3 sections, each containing chapters by different authors within Google. The chapters are more like essays and are written in a conversational style which is a joy to read.

Culture - How to Work Well on Teams, Knowledge Sharing, Engineering for Equity, How to Lead a Team, Leading at Scale, Measuring Engineering Productivity.
Processes - Style guides & Rules, Code Review, Documentation, Testing (covered in depth), Deprecation.
Tools - VCS & Branch Management, Code Search, Build Systems & Philosophy, Static Analysis, Dependency Management, Large Scale Changes, Continuous Integration, Continuous Deployment, Compute as a Service.

The chapters cover both objective information about these topics, but also case studies from inside Google where these topics came into play. In the chapter on testing we learn about Google Web Server. I'm certain that most of us can relate to a similar codebase in a company we've worked at.

GWS is the web server responsible for serving Google Search queries… In 2005, as the project swelled in size and complexity, productivity had slowed dramatically. Releases were becoming buggier, and it was taking longer and longer to push them out. Team members had little confidence when making changes to the service, and often found out something was wrong only when features stopped working in production. At one point more than 80% of production pushes contained user-affecting bugs that had to be rolled back

To address these problems, the Tech Lead of GWS decided to institute a policy of engineer-driven, automated testing. As part of this policy, all new code changes were required to include tests, and those tests would be run continuously. Within a year of instituting this policy, the number of emergency pushes dropped by half. This drop occurred despite the fact that the project was seeing a record number of new changes every quarter.

Who Should Read This Book?

This book has a wide appeal and I would recommend it to anyone interested in Software Development or adjacent fields. New developers are going to learn a lot from the breadth of topics. Likewise experienced developers will appreciate some of the deeper dives in chapters such as Testing and Measuring Engineering Productivity (not as bad as it sounds, more on this below). Even if you're not writing code every day it's interesting to see the processes and methodologies used at Google.

I used to work at a startup and am now at a large product company. Both companies follow the typical microservices approach. Github/Gitlab for source control and reviews, code gets packaged into containers, deployed to AWS. You know, the stack that's talked about on the internet to the point of absurdity.

Contrast this to Google's stack. Throughout the book we learn about their use of a monorepo, as well as the tools they use for code review, code search, and static analysis. These were all written in-house and have evolved over years of use. Reading about the details caused me to reflect on the set of tools my company uses. It's sort of a given that you use Git, and something like Github for code reviews and search. A fun thought experiment is to take the software development stack described in the book and apply it to the company you work at.

While each chapter dives into an individual topic, the book as a whole makes no attempt to sell the value of engineering. I'm assuming it's an intentional choice, so I would not recommend this book to those who see software development as purely a means to a product or commercial end.

Favourite Chapters

Teams and Leadership

Chapter 2 - How to work well on teams, Chapter 5 - How to lead a team, Chapter 6 - Leading at scale

I learned from these chapters in 2 different areas: how the topics relate to me as an individual, and what a 'good team' looks like.
How to lead a team describes the different leadership paths one can take. At Google 'Managers' are leaders of people, whereas 'Tech Leads' lead development and technology efforts. The book covers the responsibilities of both, and talks about why and how an individual contributor might start down a leadership path. I found it helpful for locating specific areas I need to develop to further my career.

You, as a member in your development team, are familiar with how your team works. Over the months any annoyances in the agile process, decision making frameworks, technical considerations, or meetings tend to get ironed out. This results in the team settling into a comfortable way of working. It's often difficult to see how other teams work, making it hard to learn from them. These chapters sketch a model of what I think is a high performing team. The role of the leaders, the role of members, how decisions should get made, and the considerations team members should have. I've found it valuable to contrast my team at work to this model of a high performing team. This sparks ideas and improvements I can bring to my team.

Hypothesis and Decision Making Frameworks

Chapter 7 - Measuring Engineering Productivity

This chapter is better titled 'Hypothesis and Decision Making Frameworks'. It describes a decision making framework which could be used for making both technical decisions, as well as product and feature decisions. To make a decision we might want to measure some metric. But is the metric worth measuring? Answer these questions first.

What result are you expecting, and why?
If the data supports your expected result, what action will be taken?
If we get a negative result, will appropriate action be taken?
Who is going to decide to take action on the result, and when would they do it?

The idea is that if the result of this metric is not actionable then it's a waste of time to measure it. Assuming we do want to measure it, how do we go about it? Google uses the Goals/Signals/Metrics (GSM) framework.

A Goal is a desired end result. It's phrased in terms of what you want to understand at a high level, and should not contain references on how to measure it.
A Signal is how you might know you've achieved the end result. Signals are things we would like to measure, but may not be measurable themselves.
A Measure is something we can actually measure.

Any goal we have is going to have trade offs. For example we could require all teams to implement end to end testing in their CI/CD pipelines. This is going to have a short term impact on the rate at which teams develop new features. It would likely hit teams who own legacy code a lot harder than those on newer projects. To look at these tradeoffs we should assess the goal in terms of QUANTS.

Quality of the code - Covering tests, architecture, ease of change, maintainability.
Attention from engineers - How an engineer works. Would they be distracted by this? Is what is proposed going to cause the engineer to context switch?
I*n*tellectual complexity - Is this going to un-necessarily or un-reasonably add to the cognitive load of engineers?
Tempo and velocity - How quickly can the engineers write and release code and products?
Satisfaction - How happy are engineers with their tools and products they are developing? Are engineers feeling burned out? The book applies this framework to a case study within Google. I found this chapter valuable because the impact of non-considered product or architectural decisions is typically weeks or months of engineering time. It's silly to think that we could always make the 'right' decision because circumstances change all the time. But by applying a framework to how we approach decisions gives us some avenue for improving our decision making process.

Thoughts

Let's start with a couple of assumptions

Companies write more code than their developers can maintain.
Code which is unmaintained for years will rust (aka. bit rot).

Given these, what is a high level software development strategy a company could follow?

Variation in software development practices over a long period of time leads to an increase in complexity. This complexity builds up and starts making itself known through the unhappy faces of the development team at the pub on a Friday night. Flaky tests, unsupported libraries, unmaintained deployment pipelines, long deployment times, lack of documentation. By the time things get to that stage the damage is done, and product delivery timelines stretch out as teams now spend time battling the years of rust.

I interpreted the book as these are problems Google has faced since the early 2000s and still faces today. Through standardising the ways of developing software they look to reduce the variation in how software is developed between teams.
Though there will still be unmaintained code rusting, if it's rusting in the same way as other code, in theory it will be easier to one day pick up and bring up to scratch. Projects implemented in a variety of software stacks, libraries, and processes will be more difficult to revive as specialist skills will be needed to bring them back.

What I Would Have Liked To See

More emphasis on product. The book describes processes to achieve an optimal engineering outcome. For a lot of us what pays the bills is product development. Deadlines are set to important product or marketing dates and don't reflect the time it takes to do quality engineering work. Yes, APIs are customer facing products, but this book has little on the customer and product side of things.

Stakeholder management. Software development teams face the infinite problem of trying to balance an implementation against time and resource constraints. So called clever implementations never get a team far, and more weight is put on communication and give and take with project stakeholders. A chapter on this is sorely missing.

There are no chapters on Agile development methodologies and this is a good thing.

Quotable Quotes

The Beyonce Rule to testing, the answer to what parts of my code should I actually test? "If you liked it then you shoulda put a test on it".
What is the company standard way of implementing X? "There are 2 ways of doing things: the one that's deprecated and the one that's not ready yet".
On documentation, "At Google, our more successful efforts have been when documentation is treated like code and incorporated into the traditional engineering workflow". If code is a liability to the company, does this mean documentation is as well?
"Hope is not a strategy". For engineering, certainly.

Conclusion

Sweet, let's go and cargo cult all of Google's software engineering practices. Yeah, nah. The book takes care to describe why the practices are in place at Google. It describes the pain Google was facing, their attempts to fix it, and the policies and processes they put in place. In this aspect I found it much more valuable than say Accelerate, which proposes a shortlist of policies and processes that are correlated between high performing companies, but very little nuance or background to them.

For me the value in the book was seeing Google's perspective and approach to software engineering. I have a huge list of personal learnings, and I'm sure you would learn a lot from the book as well.

DEV Community: Logan Mortimer

Cellular Automata in F#

Cellular Automata

Rules as Code

Modelling the Grid

Other Rules

Image Output

Rules

Rule 62

Rule 110

Rule 150

Conclusion

Further Reading

Software Engineering at Google - The Book

Hey, They Wrote a Book About It

Who Should Read This Book?

Favourite Chapters

Teams and Leadership

Hypothesis and Decision Making Frameworks

Thoughts

What I Would Have Liked To See

Quotable Quotes

Conclusion