DEV Community: Lorenzo Barasti

Crystal JSON beyond the basics

Lorenzo Barasti — Tue, 06 Oct 2020 22:50:35 +0000

Introduction

When modelling a business domain, you will often find yourself defining custom data types on the top of the language's primitives. If you've been exposed to some functional programming, you're likely to strive for sum types, in particular.

In Crystal, we can represent sum types as composite types inheriting from an abstract one. As a side benefit, this pattern makes it straightforward to encode (and decode) custom types into (and from) JSON, as hinted in the official documentation.

In this article, we'll look at how we can JSON-encode and decode sum types in Crystal using the json module and its powerful macros.

We'll cover:

Automatic encoding with JSON::Serializable
Type resolution with discriminators
Encoding of nested composite data types
Considerations on the extensibility of this approach

Case study - a P2P client

Suppose we want to model events related to a peer to peer application. We'll focus on two domain events:

Connected event: a connection with a peer is established
Started event: a file piece download is started.

A common pattern in this scenario is to represent the various types of event as classes or structs inheriting from a base Event type. Events are inherently immutable, so it makes sense to model them as structs with getters.

alias Peer = String

abstract struct Event
end

struct Connected < Event
  getter peer
  def initialize(@peer : Peer); end
end

struct Started < Event
  getter peer, piece
  def initialize(@peer : Peer, @piece : UInt32); end
end

In the snippet above

On line 1, a Peer is represented by a string - its IP address.
On line 3, we define an abstract struct Event which serves as base type for all the concrete event types. Mind that the abstract identifier makes it so that Event objects cannot be instantiated - meaning Event.new won't compile.

JSON encoding

As we are contemplating our nicely designed events hierarchy, a requirement comes in saying that we need to persist all the P2P events processed by our application for auditing purposes. After an intense discussion with the team, we decide to go for the JSON format. Let's update our code so that we can turn Event instances into JSON

require "json"

abstract struct Event
  include JSON::Serializable
end

Here we are importing the JSON package (line 1), and then simply mixing the JSON::Serializable module into Event (line 4).

Is that it? Well, let's see...

e0 = Connected.new("0.0.0.0") #=> Connected(@peer="0.0.0.0")
e1 = Started.new("0.0.0.0", 2) #=> Started(@peer="0.0.0.0", @piece=2)

e0.to_json #=> {"peer":"0.0.0.0"}
e1.to_json #=> {"peer":"0.0.0.0","piece":2}

Now, that's impressive! Simply including the JSON::Serializable module into the base type resulted in equipping its subtypes with working #to_json methods. The following works, too:

Connected.from_json(e0.to_json) #=> Connected(@peer="0.0.0.0")
Started.from_json(e1.to_json) #=> Started(@peer="0.0.0.0", @piece=2)

This is nice, e.g. for testing purposes, but mind that the exact type of an event will likely be unknown to us at compile time, so what we'd actually like to run is

Event.from_json(e0.to_json)
# raises "Error: can't instantiate abstract struct Event"

Unfortunately, this raises an error: by default, the deserializer defined within the JSON::Serializable module tries to instantiate an Event object. As we mentioned above, this is not possible, due to the abstract nature of the type. So, where do we go from here?

Discriminators to the rescue

Here is an idea: in order to deserialize a JSON payload to the correct runtime type, we will attach some extra metadata about the event type to the JSON itself. We call this field a discriminator.

Luckily, the json module comes with an aptly named use_json_discriminator macro. This will give us the deserialization capability we are looking for, but it's up to us to make sure that the discriminator field is populated properly at serialization time.

Let's update our code to add support for discriminators.

abstract struct Event
  include JSON::Serializable

  use_json_discriminator "type", {
    connected: Connected,
    started: Started
  }
end

struct Connected < Event
  getter peer
  getter type = "connected"
  def initialize(@peer : Peer); end
end

struct Started < Event
  getter peer, piece
  getter type = "started"
  def initialize(@peer : Peer, @piece : UInt32); end
end

OK, what's going here?

On line 4, we call use_json_discriminator by providing a mapping between a discriminator field value and a type. The deserializer expects the discriminator to appear under the "type" field, in this case.
lines 12 and 18 ensure that the type field is populated according to the event type name.

You'll notice a correspondence between the value of each type field and the discriminator mapping.

Let's check how this affects our serializer.

