Arc Forumnew | comments | leaders | submitlogin
2 points by waterhouse 3235 days ago | link | parent

[PRO TIP: Click "link" (or "parent") on this comment, so you can view it (mostly) by itself rather than squashed against the right side of the page.]

For me, when I was writing my spider solitaire program, I had a couple of global variables, the-deck and the-piles, which represented the state of the game. the-deck was a list of randomly permuted cards, which were integers from 0 to 51 (or 0-25 with two suits, or 0-12 with one suit). the-piles was a list of piles, which were lists of cards (the zeroth element was the top of the pile), and the cards were of the form (list card revealed?), where "card" = 0-51 and "revealed" = t/nil. (Yes, a card is an integer in the deck, but a list of an integer and t/nil on the board. This does not need to be changed.)

To flip over the top card of the nth pile, I went:

  (= (cadar the-piles.n) t)
To deal a card (face up) to top of each pile from the deck, I said:

  (forlen i the-piles
    (push (list pop.the-deck t) the-piles.i))
To move a chain of n cards from (the top of) one pile to another, I went:

  (let (a b) (split the-piles.i n)
    (= the-piles.i b
       the-piles.j (join a the-piles.j)))
Also, I created a global variable called "prev-states", and every move the user performed would

  (push (deepcopy:list the-deck the-piles) prev-states)
, and I had an (undo) function that would

  (let (a b) pop.prev-states
    (= the-deck a the-piles b))
. Now, what would you do in a "pure functional programming" language? If there were no assignment whatsoever, not even to global variables, I'd probably effectively implement global state by making every function take an extra argument representing global state, and shifting code around in other ways. If you could assign to global variables but all data structures were immutable (I think Clojure is like that, correct me if I'm wrong), then I'd have to keep rebinding the entire "the-piles" list when all I wanted to do was alter one or two piles. Revealing the top card of the nth pile would look something like this:

  (= the-piles
     (join (take (- n 1) the-piles)
           (list:cons (list (car the-piles.n) t) (cdr the-piles.n))
           (drop n the-piles)))
Dealing wouldn't be too horrible:

  (= the-piles
     (map [cons pop.the-deck _] the-piles))
