Free: Programs as Data

Write the program once, as instructions, and choose what each one does when you run it.

"Constraints liberate, liberties constrain."

— Rúnar Bjarnason, Constraints Liberate, Liberties Constrain

Bjarnason's maxim cuts both ways on this page. A Free program is held to its instructions, so you are free to choose what each one does when it runs. But each step is also free to depend on the one before, and a step that waits on a result cannot be seen until that result exists.

Free at a glance

ModelsA program held as data: instructions that an interpreter runs later, in a monad it chooses
ReplacesCalls to an injected service, made directly from business code
Effect PathFreePath
InstancesFunctor, Applicative, Monad
Choose it whenOne program must run in several ways, such as live, in a test and as an audit; otherwise call the service, see Free Applicative for a program you can inspect whole, or compare every type in Choosing a Type

What You'll Learn

  • Build an order program from instructions held as data, with nothing run yet
  • Run the same program against an in-memory store and as an audit, by choosing the interpreter
  • Predict what foldMap keeps of each instruction's value, and what still deepens the stack
  • Inspect a program before it runs, and explain why only its first instruction shows
  • Choose between Free and Tagless Final

See Example Code

The code on this page is FreeBook.java: the page includes it, so the build compiles and runs it. FreeBookTest.java holds what the page says each method does.

Where Free fits

Most code never builds a Free by hand. @EffectAlgebra generates the constructors and the interpreter base class for an instruction set, @ComposeEffects combines several, and the Effect Handlers chapter shows the whole pattern. This page shows what those programs are made of.


Instructions held as data

An order program prices a line, and cancels the order when the line costs more than a limit. Call an injected OrderService and a test can pass a fake, but each call runs the moment it is made, and nothing can look at the program first. A Free program holds the steps as instructions instead, which an interpreter runs later: a live interpreter calls the service, a test interpreter works against memory, and an audit interpreter records what it was asked. The instructions are the OrderOp records from Applicative, Selective or Monad?:

/**
 * The order service's instructions, held as data so that a program built from them can be inspected
 * before an interpreter runs it. {@code @EffectAlgebra} generates the {@code Kind} encoding, the
 * {@code Functor}, the interpreter base class and the {@code Free} constructors.
 */
@NullMarked
@EffectAlgebra
public sealed interface OrderOp<A> permits OrderOp.PriceOf, OrderOp.Cancel {

  /** Maps a function over the result type. */
  <B> OrderOp<B> mapK(Function<? super A, ? extends B> f);

  /**
   * Looks up the price of a SKU.
   *
   * @param sku the SKU to price
   * @param k continuation from the price to {@code A}
   * @param <A> the result type
   */
  record PriceOf<A>(String sku, Function<BigDecimal, A> k) implements OrderOp<A> {
    @Override
    public <B> OrderOp<B> mapK(Function<? super A, ? extends B> f) {
      return new PriceOf<>(sku, k.andThen(f));
    }
  }

  /**
   * Cancels an order.
   *
   * @param orderId the order to cancel
   * @param k continuation from {@link Unit} to {@code A}
   * @param <A> the result type
   */
  record Cancel<A>(UUID orderId, Function<Unit, A> k) implements OrderOp<A> {
    @Override
    public <B> OrderOp<B> mapK(Function<? super A, ? extends B> f) {
      return new Cancel<>(orderId, k.andThen(f));
    }
  }
}

Each record carries a continuation k, from the instruction's result to whatever the program does next. @EffectAlgebra generates the rest: OrderOpKind and OrderOpKindHelper, its encoding as a Kind; OrderOpOps, with a Free constructor for each record; a Functor; and OrderOpInterpreter, the base class an interpreter extends. The code on this page uses these imports:

import static org.higherkindedj.hkt.free.FreeKindHelper.FREE;
import static org.higherkindedj.hkt.id.IdKindHelper.ID;
import static org.higherkindedj.hkt.instances.Witnesses.id;
import static org.higherkindedj.hkt.writer.WriterKindHelper.WRITER;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.UUID;
import java.util.function.Function;
import org.higherkindedj.example.book.foundations.AuditEntry;
import org.higherkindedj.example.book.foundations.OrderOp;
import org.higherkindedj.example.book.foundations.OrderOpFunctor;
import org.higherkindedj.example.book.foundations.OrderOpInterpreter;
import org.higherkindedj.example.book.foundations.OrderOpKind;
import org.higherkindedj.example.book.foundations.OrderOpOps;
import org.higherkindedj.hkt.Functor;
import org.higherkindedj.hkt.Kind;
import org.higherkindedj.hkt.Monoids;
import org.higherkindedj.hkt.Unit;
import org.higherkindedj.hkt.effect.FreePath;
import org.higherkindedj.hkt.effect.Path;
import org.higherkindedj.hkt.free.Free;
import org.higherkindedj.hkt.free.FreeFactory;
import org.higherkindedj.hkt.free.FreeKind;
import org.higherkindedj.hkt.free.FreeMonad;
import org.higherkindedj.hkt.free.ProgramAnalyser;
import org.higherkindedj.hkt.free.ProgramAnalysis;
import org.higherkindedj.hkt.id.Id;
import org.higherkindedj.hkt.id.IdKind;
import org.higherkindedj.hkt.instances.Instances;
import org.higherkindedj.hkt.writer.Writer;
import org.higherkindedj.hkt.writer.WriterKind;

Path.free puts each generated constructor on a FreePath:

  static final Functor<OrderOpKind.Witness> ORDER_OPS = OrderOpFunctor.instance();

  // Each step is one instruction, held as data: nothing is priced or cancelled yet.
  // Function.identity() is the continuation k: the step's result is the instruction's own.
  static FreePath<OrderOpKind.Witness, BigDecimal> priceOf(String sku) {
    return Path.free(OrderOpOps.priceOf(sku, Function.identity()), ORDER_OPS);
  }

  static FreePath<OrderOpKind.Witness, Unit> cancel(UUID orderId) {
    return Path.free(OrderOpOps.cancel(orderId, Function.identity()), ORDER_OPS);
  }

The program chains them with via. The second step needs the price, so which step it is depends on what the first gives:

  // What the program decided about a line
  record Decision(String sku, BigDecimal price, boolean cancelled) {}

  // Cancels the order if the line costs more than the limit: the second step needs the price
  static FreePath<OrderOpKind.Witness, Decision> cancelIfOver(
      UUID orderId, String sku, BigDecimal limit) {
    return priceOf(sku)
        .via(
            price ->
                price.compareTo(limit) > 0
                    ? cancel(orderId).map(_ -> new Decision(sku, price, true))
                    : Path.freePure(new Decision(sku, price, false), ORDER_OPS));
  }

Nothing has been priced or cancelled. cancelIfOver gives a description of the two steps, which runs only when an interpreter runs it, and the same description can run many times.

One program, two interpreters

An interpreter says what each instruction does, in a monad it chooses. It extends OrderOpInterpreter<M>, which is a Natural from OrderOp to M, with one method for each record, and each method hands its result to the record's k. This one runs in Id, against a catalogue and a list of cancelled orders. Its CATALOGUE prices a LAMP at 40.00 and a BULB at 2.50:

  // Runs each instruction against a catalogue and a list of cancelled orders
  static final class InMemoryOrders extends OrderOpInterpreter<IdKind.Witness> {
    final List<UUID> cancelled = new ArrayList<>();

    @Override
    protected <A> Kind<IdKind.Witness, A> handlePriceOf(OrderOp.PriceOf<A> op) {
      return ID.widen(Id.of(op.k().apply(CATALOGUE.get(op.sku()))));
    }

    @Override
    protected <A> Kind<IdKind.Witness, A> handleCancel(OrderOp.Cancel<A> op) {
      cancelled.add(op.orderId());
      return ID.widen(Id.of(op.k().apply(Unit.INSTANCE)));
    }
  }

foldMap runs the program with it. LIMIT is 30.00, so the lamp's line cancels the order:

    InMemoryOrders store = new InMemoryOrders();

    Kind<IdKind.Witness, Decision> ran =
        cancelIfOver(ORDER, "LAMP", LIMIT).foldMap(store, Instances.monad(id())).runKind();

    Decision lamp = ID.narrow(ran).value();
    // Decision[sku=LAMP, price=40.00, cancelled=true]

    boolean cancelled = store.cancelled.contains(ORDER);
    // true