e0.to_json #=> {"type":"connected","peer":"0.0.0.0"}
e1.to_json #=> {"type":"started","peer":"0.0.0.0","piece":2}

Notice how the type metadata is now part of the generated JSON. This in turn makes the following work:

Event.from_json(e0.to_json) #=> Connected(@type="connected", @peer="0.0.0.0")
Event.from_json(e1.to_json) #=> Started(@type="started", @peer="0.0.0.0", @piece=2)

Brilliant!

Composing composite types

The above works all right with composite types where fields are primitive types, but what if we were to define composite types on the top of other composite types? 😱

Let's expand the definition of Peer to check this out:

struct Peer
  getter address : String
  getter port : Int32

  def initialize(@address, @port)
  end
end

e0 = Connected.new(Peer.new("0.0.0.0", 8020))
e1 = Started.new(Peer.new("0.0.0.0", 8020), 2)

Now the following fails

e0.to_json
# raises "Error: no overload matches 'Peer#to_json' with type JSON::Builder"

The compiler is pretty explicit here: it does not know how to turn a Peer object into JSON.

🤔 I know this one! Let's include JSON::Serializable into Peer.

struct Peer
  include JSON::Serializable

  getter address : String
  getter port : Int32

  def initialize(@address, @port)
  end
end

And now try

e0.to_json #=> {"type":"connected","peer":{"address":"0.0.0.0","port":8020}}
e1.to_json #=> {"type":"started","peer":{"address":"0.0.0.0","port":8020},"piece":2}

Success! What about deserialization?

Event.from_json(s0) #=> Connected(@type="connected", @peer=Peer(@address="0.0.0.0", @port=8020))
Event.from_json(s1) #=> Started(@type="started", @peer=Peer(@address="0.0.0.0", @port=8020), @piece=2)

Excellent! This is really all there is to it. Let's wrap up with an interesting trick and some more considerations on the extensibility of this method.

Adding Event subtypes

At present, both the base event type and its implementation are JSON-aware, meaning the code in both includes bits related to the JSON support.

This is not an issue in itself, but it feels like the JSON logic is leaking implementation details into the Event subtypes definition. Could we make it so that an Event implementer does not have to know about the type field? After all, the type getter returns a value that can be computed programmatically - in this case, a downcase version of the type name.

It turns out we can:

abstract struct Event
  include JSON::Serializable

  use_json_discriminator "type", {connected: Connected, started: Started}

  macro inherited
    getter type : String = {{@type.stringify.downcase}}
  end
end

Wait, what is this macro inherited on line 6 about? It's a special macro hook that injects the code in its body into any type inheriting from Event. This is exactly what we need, as it gives us the opportunity to inject the type getter into each implementation of Event and set it to the type name, stringified and downcased. On line 7, note that occurrences of @type in a macro resolve to the name of the instantiating type.

Now the rest of the code looks like this:

struct Connected < Event
  getter peer
  def initialize(@peer : Peer); end
end

struct Started < Event
  getter peer, piece
  def initialize(@peer : Peer, @piece : UInt32); end
end

No trace of JSON logic 🎉

Let's introduce a new Event type to demonstrate this.

# An event indicating the completion of a file piece.
struct Completed < Event
  getter peer, piece
  def initialize(@peer : Peer, @piece : UInt32); end
end

No extra logic on the implementer side, as expected, but mind that we still need to update the discriminator mapping:

abstract struct Event
  use_json_discriminator "type", {
    connected: Connected,
    started: Started,
    completed: Completed
  }
  # ...
end

Challenge. Can we avoid having to manually update the mapping?

Hint: the following macro generates exactly the NamedTupleLiteral we're looking for:

abstract struct Event
  macro subclasses
    {
      {% for name in @type.subclasses %}
      {{ name.stringify.downcase.id }}: {{ name.id }},
      {% end %}
    }
  end
end

Event.subclasses # => {connected: Connected, started: Started, completed: Completed}

Unfortunately, the following does not work.

use_json_discriminator "type", Event.subclasses
#=> raises Error: mapping argument must be a HashLiteral or a NamedTupleLiteral, not Call

This is because at the time when the use_json_discriminator macro is expanded, Event.subclasses hasn't been expanded, yet. I've seen this kind of issues arising often when working with macros: they can save you from writing a lot of code, but composing them can be frustratingly complicated.

Here is my recommendation:

when working with macros, keep it simple. If something feels too complicated, it probably is.

