Cogs and Levers A blog full of technical stuff

Lambda Expressions with C++11

Introduction

A whole raft of goodness has been delivered with the most recent C++ standard, C++11. One of these features is the inclusion of lambda expressions. Today’s post will take you through the basic syntax for lambdas in C++.

Basic Assignment

You can assign a lambda to a variable quite simply with the following syntax.

#include <iostream>

int main(int argc, char *argv[]) {
  // assignment to an "auto" variable
  auto f1 = [] { std::cout << "Hello, World" << std::endl; };

  f1();

  return 0;
}

I agree that this is a pretty ass-about-face way of printing “Hello, World” to the screen - but it’s done through C++11’s lambda syntax. Passing variables into a lambda expression and getting return values is quite trivial also.

// implicit return types (handled by the complier)
auto add_imp = [] (int a, int b) { return a + b; };

// explicit return types (specified by user)
auto add_exp = [] (int a, int b) -> int { return a + b };

You can nest lambdas pretty easily also. Heres is a multiply-then-divide example where the division operation is the nested operation. Multiplication occurs at the top-level lambda.

auto muldiv = [] (float a, float x, float y) {
  return [] (float v, float u) {             
    return v / u;                           
  }(a * x, y);                               
};                                            

This syntax also allows you to define higher-order functions, so that you can return function object back to the caller for later use. Here, I’ve made a multiplier factory. You give it one side of the multiplication and it’ll hand you back a function that will multiply by that number.

auto mulBy = [](int x) {
  return [=](int y) { return x * y; };
};

auto mulBy2 = mulBy(2);
auto mulBy10 = mulBy(10);

We’ve done something a little bit different here. You can see that we’ve used a term inside the square brackets for the returned function. C++ having a major focus on performance gives the developer as much flexibility as possible when handling values. The information specified within the square braces tells the lambda closure how to handle variables referenced within.

Handling outside state within a lambda

The developer describes to the lambda how she wants variables captured by making specifications within the square brackets. Some examples of what you might see look like this.

Specification Meaning
[] Don’t capture anything
[&] Capture any variable by reference
[=] Capture any variable used making a copy of it
[=, &x] Capture any variable used making a copy of it except for x. Capture x by reference.
[y] Capture y by making a copy but nothing else.
[this] Capture the enclosing class’ pointer

So, we can be quite specific in telling the compiler how we want referenced variables handled within our lambda closure. Finally, I want to present some code on using lambdas with existing constructs. In this example, I’ll reduce a list of integers by accumulating them into a variable referenced outside of a closure.

#include <iostream>                              
#include <vector>                                
#include <algorithm>                             

int main(int argc, char *argv[]) {               

  // vector to reduce
  std::vector<int> l;                           
  l.push_back(1);                               
  l.push_back(2);                               
  l.push_back(3);                               

  // reduced result
  int i = 0;                                    

  // reduction by accumulation
  std::for_each(l.begin(), l.end(),             
    [&i](int n) { i += n; }                    
  );                                            

  std::cout << "reduced to: " << i << std::endl;

  return 0;                                     
}                                                

You can see that is is quite a fluent style for writing lambdas. This post only scratches the surface. Applying these in a real project is going to be key to discovering the depths of lambdas, but they’re alive and well in C++(11) land, that’s for sure.

C++ References

Introduction

I’ve always thought of a reference as the half-way house between pointers and statically allocated objects. References are in-fact addresses but they are used within our code just like objects as opposed to requiring pointer syntax.

Some facts ..

How reference are defined

You declare a reference variable using the ampersand & to modify the type declaration.

type& var;

A reference must be initialised

This is pretty basic, it just means that when you declare your reference it must start out with a place to reference.

// this is ok
int val = 90;
int& ref = val;

// this will not compile
int& ref;

A reference cannot be changed

When we initialise a reference to point to a variable, that’s it. We can’t change what the reference points to. This caught be out to begin with, but it’s pretty easy stuff.

int val1 = 90, val2 = 100;
int& ref = val1;

// prints out "90"
std::cout << val1 << std::endl;

// doesn't change ref, but changes the value
// of val1 to val2
ref = val2;

// prints out "100"
std::cout << val1 << std::endl;

Makes sense. Gives references a sense of stubbornness (and sanity).

Pointer compatibility through dereferencing

I see a fair bit of banter on “how to convert pointer to reference”, etc. It’s really quite simple and it’s also subject to the same assignment laws as above.

int i = 50, j = 60;
int* p = &i;
int& r = *p;

// prints 50 
std::cout << *p << std::endl;

