Re: [Haskell-cafe] Zipper with two focii for concurrent fun
Ah, many thanks. this looks about right. I'll go through it later today and see if i have any questions about it. -Yaakov On Mon, Jan 17, 2011 at 06:22:34PM +1030, John Lask wrote: see http://okmij.org/ftp/continuations/Continuations.html, Zipper-based file server/OS, aka ZFS where Oleg addresses concurrent operations on a shared data structure with multiple mutable cursors implemented via delimited continuations with varying isolation levels ... your issues are specifically addressed. jvl On 17/01/2011 5:20 PM, Yaakov M. Nemoy wrote: Hey List, So i've been pondering zippers in a concurrent situation, where more than one thread has access to the same data structure, but with different focal points. I've gotten a bit stuck though trying to figure out how to do this using a zipper. The use case i'm thinking of is slightly more complex, but using a basic example below should suffice for an explanation. Say we have a list of characters in a text file which we're using in the form of a zipper to show the current user's cursor position in the text file. This means a data type such as: data ZipperList a = ZL [a] a [a] where the second element is the current position of the cursor. Now as long as one user is editing the text file, we're fine. Now let's say we're working on a newfangled multipointer desktop where two users have a keyboard and mouse each and want to work on the same open file. We could have a list like this: data ZipperList a = ZL [a] a [a] a [a] which leaves us with a number of limitations. We're now limited to two cursors rather than one, but once we start assuming multipointer, two seems like a bigger limitation than just one cursor. Also, we can't tell which user is at which focal point of the zipper easily. We could replace the user with: data User a = User String a data ZipperList a = ZL [a] (User a) [a] (User a) [a] but that gets into some ugly pattern matching. It still leaves us stuck with a two user limit. Say we create a zipper that can contain other zippers. Such as: data ZipperList a = ZL (ZipperList a) a (ZipperList a) | L [a] which lets us include as many users as we want. Now this creates a very different problem. Each cursor in our fictional text editor has a totally different data structure. This is how any calculation at any cursor knows where in the text file it is. If one user edits the character at the cursor, every other zipper-like data structure has to be updated for each other users. Thus a huge concurrency issue. This is where i hit a block. Am i totally crazy in thinking i can solve this problem using a zipper? Or has someone thought about this problem already and perhaps there's even a paper on it? Please advise. -Yaakov ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Zipper with two focii for concurrent fun
Hey List, So i've been pondering zippers in a concurrent situation, where more than one thread has access to the same data structure, but with different focal points. I've gotten a bit stuck though trying to figure out how to do this using a zipper. The use case i'm thinking of is slightly more complex, but using a basic example below should suffice for an explanation. Say we have a list of characters in a text file which we're using in the form of a zipper to show the current user's cursor position in the text file. This means a data type such as: data ZipperList a = ZL [a] a [a] where the second element is the current position of the cursor. Now as long as one user is editing the text file, we're fine. Now let's say we're working on a newfangled multipointer desktop where two users have a keyboard and mouse each and want to work on the same open file. We could have a list like this: data ZipperList a = ZL [a] a [a] a [a] which leaves us with a number of limitations. We're now limited to two cursors rather than one, but once we start assuming multipointer, two seems like a bigger limitation than just one cursor. Also, we can't tell which user is at which focal point of the zipper easily. We could replace the user with: data User a = User String a data ZipperList a = ZL [a] (User a) [a] (User a) [a] but that gets into some ugly pattern matching. It still leaves us stuck with a two user limit. Say we create a zipper that can contain other zippers. Such as: data ZipperList a = ZL (ZipperList a) a (ZipperList a) | L [a] which lets us include as many users as we want. Now this creates a very different problem. Each cursor in our fictional text editor has a totally different data structure. This is how any calculation at any cursor knows where in the text file it is. If one user edits the character at the cursor, every other zipper-like data structure has to be updated for each other users. Thus a huge concurrency issue. This is where i hit a block. Am i totally crazy in thinking i can solve this problem using a zipper? Or has someone thought about this problem already and perhaps there's even a paper on it? Please advise. -Yaakov ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Zipper with two focii for concurrent fun
see http://okmij.org/ftp/continuations/Continuations.html, Zipper-based file server/OS, aka ZFS where Oleg addresses concurrent operations on a shared data structure with multiple mutable cursors implemented via delimited continuations with varying isolation levels ... your issues are specifically addressed. jvl On 17/01/2011 5:20 PM, Yaakov M. Nemoy wrote: Hey List, So i've been pondering zippers in a concurrent situation, where more than one thread has access to the same data structure, but with different focal points. I've gotten a bit stuck though trying to figure out how to do this using a zipper. The use case i'm thinking of is slightly more complex, but using a basic example below should suffice for an explanation. Say we have a list of characters in a text file which we're using in the form of a zipper to show the current user's cursor position in the text file. This means a data type such as: data ZipperList a = ZL [a] a [a] where the second element is the current position of the cursor. Now as long as one user is editing the text file, we're fine. Now let's say we're working on a newfangled multipointer desktop where two users have a keyboard and mouse each and want to work on the same open file. We could have a list like this: data ZipperList a = ZL [a] a [a] a [a] which leaves us with a number of limitations. We're now limited to two cursors rather than one, but once we start assuming multipointer, two seems like a bigger limitation than just one cursor. Also, we can't tell which user is at which focal point of the zipper easily. We could replace the user with: data User a = User String a data ZipperList a = ZL [a] (User a) [a] (User a) [a] but that gets into some ugly pattern matching. It still leaves us stuck with a two user limit. Say we create a zipper that can contain other zippers. Such as: data ZipperList a = ZL (ZipperList a) a (ZipperList a) | L [a] which lets us include as many users as we want. Now this creates a very different problem. Each cursor in our fictional text editor has a totally different data structure. This is how any calculation at any cursor knows where in the text file it is. If one user edits the character at the cursor, every other zipper-like data structure has to be updated for each other users. Thus a huge concurrency issue. This is where i hit a block. Am i totally crazy in thinking i can solve this problem using a zipper? Or has someone thought about this problem already and perhaps there's even a paper on it? Please advise. -Yaakov ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
