# \[ANN\] heftia-effects: higher-order algebraic effects done right

**URL:** <https://discourse.haskell.org/t/ann-heftia-effects-higher-order-algebraic-effects-done-right/10509>\
**Category:** Announcements\
**Created:** [October 11, 2024, 1:22am UTC](https://discourse.haskell.org/t/ann-heftia-effects-higher-order-algebraic-effects-done-right/10509 "2024-10-11T01:22:40Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![ymdfield](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/ymdfield/32/4609_2.png) [@ymdfield](https://discourse.haskell.org/u/ymdfield)\
**Post date:** [October 11, 2024, 1:22am UTC](https://discourse.haskell.org/t/ann-heftia-effects-higher-order-algebraic-effects-done-right/10509/1 "2024-10-11T01:22:40Z")

</div>

I’m excited to announce `heftia-effects`, a new extensible effects library for Haskell.

> **[GitHub - sayo-hs/heftia: A theory‑backed, ultra type‑safe algebraic...](https://github.com/sayo-hs/heftia)**
>
> A theory‑backed, ultra type‑safe algebraic effects

# Key Features

- **Correct Semantics for Higher-Order Effects & Continuations**

- **Easy and Concise Implementation for Custom Effect Interpreters**

- **Standard and Reasonable Performance**

- **Purity**

If you’re interested, please take a look at the [documentation for usage and semantics](https://hackage.haskell.org/package/heftia-0.4.0.0/docs/Control-Monad-Hefty.html).  
I’d love to hear your thoughts!

There are countless effect system libraries in Haskell, so to be honest, I was unsure whether to announce this library. However, after several updates, I believe that Heftia v0.4 now offers value comparable to other major effect system libraries. The current version is no longer experimental and aims to provide a practical effect system.

# More Details

## Background

Traditional libraries have always struggled with semantic issues in higher-order effects\*1\*2\*3\*4.  
Heftia is based on algebraic effects and provides a simple, consistent, and predictable semantics for all interactions of effects, thereby providing answers to these issues comprehensively.

Effect and its interpreter designers only need to consider the semantics of algebraic effects and do not need to worry about the library’s internal implementation or IO monad-level details\*5.

This significantly simplifies the process of creating custom effects and writing their interpreters.  
Type safety ensures that there is no concern about breaking semantics, allowing users to focus solely on the inherent complexity of their tasks.

## Robustness of Semantics

This library prevents inherently dangerous operations\*6 that could break or obscure semantics through type safety.

This is not something added in an ad-hoc manner through methods like smart constructors but is naturally derived from the straightforward data structure of the `Eff` monad.

The constructors of the `Eff` monad are exposed, and users can manipulate them directly without any safety concerns, yet the semantics remain intact.

## Performance

This library is based on the Freer monad, which is somewhat traditional, rather than using the recent mainstream approaches like evidence passing (ReaderT IO pattern) used by `effectful`, `cleff`, or `bluefin`\*7. It’s not extremely fast, but it’s built on the fast implementation `freer-simple`, resulting in a speed that is positioned roughly in the middle between the high-speed IO-based implementations and relatively slower implementations. In typical usage, you should find the performance satisfactory.

Additionally, by basing on Freer, the semantics of the effect system are separated from the semantics of IO. This means that when interpreting effects, there is no need to consider IO-level details\*5. The consistent semantics of algebraic effects prevent leaky abstraction from the IO level. This is a significant difference from `IO`-fused effect system libraries like [effectful](https://hackage.haskell.org/package/effectful) and [cleff](https://hackage.haskell.org/package/cleff), and it’s one of the reasons why this library is based on Freer rather than on IO.

\*1: [The effect semantics zoo - lexi-lambda/eff](https://github.com/lexi-lambda/eff/blob/master/notes/semantics-zoo.md)  
\*2: [Incorrect semantics for higher-order effects - hasura/eff#12](https://github.com/hasura/eff/issues/12)  
\*3: [Semantics of higher order effects - re-xyr/speff#3](https://github.com/re-xyr/speff/issues/3)  
\*4: [Unresolved challenges of scoped effects](https://www.twitch.tv/videos/1163853841)  
\*5: Examples include “Asynchronous exceptions might be thrown,” “What is the current state of exception masking,” “This state/environment value is local and thus not shared between threads,” and more.  
\*6: For instance, interpreting the coroutine effect while the catch effect is still uninterpreted and interpreting the catch effect afterwards.  
\*7: In particular, Heftia doesn’t use GHC’s delimited continuation primops.

---

<div class="post-metadata">

**Author:** ![lylek](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/lylek/32/2937_2.png) [@lylek](https://discourse.haskell.org/u/lylek)\
**Post date:** [October 12, 2024, 12:37am UTC](https://discourse.haskell.org/t/ann-heftia-effects-higher-order-algebraic-effects-done-right/10509/2 "2024-10-12T00:37:31Z")

</div>

> [@ymdfield](#):
>
> [GitHub - sayo-hs/heftia: higher-order algebraic effects done right for Haskell](https://github.com/sayo-hs/heftia)

Thanks for creating this! You mentioned that it’s inspired by [this paper](https://dl.acm.org/doi/10.1145/3571255).

How does it relate to Nicholas Wu’s work as mentioned in [The Evolution of Effects (Haskell 2023) - ICFP 2023](https://icfp23.sigplan.org/details/haskellsymp-2023/10/The-Evolution-of-Effects)? It seems ICFP has been full of research on algebraic effects lately and I’m trying to see where this fits in.

---

<div class="post-metadata">

**Author:** ![lylek](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/lylek/32/2937_2.png) [@lylek](https://discourse.haskell.org/u/lylek)\
**Post date:** [October 12, 2024, 12:44am UTC](https://discourse.haskell.org/t/ann-heftia-effects-higher-order-algebraic-effects-done-right/10509/3 "2024-10-12T00:44:54Z")

</div>

What’s the reason for avoiding GHC’s delimited continuation primops? Are they necessarily tied to using IO as an underlying mechanism?

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [October 12, 2024, 1:53am UTC](https://discourse.haskell.org/t/ann-heftia-effects-higher-order-algebraic-effects-done-right/10509/4 "2024-10-12T01:53:33Z")

</div>

Actually, the delimited-continuation primitives [proposed for GHC](https://github.com/ghc-proposals/ghc-proposals/blob/master/proposals/0313-delimited-continuation-primops.rst) don’t rely on `IO a` :

```haskell
type PromptTag# (a :: Type)

newPromptTag# 
  :: forall (a :: Type). State# RealWorld
  -> (State# RealWorld, PromptTag a)

prompt#
  :: forall (a :: Type)
   . PromptTag# a
  -> (State# RealWorld -> (# State# RealWorld, a #))
  -> State# RealWorld -> (# State# RealWorld, a #)

control0#
  :: forall (a :: Type) (r :: RuntimeRep) (b :: TYPE r)
   . PromptTag# a
  -> (((State# RealWorld -> (# State# RealWorld, b #))
       -> State# RealWorld -> (# State# RealWorld, a #))
      -> State# RealWorld -> (# State# RealWorld, a #))
  -> State# RealWorld -> (# State# RealWorld, b #)

```

Moreover, the author explicitly warns **against** using them as operations for `IO a` :

- 

> [@](#):
>
> [Proposed Change Specification](https://github.com/ghc-proposals/ghc-proposals/blob/master/proposals/0313-delimited-continuation-primops.rst#id9)
> 
> […] note that I do **not** propose actually providing the `IO` versions anywhere! There is **no** safe way to use these operations in arbitrary `IO` code, for reasons given below.

- 

> [@](#):
>
> [Effect and Interactions](https://github.com/ghc-proposals/ghc-proposals/blob/master/proposals/0313-delimited-continuation-primops.rst#id16)
> 
> As alluded to above, `control0#` is fundamentally dangerous when used with arbitrary `IO` code, as existing programs do not account for the possibility of re-entrant `IO` computations.

…which seems as good a reason as any to avoid their use (assuming there’s been no changes beyond what was originally proposed).

---

<div class="post-metadata">

**Author:** ![lylek](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/lylek/32/2937_2.png) [@lylek](https://discourse.haskell.org/u/lylek)\
**Post date:** [October 12, 2024, 1:55am UTC](https://discourse.haskell.org/t/ann-heftia-effects-higher-order-algebraic-effects-done-right/10509/5 "2024-10-12T01:55:40Z")

</div>

Isn’t `IO` just a type synonym for `State# RealWorld`?

---

<div class="post-metadata">

**Author:** ![ymdfield](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/ymdfield/32/4609_2.png) [@ymdfield](https://discourse.haskell.org/u/ymdfield)\
**Post date:** [October 12, 2024, 2:05am UTC](https://discourse.haskell.org/t/ann-heftia-effects-higher-order-algebraic-effects-done-right/10509/6 "2024-10-12T02:05:16Z")

</div>

I’m sorry if I interrupted the discussion.

> [@lylek](#):
>
> What’s the reason for avoiding GHC’s delimited continuation primops? Are they necessarily tied to using IO as an underlying mechanism?

Essentially, yes. The reason is that [GHC’s delimited continuation primops](https://hackage.haskell.org/package/ghc-prim-0.11.0/docs/GHC-Prim.html#continuations) require the IO monad to execute them. In my design approach, libraries like `fused-effects`, `polysemy`, and `freer-simple` allow using any monad as the base monad. This isolates the semantics from the IO level, preventing users from falling into pitfalls caused by leaky abstractions from the IO layer. Relying on the IO monad would eliminate this property, which is a major concern for me.

Additionally, the situation is somewhat more complex and relates to the actual performance of primops. Benchmark results for the `eff` library, which utilizes primops for optimization, raise questions about the true speed benefits of primops. Specifically, [effects like NonDet and Coroutine exhibit O(n²) level slowness](https://github.com/sayo-hs/heftia/blob/v0.5.0/benchmark/performance.md). However, this may be due to the implementation of `eff` rather than the primops themselves.

During the performance improvement process for Heftia, I first forked a library called `speff` to prototype an [IO-based version of Heftia](https://github.com/ymdryo/speff) (which also does not use primops). While it worked and was very fast in some cases, it couldn’t resolve the [poor performance compatibility with higher-order effects](https://github.com/ymdryo/speff/blob/experiment/hefty/bench-others.svg) (such as the `catch.10000.sp_modified_for_non_scoped_resumption_support` benchmark). Given the issues with `eff`, I didn’t think using primops would help solve this problem, especially since [primops typically offer only about a 2x speedup](http://discourse.haskell.org/t/the-issues-with-effect-systems/5630/2).

Therefore, I changed my approach and optimized based on Freer using `freer-simple`, achieving practical speeds. This demonstrated that not only for semantic reasons but also for performance compatibility, Freer was a better fit. Consequently, Freer was adopted.

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [October 12, 2024, 2:09am UTC](https://discourse.haskell.org/t/ann-heftia-effects-higher-order-algebraic-effects-done-right/10509/7 "2024-10-12T02:09:49Z")

</div>

> [@lylek](#):
>
> Isn’t `IO` just a type synonym for `State# RealWorld`?

No. For GHC, it’s:

> [@](#):
>
> `newtype IO a = IO (State# RealWorld -> (# State# RealWorld, a #))`
> 
> [`IO a` (GHC.Types)](https://hackage.haskell.org/package/ghc-prim-0.11.0/docs/src/GHC.Types.html#IO)

Also see [How to Declare an Imperative](https://ics.uci.edu/~jajones/INF102-S18/readings/24_wadler) for other pedagogical implementations of `IO a`.

---

<div class="post-metadata">

**Author:** ![ymdfield](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/ymdfield/32/4609_2.png) [@ymdfield](https://discourse.haskell.org/u/ymdfield)\
**Post date:** [October 12, 2024, 2:31am UTC](https://discourse.haskell.org/t/ann-heftia-effects-higher-order-algebraic-effects-done-right/10509/8 "2024-10-12T02:31:46Z")

</div>

To be honest, I hadn’t been able to keep up with these developments much, but the primitives are provided under the assumption that programmers understand they are unsafe and will wrap them with invariant-preserving wrappers (such as libraries like `eff`). While `IO` is indeed merely a newtype around `State#`, it is specifically wrapped in a newtype intended to allow users to call it safely without any particular prior knowledge. Therefore, it’s understandable that such safe wrappers are not provided.

It appears that IO versions of `prompt` and `control0` (those without the `#`) have not been provided, consistent with the proposal without any changes.

---

<div class="post-metadata">

**Author:** ![ymdfield](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/ymdfield/32/4609_2.png) [@ymdfield](https://discourse.haskell.org/u/ymdfield)\
**Post date:** [October 12, 2024, 3:41am UTC](https://discourse.haskell.org/t/ann-heftia-effects-higher-order-algebraic-effects-done-right/10509/9 "2024-10-12T03:41:56Z")

</div>

> [@lylek](#):
>
> How does it relate to Nicholas Wu’s work as mentioned in [The Evolution of Effects (Haskell 2023) - ICFP 2023](https://icfp23.sigplan.org/details/haskellsymp-2023/10/The-Evolution-of-Effects)? It seems ICFP has been full of research on algebraic effects lately and I’m trying to see where this fits in.

Are you referring to work around 2015, such as “Effect Handlers in Scope” or “Fusion for Free,” which underpin the `fused-effects` library?

---

<div class="post-metadata">

**Author:** ![lylek](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/lylek/32/2937_2.png) [@lylek](https://discourse.haskell.org/u/lylek)\
**Post date:** [October 12, 2024, 8:03pm UTC](https://discourse.haskell.org/t/ann-heftia-effects-higher-order-algebraic-effects-done-right/10509/10 "2024-10-12T20:03:47Z")

</div>

Yes, “Effect Handlers in Scope”, but also more recent work from 2023: [“A Framework for Higher-Order Effects and Handlers”](https://arxiv.org/abs/2302.01415) (not Wu’s work, but cited) and [“Modular Models of Monoids with Operations”](https://yangzhixuan.github.io/pdf/mmm.pdf).

---

<div class="post-metadata">

**Author:** ![ymdfield](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/ymdfield/32/4609_2.png) [@ymdfield](https://discourse.haskell.org/u/ymdfield)\
**Post date:** [October 13, 2024, 12:45am UTC](https://discourse.haskell.org/t/ann-heftia-effects-higher-order-algebraic-effects-done-right/10509/11 "2024-10-13T00:45:08Z")

</div>

OK. It seems that around 2015, the so-called “higher-order free monad” hadn’t been developed, so the standard first-order free monad was used instead. The approach to higher-order effects differs from Hefty Algebras and the [A Framework for Higher-Order Effects & Handlers (2023)](https://dl.acm.org/doi/10.1016/j.scico.2024.103086), which are based on the higher-order free monad.

Specifically, `fused-effects` cannot encode coroutine effects and is aligned with “functorial state” semantics (similar to [`polysemy`](https://github.com/polysemy-research/polysemy)). In contrast, my library follows the continuation-based lineage of [`freer-simple`](https://github.com/lexi-lambda/freer-simple) and [`eff`](https://github.com/lexi-lambda/eff), resulting in a different approach.

I believe my library is closely aligned with “[A Framework for Higher-Order Effects & Handlers](https://dl.acm.org/doi/10.1016/j.scico.2024.103086),” as the `Eff` monad in my library corresponds to the higher-order free monad defined in that paper (p7). The higher-order functors _K^Par_ for concurrency that appear in the paper (pp. 14-15) can be defined in this library as the exact same GADTs presented in the paper and used as higher-order effects:

```haskell
data KPar rho f a where
    For :: rho (f b) -> (rho b -> a) -> KPar rho f a

```

In this sense, structurally, the framework in this paper is almost equivalent (although the concept of elaboration does not appear in the paper, and only a brief mention of Hefty Algebras is made towards the end).

Regarding “Modular Models of Monoids with Operations,” I have glanced through it, but I’m sorry, it was difficult for me to read due to the extensive use of category theory. The categorical foundation of algebraic effects is currently beyond my understanding.

I hope this is helpful.

---

<div class="post-metadata">

**Author:** ![lylek](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/lylek/32/2937_2.png) [@lylek](https://discourse.haskell.org/u/lylek)\
**Post date:** [October 13, 2024, 5:03am UTC](https://discourse.haskell.org/t/ann-heftia-effects-higher-order-algebraic-effects-done-right/10509/12 "2024-10-13T05:03:58Z")

</div>

That was very helpful, thanks! I was encouraged by Nicholas Wu’s 2023 talk and the work on higher-order effects, and it sounds like your library incorporates the same idea.