heinrichapfelmus / operational Goto Github PK

pattern RETURN :: a -> Program instr a
pattern RETURN x <- (view -> Return x)

pattern BIND :: instr a -> (a -> Program instr b) -> Program instr b
pattern BIND x k <- (view -> x :>>= k)

Bikeshed names.

• Thanks for merging #26
• It would be great to have a hackage release to unblock hls use of this package
• Thanks in advance @HeinrichApfelmus!

Is it possible to make instances of MonadTransControl or MonadBaseControl from Control.Monad.Trans.Control in monad-control? Not that I think you should have this package as a dependency, I just want the instances.

In PR #15, I've added a function that makes it possible to map over the instruction type that ProgramT is parameterized over.

The problem seems to be just in:
doc/examples/TicTacToe.hs

Where there is a conflict with Data.list.singleton, which I fixed by just doing:

import Data.List hiding (singleton)

May I suggest the addition of the following function?

evalRandTIO :: Monad m => RandT StdGen m a -> IO (m a)
evalRandTIO p = evalRandT p `fmap` newStdGen

I wrote this the other day:

interpretWithMonadT :: forall instr m b. Monad m
  => (forall a. instr a -> m a) -> ProgramT instr m b -> m b
interpretWithMonadT f = eval <=< viewT
  where
  eval :: forall a. ProgramViewT instr m a -> m a
  eval (Return a) = return a
  eval (m :>>= k) = f m >>= interpretWithMonadT f . k

If it's something you would want in operational, I'd be happy to put up a PR.

operational will need code changes:

Building library for operational-0.2.4.1..
[1 of 1] Compiling Control.Monad.Operational ( src/Control/Monad/Operational.hs, dist/build/Control/Monad/Operational.o, dist/build/Control/Monad/Operational.dyn_o )

src/Control/Monad/Operational.hs:213:14: error:
    • Variable not in scope:
        liftM :: (a -> b) -> ProgramT instr m a -> ProgramT instr m b
    • Perhaps you meant ‘lift’ (imported from Control.Monad.Trans)
    |
213 |     fmap   = liftM
    |              ^^^^^

src/Control/Monad/Operational.hs:217:14: error:
    • Variable not in scope:
        ap
          :: ProgramT instr m (a -> b)
             -> ProgramT instr m a -> ProgramT instr m b
    • Perhaps you meant ‘map’ (imported from Prelude)
    |
217 |     (<*>)  = ap
    |              ^^

src/Control/Monad/Operational.hs:243:13: error:
    • Variable not in scope:
        ap
          :: ProgramViewT instr m (a -> b)
             -> ProgramViewT instr m a -> ProgramViewT instr m b
    • Perhaps you meant ‘map’ (imported from Prelude)
    |
243 |     (<*>) = ap
    |             ^^

src/Control/Monad/Operational.hs:248:54: error:
    • Variable not in scope:
        (>=>)
          :: (b1 -> ProgramT instr m a)
             -> (a -> ProgramT instr m b) -> b1 -> ProgramT instr m b
    • Perhaps you meant one of these:
        ‘>>=’ (imported from Prelude), ‘>>’ (imported from Prelude),
        ‘>=’ (imported from Prelude)
    |
248 |     (instr :>>= cont1) >>= cont2 = instr :>>= (cont1 >=> unviewT . cont2)
    |                                                      ^^^

As per our discussion on reddit I'm just going to start reading through the documentation, and write down here what's crossing my mind as I do so. Unfortunately I've started to gain a little bit of intuition, but I'll try to act as I did when I saw it the first few times. (I'm not normally thinking verbose thoughts like this to myself, this is just an attempt to transcribe those quick feelings and impressions a person gets while reading into sentences.)

So I saw this package scrolling by in Google Reader and it looked interesting, I opened it in a tab along with a few other things, and now I'm looking at it to see what I can find...

(It might be helpful to open http://hackage.haskell.org/package/operational and follow along there with what I'm reading)

Tiny library for implementing monads by specifying the primitive instructions and their operational semantics. The monad laws will hold automatically. Can also be used to define monad transformers, and the lifting laws are, again, automatic.

Hmm, okay. Sounds interesting. Let's keep going.

Accompanies the article: "The Operational Monad Tutorial", published in Issue 15 of The Monad.Reader http://themonadreader.wordpress.com/2010/01/26/issue-15/.

Okay, that's good to know. Might be worth reading later on...

Related packages: MonadPrompt http://hackage.haskell.org/package/MonadPrompt.

Wow, very gentlemanlike!

Modules
Control
Monad
Control.Monad.Operational

Hmm, looks like there's only one module, so it's hopefully not too complicated... let's look at it.

click

Control.Monad.Operational
Implement monads by specifying primitive instructions and their operational semantics.

Okay...

This package is based on the "The Operational Monad Tutorial", published in Issue 15 of The Monad.Reader http://themonadreader.wordpress.com/.

Right, good to know there's a tutorial. Maybe it'll be worth reading if this looks like something I want to use, but wind up getting stuck somewhere along the way

You are reading the API reference. For more thorough documentation including design and implementation notes as well as a correctness proof, please consult the included documentation in doc/Documentation.md, also available at http://heinrichapfelmus.github.com/operational/Documentation.html .

Hmm, okay. If things get serious this might be worth returning to.

[As a side note, I commend you for providing links. It's really annoying to have to download a package and extract it to get to some file that's not available from the Hackage page.]

This API reference includes only basic example code. More intricate examples are available in the doc/examples directory, also available at https://github.com/HeinrichApfelmus/operational/tree/master/doc/examples#readme.

Hmm, alright. Let's keep reading...

type Program instr = ProgramT instr Identity

I wonder how ProgramT, instr, and Identity interact in that definition... strong urge to jump over to ProgramT to figure out what that is, so that I can figure out what this is, but let's at least read the description first...

The abstract data type 'Program instr a' represents programs.

...hmm. what are programs? I mean I know what programs are, but how does this thing relate to it...?

[Looked at another way, "the type Program represents programs" doesn't have a lot of informational value.]

The type constructor instr :: * -> * indexes the primitive instructions.

O... kay. Hmm. Yeah, there's that 'instr' thing I've seen a few times by now which I'm not too sure about.. so it indexes the primitive instructions? What does indexing mean? What are primitive instructions? Indexing sounds like one of those very precise-meaninged academic words with a different meaning from when normal people use it... I dunno what that is. "Primitive instructions" seems like something that would be a good starting point to get a handle on things but I don't know what those are either... anyway, keep reading...

a is the return type of a program.
Program instr is always a monad and automatically obeys the monad laws.

Okay.

singleton :: instr a -> ProgramT instr m a
Program made from a single primitive instruction.

There's that primitive instruction thing again, wish I knew what it was...

type ProgramView instr = ProgramViewT instr Identity
View type for inspecting the first instruction. It has two constructors Return and :>>=. (For technical reasons, they are documented at ProgramViewT.)

Huh, guess I'll have to look at that then.

click

data ProgramViewT instr m a where
View type for inspecting the first instruction.

Okay, hmm.. wait, why do I need a view type? How does it relate to the other thing? Apparently instructions can be inspected, but why only the first one? What do I do once I've inspected it?

Return :: a -> ProgramViewT instr m a
:>>= :: instr b -> (b -> ProgramT instr m a) -> ProgramViewT instr m a

Huh. ...it would take a while to digest that and I'd like to get a general idea of this whole thing first before trying to, so let's keep looking...

...at this point a bit of feeling lost and not knowing what to look at, seems there are basically similar things in this section as the other one...

...scrolling around...

hmm, 'view' seems like the major thing I haven't looked at yet...

view :: Program instr a -> ProgramView instr a

So I can get a ProgramView from a Program, okay, that's good to know, makes things a bit clearer. Still not sure why I would want or need to, but let's keep reading...

View function for inspecting the first instruction.

Okay, not much new... moving on...

Example usage
Stack machine from "The Operational Monad Tutorial".

Hmm, I remember learning about stack machines at a class in university once, but that was years ago and the memories are hazy... I also remember having read somewhere that the .NET and JVM virtual machines are stack-based as opposed to ones like Parrot which are register-based but irrelevant thought, go away.

data StackInstruction a where
Push :: Int -> StackInstruction ()
Pop :: StackInstruction Int

type StackProgram a = Program StackInstruction a

interpret :: StackProgram a -> (Stack Int -> a)
interpret = eval . view
where
eval :: ProgramView StackInstruction a -> (Stack Int -> a)
eval (Push a :>>= is) stack = interpret (is ()) (a:stack)
eval (Pop :>>= is) (a:stack) = interpret (is a ) stack
eval (Return a) stack = a

That's quite a mouthful, hmm, let's quickly skip to see what's after it...

Note that since ProgramView is a GADT, the type annotation for eval is mandatory.

Well okay, let's go back to the example then.

[...]

At this point I stare at the example for a while and try to figure out what it is and what it's doing, but it's not immediately obvious and I don't have a lot of context and after a while of looking back and forth, I fail. There seems to be some kind of intricate interplay between interpret, view, and eval, but it's not clear what the reason for that is or what it's trying to achieve. There seems to be a 'Stack' type that's not defined anywhere.

ADD kicks in, and I go back to the other tabs I opened.

Again, most of this are things that, when reading it back, make even me want to shout at myself, "use your brain you stupid lazy idiot! why don't you put in a little effort!". But if I'm someone who doesn't already know what this is, and isn't definitely sure that it's something I want to use, then the amount of effort I'm going to be willing to expend to figure it out isn't going to be limitless.

Dear Heinrich,

When I run the example (version 0.2.1.2) I get:

/home/henry/haskell/operational/doc/examples/PoorMansConcurrency.hs:49:40:
Could not deduce (m1 ~ m)
from the context (Monad m)
bound by the type signature for
runProcess :: Monad m => Process m a -> m ()
at /home/henry/haskell/operational/doc/examples/PoorMansConcurrency.hs:(42,1)-(52,37)
or from (Monad m1)
bound by the type signature for
run :: Monad m1 =>
ProgramView (ProcessI m1) a1 -> [Process m1 a1] -> m1 ()
at /home/henry/haskell/operational/doc/examples/PoorMansConcurrency.hs:(47,5)-(52,37)
m1' is a rigid type variable bound by the type signature for run :: Monad m1 => ProgramView (ProcessI m1) a1 -> [Process m1 a1] -> m1 () at /home/henry/haskell/operational/doc/examples/PoorMansConcurrency.hs:47:5 m' is a rigid type variable bound by
the type signature for runProcess :: Monad m => Process m a -> m ()
at /home/henry/haskell/operational/doc/examples/PoorMansConcurrency.hs:42:1
Expected type: [Program (ProcessI m1) a1]
Actual type: [Process m a]
In the first argument of (++)', namelyxs'
In the first argument of schedule', namely(xs ++ [k a])'
Failed, modules loaded: Control.Monad.Operational.

This goes away when I supply a type signature to schedule as follows:

schedule :: Monad m => [Program (ProcessI m) m1] -> m ()

Best wishes,
Henry Laxen

I just published the first version of my operational-class package, which introduces a MonadProgram typeclass similar to the MonadFree typeclass, and makes integrating operational into any monad transformer stack nicer to work with.

Would this be something you'd like to have directly in your package?

[1 of 1] Compiling Control.Monad.Operational ( src/Control/Monad/Operational.hs, /codetmp/oper/operational-0.2.4.0/.dist-newstyle-trustee/aa6ee86615bf83600e1a9cc59f3dab339d9b62d6eacba769f14a98fa1bfef1944c916e7d0697650e9fa9296f78441ac1098d8bdc832acfacbda4516e021f32e3/build/x86_64-linux/ghc-7.8.4/operational-0.2.4.0/noopt/build/Control/Monad/Operational.o )


src/Control/Monad/Operational.hs:215:21:
    Not in scope: type constructor or class ‘Applicative’

src/Control/Monad/Operational.hs:241:21:
    Not in scope: type constructor or class ‘Applicative’
cabal: Failed to build operational-0.2.4.0 (which is required by
exe:operational-TicTacToe from operational-0.2.4.0).

I made a revision to disallow old base: https://hackage.haskell.org/package/operational-0.2.4.0/revisions/

I would like to write lifting instances for ProgramT of other monad type classes, but cannot do so because I don't have access to the constructor. One such example is the Zoom typeclass from Control.Lens.Zoom.

For now, I am just reproducing the source code with the constructors exported, but it would be nice to have that in the future.

If the cleanliness of the interface is an issue, perhaps a separate Control.Monad.Operational.Internal module?

You could easily add a generalisation of interpretWithMonad to the transformer case:

interpretWithMonadT :: (forall x . instr x -> m x) -> ProgramT instr m a -> m a
interpretWithMonadT interpreter = go
  where
    go program = do
      firstInstruction <- viewT program
      case firstInstruction of
        Return a -> return a
        instruction :>>= continuation -> interpreter instruction >>= (go . continuation)

The .cabal file contains

Executable operational-TicTacToe
    if flag(buildExamples)
        build-depends:  random == 1.*
        cpp-options: -DbuildExamples
    else
        buildable: False
    main-is:            doc/examples/TicTacToe.hs
    hs-source-dirs:     src, .
    other-modules:      Control.Monad.Operational

However, this fails to compile (with more recent cabals) since the dependency on mtl and base are missing (they are not inherited from the library's section).

Also it seems strange that the library section declares extensions, which the executable doesn't, even though it compiles Control.Monad.Operational directly. Also, cpp-options: -DbuildExamples seems to have no purpose, as there doesn't appear to be any CPP conditional being affected by that. Also there's a modern idiom for building executables which use the package's library by simply build-depending on the package...

EDIT: long story short, I made a PR (#21) to demonstrate what I mean :-)

EDIT2: Turns out this is actually a bug in cabal's legacy cabal spec version support (haskell/cabal#4121) - but it may make sense to update the .cabal file nevertheless

https://github.com/HeinrichApfelmus/operational/tree/master/doc/examples#readme has broken links to the examples.

As recently pointed out by Oleg Kiselyov and Hiromi Ishii (http://okmij.org/ftp/Haskell/extensible/more.pdf) your GADTs are not actually GADTs but rather (only) existentially quantified data types in GADT notation. Your comments about certain example functions requiring type signatures are therefore wrong: these signatures are not needed (I verified this with ghc-7.10.3). The comments and examples in the code should be fixed accordingly.