Pat Shaughnessy

LLVM IR: The Esperanto of Computer Languages

2022-02-19T00:00:00Z

Esperanto grammar is logical and self
consistent, designed to be easy to learn.
via Wikimedia Commons

I empathize for people who have to learn English as a foreign language. English grammar is inconsistent, arbitrary and hard to master. English spelling is even worse. I sometimes find myself apologizing for my language’s shortcomings. But learning any foreign language as an adult is very difficult.

Esperanto, an “artificial language,” is different. Invented by Ludwik Zamenhof in 1873, Esperanto has a vocabulary and grammar that are logical and consistent, designed to be easier to learn. Zamenhof intended Esperanto to become the universal second language.

Computers have to learn foreign languages too. Every time you compile and run a program, your compiler translates your code into a foreign language: the native machine language that runs on your target platform. Compilers should have been called translators. And compilers struggle with the same things we do: inconsistent grammar and vocabulary, and other peculiarities of the target platform.

Recently, however, more and more compilers translate your code to an artificial machine language. They produce a simpler, more consistent, more powerful machine language that doesn’t actually run on any machine. This artificial machine language, LLVM IR, makes writing compilers simpler and reading the code compilers produce simpler too.

LLVM IR is becoming the universal second language for compilers.

One Line of LLVM IR

The Low Level Virtual Machine (LLVM) project had the novel idea of inventing a virtual machine that was easy for compiler engineers to use as a target platform. The LLVM team designed a special instruction set called intermediate representation (IR). New, modern languages such as Rust, Swift, Clang-based versions of C and many others, first translate your code to LLVM IR. Then they use the LLVM framework to convert the IR into actual machine language for any target platform LLVM supports:

LLVM is great for compilers. Compiler engineers don’t have to worry about the detailed instruction set of each platform, and LLVM optimizes your code for whatever platform you choose automatically. And LLVM is also great for people like me who are interested in what machine language instructions look like and how CPUs execute them. LLVM instructions are much easier to follow than real machine instructions. Let’s take a look at one!

Here’s a line of LLVM IR I generated from a simple Crystal program:

%57 = call %"Array(Int32)"* @"*Array(Int32)@Array(T)::unsafe_build:Array(Int32)"(i32 610, i32 2), !dbg !89

Wait a minute! This isn’t simple or easy to follow at all! What am I talking about here? At first glance, this does look confusing. But as we’ll see, most of the confusing syntax is related to Crystal, not LLVM. Studying this line of code will reveal more about Crystal than it will about LLVM.

The rest of this article will unpack and explain what this line of code means. It looks complex, but is actually quite simple.

The Call Instruction

The instruction above is a function call in LLVM IR. To produce this code, I wrote a small Crystal program and then translated it using this command:

$ crystal build array_example.cr --emit llvm-ir

The --emit option directed Crystal to generate a file called array_example.ll, which contains the line above along with thousands of other lines. We’ll get to the Crystal code in a minute. But for now, how do I get started understanding what the LLVM code means?

The LLVM Language Reference Manual has documentation for call and all of the other LLVM IR instructions. Here’s the syntax for call:

<result> = [tail | musttail | notail ] call [fast-math flags] [cconv] [ret attrs] [addrspace(<num>)]
         <ty>|<fnty> <fnptrval>(<function args>) [fn attrs] [ operand bundles ]

My example call instruction doesn’t use many of these options. Removing the unused options, I can see the actual, basic syntax of call:

<result> = call <ty> <fnptrval>(<function args>)

In order from left to right, these values are:

<result> which register to save the result in
<ty> the type of the return value
<fnptrval> a pointer to the function to call
<function args> the arguments to pass to that function

What does all of this mean, exactly? Let’s find out!

A CPU With Infinite Registers

Starting on the left and moving right, let’s step through the call instruction:

The token %57 to the left of the equals sign tells LLVM where to save the return value of the function call that follows. This isn’t a normal variable; %57 is an LLVM “register.”

Registers are physical circuits located on microprocessor chips used to save intermediate values. Saving a value in a CPU register is much faster than saving a value in memory, since the register is located on the same chip as the rest of the microprocessor. Saving a value in RAM memory, on the other hand, requires transmitting that value from one chip to another and is much slower, relatively speaking. Unfortunately, each CPU has a limited number of registers available, and so compilers have to decide which values are used frequently enough to warrant saving in nearby registers, and which other values can be moved out to more distant memory.

Unlike the limited number of registers available on a real CPU, the imaginary LLVM microprocessor has an infinite number of them. Because of this, compilers that target LLVM can simply save values to a register whenever they would like. There’s no need to find an available register, or to move an existing value out of a register first before using it for something else. Busy work that normal machine language code can’t avoid.

In this program, the Crystal compiler had already saved 56 other values in “registers” and so for this line of LLVM IR, Crystal simply used the next register, number 57.

LLVM Structure Types

Moving left to right, LLVM call instructions next indicate the type of the function call’s return value:

This name of this type, Array(Int32), is generated by the Crystal compiler, not by LLVM. That is, this is a type from my Crystal program. It could have been anything, and indeed other compilers that target LLVM will generate completely different type names.

The example Crystal program I used to generate this LLVM code was:

arr = [12345, 67890]
puts arr[1]

When I compiled this program, Crystal generated the call instruction above, which returns a pointer to the new array, arr. Since arr is an array containing integers, Crystal uses a generic type Array(Int32).

Machine languages that target real machines only support hardware types that machine supports. For example, Intel x86 assembly language allows you to save integers of different widths, 16, 32 or 64 bits for example, and an Intel x86 CPU has registers designed to hold values of each of these sizes.

LLVM IR is more powerful. It supports “structure types,” similar to a C structure or an object in a language like Crystal or Swift. Here the %"…" syntax indicates the name inside the quotes is the name of a structure type. And the asterisk which follows, like in C, indicates the type of the return value of my function call is a pointer to this structure.

My example LLVM program defines the type Array(Int32) like this:

%"Array(Int32)" = type { i32, i32, i32, i32, i32* }

Structure types allow LLVM IR programs to create pointers to structures or objects, and to access any of the values inside each object. That makes writing a compiler much easier. In my example, the call instruction returns a pointer to an object which contains 4 32-bit integer values, followed by a pointer to other 32 integer values. But what are all of these integer values? Above I said this function call was returning a new array - how can that be the case?

LLVM itself has no idea, and no opinion on the matter. To understand what these values are, and what they have to do with the array in my program, we need to learn more about the Crystal compiler that generated this LLVM IR code.

Reading the Crystal standard library, we can see Crystal implements arrays like this:

class Array(T)
include Indexable::Mutable(T)
include Comparable(Array)

# Size of an Array that we consider small to do linear scans or other optimizations.
private SMALL_ARRAY_SIZE = 16 

# The size of this array.
@size : Int32

# The capacity of `@buffer`.
# Note that, because `@buffer` moves on shift, the actual
# capacity (the allocated memory) starts at `@buffer - @offset_to_buffer`.
# The actual capacity is also given by the `remaining_capacity` internal method.
@capacity : Int32

# Offset to the buffer that was originally allocated, and which needs to
# be reallocated on resize. On shift this value gets increased, together with
# `@buffer`. To reach the root buffer you have to do `@buffer - @offset_to_buffer`,
# and this is also provided by the `root_buffer` internal method.
@offset_to_buffer : Int32 = 0

# The buffer where elements start.
@buffer : Pointer(T)

# In 64 bits the Array is composed then by:
# - type_id            : Int32   # 4 bytes -|
# - size               : Int32   # 4 bytes  |- packed as 8 bytes
#
# - capacity           : Int32   # 4 bytes -|
# - offset_to_buffer   : Int32   # 4 bytes  |- packed as 8 bytes
#
# - buffer             : Pointer # 8 bytes  |- another 8 bytes

The comments above are very illustrative and complete - the Crystal team took the time to document their standard library and explain not only how to use each class, like Array(T), but how they are implemented internally.

In this case, we can see the four i32 values inside the Array(Int32) LLVM structure type hold the size and capacity off the array, among other things. And the i32* value is a pointer to the actual contents of the array.

Functions

The target of the call instruction appears next, after the return type:

This is quite a mouthful! What sort of function is this?

There are two steps to understanding this: First, the @"…" syntax. This is simply a global identifier in this LLVM program. So my call instruction is just calling a global function. In LLVM programs, all functions are global; there is no concept of a class, module or similar groupings of code.

But what in the world does that crazy identifier mean?

LLVM ignores this complex name. For LLVM this is just a name like foo or bar. But for Crystal, the name has much more significance. Crystal encoded a lot of information into this one name. Crystal can do this because the LLVM code isn’t intended for anyone to read directly. Crystal has created a “mangled name,” meaning the original version of the function to call is there but it’s been mangled or rewritten in a confusing manner.

Crystal rewrites function names to ensure they are unique. In Crystal, like in many other statically typed languages, functions with different argument types or return value types are actually different functions. So in Crystal if I write:

def foo(a : Int32)
puts "Int: #{a}"
end

def foo(a : String)
puts "String: #{a}"
end

foo(123)
#=> Int: 123
foo("123")
#=> String: 123

…I have two separate, different functions both called foo. The type of the parameter a distinguishes one from the other.

Crystal generates unique function names by encoding the arguments, return value and type of the receiver into the into the function name string, making it quite complex. Let’s break it down:

Array(Int32)@Array(T) - this is the type of the receiver. That means the unsafe_build function is actually a method on the Array(T) generic class. And in this case, the receiver is an array holding 32 bit integers, the Array(Int32) class. Crystal includes both names in the mangled function name.
unsafe_build - this is the function Crystal is calling.
Int32 - these are the function’s parameter types. In this case, Crystal is passing in a single integer, so we just see one Int32 type.
Array(Int32) - this is the return value type, a new array containing integers.

As I discussed in my last post, the Crystal compiler internally rewrites my array literal expression [12345, 67890] into code that creates and initializes a new array object:

__temp_621 = ::Array(typeof(12345, 67890)).unsafe_build(2)
__temp_622 = __temp_621.to_unsafe
__temp_622[0] = 12345
__temp_622[1] = 67890
__temp_621

In this expanded code, Crystal calls unsafe_build and passes in 2, the required capacity of the new array. And to distinguish this use of unsafe_build from other unsafe_build functions that might exist in my program, the compiler generated the mangled name we see above.

Arguments

Finally, after the function name the LLVM IR instruction shows the arguments for the function call:

LLVM IR uses parentheses, like most languages, to enclose the arguments to a function call. And the types precede each value: 610 is a 32-bit integer and 2 is also a 32-bit integer.

But wait a minute! We saw just above the expanded Crystal code for generating the array literal passes a single value, 2, into the call to unsafe_build. And looking at the mangled function name above, we also see there is a single i32 parameter to the function call.

But reading the LLVM IR code we can see a second value is also passed in: 610. What in the world does 610 mean? I don’t have 610 elements in my new array, and 610 is not one of the array elements. So what is going on here?

Crystal is an object oriented language, meaning that each function is optionally associated with a class. In OOP parlance, we say that we are “sending a message” to a “receiver.” In this case, unsafe_build is the message, and ::Array(typeof(12345, 67890)) is the receiver. In fact, this function is really a class method. We are calling unsafe_build on the Array(Int32) class, not on an instance of one array.

Regardless, LLVM IR does’t support classes or instance methods or class methods. In LLVM IR, we only have simple, global functions. And indeed, the LLVM virtual machine doesn’t care what these arguments are or what they mean. LLVM doesn’t encode the meaning or purpose of each argument; it just does what the Crystal compiler tells it to do.

But Crystal, on the other hand, has to implement object oriented behavior somehow. Specifically, the unsafe_build function needs to behave differently depending on which class it was called for, depending on what the receiver is. For example:

::Array(typeof(12345, 67890)).unsafe_build(2)

… has to return an array of two integers. While:

::Array(typeof("abc", "def")).unsafe_build(2)

…has to return an array of two strings. How does this work in the LLVM IR code?

To implement object oriented behavior, Crystal passes the receiver as a hidden, special argument to the function call:

This receiver argument is a reference or pointer to the receiver’s object, and is normally known as self. Here 610 is a reference or tag corresponding to the Array(Int32) class, the receiver. And 2 is the actual argument to the unsafe_build method.

Reading the LLVM IR code, we’ve learned that Crystal secretly passes a hidden self argument to every method call to an object. Then inside each method, the code has access to self, to the object instance that code is running for. Some languages, like Rust, require us to pass self explicitly in each method call; in Crystal this behavior is automatic and hidden.

Learning How Compilers Work

LLVM IR is a simple language designed for compiler engineers. I think of it like a blank slate for them to write on. Most LLVM instructions are quite simple and easy to understand; as we saw above, understanding the basic syntax of the call instruction wasn’t hard at all.

The hard part was understanding how the Crystal compiler, which targets LLVM IR, generates code. The LLVM syntax itself was easy to follow; it was the Crystal language’s implementation that was harder to understand.

And this is the real reason to learn about LLVM IR syntax. If you take the time to learn how LLVM instructions work, then you can start to read the code your favorite language’s compiler generates. And once you can do that, you can learn more about how your favorite compiler works, and what your programs actually do when you run them.

Visiting an Abstract Syntax Tree

2022-01-22T00:00:00Z

Joshua Tree National Park (via: Wikimedia Commons)

In my last post, I explored how Crystal parsed a simple program and produced a data structure called an abstract syntax tree (AST). But what does Crystal do with the AST? Why bother going to such lengths to create it?

After Crystal parses my code, it repeatedly steps through all the entries or nodes in the AST and builds up a description of the intended meaning and behavior of my code. This process is known as semantic analysis. Later, Crystal will use this description to convert my program into a machine language executable.

But what does this description contain? What does it really mean for a compiler to understand anything? Let’s pack our bags and visit an abstract syntax tree with Crystal to find out.

The Visitor Pattern

Imagine several tourists visiting a famous tree: Each of them sees the same tree in a different way. The tree doesn’t change, but the perspective of each person looking at it is different. They each take a different photo, or remember different details.

In Computer Science this separation of the data structure (the tree) from the algorithms using it (the tourists) is known as the visitor pattern. This technique allows compilers and other programs to run multiple algorithms on the same data structure without making a mess.

The visitor pattern calls for two functions: accept and visit. First, a node in the data structure “accepts” a visitor:

After accepting a visitor, the node turns around and calls the visit method on Visitor:

The visit method implements whatever algorithm that visitor is interested in.

This seems kind of pointless… why use accept at all? We could just call visit directly. The key is that, after calling the visitor and passing itself, the node passes the visitor to each of its children, recursively:

And then the visitor can visit each of the child nodes also. The Visitor class doesn’t necessarily need to know anything about how to navigate the node data structure. And more and more visitor classes can implement new algorithms without changing the underlying data structure and breaking each other.

The Visitor Pattern in the Crystal Compiler

In order to understand what my code means, Crystal reads through my program’s AST over and over again using different visitors. Each algorithm looks for certain syntax, records information about the types and objects my code uses or possibly even transforms my code into a different form.

A photo I took in 2018 of Angel Oak,
a 400-500 year old tree in South Carolina.

Crystal implements the basics of the visitor pattern in visitor.cr, inside the superclass of all AST nodes:

class ASTNode
  def accept(visitor)
    if visitor.visit_any self
      if visitor.visit self
        accept_children visitor
      end
      visitor.end_visit self
      visitor.end_visit_any self
    end
  end
end

Each subclass of ASTNode implements its own version of accept_children.

My Tiny Crystal Program

To get a sense of how the visitor pattern works inside of Crystal, let’s look at one line of code from my last post:

arr = [12345, 67890]

As I explained last month, the Crystal parser generates this AST tree fragment:

Once the parser is finished and has created this small tree, the Crystal compiler steps through it a number of different times, looking for classes, variables, type declarations, etc. Each of these passes through the AST is performed by a different visitor class: TopLevelVisitor, InstanceVarsInitializerVisitor or ClassVarsInitializerVisitor among many others.

The most important visitor class the Crystal compiler uses is called simply MainVisitor. You can find the code for MainVisitor in main_visitor.cr:

# This is the main visitor of the program, ran after types have been declared
# and their type declarations (like `@x : Int32`) have been processed.
#
# This visits the "main" code of the program and resolves calls, instantiates
# methods and visits them, recursively, with other MainVisitors.
#
# The visitor keeps track of a method's variables (or the main program, split into
# several files, in case of top-level code). It keeps track both of the type of a
# variable at a single point (stored in @vars) and the combined type of all assignments
# to it (in @meta_vars).
#
# Call resolution logic is in `Call#recalculate`, where method lookup is done.
class MainVisitor < SemanticVisitor

Since Crystal supports typed parameters and method overloading, the visitor class implements a different visit method for each type of node that it visits, for example:

class MainVisitor < SemanticVisitor
  def visit(node : Assign)
  def visit(node : Var)
  def visit(node : ArrayLiteral)
  def visit(node : NumberLiteral)

Etc…

Now let’s look at three examples of what the MainVisitor class does with my code: identifying variables, assigning types and expanding array literals. The Crystal compiler is much too complex to describe in a single blog post, but hopefully I can give you glimpse into the sort of work Crystal does during semantic analysis.

Identifying Variables

Obviously, my example code creates and initializes a variable called arr:

arr = [12345, 67890]

But how does Crystal identify this variable’s name and value? What does it do with arr?

The MainVisitor class starts to process my code by visiting the root node of this branch of my AST, the Assign node:

As you can see, earlier during the parsing phrase Crystal had saved the target variable and value of this assign statement in the child AST nodes. The target variable, arr, appears in the Var node, and the value to assign is an ArrayLiteral node. The MainVisitor now knows I declared a new variable, called arr, in the current lexical scope. Since my program has no classes, methods or any other lexical scopes, Crystal saves this variable in a table of variables for the top level program:

Actually, to be more accurate, there will always be many other variables in this table along with arr. All Crystal programs automatically include the standard library, so Crystal also saves all of the top level variables from the standard library in this table.

In a more normal program, there will be many lexical scopes for different method and class or module definitions, and MainVisitor will save each variable in the corresponding table.

Assigning Types

Probably the most important function of MainVisitor is to assign a type to each value in my program. The simplest example of this is when MainVisitor visits a NumberLiteral node:

Looking at the size of the numeric value, Crystal determines the type should be Int32. Crystal then saves this type right inside of the NumberLiteral node:

Strictly speaking, this violates the visitor pattern because the visitors shouldn’t be modifying the data structure they visit. But the type of each node, the type of each programming construct in my program, is really an integral part of that node. In this case the MainVisitor is really just completing each node. It’s not changing the structure of the AST in this case… although as we’ll see in a minute the MainVisitor does this for other nodes!

Type Inference

Sometimes type values can’t be determined from the intrinsic value of an AST node. Often the type of a node is determined by other nodes in the AST.

Recall my example line of code is:

arr = [12345, 67890]

Here Crystal automatically sets the type of the arr variable to the type of the array literal expression: Array(Int32). In Computer Science, this is known as type inference. Because Crystal can automatically determine the type of arr, I don’t need to declare it explicitly by writing something more complicated like this:

arr = uninitialized Array(Int32)
arr = [12345, 67890]

Type inference allows me to write concise, clean code with fewer type annotations. Most modern, statically typed languages such as Swift, Rust, Julia, Kotlin, etc., use type inference in the same way as Crystal. Even newer versions of Java or C++ use type inference.

The Crystal compiler implements type inference when the MainVisitor encounters an Assign AST node, what we saw above.

After encountering the Assign node, Crystal recursively processes one of the two child nodes, the ArrayLiteral value, and its child nodes. When this process finishes, Crystal knows the type of the ArrayLiteral node is Array(Int32):

I’ll take a closer look at how Crystal processes the ArrayLiteral node next. But for now, once Crystal has the type of the ArrayLiteral node it copies that type over to the Var node and sets its type also:

But Crystal does something else interesting here: It sets up a dependency between the two AST nodes: it “binds” the variable to the value:

This binding dependency allows Crystal to later update the type of the arr variable whenever necessary. In this case the value [12345, 67890] will always have the same type, but I suspect that sometimes the Crystal compiler can update types during semantic analysis. In this way if the Crystal compiler ever changed its mind about the type of some value, it can easy update the types of any dependent values. I also suspect Crystal uses these type dependency connections to produce error messages whenever you pass an incorrect type to some function, for example. These are just guesses, however; if anyone from the Crystal team knows exactly what these type bindings are used for let me know.

Update: Ary Borenszweig explained that sometimes the Crystal compiler updates the type of variables based on how they are used. He posted an interesting example on The Crystal Programming Language Forum.

Expanding an Array Literal

So far we’ve seen Crystal set the type of the NumberLiteral node to Int32, and we’ve seen Crystal assign arr a type of Array(Int32). But how did Crystal determine the type of the array literal [12345, 67890]?

This is where things get even more complicated. Sometimes during semantic analysis the Crystal compiler completely rewrites parts of your code, replacing it with something else. This happens even with my simple example. When visiting the ArrayLiteral node, the MainVisitor expands this simple line of code into something more complex:

__temp_621 = ::Array(typeof(12345, 67890)).unsafe_build(2)
__temp_622 = __temp_621.to_unsafe
__temp_622[0] = 12345
__temp_622[1] = 67890
__temp_621

Reading this, you can see how later my compiled program will create the new array. First Crystal creates an empty array with a capacity of 2, and an element type of Int32. typeof(12345, 67890) returns the type (or multiple types inside a union type) found in the given set of values, in this case just Int32. Later Crystal sets the two elements in the array just by assigning them.

Crystal achieves this by replacing part of my program’s AST with a new branch:

For clarity, I’m not drawing the AST nodes for the inner assign operations, only the first line:

__temp_621 = ::Array(typeof(12345, 67890)).unsafe_build(2)

Putting It All Together

With this new, updated AST we can see exactly how Crystal determines the type of my variable arr. Starting at the root of my AST, MainVisitor visits all of the AST nodes in this order in a series of recursive calls:

And it determines the types of each of these nodes as it returns from the recursive calls:

Some interesting details here that I don’t understand completely or have space to explain here:

The TypeOf node calculates a common union type using a type formula. In this example, it just returns Int32 because both elements of my array, 12345 and 67890, are simple 32 bit integers.
I believe the Generic node refers to a Crystal generic class via the Path node shown above, in this example Array(T). When MainVisitor processes the Generic node, it sets T to the type Int32, arriving at the type Array(Int32).class.
The Call node looks up the method my code is calling (unsafe_build) and uses the type from that method’s return value. I didn’t have time to explore how method lookup works in Crystal, however, so I’m not sure about this.

Scratching the Surface

Today we looked at a tiny piece of what the Crystal compiler can do. There are many more types of AST nodes, each of which the MainVisitor class handles differently. And there are many different visitor classes also, beyond MainVisitor. When analyzing a more complex program Crystal has to understand class and module definitions, instance and class variables, type annotations, different lexical scopes, macros, and much, much more. Crystal will need all of this information later, during the code generation phase, the next step that follows semantic analysis.

But I hope this article gave you a sense of what sort of work a compiler has to do in order to understand your code. As you can see, for a statically typed language like Crystal the compiler spends much of its time identifying all of the types in your code, and determining which programming constructs or AST nodes have which types.

Next time I’ll look at code generation: Now that Crystal has identified the variables, function calls and types in my code it is ready to generate the machine language code needed to execute my program. To do that, it will leverage the LLVM framework.

Reading Code Like a Compiler

2021-12-22T00:00:00Z

Imagine trying to read an entire book while
focusing on only one or two words at a time

We use compilers every day to parse our code, find our programming mistakes and then help us fix them. But how do compilers read and understand our code? What does our code look like to them?

