Abusing TypeScript Generators
The last chapter of our Matechs Effect Core series: Explore the reason behind APIs.
In the previous chapters of the series we explored the @effect-ts/core ecosystem and some of its data-types like Effect, Managed, Layer and more.
We have explored, at length, the advantages of using statically typed functional programming in typescript to gain modularity, testability and safety of our code.
One thing is missing though, the API we have been using feels a bit awkward for people that come from non-functional languages, for the ones that come from functional languages there is a big missing, namely in scala for, in haskell do.
For the newcomers, let's first explore the reason behind this apis.
We have seen how Monads can represent the concept of sequential operations and we have been using chain to express this all over the place.
This style of programming highlight the function composition aspect, we would like to have a way to also express sequential steps in an imperative way.
For the people coming from javascript or typescript we would like to have something similar to what async/await does but generalised to every Monad.
Early approaches
Historically there have been a significant amount of attempts at approximating Do in the context of functional programming in typescript.
Namely we had 2 approaches:
- the first one by Paul Grey detailed explained in his article at: https://paulgray.net/do-syntax-in-typescript/ using a fluent based api
- the second one by Giulio Canti using a pipeable based api (that we also have as an alternative)
Let's look at the second one:
Basically what happens here is T.do initializes an empty state {} to hold the scope of the computation and bind uses it to progressively fill up the variables step by step.
This way each step has access to the whole set of variables defined up to that point.
Both the fluent & the pipeable APIs are really nice to use but still doesn't feel native typescript and there is a good degree of repetition in accessing the scope explicitly at every bind operation.
Enter the world of generators
Before anything in order to use this API you will need to enable "downlevelIteration": true in your tsconfig.json.
Let's start to explore what are generators:
This will print out:
So basically every yield give us a value and execution is controlled by the caller by calling consuming the generator.
Let's now proceed with the second thing to know:
This will print out:
So basically with a generator we can push the return values of yields from the consumer to populate the variable scope.
The types are just horrible, const a in the generator body is any and there is really no inference working.
Another feature that we are going to exploit is yield* to yield a generator into a generator, surprisingly this works well type wise
:)
Let's see:
This will print out:
and all the types work well, in the signature of constant we read Generator<a, a,="" a="">, the first A is the type of the yield, the second is the type of the yielded value and the third is the type required by the next step.</a,>
The idea here is to use a generator to declare the body of a computation in a monadic context and then, at runtime, starve the generator building up a set of chained computations (initial attempts by https://github.com/nythrox and some others, forgive me for not remembering all).
Generator based do for Effect
Let's put together what we seen so far, we would like to avoid modifying the types of Effect and in general any type so we won't directly add a generator inside them. That would also break variance of the type.
We are going to instead use a function to lift an effect into a generator of effect.
And there we go, we have our nice imperative style of composing effects!
One thing I learned is: "if you have restrictions at the api level, find opportunities to exploit them"
In this case we have an unwanted _ function that we use to convert an effect to a generator of effects we can exploit that to lift a generic natural transformation from any type we want to effect, in the @effect-ts/core/Effect package the gen function can directly deal with:
So you can use it like:
That will produce:
Multi-Shot Monads
The trick explored so far works well for effects that produce a single value, like Effect, Managed and any io-like effect type.
There is a problem with multi-shot effects like Stream or Array, for those the approach taken doesn't work, as we work through the computation above we notice how we progress the iterator at every step of the execution, in a stream or in an array we would have to replay the same for many elements but we have only one iterator.
Iterators are mutable so there is no way we can "clone" the iterator or do any form of defensive copy.
That is not the end though, supposing the body of the generator is pure, as in none of the lines of code outside of the ones inside the yields can modify any external variable or perform any side-effect, we can solve the issue by keeping the stack of computations around and by replaying the iterator every time (idea of https://github.com/mattiamanzati).
This technique has a performance complexity of O(n^2) where n is the number of yields (not the number of elements produced) so this must be taken into account when building large generators.
Let's look at the code of the Stream generator:
Apart from all the overloadings and the adapter code to support different monadic values the key part is:
As we can see we carry around a stack of result and we reconstruct the local scope at each call.
This can be used just like the previous one:
will produce:
Generalisation
Thanks to the HKT structure and the prelude described in the previous chapters we have been able to generalise this approach to work with any monad, the generic code comes in 2 functions available at: https://github.com/Matechs-Garage/matechs-effect/blob/master/packages/core/src/Prelude/DSL/gen.ts namely genF (to be used in one-shot cases, very efficient) and genWithHistoryF (to be used in multi-shot cases, n^2 complexity for the n-th yield).
Bonus:
Let's use all we've seen so far and build up a simulation of a simple program using 2 services, we'll simulate a message broker that flushes the messages on completion and a database that keeps state.
We can see how easy it is to access services using this generator based approach:
Directly yielding the Tag of a service will give you access to its content.
Also if we highlight through the code we can see that the full types are correctly inferred and almost never explicitly specified.