foldMap takes one instruction at a time. The interpreter runs it, and the program's continuation, given the result, says what comes next:

%%{init: {"sequence": {"actorMargin": 20, "diagramMarginX": 10}}}%%
sequenceDiagram
    accTitle: How foldMap runs cancelIfOver with the in-memory interpreter
    accDescr: foldMap takes the program's first instruction, PriceOf LAMP, and hands it to the interpreter, which gives Id of 40.00. foldMap hands the price to the program's continuation, which compares it with the limit and gives the next instruction, Cancel. The interpreter records the cancellation and gives Id of Unit. foldMap hands that to the continuation, which gives the program's result, a Decision that the order was cancelled.
    participant P as cancelIfOver
    participant F as foldMap
    participant I as InMemoryOrders
    P-->>F: PriceOf LAMP
    F->>I: PriceOf LAMP
    I-->>F: Id(40.00)
    F->>P: continue with 40.00
    P-->>F: Cancel the order
    F->>I: Cancel the order
    Note over I: records the order
    I-->>F: Id(Unit)
    F->>P: continue with Unit
    P-->>F: the Decision, cancelled

A second interpreter, AuditedOrders, cancels nothing. It records each instruction as an entry in a Writer's audit log:

  // Keeps an audit entry for each instruction in a Writer's log, and cancels nothing
  static final class AuditedOrders
      extends OrderOpInterpreter<WriterKind.Witness<List<AuditEntry>>> {
    private final UUID orderId;

    AuditedOrders(UUID orderId) {
      this.orderId = orderId;
    }

    @Override
    protected <A> Kind<WriterKind.Witness<List<AuditEntry>>, A> handlePriceOf(
        OrderOp.PriceOf<A> op) {
      BigDecimal price = CATALOGUE.get(op.sku());
      AuditEntry entry = new AuditEntry(orderId, "priced " + op.sku() + " at " + price);
      return WRITER.widen(Writer.of(List.of(entry), op.k().apply(price)));
    }

    @Override
    protected <A> Kind<WriterKind.Witness<List<AuditEntry>>, A> handleCancel(OrderOp.Cancel<A> op) {
      AuditEntry entry = new AuditEntry(op.orderId(), "would cancel");
      return WRITER.widen(Writer.of(List.of(entry), op.k().apply(Unit.INSTANCE)));
    }
  }

    Writer<List<AuditEntry>, Decision> audited =
        WRITER.narrow(
            cancelIfOver(ORDER, "LAMP", LIMIT)
                .foldMap(new AuditedOrders(ORDER), Instances.writer(Monoids.list()))
                .runKind());

    List<String> events = audited.log().stream().map(AuditEntry::event).toList();
    // [priced LAMP at 40.00, would cancel]

Free.foldMap also takes a raw Function from instruction to target. Prefer a Natural, such as a generated interpreter, which states that each instruction's result type comes through unchanged.

What foldMap keeps

foldMap hands each instruction's whole value to the target monad. The audit's log holds both entries because the Writer keeps every entry it is given, and in the same way a List target keeps every result, and an EitherOrBoth every warning. A deep program runs in Id, Either, Writer, EitherOrBoth, State or IO without overflowing the stack.

Two things still deepen the stack. An instruction that gives several results, such as a List of two, runs the rest of the program once for each. A Reader nests one call for each instruction when you run it.

A program always gives a value

Free.pure(null) and Path.freePure(null, functor) throw at the call, and a map function that returns null fails the program when it is interpreted. A Task Always Gives a Value sets out the rule every lazy type follows.

What can be seen before it runs

A program held as data can be inspected before it runs. ProgramAnalyser counts what it can see:

    ProgramAnalysis analysis = ProgramAnalyser.analyse(cancelIfOver(ORDER, "LAMP", LIMIT).toFree());

    // How many instructions the analysis can see, and whether a function hides any more
    int seen = analysis.suspendCount();
    // 1
    boolean hidden = analysis.hasOpaqueRegions();
    // true

Only the first instruction shows. The cancel waits inside the function that via was given, and no analysis can see into a function without running it. A program whose steps do not depend on one another can be seen whole: Free Applicative holds one, and Applicative, Selective or Monad? prices the same OrderOp instructions that way. Program Analysis lists what ProgramAnalyser counts.