// through this reference, we've changed "i" to 60
r = j;

// prints 60
std::cout << *p << std::endl;

These concepts really come into their own (I think) once you start using them within your own class structures. It’s a much more natural feel to deal with references rather than pointers and a bit easier to read as well.

Writing a Window Manager for X11

As a bit of a bookmark to myself, I just wanted to post about writing a window manager for X windows. A lot of the material that I’ve seen around the place in articles and posts themselves have all pointed me towards downloading the out-of-print O’Reilly Open Book site.

Some of the books of interest to a window manager programmer are

I’m sure that there is plenty of other reference material around, but a lot of people were suggesting to put a copy of these in your claw - so I have. Digging around a little bit more, I came across TinyWM. TinyWM looks like a suitable candidate to be the bootstrap to a window manager project. It’s functional, it doesn’t do much but it is around 50 lines of C code. I’ll be using this as my guide for when that rainy day comes and I start work on my own WM.

Clojure's spine: Java

Introduction

One of Clojure’s greatest strengths is the fact that it sits on the JVM. This puts all of those jars that people have worked tirelessly over the years to produce right at your fingertips ready for use in your Clojure code. Today’s post will just be a short tutorial on some of the most basic routines to use Java classes in your Clojure code. All of the examples that I’ll produce are all based on the Java_interop page on the Clojure site.

Importing classes

First things first. You’ll need to import the classes that you want to use. You don’t have to, it just makes your code a little less verbose later on.

