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.

Adventure game via jQuery, AJAX, and MVC

Next quarter, I'm very likely going to be tasked with starting work on the MVC version of our company's public-facing website. It's going to be a massive undertaking, especially for me given how little I know of the company's system. That's okay though. I'm confident that I'll manage get up to speed in that time. I've already made great strides, if I do say so myself.

Meanwhile, one of the real innovations we're going to join in on is the whole jQuery / AJAX / MVC bandwagon. Personally I think this is great - I'm absolutely in love with all three technologies, especially given how easy they are to integrate together. Smitten though I may be, however, I'm most definitely not as proficient with them as I will have to be in order to pursue an undertaking of this magnitude.

To that end, I've decided I'm going to create a fun little project that will hopefully get me up to speed. I am going to write a little adventure game using jQuery, AJAX, and the ASP.NET MVC Framework. When I say adventure game, think Colossal Cave Adventure or Zork. It's not going to be fancy at all, or probably even all that fun for anyone but myself, but that's not the point. I want to use this as a learning tool - and I plan on posting on my progress and insights here.

I'm thinking about starting an open source project for this so you guys can check out my progress, if you want. Meanwhile, I need to think of a name... =)

Configuration Section Handlers via IConfigurationSectionHandler redux

So, it occurs to me that I was pretty lax with my post last month on Configuration Section Handlers and IConfigurationSectionHandler. Sorry for those of you who came to find information and instead got "wow how easy!" - something of a disservice...

Anyway - IConfigurationSectionHandler is an interface in the System.Configuration namespace that, when implemented, allows your software to define and read custom configuration sections. The idea is that you'll put these configuration sections in your app.config or web.config file and permit configuration that doesn't require recompiling your codebase after making changes.

There is another way to handle custom configuration sections - you could inherit from System.Configuration.ConfigurationSection and provide attributes on your properties that you want to be read from configuration. This approach certainly works - there's a writeup on this approach on MSDN here - but I prefer IConfigurationSectionHandler because it affords me more control over the process, even though apparently its use has been deprecated. =(

The first step before you start touching code is to determine the shape of your XML configuration section. I'll use planets as an (admittedly contrived) example:

    1 <planets>

    2     <planet name="Mercury" distanceFromSun=".38"

    3         diameter="4880" mass="3.30e23" />

    4     <planet name="Venus" distanceFromSun=".72"

    5         diameter="12103" mass="4.869e24" />

    6     <planet name="Earth" distanceFromSun="1"

    7         diameter="12756" mass="5.972e24" />

    8     <planet name="Mars" distanceFromSun="1.52"

    9         diameter="6794" mass="6.4219e23" />

   10     <planet name="Jupiter" distanceFromSun="5.2"

   11         diameter="142984" mass="1.900e27" />

   12     <planet name="Saturn" distanceFromSun="9.54"

   13         diameter="120536" mass="5.68e26" />

   14     <planet name="Uranis" distanceFromSun="19.218"

   15         diameter="51118" mass="8.683e25" />

   16     <planet name="Neptune" distanceFromSun="30.06"

   17         diameter="49532" mass="1.0247e26" />

   18     <planet name="Pluto(?)" distanceFromSun="39.5"

   19         diameter="2274" mass="1.27e22" />

   20 </planets>

This is a pretty straightforward bit of XML. A single root 'planets' element that surrounds nine 'planet' elements, each with some attributes - name, distance from the sun (in astronomical units), diameter in kilometers, and mass in kilograms. The next step is deciding how to represent this in your program. Certainly, you could leave it as XML - there's nothing wrong with that - but in practice I find it more likely you'll want to use an object and its properties to hold and manipulate this data. Here's an example:

    1 public class Planet {

    2     public string Name { get; set; }

    3     public float DistanceFromSun { get; set; }

    4     public int Diameter { get; set; }

    5     public float Mass { get; set; }

    6 

    7     public Planet(string name, float distanceFromSun,

    8         int diameter, float mass) {

    9         Name = name;

   10         DistanceFromSun = distanceFromSun;

   11         Diameter = diameter;

   12         Mass = mass;

   13     }

   14 }

This is pretty straightforward so far. All we need now is a way to go from the XML representation to a collection of Planet instances. That's what IConfigurationSectionHandler is for.

