Applications

Converting a ByteString to a Double using FFI

Submitted by mrd on Tue, 12/18/2007 - 3:36pm.

ByteString, the ever-useful fast string library, has some nice functions for reading Ints which make reading in test data a breeze. However, there's no similar function for Doubles which has caused some recent troubles for me when dealing with floating point data. The C library has a function for this task: strtod. So I decided to take some older but similar FFI code and mold it into an interface to strtod.


{-# LANGUAGE ForeignFunctionInterface #-}
import Foreign
import Foreign.C.Types
import Data.ByteString.Base


foreign import ccall unsafe "stdlib.h strtod"
c_strtod :: Ptr Word8 -> Ptr (Ptr Word8) -> IO CDouble


strtod :: ByteString -> Maybe (CDouble, ByteString)
strtod str = inlinePerformIO .
withForeignPtr x $ \ p ->
alloca (\ p_endptr -> do
let p_s = p `plusPtr` s
n <- c_strtod p_s p_endptr
endptr <- peek p_endptr
let diff = endptr `minusPtr` p_s
if diff == 0
then return Nothing
else return $ Just (n, PS x (s + diff) (l - diff)))
where (x, s, l) = toForeignPtr str

The type is chosen in particular to be convenient for usage with unfoldr.

The code probably looks more complicated than it is. Since ByteStrings are really stored as ForeignPtr Word8 (along with start-offset and length), it is easy to grab the raw form for usage by C functions. withForeignPtr lets you manipulate the raw Ptr Word8 within a function. Pointer arithmetic is performed using functions like plusPtr. The second parameter to strtod is actually an "out" parameter which sets a pointer to the spot it finished reading. I allocate space to store a pointer, namely a Ptr (Ptr Word8) and Haskell can figure out how much space it needs from the inferred type. I peek to retrieve the "returned" end-pointer. Then it's just a matter of putting back together the ByteString (PS for "Packed String") with the new offset and length.

Is logging really this tuff with Haskell?

Submitted by metaperl on Thu, 11/08/2007 - 3:35pm.

I quote: http://programming.reddit.com/info/5ze57/comments

Haskell is too weird for me (if I want to add a logging statement, I don't want to rewrite ten functions to use monads instead of the types they previously had).

The algorithm for Discordian text encryption

Submitted by metaperl on Sun, 11/04/2007 - 10:25am.


module Crypt_Discordian
where

import List

vowel_list = "aeiouAEIOU"

is_vowel c = c `elem` vowel_list

move_vowels lis = move_vowels' lis [] []

move_vowels' [] c v = v ++ c
move_vowels' (x:xs) c v
| is_vowel x = move_vowels' xs c (x:v)
| otherwise = move_vowels' xs (x:c) v

remove_spaces str = filter (\x -> x /= ' ') str

encrypt str = List.sort $ move_vowels $ remove_spaces str

{-

The algorithm for Discordian text encryption is given at:

http://www.principiadiscordia.com/book/78.php

After implementing this, I realized that all the early steps are a farce.

But anyway, here is the algorithm in case you don't enjoy tilting your
head to read a page:

Step 1. Write out message (HAIL ERIS) and put all vowels at the end
(HLRSAIEI)

Step 2. Reverse order (IEIASRLH)

Step 3. Convert to numbers (9-5-9-1-19-18-12-8)

Step 4. Put into numerical order (1-5-8-9-9-12-18-19)

Step 5. Convert back to letter (AEHIILRS)

This cryptographic cypher code is GUARANTEED TO BE 100% UNBREAKABLE

.. so says the Principia Discordia. But I think we can generate and
test to break it.

Many thanks to kosmikus and Pseudonym for their help in developing
this module

-}

{-

Discordians. They are a
group of people who believe that spirituality is as much about
disharmony as it is about harmony.

So, in their primary book, Principia Discorida:

http://principiadiscordia.com/

you never know what is serious and what is play. The wikipedia has
more to say on them:

http://en.wikipedia.org/wiki/Discordian

-}

Revisiting board-building in chess

Submitted by chessguy on Sat, 08/18/2007 - 12:42pm.

So, in my last blog, we looked at the beginnings of a chess engine. That was nearly 2 months ago. I've been kicking around some possibilities for the last few months, trying to come up with a somewhat elegant solution. Ultimately, I've wound up completely refactoring what I started with. I'll be posting more on that here within the next few weeks, but I'm really excited by how one piece came out, so I'd like to show that part at least.

Last time, I mentioned FEN notation for the state of a chess game. Let's look at that in a bit more detail. Here's the FEN notation for the start of a game:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

You can see, there are 6 space-separated fields in this string. What I want to write is this function:

loadFEN :: String -> GameState

...which constructs the state of the game from the FEN. Now, this is notoriously tedious in most languages, but the solution in haskell looks quite elegant to me.

So, let's see. Each field in the FEN is going to tell us something about how to construct the GameState. The first field tells us where the pieces are, the second tells us whose turn it is, the third deals with castling statuses, etc. So we can start with an empty state, and apply multiple functions to it, based on the fields, to build up a new state. That sounds like a fold pattern to me!

However, this seems to be a bit tricky at first. We'll want to apply a different function for each field. That is, the first function will look at that first field and build up the actual squares on the board with pieces. The second function will parse the indicator of whose turn it is, and make that change to the state, etc. So let's start by zipping these functions up with the fields they correspond with:

loadFEN fen = foldl apply emptyGameState (zip funcs fields)
    where fields = words fen
          funcs = [parseBoard, parseCastleStatus]

Here, I've just listed the functions for the first 2 fields, to give us an idea. The only mystery that's left is this apply function. Let's look at its type:

apply :: GameState -> (String -> GameState -> GameState, String) -> GameState

That is, it takes a current state, and a pair, consisting of a function and a field to apply it to, and a field, and returns a new state. Well, that's not so bad:

apply state (function, field) = function field state

Running this through the @pl formatter on lambdabot in #haskell gives us an ugly mess:

apply = (`ap` snd) . flip (flip . fst)

Hmm, this is interesting though, look at the flipping going on. What if we took the input in a different order? Suppose we wrote this:

apply (function, field) state = function field state

Running this through @pl gives the very elegant:

apply = ap fst snd

Thus, the final code winds up being:

loadFEN :: String -> GameState
loadFEN fen = foldl apply emptyGameState (zip funcs fields)
    where fields = words fen
          apply = flip (ap fst snd)
          funcs = [parseBoard, parseCastleStatus]

Very nifty! Now all the real work gets moved off to smaller functions, which just have to worry about the particular field they're designed to work with. Not only that, but if I only want to deal with the first few fields for now, they're the only ones I have to parse, and I'll still wind up with a valid GameState.

Chess in Haskell

Submitted by chessguy on Thu, 06/28/2007 - 9:30pm.

I thought that since chess AI is (or, at least, has been) a hobby of mine, it would be fun and educational to write one in Haskell. And if I'm going to do that, I figure I may as well blog about it!

A few preliminary matters before I dive into the code. First, I make no promises as to how often I will add to this blog. A chess AI is a long project, and I don't currently have a ton of time to devote to it. Second, I intend to start very simply, and inefficiently, with data structures that I know can be improved on. Part of the fun will be refactoring it later. Finally, I fully admit to being a novice Haskeller. I've been studying it for a year or so now, but still struggle with things I should have mastered long ago. Suggestions are highly desirable.

Ok, let's do this! First, a few definitions:

type Board = Array Int Piece

data Piece = Piece Color PieceType
data Color = White | Black
data PieceType = Pawn | Knight | Bishop | Rook | Queen | King

We represent a board as a simple array, indexed by Ints. This gives us O(1) access to any square. This is one area that I guarantee I will come back to, but it's simple enough to start with. Board representation is a HUGE issue with chess AI, and there are many, many things we can try with it. Anyway, we'll use a standard convention, which is to number square A1 (the square closest to white, on his left) as square 0, and H8 (on black's left) as 63. That is, the board will look like this (leading 0's added for spacing only):
BLACK
56 57 58 59 60 61 62 63
48 49 50 51 52 53 54 55
40 41 42 43 44 45 46 47
32 33 34 35 36 37 38 39
24 25 26 27 28 29 30 31
16 17 18 19 20 21 22 23
08 09 10 11 12 13 14 15
00 01 02 03 04 05 06 07
WHITE

Now a few useful little things:

emptyBoard :: Board
emptyBoard = array (0,63) []

piece :: Char -> Piece
piece c = Piece color pType
where color = if (isUpper c) then White else Black
pType = case (toUpper c) of
'P' -> Pawn
'N' -> Knight
'B' -> Bishop
'R' -> Rook
'Q' -> Queen
'K' -> King

addToBoard :: Piece -> Int -> Board -> Board
addToBoard piece loc board = board // [(loc, piece)]

An empty board is trivially defined as an integer within the proper range, and with no associations. I'll note here that I've never really dealt with arrays in haskell, so this will be a learning process. I already like the fact that creating an empty array is so intuitive. The piece function is a simple constructor for Piece. It follows a typical chess convention for denoting pieces: uppercase means white, lowercase means black. More on chess notation in a moment. addToBoard adds a piece to the board. Again, it's very simple and elegant-feeling.

Now comes the fun part for this entry:

loadFEN :: String -> Board
loadFEN = loadFEN' 56 emptyBoard

loadFEN' :: Int -> Board -> String -> Board
loadFEN' _ b (' ':xs) = b
loadFEN' _ b "" = b
loadFEN' n b ('/':xs) = loadFEN' (n-16) b xs
loadFEN' n b (x:xs) | x `elem` ['1'..'9'] = loadFEN' (n + (digitToInt x)) b xs
loadFEN' n b (x:xs) = loadFEN' (n+1) b' xs
where b' = addBoard (piece x) n b

Chess has this awful thing about notation. There are a few different ones (particularly for move representation), and they tend to be pretty awful. This function is to convert a string, in a notation called FEN, to an instance of our board data structure. a description of FEN can be found here . Suffice it to say, this is a tedious process to do in any language. In fact, the above function is very elegant compared to many languages. Essentially, we're simply looping through the string, while keeping a reference to the next square on the board that we're going to put a piece on. Since FEN starts with the square on black's right, we start on square 56 (see above diagram). We'll assume for now that the FEN is well-formed.

If you notice from the Wikipedia article, there are several fields to FEN notation. For now, we'll just deal with the first, and longest field, which tells where the pieces are. We'll come back to the other fields later. Thus, if the first character of the string is a space, or if the string is empty, then we're done, and we can simply return the board. If it's a slash, we've reached the end of a row, and we need to move the board reference to the beginning of the next row, then process the rest of the string. If the first character is a digit, it indicates some empty squares, so we'll simply adjust the board reference again. Finally, the only option left, is that we're looking at an actual piece, in which case we need to construct the piece, add it to the board, and process the rest of the string.

I think that's enough for this entry. Next time: move generation!

I've seen the J and the C, how about the Haskell?

Submitted by metaperl on Fri, 03/30/2007 - 1:38pm.
Some swarthy Haskell'ing lad needs to step up to the plate on this one. How would Haskell do this? We simply want the column of the maximum value of the array.

C Language

int i, j, maxcol = 0;
float maxval = x[0][0];

for(i = 0;i<=xsize0;++i) {
  for(j = 0;j<=xsize1;++j) {

    if(x[i][j] > maxval) {
      maxval = x[i][j];
      maxcol = j;
    }

  }
}
J Language
maxcol =. (i. >./) >./ x

My that J code is quite concise ... so now we need to see that H language ... heheh.

My recent Factor travels in Light of Haskell

Submitted by metaperl on Sat, 02/24/2007 - 3:46am.

Factor is a modern stack-based language. It has a very interactive and easy-to-use GUI and is fun to work with.

Something was itching me about using this language and it was not until I picked up Haskell Road to Logic Maths and Computer Programming that I knew what was bothering me. He says that _Haskell_ is a type of descriptive programming very different from the prescriptive programming that you see in Java or C.

And that's it. In Factor, one is very mechanical. putting things on the stack, duplicating stack items. Hiding things in a retain stack, etc.

I notice that a lot of Factor functions for stack shuffling scale up to 3 stack elements. Is there something magic about this number of args to a word that it would never have to shuffle on more?

A very telling example of the difference in Haskell and Factor has to do with
this page on the Factor website discussing how to determine if all elements of a sequence obey a boolean:

The word "all"
Tests if all elements in the sequence satisfy the predicate.

The implementation makes use of a well-known logical identity:

P[x] for all x <==> not ((not P[x]) for some x)

Let's compare the Factor and the Haskell:

Factor

: all? ( seq quot -- ? )
    swap [ swap call not ] contains-with? not

Haskell

all p =  and . map p

conclusions

The author of Factor is a very strong mathematician... what provoked him to involve himself in stackrobatics (acrobatics with a stack)?

Haskell Factor again

Submitted by metaperl on Thu, 02/01/2007 - 1:55pm.

HaskelL

map putStrLn $
map (\(a,b) -> "Index: " ++ (show b) ++ "element: " ++ a) ( zip ["a" , "b", "c"] [0..] )

Factor


{ "a" "b" "c" } dup length [ "Index: " write . "Element: " write . ] 2each

CONCLUSION

Draw your own conclusions :)

Factor and Haskell comparison

Submitted by metaperl on Thu, 02/01/2007 - 11:23am.

Haskell

let sq = (\x -> x * x) in map sq $ map sq [1 .. 3]

Factor

{ 1 2 3 } [ sq ] map [ sq ] map .

Haskell 2

let sq = (\x -> x*x) in map (sq . sq) [1..3]

Factor 2

{ 1 2 3 } [ sq sq ] map .

Factor 3

3 [ 1+ sq sq ] map .

CONCLUSION

One interesting thing is that no new language mechanisms were necessary in Factor. In Haskell, one had to know $ and the composition operator . as well a varioius precedence rules to make clean concise code.

Haskell Xcode Plugin

Submitted by humasect on Mon, 01/08/2007 - 2:46pm.

Thanks to Damien Bobillot for writing the Objective Caml plugin, and his efforts in researching the Xcode plugin API interface, I've written in the last week, an Xcode plugin for Haskell.

Thanks to everyone for their direct and indirect support.