Posted onNov 2, 2020

Abusing TypeScript Generators

#functional #typescript

In the previous chapters of the series we explored the@effect-ts/core ecosystem and some of its data-types likeEffect,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 scalafor, in haskelldo.

For the newcomers, let's first explore the reason behind this apis.

We have seen howMonads can represent the concept of sequential operations and we have been usingchain 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 fromjavascript ortypescript we would like to have something similar to whatasync/await does but generalised to everyMonad.

Early approaches

Historically there have been a significant amount of attempts at approximatingDo 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:

import*asTfrom"@effect-ts/core/Effect"import{pipe}from"@effect-ts/core/Function"constprogram=pipe(T.do,T.bind("a",()=>T.succeed(1)),T.bind("b",()=>T.succeed(2)),T.bind("c",({a,b})=>T.succeed(a+b)),T.map(({c})=>c))pipe(program,T.chain((c)=>T.effectTotal(()=>{console.log(c)})),T.runMain)

Basically what happens here isT.do initializes an empty state{} to hold the scope of the computation andbind 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 yourtsconfig.json.

Let's start to explore what are generators:

function*countTo(n:number){leti=0while(i<n){yieldi++}}constiterator=countTo(10)letcurrent=iterator.next()while(!current.done){console.log(current)current=iterator.next()}

This will print out:

{ value: 0, done: false }{ value: 1, done: false }{ value: 2, done: false }{ value: 3, done: false }{ value: 4, done: false }{ value: 5, done: false }{ value: 6, done: false }{ value: 7, done: false }{ value: 8, done: false }{ value: 9, done: false }

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:

function*countTo(n:number){leti=0while(i<n){consta=yieldi++console.log(a)}}constiterator=countTo(10)letinput="a"letcurrent=iterator.next(input)while(!current.done){console.log(current)input+="a"current=iterator.next(input)}

This will print out:

{ value: 0, done: false }aa{ value: 1, done: false }aaa{ value: 2, done: false }aaaa{ value: 3, done: false }aaaaa{ value: 4, done: false }aaaaaa{ value: 5, done: false }aaaaaaa{ value: 6, done: false }aaaaaaaa{ value: 7, done: false }aaaaaaaaa{ value: 8, done: false }aaaaaaaaaa{ value: 9, done: false }aaaaaaaaaaa

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 isany and there is really no inference working.

Another feature that we are going to exploit isyield* to yield a generator into a generator, surprisingly this works well type wise
:)

Let's see:

function*constant<A>(a:A):Generator<A,A,A>{returnyielda}function*countTo(n:number){leti=0while(i<n){consta=yield*constant(i++)console.log(a)}}constiterator=countTo(10)letcurrent=iterator.next()while(!current.done){current=iterator.next(current.value)}

This will print out:

0123456789

and all the types work well, in the signature ofconstant we readGenerator<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.

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 byhttps://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 ofEffect 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 aneffect into agenerator of effect.

import*asTfrom"@effect-ts/core/Effect"import{pipe}from"@effect-ts/core/Function"importtype{_E,_R}from"@effect-ts/core/Utils"exportclassGenEffect<K,A>{constructor(readonlyop:K){}*[Symbol.iterator]():Generator<GenEffect<K,A>,A,any>{returnyieldthis}}constadapter=(_:any)=>{returnnewGenEffect(_)}exportfunctiongen<EffextendsGenEffect<any,any>,AEff>(f:(i:{<R,E,A>(_:T.Effect<R,E,A>):GenEffect<T.Effect<R,E,A>,A>})=>Generator<Eff,AEff,any>):T.Effect<_R<Eff["op"]>,_E<Eff["op"]>,AEff>{returnT.suspend(()=>{constiterator=f(adapterasany)conststate=iterator.next()functionrun(state:IteratorYieldResult<Eff>|IteratorReturnResult<AEff>):T.Effect<any,any,AEff>{if(state.done){returnT.succeed(state.value)}returnT.chain_(state.value["op"],(val)=>{constnext=iterator.next(val)returnrun(next)})}returnrun(state)})}constprogram=gen(function*(_){consta=yield*_(T.succeed(1))constb=yield*_(T.succeed(2))returna+b})pipe(program,T.chain((n)=>T.effectTotal(()=>{console.log(n)})),T.runMain)

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 aneffect to agenerator 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 thegen function can directly deal with:

f: (i: {    <A>(_: Tag<A>): GenEffect<Has<A>, never, A>    <E, A>(_: Option<A>, onNone: () => E): GenEffect<unknown, E, A>    <A>(_: Option<A>): GenEffect<unknown, NoSuchElementException, A>    <E, A>(_: Either<E, A>): GenEffect<unknown, E, A>    <R, E, A>(_: Effect<R, E, A>): GenEffect<R, E, A>    <R, E, A>(_: Managed<R, E, A>): GenEffect<R, E, A>  }) => Generator<Eff, AEff, any>

So you can use it like:

import*asEfrom"@effect-ts/core/Classic/Either"import*asOfrom"@effect-ts/core/Classic/Option"import*asTfrom"@effect-ts/core/Effect"import*asMfrom"@effect-ts/core/Effect/Managed"import{pipe}from"@effect-ts/core/Function"constresult=T.gen(function*(_){consta=yield*_(O.some(1))constb=yield*_(O.some(2))constc=yield*_(E.right(3))constd=yield*_(T.access((_:{n:number})=>_.n))conste=yield*_(M.makeExit_(T.effectTotal(()=>{console.log("open")return5}),()=>T.effectTotal(()=>{console.log("release")})))yield*_(T.effectTotal(()=>{console.log(a+b+c+d+e)}))})pipe(result,T.provideAll({n:4}),T.runMain)

That will produce:

open15release

Multi-Shot Monads

The trick explored so far works well for effects that produce a single value, likeEffect,Managed and anyio-like effect type.

There is a problem with multi-shot effects likeStream orArray, 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 ispure, 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 ofhttps://github.com/mattiamanzati).

This technique has a performance complexity of O(n^2) wheren 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 theStream generator:

importtype{Effect}from"../../Effect"import{fromEither,service}from"../../Effect"import{die}from"../../Effect/die"importtype{Either}from"../../Either"import{NoSuchElementException,PrematureGeneratorExit}from"../../GlobalExceptions"importtype{Has,Tag}from"../../Has"import*asLfrom"../../List"importtype{Option}from"../../Option"importtype{_E,_R}from"../../Utils"import{isEither,isOption,isTag}from"../../Utils"import{chain_}from"./chain"import{Stream}from"./definitions"import{fail}from"./fail"import{fromEffect}from"./fromEffect"import{succeed}from"./succeed"import{suspend}from"./suspend"exportclassGenStream<R,E,A>{readonly_R!:(_R:R)=>voidreadonly_E!:()=>Ereadonly_A!:()=>Aconstructor(readonlyeffect:Stream<R,E,A>){}*[Symbol.iterator]():Generator<GenStream<R,E,A>,A,any>{returnyieldthis}}constadapter=(_:any,__?:any)=>{if(isOption(_)){returnnewGenStream(_._tag==="None"?fail(__?__():newNoSuchElementException()):succeed(_.value))}elseif(isEither(_)){returnnewGenStream(fromEffect(fromEither(()=>_)))}elseif(_instanceofStream){returnnewGenStream(_)}elseif(isTag(_)){returnnewGenStream(fromEffect(service(_)))}returnnewGenStream(fromEffect(_))}exportfunctiongen<RBase,EBase,AEff>():<EffextendsGenStream<RBase,EBase,any>>(f:(i:{<A>(_:Tag<A>):GenStream<Has<A>,never,A><E,A>(_:Option<A>,onNone:()=>E):GenStream<unknown,E,A><A>(_:Option<A>):GenStream<unknown,NoSuchElementException,A><E,A>(_:Either<E,A>):GenStream<unknown,E,A><R,E,A>(_:Effect<R,E,A>):GenStream<R,E,A><R,E,A>(_:Stream<R,E,A>):GenStream<R,E,A>})=>Generator<Eff,AEff,any>)=>Stream<_R<Eff>,_E<Eff>,AEff>exportfunctiongen<EBase,AEff>():<EffextendsGenStream<any,EBase,any>>(f:(i:{<A>(_:Tag<A>):GenStream<Has<A>,never,A><E,A>(_:Option<A>,onNone:()=>E):GenStream<unknown,E,A><A>(_:Option<A>):GenStream<unknown,NoSuchElementException,A><E,A>(_:Either<E,A>):GenStream<unknown,E,A><R,E,A>(_:Effect<R,E,A>):GenStream<R,E,A><R,E,A>(_:Stream<R,E,A>):GenStream<R,E,A>})=>Generator<Eff,AEff,any>)=>Stream<_R<Eff>,_E<Eff>,AEff>exportfunctiongen<AEff>():<EffextendsGenStream<any,any,any>>(f:(i:{<A>(_:Tag<A>):GenStream<Has<A>,never,A><E,A>(_:Option<A>,onNone:()=>E):GenStream<unknown,E,A><A>(_:Option<A>):GenStream<unknown,NoSuchElementException,A><E,A>(_:Either<E,A>):GenStream<unknown,E,A><R,E,A>(_:Effect<R,E,A>):GenStream<R,E,A><R,E,A>(_:Stream<R,E,A>):GenStream<R,E,A>})=>Generator<Eff,AEff,any>)=>Stream<_R<Eff>,_E<Eff>,AEff>exportfunctiongen<EffextendsGenStream<any,any,any>,AEff>(f:(i:{<A>(_:Tag<A>):GenStream<Has<A>,never,A><E,A>(_:Option<A>,onNone:()=>E):GenStream<unknown,E,A><A>(_:Option<A>):GenStream<unknown,NoSuchElementException,A><E,A>(_:Either<E,A>):GenStream<unknown,E,A><R,E,A>(_:Effect<R,E,A>):GenStream<R,E,A><R,E,A>(_:Stream<R,E,A>):GenStream<R,E,A>})=>Generator<Eff,AEff,any>):Stream<_R<Eff>,_E<Eff>,AEff>exportfunctiongen(...args:any[]):any{functiongen_<EffextendsGenStream<any,any,any>,AEff>(f:(i:any)=>Generator<Eff,AEff,any>):Stream<_R<Eff>,_E<Eff>,AEff>{returnsuspend(()=>{functionrun(replayStack:L.List<any>):Stream<any,any,AEff>{constiterator=f(adapterasany)letstate=iterator.next()for(constaofreplayStack){if(state.done){returnfromEffect(die(newPrematureGeneratorExit()))}state=iterator.next(a)}if(state.done){returnsucceed(state.value)}returnchain_(state.value["effect"],(val)=>{returnrun(L.append_(replayStack,val))})}returnrun(L.empty())})}if(args.length===0){return(f:any)=>gen_(f)}returngen_(args[0])}

