jckarter

everyone already knows i'm a dog

the swift programming language is my fault to some degree. mostly here to see dogs, shitpost, fix old computers, and/or talk about math and weird computer programming things. for effortposts check the #longpost pinned tag. asks are open.


email
mailto:joe@duriansoftware.com
discord
jckarter

jckarter
@jckarter

One interesting language design thread we've stumbled upon with Swift, but haven't fully developed, is the use of coroutines as an alternative to higher-order functions for building "control flow like" constructs. No slight against higher-order functions—as a singular language concept, they definitely pay for themselves in the expressivity they add—but in typed languages, whose type systems already have a tendency toward ever-growing complexity, function types are a particularly good complexity generator. Coroutines are definitely a more complex concept than functions, but I wanted to share some of my thoughts on how they have the potential to save complexity elsewhere, allowing for similar expressivity in extensible control flow constructs while requiring a less complex type system to manage the composition of effects within those constructs.


fullmoon
@fullmoon

Specifically, go through the tutorial: https://hackage.haskell.org/package/pipes-4.3.16/docs/Pipes-Tutorial.html

My pipes package does exactly what the above chost describes and even comes with some elegant mathematical laws that fall out as a consequence of the implementation being inspired by category theory.

For example, if you model for loops using coroutines, you can derive three laws.

The first law (which is the "left identity" law) is:

for (yield x) f = f x

… which says that if you loop over a coroutine that yields once, it's the same as calling the body of the loop on the single value that was yielded.

The second law (the "right identity" law) is:

for s yield = s

… which says that if you loop over a coroutine and do nothing except re-yield each element then you get back the original coroutine.

The final law (the "associativity" law) is:

for s (\x -> for (f x) g) = for (for s f) g

… which says that any doubly-nested loop can be transformed an equivalent two-pass loop.

The correspondence to category theory becomes clearer if you define the following operator:

(f ~> g) x = for (f x) g

… because then the three laws become:

yield ~> f = f  -- Left identity law

f ~> yield = f  -- Right identity law

(f ~> g) ~> h = f ~> (g ~> h)  -- Associativity law

You must log in to comment.

in reply to @jckarter's post:

This is really interesting - I wonder how many of these problems you mention in the end could be solved with a "generator factory" pattern, where the factory function's scope stores the coroutine's state and you could call the returned generator function for one execution of the loop? Although that introduces the problem of when to run the code that in your coroutine structure is directly after the yield...