
[Golfcart](https://github.com/healeycodes/golfcart) is a minimal programming language inspired by Ink, JavaScript, and Python – implemented in Go. It's a toy programming language that I built to use for Advent of Code 2021.

```javascript
// Here's the classic interview question FizzBuzz
for i = 1; i < 101; i = i + 1 {
    log(if i % 3 == 0 and i % 5 == 0 {
        "FizzBuzz"
    } else if i % 3 == 0 {
        "Fizz"
    } else if i % 5 == 0 {
        "Buzz"
    } else {
        str(i)
    })
}
```

Another motivation was to learn how to write an interpreter from scratch.

During this project, I read [Crafting Interpreters](https://craftinginterpreters.com/) and [implemented the Lox programming language](https://github.com/healeycodes/hoot-language) using Python, and [partially ported Ink](https://github.com/healeycodes/quill) using Rust. Another introduction to interpreters I enjoyed was [A Frontend Programmer's Guide to Languages](https://thatjdanisso.cool/programming-languages). The [Ink blog](https://dotink.co/posts/) is also great.

(These resources electrified me. For the past few months all I've been thinking about is programming languages.)

For Golfcart, I began with a desire to design a small programming language that didn't use semi-colons or automatic semicolon insertion. So, no statements, and everything should be an expression that evaluates to a value. For example:
- `if/else if/else` evaluates to the successful branch
- A variable declaration evaluates to the value
- Setting a dict value evaluates to the value
- A for loop evaluates to the number of times the condition expression succeeded

```javascript
assert(
    // This runs five times
    for i = 0; i < 5; i = i + 1 {}, 5
)
```

However, I didn't realise how restrictive this design goal was. A problem I ran into early was accessing an item from a literal.

```javascript
[1][0] // This evaluates to [0] because Golfcart thinks it's two lists

// Instead, you do:
a = [1]
a[0]
```

While it's too late to add semi-colon separated statements to Golfcart, I have a new found appreciation for `;`.

## In the Beginning

I started small, with numbers and math operators (think `1 + 1 * 2`). Whenever I implemented a new type or a piece of syntax, I added a specification program with an assertion. When I came across a bug, I sometimes wrote an error program to purposefully throw an error. This project's tests `go test ./...` ensure that the specification programs and example programs run without any errors (an `assert()` call throws an error and quits) and that the error programs all throw errors.

Perhaps I was too focused on correctness on a micro-level.

The main problem with Golfcart is that there are slight differences between how Golfcart programs run in my head vs. in the interpreter. This is because I jumped to implementing the language and didn't spend enough time designing. Linus Lee (creator of Ink) has some interesting notes on designing small interpreters in [Build your own programming language](https://thesephist.com/posts/pl/#impl).

> In this phase, I usually keep a text document where I experiment with syntax by writing small programs in the new as-yet-nonexistent language. I write notes and questions for myself in comments in the code, and try to implement small algorithms and data structures like recursive mathematical functions, sorting algorithms, and small web servers.

If I had more predefined programs to start with (to run as tests), I would have noticed the divergence of how programs are actually evaluated early enough to re-think the design of Golfcart. Most of this project's example programs were written after the fact within the confines of the language's limitations.

One thing I got right was getting a REPL running from commit number one. Being able to quickly evaluate snippets became crucial to keeping me in a flow-state on this project.

Ultimately, I've learned a lot and this won't be my last language!

## More Syntax and Semantics

Golfcart is a dynamic strongly typed language with support for bools, strings, numbers (float64), lists, dicts, and nil (null). There is full support for closures and functions can alter any variable in a higher scope.

```javascript
counter = () => {
    n = 0
    () => {
        n = n + 1
        n
    }
}

my_counter = counter()
my_counter() // 1

assert(my_counter(), 2)
```

A Golfcart program is a series of expressions. Line breaks are optional and there are no semi-colons. The final expression is sent to stdout.

```javascript
a = 1 b = 2 assert(a + b, 3) // A successful assert() evaluates to nil
```

There are seven types. A type-check can be performed with `type()`.

```javascript
// Bools
true or false
true and true

// Numbers
1
1.1 + 1.1 // 2.2

// Strings
"multi-line
string"
"1" + "2" // "12"

// Lists
[1, 2]
nums = [3, 4]
nums.append(5) // [3, 4, 5]
[0] + [1] // [0, 1]

// Dicts
{a: 1} // Accessed by `.a` or `["a"]` like JavaScript
{b: n => n + 1} // Values can be any type
keys({a: 1}) // ["a"]

// Functions
_ => nil // All user-defined functions are anonymous, assignable by variable
n => n + 1
sum = (x, y) => x + y

// Nil
nil
nil == nil // true
```

The Fibonacci sequence.

```javascript
// Naive
t = time()
fib = n => if n == 0 {
    0
} else if n == 1 {
    1
} else {
    fib(n - 1) + fib(n - 2)
}
fib(20)
log("fib: " + str(time() - t))

// With memoization 
t = time()
cache = {"0": 0, "1": 1}
fib_memo = n => if cache[n] != nil {
    cache[n]
} else {
    cache[n] = fib_memo(n - 1) + fib_memo(n - 2)
}
fib_memo(20)
log("fib_memo: " + str(time() - t))
```

For more detailed examples, see:

- [Example programs](https://github.com/healeycodes/golfcart/tree/main/example%20programs)
- [Specification programs](https://github.com/healeycodes/golfcart/tree/main/example%20programs/spec%20programs)
- [Programs that purposefully throw errors](https://github.com/healeycodes/golfcart/tree/main/example%20programs/error%20programs)

(All the above are used as part of Golfcart's test suite)

## Implementation

Golfcart is a tree-walk interpreter. Its single dependency is the [Participle](https://github.com/alecthomas/participle) parsing library, which consumes a parser grammer written using Go structs and a RegEx-like syntax to create an abstract syntax tree (AST) (see [parser.go](https://github.com/healeycodes/golfcart/blob/main/pkg/golfcart/parse.go)). This library let me move fast and refactor parser bugs without headaches. Participle has great documentation and [examples](https://github.com/alecthomas/participle/tree/master/_examples) (e.g. how to parse BASIC, MicroC, GraphQL) and it's in active development.

Participle provides line numbers and column positions for each token. They are added to Golfcart's language values during evaluation (so some Golfcart errors have line numbers). All errors have error text, and hopefully enough information to find the problem and fix it but Golfcart lacks a mature stack trace.

A program runs like this: a piece of source code is turned into tokens by Participle's lexer. The lexer uses token definitions — for example, Golfcart's identifier is defined as: ```{"Ident", `\w]+`, nil}```). These tokens are parsed into an AST using struct definitions and the AST is evaluated (see [eval.go](https://github.com/healeycodes/golfcart/blob/main/pkg/golfcart/eval.go)).

Here's Golfcart's list literal:

```go
type ListLiteral struct {
    Pos lexer.Position

    // This matches any number of expressions (or none)
    // If there's more than one expression, they must be separated by a comma
    // `@@` means: recursively capture using the fields own type
    Expressions *[]Expression `"[" ( @@ ( "," @@ )* )? "]"`
    // For simple types, tokens can be parsed directly into Go values
    // e.g. bool, float, string, etc.
}
```

How does a literal node become a value? Let's take the `ListLiteral` as an example. An `Eval` method is defined for most nodes, including this one. Given a stack frame, this list literal becomes a list value.

```go
func (listLiteral ListLiteral) Eval(frame *StackFrame) (Value, error) {
    values := make(map[int]*Value, 0)
    if listLiteral.Expressions != nil {
        for _, expression := range *listLiteral.Expressions {
            result, err := expression.Eval(frame)
            if err != nil {
                return nil, err
            }
            values[len(values)] = &result
        }
    }
    return ListValue{val: values}, nil
}
```

Let's talk more about stack frames in Golfcart. A stack frame is a map of variables in scope. It's a recursive structure, every stack frame has a parent apart from the global frame. All functions are anonymous and create closures. Any variable referenced in a higher scope can be altered.

Examples explain this better than words.

```javascript
a = 1
a_function = () => a = 2 // Closure created
a_function() // When called, `a` is changed
a // 2

if true {
    // `b` is not defined in a higher scope
    // So, `b` is declared only within this scope
    b = 3
}
b // Error: cannot find value for key 'b'

c = nil
if true {
    // This assignment recursively looks in higher scopes for `c`
    // it's found and that value is altered
    c = 4
}
c // 4
```

<br>

When I needed to make a design decision for Golfcart, I drew from internal feelings about how computer programs _should_ run. It feels good to own a slice of my computing experience.

Check out the source and grab the binaries at [https://github.com/healeycodes/golfcart](https://github.com/healeycodes/golfcart) ⛳

## Learning Resources

I used these:

- [Build your own programming language](https://thesephist.com/posts/pl)
- [Crafting Interpreters](https://craftinginterpreters.com/)
- [A Frontend Programmer's Guide to Languages](https://thatjdanisso.cool/programming-languages)
- [The Ink blog](https://dotink.co/posts/)
- [Build your own programming language](https://thesephist.com/posts/pl/)

I've not tried but have heard great things about:

- [Writing An Interpreter In Go](https://interpreterbook.com/) (and the [sequel](https://compilerbook.com/))
- [Let's Build A Simple Interpreter](https://ruslanspivak.com/lsbasi-part1/)
- [The Super Tiny Compiler](https://github.com/jamiebuilds/the-super-tiny-compiler)


Creating the Golfcart Programming Language


The challenge of searching static websites is effectively a solved problem with brilliant, yet widely unadopted, solutions.

These projects scan and index your content at build time and ship it to the browser with the rest of your static files. No out-of-your-control external service required. A small library in JavaScript (sometimes accompanied by WebAssembly) loads the index and allows instant searching and works just fine offline. Searching the complete Federalist Papers for multiple keywords takes less than 100µs in my Wasm [tech demo](https://github.com/healeycodes/crane-search) (I'll get to that later on).

The most popular libraries are written in JavaScript like [Lunr](https://lunrjs.com/), or [Fuse](https://github.com/krisk/Fuse), or [FlexSearch](https://github.com/nextapps-de/flexsearch). They provide pre-compiled indexes and [fuzzy](https://en.wikipedia.org/wiki/Approximate_string_matching), wildcard, and boolean searches. They have good documentation and are ready for production usage.

But I'm more interested in how the up-and-coming Wasm-powered projects work. Browser search is a space where Wasm can really find an edge. Wasm runs faster, loads quicker, and ships smaller binaries (in theory, in practice it takes some work to get there).

The two projects I looked at both use Rust as a backend language:

- [tinysearch](https://github.com/tinysearch/tinysearch) generates a small, self-contained Wasm module (with an embedded index). It aims for a small memory footprint by using Bloom filters — a space-efficient probabilistic data structure that results in a negligible amount of false positives. Read more in [A Tiny, Static, Full-Text Search Engine using Rust and WebAssembly](https://endler.dev/2019/tinysearch) by the creator, Matthias Endler.
- [Stork](https://stork-search.net/) focuses more on the developer experience with rich documentation and examples. Stork also pays keen attention to the user experience by providing a progress bar for loading the index, excerpts for the results (keywords highlighted), theme support, and more (see [Embedding the Interface](https://stork-search.net/docs/interface)). Learn about how it came to life in [Stork Turns One: Building a search tool for static sites with Rust and WebAssembly](https://jameslittle.me/blog/2020/one-year-of-stork/) by the creator, James Little.

Stork is more interesting to me because it focuses on the human experience — of the person who builds with it, and the person who searches. See the thin, quick, configurable UI below.

![The Stork instant search in-action](stork.gif)

In order to understand how these search tools work, and the design problems involved, I built a technical demo in Go, compiled to Wasm.

## Technical Demo

My technical demo is inspired by Stork and uses a near-identical configuration file setup. So it had to be named after a bird 🐦 too — [healeycodes/crane-search](https://github.com/healeycodes/crane-search).

Crane is two programs. The first program scans a group of documents and builds an efficient index. 1MB of text and metadata is turned into a 25KB index (14KB gzipped). The second program is a Wasm module that is sent to the browser along with a little bit of JavaScript glue code and the index. The result is an instant search engine that helps users find web pages as they type.

The full-text search engine is powered in part with code from Artem Krylysov's blog post [Let's build a Full-Text Search engine](https://artem.krylysov.com/blog/2020/07/28/lets-build-a-full-text-search-engine/).

The core data-structure is an inverted index. It maps words to document IDs. This means we can check very quickly (i.e. 100µs within Wasm) which documents a word can be found in. At build time, we loop over the document files and add to the inverted index. We also create a list of results so we can relate a document ID to a document's metadata (defined in the configuration file). The metadata includes the title and URL so that we can display a list of search results in the browser.

We can return results for multiple keywords by looking at the common document IDs for each keyword. This takes linear time as the IDs are inserted into the index in order.

During the build stage, we perform normalization to make the search engine more helpful and accurate. For example, if you search for `fish` you probably want to match `Fishing`. Words are turned into lowercase, common words are dropped, and words are reduced into their root form (aka [stemming](https://en.wikipedia.org/wiki/Stemming) — Krylysov's example code uses [Snowball](https://github.com/kljensen/snowball) as a stemmer).

The document `"Alice likes to go fishing"` becomes `["alice", "go", "fish"]`. The search term `"Fishing"` is also turned into a token, at search-time it becomes `"fish"`.

To handle the document metadata, Crane's build program is passed the location of the configuration file. This tells it where to find the documents to index on disk, where they can be found on the static website, and what the search result should be titled.

```toml
[input]
files = [
    {
        path = "docs/essays/essay01.txt",
        url = "essays/essay01.txt",
        title = "Introduction"
    },
    # etc.
]

[output]
filename = "dist/federalist.crane"
```

The index and result data is combined into a single struct called a store. It's encoded using [encoding/gob](https://golang.org/pkg/encoding/gob/), a binary encoding that is faster and smaller than JSON ([one](https://gist.github.com/evalphobia/a2ba2636acbc112f68dcd89e8b81d349), [two](http://ugorji.net/blog/benchmarking-serialization-in-go)).

```go
file, err := os.Create(config.Output.Filename)
check(err)
defer file.Close()

encoder := gob.NewEncoder(file)
store := search.Store{
    Index:   index,
    Results: results,
}
err = encoder.Encode(store)
check(err)
```

The second part of Crane is the program that's compiled into Wasm and sent to the browser. It uses the Go standard library package [syscall/js](https://golang.org/pkg/syscall/js/).

> Package js gives access to the WebAssembly host environment when using the js/wasm architecture. Its API is based on JavaScript semantics.

Our browser program makes two functions available in the global JavaScript scope. A new goroutine is spawned when they're called.

```go
// Store is a shared type between both programs (build/browser)
var store search.Store

func main() {
    js.Global().Set("_craneLoad", js.FuncOf(load))
    js.Global().Set("_craneQuery", js.FuncOf(query))
    // Wait indefinitely,
    // required so that our Wasm module doesn't exit straight away
    select {}
}

func query(this js.Value, args []js.Value) interface{} {
    searchTerm := args[0].String()
    start := time.Now()
    matchedIDs := store.Index.Search(searchTerm)
    log.Printf("Search found %d documents in %v", len(matchedIDs), time.Since(start))

    var results []interface{}
    for _, id := range matchedIDs {
        results = append(results,
            map[string]interface{}{
                "title": store.Results[id].Title,
                "url":   store.Results[id].URL,
                "id":    store.Results[id].ID,
           })
    }

    // This will arrive as JSON
    return js.ValueOf(results)
}

// ..
```

Here's a high-level view of how everything fits together.

![Flow chart of the in-browser logic](crane-search-small.png)

A JavaScript support file, [wasm_exec.js](https://github.com/golang/go/blob/7be8358f70ff858f28b9aefe11986da25f1762bc/misc/wasm/wasm_exec.js), provides a Go class that connects JavaScript ⟷ Go. The Wasm module is loaded with [WebAssembly.instantiateStreaming](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/WebAssembly/instantiateStreaming) ([polyfill available](https://github.com/golang/go/blob/b2fcfc1a50fbd46556f7075f7f1fbf600b5c9e5d/misc/wasm/wasm_exec.html#L17-L22)) and is passed to the Go instance. The store is downloaded via the Fetch API and is passed to the running Wasm module where the gob-encoded binary is decoded.

I wrote a ~50 line [class](https://github.com/healeycodes/crane-search/blob/main/dist/crane.js) that abstracts away most of this to make the project easier for a developer to interact with.

```javascript
const crane = new Crane("crane.wasm", "federalist.crane");
await crane.load()

const results = crane.query('some keywords');
console.log(results);
```

The result is, well, it's no Stork. But it works and it's fast. If there's one way to get a developer to respect the complexity of your project, have them build a technical demo of it with 1/50th of the features.

![Searching for keywords with Crane from the same dataset as Stork](crane.gif)

The binary is too large at around 3MB (but I didn't optimize for this). The solution for this is to read [Reducing the size of Wasm files](https://github.com/golang/go/wiki/WebAssembly#reducing-the-size-of-wasm-files) from the Go GitHub or read any of the blogs that come up when you search `shrink go wasm binary`. The best advice I found is to use [TinyGo](https://github.com/tinygo-org/tinygo) to generate the Wasm (the "Hello world" example is 575 bytes) and to limit the number of libraries you include. TinyGo actually artificially limits the libraries that you can use because it implements a subset of Go — which means the encoding/gob package is out (encoding/json too).

## Design Problems

If there's one thing I learned, it's that search is a reasonably solved problem. It's easy to get started; stand on the shoulders of algorithms and away you go. The key problem in this space is the developer experience. Configuring the build process of a static site can be tricky when things beyond the standard content (e.g. posts, images) need to be generated. In order to return metadata about each result, these types of search tools require a config (usually TOML or JSON) and generating these files adds complexity.

Setting up a search bar with any features beyond the basics (e.g. auto-complete, full keyboard support, highlighted excerpts) is non-trivial too, especially when you want it to feel good and always react fast.

It's also hard to build a solution that solves all use cases. Every time a feature is added (e.g. zero tolerance for false positives, fuzzy search, excerpts, partial matching) the index size grows by an order of magnitude. One rather esoteric idea that I toyed around with was building a search solution that split the index depending on the letters the user entered. Having an index for all the words that start with `a` and one for `b` and so on. However, English letter frequency is weighted towards things like `th` (see [English Letter Frequency Counts:
Mayzner Revisited](https://norvig.com/mayzner.html)).

There's also the issue of getting people to contribute to your project. Wasm is a reasonably young technology and building, testing, and debugging your code feels harder than it should be. Building a full-stack Wasm project always feels like it requires one-too-many steps. (For Go, it's worth calling out [wasmbrowsertest](https://github.com/agnivade/wasmbrowsertest) that automates in-browser testing.)

In [Introduction to WebAssembly](https://rsms.me/wasm-intro), the best low-level introduction to the technology I've seen, Rasmus Andersson writes:

> The web is an amazing concept that is currently falling short carrying a heavy legacy from the past. In order to bring truly great experiences to the web and blur the lines of what is and what isn’t a “native” experience, WebAssembly—or something else like it—needs to happen.

A search tool for static sites is a good fit for Wasm, and I hope to see projects in this space continue to evolve. It's a noble goal to build a project which actually has **four** design areas when you think about it:

- Back-end (build process)
- Back-of-the-front-end (search algorithm/Wasm)
- Front-of-the-front-end (results UI)
- Developer integration (APIs, docs)

So, thank your local open source developer today.

<br>

<small>Stork GIF sourced from https://github.com/jameslittle230/stork</small>


Building a technical demo to understand this blossoming area of technology.

WebAssembly Search Tools for Static Sites


Lately, I've been revisiting concepts and algorithms that I got stuck on when I was learning to code. One of them is the boids flocking simulation.

We'll look at how this program can be written in Go and delivered via WebAssembly. You can find all the source code for this article, as well as the [WASM demo](https://healeycodes.github.io/boids/), on [healeycodes/boids](https://github.com/healeycodes/boids).

![A flock of dark colored boids swimming around a white area](preview.gif)

A boid is a simulated bird-like object, a bird-oid. Each boid looks at their local flockmates and uses three rules to respond to their behavior — _separation_, _alignment_, and _cohesion_.

This artificial life program was first developed by Craig Reynolds. In [Flocks, Herds, and Schools: A Distributed Behavioral Model](http://www.red3d.com/cwr/papers/1987/boids.html) he describes it:

> The simulated flock is an elaboration of a particle system, with the simulated birds being the particles. The aggregate motion of the simulated flock is created by a distributed behavioral model much like that at work in a natural flock; the birds choose their own course.

## Ebiten "A dead simple 2D game library for Go"

[Ebiten](https://ebiten.org/) is well documented and has a lively community (`#ebiten` channel in [Gophers Slack](https://blog.gopheracademy.com/gophers-slack-community/)). I started learning it by extending the [example programs](https://ebiten.org/examples/) to get used to the API.

Let's look at the overall structure of our program.

When you build a game with Ebiten, you must implement the [ebiten.Game](https://pkg.go.dev/github.com/hajimehoshi/ebiten#Game) interface. We define a `Game` struct to store our flock of boids as well as the methods required by Ebiten to run our game. `Update` is called every tick to handle the game logic, `Draw` is called every frame to draw the screen, and `Layout` is used to define the game's screen size (which can be 'stretched' to fit the window).

```go
type Game struct {
    flock  Flock
    inited bool
}

// Create all of the boids, give them some random velocity
func (g *Game) init() {}

// Apply logic to our flock
func (g *Game) Update(screen *ebiten.Image) error {}

// Draw all of the boids
func (g *Game) Draw(screen *ebiten.Image) {}

// Define the game's logical screen size
func (g *Game) Layout(outsideWidth, outsideHeight int) (int, int) {}

// Set the window size, the title, and pass an instance of Game to
// ebiten.RunGame
func main() {}
```

### Game Loops

Almost every game that you've played uses a programming pattern called a [Game Loop](https://gameprogrammingpatterns.com/game-loop.html).

> A game loop runs continuously during gameplay. Each turn of the loop, it processes user input without blocking, updates the game state, and renders the game. It tracks the passage of time to control the rate of gameplay.

The frequency of a game loop is sometimes referred to as the tick rate of a game. A single iteration of the loop is a _tick_.

## Simulation Logic

In our program, a boid has the following properties:

- Position — the coordinates of the boid in the world
- Velocity — how fast and in what direction the boid is moving
- Acceleration — we change the velocity by this value during the next tick

```go
type Boid struct {
    imageWidth   int
    imageHeight  int
    position     Vector2D // Exposes `X`, `Y`, and some calculation methods
    velocity     Vector2D
    acceleration Vector2D
}
```

Every tick, we need to handle three things for every boid in our flock:

- Check edges — check if the boid has gone off the edge of the screen
- Apply rules — using the three rules, set every boid's acceleration
- Apply movement — apply acceleration to the boid's velocity

```go
type Flock struct {
    boids []*Boid
}

func (flock *Flock) Logic() {
    for _, boid := range flock.boids {
        boid.ApplyEdges()
        boid.ApplyRules(flock.boids)
        boid.ApplyMovement()
    }
}
```

To handle boids hitting the edge of the screen, we wrap them around by swapping their position to the opposite side. Their velocity means they keep flying in the same relative direction.

After we've figured out the boid's acceleration by applying the three rules, we need to update its position and velocity, and reset acceleration.

```go
func (boid *Boid) ApplyMovement() {
    boid.position.Add(boid.velocity)
    boid.velocity.Add(boid.acceleration)
    boid.velocity.Limit(maxSpeed)
    boid.acceleration.Multiply(0.0)
}
```

By adding acceleration to the boid's existing velocity, and then limiting it by a maximum speed, we get smooth movement that tends towards the desired direction and speed. Velocity can be thought of as momentum and acceleration as steering.

## The Three Rules

In the following code excerpts, you may notice that the logic is not very optimized. This is to make it easier to understand. On every tick, every boid considers the position of every other boid. We would say that the asymptotic complexity is `O(n^2)`.

Different rules use different 'inclusion' zones. Whether another boid is _local_ to another boid depends on which rule we are applying.

```go
maxForce             = 1.0
maxSpeed             = 4.0
alignPerception      = 75.0
cohesionPerception   = 100.0
separationPerception = 50.0
```

The last three values are really fun to play with and greatly affect the shape and contortions of a flock of boids. `maxForce` limits the steering of a boid and `maxSpeed` is the ultimate speed limit.

I've expanded some of Craig Reynolds' low-resolution diagrams to help explain the three rules that define a boid's behavior.

### Separation

> Steer to avoid crowding local flockmates.

The closer another boid is to us, the more motivated we are to move away from it. The white circle represents `separationPerception`. Boids outside of this area are not considered. This rule encourages boids to move into free space.

![A boid looking at its local area and deciding to move away from the average position of other boids](separation.png)

(In the canonical version of the Boid program, a boid doesn't consider other boids behind itself by applying a field of view restriction.)

```go
separationSteering := Vector2D{}
separationTotal := 0

for _, other := range restOfFlock {
    d := boid.position.Distance(other.position)

    // A boid shouldn't consider itself
    if boid != other {

        // It should only consider local boids
        if d < separationPerception {
            separationTotal++

            // We want to steer away from other boids
            // If a boid is very close, consider it more strongly
            diff := boid.position
            diff.Subtract(other.position)
            diff.Divide(d)
            separationSteering.Add(diff)
        }
    }
}

// If there are no local boids, we keep the same direction and speed
if separationTotal > 0 {
    separationSteering.Divide(float64(separationTotal))
    separationSteering.SetMagnitude(maxSpeed)
    separationSteering.Subtract(boid.velocity)
    separationSteering.SetMagnitude(maxForce * 1.2)
}

// `acceleration` will be the sum of all three rules
// we'll then take the average and apply it to `velocity`
boid.acceleration.Add(separationSteering)
```

### Alignment

> Steer towards the average heading of local flockmates.

We know the direction of a boid by looking at the velocity. We sum and take the average of other nearby boids within the `alignPerception` area. This rule encourages boids to travel together.

![A group of boids with lines indicating their heading, the boid in question is about to adjust to this](alignment.png)

```go
alignSteering := Vector2D{}
alignTotal := 0

for _, other := range restOfFlock {
    d := boid.position.Distance(other.position)
    if boid != other {
        if d < alignPerception {
            alignTotal++
            alignSteering.Add(other.velocity)
        }
    }
}

if alignTotal > 0 {
    alignSteering.Divide(float64(alignTotal))
    alignSteering.SetMagnitude(maxSpeed)
    alignSteering.Subtract(boid.velocity)
    alignSteering.Limit(maxForce)
}

boid.acceleration.Add(alignSteering)
```

### Cohesion

> Steer to move toward the average position of local flockmates

To be a _cohesive_ boid, one must head towards the center of the clump. This may seem at odds with _separation_ but these two rules work together to let boids arrange themselves equally within a space. Although, the reality of this _arranging_ can look quite chaotic!

![Our boid has a red arrow pointing to a green point in space. There are lines from the other boids that lead to this average center.](cohesion.png)

```go
cohesionSteering := Vector2D{}
cohesionTotal := 0

for _, other := range restOfFlock {
    d := boid.position.Distance(other.position)
    if boid != other {
        if d < cohesionPerception {
            cohesionTotal++
            cohesionSteering.Add(other.position)
        }
    }
}

if cohesionTotal > 0 {
    cohesionSteering.Divide(float64(cohesionTotal))
    cohesionSteering.Subtract(boid.position)
    cohesionSteering.SetMagnitude(maxSpeed)
    cohesionSteering.Subtract(boid.velocity)
    cohesionSteering.SetMagnitude(maxForce * 0.9)
}

boid.acceleration.Add(cohesionSteering)
```

Each rule should be considered equally, so after summing the rules together, we divide by three to find the average.

```go
boid.acceleration.Divide(3)
```

## Building And Deploying

It's time to get this simulation in front of users! Lucky for us, Ebiten supports many platforms. (The Nintendo Switch is even on the [roadmap](https://ebiten.org/blog/roadmap2020.html#Ebiten_2.1_-_March,_2021).)

The current release (v1.11.4), supports:

- Windows, macOS, Linux, FreeBSD
- Android, iOS
- Web browsers (Chrome, Firefox, Safari and Edge)
  - via WebAssembly or GopherJS

We will be compiling to [WebAssembly](https://developer.mozilla.org/en-US/docs/WebAssembly). With WebAssembly as a compilation target, we can deliver our Go program to anyone running a modern browser. I'm currently hosting it on [GitHub Pages](https://healeycodes.github.io/boids/).

What are the benefits of WebAssembly? In brief:

- Fast, efficient, and portable
- Executes at 'near-native' speed
- Runs in a secure sandbox

To get our Boid program ready for users, we build the `.wasm` file.

```bash
GOOS=js GOARCH=wasm go build -o dist/boids.wasm github.com/healeycodes/boids
```

We set the build's target operating system to `js` as well as setting the architecture to `wasm`. If you're setting this up from scratch, you'll need a copy of `wasm_exec.js` from the Go source — you can copy it locally from your machine or get it from [golang/go](https://github.com/golang/go/blob/master/misc/wasm/wasm_exec.js).

To display the simulation in a browser, we use [WebAssembly.instantiate](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/WebAssembly/instantiate). Here's what our index page looks like:

```html
<main>
    <p>Loading..</p>
</main>

<script src="dist/wasm_exec.js"></script>
<script>
  (function () {
    const go = new Go();
    // WebAssembly.instantiateStreaming is more efficient
    // but doesn't work on Safari
    fetch('dist/boids.wasm')
      .then(response => response.arrayBuffer())
      .then(bytes => WebAssembly.instantiate(bytes, go.importObject))
      .then(result => {
        document
          .querySelector('main')
          .remove();
        go.run(result.instance);
      });
  })();
</script>
```

The full source is available on [the repository](https://github.com/healeycodes/boids).

## Where to go from here?

We looked at how to create an Ebiten game, the emergent behavior of the Boid program, and delivering a Go program via WebAssembly. But there's still more to explore!

Expand this solution with:

- Field of vision support (boids shouldn't look behind 👀)
- QuadTree optimization
- Different `maxSpeed`/`maxForce` for each boid
- Graphical interface for live-editing of values

Or use a different language:

- JavaScript/p5.js with [Daniel Shiffman](https://www.youtube.com/watch?v=mhjuuHl6qHM&vl=en)
- C#/Unity with [Sebastian Lague](https://www.youtube.com/watch?v=bqtqltqcQhw) in 3D

I'd love to see what you come up with!

<hr>

<small>Reynolds, C. W. (1987) Flocks, Herds, and Schools: A Distributed Behavioral Model, in Computer Graphics, 21(4) (SIGGRAPH '87 Conference Proceedings) pages 25-34.</small>

<small>Nystrom, R. (2020) Game Programming Patterns/Sequencing Patterns</small>


The famous flocking simulation built with the Ebiten game library.

Boids in WebAssembly Using Go


My [first program](https://github.com/healeycodes/conways-game-of-life) in Go was Conway's Game of Life. This time I made an [in-memory HTTP caching server](https://github.com/healeycodes/in-memory-cache-over-http) with similar methods to Memcached like increment/decrement and append/prepend.

I use caching pretty often but I had never coded up a Least Recently Used (LRU) cache by hand before. Neither had I used Go's `net/http` or `container/list` packages. Both packages are elegant and have great documentation and readable source code — the latter being one of my favorite things about Go.

With my first program, I threw everything in a file called `main.go` and called it a day. This time I created two packages.

- api — an HTTP server which responds to GET requests like `/set?key=name&value=Andrew&expire=1571577784` and `/get?key=name`.
- cache — an LRU cache that allows an expire time and a max number of keys.

## Caching

As an LRU cache fills up and needs to forget an item it will choose the one that was _last accessed_ the _longest time ago_. It also allows lookups in constant time. To build mine, I mapped strings to doubly linked list elements.

```go
// Store contains an LRU Cache
type Store struct {
	mutex *sync.Mutex
	store map[string]*list.Element
	ll    *list.List
	max   int // Zero for unlimited
}
```

Each list element is a Node. We also store the key inside the Node so that when the cache fills up, we can do a reverse lookup from the back of the list to remove that item from the map.

```go
// Node maps a value to a key
type Node struct {
	key     string
	value   string
	expire  int  // Unix time
}
```

The `mutex` field of the Store allows the cache to avoid having concurrent readers and writers to the data structures. The default behavior of `net/http` is to spawn a goroutine for every request. In [some cases](https://groups.google.com/forum/#!msg/golang-nuts/HpLWnGTp-n8/hyUYmnWJqiQJ) it appears to be okay to have multiple concurrent map readers but I played it safe and every cache operation is guarded by a mutex.

In a previous version of this article, I exported the mutex from the cache and locked/unlocked in the API's middleware. However, this meant that the application may be bottlenecked by HTTP read/write speeds (a friendly commentator pointed this out). Instead of changing where the middleware locked/unlocked to avoid the read/write limitation, I chose to hide the mutex inside the cache to make the application safer for future maintainers while also gaining the performance boost.

There is not much in the middleware right now apart from some basic logging that helps during development. Having an overall middleware usually cuts down on duplicate code.

```go
// Middleware
func handle(f func(http.ResponseWriter, *http.Request)) func(w http.ResponseWriter, r *http.Request) {
	return func(w http.ResponseWriter, r *http.Request) {
		if getEnv("APP_ENV", "") != "production" {
			fmt.Println(time.Now(), r.URL)
		}
		f(w, r)
	}
}
```

## Give key, get value

In Go, the HTTP protocol is a first-class citizen. Clients and servers are simple (and extensible). Writing the `/get` method for my server uses six lines.

```go
// Get a key from the store
// Status code: 200 if present, else 404
// e.g. ?key=foo
func Get(w http.ResponseWriter, r *http.Request) {
	value, exist := s.Get(r.URL.Query().Get("key"))
	if !exist {
		http.Error(w, "", 404)
		return
	}
	w.Header().Set("content-type", "text/plain")
	w.Write([]byte(value))
}
```

The cache method that maps to this route is more complex. It looks for a key in the map and checks that it is valid (not expired or due for cleanup). It returns `(string, bool)` — (the value or an empty string, true if the value was found). If a string is found, its Node is moved to the front of the list because it is now the most recently accessed.

If the key is expired then it's passed to the delete method which will remove the key from the map and the Node will be passed to the garbage collector.

```go
// Get a key
func (s *Store) Get(key string) (string, bool) {
	s.mutex.Lock()
	defer s.mutex.Unlock()
	current, exist := s.store[key]
	if exist {
		expire := int64(current.Value.(*Node).expire)
		if expire == 0 || expire > time.Now().Unix() {
			s.ll.MoveToFront(current)
			return current.Value.(*Node).value, true
		}
	}
	return "", false
}
```

I've been reaching for `defer` in my other programming languages recently. It helps one better manage the lifetime of objects. It's explained in a Go [blog post](https://blog.golang.org/defer-panic-and-recover).

> Defer statements allow us to think about closing each file right after opening it, guaranteeing that, regardless of the number of return statements in the function, the files will be closed.

The syntax `current.Value.(*Node).value` performs a type assertion on the list element providing access to the underlying Node pointer. If it's the wrong type, this will trigger a panic. Type assertions can also return two values if requested, the second being a boolean whether the assertion succeeded: `value, ok := current.Value.(*Node).value`. 

## Insert into cache

Putting something into the cache means either creating a new Node at the front of the list or updating the details of a pre-existing Node and moving that to the front of the list. If we go over the maximum number of keys then we delete the Node with the oldest last-accessed time.

The expire parameter is optional.

```go
// Set a key
func (s *Store) Set(key string, value string, expire int) {
	s.mutex.Lock()
	defer s.mutex.Unlock()
	s.set(key, value, expire)
}

// Internal set
func (s *Store) set(key string, value string, expire int) {
	current, exist := s.store[key]
	if exist != true {
		s.store[key] = s.ll.PushFront(&Node{
			key:    key,
			value:  value,
			expire: expire,
		})
		if s.max != 0 && s.ll.Len() > s.max {
			s.delete(s.ll.Remove(s.ll.Back()).(*Node).key)
		}
		return
	}
	current.Value.(*Node).value = value
	current.Value.(*Node).expire = expire
	s.ll.MoveToFront(current)
}
```

Since many other cache methods require 'set' and 'delete' functionality, there are internal `set` and `delete` methods to avoid duplication of code. Terminology note: a method is a function on an instance of an object.

When removing all keys from the cache we can lean on the garbage collector to do the hard stuff for us by removing all existing references to the objects.

```go
// Flush all keys
func (s *Store) Flush() {
	s.mutex.Lock()
	defer s.mutex.Unlock()
	s.store = make(map[string]*list.Element)
	s.ll = list.New()
}
```

The full list of methods is Set, Get, Delete, CheckAndSet, Increment, Decrement, Append, Prepend, Flush, and Stats.

<br>

This project took me two Sunday mornings and I continue to warm towards Go. It's not as terse as other languages but remains understandable. It tends to lead to vertical code as opposed to horizontal code which also aids readability. It also brings all of the benefits of a static language without requiring a lot of boilerplate.

So far, I've had a great 'Google experience' alongside my Go programming. Looking up solutions normally leads to a sensible and well-explained answer. When I'm heading in the wrong direction, I normally find out after searching rather than running into problems further down the line. But perhaps this is because the language is quite new and there are fewer results for the incorrect version!

Check out the code on [GitHub](https://github.com/healeycodes/in-memory-cache-over-http).


Cloning Memcached with Go


I’m new to Go. Over the last week, I completed [A Tour of Go](https://tour.golang.org/welcome/1) and tonight I wrote my first program, an interactive [Conway's Game of Life](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life). I used [Ebiten](https://github.com/hajimehoshi/ebiten) which describes itself as *a dead simple 2D game library in Go*. Given its current stage of development, the [documentation](https://ebiten.org/) and [examples](https://github.com/hajimehoshi/ebiten/tree/master/examples) are amazing. It's also cross-platform 🎮.

![Conway's Game of Life GIF](conwaysgameoflife.gif)

Most of my professional experience is with dynamic languages like JavaScript and Python. When I start learning a language I like to run through the official tutorial and then get stuck-in building a game. It brings me back to my roots. I got into programming to make solo games but found out that I love writing high-performance things for the web (front or back!).

It's very rewarding to make things on your screen move, dance, and die. This is one of the reasons that learning web development is so much fun. Except nothing dies on the web (0.03% of the web still use Internet Explorer 5/6/7!).

### My Reasons for Learning Go

I love the single binary deployment of Go. It's totally opposite to Node/Python and it's a lot easier for me to share small things with my friends. People on my team at work are really excited by Go. It's fun to talk to them about the language and I know if I continue to learn they will be interested in hearing about my experience. With other people picking it up, there's a chance that we'll develop some Go microservices in the future too.

I could easily say that I'm learning Go because I like building high-performance applications for the web (which certainly excites me) but one of the main reasons is that it's new and exciting. There's an online buzz for the language similar to the Rust community. I enjoy learning and seeking that spark when something clicks. It's also well-documented and supported (e.g. StackOverflow threads), and there seem to be regular conferences and meetups near me.

### Conway's Game of Life

Conway's Game of Life is a _cellular automaton_ but that doesn't mean a lot to most people. Imagine a grid of cells that exist in two states: alive or dead. The 'animation' that you see is actually successive generations being rendered to the screen. There are four rules that help decide the next generation's state. Wikipedia describes them thusly.

1. Any live cell with fewer than two live neighbours dies, as if by underpopulation.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overpopulation.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

There needs to be an initial state. As we saw from the rules, an empty board will not produce cells

The `rand` package in Go _produces a deterministic sequence of values each time a program is run_. I don't want my board's default state to be the same on every load so I seed it with an ever-changing variable: time.

The following function takes a pointer to my `Game` struct which has a property called board. We edit the board that is stored in memory so we don't need to return anything.

```go
// Given an empty board, give it a random state
func giveState(g *Game) {
	rand.Seed(time.Now().UnixNano()) // <-- Different every time
	for x := 0; x < RES; x++ {
		for y := 0; y < RES; y++ {
			if rand.Intn(15) == 1 {
				g.board[x][y] = 1
			}
		}
	}
}
```

Every cell has a 1-in-15 chance of being alive during the first generation. Ebiten's update function runs at 60fps per second and I create a new generation for every tick. I print out the current generation number in the top left.

![Generation number](gennumber.png)

Conway's Game of Life seems to be a rite of passage for Computer Science students. At least, that's what I've learned from the web. It didn't come up in any of my classes so it's been fun to play around with it and read about the amazing things people have created with it. For example, a [replica of a digital clock](https://codegolf.stackexchange.com/a/111932) that has even time-steps.

### Interaction

![Interaction GIF](interaction.gif)

If you click the board, the nearby cells have their states flipped. You can drag around the screen to make the cells cascade. Animated patterns have a simple pleasure about them. Ebiten has a function for clicking and I call it on every update tick. Here we use multiple inline assignments to set the value of `x` and `y`. The type of these variables is inferred at compile time.

```go
if ebiten.IsMouseButtonPressed(ebiten.MouseButtonLeft) {
	x, y := ebiten.CursorPosition()
	interaction(x, y, g)
}
```

As low-level as Golang is, it seems to keep out of your way by default.

### Go Modules

I understand that Go's module system is a fairly recent addition. I created a mod file by running `go mod init github.com/my/repo` and then whenever I built or ran my code the dependencies were automatically updated. Changing development setup was as easy as cloning the repository and running `go install`.

I've also found VS Code's Go plugin to be incredibly useful, with it performing more helpful actions than I'm probably aware of! This has helped me focus on learning the language. For anyone looking for a way into Go, I recommend [A Tour of Go](https://tour.golang.org/welcome/1). For resources beyond that, who knows — I'm testing a few myself and welcome recommendations!

Check out the [code](https://github.com/healeycodes/conways-game-of-life) on my GitHub.


Go posts