Retrospect

While working on converting my name generator from C# to F#, I've come across some strange things.

I mentioned earlier that the statistical analysis portion of my generator counts the number of syllables in its input set in order to use that data to make certain syllables appear more often than others. While looking through my C# code, it appears that this is not the case - I, in fact, am not using that data for anything.

It was my original intention to use it as such, but in retrospect I recall having issues translating this requirement into functionality - especially since I was using SQL Server to perform my random picking. I wonder if I can fulfill this requirement now that I'm using F# and eschewing SQL.

By the way - when I'm done with this project, I'll post up snippets of my F# for review... I'm sure you vets will have plenty to chuckle at! :)

F# progress

Made some progress on my name generator. The statistical analysis side is the hardest part - parsing individual words into their constituent syllables. I am happy to report that after several hours of plugging away, I have a mostly F#-axiomatic syllable parser based on the logic of my C# version. I made gratuitous use of discriminated unions, pattern matching, and recursive functions to write the word parsing logic, rather than OOP and procedural methods similar to what I used in C#. I feel like this has given me a decent grasp on what the language is capable of.

My next task is to continue the statistical analysis portion, and generate syllable boundary data (which is important for the generator to know how to put words together in ways that make sense). After that, the generator itself needs to be written, which should be a simple matter.

The only question at this point that I have is how to handle the SQL database access - much of the logic for generation is embedded in the SQL calls to the database. I'm considering eschewing the database completely and designing my own file-based storage solution, but then I have a whole new class of problems.