(Note that "push" and "pop" are legal because they just do global assignment; they don't alter any data structures). And then moving a chain of n cards from i to j would look like this:

  (= the-piles
     ; ... oh god I have to know whether i>j
     ;(join (take (dec:min i j) the-piles)
     ;      ... egad I may as well just say (if (< i j) ...
     ;(if (< i j)
     ;    (join (take dec.i the-piles)
     ;          (list:drop n the-piles.i)
     ;          (cut the-piles i dec.j)
     ;          (list:join (take n the-piles.i) the-piles.j)
     ;          (drop j the-piles))
     ;    (join ... egad the repetition is intolerable
     ; hmm, this'll work
     (with (new-i (list:drop n the-piles.i)
            new-j (list:join (take n the-piles.i) the-piles.j))
       (if (< i j)
           (join (take dec.i the-piles)
                 new-i
                 (cut the-piles i dec.j)
                 new-j
                 (drop j the-piles))
           (join (take dec.j the-piles)
                 new-j
                 (cut the-piles j dec.i)
                 new-i
                 (drop i the-piles)))))
On the plus side, I would no longer need to use "deepcopy" when creating a backup of the game state.

  (push (list the-deck the-piles) prev-states)
Which is pretty much the only benefit I'd get from outlawing modification of data structures, which I assume is what "pure functional programming" would mean. Don't even talk to me about how this would look if I had to simulate global variables...

Functional programming is a useful tactic in some cases. For example, I use a "chain-length" function, which might, say, take the list (7♥ 8♥ 9♣) and return 2, the number of revealed cards of consecutive rank of the same suit. I first thought about making it take "i" as an argument, referring to the ith pile in the-piles, but I made it take the list "xs" instead, and that allowed me to use it for other purposes: e.g. determining whether a move of n cards from pile i to j will create a longer single-suited chain. (Like, moving that 7♥ 8♥ chain onto a 9♥. I have a couple of AI-assistance procedures that look for moves satisfying conditions like that.) The expression is:

  (is (+ n chain-length:the-piles.j)
      (chain-length:join (take n the-piles.i) the-piles.j))
Had I written "chain-length" to refer just to the ith pile in the global "the-piles" variable, I'd... basically have to rewrite most of it. So factoring out things into individual functions (which, btw, is, I think, in the category of things called "functional programming", but isn't usually the same as making things side-effect-free) is frequently a good thing--it makes the program easier to write, to read, to understand, and to maintain.

But the goal, the reason you'd want to do it, is not because it's called "functional programming"--it's to make the program easier to write/read/understand/maintain. And if something called "functional programming" makes it harder to do those things, then I would advocate throwing it out. I think preventing all side effects, or all side effects except those on global variables, falls firmly into the latter category; I think my example demonstrates this.



3 points by rocketnia 3233 days ago | link

Your examples can be simplified quite a bit. ^_^

  ; Move a chain of n cards from i to j.
  (zap [let (taken leftovers) (split _.i n)
         (copy _ i leftovers j (join taken _.j))]
       the-piles)
  
  
  ; Reveal the top card of the nth pile.
  
  (def copdate (orig . kvs)
    (apply copy orig (mappend [list _.0 (_.1:orig _.0)] pair.kvs)))
  
  (zap [copdate _ n [cons (list _.0 t) cdr._]] the-piles)
In principle I agree, disabling the programmer's ability to use mutation without reason is just frustrating. But I don't expect an example to help show this; most examples we could come up with would probably have easy-in-hindsight solutions like this. I think the point is that mutation gives us more easy ways to do things, so that we can quickly experiment and stuff.

-----

2 points by akkartik 3230 days ago | link

  ; Reveal the top card of the nth pile.
  
  (def copdate (orig . kvs)
    (apply copy orig (mappend [list _.0 (_.1:orig _.0)] pair.kvs)))
  
  (zap [copdate _ n [cons (list _.0 t) cdr._]] the-piles)
How the heck is this 'simplified' compared to:

  (set:cadar the-piles.n)
? :)

-----

1 point by rocketnia 3230 days ago | link

I see you want to push the example to its limit a bit. ^_^ Well, I assume this hypothetical language would be stocked with utilities that made up for what its pureness missed out on. How believable are these?

  (def zipdate (func subject . indices)
    (iflet (first . rest) indices
      (copdate subject first [apply zipdate func _ rest])
      func.subject))
  
  (def zet (subject . args)
    (apply zipdate [do t] subject args))
  
  (zap zet the-piles n 0 1)

-----

1 point by evanrmurphy 3230 days ago | link

Was he calling it a simplification of one of waterhouse's more complex snippets, such as the one below?

   (= the-piles
       (join (take (- n 1) the-piles)
             (list:cons (list (car the-piles.n) t) (cdr the-piles.n))
             (drop n the-piles)))

-----

1 point by rocketnia 3230 days ago | link

That's definitely what I meant, and I was going to just say so, but whan I saw the ":)" I realized akkartik probably knew that and meant something like "that may not be 'oh god' complicated, but it's still not nearly as convenient as the mutating code." I don't know if that's a correct interpretation, but it made it more interesting to respond. ^_^

-----

1 point by akkartik 3230 days ago | link

No I didn't think about it nearly that much, just misunderstood which snippet you were responding to :/

-----

1 point by rocketnia 3230 days ago | link

Oh, then I'm glad that's resolved now. XD;;

-----

1 point by evanrmurphy 3235 days ago | link

Yeah, I like the way you handle the-deck and the-piles. And I like this style of programming in general (i.e. a few global variables to keep state, functions corresponding to verbs in the problem space that manipulate the globals in an intuitive way). You've reminded me of how preventing all side effects could get awkward by ruling out this style of programming entirely.

To clarify, I'm not mostly interested in eliminating side effects because of some obsession with purity, but rather for performance sake. I've been pursuing so many lang design choices like fexprs/first-class macros that are supposed to really cripple performance, that I'm starting to worry my hobby implementations aren't even going to run. I'd heard that Haskell and Clojure get a big performance boost from enforced immutability/no side effects because it guarantees that most operations can safely be run concurrently, so I've just considered it an option.

I'm a real novice when it comes to optimization, and I'm certainly interested in techniques that could help me get decent performance without having to sacrifice mutability. TCO, strategic memoization, compiler hints? Any tips on this front could be really useful to me.

-----

2 points by akkartik 3235 days ago | link

Yeah there's a bunch of haskell papers on this. Among other things, purity and lazy eval allow them to do crazy loop-fusion transformations: http://stackoverflow.com/questions/578063/what-is-haskells-s...

I did compiler work in a past life, but it was C compilers where you have to be crazy conservative in your transformations.

-----