Fromhttps://github.com/Matechs-Garage/matechs-effect/blob/master/packages/system/src/Stream/Stream/gen.ts

Apart from all the overloadings and the adapter code to support different monadic values the key part is:

suspend(()=>{functionrun(replayStack:L.List<any>):Stream<any,any,AEff>{constiterator=f(adapterasany)letstate=iterator.next()for(constaofreplayStack){if(state.done){returnfromEffect(die(newPrematureGeneratorExit()))}state=iterator.next(a)}if(state.done){returnsucceed(state.value)}returnchain_(state.value["effect"],(val)=>{returnrun(L.append_(replayStack,val))})}returnrun(L.empty())})

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:

import*asEfrom"@effect-ts/core/Classic/Either"import*asOfrom"@effect-ts/core/Classic/Option"import*asTfrom"@effect-ts/core/Effect"import*asSfrom"@effect-ts/core/Effect/Stream"import{pipe}from"@effect-ts/core/Function"constresult=S.gen(function*(_){consta=yield*_(O.some(0))constb=yield*_(E.right(1))constc=yield*_(T.succeed(2))constd=yield*_(S.fromArray([a,b,c]))returnd})pipe(result,S.runCollect,T.chain((res)=>T.effectTotal(()=>{console.log(res)})),T.runMain)

will produce:

[0, 1, 2]

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 namelygenF (to be used in one-shot cases, very efficient) andgenWithHistoryF (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.

import"@effect-ts/core/Operators"import*asArrayfrom"@effect-ts/core/Classic/Array"import*asMapfrom"@effect-ts/core/Classic/Map"import*asTfrom"@effect-ts/core/Effect"import*asLfrom"@effect-ts/core/Effect/Layer"import*asMfrom"@effect-ts/core/Effect/Managed"import*asReffrom"@effect-ts/core/Effect/Ref"importtype{_A}from"@effect-ts/core/Utils"import{tag}from"@effect-ts/system/Has"// make Database LiveexportconstmakeDbLive=M.gen(function*(_){constref=yield*_(Ref.makeRef<Map.Map<string,string>>(Map.empty)["|>"](M.make((ref)=>ref.set(Map.empty))))return{get:(k:string)=>ref.get["|>"](T.map(Map.lookup(k)))["|>"](T.chain(T.getOrFail)),put:(k:string,v:string)=>ref["|>"](Ref.update(Map.insert(k,v)))}})// simulate a database connection to a key-value storeexportinterfaceDbConnectionextends_A<typeofmakeDbLive>{}// Tag<DbConnection>exportconstDbConnection=tag<DbConnection>()// Database Live LayerexportconstDbLive=L.fromManaged(DbConnection)(makeDbLive)// make Broker LiveexportconstmakeBrokerLive=M.gen(function*(_){constref=yield*_(Ref.makeRef<Array.Array<string>>(Array.empty)["|>"](M.make((ref)=>ref.get["|>"](T.chain((messages)=>T.effectTotal(()=>{console.log(`Flush:`)messages.forEach((message)=>{console.log("-"+message)})}))))))return{send:(message:string)=>ref["|>"](Ref.update(Array.snoc(message)))}})// simulate a connection to a message brokerexportinterfaceBrokerConnectionextends_A<typeofmakeBrokerLive>{}// Tag<BrokerConnection>exportconstBrokerConnection=tag<BrokerConnection>()// Broker Live LayerexportconstBrokerLive=L.fromManaged(BrokerConnection)(makeBrokerLive)// Main Live LayerexportconstProgramLive=L.all(DbLive,BrokerLive)// Program Entryexportconstmain=T.gen(function*(_){const{get,put}=yield*_(DbConnection)const{send}=yield*_(BrokerConnection)yield*_(put("ka","a"))yield*_(put("kb","b"))yield*_(put("kc","c"))consta=yield*_(get("ka"))constb=yield*_(get("kb"))constc=yield*_(get("kc"))consts=`${a}-${b}-${c}`yield*_(send(s))returns})// run the program and print the outputmain["|>"](T.provideSomeLayer(ProgramLive))["|>"](T.runMain)