In order to do this, your project will need a reference to System.Configuration, if it doesn't have one already. For our Planets configuration, we'll create a new handler called PlanetsConfigurationHandler and with it implement IConfigurationSectionHandler.

IConfigurationSectionHandler is a very small interface. It contains only one method to implement:
object Create(object parent, object configContext, XmlNode section);
As you can see this method is passed a parent object, a context object, and an XmlNode which represents the section itself. Now, I'm going to be completely honest and say that I have no idea what parent and configContext are for. The section parameter is the only one I'm interested in, and it's the only one I've ever used, so I'm going to say it's pretty safe to ignore them for now.

A word of caution. The Configuration system that is responsible for calling your handler will assume that you're not storing any state in your handler, and that it is thread-safe. This means that you really shouldn't use any external or internal state in the body of the Create method. You should assume that your handler will be called multiple times per instance, in random order.

So by this point, all you need to do is write your XML parsing code. For the sake of sanity and simplicity, I'm going to convert this old 1.0-style XmlNode object into a 3.5-style XDocument object, and work with it from there. I prefer to keep up with the current developments in programming languages. If you can't use 3.5 for whatever reason... well, there are plenty of System.Xml references available out there. You're resourceful, you'll find something. ;)

Here's my handler:

    1 public class PlanetsConfigurationHandler

    2     : IConfigurationSectionHandler {

    3 

    4     public object Create(

    5         object parent, object configContext, XmlNode section) {

    6 

    7         XDocument doc = XDocument.Parse(section.OuterXml);

    8         XElement root = (XElement)doc.FirstNode;

    9 

   10         IList<Planet> rList = new List<Planet>();

   11 

   12         foreach (var element in root.Elements() ) {

   13             if (element.Name != "planet")

   14                 throw new ConfigurationErrorsException(

   15                     "planets section only accepts" +

   16                     " 'planet' elements.");

   17 

   18             try {

   19                 string name = element.Attribute("name").Value;

   20                 float distanceFromSun =

   21                     float.Parse(

   22                         element.Attribute("distanceFromSun").Value);

   23                 int diameter =

   24                     int.Parse(

   25                         element.Attribute("diameter").Value);

   26                 float mass =

   27                     float.Parse(

   28                         element.Attribute("mass").Value);

   29 

   30                 Planet newPlanet =

   31                     new Planet(name, distanceFromSun, diameter, mass);

   32 

   33                 rList.Add(newPlanet);

   34             } catch (Exception ex) {

   35                 throw new ConfigurationErrorsException(

   36                     "Error reading planet element."

   37                     , ex);

   38             }

   39         }

   40 

   41         return rList;

   42     }

   43 }

Please excuse the weird formatting - I don't want the code lines to wrap.

So - pretty straightforward. I take the XML section data and using the XDocument elements I parse it for its content. A couple things to notice here: I'm assuming that the root element is correctly named 'planets' - in fact, it's possible it'll be named something else - you'll see how later - so I'm trusting here that the configuration system has passed me the correct section. We'll go with that for now. Second, I am doing some validation on the inner xml - none will be done for me - and I'm making sure that the only thing in my configuration section are 'planet' elements. Third, I've wrapped the rest of the body of the iterator in a try/catch block. I'm using .Parse methods which will throw an exception if the string they're trying to parse is null or malformed - I catch that exception, then throw a ConfigurationErrorsException, passing in the original exception in its constructor to preserve context. This will allow callers of your library to understand what went wrong, when something does.

We've got one last thing to do in order to actually *use* this handler. You've got to register it with the configuration system by adding a bit of XML in the 'Configuration' section:

    1 <configSections>

    2     <section

    3       name="planets"

    4       type="ConfigDemo.PlanetsConfigurationHandler, ConfigDemo"/>

    5 </configSections>

This should be pretty much self-explanatory. This bit of XML tells the configuration system that you've got a custom handler that will handle any sections named 'planets'. Earlier I mentioned that it's possible to use an arbitrary name when dealing with a configuration section. Well, this is where that name is selected. If you change the 'name' attribute's value here, you'll have to use the same value for the name of the section itself - that is, the root element of the section's XML. You'll also need to use that name when you retrieve the section itself - which brings me to my final bit of code:

    1 class Program {

    2     static void Main(string[] args) {

    3         var planets =

    4             (IList<Planet>)

    5             ConfigurationManager.GetSection("asdasd");

    6 

    7         string planetTemplate = "{0}: {1}au, {2}km, {3}kg";

    8 

    9         foreach (var planet in planets) {

   10             Console.WriteLine(

   11                 string.Format(planetTemplate,

   12                 planet.Name,

   13                 planet.DistanceFromSun,

   14                 planet.Diameter,

   15                 planet.Mass)

   16             );

   17         }

   18 

   19         Console.ReadLine();

   20     }

   21 }