(import 'java.net.URL)

We’re now able to use the URL class in our code. If you’re importing classes into your programs that aren’t local and need to be downloaded as a dependency, I suggest you use Leiningen to do all the heavy lifting for you there. You’d just need to list your external package in the dependencies list in your project file and away you go.

Using the classes

We need to construct some objects so that we’ll be able to call methods on them, so following on from the example, we construct instances of the classes that we import like so.

(def google (new URL "http://www.google.com"))

This is really getting the Java mojo mixed in with Clojure now. So “google” is our constructed object, we can start to call methods on this variable like so.

(.getProtocol google)

(def yahoo (new URL "http://www.yahoo.com"))
(.sameFile google yahoo)

We were able to find out the protocol of the URL using getProtocol and we were able to compare “google” and “yahoo” using sameFile.

doto

The last thing I want to talk about is doto. doto evaluates its first parameter than allows you to chain a series of calls (just as you would in Java using the . operator) together. Here’s a an example using a HashMap class and chaining a few put’s together. This statement will return the built HashMap.

(doto (java.util.HashMap.)
      (.put "First Name" "John")
      (.put "Last Name" "Smith"))

Well, that’s it for today. I’m off to write some Java .. I mean, Clojure, I mean … you know what I mean.

Tic Tac Toe in Haskell

Introduction

Still trying to flex my skills in the Haskell arena and am still chasing a real project to do. Until I find said project, silly little games it is. A little while ago I watched the Haskell Live videos and in these videos a good start is made on a chess framework. Very interesting stuff to see how something like this is put together and if you haven’t seen them, I suggest you go and check out episode 1 and episode 2. Anyway, the videos don’t yet take you through to a completed implementation and while I’d love to say that I possess the skills to take the chess game through, I’d be punching above my weight. In compromise, I’ve been able to use some of the concepts that Rein has demonstrated in his videos - in my own implementation of Tic Tac Toe. Today’s post will take you through my implementation.

Functional Specification

Well, if you’re really wanting the functional in’s-and-out’s of the game Tic-tac-toe, I suggest you step our of your bubble and read this. This implementation will involve two rather random computer players battling it out, so no user interactivity (yet). Well, thanks to a cheeky link to a wikipedia article, that’s the smallest functional specification I’ve ever seen. On to the code.

Pieces

First up, we’ll deal with pieces. To this program, a piece can be a Naught or a Cross. When the piece is a Naught, we want to represent it with a ‘o’, when the piece is a Cross, we want to represent it with an ‘x’. Here’s the type declaration and functions we’ll use to work with pieces.

-- | A piece is what a player places in a cell
data Piece = Naught | Cross                   
   deriving (Eq, Show, Read)
 
-- | Converts a piece into the board representation     
showPiece :: Piece -> Char                              
showPiece Naught = 'o'                                  
showPiece Cross  = 'x'                                  
                                                        
-- | Converts the board representation back into a piece
readPiece :: Char -> Piece                              
readPiece 'o' = Naught                                  
readPiece 'x' = Cross                                   

A piece can only be either a Naught or a Cross, nothing else. The functions are all very straight forward and meeting the requirements of our specification. Naughts will look like “o’s” and Crosses will look like “x’s”. Just to be sure, we can setup a couple of QuickCheck tests to assure us that it’s ok.

quickCheck (readPiece (showPiece Naught) == Naught) 
quickCheck (readPiece (showPiece Cross) == Cross)   

We’re ready to move on.

Cells

A cell is a representation of one of the nine squares that you find on a tic-tac-toe board. A cell differs from a piece as a cell can have a piece value or it can be empty. In our implementation, empty cells will be represented by a period .. Let’s take a look at the types and the functions we’ll use to interact with cells.

-- | A cell is empty or it contains a piece
type Cell = Maybe Piece                    

-- | Shows the value of a cell        
showCell :: Cell -> Char              
showCell Nothing  = '.'               
showCell (Just p) = showPiece p       
                                      
-- | Reads a board cell and transforms
readCell :: Char -> Cell              
readCell '.' = Nothing                
readCell p   = Just $ readPiece p     

We use Maybe to allow either a Nothing or a Piece value for a cell. With the help of those functions we’ve already written for pieces, you can see that these cell functions are very simple. We’ve only had to cater for one extra case, the case of when there’s no value in a cell. We’ll setup a few more QuickCheck tests just to make sure that our Cell code is working ok.

quickCheck (readCell (showCell Nothing) == Nothing)            
quickCheck (readCell (showCell (Just Cross)) == (Just Cross))  
quickCheck (readCell (showCell (Just Naught)) == (Just Naught))

Great. With this code written we’re ready to wrap up a List of these cells into a field that we will play on.

The Field

A 3x3 grid is normally what’s drawn prior to playing a game of tic-tac-toe. We will define the field as an array of an array of cells. Here’s the type and supporting functions for a field.

-- | A field is a 3x3 array of cells
type Field = [[Cell]]               

-- | Shows a field of cells        
showField :: Field -> [String]     
showField = map showCellRow        
   where showCellRow = map showCell
                                   
-- | Reads a field                 
readField :: [String] -> Field     
readField = map readCellRow        
   where readCellRow = map readCell

Much as before, you can see that we’re leaning on our already-built set of functions to implement all of our field-based functions. At this point, we can define the starting field that all of our games will originate with.

initialField = ["..." 
               ,"..." 
               ,"..."]

You can see that the field is in string format. It’s a little more human to read and it’s all ready for our readField function to use as is demonstrated by the following QuickCheck test.

quickCheck (showField (readField initialField) == initialField)

It’s at this point where any similarities between the Haskell Live videos and my implementation end. It’s probably natural that this is the point as we’re going to start dealing with some game logic.

Winners and Losers

There are a few tests that we have to be constantly running in order to simulate a real-life game of tic-tac-toe. One of which is “do we have a winner yet? Testing if a winner has been established is testing if the same symbol appears on a horizontal, vertical or diagonal line. In each of these configurations, there are only going to be three cells to test, so I made a general purpose array tester. I’ve use pattern matching in this function to be as clear as possible. It’s not as DRY as it could be, but we can improve it later - let’s just get it working. Here’s the function to test three list elements to see if there’s a winner.

-- | Tests a prepared row for a winner                       
testRow :: [Cell] -> Maybe Piece                             
testRow [Just Naught, Just Naught, Just Naught] = Just Naught
testRow [Just Cross, Just Cross, Just Cross]    = Just Cross 
testRow _                                       = Nothing    

Easy. This function looks like it will be very effective in testing winners on the horizontal lines. But what about the vertical lines that occur in different arrays? and the diagonal lines that exist in different arrays and in different indexes across the horizontal axis? My answer here is to create a function that make all of these testable vectors into horizontal rows so that we can use the above function on all of the different win configurations. Here’s the code to build an array of these 3 element arrays.

-- | Flattens the winnable view of a field into testable rows         
makeRows :: Field -> [[Cell]]                                         
makeRows f = horiz ++ vert ++ diag                                    
   where horiz = [r | r <- f]                                         
         col1  = [r | r <- head f]                                    
         col2  = [r | r <- head $ drop 1 f]                           
         col3  = [r | r <- head $ drop 2 f]                           
         vert  = [col1, col2, col3]                                   
         diag  = [[head col1, head $ drop 1 col2, head $ drop 2 col3] 
                 ,[head $ drop 2 col1, head $ drop 1 col2, head col3]]

Walking through this one piece-by-piece, we can see a number of items in the where clause. Sure, these could be consolidated into a big-fat-one-liner, but I wanted to make clear exactly what was being concatenated. So, horiz is a list comprehension giving you each horizontal line, col1, col2 and col3 are the vertical columns. diag is a little less clearer through its use of head and drop, but it does form the diagonals into testable rows.

Playing the game

Weather you’re a computer or human player, you’ll need to know where are the valid spots to move. It’ll be intuitive enough from the user interface presented for a human to realise where their next move will be, but our computer player counterparts will need to be told explicitly where they can move. This next function just finds all of the available cells that you can move into.

-- | Gathers all of the positions that are free                     
getOptions :: Field -> [Int]                                        
getOptions f = [snd x | x <- zip (concat f) [0..], fst x == Nothing]

We assign an index (from 0 to 8) to each cell and only return the indexes that are paired with a Nothing value. This function will help us later when we go to build a user interface for this application. We’ll be able to prompt the user intuitively.

Flattening the array gives us the [0..8] range, which over the 3x3 grid (which is really our tic-tac-toe representation), the range looks like this.

0 1 2
3 4 5
6 7 8

This is timely information as we’re just about to present the function that will place a piece on the field for us. Placing a piece will require us to provide the current game field, the piece we want to apply and the index that we want to apply it at. This function cuts the list on the index that we want to apply and then re-concatenates the broken list around the new piece (obviously dropping the cell that we’re putting a piece into). Here’s the code.

-- | Places a piece on the board                        
placePiece :: Field -> Piece -> Int -> Field            
placePiece f p n = chunksOf 3 $ prior ++ [cell] ++ after
   where flat = concat f                                
         prior = take n $ flat                          
         after = drop (n + 1) $ flat                    
         cell = (Just p) :: Cell                        

Trying to be as clear as possible with my names here. prior being the list before the break, after is what comes after. Now it’s time to introduce our “artificial intelligence” which really - there isn’t any intelligence here. It’s based purely off of a random number generator. Here’s how our computer players will play a round of tic-tac-toe.

-- | Takes a random turn on a field                                      
takeRandomTurn :: StdGen -> Piece -> Field -> (StdGen, Field)            
takeRandomTurn gen p f = (seed, placePiece f p (opts !! idx))            
   where opts        = getOptions f                                      
         (idx, seed) = randomR(0, (length opts) - 1) gen :: (Int, StdGen)

We’re taking in a random number generator, the piece type that the computer will place and the field that it will be placed in. The output to which will be a new random number generator and the changed field. This way, we can repeatedly call this function and not worry about losing our sense of entropy (or field state!). Finally we have the function that will play our game until we have a result (win naught, win cross or tie). I needed to implement a “not” function for my piece type. This is just so I can offer each “player” a go interchangeably. Here’s the code.

-- | Acts like a boolean "not" for tic-tac-toe pieces                         
otherPiece :: Piece -> Piece                                                  
otherPiece Cross = Naught                                                     
otherPiece Naught = Cross                                                     
                                                                              
-- | Plays a game between two random cpu players                              
playGame :: StdGen -> Piece -> Field -> IO ()                                 
playGame gen p f = if spaces == 0                                             
                      then putStrLn "Game was a tie!"                         
                      else if winner /= Nothing                               
                              then do                                         
                                 putStrLn $ (unlines fstr)                    
                                 putStrLn $ (show winner) ++ " won the game!" 
                              else do                                         
                                 putStrLn $ (unlines fstr)                    
                                 playGame ng (otherPiece p) nf                
   where winner   = hasWinner f                                               
         spaces   = length $ getOptions f                                     
         (ng, nf) = takeRandomTurn gen p f                                    
         fstr     = showField f                                               

This reads fairly humanly. We assume that if execution breaks into this function, a result wasn’t established on the execution prior, so we’re comfortable in the first check that if there are no spaces left to put pieces, we must declare the game as a tie. The next test is if the previous call to this function caused the other player to win the game. In the event that this check is confirmed, a message is written out and we do not continue any further. If there still isn’t a winner, we get this player to place a piece into a cell and then recurse on this function as the other player. Here is how a game runs when using 1 into mkStdGen.

*TicTacToe> let f = readField initialField
*TicTacToe> playGame (mkStdGen 1) Cross f
...
...
...

..x
...
...

o.x
...
...

o.x
...
..x

o.x
...
.ox

oxx
...
.ox

oxx
.o.
.ox

oxx
.o.
xox

oxx
.oo
xox

Game was a tie!

That’s tic-tac-toe.

Next time I’ll add some user interactivity so that the computer doesn’t have all the fun!