Pretty's implementation

1. Tagged unions
2. Laziness
3. Concepts

This is a brief summary of some interesting parts of Pretty's implementation.

1 Tagged unions

The Haskell code in Wadler's paper makes frequent use of tagged unions (or "algebraic data types").

A simple example of a tagged union in Haskell is

data Shape
  = Circle Double
  | Rectangle Double Double

area :: Shape -> Double
area (Circle radius) = pi * radius * radius
area (Rectangle length width) = length * width

The way Pretty encodes a type like Shape in C++ is through a reference-counted pointer to a polymorphic class.

namespace detail {
  class Impl {
  public:
    virtual ~Impl() = default;
    virtual double area() const = 0;
  };
} // namespace detail

class Shape final {
public:
  struct Circle{};
  struct Rectangle{};

  Shape(Circle, double radius);
  Shape(Rectangle, double width, double length);
  Shape(Shape&&) = delete;

  double area() const {
    return _impl->area();
  }

private:
  std::shared_ptr<detail::Impl const> _impl;
};

With this encoding, instances of Shape are immutable and relatively cheap to copy.

Each kind of shape is a subclass of detail::Impl:

namespace detail {

  class CircleImpl final : public Impl {
  public:
    explicit CircleImpl(double radius) : _radius{radius} {}

    double area() const override {
      return std::numbers::pi * _radius * _radius;
    }
  private:
    double _radius;
  };

  class RectangleImpl final : public Impl {
    // etc.
  };

} // namespace detail

Helper functions make it easy to create instances of Shape:

Shape circle(double radius) {
  return Shape{Shape::Circle{}, radius};
}

In Pretty, one of the cases of the Doc class is nil (the empty document). We represent this case not with a subclass of DocImpl but instead with the reference-counting pointer set to nullptr. This way, it's straightforward for instances of Doc to be movable.

2 Laziness

In Haskell, values are evaluated lazily. This is a crucial aspect of Wadler's implementation.

In Pretty's implementation, most values are not lazy (they're "strict"). Instead, only the "left" document of the union combinator is evaluated lazily. I believe this is sufficient to achieve the same asymptotic running time as the Haskell version.

Lazy evaluation is achieved via this simple class:

template <typename T>
using Ptr = std::shared_ptr<T const>;

template <typename T>
class LazyPtr final {
public:
  template <typename F>
  explicit LazyPtr(F f) : _f{std::move(f)} {
  }

  Ptr<T> const &force() const {
    if (_f != nullptr) {
      _ptr = _f();
      _f = nullptr;
    }

    return _ptr;
  }

private:
  mutable std::function<Ptr<T>()> _f;
  mutable Ptr<T> _ptr{nullptr};
};

3 Concepts

Concepts are a new feature of C++20.

One use of concepts in Pretty is for overload resolution in template functions. For example, consider the fill function:

template <std::same_as<Doc>... Ds>
Doc fill(Ds const &...ds);

template <std::input_iterator I>
Doc fill(I begin, I end);

Pretty's implementation

Table of Contents

1 Tagged unions

2 Laziness

3 Concepts