We tend to read code like we would read a human language like English. We don’t see letters; we see words and phrases. And in a very natural way we use what we just read, the proceeding sentence or paragraph, to give us the context we need to understand the following text. And sometimes we just skim over text quickly to gleam a bit of the meaning without even reading every word.

Compilers aren’t as smart as we are. They can’t read and understand entire phrases or sentences all at once. They read text one letter, one word at at time, meticulously building up a record of what they have read so far.

I was curious to learn more about how compilers parse text, but where should I look? Which compiler should I study? Once again, like in my last few posts, Crystal was the answer.

Crystal: A Compiler Accessible to Everyone

Crystal is a unique combination of simple, human syntax inspired by Ruby, with the speed and robustness enabled by static types and the use of LLVM. But for me the most exciting thing about Crystal is how the Crystal team implemented both its standard library and compiler using the target language: Crystal. This makes Crystal’s internal implementation accessible to anyone familiar with Ruby. For once, you don’t have to be a hard core C or C++ developer to learn how a compiler works. Reading code not much more complex than a Ruby on Rails web site, I can take a peek under the hood of a real world compiler to see how it works internally.

Not only did the Crystal team implement their compiler using Crystal, they also wrote it by hand. Parsing is such a tedious task that often developers use a parser generator, such as GNU Bison, to automatically generate the parse code given a set of rules. This is how Ruby works, for example. But the Crystal team wrote their parser directly in Crystal, which you can read in parser.cr.

Along with a readable compiler, I need a readable program to compile. I decided to reuse the same array snippet from my last post:

arr = [12345, 67890]
puts arr[1]

This tiny Crystal program creates an array of two numbers and then prints out the second number. Simple enough: You and I can read and parse these two lines of code in one glance and in a fraction of a second understand what it does. Even if you’re not a Crystal or Ruby developer this syntax is so simple you can still understand it.

But the Crystal compiler can’t understand this code as easily as we can. Parsing even this simple program is a complex task for a compiler.

How the Crystal Compiler Sees My Code

Before parsing or running the code above, Crystal converts it into a series of tokens. To the Crystal compiler, my program looks like this:

The first IDENT token corresponds to the arr variable at the beginning of the first line. You can also see two NUMBER tokens: the Crystal tokenizer code converted each series of numerical digits into single tokens, one for 12345 and the other for 67890. Along with these tokens you can also see other tokens for punctuation used in Crystal syntax, like the equals sign and left and right square brackets. There is also a new line token and one for the end of the entire file.

Reading a Book One Word at a Time

To understand my code, Crystal processes these tokens one at a time, stepping tediously through the entire program. What a slow, painful process!

How would we read if we could only see one word at a time? I imagine covering the book I’m trying to read with a piece of paper or plastic that had a small hole in it… and that through the hole I could only see one word at a time. How would I read one entire page? Well, I’d have to move the paper around, showing one word and then another and another. And how would I know where to move the paper next? Would I simply move the paper forward one word at at time? What if I forgot some word I had seen earlier? I’d have to backtrack - but how far back to go? What if the meaning of the word I was looking at depended on the words that followed it? This sounds like a nightmare.

To read like this, if it was even possible at all, I’d have to have a well thought out strategy. I’d have to know exactly how to move that plastic screen around. When you can only read one word at a time, deciding which word to read next becomes incredibly important. I would need an algorithm to follow.

This is what a parser algorithm is: Some set of rules the parse code can use to interpret each word, and, equally important, to decide which word to read next. Crystal’s parse code is over 6000 lines long, so I won’t attempt to completely explain it here. But there’s an underlying, high level algorithm the parse code uses:

First, the parser compares the current token, and possibly the following or previous tokens as well, to a series of expected patterns. These patterns define the syntax the parser is reading. Second, the parser recurses. It calls itself to parse the next token, or possibly multiple next tokens depending on which pattern the parser just matched. Finally, the parser records what it saw: which pattern matched the current token and the results of the recursive calls to itself, for future reference.

Matching a Pattern

The best way to understand how this works is to see it in action. Let’s follow along with the Crystal compiler as it parses the code I showed above:

arr = [12345, 67890]
puts arr[1]

Recall Crystal already converted this code into a token stream:

(To be more accurate, Crystal actually converts my code into tokens as it goes. The parse code calls the tokenizer code each time it needs a new token. But this timing isn’t really important.)

As you might expect, Crystal starts with the first token, IDENT.

What does this mean? How does Crystal interpret arr? IDENT is short for identifier, but what role does this identifier play? What meaning does arr have in my code?

To decide on the correct meaning, the Crystal parser compares the IDENT token with a series of patterns. For example Crystal looks for patterns like:

a ternary expression a ? b : c
a range a..b
an expression using a binary operator, such as: a + b, etc.
and many more…

It turns out none of these patterns apply in this case, and Crystal ends up selecting a default pattern which handles the most common code pattern: a function call. Crystal decides that when I wrote arr I intended to call a function called arr.

I often tell people I work with at my day job that I have really bad memory. And it’s true. I constantly have to google the syntax or return values of functions. I often forget what some code means even just a month after I wrote it. And the Crystal compiler is no better: As soon as it processes that IDENT token above, it has to write down what it decided that token meant or else it would forget.

To record the function call, Crystal creates an object:

As we’ll see in a moment, Crystal builds up a tree of these objects, called an Abstract Syntax Tree (AST). The AST will later serve as a record of the syntactic structure of my code.

Recursively Calling Itself

Parsing is inherently a recursive process. Unlike English text, Crystal expressions can be nested one inside another to any depth. Although I suppose English grammar is somewhat recursive and can be nested to some degree. I wonder if the grammars for some other human languages are more recursive than English? Interesting question.

For parsing a programming language like Crystal, the simplest thing for the parser code to do is recursively call itself. And it does this based on the pattern it just matched. For example, if Crystal had parsed a plus sign, it would need to recursively call itself to parse the values that appeared before and after the plus.

In this example, Crystal has to decide what arguments to pass to this call to the arr function. Did I write arr(1, 2, 3) or just arr? Or arr()? What were the values 1, 2 and 3? Each of these could be a complex expression in their own right, maybe appearing inside of parentheses, a compound value like an array or maybe yet another function call.

To find the arguments of the function call, inside the recursive call to the parse code Crystal proceeds forward to process the next two tokens:

Crystal skips over the space, and then encounters the equals sign. Suddenly Crystal realizes it was wrong! The arr identifier wasn’t a reference to a function at all, it was a variable declaration. Yes, sometimes compilers change their minds while reading, just like we do!

Recording an AST Node

To record this new, revised syntax, Crystal changes the Call AST node it created earlier to an Assign AST node, and creates a new Var AST node to record the variable being assigned to:

Now the AST is starting to resemble a tree. Because of the recursive nature of parse algorithm, this tree structure is an ideal way of record what the compiler has parsed so far. Trees are recursive too: Each branch is a tree in its own right.

Rinse and Repeat

But what value should Crystal assign to that variable? What should appear in the AST as the value attribute of the Assign node?

