IRC channel logs

2014-12-03.log

back to list of logs

<davexunit>good evening guilers
*davexunit thinks about a good way to write a purely functional minesweeper clone
<davexunit>or rather, to have the fundamental operations on the minesweeper board use a purely functional data structure.
<cky>davexunit: So, there's two parts to this: the model and the view. (Yes, I'm applying MVC here.)
<cky>The model is the arrangement of the mines. The view is stuff like which squares are uncovered.
<cky>The model is immutable. Easy.
<cky>The view is where the fun is, and you can probably use some kind of persistent data structure for that.
<davexunit>cky: the hard part about the model is efficiently uncovering mines.
<davexunit>or rather, tiles.
<davexunit>it's a recursive operation. did the revealed tile have any neighboring mines? no? well, recursively reaveal all neighbors.
<cky>Right. What's hard about that?
<davexunit>doing it imperatively with an array is trivial. what persistent data structure do you choose to do it functionally? using lists doesn't seem to be a way to go.
<cky>So, Racket has these functional persistent hash tables (these are O(log n) lookup, unlike mutable hash tables, which are O(1)). I'm thinking of implementing the square lookup using that.
<cky>I have half a mind to port it to Guile.
<cky>Especially if there's any interest in getting it in-tree.
<cky>(Speaking of getting things in-tree, I want to ping Mark Weaver about reviewing my OS X build fix.)
<davexunit>I think having more persistent data structures in core guile would be good.
<turbofail>racket's implementation isn't quite ideal, a HAMT implementation of functional hash tables would be better
<davexunit>I guess for minesweeper I could just use a vector of vectors and not modify the vector after construction.
<davexunit>that way I can have constant access time. just have to replace a whole row if I change any tiles.
***Fuuzetsu is now known as Guest96040
***Fuuzetsu` is now known as Fuuzetsu
***Fuuzetsu is now known as Guest8364
***Guest8364 is now known as Fuuzetsu`
***Fuuzetsu` is now known as Fuuzetsu
<cky>mark_weaver: Interesting host name. :-D
<cky>mark_weaver: Thanks for the review of the SRFI 28 and pushing it through. Do you have any feedback for my other patch? I'd like to get it into stable-2.0 at some stage too (it seems to have worked for taylanub), if it looks (or can be made to look) reasonable. :-)
<cky>Oh, I see civodul wrote something about it.
<cky>Lemme respond to that.
<mark_weaver>cky: yeah, I was going to write something similar to what civodul wrote. thanks for looking into it!
<mark_weaver>it would be nice to know the nature of the problem. it seems unlikely that macos would have a broken TLS.
<cky>*nods*
<nalaginrut>morning guilers~
<artyom-poptsov>Hello nalaginrut
<nalaginrut>heya
<artyom-poptsov>Argh, github.com is blocked in Russia again.
<artyom-poptsov>I mean, with all the cool Guile projects hosted there.
<nalaginrut>artyom-poptsov: congrats! it's blocked in China frequently
<nalaginrut>I never know there're so many dangerous guys against these fragile gov on github
<nalaginrut>;-P
<artyom-poptsov>nalaginrut: Oh, thanks. It seems that my country tries to keep up in the blacklisting race.
<nalaginrut>artyom-poptsov: well, they're trying to go further in a wrong way
<nalaginrut>after all, treat a pure tech site as dangerous is ridiculous
<artyom-poptsov>nalaginrut: Although I have never felt neither myself nor my projects dangerous enough to be blocked in such a scale.
<nalaginrut>I think their opinion is: knife is harmful, so we should close all the knife shops
<Chaos`Eternal>not that reason
<Chaos`Eternal>github can be used for publish
<artyom-poptsov>AFAIK the reason for blocking was some bad repository with a bad file in it that clever people forked many times just to make fun of the situation.
<Chaos`Eternal>and practically, there are some articles published on github
<Chaos`Eternal>they afraid of that, and simple way is block github
<nalaginrut>alright, git-pages?
<ArneBab>mark_weaver: I again run into the problem that when I write multiple top-level wisp forms in a block and put that in the REPL, only the first is executed right away and the others are executed when I write the first line of the next block.
<ArneBab>mark_weaver: do you have an idea how I can fix this?
<ArneBab>mark_weaver: I would have to trigger the reader multiple times when getting new data from a port.
<nalaginrut>configure: error: searching for guile development files for versions 2.0 1.8, but previously found /usr/local/bin/guile version 2.2
<nalaginrut>hmm...how can I configure it under master?
<ArneBab>you know that the name “scheme” is a really unpractical name when you try to google for “cuckoo hash scheme”
<taylanub>nalaginrut: are you using the -C flag of ./configure?
<nalaginrut>taylanub: it's ok now , I think guile.m4 in master has not updated yet
<nalaginrut>so I'm using stable2
<cky>ArneBab: It's less impractical than a language named Go.
<cky>That's one advantage of languages like Clojure and Scala: instant "brand" recognition.
<ArneBab>sneek: later tell davexunit: for the minesweeper why not simply have a list on which you cons the currently uncovered tiles? That would give you an undo-stack.
<sneek>Got it.
<ArneBab>cky: regarding Go: definitely ☺
<ArneBab>sneek: botsnack
<sneek>:)
<ArneBab>cky: but Google can ensure that Go comes early when you google for Go.
<cky>ArneBab: They're not supposed to manually adjust search results. :-P
<cky>ArneBab: The problem with having a list of uncovered tiles is that lookups are O(n) on that list.
<ArneBab>cky: except when someone thinks that their results do not reflect a person properly (in the EU)
<cky>ArneBab: You definitely want something with at most O(log n) lookups.
<ArneBab>cky: GNU Guile actually manages to come ahead of Guile theme ☺
<ArneBab>cky: you could just use a list of arrays?
<cky>ArneBab: I don't understand.
<ArneBab>that would have O(n²) memory
<cky>Oh, ouch.
<ArneBab>(cons (add (car uncovered) (new-tiles)) uncovered)
<ArneBab>cky: If this is about the game, then doing more complicated stuff is far too much hassle.
<ArneBab>cky: if this is about learning to do it right (so it works for other structures, too), then it’s worthwhile :)
<cky>That depends on whether you're writing a single-player desktop game, or whether you're trying to make a C10k implementation for a gaming network.
<ArneBab>ah, yes…
<davexunit>ArneBab: sneek delivered your message to me in #guix
<davexunit>I'm not sure how your suggestion would work. right now I'm using just a list of lists to represent rows and columns.
<davexunit>not the greatest solution, but it does mean that to alter a tile I can preserve n - 1 rows.
<cky>It's probably a good tradeoff.
<davexunit>cky: morning!
<cky>Heya!
<davexunit>last night I got the basic board layout and rendering done. hopefully today or tomorrow I will write the tile revealing algorithm and add mouse input to drive it.
<davexunit>doing this is making me realize that I need to write some optimizations for sprite rendering sooner rather than later.
<davexunit>a large minesweeper board can easily result in 500+ sprites needing to be rendered
<davexunit>I need some sort of mutable data structure behind the scenes that can do this rendering optimization...
<davexunit>cky: I wrote a macro this morning called 'chain', for writing nested procedure calls linearly. surely there's either a) a more robust implementation of something similar that's been around for decades b) a reason why it's a terrible idea
<davexunit>do you know anything about such a macro?
<davexunit>an example usage: (chain '(1 2 3 4 5 6) (filter even?) (fold + 0)) ;; => 12
<wingo>davexunit: doesn't clojure have something like that?
<davexunit>wingo: hmm, dunno! I have never used clojure.
<davexunit>I will have a look-see
<taylanub>davexunit: how about simple reverse-function-composition? https://gitorious.org/taylan-scheme/r7rs-extras/source/higher-order.body.scm#L44 (not sure about the name 'pipeline')
<wingo> http://stackoverflow.com/questions/4579226/what-does-do-in-clojure
<taylanub>ISTR some #emacs people were talking about implementing that in Elisp, and the preferred name was 'thread'.
<davexunit>I don't the like the name 'thread' for this, for hopefully obvious reasons.
<taylanub>yes, me too :)
<davexunit>taylanub: I think that 'pipeline' function is a better solution
<davexunit>thanks for that
<davexunit>also reading about the clojure thing
<taylanub>np
<davexunit>ah, -> in clojure does exactly what my macro does.
<davexunit>I guess both the macro and non-macro solutions have their use-cases.
<davexunit>I like the syntax of ->, but I like that pipeline returns a procedure instead of actually doing the operation.
<davexunit>couldn't hurt to have both, I suppose.
<taylanub>by the way, sometimes I find it better after all to just use let* for such pipelining, which can give each intermediate value a distinct name. one can also repeatedly use the same name when that makes sense: (let* ((x (foo)) (x (bar x)) (x (baz x))) x)
<davexunit>often I don't want that, but I had considered it.
<taylanub>davexunit: by the way have you considered using 2D arrays instead of lists/vectors of lists/vectors?
<davexunit>taylanub: I use arrays when I want a mutable data structure, but I took a look at using it in a persistent way and didn't find anything
<davexunit>so I just use a list of lists, wrote ref/set procedures, and moved on.
<taylanub>ah, using solely immutable data?
<davexunit>yes
<davexunit>taylanub: in the future, I want to have the equivalent of Elm's 'time travelling debugger' http://elm-lang.org/
<davexunit>so, by using soley immutable data, I can implement stuff like this :)
<taylanub>indeed, that's very neat
<davexunit>Sly needs a better integration between the scheduler and the FRP stuff.
<davexunit>but once that's done, that debugger is possible to write.
<drdanmaku>davexunit: did you watch the elm creator's strange loop presentation? what type of FRP does sly use?
<davexunit>no, I didn't know about it. I should watch.
<drdanmaku>it's basically classifying the different types of FRP systems in the wild
<drdanmaku>makes it easier to talk about them
<davexunit>drdanmaku: here's where my relative ignorance shows, I don't know what to classify my FRP implementation as.
<davexunit>I should watch, then. :)
<drdanmaku> https://www.youtube.com/watch?v=Agu6jipKfYw
<davexunit>I push events, rather than polling periodically.
<davexunit>the signal tree is a doubly linked data structure, with one direction using weak-refs to allow dead signals to be GC'd.
<drdanmaku>the key point is whether you have any sort of non-frp side effects, and whether you allow high order signals (signals of signals)
<davexunit>I've thought about higher-order signals. I don't do anything to disallow it, but it's not like there's some magic unboxing of signals.
<drdanmaku>or whether you don't use signals at all, some frp variants only use functions between signals
<drdanmaku>hm, there is a subtle thing that happens when you just allow high order signals without handling it specially, evan talks about it in that video
<davexunit>drdanmaku: I can't watch the presentation now, but maybe over lunch I can.
<drdanmaku>sure :]
<davexunit>surely my FRP implementation could use some work. it's rather naive.
<davexunit>but it's worked reliably for everything I've done thus far.
<davexunit>I imagine this talk will teach me that my FRP implementation sucks.
<drdanmaku>nah, it's not marking any of them as good or bad, just talking about how they relate to each other
<davexunit>I meant my specific code, not the style of FRP that I attempted. :P
<davexunit>"oh, didn't think about that edge-case, my old implementation is flawed."
<davexunit>s/old/whole/
<davexunit>weird typo
<dsmith-work>Morning Greetings, Guilers
<paroneayea>hi dsmith-work
<amirouche>I'm doing some bytevector stuff and just realized that I've implemented procedures similar to string procedure like string-take & string-drop
<amirouche>I'm wondering whether it can be a contribution to guile or maybe there is already something like that
<amirouche>anyway, wiredtiger is beginning to roar ;)
<amirouche>taylanub: I don't really like let syntax and prefer pipeline over it, it's imo more readable
<amirouche>here is few procedures I created/found, any comment is welcomed http://dpaste.com/1FZV91H
<davexunit>what's wiredtiger?
<ArneBab>davexunit: cky had some estimates of the cost of various approaches, that could be good to check.
<taylanub>amirouche: I would discourage against using forms like 'from' which serve for nothing more than to make your code more similar to another language. 'use-modules' is already very simple and hasn't much room for confusing the module name with anything else...
<ArneBab>davexunit: currently I almost always prefer having a plain word for functionality instead of graphical identifiers, so I like your chain better :)
<amirouche>davexunit: a low level database, it's meant to build high performance databases, at the core it's a key/value store with global acid trasaction and many other nice things like projection, indexing... it is similar to Oracle Berkeley DB (same creator)
<taylanub>such "neat little hacks" can be tempting but I think they just end up causing more mental overhead for someone who's used to the bare language...
<davexunit>ArneBab: pipeline certainly has a very good use-case, though. it returns a new function that you can pass around whereever. very composable. (get it?)
<amirouche>davexunit: mongodb will use it, which will at last bring global transaction (and persistence ;)
<davexunit>ew mongo
<davexunit>amirouche: are you writing guile bindings for it?
<amirouche>yes
<davexunit>cool
<ArneBab>davexunit: sounds pretty powerful, yes
<davexunit>I think I might add both to (sly utils)
<amirouche>taylanub: really I don't feel confortable with use-modules implementation it makes things hard, you don't know what is imported, you have to be explicit about what you export. I know I shouldn't bring things from python...
<taylanub>ah well, ok
<jmd>amirouche: I believe there is a way to select only certain procedures to import.
<taylanub>jmd: yes, the code uses that internally; see pastebin link
<amirouche>jmd: yes I know, but the (from (thing) import some) is easier to the mind ;)
*amirouche afk
<taylanub>another nitpick: (. foo) syntax is a non-standard extension and might be best to avoid, because it again adds nothing extra, being the same as just 'foo'
<ArneBab>amirouche: try (use-modules ((package module) #:select function1 function2 #:prefix module-))
<davexunit>drdanmaku: watching the strange loop frp video
<davexunit>my signal graph is dynamic. it can change at runtime, it's one of the fundamental features of my system.
<davexunit>he talks about a problem with needing infinite history in order to have a signal Mouse.clicks that is defined at an abitrary point in the program's life.
<davexunit>maybe my method is just stupid, but I didn't care about that history. if the signal didn't exist before, then the counter starts at 0 starting from when it was created.
<davexunit>I guess all of the FRP people will point and laugh at my silly implementation.
<drdanmaku>yeah, that seems like the natural way to think about it if you're allowing imperative effects in places anyway
<drdanmaku>i think the reason that distinction is important to some people is that they want to preserve equational reasoning throughout the whole system, i.e. the reactive version of being a haskell weenie :]
<davexunit>haha
<davexunit>to me, I can continue to reason about my signals.
<davexunit>but it's reasoning about the behavior of signals and what their current value should always be, not what their past is.
<davexunit>I suppose it's just a difference in perspective. I initially modeled my FRP thingy after the 'system of constraints' described in chapter 3 of SICP.
<davexunit>except I made a simplification by making the data structure a DAG.
<civodul>Hello Guilers!
<dsmith-work>civodul: Greetings!
<davexunit>guile, immutable strings. when? :)
<wingo>ask the list :)
<davexunit>hehe
<wingo>see what crazy negative reactions you get :)
<wingo>we could start by deprecating string-set! and see where that gets us
<paroneayea>hey cm
<paroneayea>er
<paroneayea>cmhobbs:
<paroneayea>how goes
<cmhobbs>it goes
<cmhobbs>heh
<cmhobbs>yourself?
<paroneayea>okay!
<paroneayea>I just merged a big chunk of code into mediagoblin master
<paroneayea>that will help us eventually get towards removing globals
***karswell` is now known as karswell