Breaking stuff apart - Destructuring.

So... boooored. I might as well type up whatever I know about destructuring, which is... extremely, EXTREMELY useful, to say the least.

In fact, I know quite a bit about how to use it (not everything, though), but nothing about how it works under the hood. I only recently learned how lazy-seqs work (which, incidentally, is an interesting topic for another time).

So, destructuring.

If you recall, in my previous post I used something along the lines of

(defn reroot [tree [n1 & nr]] ...

Aaaand, here's destructuring. Instead of giving a second name for the second argument, I put [n1 & nr]. The second argument passed will be destructured into n1 and nr, where n1 holds the first element of that vector, and nr the other elements (that's what &, the rest argument is for). The funny thing is, this kind of destructuring can be arbitrarlily nested, which is powerful.

Really.

More examples:

(let [[a b c] [1 2 3]]

  (println a b c))

-> "1 2 3"

(let [[a b & c] [1 2 3]]

  (println a b c))

-> "1 2 [3]"

(let [[[a & b] & c] [[1 2 3 4] 5 6 7 8]]

  (println a b c))

-> "1 [2 3 4] [5 6 7 8]"

I'm currently writing a game, and I have a map that holds the entire game state. Pure functions act on that map, returning a new one with changes to the game world incorporated. There are many uses for destructuring there.

The world is made up of tiles. I use a map of vectors to maps for those tiles; the vector has two elements (x and y position), and the maps holds all data about the given tile. Now, when a map is ran through (seq), it returns a seq of two-element vectors - the first element is the key, the second one the value. Hence when drawing the field, I can do this:

(doseq [[[x y] tile] tiles]

  ...)

Yes, destructuring can be used in doseq and for. Even in let!

See, I destructured the input vector (which is, remember, a key-value pair) into [x y] and tile. Then, the first element is further destructured into x and y. That way I have access to all those important informations without having to manually extract them.

And this is destructuring for vectors only. Yes, there are other kinds.

But before I go into them, let me note one thing first. If, via destructuring, a name should be bound to some element, but there is none, those names are bound to nil:

(let [[a b c] [1 2]]

  (println a "/" b "/" c))

-> "1 / 2 / nil"

Alright. Destructuring MAPS. This is fun as well. See, in my game I rely on maps a lot. Units, for example, are maps holding all necessary information. In many functions, I don't need all of these informations, so some handy way to extract the ones I DO need would be... handy.

Behold.

(def unit

  { :power 1 :endurance 3 :name "Thing" :image nil :owner 1 :range 3 :position [2 2] })

(let [{name :name, owner :owner} unit]

  (println name "belongs to player" owner))

-> "Thing belongs to player 1"

And you can mix both types of destructuring.

(let [{name :name, [x y] :position} unit]

  (println name "is on field" x y))

-> "Thing is on field 2 2"

Again; if a key is not found in the map, nil is bound to the corresponding names.

So. Destructuring is awesome.

 

Words of warning, though. Overusing this makes code unreadable. Seriously. I usually try to avoid using this in defn parameter vectors, unless the function is trivial, but it really shines in for and doseq, and has it's uses in lets. I rely on it a lot to make those parts more concise.

