Merge Effect and ST

[garyb]

This is a idea for the future, floated by @natefaubion when we were talking about #30.

ST and Effect have the same implementation, and it should be possible to coerce safely in either direction (at first I thought runST would essentially become unsafePerformEffect when applied to an Effect converted to ST Global, but actually that won't type check). Given that, Effect could just be what is currently ST Global.

This would mean we have fewer cases to deal with in the optimizer, no need to implement two sets of essentially identical instances and functions, and avoid the need to explicitly coerce or lift ST things to work in Effect (useful for STArray, etc.).

With this unified thing, the somewhat obvious name for the type is Effect, but we'd probably want to preserve the Type -> Type version of Effect we currently have so we don't have to perform an Eff-to-Effect-worthy migration again, so we'd need to come up with something else.

Nate also suggested that we'd want to wait until synonyms are preserved in error messages, since we don't want to reveal the underlying type for Effect to newbies unless we need to, which I agree with.

[hdgarrood]

I dislike this for more or less the same reason that I dislike #30, although this one bothers me quite a bit more. My objection to this is that I don’t think it makes a lot of sense unless you’re intimately familiar with how these things are all implemented. Mutable variables are just one of the many things you can do with Effect - why privilege that specific thing over all the others? It seems plausible that there is at least one other effectful concept which makes sense to model in a similar way to ST, but if we implement this, Effect will already be tightly welded to ST (and exclusively ST) so that won’t be an option. Also, what will a beginner who finds type Effect = ST Global in Pursuit think? I think that’s likely to be very misleading, ie imply that Effect is only about mutable variables specifically, rather than as the general type for all synchronous effectful actions.

For me, an API surface that makes sense should really come before implementation concerns; I don’t think this proposal follows that principle.

[natefaubion]

It's not really about mutation per se. It's more that it's tracking the token for observable effects. If IO/Effect is pseudo-semantically RealWorld token passing, then this is parameterizing the effect by the world token for which you can observe the effects. If we have a rank-2 effect here then it's effects can't be observed and it can safely be eliminated. I understand it's rehashing the old Eff a bit, but it's far more limited in scope.

I think there's quite a bit of value in sharing as much as possible and I think there's something semantically that unites them. For example you can't use EffectFns in ST even though it's the one place that would benefit the most from it, and I'm not confident a proposal would be accepted to introduce them (due to complexity concerns or proliferation of types).

[hdgarrood]

Can you give an example of where you might want to make use of this idea outside of what's currently covered by ST? I worry that if we do this then we will spend the next year or so having to explain to people what Effect :: Region -> Type -> Type means, and why they need to replace all of their uses of Effect with Effect Global. I barely ever use ST anyway, and I just can't see this functionality being used anywhere near enough to justify reconfiguring one of the most basic types in the whole ecosystem. To me, a separate set of STFn types and optimizations for them is significantly more appealing.

[garyb]

Not that this was part of the original goal, but actually it could be Eff :: k -> Type -> Type, as then it can work like the original Eff, or be used as type Effect = Eff Global or be type ST r = Eff (r :: Region) 😄.

The point of this is to be able to freely mix Effect and ST code (like, use STArray for a mutable buffer in general, not stuck in a private region). That is possible with liftST, but it would happen "for free" this way.

It seems to me that the cons are:

1. It might be hard to explain to newcomers if they see the underlying Eff (or whatever) type.

vs pros:

1. No need to duplicate FFI implementations for Effect and ST, the looping operations, and the related things like Ref
2. No need to duplicate optimisation code in the compiler
3. Make use of ST-things in Effect without casting/coercion
4. People could use effect rows and such again if they really wanted to

The con seems like even less of a serious concern given one of the conditions of implementing this is that synonyms would appear in error messages, so the only place to see type Effect = Eff Global would be when tracking down the implementation or something.

[hdgarrood]

The point of this is to be able to freely mix Effect and ST code (like, use STArray for a mutable buffer in general, not stuck in a private region). That is possible with liftST, but it would happen "for free" this way.

But surely it won't be possible to do this, or indeed to reap any of the userland benefits of this proposal, without exposing the guts of how Effect and Eff relate to each other? This is why I still think the "confusing API" issue is a serious concern.

I think I might be able to get on board with this if we were to define

data Eff :: k -> Type -> Type
newtype Effect a = Effect (Eff Global a)

and set things up so that the Effect constructor isn't normally visible, i.e. not exported by the Effect module. The optimisation code in the compiler might need to be made smarter so that it works for newtypes too, but that's probably something which would be useful to have anyway. Now that we have Coercible I think having people use coerce to go between Effect and ST isn't too much of a burden.

[garyb]

I guess I just don't see what would be confusing about it, it doesn't seem much different than the likes of type State = StateT Identity, etc. to me.

[hdgarrood]

Ah right yeah, that is a good point.

[hdgarrood]

I guess we ought to make a decision here. I'm still reluctant; I think my problem with this is really that Effect is used quite heavily in basically every single PureScript app, while in my mind ST is, to be frank, mostly a curiosity and an example for showcasing rank-n types. Given this, I don't think the design of Effect should be influenced by what would be handy for users of ST; I don't think we should complicate the API for using mutable variables in Effect so that the same functions can be used in ST without coercions, even if it is in the relatively minor way being proposed here. Just because Effect is so much more important than ST is.

Having type Effect = Effect' Global might not be so bad, but when you are dealing with things which are supposed to work in both Effect and ST, the API necessarily becomes a little more complicated; Ref needs to get an extra type parameter, and the type of Ref.read becomes forall r a. Ref r a -> Effect' r a; at that point, the reader probably does need to get their head around the fact that Effect is now defined as type Effect = Effect' Global.

As for the other pros you mentioned:

• No need to duplicate FFI implementations for Effect and ST, the looping operations, and the related things like Ref
• No need to duplicate optimisation code in the compiler

For me, having these things influence the API design is wrong. These are implementation concerns which I still don't think should be a factor here. I'm sure there are other ways of removing this duplication (e.g. making ST a newtype around Effect and making the compiler optimizations appropriately smart).

• People could use effect rows and such again if they really wanted to

This is arguably a con rather than a pro, I think 😛

[ajnsit]

I just want to say that the migration from Eff to Effect was really painful, and we shouldn't have to go through anything like that again without good reason.

For me, having these things influence the API design is wrong. These are implementation concerns which I still don't think should be a factor here.

Totally agreed.

[srghma]

maybe even (I didnt think too much)

type Effect = ST (global :: Global)

type MyEffect = ST (global :: Global, mutableArray1 :: STMutableArray, mutableArray2 :: STMutableArray)

[garyb]

I listed those pros as like, "bonus things we get if we do this", not reasons to do it, the implementations are already identical.

I like it for the API as conceptually I think it makes sense too - everything you can do in ST is reasonable to do in Effect also. It's just whether it's allowed to happen locally or globally.

[JordanMartinez]

For what it's worth, I think explaining Effect to people should be handled via documentation. People are already choosing a niche language that already has a learning curve. Why should "but learners will get confused" be a reason to not implement something that might otherwise be useful? Isn't this problem better solved by clear tutorials and documentation?

People could use effect rows and such again if they really wanted to

We've already got run for people who want to have that. So, this argument doesn't appeal to me. However, I get that those who want that can now have it again.

making ST a newtype around Effect and making the compiler optimizations appropriately smart

This sounds like a better tradeoff for deduplicating code, merging ST and Effect, and ensuring Effect is still easily understandable by new learners. @garyb Would this approach be a better way to do that?

For example you can't use EffectFns in ST even though it's the one place that would benefit the most from it, and I'm not confident a proposal would be accepted to introduce them (due to complexity concerns or proliferation of types).

Based on Nate's comment above, perhaps this is why making ST a newtype around Effect wouldn't work?

Make use of ST-things in Effect without casting/coercion

If we did not implement this change and used Coercible, what would be the pros/cons of that?

[JordanMartinez]

I like it for the API as conceptually I think it makes sense too - everything you can do in ST is reasonable to do in Effect also. It's just whether it's allowed to happen locally or globally.

Couldn't we also just add API that enables ST in a global context? Or is this the "make ST a newtype around Effect" idea that Harry proposed?

[hdgarrood]

Why should "but learners will get confused" be a reason to not implement something that might otherwise be useful?

I think there's definitely a tradeoff in how general you make things. When you make things really general, the benefit is that you only need to make sense of the function once and you can apply that knowledge in lots of different places. However, when you make things more targeted towards particular use cases, it means that the APIs require less effort to understand, you're able to write documentation which is easier to make sense of (since you can use more concrete examples without being misleading), and I think the APIs are also less likely to behave in surprising ways if they end up being applied in a setting where they don't really make sense.

In this particular case, my opinion is that the difference between Ref.read :: forall r a. Ref r a -> Effect' r a and Ref.read :: forall a. Ref a -> Effect a is small but nontrivial, and not that easy to justify based on how often I think mutable variables are used in Effect versus in ST.

I don't actually think this issue is specific to learners (although it is likely to affect learners more than other people); I think it's potentially an issue for anyone who uses this API. Ergonomics really do matter; it shouldn't just be a case of saying "approach A allows people to do X in more situations than approach B therefore A is better." I should note that this proposal could improve the ergonomics quite significantly for people who are interested in using mutable variables in both Effect and ST, so I guess my objection here is dependent on my impression that people don't use ST very often, which could be wrong!

This sounds like a better tradeoff for deduplicating code, merging ST and Effect, and ensuring Effect is still easily understandable by new learners. @garyb Would this approach be a better way to do that?

Not necessarily: I think the argument in favour of doing this is (more or less) that if we do what's proposed here, we'll end up with less API surface overall, and we won't run into cases where there's some abstraction which is usable only in Effect or only in ST even though it makes sense for both (such as EffectFns). Right now, you have to explicitly coerce to go between Effect and ST, which means that you have to go out of your way to make something which works in both settings, by doing something like the MutableBuffer class in node-buffers.

If we did not implement this change and used Coercible, what would be the pros/cons of that?

I think using Coercible is basically the same as what I am advocating; the central question is "should there be explicit coercions or not".

Couldn't we also just add API that enables ST in a global context?

We have that already; see #26

[hdgarrood]

I'd actually forgotten about MonadST until just now. I kind of feel like MonadST solves all the same problems from the API surface perspective, but it's just not viable right now because it can't be optimized. So maybe we could alternatively solve these problems by providing MonadST operations for the case where people want to use the same code in both Effect and in ST, continuing to have Effect and ST be separate types needing explicit coercions, and instead working on making compiler optimizations smart enough to make MonadST viable?

[natefaubion]

The main issue right now is needing STFn functions, which are provided for Effect, but not ST. Having MonadST does not help with that. It's not totally clear to me how newtyping would solve the STFn problem either. I could see solving magic-do if a particular bind implementation dereferences to the concrete Effect bind implementation (via derive newtype instance), but no instances are involved for Fn saturation/inlining.

[natefaubion]

Note, I'm not saying that to advocate for the approach in this thread. If we want to support parallel implementations of everything, sure, that's fine. All I personally care about is that I can write more efficient ST code when necessary.

[hdgarrood]

Right, I see. To be completely honest I don't love the application of EffectFn as a solution for performance problems, I personally prefer to think of it as an API marshalling helper thing like promise-aff... if I'm coming from just the performance perspective, is it more or less accurate to say that the issue here is, in a sense, that we broke ST inlining with the Eff->Effect change and we haven't yet fixed it?

[natefaubion]

To be completely honest I don't love the application of EffectFn as a solution for performance problems

I'm not sure it's avoidable as long as these are packed behind curried FFI functions. Or at least it would be non-trivial and require a backend specific optimizer that understands the FFI. EffectFn and magic-do is the only reason halogen-vdom is usable. Currying unfortunately has significant overhead in tight loops.

is it more or less accurate to say that the issue here is, in a sense, that we broke ST inlining with the Eff->Effect change and we haven't yet fixed it?

Kind of. AFAIK there were never EffFn equivalents for ST bindings. It is true that you could write them yourself though.

[timjs]

I think @hdgarrood explained the pros and cons quite clearly, but I don't think that the burden on learning that Ref.read :: forall a. Ref Global a -> Effect' Global a and friends when using effects is that big. I think it just informs programmers more by telling them "oh, this is a global effect using global references".

When starting to learn PureScript, you'd be only introduced to global effects. This means that Effect a = Effect' Global a, wich seems ok to me. After that, one could naturally introduce local effects and the tricks used to contain them (higher ranked types).

In contrast, by using MonadST we'd introduce another layer of complexity, which is less easily explainable because you need more concepts and abstractions to grasp it (type classes, possibly fundeps), and you'd ask programmers to choose between "should I write this function for IO, for ST, or should I abstract because library users need both?" Also, you'd need to make MondST know to the compiler.

ST is a strange and quite separate beast that I, as just one example, only found out it existed some years after learning Haskell and knowing about IORefs. I think this separation and the thought "why do I need another way of using references when I can do this in IO" is the reason ST is not used very often. I think merging Effect and ST into one will have positive effects on migrating effectful code from a global region, to a local one, just because you do not need to jump through loops (coercions, embeddings, ...) to make it happen.

[JordanMartinez]

Below is my understanding of the issue. I wish

1. to clarify how Effect and ST are similar and dissimilar
2. to overview the issues that arise by these two types being separate rather than merged/newtyped together
3. to summarize the problems these issues raise, how we could solve them, and the implications of those approaches

Lastly, I'll explore the Eff "bonus" Gary mentioned and present a possible API we could have. I don't know whether the power-to-weight ratio is worth it, but it was fun to think about.

Affected Parties and Their Concerns

The relevant parties identified so far are...

• PureScript developers who need performance AND safety
  • JavaScript sucks but its fast. Can I please replace unsafe/untyped FFI with PureScript without losing performance due to currying?
• PureScript developers who experienced the Eff -> Effect transition
  • The breakage was huge. Can we not do this again?
• New learners who get scared by higher-kinded types
  • ST has this crazy-looking forall a. (forall h. ...) thing! Can you help me understand this?
• Backend maintainers
  • Please don't make my job more burdensome

Similarities and Dissimilarities

First, Effect a and ST a are similar in that they currently have the same implementation: Unit -> a. Each is a computation that has a side-effect.

Second, they are dissimilar in why they exist. In Effect, anything unsafe can happen (e.g. runtime errors, state mutation, etc.). ST h a seems to exist solely for locally-scoped state mutation that is guaranteed by the compiler to never escape its local scope. While runtime errors can still be thrown in ST, one must use an unsafe API to do so (e.g. unsafeIndex 0 []). Effect has throw where ST does not.

Third, both are always in curried forms: (a -> (b -> (c -> d))). While useful for partial application, it's a needless performance hit when all arguments will be applied every time.

Fourth, Effect doesn't incur this performance penalty because it can exist in an uncurried form via compiler support for EffectFn. However, ST does not have such a counterpart (e.g. STFn). If we did support an uncurried version of ST, we would gain two main benefits:

• More type-safe PureScript code could be written to replace untyped/unsafe FFI code without incurring a performance hit (e.g. array manipulations).
• Backend maintainers could have less FFI to maintain, test, and verify as some functions (e.g. sorting an Array) could be written in PureScript.

Other Related Problems Caused by These Types Being Separate

First, each API must be defined twice, so that one can use the API in both an Effect or ST monadic context. For example:

• node-buffer: the ImmutableBuffer API, the Internal module's usingToImmutable, and the MutableBuffer class work together to provide both immutable and mutable buffer APIs that work in both Effect and ST.
• randomInt: it can be run in Effect but not in ST despite having no risk (at least in the case of JavaScript) of throwing a runtime error.
• arrays: while there is an API for mutating arrays in ST, there isn't a corresponding API for Effect. Rather, one must use a combination of Ref and STA.unsafeThaw (e.g. Ref.modify_ (\a -> ST.run (STA.unsafeThaw a >>= \st -> STA.push 1 st)) r)

Second, we need two mutable reference types (i.e. Ref and STRef) rather than one despite both indicating the same thing: a mutable reference.

While the above two problems were lessened with MonadST's liftST, Nate pointed out, "Ideally there wouldn't be a penalty for using MonadST even in a monomorphic setting."

What Problem(s) are we trying to solve?

In sum, there are actually two problems we are trying to solve:

1. Adding an uncurried version of ST via STFn
2. Making it possible to define APIs that uphold these principles:
   • they are defined only once, so that we do not need to maintain two versions that might go out of sync
   • those that work in ST also work in Effect without requiring us to use "hacks" (e.g. MutableBuffer class)
   • those that work only in Effect do not work in ST (e.g. throw)
   • we only need to define a single Ref type

If we're only trying to solve only Problem 1 (i.e uncurried ST), then we can duplicate the EffectFn stuff as STFn. DRY is not always a good principle. Not all duplication is bad. The work for this has already been done and can be easily merged now (see the compiler PR and the ST library PR). We literally duplicate the code and prefix the kind signature with Region ->:

foreign import data EffectFn1 ::           Type -> Type -> Type
foreign import data STFn1     :: Region -> Type -> Type -> Type

foreign import mkEffectFn1    :: forall   a r. (a -> Effect r) -> EffectFn1 a r
foreign import mkSTFn1        :: forall h a r. (a -> ST h   r) -> STFn1 h   a r

foreign import runEffectFn1   :: forall   a r. EffectFn1 a r -> a -> Effect r
foreign import runSTFn1       :: forall h a r. STFn1 h   a r -> a -> ST h   r

If we're trying to solve both Problems 1 and 2, then I believe merging Effect and ST together by making Effect a newtype over ST is the only solution. It would look like this:

foreign import data Region -- kind
foreign import data ST :: Region -> Type -> Type

foreign import data Global :: Region
newtype Effect a = Effect (ST Global a) -- Effect newtype constructor is not exported

We can solve Problem 1 now and decide how we want to solve Problem 2 later. If we choose to solve Problem 2 by merging Effect and ST together, we would still be solving Problem 1 with minimal breaking changes. I personally don't see a reason not to solve Problem 1 now rather than later.

Note: if we did provide STFn, that doesn't mean we would need to update all libraries that could benefit from it (e.g. arrays) to use STFn immediately.

The Eff "Bonus"

As @garyb pointed out above, we could define things differently, so that it re-enables the pre-v0.11.x effect monad, Eff rows a. Importantly, the resulting Eff would still be opt-in like it is now rather than something that is forced on others. Thus, we wouldn't have a massive Eff-to-Effect situation like before, but those who wanted to jump back to Eff still could.

Below is one way this could be done. There's one drawback. Since custom kinds are open and not closed, I can't prevent someone from defining their own function that would break the guarantees below. Perhaps some variant of what I wrote would work:

-- Eff, the base monad
foreign import data Eff :: forall k. k -> Type -> Type

-- ST, which allows intercomposition of locally-scoped references
-- and globally-scoped references
foreign import data Region
foreign import data LocalRegion :: Region
foreign import data GlobalRegion :: Region

type GlobalRegionSymbol = "globalRegion"
type GlobalRegionRow localRegions = (globalRegion :: GlobalRegion | localRegions)

-- ST newtype constructor NOT exported
newtype ST :: Row Region -> Type -> Type
newtype ST regions a = ST (Eff regions a)

-- Effect newtype constructor NOT exported
newtype Effect a = Effect (ST (GlobalRegionRow ()) a)

-- Since `ST` has a Row of Regions, we need a different way of
-- tracking which references are "locally-scoped" and cannot escape
-- their scope and which references are "globally-scoped"
run :: forall a. (forall regions. ST regions a) -> a

-- So, we force the caller to specify the "name" of the scope of the reference
foreign import data Ref :: Symbol -> Region -> Type -> Type

-- maybe call this function, `localRef`?
new :: forall s r a.
    IsSymbol s =>                     -- s is a symbol
    Row.Lacks s r =>                  -- that isn't already in the rows, `r`
    Row.Lacks GlobalRegionSymbol r => -- and it's not the "globalRegion" one either
    Row.Cons s LocalRegion r tail =>  -- so we can add it to our row of local regions
    a ->
    ST (GlobalRegionRow + tail) (Ref s LocalRegion a) -- which are tracked via `ST`

new' :: forall s r a.
    IsSymbol s =>                     -- same as before...
    Row.Lacks s r =>
    Row.Lacks GlobalRegionSymbol r =>
    Row.Cons s LocalRegion r tail =>
    Proxy s ->                        -- but enable user to say what `s` is
    a ->
    ST (GlobalRegionRow + tail) (Ref s LocalRegion a)

{-
  ST.run do
    b1 <- ST.new false
    b2 <- ST.new' @"localBoolean" false -- easier to understand type errors
-}

-- maybe call this function, `globalRef`?
newG :: forall a.
    a ->
    Effect (Ref "globalRegion" GlobalRegion a)

-- Finally, we make it possible to run `ST` in `Effect`

liftST :: forall a.
  (forall localRegions.
    -- maybe a constraint here that says all `Region`s in `localRegions`
    -- are the `LocalRegion` region and nothing else?
    ST (GlobalRegionRow + localRegions) a
  ) ~> Effect

[garyb]

I'll come back to this with my own summary soon, what you have here is close, but not quite right I think.

[garyb]

I think part of the problem with this discussion so far is it mixes ergonomic concerns and implementation concerns and switches back and forth between them. My primary motivation for this was the ergonomics.

Ergonomics

• ST is a strict subset of Effect
• Everything you can do in ST is also useful to be able to do in Effect

We currently have the MonadST class and Global region to make it possible to use "ST interfaces" in Effect by using liftST on every operation.

We could start implementing all ST interfaces with a MonadST-constrained type rather than specialising to ST if we wanted to make them as pleasant as possible to use from both ST and Effect.

MonadST implementation drawbacks

Error messages will get worse in some situations, as missing instance errors are always less pleasant than concrete type errors.

If we MonadST-constrain the interfaces rather than using liftST everywhere, then everyone has to pay the typeclass overhead.

Effect and ST implementation

The foreign implementation for both types is identical. ST only differs from Effect in how it is treated in the type system - by having the extra type parameter, and operations for it defined in such a way that they will not violate referential transparency.

Right now, if every Effect type was replaced with ST Global, PureScript programs would continue to behave in the same manner (excluding edge cases that might be depending on magic-do optimisation or something like that).

Merged ST and Effect benefits

For the examples here, assume:

foreign import data Eff :: Region -> Type -> Type
type ST = Eff
type Effect = Eff Global

Ergonomic benefit

MonadST and liftST become redundant. Operations that are valid for use in both ST and Effect would be defined with a polymorphic type for the region, exactly the way they are defined for ST currently. For example:

peek :: forall h a. Int -> STArray h a -> Eff h (Maybe a)

Operations that are not valid for use in ST would be defined with Effect (the Global region in Effect = Eff Global indicating they cannot be constrained to a local context).

Implementation benefits

No MonadST overhead for anyone, since it wouldn't be necessary, per previous point.

No need to implement Ref twice and maintain two libraries (admittedly very small overhead since they're basically "done").

The compiler's Effect optimisation all apply to ST too, and we wouldn't need separate code paths to support both. Similarly, EffectFn could be updated to EffFn h and usable for both Effect and ST scenarios.

Drawbacks

Some types that used to have an Effect type present will now read as Eff h in the code, API docs, and error messages.

The error message part of this could be partially mitigated if we were better with synonyms in the compiler - any uses of Effect could be preserved rather than desugaring to Eff Global in the error message.

This seems to be where Harry and I have a difference of opinion, because he views the connection between ST and Effect as an implementation detail, and is concerned about exposing people to the fact the type can be used for both local and global effects when most effect usage is global. In my view the current situation is introducing unnecessary indirection between two things that are very closely related.

---

I'm not even going to get into my Eff :: k -> Type -> Type suggestion, as although it's theoretically a thing, I don't think it's actually going to used for real 😄.

randomInt can't be ST - it's not because of a runtime error risk, it's because it would violate referential transparency.

[mikesol]

Would a good compromise here be doing newtype ST r a = ST (Effect a). Are there any drawbacks to that?

[garyb]

Yeah, it's the wrong way around 😉 - Effect is a superset of ST.