Anyhow, leave a comment in the section below, if you'd like to share your ~~hack~~ solution.

Building an interactive DSL

Lorenzo Barasti — Sat, 11 Jul 2020 08:16:15 +0000

Introduction

Over the past couple of months, I've released a series of videos exploring the fundamentals of building an interactive Domain-Specific Language (iDSL) from the ground up.

To be more specific, the series describes how to build an external DSL and REPL, by means of a general-purpose language - Crystal, in this case. Concepts you'll find here are 100% transferable, so you should be able to replicate the behaviour our iDSL in your favourite language 🚀

I've collected all the episodes in this article, with some further technical comments, reflections and reading recommendations.
You can find the project's source code on GitHub, in case you feel like following along.

Getting ready

I've broken our external iDSL architecture down into 5 components.

1. Read-eval-print-loop (REPL)

A REPL is "an interactive computer programming environment that takes single user inputs (i.e., single expressions), evaluates (executes) them, and returns the result to the user" (source: Wikipedia)

Together with the Runtime System, this component is what makes our language truly interactive. A REPL can make on-boarding new users easier, and let them explore our language API in a frictionless way, e.g. thanks to some auto-completion feature.

2. Parser

A parser takes instructions written in our DSL, and translates them into commands digestible by the language interpreter.

All programming languages have one. Some languages parse input into commands and evaluate them in one go, others hand over the parsed command to an interpreter or are part of a compiler's phases.

In our DSL, the parser will turn user input into an intermediate representation for our interpreter to consume.

3. Interpreter

In our architecture¹, the interpreter is the component that evaluates commands coming from the parser - the Eval in REPL - and computes some result to be handed back to the user.

In very simple languages, commands can be interpreted in isolation, with no context of previously run instructions - a calculator supporting basic arithmetic is a good example of this. If we want to take this further, and interpret commands in context, then we need to leverage a runtime system.

¹According to this Wikipedia definition of interpreter, our parser covers steps 1 and 2, while our interpreter covers step 3.

4. Runtime system

A runtime system is the access point to the DSL's parser and interpreter, and manages the state of the system at runtime. Interestingly, not all runtime systems support running commands interactively. We'll make sure ours does 😉

5. Command Line Interface (CLI)

To enable our users to launch scripts or run the REPL from the command line, we'll provide the user with a command-line interface. Our CLI will be akin to python, in particular.

Getting the REPL out of the way

I first had the idea to make a video on how to build a REPL when I stumbled upon Fancyline, a Crystal library that makes it extremely easy to build complex behaviour into your CLI.

This series was the perfect use case to try it out, so, in session 1, we leverage Fancyline to write a general-purpose REPL featuring error handling, command history and backward search. Just brilliant 🌠

Code highlight. In session 5, we'll add support for one more feature: loading scripts from the REPL via the magic-command %load. Here is what that looks like in the code:

if input.starts_with?("%load")
  filepath = input.lchop("%load").strip
  File.each_line(filepath) { |line|
    Repl.eval_and_print process, line
  }
else
  Repl.eval_and_print process, input
end

Parsing with parser combinators

