IRC channel logs


back to list of logs

<sapientech>hi all, ive spent the last few days trying to add to guix, but i keep getting the following error
<sapientech>also sending this info to guix
<amz3`>héllo #guile
<amz3`>my article about the graphdb was retweeted by the creator of Tinkerpop and Gremlin
<amz3`>ACTION wonder whether to send a mail to the mailing list
<amz3`>does anyone have a threading macro like the one used clojure that allows to write composition left-to-right
<amz3`>time to go to work
<sapientech>also #guile, just wrote my first blog post using haunt, and its about guile prompts!
<civodul>Hello Guilers!
<amz3>thx civodul :)
<civodul>wingo: we have "lib/guile/2.0/ccache" in 'search-paths' for Guile but it isn't great because that also adds Guile's own directory in there
<civodul>it should have been "/site-ccache", not "/ccache"
<civodul>silly me
***dmiles is now known as dmiles_-
***dmiles_- is now known as dmiles
<OrangeShark>sapientech: in your you have graph/vl-vector listed twice in SOURCES
<OrangeShark>sapientech: the develop branch is the one you are working on, right?
<paroneayea>hello, *
<paroneayea>hi wingo, what's happenin
<wingo>chillin :)
<paroneayea>wingo: catching up on some email, then either working on spec issues or working on my emacs client for activitypub...
<dsmith-work>Happy Friday, Guilers!!
<daviid>hello guilers, happy friday indeed!
<wingo>paroneayea: btw i think emacs client was the right choice :)
<paroneayea>wingo: :)
<wingo>what's a good data structure to keep a sorted list of (time, x) pairs, with sublinear insertion time?
<davexunit>wingo: ooh are you doing timeseries stuff?
<davexunit>ACTION wants a guile equivalent of statsd
<wingo>this is for fibers
<davexunit>oh okay
<wingo>if many threads sleep you want to keep them in some data structure to know when to wake them up, how long to poll, etc
<wingo>the thing i have now is quadratic
<davexunit>I sleep coroutines in an "agenda" taken out of SICP
<davexunit>which uses queues
<wingo>then that's quadratic too if you insert to the middle
<davexunit>honestly, I've forgotten the details of how it works because I haven't looked at it in years and it's some of my earliest guile code...
<davexunit>but I believe each time gets its own queue
<OrangeShark>a balanced binary tree?
<davexunit>a list of queues
<davexunit>insertion is linear
<davexunit>linear traversal over the list to find the time segment
<davexunit>the list is ordered by time
<davexunit>if the time segment doesn't exist, set-cdr! is used to insert it
<davexunit>so, yeah, not sublinear. :(
<paroneayea>yeah sicp's scheduler is linear
<paroneayea>wingo: just a random search, but maybe relevant?
<wingo>a balanced binary trie sounds about right to me
<OrangeShark>Linux kernel apparently uses a Red Black tree for one of their schedulers
<wingo>but yeah
<paroneayea>man it is really hard to keep switching back and forth between lisps
<paroneayea>defun/define setq/set! eq?/eq etc
<paroneayea>ACTION writing scheme and emacs lisp at the same time
<daviid>anyone wrote a red black tree implementation in/for guile?
<paroneayea> I wonder if our FFI is vulnerable to this
<janneke>paroneayea: surely you must be enjoying closures and lexical-let then! ;-)
<davexunit>paroneayea: this got brought up before
<davexunit>maybe even by you!
<davexunit>IIRC mark_weaver verified that it's not a problem
<paroneayea>davexunit: oh I think I did bring it up before
<paroneayea>davexunit: whew!
<paroneayea>thanks davexunit :)
<wingo>interestingly for gnu folks, i was invited to give a talk at an llvm event that was co-located with a gnu tools event
<wingo>the gnu tools cauldron side of things was much more active and attended
<wingo>sometimes we think that llvm is taking over but it is not the case everywhere anyway :)
<janneke>ACTION cheers
<davexunit>wingo: interesting!
<davexunit>maybe all the llvm people were busy at the apple conference
<wingo>heh it's true that apple folks weren't there
<wingo>some google people were there but not many
<wingo>but i think more google people were there for the gnu side; even as google is investing much more in llvm
<wingo>maybe it just says that the llvm event was underattended or something
<wingo>i need halp
<wingo>i am getting lost in data structures
<wingo>can you tell me what i need
<davexunit>I heard that if you say "ijp" three times into a mirror...
<wingo>i need to be able to insert with O(log n) or less, in a map from K to V where K values have an order, and i will remove only from the minimum
<mark_weaver>wingo: sounds like something for a priority queue
<wingo>insertions can happen across the domain of K without restriction, it must be O(log n) in queue size in an amortized way
<mark_weaver>if the elements of the priority queue are actually pairs, but sorted by their keys.
<wingo>mark_weaver: maybe so!
<mark_weaver>okasaki had some good purely-functional priority queues in his book, and elsewhere
<wingo>jao loaned me his okasaki book once but i need to get a copy of my own :P
<mark_weaver>and some that allow efficient merging of priority queues, e.g. lazy-pairing heaps which are wonderfully simple, but maybe that's more than you need.
<wingo>i don't necessarily need something purely functional, these data structures are never mutated from multiple threads at once
<mark_weaver>iirc, there's a free library called "Edison" with implementations of his data structures
<mark_weaver>but probably in Haskell or some version of ML
<wingo>mark_weaver: hey do you have a recent 2.2 build? you might enjoy this test case
<mark_weaver>yes, I built 'master' just in the last day or two.
<wingo>need to get out another 2.1.x release soon i guess
<wingo>then git clone, do the autoreconf and make dance, then make test within a guile 2.2 environment :)
<mark_weaver>although I'm about to leave for a volunteer shift at MIT's radio station.
<wingo>ah cool
<wingo>enjoy the show :)
<wingo>if you try this out, it has a delightfully computersciencey quadratic scalability problem :)
<mark_weaver>thanks, will do! (both of those things :)
<paroneayea>wingo: I wonder if is O(log n)
<wingo>i couldn't tell!
<wingo>i don't need a separate notion of priority -- all my keys are sorted and i just remove from one end of the queue
<wingo>so that put me off a bit
<wingo>ijp's heaps are lovely but not balanced afaict
<wingo>so if you are always adding onto the end, then sadness
<wingo>which is the case for many fibers that (sleep 1)
<wingo>of the data structures in pfds, bbtrees seem to be the thing
<wingo>dunno tho
<paroneayea>isn't that a snack food popularized through simpsons-based advertisement in the 1990s
<paroneayea>oh no wait those were butterfinger bbs
<paroneayea>close enough, I'm sure
<wingo>maybe psqs are the thing
<wingo>i can just collapse the key and the priority and that will work for me(?)
<wingo>or are the priorities the values? so weird
<stis>sort first according to priority and then according to key order sounds ok, just a balancing tree of sorted nodes no?
<stis>then the leftmost in the tree has minimum priority
<wingo>i guess i was thinking in the reverse way. i need to keep the sorted list of time -> fiber, but in a PSQ the key is the fiber and the priority is the time
<wingo>i will try that :)
<wingo>using ijp's priority search queues removes my quadratic badness, it seems
<stis>thumbs up
<paroneayea>wingo: yay