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 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 fromrecursive
toiterative
(and similarly in the other cases), we continue dualizing the body.”.
Looking at the table, here’s what we can see:
- Units are dual to continuations.
- Functions are dual to pairs.
- Eithers are dual to choices.
- Recursives are dual to iteratives.
- Foralls are dual to existentials.
- The duality always goes both ways!
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.
- We don’t manually bind the remainder of the list — the communication simply continues on
the original variable:
- 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 withyield.item(value)
, then loop again. Re-binding of the rest of the list is not needed here, either.
- If it’s
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!