In session 2, we build a parser for a prototypical iDSL called IGOL (Interactive [Conway's] Game Of Life).

Thanks to Pars3k, a Crystal library implementing parser combinators, we can define a modular, human-readable and testable parser in a few lines of code.

I've known about parser combinators for a while, but this introduction by Li Haoyi - an exceptional member of the Scala community - reignited my interest in building something with them 🙏

Code highlight. I used the dataclass macro to define the Algebraic Data Types representing the commands. Here is an example from the code:

dataclass Apply{coord : {Int32, Int32}, pattern : VarName | Pattern} < Command

Reminder. Unlike structs, classes support defining recursive data types. This is a pretty desirable feature when defining the grammar of a language - see this example.

Interpreting commands

In session 3, we define the interpreter as a function that transforms a State and a Command into a new State, plus some return value. A signature for such a function could look like

def interpret(state : State, command : Command) : {State, T}

where T is the type of the return value.

In this first implementation, we limit state management to the GameOfLife grid, and always return a String as return type.

Code highlight. We leverage Crystal's case statement to safely match a command to its runtime type. Note how the return type of interpret is a tuple containing:

the new State of the system
the result of the command execution - this will be presented to the user by the Print step of our REPL.

def self.interpret(state : State, command : Command) : {State, String}
  case command
  when Show
    {state, state.grid.draw}
  when Evolve
    new_grid = state.grid.evolve(command.n)
    new_state = state.copy(grid: new_grid)
    {new_state, new_grid.draw}
  # ...
end

You can look at the code above in context here.

Generic runtime systems

In session 4, we define a generic runtime system to support any interactive DSL. To prove it, we'll define a minimal DSL for a counter - not the most exciting DSL in the world, I admit - and show how effortless it is to plug it into the runtime.

Code highlight. The runtime class is a beautiful display of Crystal generics: in the code below, State, Cmd and Err are type parameters, meaning you can instantiate the Runtime class with any state, parser and interpreter satisfying the given generic signatures.

class Runtime(State, Cmd, Err)
  def initialize(
    @state : State,
    @parser : String -> Cmd | Err,
    @interpreter : State, Cmd -> {State, String})
  end

  def run(input : String)
    command = @parser.call(input)
    case command
    when Cmd
      @state, output = @interpreter.call(@state, command)
      input.strip.ends_with?(";") ? nil : output
    else
      "Syntax error: #{command}"
    end
  end
end

A user friendly CLI

In session 5, we define a user-friendly CLI that will either launch the REPL or run a script, depending on whether a file path is provided.

We'll see how Clim, a Crystal library to build CLIs, makes it simple to put together a CLI that is both pretty and extensible, in a few lines of code.

Code highlight. To make the CLI reusable by other iDSLs, we used macros 🔮

module CLI
  macro run(mod)
    class {{mod}}_CLI < Clim
      main do
        desc "{{mod}} interpreter"
        usage {{mod.stringify.downcase}} + " [option] [filepath]"
        version "Version #{{{mod}}.version}", short: "-v"
        help short: "-h"
        argument "filepath", type: String, desc: "path to {{mod}} script"
        # ...

This allows us to instantiate a CLI for any iDSL, provided that their module defines the #version and #runtime methods. Here is the final main for the IGOL iDSL:

require "./lib/cli"
require "./igol"

CLI.run(IGOL)

And here is the end result:

This is it! If you managed to read this far, then you deserve a ⭐

I hope you enjoyed the write-up and learned something new in the process. If you have any question or would like to share your iDSL stories, then I'd love to read them in the comments section below.

If you'd like to stay in touch, you can follow me on Twitter.

This post was originally published on lbarasti.com.

Conway's Game of Life, sparse

Lorenzo Barasti — Sat, 20 Jun 2020 23:41:50 +0000

Introduction

A lot has been written about Conway's Game of Life. If you're reading this, chances are you've implemented a version of it yourself.

This article offers a visual guide to a less-common formulation of the game and presents a surprisingly succinct implementation of it, mostly for fun.

I'll assume you're already familiar with the game. If that's not the case, I'd recommend reading the original article published on Scientific American in 1970.

Canonical formulation

When you think of Game of Life, you probably think about a grid where live and dead cells are represented with different colors, and the following 3 rules define how to evolve the grid from the current state to the next (source: Wikipedia).

Any live cell with two or three live neighbours survives.
Any dead cell with three live neighbours becomes a live cell.
All other live cells die in the next generation. Similarly, all other dead cells stay dead.

These rules emphasise the role of both live and dead cells and lead to a straight-forward implementation where the state of the system is represented by a matrix of boolean values where each (i, j) entry represents a cell's state: true for live, false for dead.

A sparse formulation

Compact as the above might be, I've always found the following, equivalent formulation more interesting.

Consider an infinite grid of cells defined as per the canonical formulation. For each live cell, gather the coordinates (i, j) of all the cell's neighbours, plus the coordinates of the live cell itself.

Now count the number of times each cell appears in the collection.
Only the cells abiding by the following rules will be part of the next generation:

Any cell that occurs 3 times
Any cell that occurs 4 times and is currently live.

One thing I enjoy about this formulation, is the fact that it leads to a very natural implementation based on a sparse representation of the grid, where we only keep track of live cells.

Given a set of live cells - aptly called population - the next generation can be computed as follows - the code below is in Crystal, but your favourite language's implementation shouldn't differ much from this.

population.flat_map { |cell| expand(cell) }
  .tally
  .select { |cell, count| count == 3 || (count == 4 && population.includes?(cell)) }
  .keys

Here, expand is a simple function that returns the 9 cells in the 3x3 square centered in the cell passed as argument.

OriginSquare = [
  {-1,  1}, {0,  1}, {1,  1},
  {-1,  0}, {0,  0}, {1,  0},
  {-1, -1}, {0, -1}, {1, -1}
]

def expand(cell)
  OriginSquare.map { |(x, y)| {cell[0] + x, cell[1] + y} }
end

Let's explore the code line by means of an example.

Consider the L-shaped population

population = [{2, 0}, {1, 0}, {0, 0}, {0, 1}]

Figure 1. The picture shows the initial population [{2, 0}, {1, 0}, {0, 0}, {0, 1}] on a two-dimensional orthogonal grid of square cells. We can think of the grid as a Cartesian plane where a live cell {x, y} is represented by a gray square with bottom left corner in {x, y}.

We iterate over the live cells and expand them into the neighbouring cells plus the live cell itself - see Figure 2 below.

population.flat_map { |cell| expand(cell) }
# => [{-1, 2}, {0, 2}, {1, 2}, {-1, 1}, ..., {2, -1}, {3, -1}]

Figure 2. The picture represents the expansion of each live cell into the corresponding 3x3 square. Cells in such squares are accumulated into a collection, with repetition. Notice that the number of *stars* in each cell at the end of iteration 4 - bottom right picture - reflects the number of times a cell appears in any expanded square.

We now count the number of times a cell appears in the computed collection. In Crystal, this is as easy as calling #tally on an array. This returns a dictionary from cell to number of occurrences.

population.flat_map { |cell| expand(cell) }
  .tally
  # => {{-1, 2} => 1, {0, 2} => 1, ..., {3, -1} => 1}

Figure 3. The figure shows the number of occurrences for each cell in the expanded squares.

Finally, we filter out any cell that doesn't match either rule 1 or rule 2 defined above. This is done by invoking .select on the dictionary with a predicate representing the rules.

population.flat_map { |cell| expand(cell) }
  .tally
  .select { |cell, count| count == 3 || (count == 4 && population.includes?(cell)) }
  # => {{0, 1} => 3, {0, 0} => 3, {1, 0} => 4, {1, -1} => 3}

Figure 4. The numbers in bold show the new generation of live cells. The light gray squares where the count is 4 are kept alive. Any cell with a count of 3 will be live in the next generation.

We now discard the number of occurrences, and keep the cells' coordinates.

population.flat_map { |cell| expand(cell) }
  .tally
  .select { |cell, count| count == 3 || (count == 4 && population.includes?(cell)) }
  .keys
  # => [{0, 1}, {0, 0}, {1, 0}, {1, -1}]

Figure 5. The new generation of live cells is represented by the squares in light gray.

Excellent! Let's talk about some of the features of this algorithm, but first...

Challenge. Now that we've discussed a script to evolve a population, can you extract this into a function or instance method, so that we can run an arbitrary number of evolutions? I'm thinking about something like

new_population = GameOfLife.evolve(population, times: 20)

Some notes on efficiency

The memory-efficiency of the sparse implementation makes evolving some configurations feasible, where they wouldn't be on the dense one. In particular, we can cope with cells patterns moving arbitrarily far from each other without going out of memory. This is not true for the dense implementation, where an initial population featuring, for example, two spaceships heading in different directions will exhaust your memory fairly quickly.

I like how the sparse implementation encodes a strong system invariant: in terms of state, nothing can ever change far from live cells.

Hence, the sparse implementation is more memory-efficient than the dense one, but the battle for best performance is totally open and depends on the configuration we're evolving. If you're thinking that the dense implementation might enjoy performance gains thanks to GPU architectures, then you're right on point.

Challenge. No matter the underlying implementation, printing a grid on the screen still poses a challenge, as we're materialising a possibly very large grid of cells. Can you think of strategies to display the current state of the grid that don't require printing it in its entirety?

DEV Community: Lorenzo Barasti

Crystal JSON beyond the basics

Introduction

Case study - a P2P client

JSON encoding

Discriminators to the rescue

Composing composite types

Adding Event subtypes

Further reading

Building an interactive DSL

Introduction

Getting ready

1. Read-eval-print-loop (REPL)

2. Parser

3. Interpreter

4. Runtime system

5. Command Line Interface (CLI)

Getting the REPL out of the way

Parsing with parser combinators

Interpreting commands

Generic runtime systems

A user friendly CLI

Conway's Game of Life, sparse

Introduction

Canonical formulation

A sparse formulation

Some notes on efficiency

Further reading