Mazes and trees (sounds better than Clojure and Emacs, doesn't it?)

Some days ago I wrote a simple maze generator using depth-first search. It's really trivial, took much less space than my age-old Ruby implementation and - most importantly - made me play around with trees in Clojure.

Today, on a three-hour ride on the train I was bored. So my mind drifted off to my happy place (which, incidentally, is programming) and I started thinking about the aforementioned generator. I realized that all generated mazes could be represented as a tree (I... won't confess as to what data structure I used before.), so, upon further thought, I also concluded that path-finding between two points is trivial, assuming that one of the points is the root node... then I thought some more, and thought, "Hey! In the case of the maze it doesn't really matter WHICH node is the root node... so, I should be able to make a different node the root node without changing the structure of the maze at ALL."

Some mililitre of ink, some paper and quite some thoughts later...

It's definately possible. And, actually, not so hard.

1 -> 2

  -> 3

  -> 4 -> 5 -> 6

       -> 7 -> 8

            -> 9

Let's use this beautiful *cough* tree. Let's say we want to find the way from 4 to 3. The way is simple: 4 -> 1 -> 3. But it's not entirely clear from a data-structure point of view. So...

4 -> 5 -> 6

  -> 7 -> 8

       -> 9

  -> 1 -> 2

       -> 3

Upon closer inspection, what happened is very clear. All nodes UP from 4 were appended to the 4 instead. I don't feel like typing out another entire tree, but if there were more nodes above the 4, then all nodes above it would be in reversed order:

1 -> 2 -> 3 -> 4 -> 5

  becomes

3 -> 4 -> 5

  -> 2 -> 1

You see, 1 -> 2 became 2 -> 1.

So, that's about the entire theory - take all nodes up until the root, reverse the order,  and append that to the node you want to be the new root.

Let's implement it.

I assume trees built from vectors in the form of:

node => [[object] & nodes]

Which means the first item of each vector is basically anything (in our example these would be numbers), followed by any number of similarly-structured vectors.

[1 [2] [3 [4]]]

is equal to:

1 -> 2

  -> 3 -> 4

Because I was on a train at the time, and I couldn't recall any function to do it (nor use the clojure.repl tools very well) I wrote my own function to remove an indexed item from a vector, called "without". Basically...

(defn without [n v]

  (vec (concat (take n v) (drop (inc n) v))))

Nothing too exciting. Also, probably redundant.

At this point I was kind of stuck. I wrote something along the lines of this...

(defn reroot [tree [n1 & nr]]

  (if n1

    (conj (reroot (tree n1) nr) (without n1 tree))

    tree))

I used destructuring here (which I will go into in more detail in the next post), but here, it's enough to know that (reroot [tree] [1 2 3]) would have n1 = 1 and nr = [2 3].

Anyway, the first argument is the tree itself, obviously, whereas the second argument is the "path" to the new root node.

For example,

(reroot [1 [2] [3 [4]]] [2 1])

should result in

[4 [3 [1 [2]]]] 

since item #1 in item #2 of the original tree is 4.

Anyways, the code snipped above is wrong. I didn't really know why, I only knew I was doing something wrong. I was totally shotgunning it, putting a without there, removing one somewhere else, replacing it with a simple access-by-index... Until I thought - SCREW THIS, let's do it properly.

I wrote another helper function, I called it swap. It would swap (HAH!) the places of the root node and it's child node of index n:

(defn swap [tree n]

  (conj (tree n) (without n tree)))

Trivial enough.

I didn't explain yet why I use the without. Picture this tree:

1 -> 2 -> 3

  -> 4 -> 5

Calling swap 1 on it (index 1 is the 2 -> 3 branch) would result in this without the "without":

2 -> 3

  -> 1 -> 2 -> 3

       -> 4 -> 5

while it should be

2 -> 3

  -> 1 -> 4 -> 5

Now it's quite obvious; I use the "without" to achieve the effect of taking out the branch from the tree I'm appending to it.

Now return to our reroot...

(defn reroot [tree [n1 & nr]]

  (if n1

    (recur (step tree n1) nr)

    tree))

This works as intended.

But, this being Clojure, such a simple function in four lines? No way this is done. We can do it better.

And of course, the pattern is pretty obvious: some value that is modified repeatedly, according to some list passed along. Sounds awfully like reduce.

Hence, the final version:

(defn without [n v]

  (vec (concat (take n v) (drop (inc n) v))))

(defn swap [tree n]

  (conj (tree n) (without n tree)))

(defn reroot [tree path]

  (reduce swap tree path))

If this isn't elegant, I don't know what is*.

*If you ignore the part with that "without" for a moment.

Clojure! Also, Emacs (I'm good with post titles.)

I recently (a few months ago?) started learning Clojure. It's a wonderful language. LISPs have fascinated me for a long time, I tried a flavor of Scheme in the past (Racket), but couldn't quite get into, despite my fascination for everything that family of languages stands for, with it's philosophy, it's appearance...

Nevermind. Clojure. I wanted to learn it. It promised a lot, parts of which I couldn't (and partially still can't) grasp the significance of, but as far as I can tell, it delivered.

I really could go all fanboy over it for significant, semi-infinite stretches of time (and my roommate just assumes it's going to be about Clojure when I tell him I have something interesting to say by now), so let's get back to earth.

So, installation. As it so often happens with this kind of awesome things, installation isn't quite that straightforward, in the Windows-sense of click, click, click some more, it runs. Actually, getting it to run under Windows was somewhat annoying.

I happen to run a Linux Mint VM, so I tried it there. I installed Emacs and tried to get SLIME/Swank to run (basically a neater REPL for LISPlikes), but numerous step-by-step tutorials have failed me, so I clean-installed Emacs and did everything by hand. Now, it's not the most "optimal", "comfortable" or anything like that setup, but the most important thing is, I'm wrestling with Emacs and Emacs Lisp myself (the latter being the reason I originally decided for Emacs over Vim, actually). It runs. There is this extremely awesome tool called Leiningen. It makes the entire thing much more comfortable than any graphical interface ever could. So does Emacs. But it takes some commitment.

I can only recommend the rough path, really. It's done me good so far.

I'll probably post some code snippets or stuff in the future. I dunno.

%:str:

Today, I was fiddling around with Ruby, as I often do.
I produced this abomination:

def wh*t

  p(%w(%s)[0]%t[0]+%:es:)

end

wh"y"

This code works (at least under 1.9.2) and it prints "yes". Bonus points if you can explain wh"y".

Okay, it's not that hard*, but I made an accidental discovery. Aside from ", ' and <<NAME there's yet another way to write out string literals.

Handy to know.

*p - function call, one of the three basic print operations. %w(a b c) produces an array of strings, a quick way to write out lists of strings. "%s" is a format string that is substituted by another string. %w(%s)[0] basically returns "%s". The % operator on a string is the same as a call to format(str, *args). The argument to format here is t[0]. t is the "rest" argument of the method, so it's an array. We call the method with the parameter "y", which makes t equal ["y"]. + concatenates two strings. %:es: is a string literal, "es". Concatenating "y" with "es" gives us... "yes".

Hello World. With dice.

Hello. From now on, I probably, maybe, will post some more-or-less interesting things related to programming and/or gaming here.

Let me start with the first gem, namely Ruby.
I'm writing something that could be called a "game", and it makes heavy use of die rolls. First, I of course needed a way to store and roll dice, so a dice class was the obvious first choice.

class Dice
  attr_accessor :amount, :sides

  def initialize(amount, sides)
    @amount, @sides = amount, sides
  end

  def roll
    result = 0
    @amount.times { |i| result += Random.rand(@sides) + 1 }
    return result
  end
end

Pretty straightforward. Minor additions include a to_s functions that outputs the object in the common dice nomination ("xdy", where x is the amount of dice, and y how many sides each die has) and a class method that parses such a string back into a Dice object.

This class is a nice thing to have, probably reusable, and so on. But it's far from done.

Now, you see, when you use dice rolls a lot, you'll probably also want to roll some dice without unnecessarily creating Dice objects every time. Doing

Dice.new(2, 6).roll

is not only ugly, but also creates redundant objects. So, we'll also want Dice::roll.

Now,

Dice.roll(2, 6)

is much better. But still pretty verbose.

You see, Ruby is very flexible and has a lot of wonderful features that allow for really cool code. I thought, hey, it would be awesome to just write 2d6 and have it roll 2d6. Then I came across method_missing. It is defined in BasicObject and called whenever an object is sent a message it cannot process. For example, Dice.foo would cause a call to method_missing, which by default (per definition in BasicObject) raises an exception.

We can intercept that. See where I'm going?

I promptly wrote a neat module. Look:

module DiceRolls
  def method_missing(sym, *args, &block)
    sym.to_s.match(/^_(\d+)d(\d+)$/) do |md|
      result = 0
      md[1].to_i.times { |i| result += Random.rand(md[2].to_i) + 1 }
      return result
    end
    super
  end
end

This, I am proud of.

Let me explain. The sym argument is the name of the method we tried to call.

(By the way, you'll recognize the three innermost lines as duplicate code from the above Dice#roll, which actually rolls the required amount of dice. They can be substituted with the previously defined Dice::roll, with md[1] and md[2] as arguments. I just wrote it that way to prevent any dependencies.)

The regexp matches strings of the form "_[x]d[y]", where x and y are... well, you should know by now. The underscore is there because Ruby function names can't start with a digit. Basically, whenever a function of that form is called, it is intercepted and processed by method_missing (unless it IS defined... but what are the odds? And even if, it's such a rare occurrence that you'd probably be aware of it).

If a class includes that module, you could just call _2d6  from anywhere in that class and get the ready random result. This is much more graceful than the clunky

Dice.roll(2, 6)

used before. The chance of name clashes (IE. a method of that form already defined) is, again, negligibly small, since... I mean, seriously. Who would call a method _2d6?

The super at the end passes the message on to the ancestors method_missing, to deal with any messages we didn't process.

Now. You could go one step further. I personally use it for my project, since I know it won't cause any harm, but I'm not sure it's always entirely safe.

That is, include the module in Object. Then, you can use this trick ANYWHERE, including top-level code.

I also later defined a similar match block that catches methods of the form "c[x]d[y]" and returns a new, matching Dice object:

module DiceRolls

    def method_missing(sym, *args, &block)

        sym.to_s.match(/^([_c])(\d+)d(\d+)$/) do |md|

            case md[1]

                when "_"

                    return Dice.roll(md[2].to_i, md[3].to_i)

                when "c"

                    return Dice.new(md[2].to_i, md[3].to_i)

            end

        end

        super

    end

end

(I keep the Dice class and this module together in one file, which I have on my load path, so I finally decided to use Dice::roll and Dice::new.)

I'm sure there are other applications for scenarios where similar notations (like [x]d[y]) exist, I can't think of any for now, though.

I love Ruby.