Pretty's implementation

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 (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(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:

double area() const override {
}
private:
};

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

} // namespace detail

Helper functions make it easy to create instances of Shape:

}

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);

Created: 2021-10-19 Tue 19:55