A mutable reference *is* a lens

[infinity0]

This is more of a comment for discussion, not a bug report. I was reading the docs and the comment "A MutPart m s a is spiritually similar to a lens" prompted me to write up my thoughts.

A theme I've realised recently is that a reference very literally is a lens, they are one and the same thing. All stateful monads that can be "referenced" into, have a state type parameter; in PrimMonad this is PrimState, for ST s this is s and for IO it is RealWorld. A reference is just an index into part of this overall state.

One advantage is that the user cannot choose s, it is kept either forcibly parametric that the user can't instantiate, or a phantom type like RealWorld that the user cannot instantiate either. This forces stateful code to be compositional - unlike StateT s where a common pattern (and the "obvious intuition") is to instatiate s to something, or place static constraints upon it. Indeed, when dealing with StateT s I've found it useful to not instantiate/constrain s and rather have the user pass in a lens; this avoids nasty issues such as:

• nesting two StateT
• use-cases where you want to store a StateT s action as part of the state itself; attempting to instantiate s will result in lots of "cannot construct infinite type" errors

and using a lens avoids all of these issues. The code you end up with looks very similar to mutable code using references - your have to pass references around, you pass lens around.

In fact, this is not surprising, the typical way to implement a reference within a stateful monad like IO or ST is for the overall state type to be indexable, and for each reference value to carry this index - exactly like a Store comonad which is what a lens is. For every reference, you will be able to write something like (a -> f b) -> (s -> f t) - given a way to mutate the reference, it gives a way to mutate the overall state. In fact this is a great way to encode the reference itself, you do not need a separate "reference" vs a "lens" type.

Instead of defining MutVar, IORef, all of these separate types, one can simply return a lens that acts over RealWorld, etc, perhaps wrapped up in a generic newtype for the user. This sort of pattern also obsoletes MutPart since this can be represented simply by another lens.

[infinity0]

Case in point, here is a direction conversion from STRef s a to Lens' s a. It involves some low-level hacks only because GHC doesn't expose these internals to the end user, but in principle it could be done and it's all type-safe and pure:

{-# LANGUAGE MagicHash #-}
{-# LANGUAGE RankNTypes    #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE UnboxedTuples #-}

module Control.Lens.Mutable where

import Control.Lens.Type  (Lens')
import GHC.ST             (ST(..), STRep(..))
import GHC.STRef          (STRef(..))
import GHC.Base           (State#, readMutVar#, writeMutVar#)

type STLens s a = Lens' (S s) a
data S s = S (State# s) -- hack to lift State#

stRefToLens :: STRef s a -> STLens s a
stRefToLens (STRef var#) f = \(S s1#) ->
  let (# s2#, valr #) = readMutVar# var# s1#
  in fmap (\valw -> S (writeMutVar# var# valw s2#)) (f valr)

stateToST :: (S s -> (a, S s)) -> ST s a
stateToST state = ST $ \s1# -> let (a, S s2#) = state (S s1#) in (# s2#, a #)

stateSTRef :: STRef s a -> (a -> (x, a)) -> ST s x
stateSTRef ref state = stateToST $ stRefToLens ref state

edit: generalised to work with any functor, like a lens can

[mstksg]

Huh! I guess this is "obvious" if you consider s to be a token representing the state, a lens into s is a lens into the state to modify. Everything typechecks too.

To be honest I originally set out to make this generic over things that aren't ST and IO, like maybe some GPU codegen. But i'm not sure if keeping that would be worth it ... but also maybe any useful mutable context should be representable in terms of that s token too. In any case this is definitely really profound and worth exploring deeper -- thanks for bringing it up :) Then all of the "parts" stuff might then would just be simple functions.

[mstksg]

If I "commit" to a lens into s view then it might make #1 easily doable

[infinity0]

Cool! I expanded the above code into a mini-library here, feel free to take ideas or even code from it. For now it just has a few lens for single-value references, it doesn't do your GRef stuff for containers.

[mstksg]

thanks for this again :) I've had a chance to look into this deeper and going into "mutable variables are lenses" as a basis for this library.

the main issue i ran into was that while this covers read (or "freeze") and write (or "copy"), i'm not sure how to account for new (or "thaw"). Creating a new ref while thinking of a ref as an s into a Lens seems to be something that isn't captured in this view, and must be done separately (effectfully "creating" the lens as a separate action). It would be neat if there was a way to bring new/allocate into this view too! Would be interested to hear if you had any thoughts on this matter.

[infinity0]

@mstksg I ran into this as well :) I created a new typeclass called Allocable.

For symmetry I added free to the interface even though I didn't actually have a use for it (since GC exists). However I do note that the lens representation (which is just a function essentially) does not give you enough information to implement free, since the "address" of the reference is hidden away inside the function/closure. So that's why my Allocable is not directly a lens - but it is a subclass of AsLens so you can convert it into a lens whenever you want.

Example instances are here though this is just a toy example in a very experimental repo.

I also did some basic benchmarking that I didn't push yet, but I found this to be ~2x slower than using the reference directly. (In a real program the overall performance hit will likely be smaller than 2x, since your program would be doing stuff other than reading/writing to the reference.) Not great, but not terrible.

BasicBenchmark.hs

{-# LANGUAGE DataKinds, LambdaCase, TypeApplications #-}

{-
cabal new-build --enable-profiling
cabal new-exec --enable-profiling ghc -- -package mutable-lens -threaded -rtsopts -prof -fprof-auto BasicBenchmark.hs && ./BasicBenchmark +RTS -hr
-}

import Control.Lens
import Control.Lens.Mutable
import Data.Primitive.MutVar
import Control.Concurrent
import GHC.Exts
import System.CPUTime
import System.Mem

whileJustM :: (Monad m, Monoid a) => m (Maybe a) -> m a
whileJustM act = go mempty
 where
  go accum = act >>= \case
    Just r  -> go $! accum <> r
    Nothing -> pure accum

iterations = 100000000

test1 :: IO ()
test1 = do
  r <- newMutVar 0
  whileJustM $ do
    v <- readMutVar r
    --threadDelay 1
    writeMutVar r (v + 1)
    if v < iterations
      then pure $ Just ()
      else pure Nothing

test2 :: IO ()
test2 = do
  r <- stToM $ alloc @(S 'OpST RealWorld) @Int @(MutVar RealWorld) 0
  whileJustM $ do
    v <- stToM $ asLens @(S 'OpST RealWorld) @Int @(MutVar RealWorld) r $ \v -> (v, v)
    --threadDelay 1
    stToM $ asLens @(S 'OpST RealWorld) @Int @(MutVar RealWorld) r $ \v -> ((), v + 1)
    if v < iterations
      then pure $ Just ()
      else pure Nothing

time :: String -> IO a -> IO a
time n a = do
  start <- getCPUTime
  putStrLn $ n <> ": start"
  r <- a
  end <- getCPUTime
  putStrLn $ n <> ": time " <> show (end - start)
  pure r

main :: IO ()
main = do
  time "test1" test1
  performGC
  time "test2" test2
  performGC
  time "test1" test1
  performGC
  time "test2" test2