Pre-GHC-Proposal: Instantiate backpack signatures when importing

jaror · June 28, 2023, 7:30pm

Instantiate backpack signatures when importing

opened 07:20PM - 28 Jun 23 UTC

Backpack is not used much. I think there are two main reasons for this which we …can address with a GHC proposal: 1. Backpack is not supported by Stack 2. Backpack is often not at hand I think both these points can be addressed by integrating Backpack more tightly into the language. In particular, I'd propose we allow instantiating Backpack signatures when importing modules. The syntax could look like this: ```haskell -- A.hsig signature A where foo :: String -- B.hs module B where import A someFun = putStrLn foo -- Hello.hs module Hello where foo = "Hello, World!" -- Goodbye.hs module Goodbye where foo = "Goodbye, World!" -- Main.hs import qualified Hello import qualified Goodbye import qualified B as BHello where A = Hello import qualified B as BGoodbye where A = Goodbye main = do BHello.someFun BGoodbye.someFun ``` As you might expect, this program would print: ``` Hello, World! Goodbye, World! ``` Notes: 1. Signature dependencies propagate transitively. The only requirement is that they are eventually instantiated. _E.g. in the example above you could create a module `C` that imports `B` without instantiating `A`, as long as the module that imports `C` does instantiate `A` (or if there is again another module above `C` that instantiates `A`)._ 2. Concrete modules need to be imported before they can be used to instantiate signatures. _E.g. `import qualified Hello` and `import qualified Goodbye` in the example above._ 3. Signatures can be instantiated by other signatures, as long as those are eventually instantiated too. _E.g. we could create a new signature `C.hsig` and write `import qualified B as BC where A = C` as long as `C` is then eventually instantiated too._ 4. Multiple signatures can be instantiated in one `import ... where ...` block. _E.g. `import W where X = Foo; Y = Bar; Z = Baz` or over multiple lines following the layout rules._ 5. Signatures can be instantiated by modules which provide more than what the signature require or even by modules that provide less than what the signature requires if only a subset of the signature is used. This follows the standard Backpack instantiation mechanism. 6. The `where ...` part must always be at the end of the `import ...` line. This is intended to make it easier to parse. These changes are meant to make it easier for Stack to support a minimally usable version of Backpack, because under this proposal GHC can handle most of the instantiation on its own (as long as the proper modules and signatures are supplied). Furthermore, this makes Backpack much more at hand. Using a signature becomes as simple as writing a `.hsig` file, importing that in a module, and instantiating that module when it is imported. No more messing around with local libraries in cabal files or mixins.

Bodigrim · June 28, 2023, 8:15pm

Usually the main reason that something is not used is that something is not useful. What’s the purpose of Backpack? Clearly its original destiny to solve the String problem flopped.

jaror · June 28, 2023, 8:17pm

My reason for thinking about it again is this issue:

If Backpack was more mature, then the duplication between IntMap and Word64Map would not really be an issue at all.

Bodigrim · June 28, 2023, 8:19pm

CPP is good enough for such things, look how filepath (or tests of bytestring) avoids duplication.

Ambrose · June 28, 2023, 8:19pm

Exactly! The UX around Backpack isn’t great and that’s why it has remained niche & unused. I think to say anything more (like that Backpack’s fundamental goals and capabilities are now proven to not be useful) is a bit much given the UX situation.

One usage of backpack that we could really use in the ecosystem is unboxed containers. They exist with Backpack but the way you use them is ugly and a pain.

Basically, I like this proposal in theory because it makes Backpack more of a first-class citizen.

jaror · June 28, 2023, 8:40pm

It’s possible to make it work with CPP, but do you really think CPP is a better way to solve these kinds of issues than to use Backpack (if Backpack were more mature)?

Bodigrim · June 28, 2023, 9:13pm

Yes, I do. This kind of issues is precisely what macros are for. No need to invent an arcane technology for something that works out of the box for half a century.

jaror · June 28, 2023, 9:30pm

Aren’t the flaws of CPP obvious, e.g. these from http://blog.haskell-exists.com/yuras/posts/stop-abusing-cpp-in-haskell.html:

CPP is a C preprocessor, but it is common to use it in Haskell. That leads to a number of issues.

It can mess with haskell code.

CPP doesn’t understand Haskell code, instead it assumes C code. It is free to remove insignificant (for C, not for Haskell) whitespace, expand macros in Haskell comments and strings or mess with identifiers that contain ' or #.

It leads to unnecessary recompilation.

Every time you change your .cabal file, e.g. add new module, or update dependencies, cabal regenerates cabal-macros.h file. Then the recompilation checker pessimistically decides to recompile all modules with CPP enabled.

It makes automatic code analyzing and transforming harder.

If you use hlint or HaRe, then you probably know what I mean.

And I’d like to add that CPP is not typed (not even always syntactically sound) and the error messages will often become hard to understand because they are about the resulting file after macro expansion, not about the source file that you write (at best the source locations might be shifted to their proper place). Edit: add broken Haddock source links to the list.

I understand wanting to avoid complexity, but the problems do pile up after half a century.

Also, ML-style modules are also around 40 years old by now, so the ideas behind Backpack are not particularly new.

Bodigrim · June 28, 2023, 9:46pm

shrug There is a simple working solution for your use case in containers, attested in other boot libraries. But if you prefer to wait 5+ years until containers drop support of all existing versions of GHC to be able to rely on improved Backpack, you are free to do so indeed.

I bet that Backpack error messages are way harder to understand

romes · June 28, 2023, 9:52pm

I use backpack extensively in my game engine.
I wanted to implement a “small” core of the engine (in the style of GHC.Core) that would be abstract in the renderer implementation.

I thought a long while about it and tried going multiple different paths before I realized what I really needed was backpack.

The “core engine” is then defined in terms of abstract renderer interfaces which define loads of rendering-specific abstract datatypes (say DescriptorSet, GraphicsPipeline) and many more functions on them.
Then, I have a vulkan implementation of these abstract interfaces.
Finally, the “big, batteries-included, engine” instances the Core signatures with vulkan implementation and it all works great (except for up until it actually does: HLS, cabal, ghc bugs…) — but when it’s finally working it’s going really great.

Despite trying, it was completely impractical, not to mention less performant (compile and likely runtime wise), to have a MonadRenderer. It would have to define too many type families, way too many functions, and then all calls to these functions on “Core” would have to wrap the monad type parameter (DescriptorSet m, GraphicsPipeline m, etc etc)

Etc etc etc, I have a lot to say about what it bought me in terms of abstraction and extensibility (and potential for “””easily”””swapping the renderer implementation), but I’ll wait until I have a good enough version 0.1

Anyway!

Bodigrim · June 28, 2023, 11:05pm

The unique selling point of Backpack is that potential instantiations are unlimited, “open world”. Practically however one is more likely to deal with a finite set of possibilities, such as String, PosixString and WindowsString in filepath; IntSet, Int64Set, WordSet and Word64Set in containers; or a fairly limited list of rendering engines. If CPP feels too low level, Cabal flags switching between packages and mixins can work better on large scale.

Ambrose · June 29, 2023, 12:23am

unboxed containers are a perfect “open world” example actually - arbitrary users want their arbitrary record UNPACKed in a container type instead of being boxed

simonpj · June 29, 2023, 7:21am

I am convinced that Backpack addresses an important problem. I think the primary reason it has remained “niche and unused” is that Backpack lacks a champion: a person (or preferably several) who is excited to get into the details, fix the UX, write blogs and documentation, and generally knock down the barriers to entry.

Maybe someone reading this thread feels motivated to step up to that challenge?

Simon

danidiaz · June 29, 2023, 6:19pm

I bet that Backpack error messages are way harder to understand

I was curious, so I took this example and introduced some errors to see what they looked like.

Leaving the Str module signature unfilled here:

mixins:
...
lesson2-signatures (Lesson2 as Lesson2.Text)

The error:

    Non-library component has unfilled requirements: Str
    In the stanza 'executable lesson2'
    In the inplace package 'lesson2-signatures-1.0.0.0'

Giving an implementation type here a kind different to what the module signature specifies:

type Str = Maybe

splitOn :: Char -> Maybe () -> Maybe ()
splitOn c = undefined

The error:

    • Type constructor ‘Str’ has conflicting definitions in the module
      and its hsig file
      Main module: type Str :: * -> *
                   type Str = GHC.Maybe.Maybe :: * -> *
      Hsig file:  type Str :: *
                  data Str
      The types have different kinds
    • while checking that lesson2-signatures-1.0.0.0:impl-text:Str.Text implements signature Str in lesson2-signatures-1.0.0.0[Str=lesson2-signatures-1.0.0.0:impl-text:Str.Text]

Removing the function splitOn from the implementation module here so that it can’t correctly instantiate the module signature.

The error:

lib/Str.hsig:1:1: error:
    • ‘splitOn’ is exported by the hsig file, but not exported by the implementing module ‘lesson2-signatures-1.0.0.0:impl-text:Str.Text’
    • while checking that lesson2-signatures-1.0.0.0:impl-text:Str.Text implements signature Str in lesson2-signatures-1.0.0.0[Str=lesson2-signatures-1.0.0.0:impl-text:Str.Text]
  |
1 | signature Str where

jaror · June 29, 2023, 6:34pm

Those first two are pretty good error messages. ~~The last one could use some improvement.~~ Edit: I didn’t read correctly that you actually deleted the whole function. In that case the last message also seems to be accurate.

hasufell · June 30, 2023, 4:28am

I think it would be interesting if someone actually were to rewrite that CPP code of filepath/bytestring etc. with backpack and demonstrate that it’s nicer and easier to maintain.

The other argument that comes up frequently is a common API for containers without the overhead of typeclasses.

I think @ChShersh has blogged about it here: Picnic: put containers into a backpack :: Kowainik

I still find most of the examples not too convincing. Maybe I Iack imagination?

chrisdone · June 30, 2023, 6:18am

If we’re spitballing alternative methods of achieving backpack…

You could possibly also use convenience internal libraries, make them share the same source module that you want to have multiple implementations, but each import their parameter (types, implementations) from a module in isolated source directories. To instantiate them you’d use PackageImports. No CPP required (although could be used).

That would serve the local project case, but wouldn’t serve the open world case that backpack does.

santiweight · June 30, 2023, 12:23pm

At my previous job on a smaller codebase with a performance-constrained simulator, we wanted to use backpack.

The reason we didn’t is because HLS wouldn’t work well with backpack, and we relied on HLS to be productive.

Beyond that we were also concerned about sharp edges that might bite us. In the end we chose dependency injection via passing records (which has a runtime overhead ofc).

Bodigrim · June 30, 2023, 12:27pm

Arguably GHC could have specialised polymorphic types to reap benefits of unpacked strict fields automatically.

Have you seen any comprehensive benchmarks for Backpack-ed containers? Tree-like structures eat a ton of extra memory anyways, so memory savings from unboxing keys are unlikely to be significant. The real benefit could come from instance Ord key inlined and operating on unboxed Int#, but you get the same with IntMap (if you keys are small enough) or HashMap (if your keys are larger).

Ambrose · June 30, 2023, 1:54pm

What about GC pause gains? It seems to me it would cut the amount of scanning the GC does for live containers. For most workloads and use-cases, it’s probably not interesting. But I suspect it can make a difference for large containers that are dynamic (cannot use compact) + have actual tight latency budgets (e.g. not your average Haskell production web app).