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 obtained is actually a lot more than a return handle. It’s a dual, a direct
access to the consumer of the whole chan
expression. 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 get scared by the
F<...>
in self-referential types and generics. It’s just a way to formalize that after flipping fromrecursive
toiterative
(and similarly in the other cases), we proceed to dualize 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!
Now, let’s remember that in the chan
expression, the channel obtained inside its process
has the dual type of the overall result of the expression. 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 turns the yield
channel into a ?
. When a channel has type ?
,
it means you’re done — nothing more is expected of you, and in fact, nothing more is
allowed for you. You have to finish.
The only command available for ?
is called 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
And so we see, 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 out of parts, chan
and duality
come to the task!