#clojure logs

2008-08-10

11:03achim_phi there
11:03achim_pdoes anybody have recommendations for FP specific algorithms/data structurs texts?
11:05arohnerthat's a good question
11:05arohnerI've heard of a few, but I don't know if they're any good
11:10achim_pi saw these being mentioned:
11:10achim_phttp://www.eecs.usma.edu/webs/people/okasaki/pubs.html#cup98
11:10achim_phttp://www.iro.umontreal.ca/~lapalme/Algorithms-functional.html
11:11arohneri was about to link to purely functional data structures
11:14arohnerrhickey: how much work would it be to replace all references to a datastructure with a weak reference?
11:15arohneri.e. (def x (weak-ref x))
11:15rhickeyarohner: for me to change vars?
11:15arohnernot all vars
11:15arohnerbut at runtime to modify an existing var
11:16rhickeywhat is the use case?
11:16arohnerimplementing a DB :-)
11:17arohnerso I can serialize parts of my dataset to disk
11:17arohnerso replace a var with a weak ref to the var, and serialize it to disk
11:17arohnersince the ref is now weak, the GC can collect it
11:17rhickeyarohner: you can use weak references whenever you want, not sure how Clojure would get involved
11:18arohnerI guess I'm asking if the compiler/runtime keeps any references to objects under the covers
11:18rhickeylots
11:18arohnerso my one more weak ref wouldn't do anything in the whole GC scheme
11:18arohnerbecause the object won't get GC'd until all of the strong refs are gone
11:18rhickeynot sure what you mean, you can put a weak ref in a var, that will be the only ref
11:19arohneroh, duh.
11:19rhickeybut data structures share structure profusely
11:20arohnerbecause of things like conj?
11:22rhickeyjust the nature of persistent data structures - object identity isn't such a strong notion, but that won't really effect a weak-ref scheme for gc, ust note that part of you data structure may still be strongly ref-ed from another that shares structure
11:23arohneris there any way to identify what shares structure, or a way to split the two?
11:23rhickeyno, but I would wonder why you would need to do so
11:24arohnerso I can have a clear understanding of when something is able to be serialized to disk and GC'd
11:26arohnerI want this to happen automatically based on memory usage
11:26rhickeythe data structures are immutable, you can serialize at any time
11:28rhickeysounds like you want SoftReferences
11:29arohnerah, you're right
11:30arohneryou covered the step I missed earlier, that the compiler/runtime can't hold any hidden refs to objects, or else normal GC wouldn't happen
14:27ChouserThe clojure.set operations, by virtue of returning sets, are eager. However, if they returned seqs many could be lazy. I wonder if this would generally be of any benefit.
14:30rhickeyChouser: which ones?
14:32ChouserI haven't picked trhough all of them, but union, difference, and intersection each only need to access one of their inputs randombly -- the other input and the output could be lazy seqs.
14:34rhickeyThe idea in set is that these operations can be composed efficiently, as soon as they return seqs then they no longer are sets, and would have to be made into sets for the next operation
14:35rhickeybut the ops union etc would be interesting as seq fns too, I agree, but not instead
14:36Chousersure. I still don't know if there would often be any use or benefit to the seq forms. It was just an observation.
14:36Chouser(I'm still reading Tar Pit)
14:37rhickeyChouser: do you like it?
14:37Chouservery much -- it's stimulating a lot of thought.
14:38arohnerwhat is Tar Pit?
14:38arohneroh, the paper that was linked on groups the other day
14:38Chouseryes. still looking for the link.
14:38arohneryeah, I'm reading it too, I just didn't remember what it was called :-)
14:38Chouser:-)
14:39drewrarohner: http://groups.google.com/group/clojure/msg/5512f4d7be55edc7
14:41ChouserI think the ICFP problem would be an easy fit for separating as the paper describes.
14:42ChouserThe functional business of deriving useful state from the textual input felt pretty clean to me in Clojure.
14:43ChouserI wasn't thinking too clearly about how to store that state, so that's where my solution starts to get messy.
14:43ChouserAnd finally the "logic" part for deciding what commands to send is a tiny part of my final code base -- it is also rather dumb and yet still overly complicated.
14:44ChouserI'm fascinated by the thought of replacing the logic part with some set of rules to be given to a rule engine.
14:44rhickeyRight, that's the last piece for Clojure
14:45ChouserThis paper is certainly helping me see why you'd choose to work on that next. I was rather surprised when you first mentioned it.
14:45rhickeyI went with Agents/Refs and STM for the 'world' state, vs relaTIONAL
14:46rhickeyI don't know that the authors ever delivered a system that realized their vision
14:52ChouserI still feel like I need an efficient mechanism for backing a collection to disk, specifically a collection in a ref.
14:53ChouserSTM makes it pretty easy to correctly snapshot an in-memory collection to disk (for example with prn), and of course you can read in such a collection from disk at startup.
14:54Chouserbut it seems a shame to write out the whole collection when you, say, add an item to a set. And the whole thing breaks down if your data is too large for RAM.
14:59rhickeyChouser: you have to be careful about attaching disk IO to transactions
15:01rhickeyI'd like to figure out a way for the disk version of data structures to share structure like the in-memory versions - seems like a good fit for Terracotta though