In the end, this is going to get compiled as a class library, for consumption in my name generator website (which currently isn't online).

New F# project

Despite the fact that work has intervened in almost all my personal project plans (mostly in the form of making me want to do anything but programming while I'm at home), I still want to learn a new language. F# has been on my radar for a while, especially since it's being included with vs2010. I have been struggling with trying to find something to write in F#, something that I know well enough to be useful as a tutorial for myself, but also something large enough that I'll be able to use most of the idioms in F# that I should need for most any large project.

I had forgotten that, apart from simple expression parsers, I used my Random Name Generator project to learn new languages. My name generator requires text input in order to build statistical data from which random words are generated. It was originally written in Visual Basic 6.0, and was ported to VB.NET, then to C#, in order for me to learn those respective languages. I think it's time to do it again. =)

F# mindblow... simple math expression evaluator

One of the things I typically do when I learn a new programming language is, of course, write a program in it. I try to pick something that will help me understand not just the syntax of the language, but will also help me pick up the style and thinking patterns of the language.

One of the little tasks I typically force upon myself is a simple infix expression evaluator. For the uninitiated, 'infix notation' is the form of notation we humans commonly write our mathematical expression in - that is, the form "a + b * c" etc. Here's a wiki!

Anywho - I decided today was the time for F# to get its own infix evaluator...

Feel free to laugh. I'm laughing at myself, actually - way down inside, in the tiny places, where I harbor my self-loathing and self-doubt, down where I quietly plot my own demise... *ahem*

It took me about 7 hours today to write a total of 95 lines of code. That's ~13 lines of code an hour. Horrible, horrible. Though I'm really not beating myself up as badly as you might think - it took me as long to write this evaluator in VB.NET when I was learning that language (though not nearly as long in C# due to the syntax being the only difference between the languages). I'm just not used to thinking recursively. Sure, I've done recursion in C#, VB.NET, etc., but I've never really used it to replace what would otherwise be imperative-style constructs before. I've only used it when something *had* to be recursive. Also I wanted to adhere to the pure functional programming dogma - zero side effects. This code does indeed adhere to this self-imposed mandate.

Before I post the code, I want to stress that this is *not* optimal code. I know a little about tail recursion, etc., but I *clearly* didn't use it here. I don't even know if I *can* use it here. Also I'm not terribly knowledgeable about the various Seq and List functions that are available, so I probably flubbed them up as well. I don't really care - this works, and I'm proud of it. This is my first major attempt at writing something of any facility in a functional programming language. Also I'd like to mention that I am *very* open to suggestions. If I did something really, truly stupid in here, please call me on it. This is a learning exercise, and I'd like to learn as much as I can from it - part of that is peer review.

So, without further ado, here it is. (Apologies for the different theme - I'm doing this at home and haven't gotten around to installing the darker theme yet.)

    1 #light

    2 

    3 open System

    4 

    5 type operator =

    6   | Add

    7   | Subtract

    8   | Multiply

    9   | Divide

   10 

   11 type token =

   12   | Number of int

   13   | OpenParen

   14   | CloseParen

   15   | Operator of operator

   16 

   17 let tokenize i =

   18   let rec tk s =

   19     match s with

   20     | ' ' :: tail -> tk tail

   21     | '(' :: tail -> OpenParen :: tk tail

   22     | ')' :: tail -> CloseParen :: tk tail

   23     | '+' :: tail -> Operator Add :: tk tail

   24     | '-' :: tail -> Operator Subtract :: tk tail

   25     | '*' :: tail -> Operator Multiply :: tk tail

   26     | '/' :: tail -> Operator Divide :: tk tail

   27     | n :: tail when Char.IsNumber(n) ->

   28       let rec intListToValue (i:int list) acc c =

   29         match i with

   30         | [] -> acc

   31         | n :: tail -> intListToValue tail (acc + (n * int (10.0 ** float c))) (c + 1)

   32       let rec tc (i:int list) (n:char) (s:char list) =

   33         let value = Int32.Parse(string n)

   34         match s with

   35         | n :: tail when Char.IsNumber(n) -> tc (value::i) n tail

   36         | x :: tail -> (Number (intListToValue i value 1)) :: tk (x :: tail)

   37         | [] -> [Number (intListToValue i value 1)]

   38       tc [] n tail

   39 

   40     | [] -> []

   41     | n :: _ -> failwith ("Parse error - invalid character detected: " + n.ToString())

   42   tk (Seq.to_list i)

   43 

   44 let evalTokens input =

   45   let pop2 (stack:'a list) = (stack.Head, stack.Tail.Head, stack.Tail.Tail)

   46 

   47   let eval a b op =

   48     match op with

   49     | Operator Add -> b + a

   50     | Operator Subtract -> b - a

   51     | Operator Multiply -> b * a

   52     | Operator Divide -> b / a

   53     | _ -> failwith "error parsing input"

   54 

   55   let rec eval_rec input numstack (opstack:token list) =

   56     match input with

   57     | Number n :: tail -> eval_rec tail (n::numstack) opstack

   58 

   59     | Operator op :: tail ->

   60       if opstack.Length <> 0 && opstack.Head > (Operator op) then

   61         let firstNum, secondNum, numstackRem = pop2 numstack

   62         let e = eval firstNum secondNum opstack.Head

   63         eval_rec tail (e::numstackRem) (Operator op::opstack.Tail)

   64       else

   65         eval_rec tail numstack (Operator op::opstack)

   66 

   67     | OpenParen :: tail -> eval_rec tail numstack (OpenParen::opstack)

   68 

   69     | CloseParen :: tail ->

   70       match opstack with

   71       | Operator op :: opsTail ->

   72         let firstNum, secondNum, numstackRem = pop2 numstack

   73         let e = eval firstNum secondNum (Operator op)

   74         eval_rec input (e::numstackRem) opsTail

   75       | OpenParen :: _ ->

   76         eval_rec tail numstack opstack.Tail

   77       | _ -> failwith "error parsing input"

   78 

   79     | [] ->

   80       match opstack with

   81       | Operator op :: tail ->

   82         let firstNum, secondNum, numstackRem = pop2 numstack

   83         let e = eval firstNum secondNum (Operator op)

   84         eval_rec [] (e::numstackRem) tail

   85       | [] -> numstack.Head

   86       | _ -> failwith "error parsing input"

   87 

   88   eval_rec input [] []

You call this like so: evaluate "((1 + 2) * 3) / 3" -- this would, of course, evaluate to 3, as expected - it understands and follows the correct order of operations, and respects parenthesis correctly as expected. It doesn't yet handle floats, but I might get around to that at some point. It'll complicate the parsing, but that's not really that big of a deal. The way I'm handling it is weird anyway...

Well there you have it. My first real F# program of any value at all. Despite taking me 7 hours, I'm rather proud of this. It's taught me a great deal, especially that I need to be patient with myself while trying to learn to think in functions. Also, staying pure and functional can be *hard*, especially coming from an imperative / mutable state world. I should also note that my first C# implementation included around 4 times the number of lines of code...

All told, I really enjoyed my dive into F#. My advice to anyone looking into it as a real programming language (and not as a toy) would be to keep an open mind and give it a fair shot.

square root function update and code coloring

Couple things today - first, I did some benchmarking on the F# implementation of my square root approximation function. Truth is, performance sucks, as I figured it would - don't use that code in production! The built-in sqrt function ends up calling the 'fsqrt' assembly opcode, and so is orders of magnitude faster than my code.

Second, thanks to Guy Burstein for the new code syntax highlighting add-in I'm using for the blog. I was using a javascript syntax colorer, but it wasn't working correctly in RSS readers, and it was clunky to use. This new add-in I'm using allows me to copy my source as HTML, preserving the colors as seen in Visual Studio and allowing me to stick with my darker colorings - I'd have had to mess with CSS to get the old javascript colorer to match my settings, and I just didn't have the patience. Also this works properly with C#, F#, XML, HTML - anything VS displays and colorizes. You see it exactly as I see it. =)

Here's a little code sample to demonstrate. This is a little F# function showing off units of measure to calculate the speed at which a body will hit the Earth from a given height in meters, assuming the Earth has no atmosphere... Not terribly useful perhaps but here it is:

    1 #light

    2 

    3 open System

    4 

    5 let out p = Console.WriteLine(p:string)

    6 let inp = Console.ReadLine

    7 

    8 let prompt p = out p; inp()

    9 

   10 [<Measure>] type meter

   11 [<Measure>] type feet

   12 [<Measure>] type mile

   13 [<Measure>] type second

   14 [<Measure>] type hour

   15 

   16 let gAcc = 9.2<meter/second^2>

   17 let feetPerMeter = 3.28084<feet/meter>

   18 let secondPerHour = 3600.0<second/hour>

   19 let feetPerMile = 5280.0<feet/mile>

   20 

   21 let _ =

   22     let i = prompt "Enter a value"

   23     let v = ((float i) * 1.0<feet> / feetPerMeter)

   24     let spd = sqrt (2.0 * gAcc * v)

   25     let spdMpH = ((spd * feetPerMeter) * secondPerHour) / feetPerMile

   26     out ("from " ^ (string (Math.Round(float v, 4))) ^ " meters: ")

   27     out (string (Math.Round(float spd, 4)) ^ " meters/second")

   28     out (string (Math.Round(float spdMpH, 4)) ^ " miles/hour")

   29     ignore(prompt "Press enter to end")

So, enjoy!

F# square root approximation function

So I've been messing around in F#, trying to get a feel for the language, when a suitable challenge crossed my mind while reading an article on neat hacks. In particular, a square root approximation hack used in Quake 3. I'm not going to duplicate that code - what I really wanted to do was make something legitimate, so I went with Newton's Iteration function instead.

The idea is simple - starting with your number, and a guess at the square root of the number, iteratively refine the guess using simple arithmetic until you've decided that your guess is close enough.

Here's my implementation, in C#:

    1 static decimal mySqrt(decimal number, int iterations) {

    2     Func<decimal, int, decimal> rec = null; rec = (guess, iter) =>

    3     {

    4         if (iter == 0) return guess;

    5         return rec((guess + (number / guess)) / 2, iter - 1);

    6     };

    7 

    8     return rec(number / 2, iterations);

    9 }

This implementation uses a recursive lambda function. I could have stuck with a for-loop which would have been more efficient in C#, but my ultimate goal was to use this problem to help me understand F# better. Here's the same function in F#:

    1 #light

    2 

    3 let fsqrt n i =

    4   let rec guess g i =

    5     match i with

    6     | 0 -> g

    7     | _ -> guess ((g + (n / g)) / 2M) (i - 1)

    8   guess (n / 2M) i;;

In both of these functions I'm allowing the caller to specify how many refining iterations to perform. I'm considering writing a method that will determine the fitness of a guess.

I'd like to compare this solution against the official .NET implementation of Math.Sqrt, but unfortunately that function is a stub - it's implemented in MSVCRT by calling the 'fsqrt' opcode, as answered in my StackOverflow question on the subject. If anyone has any more insight into how this works on the processor, please post an answer there - I *really* want to know how it works...

F#, C#, and games programming

I'm making it official. I've decided that I'm going to use F# and C# to create a game.

I'll go into details when I have something concrete to show - but for now, suffice it to say that making this game will teach me a great deal about F#, physics algorithms, DirectX, WPF, and C# -> F# interop. I plan on writing everything from scratch - I don't want to use any existing physics libraries, for example - because I want to do some actual learning.