Free or Tagless Final

Tagless Final reaches the same goals, several interpreters and tests without a live service, without building programs as data. The program is a method written against an interface of operations, generic over the monad, and each interpreter implements the interface.

FreeTagless Final
A program isA value, which you can hold, pass around and run more than onceA method, which runs when it is called with an interpreter
Seen before it runsUp to the first instruction whose result the rest needsBy running it with an interpreter that records instead of acting
Cost per stepHigher: each instruction is interpretedLower: each call runs directly
Code to writeAn instruction set, which @EffectAlgebra encodes, and each interpreterAn interface, and each implementation

Choose Free when the program itself must be a value: to pass it around, or to move it into a larger instruction set with EitherF. It also runs a deeply recursive program in a strict target such as Id, where foldMap's loop keeps the stack flat. Choose Tagless Final when only the interpreters matter.

Creating instances

A generated constructor such as OrderOpOps.priceOf(sku, k) lifts one instruction into a Free, and Free.liftF(fa, functor) lifts any. Free.pure(value) holds a result with no instruction. Path.free(free, functor), Path.freeLift(fa, functor) and Path.freePure(value, functor) start a FreePath. An instruction set without a Functor of its own can take one from Coyoneda.

Methods

MethodWhat it does
freePath.via(f), map(f)Chain the next step on the result, or change the result
zipWith(other, f)Combine two programs' results
handleError(type, handler)Recover a failure of that type in the target monad, when the target is a MonadError
recover(f)Recover any Throwable failure the same way
foldMap(interpreter, monad)Run the program, giving a GenericPath in the target monad
toFree()Gives the Free
free.foldMap(interpreter, monad)Run a Free, giving a Kind in the target monad
Free.translate(free, natural, functor)Move a program to another instruction set, as the EitherF page shows

Working with Kind

A Free is already its own Kind, so FREE.widen and FREE.narrow, from FreeKindHelper, are casts. Generic code takes it through a FreeMonad, built with new FreeMonad<>(), whose map and flatMap build the program as Free's own do:

    FreeMonad<OrderOpKind.Witness> frees = new FreeMonad<>();

    // A Free is already its own Kind, so widen and narrow are casts
    Kind<FreeKind.Witness<OrderOpKind.Witness>, BigDecimal> lampPrice =
        FREE.widen(OrderOpOps.priceOf("LAMP", Function.identity()));
    Kind<FreeKind.Witness<OrderOpKind.Witness>, BigDecimal> withDelivery =
        frees.map(price -> price.add(new BigDecimal("4.99")), lampPrice);

    BigDecimal charged =
        ID.narrow(FREE.narrow(withDelivery).foldMap(new InMemoryOrders(), Instances.monad(id())))
            .value();
    // 44.99

Free.pure at the start of a chain gives Java nothing to infer the instruction type from, so javac refuses this, with "no instance(s) of type variable(s) B exist":

Free<OrderOpKind.Witness, BigDecimal> fee =
    Free.pure(new BigDecimal("40.00")).map(price -> price.multiply(new BigDecimal("0.10")));

A FreeFactory fixes the instruction type once:

    // A factory fixes the instruction type once, so Java can infer it along the chain
    FreeFactory<OrderOpKind.Witness> orders = FreeFactory.of();

    Free<OrderOpKind.Witness, BigDecimal> fee =
        orders.pure(new BigDecimal("40.00")).map(price -> price.multiply(new BigDecimal("0.10")));

A FreePath needs no factory, since Path.freePure(value, functor) takes the instruction type from its Functor.

When to use Free

You needUse
One program run live, in tests and as an auditFree, through @EffectAlgebra
A program inspected whole before it runsFree Applicative
Several instruction sets in one programEitherF, or @ComposeEffects
One side effect, run one wayIO, or a direct call
A hot loopDirect code: each instruction costs an interpretation

Hands-On Learning

Practise the pattern in Tutorial 01: Effect Algebra Basics (5 exercises) and Tutorial 02: Multiple Interpreters (3 exercises), from the Effect Handlers journey.

Benchmarks: FreeBenchmark measures building and interpreting Free programs, and FreeEffectBenchmark the cost of composing several instruction sets. Benchmarks & Performance says how to run them.


Previous: Trampoline Next: Free Applicative