This is a console application that retrieves the configuration section 'planets' from App.config, then displays the planets on the console. Very simple. Notice that we need to cast the return from ConfigurationManager.GetSection to the type we expect to receive - that method returns 'object', which is to be expected since it couldn't possibly know what type to expect your handler to return. Once you've got your data out of configuration, it's up to you to decide what to do with it.

So, that's that. I do however have one last thing to say. I've been getting into functional programming quite a bit, and as such I like to exercise those newly-forming muscles any chance I can get. As I mentioned above, the Create method needs to avoid internal or external state. Any time it is given an input (the xml configuration section) it should provide the same output. This sounds an awful lot like it needs to be a pure function, to me - so let's change the method to make it a little more obvious that that's what we're going for:

    1 public class PlanetsConfigurationHandler

    2     : IConfigurationSectionHandler {

    3 

    4     public object Create(

    5         object parent, object configContext, XmlNode section) {

    6         XDocument doc = XDocument.Parse(section.OuterXml);

    7         XElement root = (XElement)doc.FirstNode;

    8 

    9         if (root.Descendants().Any(e => e.Name != "planet"))

   10             throw new ConfigurationErrorsException(

   11                 "planets section only accepts" +

   12                 " 'planet' elements.");

   13 

   14         try {

   15             return

   16                 (from p in root.Descendants()

   17                 let newPlanet = new Planet(

   18                     p.Attribute("name").Value,

   19                     float.Parse(p.Attribute("distanceFromSun").Value),

   20                     int.Parse(p.Attribute("diameter").Value),

   21                     float.Parse(p.Attribute("mass").Value)

   22                 )

   23                 select newPlanet).ToList();

   24         } catch (Exception ex) {

   25             throw new ConfigurationErrorsException(

   26                 "Error reading planet element."

   27                 , ex);

   28         }

   29     }

   30 }

Whoa. Way different - and yet the functionality is the same. Much fewer lines of code here, as well. I'll leave it as an exercise to the reader to work this out, if it's not already apparent - it's not a very tough query, really. I have faith. :)

Good luck with your own IConfigurationSectionHandler implementations - feel free to shoot me any questions you may have about the process, and I'll answer as best I can.

Hatin' on GOTO

So, it's general consensus that the GOTO statement (in any form) is evil, wrong, bad, no-no, etc. There's a fairly famous piece by Edsger Dijkstra entitled Go To Statement Considered Harmful in which he asserts that "the go to statement should be abolished from all 'higher level' programming languages."

There are a myriad of evil uses for the GOTO statement, in any language, it's true. My early days of programming were riddled with spaghetti code issues, especially once any of my far-too-ambitious projects attained a sort of critical mass. I remember in my early days of QuickBasic getting to around 15k lines of code (all in one huge Sub) being absolutely mystified as to why I could never finish anything...

I eventually grew up a bit, and as I encountered Visual Basic (at around version 3) I came to much the same conclusion as Mr. Dijkstra did; that the GOTO statement was the single greatest cause of error and confusion in software programming.

Looking back now, however, that might have been an error.

The problem isn't necessarily with the GOTO statement in and of itself, but rather with the willingness of the programmer to use the GOTO statement as a quick-fix way to get out of a sticky situation. In my QB days I indulged in this particular sin with impunity, only to wonder why my projects self-destructed not even a third of the way in.

The crime I committed was not in using GOTO, but rather in using GOTO incorrectly, and for incorrect uses. GOTO for me was a hammer, and all my program logic flow problems were nails - I wasn't shy in applying my tool - however to place the blame for my failings on the GOTO statement is a deception.

GOTO is a tool. It is a useful tool, sharp, though perhaps diminished in this age of WHILEs, DOs, FOREACHes, and the like, but still useful nonetheless. Be aware of its danger, however, in that it allows you to fall into your own traps. But should it be abolished because it is such a sharp tool?

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.