Doug's Compiler Corner

Originally posted on 2024-11-23 17:30:00 +0000

Last updated on 2024-11-24 06:47:01 +0000

Swift for C++ Practitioners, Part 11: Domain-Specific (Embedded) Languages with Result Builders

The prior installment of this series covered operator overloading in Swift in great detail. As in C++, operator overloading can be used to great effect to build Domain-Specific Languages embedded within normal source code. When used well, these Domain-Specific Embedded Languages (DSELs) can make it easy to express your ideas in a specific domain while still leveraging all of the tools of the general-purpose programming language in which they are embedded. (Used poorly, it can be make a mess... so let's not do that.)

Swift provides some additional features specifically to help with the construction of DSELs. All of these are syntactic sugar: you can express what they do in Swift code without them, but doing so often requires a lot of boilerplate that can leave a bitter taste in your mouth. (Boiled plates, yuck!)

Result builders

There is a large class of DSLs that are declarative in nature, meaning that you state (declare) what you want but not how it should be accomplished. Then, the library or tool that processes the declarative DSL will turn that into a computation that produces the desired result. While there are some programming languages that are declarative (such as Prolog), neither Swift nor C++ are declarative languages: they're both imperative with some functional elements, but however you spin it, in Swift and C++ it's up to you to describe how to compute the answer you want.

Within imperative and functional languages, there are often libraries that provide a declarative API. For example, a regular expression library like std::regex has an interface to describe the shape of strings you want to match, and the library "compiles" that into an efficient state machine to use when matching the regular expression against input strings. To achieve this, the input language (regular expressions) is constrained to something that admits an efficient implementation. This is an important aspect of declarative DSLs: constraints are key to keeping code using the DSL easy to reason about and ensure that efficient implementation is possible. Other common kinds of DSLs include structured output (e.g., to HTML) and declarative UI libraries.

Swift's result builders provide a way to embed a declarative DSL directly in Swift. The inputs to result builders are blocks of code---closures---with a restricted form that gets translated into a structured form that the library can compute. Each kind of entity allowed within the closures, such as expressions and if statements, can be mapped by the result builder into another value, with the results being combined at the end of each block. That's all very abstract, so let's get to the CODE!

A small HTML DSL

Emitting HTML from a program is a simple but tedious exercise: tags need to be typed correctly and matched, and the moment you have any logic in there, you're concatenating strings together everywhere. Multi-line strings and interpolation can reduce the boilerplate a bit, but it can still be messy even for simple things:

let output = """
  <html>
    <body>
      <div>
        \(chapterTitle != nil ? "<h1>\(chapterTitle!)</h1>\n" : "")
        <para>Call me Ishmael. Some years ago...</para>
				<para>There is now your insular city...</para>
      </div>
    </body>
  </html>
  """

With result builders, we can write the above in a more declarative manner that leverages Swift's syntax and control structures to eliminate the error-prone matching of syntax and nesting of string interpolations. Let's start with the result and work back from there. We can produce something like this:

let output = html {
  body {
    div {
      if let chapterTitle {
        h1 { chapterTitle }
      }
      para { "Call me Ishmael. Some years ago..." }
      para { "There is now your insular city..." }
    }
  }
}

The structure is the same, but we've taken all of the manual strings and nested string interpolations out of it: the nesting structure of the HTML is expressed in the braces structure of the Swift, the actual strings we're placing into the HTML are either string literals or string variables, without nesting, and we get to use control-flow affordances like if let to deal with optionals cleanly, so we don't need to do the != nil and ! dance we did before.

From the Swift language perspective, this looks like a bunch of calls to functions html, body, div, h1, and para, where each of these calls takes a trailing closure. That is the entry point for result builders: the closures here have the result builder transformation applied to them, which turns this declarative code into values at runtime, which are then rendered into HTML. The core of my implementation is a simple protocol for a value that can be rendered into HTML:

protocol HTMLElement {
  /// Render this HTML element into a string using the given indentation level.
  func renderHTML(indentation: Int) -> String
}

Strings can be rendered into HTML trivially, although a real implementation would properly escape HTML control characters like < and >:

extension String: HTMLElement {
	func renderHTML(indentation: Int) -> String { self }
}

More importantly, we can define a new HTML "tag" type that expresses the notion of wrapping an HTML element in a tag. The code itself is some straightforward string concatenations:

struct HTMLTag: HTMLElement {
  let name: String
  let requiresNewline: Bool
  let element: any HTMLElement

  func renderHTML(indentation: Int) -> String {
    let indentString: String
    if requiresNewline {
      indentString = "\n" + String(repeating: " ", count: indentation)
    } else {
      indentString = ""
    }

    var rendered = indentString
    rendered += "<\(name)>"
    rendered += element.renderHTML(indentation: indentation + 2)
    rendered += indentString
    rendered += "</\(name)>"
    return rendered
  }
}

Note that the element can be any HTMLElement, so we can nest HTML tags within other tags. A div tag containing a para tag with some text in it can be represented as, e.g.,

HTMLTag(
  name: "div", 
  requiresNewline: true, 
  element: HTMLTag(
    name: "para",
    requiresNewline: false,
    element: ""Call me Ishmael. Some years ago...""
  )
)

We also need to be able to produce a sequence of HTML elements. The simplest way to do this is by making heterogeneous arrays of HTMLElement values into an HTMLElement:

extension Array<any HTMLElement>: HTMLElement {
  func renderHTML(indentation: Int) -> String {
    switch count {
    case 0:
      return ""

    case 1:
      return self[0].renderHTML(indentation: indentation)

    default:
      let indentString = "\n" + String(repeating: " ", count: indentation)
      return String(flatMap { element in
          indentString + element.renderHTML(indentation: indentation + 1)
        }
      )
    }
  }
}

We now have enough to be able to express a structured HTML document as an any HTMLElement, composing it from strings (the text), HTML tags wrapping other HTML elements, and arrays of HTML elements. But the syntax for building an HTML document this way tastes a bit like boiled plates. That's where result builders come in.

Result builders for the HTML DSL

Result builders take a closure and apply a syntactic transformation to each of the values in that closure, mapping syntax like if/else over to functions that capturing the resulting values. Let's step back to our goal for the DSL:

let output = html {
  body {
    div {
      if let chapterTitle {
        h1 { chapterTitle }
      }
      para { "Call me Ishmael. Some years ago..." }
      para { "There is now your insular city..." }
    }
  }
}

Each of the tag names here---html, body, div, h1, and para---will be implemented by a function that takes a closure. The values produced by each closure form the HTML elements, that are aggregated together. That aggregation is performed by the static methods on a result builder type, which we are going to call HTMLBuilder. It looks like this:

@resultBuilder
struct HTMLBuilder {
  static func buildExpression(_ element: some HTMLElement) -> any HTMLElement {
    element
  }

  static func buildBlock(_ elements: any HTMLElement...) -> any HTMLElement {
    elements
  }

  static func buildOptional(_ element: (any HTMLElement)?) -> any HTMLElement {
    if let element { [element] }
    else { [] }
  }

  static func buildEither(first: any HTMLElement) -> any HTMLElement {
    first
  }

  static func buildEither(second: any HTMLElement) -> any HTMLElement {
    second
  }

  static func buildArray(_ components: [any HTMLElement]) -> any HTMLElement {
    components
  }
}

Note that each of the functions here takes in some any HTMLElement instances and produces an any HTMLElement. The so-called result builder transform produces calls to these static methods based on language syntax. If you read the earlier post in this series about ExpressibleByStringInterpolation, this approach of calling functions on a builder might look familiar. Here are how some of the calls get formed in the result builder transform:

  • buildExpression is called to transform a single value in a closure into something that can be combined into a block. For example, the string value "Call me Ishmael. Some years ago..." will be passed into it via
   HTMLBuilder.buildExpression(`"Call me Ishmael. Some years ago..."`)

If buildExpression is not provided, Swift applies the identity function. Our HTMLBuilder example doesn't actually need it at all, because it's effectively just the identity function, but it's possible to do some translation of values here to get them into a common type.

  • buildBlock is called to gather all of the results together from a single statement block in the closure. For example, if a closure had two strings in it, e.g.,
   {
    "hello"
    "world"
  }

Then buildBlock would be called as HTMLBuilder.buildBlock("hello", "world").

  • buildOptional is called when there is an if statement that may or may not produce a value. For example, consider the chapter title:
   if let chapterTitle {
    h1 { chapterTitle }
  }

Here, if chapterTitle was non-nil, we'll have an h1 tag with the chapter title in it. Otherwise, nothing! The result builder transform maps this as a call to buildOptional with either the result of the if block, or a nil. Our HTMLBuilder chooses to handle this via an array containing either zero or one element.

  • buildEither(first:) and buildEither(second:) are used for if statements that also have an else. If the if evaluates true, buildEither(first:) ends up getting called with the value produced by the if block. If the if evaluates false, buildEither(second:) gets called with the value produced by the else block. Here's another made-up example:
   if let dedication {
    para { dedication }
  } else {
    para { "To all the world's children." }
  }

This translates into, roughly,

   dedication != nil ? HTMLBuilder.buildEither(first: para { dedication! })
                    : HTMLBuilder.buildEither(second: para { "To all the world's children." })

The actual implementation generalizes to arbitrary if-else chains (sometimes with a buildOptional at the end) and even arbitrary switch statements, which are themselves essentially just syntactic sugar for an if-else chain. buildEither(first:), buildEither(second:), and buildOptional are all optional: if a result builder omits them, it cannot be applied to closures that include if or switch statements.

  • buildArray is used to capture the results of a for loop, which are passed into buildArray as an array of captured values. Our original example is a bit too pre-baked, but we could imagine generating the chapters and their paragraphs in nested for loops:
   for chapter in chapters {
    div {
      if let chapterTitle = chapter.title {
        h1 { chapterTitle }
      }
      
      for paragraphText in chapter.paragraphs {
        para { paragraphText }
      }
    }
  }

The inner for loop executes, collecting new any HTMLElement values for each iteration. Then, the resulting array is passed to HTMLBuilder.buildArray. That result becomes part of the buildBlock for the enclosing for loop's body, and each of those values gets collected into an array for the outermost call to HTMLBuilder.buildArray. Like with the previous operations, buildArray is optional: if not provided, the result builder cannot be applied to a closure containing for loops.

Going back to our original example, here is the "desugared" version after the result builder transform has been applied to each of the closures:

let output = html {
  let a1 = body {
    let b1 = div {
      let c1_opt: (any HTMLElement)?
      if let chapterTitle {
        let d1 = h1 { 
          let e1 = HTMLBuilder.buildExpression(chapterTitle)
          return HTMLBuilder.buildBlock(e1)
        }
        
        c1 = HTMLBuilder.buildBlock(d1)
      } else {
        c1 = nil
      }
      let c1 = HTMLBuilder.buildOptional(c1_opt)
      
      let c2 = para { 
        let f1 = HTMLBuilder.buildExpression("Call me Ishmael. Some years ago...")
        return HTMLBuilder.buildBlock(f1)
      }
      
      let c3 = para { 
        let g1 = HTMLBuilder.buildExpression("There is now your insular city...")
        return HTMLBuilder.buildBlock(g1)
      }
      
      return HTMLBuilder.buildBlock(c1, c2, c3)
    }
    return HTMLBuilder.buildBlock(b1)
  }
  return HTMLBuilder.buildBlock(a1)
}

We are almost done, but we still don't know what the tag functions look like, or how it is that Swift decides to apply the result builder transform. Here is the body function:

func body(@HTMLBuilder body: () -> any HTMLElement) -> HTMLTag {
  HTMLTag(name: "body", requiresNewline: true, body: body)
}

The body function takes a closure that has @HTMLBuilder attribute on it, meaning that the HTMLBuilder transform will be applied to a closure passed into body. Once HTMLBuilder has been applied, that closure will return any HTMLElement, and we wrap that resulting value in the HTMLTag structure. We're done! The other HTML elements look basically the same:

func h1(@HTMLBuilder body: () -> any HTMLElement) -> HTMLTag {
  HTMLTag(name: "h1", requiresNewline: false, body: body)
}

func div(@HTMLBuilder body: () -> any HTMLElement) -> HTMLTag {
  HTMLTag(name: "div", requiresNewline: true, body: body)
}

func para(@HTMLBuilder body: () -> any HTMLElement) -> HTMLTag {
  HTMLTag(name: "para", requiresNewline: false, body: body)
}

Only on the top-level html function do we do anything different, because here we render the produced HTMLTag to a string directly:

func html(@HTMLBuilder body: () -> any HTMLElement) -> String {
  HTMLTag(name: "html", requiresNewline: true, body: body).renderHTML(indentation: 0)
}

Strong typing for result builders

If you read my earlier post on type erasure, you might be a little bit worried about the number of any HTMLElement instances running around: it's all very dynamic, but does it have to be?

Short answer: no.

Long answer: the result builder transform is designed such that it's possible to retain the types of all of the elements, and even some of the control structures, within the type system. If you're thinking "expression templates", you're right! We're going to systematically remove the any types from our example above to produce a result builder that maintains the structure of the document in the static type system. Let's do this!

Let's start out easy: the HTMLTag type currently stores an any HTMLElement, but we can lift that into a generic parameter without changing much code at all:

struct HTMLTag<Element: HTMLElement>: HTMLElement {
  let name: String
  let requiresNewline: Bool
  let element: Element

  init(
    name: String,
    requiresNewline: Bool,
    @HTMLBuilder body: () -> Element
  ) {
    self.name = name
    self.requiresNewline = requiresNewline
    self.element = body()
  }

  // .. renderHTML(indentation:) stays the same
}

Now that HTMLTag is generic, we can make those top-level functions like body and div generic. For example, body could look like this:

func body<Element: HTMLElement>(@HTMLBuilder body: () -> Element) -> HTMLTag<Element> {
  HTMLTag(name: "body", requiresNewline: true, body: body)
}

The real action is HTMLBuilder, where we have a lot of functions that return any HTMLElement. We'll take them one-by-one, starting with the easiest: buildExpression just returns what it got, so we can make it generic directly:

   static func buildExpression<Element: HTMLElement>(_ element: Element) -> Element {
    element
  }

Next, we'll tackle buildOptional, which is used for (e.g.) an if without an else. The type-erasing implementation from above turns an optional into an array of zero or one elements, which is very dynamic. We need something that takes an optional of some HTMLElement type, like this...

   static func buildOptional<Element: HTMLElement>(_ element: Element?) -> ??? {
    ???
  }

But how can we fill in the result type and body? We need an HTMLElement that is optional (0 or 1) value, so why not use... Optional itself?

extension Optional: HTMLElement where Wrapped: HTMLElement {
  func renderHTML(indentation: Int) -> String {
    self?.renderHTML(indentation: indentation) ?? ""
  }
}

Now, an optional of some HTMLElement-conforming type is itself an HTMLElement, so our buildOptional can just be the identity function:

    static func buildOptional<Element: HTMLElement>(_ element: Element?) -> Element? {
     element
   }

As mentioned above, buildEither handles if..else statements, but is interesting because it comes as a pair of functions buildEither(first:) and buildEither(second:) that are called for the "if" value and "else" values, respectively. To capture both sides of the branch, we'll need some type that can represent either of two options. Alas, Swift's standard library doesn't have one just, so we'll define one ourselves as a generic enum Either:

enum Either<First, Second> {
  case first(First)
  case second(Second)
}

and make it an HTMLElement when both sides are HTMLElements:

extension Either: HTMLElement where First: HTMLElement, Second: HTMLElement {
  func renderHTML(indentation: Int) -> String {
    switch self {
    case .first(let element):
      element.renderHTML(indentation: indentation)
    case .second(let element):
      element.renderHTML(indentation: indentation)
    }
  }  
}

With this, we can define the pair of buildEither overloads to return Either, like this:

   static func buildEither<First: HTMLElement, Second: HTMLElement>(first element: First) -> Either<First, Second> {
    .first(element)
  }

  static func buildEither<First: HTMLElement, Second: HTMLElement>(second element: Second) -> Either<First, Second> {
    .second(element)
  }

Look at those functions individually, and they are kind of weird: both have First and Second types, yet only one of those types is mentioned as a type of a parameter. However, taken as a pair of calls, we can form a meaningful type. Imagine the following expression:

condition ? buildEither(first: x) : buildEither(second: y)

That whole expression needs to have a single type, and a value of that type can be formed by either the buildEither(first: x) call or the buildEither(second: x) call. Therefore, the branch that calls buildEither(first:) will determine the First type from x (let's call it X) and the branch that calls buildEither(second:) will determine the Second type from y (let's call it Y), resulting in a result type Either<X, Y>.

On to buildArray, which currently takes an array of any HTMLElement, but that won't do: we want to have a concrete element type for the array. Fortunately, we can lift this to take an array of some HTMLElement-conforming type, making it the identity function just like buildOptional:

   static func buildArray<Element: HTMLElement>(_ components: [Element]) -> [Element] {
    components
  }

We do have to generalize the conformance of Array to HTMLElement by making it work for any HTMLElement-conforming Element type, like this:

extension Array: HTMLElement where Element: HTMLElement {
  func renderHTML(indentation: Int) -> String {
    // same as above
  }
}

Only one function remains, buildBlock, but this one is tricky. Right now, it accepts any number of any HTMLElement arguments, which it treats as an array. Unlike with the buildArray function, each of the arguments can have a completely different type because it comes from a different statement in the transformed closure. In the post on generics, I talked about parameter packs, which are a good match for this function:

static func buildBlock<each Element: HTMLElement>(_ element: repeat each Element) -> ??? {
    ???
 }

Now, buildBlock can accept any number of arguments, of different types, so long as every type conforms to HTMLElement. How do we turn that into a single instance that conforms to HTMLElement? Here's the best I came up with:

struct ElementSequence<each Element: HTMLElement>: HTMLElement {
  var renderer: (Int) -> String

  init(_ element: repeat each Element) {
    switch Self.elementCount {
    case 0:
      renderer = { _ in "" }

    case 1:
      renderer = { indentation in
        for element in repeat each element {
          return element.renderHTML(indentation: indentation)
        }
        fatalError("must have returned from the loop")
      }
 
    default:
      renderer = { indentation in
        var finalString = ""
        let indentString = "\n" + String(repeating: " ", count: indentation)
        for element in repeat each element {
          finalString += indentString
          finalString += element.renderHTML(indentation: indentation + 1)
        }
        return finalString
      }
    }
  }

  func renderHTML(indentation: Int) -> String {
    renderer(indentation)
  }

  private static var elementCount: Int {
    var count = 0
    for _ in repeat (each Element).self {
      count += 1
    }
    return count
  }
}

Here, the ElementSequence struct takes any number of type arguments. There's a helper property elementCount that walks through all of the element types to count how many there are, so we can use it in the switch. The interesting bit is in the initializer: it takes all of the actual elements, but rather than store them directly, it stores a function that handles the rendering. The default case is the one that does most of the work: it iterates over each of the elements, rendering them into the resulting string in the same way that we did for arrays. The 0 and 1 cases are there to match what we did for arrays earlier, but are otherwise uninteresting.

The solution above works, and gives us our implementation of buildBlock:

   static func buildBlock<each Element: HTMLElement>(_ element: repeat each Element) -> ElementSequence<repeat each Element> {
    ElementSequence(repeat each element)
  }

I suspect there's a better implementation of ElementSequence. If you find one, please tell me! For now, let's step back to what we've done here: we've eliminated every use of any types, so we have complete static type information. We can see this if we intentionally trigger a compile-time error that will print the type, e.g.,:

let _: Int = body {
    if let chapterTitle {
      h1 {
        chapterTitle
      }
    }

    para {
      "Call me Ishmael. Some years ago..."
    }

    para {
      "There is now your insular city"
    }
  }

The resulting error message contains the full type in all of its static, expression-template-y glory:

HTMLTag<
  ElementSequence<
    ElementSequence<
      HTMLTag<ElementSequence<String>>
    >?, 
    HTMLTag<ElementSequence<String>>, 
    HTMLTag<ElementSequence<String>>
  >
>

Hiding the types

Now that we've proven to ourselves that we can maintain complete static type information throughout the entirety of the result-builder transform, we can have to ask ourselves: is it everything we ever wanted? On the one hand, this approach is a whole lot more optimizable than the one using any types, because enough generic specialization and inlining can completely eliminate all of the abstractions here. On the other hand, that is quite the monster of a type for such a simple example DSL: is it worth inflicing such types on the users of our DSL and leaking them out of the implementation?

This is where some types come in: technically called opaque types, and covered in the earlier post on type erasure, opaque types let you hide the actual types you are returning from a generic function without losing identity. The idea is that the types still exist, but they aren't exposed directly to the user. We can replace the result types of some of our functions with some HTMLElement, meaning "some specific type that conforms to HTMLElement", without changing much other code. For example, buildBlock can be written as follows:

   static func buildBlock<each Element: HTMLElement>(_ element: repeat each Element) -> some HTMLElement {
    return ElementSequence(repeat each element)
  }

This lets us hide the ElementSequence type entirely: it could be private to this file, and therefore not visible to clients. The same could be done for all of the top-level functions like body and h1, which can return some HTMLElement rather than exposing their full return type:

func body(@HTMLBuilder body: () -> some HTMLElement) -> some HTMLElement {
  HTMLTag(name: "body", requiresNewline: true, body: body)
}

func h1(@HTMLBuilder body: () -> some HTMLElement) -> some HTMLElement {
  HTMLTag(name: "h1", requiresNewline: false, body: body)
}

Now, the HTMLTag type has become an implementation detail, and need not be exposed to users. Later versions of the library could choose to express it in some different way without breaking clients, because clients just see some HTMLElement for the types of these calls.

Note that the types still exist, and can be queried at runtime if they are needed. For example, we can capture the call to body in a variable and print its type with type(of:), like this:

let b = body {
    if let chapterTitle {
      h1 {
        chapterTitle
      }
    }

    para {
      "Call me Ishmael. Some years ago..."
    }

    para {
      "There is now your insular city"
    }
  }
print(type(of: b))

and we'll get a printed representation of the full structure of the type like this:

HTMLTag<ElementSequence<Pack{Optional<ElementSequence<Pack{HTMLTag<ElementSequence<Pack{String}>>}>>, HTMLTag<ElementSequence<Pack{String}>>, HTMLTag<ElementSequence<Pack{String}>>}>>

Opaque types provide a balance between the benefits of maintaining DSL structure in the type system (more type checking, better specialization) and putting structure behind an abstraction barrier (for conciseness and implementation-hiding).

Other uses of result builders

We've gone really deep on rendering HTML, something that could perhaps be considered a trivial example. However, it turns out to be really nice in practice, as you can see from Paul Hudson's static site generator Ignite. Result builders are also in use in a number of other DSLs. Here are some examples:

  • Regular expressions: Swift supports regular expressions with a syntax that uses surrounding slashes, e.g., /[$£]\d+\.\d{2}/. However, for more complicated regular expressions, there is also a RegexBuilder DSL that uses result builders. Here is the equivalent in that DSL:
   Regex {
    One(CharacterClass.anyOf("$£"))
    OneOrMore(.digit)
    "."
    Repeat(count: 2) {
      One(.digit)
    }
  }
  • Declarative UI: Perhaps the most well-known use of result builders is the SwiftUI library for declarative UI, which uses result builders. For example:
   List(album.songs) { song in 
    HStack {
      Image(album.cover)
      VStack(alignment: .leading) {
        Text(song.title)
        Text(song.artist.name)
          .foregroundStyle(.secondary)
      }
    }
  }
  • Routing: the Hummingbird package uses result builders to express routing for services:
   let router = RouterBuilder(context: BasicRouterRequestContext.self) {
      TracingMiddleware()
      Get("test") { _, context in
          return context.endpointPath
      }
      Get { _, context in
          return context.endpointPath
      }
      Post("/test2") { _, context in
          return context.endpointPath
      }
  }

Wrap-up and what's next?

Result builders are a big heap of syntactic sugar designed specifically to make it possible to build elegant, type-safe Domain Specific Languages embedded in Swift. They provide a declarative syntax that can be transformed in a manner that can describe the structure of the input in the type system, or collapse it down when that's not necessary, giving expressive power to the author of the result builder.

This post has drifted somewhat from the focus on teaching Swift to C++ programmers, so next I'll bring it back and we'll talk about C++ move semantics and the Swift analogue: noncopyable types.

Tagged with: