Is there such a thing as a lazy monadic list?
Hi all, I'm currently trying to write a very simple VM in order to learn and stretch my Haskell. I'm currently up against a problem. I'm using an (IOUArray Int Word32) to represent the memory of a VM instance. This is all fine so far, but now I'm trying to write a 'disassemble' function that will disassemble an instruction starting from a given location in memory. Ideally I could write a function that would lazily yield successive elements from memory, sort of like this:
readVMFrom :: VM -> Address -> IO [Word32] readVMFrom v f = do i <- readArray (memory v) f rest <- readVMFrom v (succ f) return $ i : readVMFrom v (succ f)
Of course, this isn't lazy, and so happily runs off the end of memory each time. (I could stop that, but that's not the point!) I'm not sure how to lazily construct a list in IO. My next thought is to instead make a function to return an action that yields successive values of memory, given some start, i.e. something like:
readVMFrom :: VM -> Address -> IO Word32
.. but I'm thinking I might have to do some StateT nonsense in order to actually keep track of which index we want to read next. (subtext: I don't know how to do that!) So I then think that perhaps I can do this by having readVMFrom return an action which yields a) the next value, b) the address of the next value (so we know how much we ate), and c) an action to yield the next value and action and so on, so on. I managed that this way (WARNING, BEGINNER HASKELL CODE FOLLOWS):
newtype RVFResult = RVFResult { getRVFResult :: (Word32, Address, IO RVFResult) }
readVMFrom :: VM -> Address -> IO RVFResult readVMFrom v f = do i <- readArray (memory v) f return $ RVFResult (i, succ f, readVMFrom v $ succ f)
A function can then take an argument of type RVFResult as an indication it wants 1..n sequential values from memory:
disassemble :: RVFResult -> IO (Instruction, Address) disassemble r = do let (i, p, a) = getRVFResult r case i of 0x01 -> return (Push, p) 0x02 -> return (Pop, p) 0x03 -> return (Call, p) 0x04 -> do r <- a let (v, p, a) = getRVFResult r return (Out v, p)
Here you can see how we consume an additional value by executing the returned action 'a'. It's damn ugly, and this almost looks like the place for a monad (possibly something involving StateT, though, I don't know!). Ideally I'd manage a lazily constructed list -- somehow I feel that's most "Haskelly" -- but does anyone else have any ideas? I kinda fleshed this last solution out as I wrote this email, so it's kinda cruddy. Cheers, Arlen
Couldn't this be solved with an Iteratee approach? An Enumerator produces values from your VM, an Enumeratee checks that only enough pass (enough to disassemble 'this' instruction) and an Iteratee chews the memory into the final value. I'm writing this without the time to actually develop it, I'm sorry for not providing any examples. On Mon, 2011-05-09 at 18:41 +1000, Arlen Cuss wrote:
Hi all,
I'm currently trying to write a very simple VM in order to learn and stretch my Haskell. I'm currently up against a problem.
I'm using an (IOUArray Int Word32) to represent the memory of a VM instance. This is all fine so far, but now I'm trying to write a 'disassemble' function that will disassemble an instruction starting from a given location in memory.
Ideally I could write a function that would lazily yield successive elements from memory, sort of like this:
readVMFrom :: VM -> Address -> IO [Word32] readVMFrom v f = do i <- readArray (memory v) f rest <- readVMFrom v (succ f) return $ i : readVMFrom v (succ f)
Of course, this isn't lazy, and so happily runs off the end of memory each time. (I could stop that, but that's not the point!) I'm not sure how to lazily construct a list in IO.
My next thought is to instead make a function to return an action that yields successive values of memory, given some start, i.e. something like:
readVMFrom :: VM -> Address -> IO Word32
.. but I'm thinking I might have to do some StateT nonsense in order to actually keep track of which index we want to read next. (subtext: I don't know how to do that!)
So I then think that perhaps I can do this by having readVMFrom return an action which yields a) the next value, b) the address of the next value (so we know how much we ate), and c) an action to yield the next value and action and so on, so on. I managed that this way (WARNING, BEGINNER HASKELL CODE FOLLOWS):
newtype RVFResult = RVFResult { getRVFResult :: (Word32, Address, IO RVFResult) }
readVMFrom :: VM -> Address -> IO RVFResult readVMFrom v f = do i <- readArray (memory v) f return $ RVFResult (i, succ f, readVMFrom v $ succ f)
A function can then take an argument of type RVFResult as an indication it wants 1..n sequential values from memory:
disassemble :: RVFResult -> IO (Instruction, Address) disassemble r = do let (i, p, a) = getRVFResult r case i of 0x01 -> return (Push, p) 0x02 -> return (Pop, p) 0x03 -> return (Call, p) 0x04 -> do r <- a let (v, p, a) = getRVFResult r return (Out v, p)
Here you can see how we consume an additional value by executing the returned action 'a'. It's damn ugly, and this almost looks like the place for a monad (possibly something involving StateT, though, I don't know!).
Ideally I'd manage a lazily constructed list -- somehow I feel that's most "Haskelly" -- but does anyone else have any ideas? I kinda fleshed this last solution out as I wrote this email, so it's kinda cruddy.
Cheers,
Arlen _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
Hi Elvio,
Couldn't this be solved with an Iteratee approach?
Thanks for your reply! I'm now looking into this solution; is there a standardised Enumerat{or,ee}/Iteratee library? Or is the situation still as it was discussed in the following URL? https://john-millikin.com/articles/understanding-iteratees/
An Enumerator produces values from your VM, an Enumeratee checks that only enough pass (enough to disassemble 'this' instruction) and an Iteratee chews the memory into the final value.
Cheers!
I'm writing this without the time to actually develop it, I'm sorry for not providing any examples.
I'll come back when/if I manage it :) Arlen
On Mon, 2011-05-09 at 18:41 +1000, Arlen Cuss wrote:
Hi all,
I'm currently trying to write a very simple VM in order to learn and stretch my Haskell. I'm currently up against a problem.
I'm using an (IOUArray Int Word32) to represent the memory of a VM instance. This is all fine so far, but now I'm trying to write a 'disassemble' function that will disassemble an instruction starting from a given location in memory.
Ideally I could write a function that would lazily yield successive elements from memory, sort of like this:
readVMFrom :: VM -> Address -> IO [Word32] readVMFrom v f = do i <- readArray (memory v) f rest <- readVMFrom v (succ f) return $ i : readVMFrom v (succ f)
Of course, this isn't lazy, and so happily runs off the end of memory each time. (I could stop that, but that's not the point!) I'm not sure how to lazily construct a list in IO.
My next thought is to instead make a function to return an action that yields successive values of memory, given some start, i.e. something like:
readVMFrom :: VM -> Address -> IO Word32
.. but I'm thinking I might have to do some StateT nonsense in order to actually keep track of which index we want to read next. (subtext: I don't know how to do that!)
So I then think that perhaps I can do this by having readVMFrom return an action which yields a) the next value, b) the address of the next value (so we know how much we ate), and c) an action to yield the next value and action and so on, so on. I managed that this way (WARNING, BEGINNER HASKELL CODE FOLLOWS):
newtype RVFResult = RVFResult { getRVFResult :: (Word32, Address, IO RVFResult) }
readVMFrom :: VM -> Address -> IO RVFResult readVMFrom v f = do i <- readArray (memory v) f return $ RVFResult (i, succ f, readVMFrom v $ succ f)
A function can then take an argument of type RVFResult as an indication it wants 1..n sequential values from memory:
disassemble :: RVFResult -> IO (Instruction, Address) disassemble r = do let (i, p, a) = getRVFResult r case i of 0x01 -> return (Push, p) 0x02 -> return (Pop, p) 0x03 -> return (Call, p) 0x04 -> do r <- a let (v, p, a) = getRVFResult r return (Out v, p)
Here you can see how we consume an additional value by executing the returned action 'a'. It's damn ugly, and this almost looks like the place for a monad (possibly something involving StateT, though, I don't know!).
Ideally I'd manage a lazily constructed list -- somehow I feel that's most "Haskelly" -- but does anyone else have any ideas? I kinda fleshed this last solution out as I wrote this email, so it's kinda cruddy.
Cheers,
Arlen _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
Hi, Arlen. Last time I checked (which wasn't too long) the central packages were iteratee xor iteratee-mtl. I used a 'xor' there because they both implement the same functionality... their differences are beyond my knowledge, but check out their dependency list for a faint idea. What I ended up using, however, was the enumerator package. I did this following Michael Snoyman's blog post on the yesod blog[1] (three part post by the end of last year). I suggest you check it out, it was very useful for me (although it might have aged by now). Happy hacking! [1] http://www.yesodweb.com/blog/enumerators-tutorial-part-1 On Tue, 2011-05-10 at 22:11 +1000, Arlen Cuss wrote:
Hi Elvio,
Couldn't this be solved with an Iteratee approach?
Thanks for your reply! I'm now looking into this solution; is there a standardised Enumerat{or,ee}/Iteratee library? Or is the situation still as it was discussed in the following URL? https://john-millikin.com/articles/understanding-iteratees/
An Enumerator produces values from your VM, an Enumeratee checks that only enough pass (enough to disassemble 'this' instruction) and an Iteratee chews the memory into the final value.
Cheers!
I'm writing this without the time to actually develop it, I'm sorry for not providing any examples.
I'll come back when/if I manage it :)
Arlen
On Mon, 2011-05-09 at 18:41 +1000, Arlen Cuss wrote:
Hi all,
I'm currently trying to write a very simple VM in order to learn and stretch my Haskell. I'm currently up against a problem.
I'm using an (IOUArray Int Word32) to represent the memory of a VM instance. This is all fine so far, but now I'm trying to write a 'disassemble' function that will disassemble an instruction starting from a given location in memory.
Ideally I could write a function that would lazily yield successive elements from memory, sort of like this:
readVMFrom :: VM -> Address -> IO [Word32] readVMFrom v f = do i <- readArray (memory v) f rest <- readVMFrom v (succ f) return $ i : readVMFrom v (succ f)
Of course, this isn't lazy, and so happily runs off the end of memory each time. (I could stop that, but that's not the point!) I'm not sure how to lazily construct a list in IO.
My next thought is to instead make a function to return an action that yields successive values of memory, given some start, i.e. something like:
readVMFrom :: VM -> Address -> IO Word32
.. but I'm thinking I might have to do some StateT nonsense in order to actually keep track of which index we want to read next. (subtext: I don't know how to do that!)
So I then think that perhaps I can do this by having readVMFrom return an action which yields a) the next value, b) the address of the next value (so we know how much we ate), and c) an action to yield the next value and action and so on, so on. I managed that this way (WARNING, BEGINNER HASKELL CODE FOLLOWS):
newtype RVFResult = RVFResult { getRVFResult :: (Word32, Address, IO RVFResult) }
readVMFrom :: VM -> Address -> IO RVFResult readVMFrom v f = do i <- readArray (memory v) f return $ RVFResult (i, succ f, readVMFrom v $ succ f)
A function can then take an argument of type RVFResult as an indication it wants 1..n sequential values from memory:
disassemble :: RVFResult -> IO (Instruction, Address) disassemble r = do let (i, p, a) = getRVFResult r case i of 0x01 -> return (Push, p) 0x02 -> return (Pop, p) 0x03 -> return (Call, p) 0x04 -> do r <- a let (v, p, a) = getRVFResult r return (Out v, p)
Here you can see how we consume an additional value by executing the returned action 'a'. It's damn ugly, and this almost looks like the place for a monad (possibly something involving StateT, though, I don't know!).
Ideally I'd manage a lazily constructed list -- somehow I feel that's most "Haskelly" -- but does anyone else have any ideas? I kinda fleshed this last solution out as I wrote this email, so it's kinda cruddy.
Cheers,
Arlen _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
I've actually put the three parts together in a single chapter of the
Yesod book[1]. The information there should be up-to-date. I should
put a link to the chapter from the blog posts actually.
Michael
[1] http://www.yesodweb.com/book/enumerator
On Tue, May 10, 2011 at 5:31 PM, Elvio Toccalino
Hi, Arlen. Last time I checked (which wasn't too long) the central packages were iteratee xor iteratee-mtl. I used a 'xor' there because they both implement the same functionality... their differences are beyond my knowledge, but check out their dependency list for a faint idea. What I ended up using, however, was the enumerator package. I did this following Michael Snoyman's blog post on the yesod blog[1] (three part post by the end of last year). I suggest you check it out, it was very useful for me (although it might have aged by now).
Happy hacking!
[1] http://www.yesodweb.com/blog/enumerators-tutorial-part-1
On Tue, 2011-05-10 at 22:11 +1000, Arlen Cuss wrote:
Hi Elvio,
Couldn't this be solved with an Iteratee approach?
Thanks for your reply! I'm now looking into this solution; is there a standardised Enumerat{or,ee}/Iteratee library? Or is the situation still as it was discussed in the following URL? https://john-millikin.com/articles/understanding-iteratees/
An Enumerator produces values from your VM, an Enumeratee checks that only enough pass (enough to disassemble 'this' instruction) and an Iteratee chews the memory into the final value.
Cheers!
I'm writing this without the time to actually develop it, I'm sorry for not providing any examples.
I'll come back when/if I manage it :)
Arlen
On Mon, 2011-05-09 at 18:41 +1000, Arlen Cuss wrote:
Hi all,
I'm currently trying to write a very simple VM in order to learn and stretch my Haskell. I'm currently up against a problem.
I'm using an (IOUArray Int Word32) to represent the memory of a VM instance. This is all fine so far, but now I'm trying to write a 'disassemble' function that will disassemble an instruction starting from a given location in memory.
Ideally I could write a function that would lazily yield successive elements from memory, sort of like this:
readVMFrom :: VM -> Address -> IO [Word32] readVMFrom v f = do i <- readArray (memory v) f rest <- readVMFrom v (succ f) return $ i : readVMFrom v (succ f)
Of course, this isn't lazy, and so happily runs off the end of memory each time. (I could stop that, but that's not the point!) I'm not sure how to lazily construct a list in IO.
My next thought is to instead make a function to return an action that yields successive values of memory, given some start, i.e. something like:
readVMFrom :: VM -> Address -> IO Word32
.. but I'm thinking I might have to do some StateT nonsense in order to actually keep track of which index we want to read next. (subtext: I don't know how to do that!)
So I then think that perhaps I can do this by having readVMFrom return an action which yields a) the next value, b) the address of the next value (so we know how much we ate), and c) an action to yield the next value and action and so on, so on. I managed that this way (WARNING, BEGINNER HASKELL CODE FOLLOWS):
newtype RVFResult = RVFResult { getRVFResult :: (Word32, Address, IO RVFResult) }
readVMFrom :: VM -> Address -> IO RVFResult readVMFrom v f = do i <- readArray (memory v) f return $ RVFResult (i, succ f, readVMFrom v $ succ f)
A function can then take an argument of type RVFResult as an indication it wants 1..n sequential values from memory:
disassemble :: RVFResult -> IO (Instruction, Address) disassemble r = do let (i, p, a) = getRVFResult r case i of 0x01 -> return (Push, p) 0x02 -> return (Pop, p) 0x03 -> return (Call, p) 0x04 -> do r <- a let (v, p, a) = getRVFResult r return (Out v, p)
Here you can see how we consume an additional value by executing the returned action 'a'. It's damn ugly, and this almost looks like the place for a monad (possibly something involving StateT, though, I don't know!).
Ideally I'd manage a lazily constructed list -- somehow I feel that's most "Haskelly" -- but does anyone else have any ideas? I kinda fleshed this last solution out as I wrote this email, so it's kinda cruddy.
Cheers,
Arlen _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
Excellent, thank you Michael. I gotta reread that piece. On Tue, 2011-05-10 at 18:42 +0300, Michael Snoyman wrote:
I've actually put the three parts together in a single chapter of the Yesod book[1]. The information there should be up-to-date. I should put a link to the chapter from the blog posts actually.
Michael
On Mon, 2011-05-09 at 10:29 -0300, Elvio Toccalino wrote:
Couldn't this be solved with an Iteratee approach? An Enumerator produces values from your VM, an Enumeratee checks that only enough pass (enough to disassemble 'this' instruction) and an Iteratee chews the memory into the final value. I'm writing this without the time to actually develop it, I'm sorry for not providing any examples.
Oh wow, more over my head than I thought ;-) We shall see!
participants (3)
-
Arlen Cuss -
Elvio Toccalino -
Michael Snoyman