Construction by Destruction

We’ve now seen the chan expression in action, using the obtained channel to return early in its process. But that only scratches the surface!

The channel you obtain isn’t just a return handle — it’s a direct connection to the consumer of the result. It can be interacted with sequentially, constructing a value step-by-step.

The title of this section, “construction by destruction”, is very apt! What we’re about to learn here is exactly analogous to the famous trick in mathematics: a proof by contradiction. And, it’s just as powerful.

Duality in theory

Every type in Par has a dual — the opposite role in communication.

There is a type operator, dual <type>, which transforms a type to its dual. Here’s how it’s defined structurally:

dual ! ?
dual ? !
dual (A) B [A] dual B
dual [A] B (A) dual B
dual either {
  .left A,
  .right B,
}
choice {
  .left => dual A,
  .right => dual B,
}
dual choice {
  .left => A,
  .right => B,
}
either {
  .left dual A,
  .right dual B,
}
dual recursive F<self> iterative dual F<dual self>
dual iterative F<self> recursive dual F<dual self>
dual [type a] F<a> (type a) dual F<a>
dual (type a) F<a> [type a] dual F<a>

Don’t worry if the F<...> in recursive and generic types looks intimidating. It’s just a way to formalize that after flipping from recursive to iterative (and similarly in the other cases), we continue dualizing the body.”.

Looking at the table, here’s what we can see:

The last point is important. It’s a fact, in general, that dual dual A is equal to A.

Duality in action

Here’s a familiar definition:

type List<a> = recursive either {
  .end!,
  .item(a) self,
}

So, what’s its dual? Applying the above rules, we get:

iterative choice {
  .end => ?,
  .item(a) => self,
}

While a List<a> provides items, until it reaches the end, its dual requires you to give items (via the .item branch), or signal the end. Whoever is consuming a list, this dual type provides a good way to communicate with them.

Notice the ? in the .end branch. That’s a continuation. There is no expression syntax for this type, but finally, we’re going to learn how to handle it in processes!

Remember: in a chan, the channel you obtain inside the block always has the dual type of the expression’s final result. Let’s use this to construct a list step-by-step.

def SmallList: List<Int> = chan yield {
  yield.item(1)
  yield.item(2)
  yield.item(3)
  yield.end
  yield!
}

// def SmallList = *(1, 2, 3)

This is just a usual handling of an iterative choice, except for the last line.

Selecting the .end branch transforms the yield channel into a ? — the continuation type. At that point, the protocol is over, and only one command is valid: a break. It’s spelled !, that’s the last line:

  yield!  // break here

Like linking, it has to be the last command in a process. In fact, link and break are the only ways to end a process.

A real example: flattening a list of lists

Let’s now use this style to implement something meaningful. We’ll write a function that flattens a nested list:

dec Flatten : [type a] [List<List<a>>] List<a>

It’s a generic function, using the forall for polymorphism.

Here’s the full implementation, imperative-style:

def Flatten = [type a] [lists] chan yield {
  lists.begin/outer.case {
    .end! => {
      yield.end!
    }

    .item(list) => {
      list.begin/inner.case {
        .end! => {}
        .item(value) => {
          yield.item(value)
          list.loop/inner
        }
      }
      lists.loop/outer
    }
  }
}

It makes a bunch of concepts we’ve already covered come together.

  • We loop through the outer list of lists using .begin/outer and .loop/outer.
  • If it’s .end!, we finish: yield.end!.
  • If it’s .item(list), we then begin looping through the inner list.
    • We don’t manually bind the remainder of the list — the communication simply continues on the original variable: lists.
    • The nested .begin/.loop shines here; no helper functions needed.
  • In the inner loop:
    • If it’s .end!, we’re done with that list — we continue the outer loop.
    • If it’s .item(value), we yield it to the consumer with yield.item(value), then loop again. Re-binding of the rest of the list is not needed here, either.

Duality combined with the chan expressions gives us a lot of expressivity.
Constructing lists generator-style is just one of the use-cases.
Whenever it feels more appropriate to become a value instead of constructing it from parts, chan and duality come to the task!