To find out, the Crystal compiler recursively calls the same parsing algorithm again, but starting with the [ token:

Following the pattern match, record and recurse process, the Crystal compiler once again matches the new token, [, with a series of expected patterns. This time, Crystal decides that the left bracket is the start of literal array expression and records a new AST node:

But before inserting it into the syntax tree, Crystal recursively calls itself to parse each of the values that appear in the array. The array literal pattern expects a series of values to appear separated by spaces, so Crystal proceeds to process the following tokens, looking for values separated by commas:

After encountering the comma, Crystal recursively calls the same parse code again on the previous token or tokens that appeared before the comma, because the array value before the comma could be another expression of arbitrary depth and complexity. In this example, Crystal finds a simple numeric array element, and creates a new AST node to represent the numeric value:

After reading the comma, Crystal calls its parser recursively again, and finds the second number:

Remember Crystal has a bad memory. With all these new AST nodes, Crystal will quickly forget what they mean. Fortunately, Crystal reads in the right square bracket and realizes I ended the array literal in my code:

Now those recursive calls to the parse code return, and Crystal assembles these new AST nodes:

…and then places them inside the larger, surrounding AST:

After this, these recursive calls return and the Crystal compiler moves on to parse the second line of my program.

A Complete Abstract Syntax Tree

After following the Crystal parser for a while, I added some debug logging code to the compiler so I could see the result. Here’s my example code again:

arr = [12345, 67890]
puts arr[1]

And here’s the complete AST the Crystal compiler generated after parsing my code. My debug logging indented each line to indicate the AST structure:

<Crystal::Expressions exp_count=3 >
  <Crystal::Require string=prelude >
  <Crystal::Assign target=Crystal::Var value=Crystal::ArrayLiteral >
    <Crystal::Var name=arr >
    <Crystal::ArrayLiteral element_count=2 of=Nil name=Nil >
      <Crystal::NumberLiteral number=12345 kind=i32 >
      <Crystal::NumberLiteral number=67890 kind=i32 >
  <Crystal::Call obj= name=puts arg_count=1 >
    <Crystal::Call obj=arr name=[] arg_count=1 >
      <Crystal::Var name=arr >
      <Crystal::NumberLiteral number=1 kind=i32 >

Each of these values is a subclass of the Crystal::ASTNode superclass. Crystal defines all of these in the ast.cr file. Some interesting details to note:

The top level node is called Expressions, and more or less holds one expression per line of code.
The second node, the first child node of Expressions, is called Require. The surprise here is that I didn’t even put a require keyword in my program! Crystal silently inserts require prelude to the beginning of all Crystal programs. The “prelude” is the Crystal standard library, the code that defines Array, String many other core classes. Reading the AST allows us to see how the Crystal compiler does this automatically.
The third node and its children are the nodes we saw Crystal create above for my first line of code, the array literal and the variable it is assigned to.
Finally, the last branch of the tree shows the call to puts. This time Crystal’s default guess about identifiers being function calls was correct. Another interesting detail here is that the inner call to the [] function was not generated by an identifier, but by the [ token. This was one of the patterns the Crystal parser checked for after one of the recursive parse calls.

Next Time

What’s the point of all of this? What does the Crystal compiler do next with the AST? This tree structure is a fantastic summary of how Crystal parsed my code, and, as we’ll see later, also provides a convenient way for Crystal later to process my code and transform it in different ways.

When I have time, I plan to write a few more posts about more of the inner workings of the Crystal compiler and the LLVM framework, which Crystal later uses to generate my x86 executable program.

Find Your Language’s Primitives

2021-11-29T00:00:00Z

If you dig into your programming language's syntax, you might
discover that it is capable of much more than you thought it was.

Wikipedia defines “Language Primitive” this way:

In computing, language primitives are the simplest elements available in a programming language. A primitive is the smallest 'unit of processing' available to a programmer of a given machine, or can be an atomic element of an expression in a language.

By looking at a language’s primitives, we can learn what kind of code will be easy to write or impossible to express, and what types of problems the language was intended to solve. Whether you’ve been using a language for years, or just now learning a new language for fun, take the time to find and learn about your language’s primitives. You might discover something you never knew, and will come away with a deeper understanding of how your programs work.

As an example today, I’m going to look at how arrays work in three languages: Ruby, Crystal and x86 Assembly Language.

Retrieving an Array Element In Ruby

In Ruby I can create an array and later access an element like this:

arr = [12345, 67890]
puts arr[1]

This code would be the same or almost the same in many other programming languages. It just means: “find the second element of the array and print it to stdout.”

But how does this actually work? In Ruby, the Array class and all of its methods are language primitives. This means array methods like [] or []= cannot be broken down into smaller pieces of Ruby code. As Wikipedia says, these methods are the smallest unit of processing available to Ruby programmers working with arrays.

Ruby hides the details of how arrays actually work from us. To learn how Ruby actually saves and retrieves values from an array, we would need to switch languages and drop down a level of abstraction, and read the C implementation in the Ruby source code: array.c. There’s nothing wrong with this, of course. Ruby developers use arrays every day without any trouble. But switching from Ruby to C makes understanding internal details much more difficult.

Retrieving an Array Element In Crystal

This Fall I decided to learn more about Crystal, a statically typed language with syntax that resembles Ruby. I expected to find a similar Array#[] primitive. But surprisingly, I was wrong!

The same code from above also works in Crystal:

arr = [12345, 67890]
puts arr[1]

In Crystal, arrays are not language primitives because the Crystal standard library implements arrays using Crystal itself. The Array#[] method is not the smallest unit of processing available to Crystal programmers. Let’s dig into the details and divide up the [] method into smaller and smaller pieces to see how the Crystal team implemented it.

Reading src/indexable.cr in the Crystal standard library, here’s the implementation of Indexable#[] which the array class uses when I call arr[1] above:

# Returns the element at the given *index*.
#
# Negative indices can be used to start counting from the end of the array.
# Raises `IndexError` if trying to access an element outside the array's range.
#
# ```
# ary = ['a', 'b', 'c']
# ary[0]  # => 'a'
# ary[2]  # => 'c'
# ary[-1] # => 'c'
# ary[-2] # => 'b'
#
# ary[3]  # raises IndexError
# ary[-4] # raises IndexError
# ```
@[AlwaysInline]
def [](index : Int)
  fetch(index) { raise IndexError.new }
end

The Crystal team implemented [] using another method called fetch:

# Returns the element at the given *index*, if in bounds,
# otherwise executes the given block with the index and returns its value.
#
# ```
# a = [:foo, :bar]
# a.fetch(0) { :default_value }    # => :foo
# a.fetch(2) { :default_value }    # => :default_value
# a.fetch(2) { |index| index * 3 } # => 6
# ```
def fetch(index : Int)
  index = check_index_out_of_bounds(index) do
    return yield index
  end
  unsafe_fetch(index)
end

Neither the [] operator nor the fetch method are language primitives. To find a language primitive, I need to keep dividing the code up into smaller and smaller pieces, until it can’t be divided any further. The same process a chemist would use to break up some material into smaller and smaller molecules until they are left with a set of atoms.

Let’s continue by reading unsafe_fetch:

# Returns the element at the given *index*, without doing any bounds check.
#
# `Indexable` makes sure to invoke this method with *index* in `0...size`,
# so converting negative indices to positive ones is not needed here.
#
# Clients never invoke this method directly. Instead, they access
# elements with `#[](index)` and `#[]?(index)`.
#
# This method should only be directly invoked if you are absolutely
# sure the index is in bounds, to avoid a bounds check for a small boost
# of performance.
abstract def unsafe_fetch(index : Int)

Since Indexable#unsafe_fetch is an abstract method, I need to read how the Array class implements it back in src/array.cr:

@[AlwaysInline]
def unsafe_fetch(index : Int) : T
  @buffer[index]
end

(source: Nick Bonzey via Wikimedia Commons)

So far, I’ve drilled down through 3 levels of Crystal implementation:

But I haven’t found a primitive function yet. Let’s keep digging!

The Crystal Array Class

To learn more, I need to scroll up and read the beginning of the Crystal Array class definition:

# An `Array` is an ordered, integer-indexed collection of objects of type T.
#
# Array indexing starts at 0. A negative index is assumed to be
# relative to the end of the array: -1 indicates the last element,
# -2 is the next to last element, and so on.

etc...

# An `Array` is implemented using an internal buffer of some capacity
# and is reallocated when elements are pushed to it when more capacity
# is needed. This is normally known as a [dynamic array](http://en.wikipedia.org/wiki/Dynamic_array).
#
class Array(T)

etc...

# The buffer where elements start.
  @buffer : Pointer(T)

I’ve deleted some of the comments and code for clarity. You can read the full, original version in src/array.cr.

Now I get a sense of how the unsafe_fetch method above works. Let’s repeat that again:

def unsafe_fetch(index : Int) : T
  @buffer[index]
end

Crystal saves all of the elements in each array into a memory buffer called @buffer. And when I access an element of the array like this:

puts arr[1]

Crystal first checks that the array index (1 in this example) is valid, and then loads the array element I want from the buffer using: @buffer[1].

The Crystal Pointer Class

But how does @buffer[index] actually work? I haven’t learned anything yet! I’m just going around in circles. So far all I’ve been able to find is that Crystal implements Array#[] with a different [] operator, on a different class. What type of object is @buffer? What does it do?

Reading the array class declaration again more carefully, I can see that @buffer is an instance of the Pointer class:

# The buffer where elements start.
@buffer : Pointer(T)

Let’s read how Crystal implements Pointer#[] in src/pointer.cr:

# Gets the value pointed at this pointer's address plus `offset * sizeof(T)`.
#
# ```
# ptr = Pointer.malloc(4) { |i| i + 10 }
# ptr[0] # => 10
# ptr[1] # => 11
# ptr[2] # => 12
# ptr[3] # => 13
# ```
def [](offset)
  (self + offset).value
end

Reading this, I discovered the Crystal team has written a class that represents pointers! Just like using a pointer in C, Crystal code can refer to and access any memory location directly. Because the Pointer class is part of the language, Crystal allows us to implement our own data structures and algorithms in a very detailed manner, allocating and accessing memory just like the Crystal team has while implementing arrays, hashes and other classes.

Now I’ve dug down through 4 levels of Crystal function calls, but I still haven’t found a language primitive yet.

A Crystal Language Primitive

We still haven’t discovered how arrays actually work - how pointers actually work. That is, reading this line of code above:

(self + offset).value

…I understand the meaning and intent of pointer arithmetic, and how it’s used by Crystal arrays, but I still don’t see how or where Crystal actually obtains the array element referenced by a given pointer.

Digging deeper, let’s read the Pointer#value method to find out - this method’s implementation should tell me exactly how Crystal obtains the value:

# Gets the value pointed by this pointer.
#
# ```
# ptr = Pointer(Int32).malloc(4)
# ptr.value = 42
# ptr.value # => 42
# ```
@[Primitive(:pointer_get)]
def value : T
end

As you can see, this is a language primitive - it says “primitive” right there above the method definition!

Returning to Wikipedia’s definition of a language primitive, this is an atomic element of an expression. The Crystal compiler knows not to try to compile this code but to assume this behavior is part of the language. In fact, there is no implementation for Pointer#value here at all: the method is empty!

def value : T
end

The empty value method above doesn’t tell us where the value actually comes from, or how Crystal obtains it. To learn that, we need to step down one level of abstraction - we need to use a lower level language, not Crystal.

Retrieving an Array Element In x86 Assembly Language

What lower level language should we use? Since the Crystal team used the Low Level Virtual Machine (LLVM) project to implement their compiler, I could look at LLVM’s low level instruction language. But since I’m not familiar with that, or with how the Crystal compiler works, I decided to jump down to the lowest level of abstraction available to me on my Intel Mac: x86 Assembly Language.

Here’s my Crystal program again:

$ cat array_example.cr
arr = [12345, 67890]
puts arr[1]

If I compile the program without running it, and then use the llvm-objdump command, LLVM will give me a version of my code converted into Intel x86 Assembly Language:

$ crystal build array_example.cr
$ llvm-objdump -D array_example > array_example.a

Now by reading the assembly produced by the Crystal compiler and LLVM, I can see how the Pointer#[] and Pointer#value methods actually work:

0000000100089bb0 <_*Pointer(Int32)@Pointer(T)#[]:Int32>:
100089bb0: 50                           pushq %rax
100089bb1: e8 0a 00 00 00               callq 0x100089bc0 <_*Pointer(Int32)@Pointer(T)#+:Pointer(Int32)>
100089bb6: 8b 00                        movl  (%rax), %eax
100089bb8: 59                           popq  %rcx
100089bb9: c3                           retq

0000000100089bc0 <_*Pointer(Int32)@Pointer(T)#+:Pointer(Int32)>:
100089bc0: 48 63 c6                     movslq  %esi, %rax
100089bc3: 48 c1 e0 02                  shlq  $2, %rax
100089bc7: 48 01 c7                     addq  %rax, %rdi
100089bca: 48 89 f8                     movq  %rdi, %rax
100089bcd: c3                           retq

Assembly language is just another programming language like any other, but with a different set of primitives. The primitives in this language are hardware instructions that my laptop’s CPU can understand and execute directly:

I won’t pretend to understand all the details here, but if you’re curious about what this code does - how my compiled Crystal program actually retrieves a value from an array - here are a few highlights you can look for:

If you’d like to learn more about x86 assembly language, I wrote an article a few years ago explaining some of the basics: Learning to Read x86 Assembly Language.

Understand the Primitives of the Language You Are Using

Why did I bother with this exercise? To make sure I deeply understand the programming languages I’m using. Ruby hides much of its implementation in C, so I didn’t learn much looking at the Ruby array primitives in this example. And the primitive functions of assembly language are by definition the instructions my CPU can execute directly. It’s always fun trying to identify and understand machine level instructions!

But Crystal surprised me - I expected to see a set of primitive array functions like we have in Ruby, but I was wrong. Instead, I learned that Crystal supports pointers, just like C or other low level languages do. I discovered that Crystal, unlike Ruby, might be an appropriate choice for low level systems programming tasks. And I was able to learn all of this, along with the array implementation details, because the Crystal team implemented its standard library in the same, target language: Crystal. All I had to do was make an effort to read some code.

Dive into details and find out what the language primitives are in your favorite programming language. You might be surprised and discover that your language is capable of much more than you thought it was.

Generic Types: Adding Math Puzzles To Your Code

2021-11-06T00:00:00Z

In this formula, x is the bound variable, a is
the free variable and e is constant.

Most modern, statically typed languages allow us to use generic types. We write a function once with generic type syntax, and then the compiler can apply the same code over and over again to different actual, concrete types. Hence the name generic.

This is a powerful language feature, but generic code is often confusing and hard to read. For me, generic code resembles something from my high school algebra textbook. I see small math puzzles sprinkled around my computer program. Why do this? Why add math problems to your code? Computer programming is already hard enough; why make it even more complicated?

Generic types allow us to get the best of both words: the safety and performance of static types, with the flexibility and simplicity of a dynamic, typeless language.

But this comes at a steep price: Using generic types force you to write two programs, in a sense. Your normal code for runtime, and a second, parallel type-specific program that runs at compile time. To see what I mean, let’s take an example from the Crystal standard library and explore how the Crystal team used generic type syntax to implement their array class.

Array#uniq in Crystal

Last time I looked at the Crystal standard library, specifically at how Crystal removes duplicate elements from an array in Array#uniq. I discussed a couple of optimizations the Crystal team used to implement uniq for small or empty arrays.

But what about the general case? How does Crystal remove duplicate elements from large arrays? If I remove the small array optimizations, the Crystal implementation of Array#uniq reads like this:

class Array(T)

  def uniq
    # Convert the Array into a Hash and then ask for its values
    to_lookup_hash.values
  end

  protected def to_lookup_hash
    to_lookup_hash { |elem| elem }
  end

  protected def to_lookup_hash(& : T -> U) forall U
    each_with_object(Hash(U, T).new) do |o, h|
      key = yield o
      unless h.has_key?(key)
        h[key] = o
      end
    end
  end

end

This is almost easy to read. Admittedly, I’m a Ruby developer, so the Ruby-like syntax makes perfect sense to me. However, most developers will be able to figure this out without much effort.

Crystal identifies the unique elements of the array by converting it into a “lookup hash:”

As you know, hash keys are unique. By converting the array into a hash, Crystal has quickly identified the unique elements of that array.

Converting An Array To A Hash At Runtime

But if you read carefully, you’ll see that Crystal converts the array to a hash twice: once at compile time and then later again at runtime. Let’s look at the second, runtime program first, working our way from the inside out.

First, the unless clause inside the loop checks whether the hash already contains a given element. If the element isn’t already in the hash, Crystal adds it:

unless h.has_key?(key)
  h[key] = o
end

This is the crux of the unique algorithm. Crystal won’t insert a given key value twice. (Although the unless clause is technically unnecessary; saving a repeated value would be harmless, overwriting the previous copy in the hash.)

Looking up one line, we can see the to_lookup_hash function accepts a block, and calls it to calculate the a key value for each array element:

key = yield o
unless h.has_key?(key)
  h[key] = o
end

And reading farther up, we can see another definition of to_lookup_hash passes in such a block:

protected def to_lookup_hash
  to_lookup_hash { |elem| elem }
end

Since the block { |elem| elem } just returns whatever was passed into it, the keys and values of the lookup hash will be the same:

This block adds a bit of flexibility to the code. The Crystal team might want to reuse this function someday with a different block and set of keys.

Finally, let’s look at how Crystal iterates over the array:

each_with_object(Hash(U, T).new) do |o, h|
  key = yield o
  unless h.has_key?(key)
    h[key] = o
  end
end

Crystal calls each_with_object on the array and provides a single argument: Hash(U, T).new. Here’s our first example of generic type syntax. I’ll come back to that in a moment. For now, I can guess that Hash(U, T).new creates a new, empty hash.

Next, each_with_object loops over the receiver (the array), and calls the block do |o, h| … end for each element. It sets o to each element’s value as it iterates, and h to the hash created with Hash(U, T).new. As we saw above, the block inserts each value o into the hash h, skipping duplicates.

Finally, after the iteration completes, Crystal returns the values from the new hash, a new array containing only the unique elements from the original array:`

to_lookup_hash.values

Converting An Array To A Hash At Compile Time

But there’s more to this program than meets the eye. Crystal actually runs part of this code, the generic type syntax, earlier at compile time. And, curiously, that code also converts the array into a hash but in a different way. When the Crystal team wrote Array#uniq, they had to write two programs, not one!

What exactly do I mean by “converting an array to a hash at compile time?” How and why does this happen? And what’s the second program here?

The answer has to do with the Hash(U, T).new expression we read above. Crystal needs to convert the type Array(T) into the type Hash(U, T). Let’s step through the second, type-level mirror program to find out how this works.

You can imagine the Crystal compiler processing the generic type code like this:

The first line is actually the most important:

class Array(T)

This line means the Crystal team is not implementing a simple array of elements. Instead, they are implementing an array that must contain elements of the same type. And here on this line they name that type in a generic way: the type variable T.

Specifying an array element type provides two important benefits: First, it is a nice safety net for us, the developers using Crystal arrays. Crystal’s compiler will prevent us from accidentally inserting elements from a different or unexpected type into the array. And the best part is that Crystal will tell us about our mistake at compile time, before our code ever runs and does any harm with real data. It’s annoying and difficult to write a second compile-time program using types, but the compiler might - and probably will - find some of our mistakes and tell us before the program even runs.

Second, because Crystal knows that all of the elements of the array have the same type, it can emit more efficient code that takes advantage of this knowledge. The machine language code the compiler produces can save and copy array elements faster because it knows how much memory each element occupies.

And by using generic type syntax to write Array#uniq, the Crystal team gives us these benefits regardless of what kind of elements we add to our arrays. The Crystal compiler automatically maps the type we happen to choose in our code to the variable T.

Next, take a look at the to_lookup_hash function declaration:

protected def to_lookup_hash(& : T -> U) forall U

What in the world does this mean? What is forall U referring to?

The first thing to note here is Crystal’s block parameter syntax: & : T -> U. Crystal has borrowed the & character from Ruby to indicate the following value is a block or closure, not a simple value. But in Crystal, the block parameters and the block’s return value all must have types. And here in this code those types are generic types: T and U. The arrow syntax tells us that the block takes a single parameter of type T, and returns a single value of type U.

But what do T and U mean? Where are they defined?

This is our math puzzle for the day. Just like in a limit, integral or infinite series from Calculus, this formula contains bound and free variables:

& : T -> U forall U

Since the enclosing class statement above declared the class to be Array(T), Crystal binds the T type variable here to be the same type as above. In order words, the type of values passed into this block must be the same as the type of the elements in the array.

But what about U? What type is that?

The forall U clause declares the U type to be a free variable. That means that U, unlike the type T, is not bound to any known type value. forall tells the Crystal compiler that the following code should apply equally well to any type U, “for all” possible types U.

The Crystal compiler solves this math puzzle using the yield statement we saw above:

key = yield o

Here Crystal knows the value o has a type of T. How? Because Crystal knows that all of the elements of the array have a type T, (this is the Array(T) class) and Crystal knows the variable o was set earlier to an array element by each_with_object.

Next, the Crystal compiler can determine that U == T, that both types are the same. How? When Crystal compiles the block’s code above:

to_lookup_hash { |elem| elem }

…Crystal notices that the return value of the block is the same as the value passed into the block, that elem == elem. Then, the Crystal compiler maps this return value to the block declaration: & : T -> U. Because Crystal knows elem == elem in the block code, it deduces that the types of these values are also the same, that U == T.

Finally, let’s return to the line above that iterates over the array:

each_with_object(Hash(U, T).new) do |o, h|

Now the Crystal compiler can use the knowledge that types U == T when it creates the lookup hash. In Crystal when you create a hash, just as when you create an array, you have to provide a type parameter for all the values. And for hashes you also need to provide a type for the keys. Hash(U, T).new means: Create a new hash which has keys of type U and values of type T.

Armed with the knowledge that the keys of the lookup hash all have type U, and that U == T, the Crystal compiler can emit the correct, optimized code for finding and inserting hash values when it produces machine language instructions for this passage:

key = yield o
unless h.has_key?(key)
  h[key] = o
end

Crystal knows that both o and key have the same type T, which allows the has_key? and []= methods to run quickly and correctly.

Are Generic Types Worth It?

It’s a good thing the Crystal compiler is good at solving math puzzles! Crystal, like many other modern languages (Haskell, Swift, Rust, etc.) is able to determine the actual, concrete types for variables like T and U, and for all values in your code, using type inference. The Crystal compiler can deduce what the type of each variable is based on the usage of that variable and the context of the surrounding code.

But the problem is that I, a user of the Crystal language, have to be good at math puzzles also. As we’ve just seen, in order to write code using Crystal or any language with a modern type system, I have to write my code twice: once to solve the problem I actually want to solve, and a second time to prove to the compiler that my code is consistent and mathematically correct at a type level.

Are the added performance and added safety worth it? That depends entirely on what code you are writing, how fast it needs to run, how many times and for how long that code will be used - and most importantly, how much time you have to solve math problems.

To Learn a New Language, Read Its Standard Library

2021-10-23T00:00:00Z

If I was learning to read English as a foreign language,
I would need something simple to get started.
(from The Remarkable Story of Chicken Little, 1840)

The best way to learn a new programming language, just like a human language, is from example. To learn how to write code you first need to read someone else’s code. But who is the best person to learn from? Which code should we read? Where should we look to find it?

This year in my spare time I was learning about Crystal. I had played around with some simple scripts, but I wanted to learn more. Then I stumbled on to Crystal’s standard library. I was relieved to see that Crystal’s core classes are implemented using Crystal itself!

Crystal’s standard library is clear, simple, concise and well documented. Reading Crystal’s internal implementation of Array or Hash is like reading a fairy tale in a children’s book. Anyone can understand it, even people without a Ph.D. in Computer Science or systems programming experience.

Update: There was a long discussion on Hacker News about whether reading the standard library really is a good idea for various different languages.

At First Glance, Crystal Is Ruby

At first glance, when I read Crystal’s Array implementation, I thought I was reading a Ruby program:

class Array(T)
  include Indexable::Mutable(T)
  include Comparable(Array)

  # Size of an Array that we consider small to do linear scans or other optimizations.
  private SMALL_ARRAY_SIZE = 16

  # The size of this array.
  @size : Int32

  # The capacity of `@buffer`.
  # Note that, because `@buffer` moves on shift, the actual
  # capacity (the allocated memory) starts at `@buffer - @offset_to_buffer`.
  # The actual capacity is also given by the `remaining_capacity` internal method.
  @capacity : Int32

  # Offset to the buffer that was originally allocated, and which needs to
  # be reallocated on resize. On shift this value gets increased, together with
  # `@buffer`. To reach the root buffer you have to do `@buffer - @offset_to_buffer`,
  # and this is also provided by the `root_buffer` internal method.
  @offset_to_buffer : Int32 = 0

  # The buffer where elements start.
  @buffer : Pointer(T)

There are lots of familiar keywords, like class, include and private. I also see Ruby’s @ character indicating an instance variable. This code is about 100x easier to read vs. Ruby’s own C implementation of Array.

Along with the familiar Ruby-like syntax, notice the helpful comments. Even though I’ve just started reading I can already make an educated guess at how Crystal arrays function internally. I can see there’s a pointer to memory which holds the array elements, and that the code keeps track of the capacity of this memory along with the actual size of the array. Finally, reading the comment for offset_to_buffer I can imagine there are some optimizations related to adding and removing elements. The comment is both helpful and intriguing.

But I’m not reading Ruby code. There are important differences here: generic type syntax and most importantly each of the instance variables is declared with a static type known at compile time. How do I use static types in Crystal? What types are available? What about the generic type parameter T? Should I use that in my own Crystal code? What other syntax differences vs. Ruby are there?

The best way to learn how to write Crystal code is simply to scroll down and read one of the Array methods.

Array#uniq

Here’s how Crystal finds the unique elements of an array:

def uniq
  if size <= 1
    return dup
  end

  # Heuristic: for a small array it's faster to do a linear scan
  # than creating a Hash to find out duplicates.
  if size <= SMALL_ARRAY_SIZE
    ary = Array(T).new
    each do |elem|
      ary << elem unless ary.includes?(elem)
    end
    return ary
  end

  # Convert the Array into a Hash and then ask for its values
  to_lookup_hash.values
end

The first three lines handle the trivial case of when an array is empty or contains only one element:

if size <= 1
  return dup
end

Obviously in this case, there are no duplicate elements and Array#uniq should simply return the original array. One important detail: Crystal uses dup to return a copy of the array. This reminds me that in Ruby uniq returns a copy of the receiver, while uniq! mutates the receiver. My guess is that Crystal implements Array methods in the same way…

The second passage is an optimization:

# Heuristic: for a small array it's faster to do a linear scan
# than creating a Hash to find out duplicates.
if size <= SMALL_ARRAY_SIZE
  ary = Array(T).new
  each do |elem|
    ary << elem unless ary.includes?(elem)
  end
  return ary
end

For small arrays (16 or fewer elements) Crystal iterates over them and removes duplicates using a simple algorithm. I’ll take a look at how that works in a moment.

The final line of code handles arrays with 17 or more elements:

# Convert the Array into a Hash and then ask for its values
to_lookup_hash.values

As you might guess, Crystal removes duplicate values from larger arrays using a hash. I'll dive into the details about how this works in my next post.

Arrays With 16 Or Fewer Elements

But first, let’s take a closer look at case #2 from above, when the array contains 16 or fewer elements. First, Crystal creates a new, empty array called ary:

ary = Array(T).new

Note the generic type syntax Array(T).new. This tells the Crystal compiler that the new array, what will become the return value from Array#uniq, will only contain elements of the same type as the original array.

Ruby developers will find the rest of this code easy to follow…

each do |elem|
  ary << elem unless ary.includes?(elem)
end

Crystal calls each to iterate over all the elements in the receiver, the array we are calling uniq on. Then using <<, Crystal appends each of the original array’s elements to the new array, unless the new array already contains a given element.

Like Ruby, Crystal implements the includes? method inside the Enumerable module. Crystal arrays are enumerable because of the include Indexable::Mutable(T) statement we read above. (Indexable::Mutable includes Indexable which includes Enumerable). You can find Crystal’s implementation of includes? (not include? as in Ruby) in enumerable.cr:

def includes?(obj) : Bool
  any? { |e| e == obj }
end

Here the any? method calls the given block once for each element in the array, and returns true if the block returns true for any of the elements. In other words, this code searches the array in a linear fashion, one element at a time. Crystal’s development team has decided that it’s faster to filter out repeated elements from small arrays by repeatedly searching the array using linear scans. Since there are never more than 16 elements, those scans won’t take too much time.

Simple and Concise

You might be thinking: This is an incredibly simple algorithm; anyone could have written this code! Why bother writing a blog post about this?

That’s exactly my point: This is simple and concise code. I could have written it - you could have also. There’s nothing superfluous, not an extra word here. Just enough code to get the job done. And there’s no noise… no macros, no odd C memory tricks, no weird bitwise mask operations. This is the kind of code I need to read now when I’m learning how to use Crystal. As a side benefit, I also get to learn how Crystal works internally.

But what happens for longer arrays, with 100s or 1000s of elements? How does Crystal remove duplicates from longer arrays efficiently? I'll take a look at how that works in my next post.

Downloading 100,000 Files Using Async Rust

2020-01-20T00:00:00Z

Rust's new async/await feature makes it
easy to stop and start asynchronous tasks
(from: Wikimedia Commons)

Imagine if you had a text file containing thousands of URLs:

$ cat urls.txt
https://example.com/1.html
https://example.com/2.html
https://example.com/3.html

etc...

https://example.com/99999.html
https://example.com/100000.html

…and you needed to download all of those HTML pages efficiently. How would you do it? Maybe a shell script using xargs and curl? Maybe a simple Golang program? Go’s powerful concurrency features would work well for this.

Instead, I decided to try to use Rust. I’ve read a lot about safe concurrency in Rust, but I’ve never tried it. I also wanted to learn what Rust’s new “async/await” feature was all about. This seemed like the perfect task for asynchronous Rust code.

TL/DR: Here’s the code. The rest of this post will explain how it works.

Getting Started With Reqwest

There are many different Rust HTTP clients to choose from, and apparently some controversy about which works best. Because I’m a Rust newbie, I decided simply to pick the most popular: reqwest. Request is a high level, easy to use HTTP client, written by Sean McArthur. He just updated it to work with Tokio, Rust’s new async/await engine, so this is the perfect time to try using it. Here’s the example from the readme:

use std::collections::HashMap;

#[tokio::main]
async fn main() -> Result<(), Box<dyn std::error::Error>> {
    let resp = reqwest::get("https://httpbin.org/ip")
        .await?
        .json::<HashMap<String, String>>()
        .await?;
    println!("{:#?}", resp);
    Ok(())
}

This version downloads some JSON and parses it. Notice the new async and await keywords. The main function is async - this means that the function becomes part of a large state machine run by Tokio. When you mark a function asynchronous, you can then call await inside it, which will pause that function temporarily, allowing other asynchronous functions to run on the same thread.

I decided to modify this to print out the number of bytes downloaded instead; you could easily change it to save the data to a file or do whatever you want.

let path = "https://httpbin.org/ip";
match reqwest::get(path).await {
    Ok(resp) => {
        match resp.text().await {
            Ok(text) => {
                println!("RESPONSE: {} bytes from {}", text.len(), path);
            }
            Err(_) => println!("ERROR reading {}", path),
        }
    }
    Err(_) => println!("ERROR downloading {}", path),
}
Ok(())

This is a two step process:

First I call get(path) to send the HTTP GET request. Then I use await to wait for the request to finish and return a result.
Second, if the request was successful, I call resp.text() to get the contents of the response body. And I wait again while that is loaded.

I handle the errors explicitly and always return a unit result Ok(()) because that makes the code below simpler when I start downloading more than one page concurrently.

Visually, I can draw the get and text calls like this:

First I call get and wait, then I call text and wait.

But what is asynchronous about this? This reads like normal, single threaded code. I do one thing, then I do another.

Sending 3 Concurrent Requests

The magic happens when I have more than one request I want to make in parallel. Let’s use three hard coded path strings:

let paths = vec![
    "https://example.com/1.html".to_string(),
    "https://example.com/2.html".to_string(),
    "https://example.com/3.html".to_string(),
];

To download the 3 HTML files in parallel, I spawn three Tokio “tasks” and wait for them all to complete. (This requires adding the futures crate to Cargo.toml, which implements join_all.)

// Iterate over the paths.
let mut tasks: Vec<JoinHandle<Result<(), ()>>>= vec![];
for path in paths {

    // Copy each path into a new string
    // that can be consumed/captured by the task closure
    let path = path.clone();

    // Create a Tokio task for each path
    tasks.push(tokio::spawn(async move {
        match reqwest::get(&path).await {
            Ok(resp) => {
                match resp.text().await {
                    Ok(text) => {
                        println!("RESPONSE: {} bytes from {}", text.len(), path);
                    }
                    Err(_) => println!("ERROR reading {}", path),
                }
            }
            Err(_) => println!("ERROR downloading {}", path),
        }
        Ok(())
    }));
}

// Wait for them all to finish
println!("Started {} tasks. Waiting...", tasks.len());
join_all(tasks).await;

Each Tokio task is a closure passed to the tokio::spawn function, marked async move. I create a copy of each path, using path.clone(), so the closure has its own copy of the path string with its own lifetime.

The complex type annotation on the tasks array indicates what each call to spawn returns: a JoinHandle enclosing a Result. To keep things simple, I handle all errors in the closure and just return Ok(()). This means each JoinHandle contains a trivial result: Result<(), ()>. I could have written the closure to return some value and/or some error value instead.

After the loop is finished and all three tasks have been spawned, I call join_all(tasks).await to wait for them all to finish.

Asynchronous vs Multithreaded

(from: Wikimedia Commons)

At first glance, it looks like this code is spawning three different threads. I even call a spawn function. A multithreaded download might look like this:

We have 3 paths, so we have 3 threads. Each thread calls get and waits, and then calls text and waits.

However, Rust’s Tokio engine doesn’t work that way. Instead of launching an entirely new thread for each task, it runs all three tasks on the same thread.

Update: Wesley Moore pointed out on Twitter that: "Tokio multiplexes m tasks into a pool of n threads so it’s able to use all available cores. (M:N threading)." It looks like Tokio supports both a Basic (single threaded) and Threaded (thread pool) Scheduler; see the docs for more information.

I imagine three tasks running on one thread like this:

Each time I call await, Rust stops one task and starts another using the same thread. In fact, depending on how long it takes for each task to complete, they might be run in a different order:

There’s no way to predict ahead of time what order the tasks will run it. That’s why I needed to copy each path string above; each task needs it own copy of the string with its own independent lifetime because it might be run at any time.

The only guarantee I have is that the join_all call at the bottom will block until all of the tasks have finished; that is, until all of the futures I pushed onto the tasks array have completed.

Sending 100,000 Concurrent Requests

I can scale this up to 100,000 requests by reading the URLs in from a file instead:

fn read_lines(path: &str) -> Result<Vec<String>, Box<dyn Error>> {
    let file = File::open(path)?;
    let reader = BufReader::new(file);
    Ok(
        reader.lines().filter_map(Result::ok).collect()
    )
}

#[tokio::main]
async fn main() -> Result<(), Box<dyn Error>> {

	let paths: Vec<String> = read_lines("urls.txt")?;

etc...

When I tried this out for the first time I was excited: How long would it take to download 100,000 HTML pages simultaneously like this? Would it be 100,000x faster than downloading one file? I typed cargo run --release to build my code in release mode and get the best possible performance out of Rust. Asynchronous code, zero cost abstractions, no garbage collector, this was going to be great!

Of course, it didn’t work.

What happened? The problem is the web server can't handle so many concurrent network connections. Using my thread/task diagram, launching all 100,000 tasks might look like this:

I spawn 100,000 tasks all on to the same thread, and Tokio starts executing them all. Each time my code above calls get(&path).await, Tokio pauses that task and starts another, which calls get(&path).await again, opening yet another HTTP request. My laptop quickly runs out of network resources and these tasks start to fail.

Sending a Buffered, Concurrent Stream of 100,000 Requests

Instead, I need to limit the number of concurrent Tokio tasks - the number of concurrent HTTP requests. I need the diagram to look something like this:

After the first 8 tasks are started, the first 8 blue boxes on the left, Tokio waits for at least one of them to complete before starting a 9th task. I indicate this with the “max concurrency” arrow.

Once one of the first 8 calls to reqwest::get completes, Tokio is free to run a 9th task. The first "pop from buffer" arrow. And once that 9th task or any other task completes, Tokio starts a 10th task, etc., in this manner processing all 100,000 tasks 8 at a time.

To achieve this, I can use StreamExt trait’s buffer_unordered function:

let fetches = futures::stream::iter(
    paths.into_iter().map(|path| {
        async move {
            match reqwest::get(&path).await {
                Ok(resp) => {
                    match resp.text().await {
                        Ok(text) => {
                            println!("RESPONSE: {} bytes from {}", text.len(), path);
                        }
                        Err(_) => println!("ERROR reading {}", path),
                    }
                }
                Err(_) => println!("ERROR downloading {}", path),
            }
        }
})
).buffer_unordered(8).collect::<Vec<()>>();
println!("Waiting...");
fetches.await;

First I create an iterator which maps all of the paths to my closures, and passes them to futures::stream::iter. This will create a list of futures, each one executing my closure.

At the bottom I call buffer_unordered and pass in 8. The code in buffer_unordered will execute up to 8 futures from the stream concurrently, and then start to buffer the remaining futures. As each task completes, each HTTP request in my example, buffer_unordered will pull another task out of its buffer and execute it.

This code will slowly but steadily iterate over the 100,000 URLs, downloading them in parallel. Experimenting with this, it doesn’t seem to matter very much exactly what level of concurrency I pick. I found the best performance when I picked a concurrency of 50. Using 50 concurrent Tokio tasks, it took about 30 minutes to download all one hundred thousand HTML files.

However, none of that matters. I’m not measuring the performance of Rust, Tokio or Reqwest. These numbers have more to do with the web server and network connection I’m using. The real performance here was my own developer performance: With just a few lines of code I was able to write an asynchronous I/O program that can scale as much as I would like. The async and await keywords make this code easy to write and easy to read.

Using Result Combinator Functions in Rust

2019-11-19T00:00:00Z

Rust’s Result type can help you control your program’s
flow by checking for errors in a succinct, elegant way

Using Rust for the first time, error handling was my biggest stumbling block. Was this value a Result<T, E> or just a T? And the right T? The right E? I couldn’t just write the code I wanted to write. It felt confusing and overly elaborate.

But after a while, I started to get a feel for the basics of using Result. I discovered that the combinator methods Result provides, like map, or_else and ok, made error handling fun. Well, maybe that's a bit of an overstatement. They made using Result a bit easier, at least.

So far my favorite Result combinator method is and_then. Using and_then is actually fun! For example, I wrote this Rust code to generate the static HTML pages for this blog site:

let count = all_posts.len();
all_posts.sort_by_key(|p| Reverse(p.date));
let params = CompileParams {all_posts: all_posts, output_path: output_path, draft: draft};
Ok(params).and_then(compile_posts)
          .and_then(compile_home_page)
          .and_then(compile_rss_feed)
          .map(|_output| count)

Ignoring the details about sorting and counting, my code:

First creates a struct holding input parameters, and wraps it using Ok(params)
And then tries to compile all the posts in my blog, passing in the input parameters
And then if this was successful, it tries to compile the home page (index.html)
And then if this was successful, it tries to compile the RSS feed (index.xml)

If there was an error at any time in this process, it short circuits and stops. Here’s a flowchart that illustrates this control flow:

The happy path is from top to bottom, along the left side. If any of the compile methods fail, and_then short circuits the happy path and jumps to the end.

Matching Result Types

To chain and_then methods together like this, I used the same input and output types for each of the compile methods:

fn compile_posts(params: CompileParams) -> Result<CompileParams, InvalidPostError>

fn compile_home_page(params: CompileParams) -> Result<CompileParams, InvalidPostError>

fn compile_rss_feed(params: CompileParams) -> Result<CompileParams, InvalidPostError>

Each method expects a CompileParams struct, and returns one wrapped in Result. Rust unwraps the CompileParams from one call and passes it to the next.

I use InvalidPostError throughout my code to provide a consistent way to return errors. This was a bit of a challenge at first, until I realized it was easy to cast other types of errors into InvalidPostError like this:

impl From<std::io::Error> for InvalidPostError {
    fn from(e: std::io::Error) -> InvalidPostError {
        let message = format!("{}", e);
        InvalidPostError::new(&message)
    }
}

Now the Rust compiler knows how to map a std::io::Error into an InvalidPostError.

Error Handling the Old Fashioned Way

Here’s the code I didn’t have to write: (This is Ruby; substitute your favorite PL that doesn't support monadic error handling.)

if compile_posts(params)
  if compile_home_page(params)
    if compile_rss_feed(params)
      puts "Success!"
    else
      puts "Error compiling RSS Feed"
    end
  else
    puts "Error compiling home page"
  end
else
  puts "Error compiling a blog post"
end

I didn’t have to write a series of if/else blocks. This would have been tedious to write and tedious to read. And I probably would have forgotten (or have been too lazy) to check one of the return values.

And I didn’t have to write this code either:

def compile_posts(params)
  raise InvalidPostError.new("Failed compiling the posts")
end

def compile_home_page(params)
  raise InvalidPostError.new("Failed compiling the home page")
end

def compile_rss_feed(params)
  raise InvalidPostError.new("Failed compiling the RSS feed")
end

begin
  compile_posts(params)
  compile_home_page(params)
  compile_rss_feed(params)
  puts "Success"
rescue InvalidPostError => e
  puts e.message
end

Once again this is fragile: I might raise the wrong exception type or not raise one at all. Or I might rescue the wrong type. Worse, there’s no indication at the call site what might happen.

To be honest, I probably won’t bother handling errors at all for a simple Ruby script like this. If an exception happens someday while building my blog site, then I’ll deal with it then. I’d probably just write this code:

compile_posts(params)
compile_home_page(params)
compile_rss_feed(params)
puts "Success"

Rust Error Handling: Easy To Read, Hard To Write

Combining results together using and_then and other Result functions enables me to write error checking code in a natural, succinct way:

Ok(params).and_then(compile_posts)
          .and_then(compile_home_page)
          .and_then(compile_rss_feed)

This is just as simple to read as the Ruby version above that doesn’t check for any errors. While it’s harder to write, having the Rust compiler check my thought process as I piece together different code paths is a huge help. Learning to use and get along with the Rust compiler is worth it: You end up with code that is both readable and correct.

How Rust Makes Error Handling Part of the Language

2019-10-03T00:00:00Z

In Spanish these are all “dedos,” while in English
we can distinguish between fingers and toes.

Learning a foreign language can be an incredible experience, not only because you can talk to new people, visit new countries, read new books, etc. When you learn the words someone from a different culture uses, you start to see things from their perspective. You understand the way they think a bit more.

The same is true for programming languages. Learning the syntax, keywords and patterns of a new programming language enables you to think about problems from a different perspective. You learn to solve problems in a different way.

I’ve been studying Rust recently, a new programming language for me. As a Ruby developer, I was curious to learn how Rust developers approach solving problems. What do Rust programs look like? What new words would I learn?

Why Rust Was Difficult For Me

I knew it would be a challenge to learn Rust. I had heard horror stories about how difficult the Rust compiler can be to use, or about how confusing the ownership memory model and the borrow checker can be. And I was right: Rust is a very difficult language to learn. But not because of move semantics or memory management.

For me, the most challenging syntax in Rust had to do with simple error handling. Let’s take an example: opening and reading a text file. In Ruby, this is a one-liner and error handling is completely optional:

string = File.read("foo.txt")

In Ruby, File.read returns a simple string. Will this ever return an error? Who knows. Maybe Ruby will raise an exception, maybe not. I don’t have to worry about that at the call site when I’m writing the code. I can focus on the happy path, but I end up with a program that can’t handle errors.

Golang, at least, returns an error value explicitly when I try to read a file:

b, err := ioutil.ReadFile("foo.txt")
if err != nil {
    fmt.Print(err)
} else {
    str := string(b)
}

Here the Golang ioutil.ReadFile function returns two values: the string I want and also an error value. The Go compiler forces me to think about errors that might occur, at least for a moment. But error handling is still optional. I can simply choose to ignore the err value entirely. Most C programs work in a similar fashion, returning an error code in some manner. And if I do choose to handle the error, I end up with verbose, messy code that checks for error codes over and over again.

In Rust error handling in mandatory. Let’s try to rewrite the same example using Rust:

let mut file = File::open("foo.txt");
let mut contents = String::new();
file.read_to_string(&mut contents);

Right away I run into trouble when I try to compile this:

error[E0599]: no method named `read_to_string` found for type
`std::result::Result<std::fs::File, std::io::Error>` in the current scope

What? What is the Rust compiler talking about? I can see there’s a read_to_string method on the File struct right in the documentation! (Actually the method is on the Read trait which File implements.) The problem is the File::open function doesn’t return a file at all. It returns a value of type io::Result<File>:

pub fn open<P: AsRef<Path>>(path: P) -> io::Result<File>

How do I use this? What does io::Result<File> even mean? When I try to write Rust code the way I write Ruby or Go code, I get cryptic errors and it doesn’t work.

The problem is I’m trying to speak Rust the same way I speak in Ruby. Rust is a foreign language; I need to learn some vocabulary before I can try to talk to someone. This is why Rust is difficult to learn. It’s a foreign language that uses many words completely unfamiliar to most developers.

Types Are the Vocabulary of Programming Languages

My wife is Spanish, and lucky for me she’s had the patience and the endurance to teach me and our kids Spanish over the years. As a native English speaker, it always seemed curious and amusing to me that Spanish has only one word for fingers and toes, dedos. Don’t people in Spain or Latin America ever need to talk about only fingers and not toes? Or vice-versa? And in Spain I invariably end up saying silly things like dedos altos (“upper fingers”), or dedos bajos (“lower fingers”). I always worry about which digits I’m talking about. Somehow, though, the Spanish never have any trouble with this; where the dedos are located always seems obvious to them from the context.

But I wonder: Do Spanish speakers have trouble learning English when it comes to fingers vs. toes? Do they ever say finger when they mean toe? The problem is not just learning a new word. You have to learn the meaning behind the word. English has a concept, a distinction, that Spanish doesn’t.

Back to computer programming, the “words” we use in programming languages aren’t only syntax tokens like if, else, let, etc. They are the values that we pass around in our programs. And those values have types, even for loosely, dynamically typed languages like Ruby.

Aside from whatever formal definition Computer Science has for types, I simply think of a value’s type as it’s meaning or purpose. To understand what role a value plays in your program, you need to understand the concept behind its type. Just like the words finger and toe represent certain anatomical concepts in English, types like Result<T, E> or Option<T> represent programming concepts in Rust - concepts that foreigners need to learn for the first time.

Language shapes the way we think, and determines what we can think about.
-- Benjamin Lee Whorf

In fact, some linguists take this to the extreme: That a language’s words determine what people in that community are able to think and talk about, what concepts they can understand. (However, most modern linguists, according to Wikipedia, don’t believe this is actually true.)

Because Rust includes the Result type, Rust programmers are empowered to talk about error handling in a very natural way. It’s part of their daily vocabulary. Of course, native Spanish speakers, I’m guessing, have no trouble understanding the distinction between fingers and toes. But I certainly have trouble understanding the concept behind Result in Rust.

If Rust is Spanish, then Haskell is Latin

So what does Result<T, E> mean? What is a value of type Result<T, E>?

Just as human language borrow words from other languages — many Spanish words are taken from Latin or Arabic while English borrowed many words from French and German — programming languages borrow words and concepts from other, older programming languages.

Rust borrowed the concept behind the Result<T, E> type from Haskell, a strongly typed functional programming language. Haskell includes a type called Either:

data Either a b = Left a | Right b

This syntax seems bizarre at first glance but in fact it’s simple. Haskell makes it easy to create new types by combining other types together. This line of code means the Either type is a combination of two other types: a and b. Drawing that type equation, this is how I visualize Haskell Either values:

A single Either value can only encapsulate either a value of type a or a value of type b:

If the Either value is Left, then it contains an inner value of type a. This is written: Left a
If the Either value is Right, then it contains an inner value of type b. This is written: Right b

The Either type is also “monad,” because Haskell provides certain functions that create and operate on Either values. I won’t cover this concept here today, but when I have time I'll discuss monads and how they can be applied to error handling in a future post.

In Haskell, the Either type is completely general, and you can use it to represent any programming concept you would like. Rust uses the concept behind Either for a specific purpose: to implement error handling. If Haskell is Latin, then Rust is Spanish, a younger language that borrows some of the older languages’s vocabulary and grammar.

Result<T, E> in Rust

In Rust, the Result type encapsulates two other types like Either. A single Result value has either one of those types or the other:

Instead of Left a and Right b like in Haskell, Rust uses the words Ok(T) and Err(E):

If the Result value is Ok, then it contains an inner value of type T. This is written: Ok(T). Ok(T) means some operation was successful, and the result of the operation is a value of type T.
If the Either value is Err, then it contains an inner value of type E. This is written: Err(E) Similarly, this means the operation was a failure, and the result of the operation is an error of type E.

Back to my open file example, the proper way to open a file and read it using Rust is to check the Result values returned by the Rust standard library functions:

fn main() {
    let file = File::open("foo.txt");
    match file {
        Ok(file) => println!("I have a file: {:?}", file),
        Err(e) => println!("There was an error: {}", e)
    }
}

And If I want to actually read in the contents of that file, I would check that return value also:

fn main() {
    let file = File::open("foo.txt");
    match file {
        Ok(mut file) => {
            let mut contents = String::new();
            match file.read_to_string(&mut contents) {
                Ok(_) => println!("The file's contents are: {}", contents),
                Err(e) => println!("There was an error: {}", e)
            }
        }
        Err(e) => println!("There was an error: {}", e)
    }
}

The ? Operator In Rust

That last code snippet is quite a mouthful - error checking with Rust is even more tedious and verbose than it is using Go!

Fortunately, Rust includes an operator that allows Rust programmers to abbreviate all of this logic. By appending the ? character to the call site of a function that returns a Result<T, E> value, Rust automatically generates code that checks the Result<T, E> value, and returns underlying T value if the result is Ok(T):

fn main() {
    let mut file = File::open("foo.txt")?;
    let mut contents = String::new();
    file.read_to_string(&mut contents)?;
}

Here, the use of ? after File::open("foo.txt") tells the Rust compiler to check the return value of File::open for me automatically:

If the return value of File::open is Ok(T), then Rust assigns the inner T value to file. If File::open returns Err(E), then Rust jumps to the end of the main function immediately and returns.

The program above is much more concise and easy to understand. The only problem is that it doesn’t work! When I try to compile this, I get:

error[E0277]: the `?` operator can only be used in a function that returns `Result` or `Option`
(or another type that implements `std::ops::Try`)
 --> src/main.rs:5:20
  |
5 |     let mut file = File::open("foo.txt")?;
  |                    ^^^^^^^^^^^^^^^^^^^^^^ cannot use the `?` operator in
  a function that returns `()`
  |
  = help: the trait `std::ops::Try` is not implemented for `()`
  = note: required by `std::ops::Try::from_error`

Rust Programs Revolve Around Error Handling

As the error message says, the problem here is that the ? operator generates code that will jump to the end of the main function and return the Err(E) value, where E is of type std::io::Error. The problem is that I haven’t declared a return value for main. Therefore the Rust compiler gives me an error:

the `?` operator can only be used in a function that returns `Result` or
`Option` (or another type that implements `std::ops::Try`)

The function containing the use of the ? operator has to return a value of type Result<T, E> with a matching E type in order for this to make sense. I have to extract my File calls into a separate function, like this:

fn read() -> Result<String, std::io::Error> {
    let mut file = File::open("foo.txt")?;
    let mut contents = String::new();
    file.read_to_string(&mut contents)?;
    Ok(contents)
}

fn main() {
    match read() {
        Ok(str) => println!("{}", str),
        Err(e) => println!("{:?}", e)
    }
}

Note the new read() function above returns a value of type Result<String, std::io::Error>. This allows the use of the ? operator to compile properly. For the happy path, if my code is able to find the “foo.txt” file and read it, then read() returns Ok(contents). However, if there’s an error, read() will return Err(e), where e is a value of type std::io::Error. Note open returns the same error type that read does:

This is where Rust shines. It allows for concise and readable error handling that is also thorough and correct. The Rust compiler checks for error handling completeness at compile time, before I ever run my program.

Now that I’ve learned some vocabulary words, now that I can understand how native Rust speakers use the word Result<T, E>, I can have a Rust conversation about error handling. I can begin to think like Rust developers think. I can start to see things from their perspective.

And I begin to realize that Rust programs tend to be designed with error handling in mind. Notice above how I had to extract a separate function that returned a value of type Result<T, E>, just because of the ? operator. The overall structure of my program is determined by error handling just as much as it’s determined by the nature of the task I’m trying to accomplish. Rust programmers think about errors and what might go wrong from the very beginning, from when they start writing code. To be honest, I've often thought about errors and what might go wrong as an afterthought, after I've written and deployed my code.

Using Rust to Build a Blog Site

2019-09-04T00:00:00Z

Rust comes with batteries included
(source: Wikimedia Commons)

After “Hello World,” blog sites are the world’s second most unneeded application. If you want to write a blog, use Medium, Wordpress or just Twitter. The world doesn’t need another blog app.

However, like Hello World, building a static site generator is a great way to get your feet wet in a new programming language. Recently I rewrote the script I use to generate this web site using Rust: I needed to update and fix my script, but really I was looking for an excuse to write Rust. Despite its reputation as a difficult to learn, expert level language, Rust turned out to be a great choice for the simple task of generating a few HTML files, quickly and reliably. Why? Not because of its sophisticated borrow checker or support for safe concurrency.

Rust was a great choice for me because I didn’t have to write most of the code. Rust’s dependency management and build tool, Cargo, allowed me to glue together open source Rust libraries called “crates” which do most of the work. The Rust community’s crate registry, crates.io, has over 29,000 crates available. Downloading, compiling and using them is dead simple. And writing a blog site using Rust turned out to be simple too.

My Cargo.toml File

I needed a few important features to generate this web site. I wanted my script to work like this for each blog post:

For each blog post, My new Rust script had to: parse the markdown source file and convert it to HTML markup, highlight the syntax of my code snippets using <style> tags and CSS, and use a template to insert the HTML for each post into the surrounding web layout/design. Sounds like a lot of work, right?

Wrong. Other Rust developers smarter than me had already implemented all of this. All I had to do was find the crates I needed and add them to my Cargo.toml file:

[dependencies]
maud = "*"
pulldown-cmark = "*"
syntect = "3.0"

Pulldown-cmark is a markdown parser crate, Syntect is a color syntax highlighting crate, and Maud is an HTML template crate. Actually, to be honest I ended up adding a few other crates to get my script to work:

[dependencies]
maud = "\*"
pulldown-cmark = "\*"
regex = "\*"
lazy_static = "\*"
syntect = "3.0"
chrono = "\*"
clap = "\*"
ordinal = "\*"

I’m not sure why, but the Rust standard library is very minimal. Features that are included in other languages, like regular expressions or date/time parsing, are handled by crates (e.g. regex and chrono).

In any case, all I had to do was build my project and Cargo downloaded everything I needed:

$ cargo build --release
    Updating crates.io index
  Downloaded chrono v0.4.7
  Downloaded clap v2.33.0
  Downloaded maud v0.19.0
  Downloaded lazy_static v1.2.0
  Downloaded pulldown-cmark v0.2.0
  Downloaded ordinal v0.2.2
  Downloaded regex v1.1.0
  Downloaded syntect v3.0.2
  Downloaded libc v0.2.44
  Downloaded num-integer v0.1.41
  Downloaded num-traits v0.2.8
  Downloaded time v0.1.42

etc…
   Compiling syntect v3.0.2
   Compiling blogc v0.1.0 (/Users/pat/apps/patshaughnessy.github.io)
    Finished release [optimized] target(s) in 2m 27s

It couldn’t be easier! During the rest of this post, I’ll show you how I used these three crates: Pulldown-cmark, Syntect and Maud.

Pulldown-cmark

Now that my blog app included the Pulldown-mark crate, using it was just a matter of pasting in a few of lines of code from the helpful example on docs.rs:

let parser = Parser::new(&markdown);
let mut html = String::new();
html::push_html(&mut html, parser);

The first line created a Parser struct, passing in a reference to my markdown string. Then I created an empty, mutable target string, called html. Last, I called the push_html function which parsed the markdown source, converted it to HTML and saved it into html. I didn’t have to do any work whatsoever.

In fact, the only real work for me had to do with “header” strings present at the top of each post source file. For example, the 2017-12-15-looking-inside-postgres-at-a-gist-index.markdown file starts with:

title: "Looking Inside Postgres at a GiST Index"
date: 2017/12/15
tag: the Postgres LTREE Extension

etc…

Here the first three lines are metadata values about the post and not part of the post content. So before calling Pulldown-mark, my script parses and removes these header lines:

fn other_lines(lines: &Vec<String>) -> Vec<String> {
  lines.iter().skip_while(|l| is_header(l)).map(|l| l.to_string()).collect()
}

Above the lines parameter is an array of strings, each a single line of text in the markdown source file. (More precisely, it’s a reference to a Vec<String>, not an array.) The code is fairly readable: other_lines creates an iterator over the lines, skips the first few header lines, and then collects the remaining lines into a second array which the function returns.

Here’s the complete html_from_markdown function, which calls other_lines, joins them together into a single large string, and then passes that to Pulldown-mark:

fn html_from_markdown(lines: &Vec<String>) -> Result<String, InvalidPostError> {
  let mut markdown = String::new();
  for line in other_lines(lines) {
    markdown.push_str(&line);
    markdown.push('\n');
  }
  let parser = Parser::new(&markdown);
  let mut html = String::new();
  html::push_html(&mut html, parser);
  Ok(with_delim_removed(with_highlighted_code_snippets(&html)))
}

Syntect

If you read the code above carefully, you’ll notice html_from_markdown calls with_highlighted_code_snippets before returning the HTML for each post. This function performs color syntax highlighting.

The code snippets in each of my blog posts appear inside of <pre>…</pre> tags. And I use a “type” attribute to indicate the programming language of the snippet. For example:

<pre type="ruby">
puts "This is Ruby code I’m writing about…"
</pre>

Like parsing markdown, syntax highlighting is a very complex task: The Syntect crate has to parse the given code snippet, determine the semantic meaning of each keyword in the snippet based on the provided programming language, and then insert the proper color information. Thank goodness I didn’t have to write that code!

But using Syntect was easy:

pub fn highlighted_html_for_language(snippet: &String, attributes: String) -> String {
  lazy_static! {
    static ref SYNTAX_SET: SyntaxSet = SyntaxSet::load_from_folder(syntax_path()).unwrap();
    static ref THEME: Theme = ThemeSet::get_theme(theme_path().as_path()).unwrap();
    static ref RUBY_SYNTAX: &'static SyntaxReference =
      SYNTAX_SET.find_syntax_by_extension("rb").unwrap();
    static ref RUST_SYNTAX: &'static SyntaxReference =
      SYNTAX_SET.find_syntax_by_extension("rs").unwrap();

etc...

  }
  if attributes.contains("ruby") {
    highlighted_html_for_string(&snippet, &SYNTAX_SET, &RUBY_SYNTAX, &THEME)
  } else if attributes.contains("rust") {
    highlighted_html_for_string(&snippet, &SYNTAX_SET, &RUST_SYNTAX, &THEME)

etc...

First I used a lazy_static block to initialize a few constant values. (lazy_static is another crate I didn’t have to write!) Rust executes this block once the first time it’s encountered and then never again. The values are:

SYNTAX_SET: These are the Sublime syntax files describing each programming language I need to colorize. vim is my editor, but I use Sublime for color syntax highlighting :) I just downloaded these files for the languages I needed and checked them into my app.
THEME: These are the Sublime “theme” files, which select the colors to use for each type of code keyword. I found and adapted one of these files. They play the role of a CSS file, but use XML syntax. Weird, but not hard to figure out.
RUBY_SYNTAX, RUST_SYNTAX, etc. The lazy block also looks up the syntax language file for each language.

Later my highlighted_html_for_language function checks which programming language my post displays, and calls syntect::html::highlighted_html_for_string with the proper values:

if attributes.contains("ruby") {
    highlighted_html_for_string(&snippet, &SYNTAX_SET, &RUBY_SYNTAX, &THEME)
  } else if attributes.contains("rust") {
    highlighted_html_for_string(&snippet, &SYNTAX_SET, &RUST_SYNTAX, &THEME)

etc...

attributes is the array of HTML attributes from the <pre> tag surrounding the code snippet in my post source. My app uses regular expressions to find the <pre>…</pre> HTML blocks, parses the attributes and provides them to highlighted_html_for_language.

Maud

Now my script has HTML for each blog post. All I have to do now is save it in a series of HTML files. But first I needed a template engine for Rust, like ERB for Ruby or Mustache for node.js.

This turned out to be one of the most fun parts of this project. I rewrote my HTML markup using Maud @ directives, like this:

@if let Some(ref t) = post.tag {
  div class="header" {
    "More on " (t)
  }
  div class="links" {
    ul {
      @for (link_url, link_title) in recent_links {
        li {
          a href={ "/" (link_url) } {
            (link_title)
          }
        }
      }
    }
  }
}

Maud doesn’t parse the layout code at runtime, like ERB does in Ruby. Instead, the @if and @for directives above are macros. In fact, all of the HTML elements that appear above, like div and ul, are macros also. This means my Maud layout code is actually Rust code! And that means the Rust compiler will check it and make sure it’s valid before it ever runs.

Converting my old ERB templates into Rust macros was a bit tedious, but it was a great way to review and clean up my HTML. In fact, I found a number of mistakes and errors in my HTML code that had been there for 10 years or longer. It was like showing my dirty laundry to the Rust compiler. By the time the compiler was done and let me compile my layout, it was very clean!

What It Worth It?

It took me several months on a spare time basis - an hour here an hour there - to rewrite my blog in Rust. An experienced Rust developer working full time could have done it in a day or two probably.

What did I get for all this effort? Now I have a script that compiles all 146 of my markdown posts very quickly. My old Ruby script took 7.7 seconds to do this, while the new Rust script only takes 0.28 seconds! That’s over 27 times faster! In fact, the Rust code is so fast at parsing and compiling the markdown files that I don’t check which files need to be recompiled by comparing timestamps, i.e. what a Makefile would do during a build process. And I don’t process the posts in parallel. Why bother? By the time I pressed ENTER and looked up Rust was almost done building all 146 files in sequence, one after the other.

But what else did I get? The biggest improvement to my blog script, actually, wasn’t the performance. It was the error handling I added. I didn’t mention this above, but using the Rust standard library required me to use the Result<T> generic type. This, in turn, forced me to think about what might go wrong and what to do when it did go wrong. I’ll cover this in my next article. I ended up with a script that was much more reliable and resilient to silly mistakes in my source files, and that gave me helpful error messages… all the while running 27 times faster.

However, the biggest benefit to rewriting my blog in Rust was that I clawed my way up the Rust learning curve a bit. But that wouldn’t have been possible without crates.io and Cargo. Using code from smarter, more seasoned Rust developers gave me a chance to build a useful app, even as a beginner. Cargo found, downloaded and compiled open source code from experts with just a few simple commands.