Conversations II: Closures and Events

Ive been meaning to continue the post from last time but havent really had the time.

Having tested that the conversation structure could be easily deconstructed I decided to check how it would work in a more graphicy environment. But I had no game or graphics engine to use. So I decided to knock up something quickly using WinForms and GDI+. Most of the test code was held in the form and another class meant to read into the conversation data structure. Since much of a game deals with handling and working with various representational data structures, working in a language which can easily manipulate such makes many implementation details quite straight forward. A quick aside first.

One of my coding peeves is having to write nested for loops. So I decided to write a macro that was syntactic sugar inspired by list comprehensions. List comprehensions are a way of building lists that borrows from mathematical setbuilder notation. For example this is the set of all numbers whose squares are even : . Similarly such a list can be built using list comprehensions: [x | x <- [0..], x ** 2 % 2 == 0]. Something like this would be good for building sequences of operations which you wish to occur during certain conditions or are in nested loops. Also I wished to experiment further on with Nemerle macros. I was able to write a dozen line macro which allows the following code:

seq [ WriteLine(x), x in [0 .. 10], even(x) ]

Here seq takes a single expression and the conditions under which it should be run. Thus its definition is: seq[expr,list[expr]]. Being able to only take a single expression is not very flexible but there are work arounds. For example, instead of passing an expression I could pass a function:

def times9(z){def k = 9; WriteLine(k*z)}
seq [ times9(x), x in [0 .. 10], even(x) ]

The function passed thus allows sequences expressions of arbitrary complexity to be built. As well, so a function does not have to be written always, I also wrote a macro which itself looks like/is a single expression that takes a list of expressions and converts them to executable expressions: dothis[list[expr]].

seq [ dothis [mutable y = x, 
                      WriteLine(x*y)], x in [0 .. 10], even(x) ]
Output:
0
4
16
36
64
100

Thus either a function, a statement, or a list of statements converted treated like an expression using the dothis macro can be fed into seq to create simple to reason about but interesting combinations of nested loops and conditionals.

During compile time the following:

seq [ e.Graphics.DrawImage(grass, Point(x ,y )), x in [0,grass.Width..640], y in [0,grass.Height  ..480] ]
               
is expanded into:
    foreach(y in [0,grass.Height  ..480])
                foreach(x in [0,grass.Width..640])
                    e.Graphics.DrawImage(grass, Point(x ,y ));

To continue, in the form there are the following declareations:

mutable playerpos : Point 
hc : HandleTalk 
[Accessor (flags = WantSetter)] mutable isTalking : bool
[Accessor (flags = WantSetter)] mutable writing : string

In the onpaint event the grass is drawn and two images, a mage and a soldier, represented by you. Its position is altered on the KeyDown event. As well, when isTalking is true a blue rectangle is drawn as well as the text held in the writing Field.

when(isTalking)
                e.Graphics.DrawRectangle (Pen(Color.White), Rectangle(9, 9, 465, 151));                
                e.Graphics.FillRectangle (SolidBrush(Color.FromArgb(180,0,0,255)), Rectangle(10, 10, 464, 150));  
                e.Graphics.DrawString(writing , Font("Verdana",10),SolidBrush(Color.White), RectangleF(10,10,464,150))
...
private MainForm_KeyDown (sender : object,  e : System.Windows.Forms.KeyEventArgs) : void           
             
            unless(isTalking)             
                match(e.KeyCode)
                    | Keys.Down => playerpos.Y+= 20
                    | Keys.Left => playerpos.X-= 20
                    | Keys.Right => playerpos.X+= 20
                    | Keys.Up => playerpos.Y-= 20
                    | Keys.Space => 
                                        when(((400 - playerpos.X) ** 2)  + ((190 - playerpos.Y) ** 2)  < (100 ** 2))
                                           isTalking = true;  
                                           writing = hc.interact( Conversations.Guy1.Hello, this);
                    | _ => ();

The player cannot move when talking. When the space bar is pressed it checks if the player is near where I hardcoded the “mage”. If it is, converstion is initiated and the form is passed to conversation handler.

The HandleTalk class is similar to the one demonstrated in the last post.

class HandleTalk
GetResponses (ConversationList : list[string * (Npc->Conversation)], ResponseList : list[Npc-> Conversation], i : int, output:StringBuilder) : StringBuilder *list[Npc -> Conversation]
match(ConversationList)
| anItem::restOfList => def (theString, theFunction) = anItem;
output.AppendLine($”( $(i.ToString()) ): $theString”)
GetResponses(restOfList, theFunction::ResponseList, i + 1, output)
| [] => (output, ResponseList)

public interact(c : Npc -> Conversation, f : MainForm) : string

def interinner(ci,fi)
def p = Npc()
p.Name = “Daerax”
def hi = ci(p);

def resps = hi.arrows;
def l = GetResponses(resps, [], 1,StringBuilder($”$(hi.initial)\n\n”));
l[0].AppendLine($”( $( (l[1].Length+1).ToString()) + ) : $(hi.terminal()) \n”)
l

def dat = interinner(c,f)
def sayThis = dat[0]
mutable listOfOptions = dat[1]
def allowed = [“0″,”1″,”2″,”3″,”4″,”5″,”6″,”7”, “8”, “9”]
def capture(o : object , e: Windows.Forms.KeyPressEventArgs)
match(listOfOptions.Rev())
| [] => f.IsTalking = false; f.KeyPress -= capture;
();
| xs => seq[dothis[ def k = interinner(xs.Nth(select), f), //Conditions
f.Writing = k[0].ToString (),listOfOptions = k[1]], e.KeyChar.ToString() -> chara ,allowed.Contains(chara),
(int.Parse(chara) – 1) -> select,select < xs.Length] f.KeyPress += capture sayThis.ToString () [/source] What it does is when interact is first called it creates a closure about the function interinner. It then adds the function capture to the keypress event of the form which is called whenever a key is pressed. Thus whenever a key is pressed our closure remembers the last value of listOptions, calls our function representing the response, changes the contents of the writing field apropriately and exits. When the conversation is done the function is disconnected from the keypress event. This allows the rest of the world to go on without being held up by the conversing people. Note also the sequence in the second match: [source lang="python"]seq[dothis[ def k = interinner(xs.Nth(select), f), //Conditions f.Writing = k[0].ToString (), listOfOptions = k[1]], e.KeyChar.ToString() -> chara ,allowed.Contains(chara),
(int.Parse(chara) – 1) -> select,select < xs.Length] expands to: def chara = e.KeyChar.ToString(); when(allowed.Contains(chara)) def select = int.Parse(chara) - 1; when(select < xs.Length) def k = interinner(xs.Nth(select), f); f.Writing = k[0].ToString () ; listOfOptions = k[1][/source]The -> operator for assignment is not part of the language, nor in fact defined as a macro, it is actually only matched when the seq expression is deconstructed.

Conversations

My last post was a prelude to this. This weekend I decided to I decided to tackle scripting in a game engine. Specifically being able to talk to an entity and having a flexible system which if necessary could handle Planescape level of jabbering complexity. Originally, I had thought to perhaps use a graph structure in conjuction with some IronPython to do this.

However, I decided why not just have the conversation structure be written in Nemerle as well. Then instead of various scripts and structures to be built at runtime I’d have a compiled dll which could be called into with the added benefit of having also been statically/compile time verified. I also wanted to experiment with how programming in a functional language would aid in game programming. For I have not actually deen any real game related programming that actually used these concepts (really i havent done anything beyond getting irrlicht to load some models in years). As well I wished to try out some of my ideas of Nemerle as a host language for a game. Of course I have no game engine so I decided to do some console based testing.

First I considered the most basic representation of a conversation as both a statement and the set of responses associated with the statement. I also wanted this model to be simple to extend. To start, I decided statements are of type string and responses can be of type () -> string. So each response is a function which when invoked returns the string to be displayed. This of course could not be implemented without entering into circular dependencies so I decided to create a Conversation type/class.

A conversation contains an initial object of type string, (for all c in C, i -> c does exist, sometimes via composition) a terminal object of type () -> string and arrows of type list[string * (Npc -> Conversation)]. I defined it this way in case I ever wanted to create a category theoretic treatment of conversations I had a loose analogy already in place.

So it looks like this:

public class Conversation
        public this()
            ()
        public this(s : string)
            initial = s
        public this(s : string, t : response)
            initial = s
            terminal = t
            
        public mutable initial : string
        public mutable terminal : response
        public mutable arrows : list[string * (Npc -> Conversation)]

Then conversation is always initiated with intial and can be ended at any time with terminal. Initial is then written out with arrows holding the list of responses (a list of functions) that will take one to another conversation and string displaying the current statement. This was then wrapped in a dll. All the conversations would then be held in one or more dlls. As a test I created a module to represent conversations that could be interacted with. The code goes:

namespace Conversations
    public module Guy1
        public Hello(n: Npc) : Conversation     
 	    def k = Conversation()
	    def k.initial = $"Hello $(n.Name), My name is Joe."
            def k.terminal = Bye
                       
            k.arrows = [("What are your plans", Future), ("How is life?",Terrible)]
            k              
        
        Future(n: Npc) : Conversation
            def k = Conversation("The future is a terrible place")
            def response1 = "Why?"
            def response2 = "What is your name?"
            
            k.terminal = Bye
            k.arrows = [(response1,Terrible), (response2,Hello)]            
            k       
           
	...
            
        Bye(): string       
            "Bye"

Then I could go Guy1.Hello() to initiate conversation and extract the required responses. Next I decided to code a DSL that would make conversations clearer to read. Based on the original code I decided a simple language that mostly served to remove boiler plate code and also make conversations clearer would do.

Nemerle has macros which allow one to do metaprogramming. Not C style but scheme like hygenic macros. The metaprogramming is in two or three parts. The first is of a style that people who have done C++ template metaprogramming would recognize. Namely various compile time execution of certain code that allow various optimizations and new behaviours. The other type is akin to MetaML or Template Haskell and Scheme. Which is the ability to operate on the language’s syntax tree using the language itself and to do various bits and bobs e.g. modify/auto generate code. It also has flexible syntax extension. It is also motivated by MetaML in the idea of having typed code and the notion of execution staging. Being able to operate on, pass around and modify code at compile time is a really nice concept that makes the language flexible. I am experimenting with extending this into runtime – is quite possible.

To continue I arrived at a small set of keywords based on what I had experienced: TlkOf, EndOn, ResponsesOf, Linkers,In, Is, intl, tmnl, put and sc_. sc_ is a short hand macro whose use is sc_[var, string, () ->string]. Which is equivalent to var = Conversation(string); var.terminal = () -> string. Here is a snippet acting as a test:

[Fp] Hello() : ifr 
                    
            TlkOf cnv 
                $"Hello $(n.Name), My name is Joe." 
            EndOn Bye
                       
            ResponsesOf cnv 
                ["What are your plans", "How is life?"]
            Linkers [Future, Terrible]   
[Cp] Terrible() : ifr
                       
            def k = Conversation($"I am dead, $(n.Name)")
            
            tmnl k Is Bye;
            put [] In k.arrows 
            k

A few things to explain are ifr and the [Cp], [Fp] tags. These names are tentative and are attributes that modify the compile time behaviour of the code. Nemerle does not have top level type inference so having to do all that annotating is annoying, especially as the number of parameters I wish to pass each conversation object increseases. ifr is just a type alias for void and is only there to reduce key strokes…

The Cp means conversaton path, it takes the body of the method, generates a new method with the same body as the old one but also binds whatever parameters to the method I require so I do not have to explicitly declare them in the conversation script – for now just n of type Npc (but will eventually be whatever other ones I decide to add later, this is useful because then scripts automatically benefit and functions wont break when i introduce new parameters – although i might do a few overloads for arrows) and makes the method of type Conversation and makes it public. It then clears the old method. Fp does the same but also initializes cnv (bound to the site) to Conversation() and makes sure the method returns cnv so I dont have to type that. When one decorates their methods with those attributes they must realize also be aware of what variables names have been bound (controlled unhygenics). Ofcourse their use is optional. The dsl thing is abt 50 lines of code. I have the Visual studio integration so I get free syntax highlighting as well.

To actually load the conversation I simply recurse through the paths till I terminate.

Module Program
  Main() : void 
    def p = Npc();
    p.Name  = "Daerax"    
    
    def say (b, l, i) : list[Npc -> Conversation]
        match(b)
            | s::ss => def (a, d) = s;
                        WriteLine($"( $(i.ToString()) ): $a" )
                        say(ss, d::l, i + 1)
            | [] => l  
                         
        def interact(c)
        def hi = c(p);
       
        WriteLine($"$(hi.initial)\n")
        def resps = hi.arrows;
        def l = say(resps, [], 1).Rev();
        WriteLine($"( $( (l.Length+1).ToString()) ) : $(hi.terminal()) \n");    
        def o = int.Parse(ReadLine());
        match(l)
            | [] => ()
            | xs => interact(xs.Nth(o-1))
    def k = 0;               
    interact(Guy1.Hello)

 public class Npc
        health : int 
        pos : position2D
        public mutable race: string
        [Accessor (flags = WantSetter)] mutable name : string;

Thinking Out Silent

Some people like to code at a low level, I am not a member of that set. I prefer programming at an abstracted higher level. Being able to do more with less to me is both a time saver and a fun puzzle to solve. Not a time saver in the sense of having typed less code but in time saved from having to later hunt down obscure unpredicted behaviour. This statement by Carl Gauss applies here too: “You know that I write slowly. This is chiefly because I am never satisfied until I have said as much as possible in a few words, and writing briefly takes far more time than writing at length.” Most of my time is spent fixing compiler errors and those rarely amount to much. Usually if it compiles then it works. Any runtime errors are usually due to flaws in my logic which are so far without fail readily visible and transparent,not dulled and buried within layers of implementation. I remember once, when i used to try C++, hitting the run button was a frightening thing to do. I am glad those days are behind me.

On the other hand there is nothing inherent about C++ that makes it an unadvisable language for beginners or in general. Only within context can such a statment be considered. There was a time when C++ was a higher level language and made more sense as a beginner language (but not as much sense as Pascal or Basic) than it does today. But times have changed (and C++ hasnt aged well its become fat and loud) environments have gotten more complex and unless you are doing some proper systems programming there is no need to hanker yourself down worrying about every little detail of memory managament*, proper use of pointers or detailing every little thing of what you want done and other bit twiddling inanities. There are more important things to concern onesself with.

Eating NP-Completely in McDonalds Again

Some time ago I wrote about using the knapsack algorithm to make my spendings in McDonald’s as efficient as possible. Ive actually used this program fairly often and it has proven surprisingly useful. However the program always left a certain taste of dissatisfaction in me. Namely, due to how i encoded my value function certain inputs of money e.g. £3.56 gave silly outputs like: Fries,Fries,Fries,Fries. So I returned to the program this weekend. But first some background.

What is the Knapsack Algorithm?

The knapsack problem is a problem in optimization. It is often presented as a problem faced by a thief with a certain sized bag. A thief with a bag of size S breaks into a house. There are items of different sizes and values, what items must the thief take to maximize the value of the items in his bag? Or mathematically: Maximize

with

Where for the t types of items, v_i is the value of each type of item, s_i is size and x_i is the number of each kind of item.

One way to solve this is to use something called dynamic programming where we calculate the highest values for every size bag and taking into account every item type. For each item we check how it fits in every size bag up to the size S of our bag. Then for every new item considered we check if the value of what was there previous is less than the value of the new item and what is left when we remove items to make space for the new one in the bag. If less we discard old item and replace with new. Recursively in Haskell:

sub = (!!)

s = [3 , 2, 1,5]
v = [6 , 3 ,7,10]

maxval 0 = 0
maxval size = maximum [ v `sub` i + maxval (size – s `sub` i ) | i<-[0..t], s `sub` i <= size] where t = (length s) - 1 [/source] The problem is that this recursive solution is poor performance wise and is not very good for large values. However this can be rewritten to use a table - utilizing memoization to improve performance - where previous values are stored and used to calculate new ones. For every item and every size bag we check (F#): [source lang="python"]if (opt_cost.[cost_n] < opt_cost.[cost_n-cost.[item_n]] + value_c ) then opt_cost.[cost_n] <- (opt_cost.[cost_n-cost.[item_n]] + value_c) best_n.[cost_n] <- item_n[/source] Values across Ranges

To address the old problem of stupid suggestions I tried introducing bounds and making certain items appear only within certain cost ranges but these were not satisfactory. Finally I decided upon a simple solution. Originally one could say that the value v, for each item was a mapping from my internal preferences to the natural numbers. However this was unsatisfactory so I introduced a range given in the form of a tuple to my value function. Thus instead of each item having a value V, it was a number that could take any value between V and W with V <= W. e.g.:

let value = [|(0,0) ; (20, 23) ; (21,22); (21, 23); (65, 70); (60,65)|]

Then within the bag packing function a random number that falls within each respective range is given to value. This minor addition has proven to be the difference between making my little app fairly useful to very useful. A button on the interface ‘New Combo’, generates a new combination of items within the price constraint if I am not satisfied with the current combination. Now I know that for £3.56 instead of 4 fries I can get 2 hamburgers, french fries and a coke.

The thing runs on my pocket pc and was written in F#. And yes the value function concept is very subjective.

Functional Programming on .NET part 2

So most who read this aught to know what a prime number is, a number whose only factors are one and itself. This post is not on primes but does use them in a simple program which uses a simple algorithm to factor any given number. Now, many of you should know the difficulty in factoring numbers and how much of current cryptographic techniques rely on how hard the problem is. The program I wrote was written as a benchmark between the languages F# and Nemerle. Primarily as an “expressioning” benchmark and then as an aside a note on speed.

The task was to write a program which takes an unbounded positive integer and outputs a list that is the decomposition of the number into its prime factors. I decided to leverage laziness to allow me to write a flexible and short implementation. As I will get to later neither of these languages support laziness in the true sense and hence corecursion (in the sense of the dual of recursion) was unavailable, disallowing techniques such as a lazy sieve. Firstly the theory.

Theory

Given some number n, there exists primes such that and the product is unique to n. This is known as the Fundamental Theorem of Arithmetic or the unique factorization theorem. I will leave the proof as an excercise to the reader. A way to get to this is to divide n by its smallest factor > 1. Store the factor and repeat on the quotient until we get to 1. Why the smallest factor? Because the smallest factor of n > 1 must be prime. Why?

Suppose that this was false and smallest factor or least divisor of n, say a, was composite. Then we would have that there exists some b and some c such that a = b * c and that b > 1 and b < a (we are working with positive integers so if b = 1 then c = a, remember that b and c < a). So b also divides n (consider n = a * d = b * c * d). But we stated earlier that a was the smallest divisor of n so by contradiction a must be prime.

So as an example we take n = 18. we have a = 9 and d = 2. 3 divides 9 so it must divide 18 and 18 / 3 = 3 * 2. Now to continue.

Suppose we keep n = 18. We know 3 is its least divisor and its prime. so p1 = 3. We do 18/3 = 6.
Next we find least divisor of 6 which is 2. so p2 = 2. Now we do 6/2 = 3. 3 is prime so 18 = 3 * 2 * 3.

So it seems to do this we need to know how to find the least divisor for a given number. Well we know that the least divisor of a number must always be prime. So if given n, to find ld of n we start from 2, check if n mod 2 = 0 and work up till we find a prime that divides n. So for 35 we’d go through 2, 3, and hit 5 as its least divisor. A way to stop unnecessary checks is to leverage the fact that if an integer n > 1 is not divisible by any primes < = then n is prime.

Let n = (p)(a). Let us suppose that p is the least divisor of n, we know it must be prime. Now suppose p > then a > since p <= a (remember p is the smallest divisor). Then we have that which is a contradiction since it says n > n. So at least one of p or a must be less than . We know p <= a so we know that at least p < . This proves our proposition. Note also that since . We use that fact to lessen our checks.

The basic idea then is to define an infinite list of all natural numbers and the primes as those numbers which fail some primality test filtered out. We define that tests as any number which is its own least divisor. I will not explain the code in depth – there is plenty of documentation on both languages – this is mostly to show how easy it is to go from reasoning to implementation.

Implementation.

Below is the F# code which implements this functionality:

open System

module Primes_f = 
    let (+:) a alList = LazyList.cons a alList

    let Z3 : bigint LazyList = LazyList.unfold (fun x -> Some(x , x + 1I)) 3I 

    let rec least_denominator_byfactor l n = 
        match l with 
            LazyList.Cons(p,ps) -> if n % p = 0I then 
                                        p
                                   elif p * p > n then
                                        n
                                   else
                                        least_denominator_byfactor ps n  
                       
    let rec prime = function
        n when n  failwith "Not positive Int"
        | n when n = 1I -> false
        | n when n > 1I -> least_denominator n = n
        | _ -> failwith "?"
        
    and primes =  2I +: (LazyList.filter prime Z3)

    and least_denominator n = least_denominator_byfactor primes n
    
    let rec factors = function
        n when n  failwith "Not positive Int"
        | n when n = 1I -> []
        | n when n > 1I -> let p = least_denominator n  
                           p :: (factors (n / p)) 
                           
        | _ -> failwith "?"

To display:

    let dtm = DateTime.Now
    print_any ("Time is: " ^ dtm.ToString() )
    
    //99999988888776655423101   //let z = factors 999988710I//999998888877665542310I    
    let rnd = Random()                                        
    
    let rec Generate tx l = 
        match tx with
            0 -> l
            | _ -> let z = bigint.FromInt32 (rnd.Next(1000000,int.MaxValue))    
                   Generate (tx - 1) ( ( factors z )::l )
                                        
    let list_of_primefactors =  Generate 10000 []//factors 9876543210I  //3 mins 100,000 -  20sec 10,000 .05
    let dtm2 = DateTime.Now 
    let d = dtm2 - dtm
  
    let primes1 = List.filter (fun l -> if List.length l = 1 then true else false) (list_of_primefactors)
    
    let probprimes = System.Convert.ToDouble( (List.length primes1)) / 1000.0
    
    
    List.map (fun c -> print_any c ; System.Console.WriteLine ("") ) primes1   
    print_any probprimes
    //print_any list_of_primefactors      
       
    System.Console.Write ("\n\nTime is: " ^ dtm2.ToString() ^ " Took: " ^ d.ToString() ^ "\n" )  
    System.Console.ReadLine ()

The F# code was pretty straightforward to implement. The language remains quite functional and I had a lazy list data structure which allowed semi-corecursion via unfold. Now the Nemerle code. Because of its more object-centricism (not a critique) I had to approach how I arranged the code a bit differently.

  
module Number
    private least_denominator_byfactor(l : Primes,  n : decimal) : Decimal 
        def p =  l.prime
        
        if((p==3) && (n%2 == 0))            
            2m
        else    
            if(n % p == 0)  
                p
            else if(p * p > n)
                n
            else
                least_denominator_byfactor(l.next,n)          
            
    public least_denominator(n : Decimal) : Decimal 
        least_denominator_byfactor(Primes(3), n ) 
        
    public IsPrime(k: Decimal) : bool
        | n when n  throw ex("Not positive")
        | n when n == 1 => false
        | n when n == 2 => true
        | n when n % 2.0m == 0 => false
        | n when n > 2 => (n == least_denominator(n))
   
    public next_prime (v : Decimal) : Decimal
        def ip = IsPrime(v + 1)
        match(ip) 
            | true => v + 1
            | false => next_prime(v + 1)
        
    public factors(number : Decimal) : list[Decimal]
            | n when n  throw ex("Not Positive")
            | n when n == 1 => []
            | n when n > 1 => def p = least_denominator(n) ; p :: factors(n/p)          

class Primes
    public prime : Decimal
    public next : LazyValue [Primes]
            
    public this (p : Decimal) 
        prime = p
        next = lazy (Primes (Number.next_prime(p)))

To display:

  
module Program
    Main() : void
    
        def dtm = DateTime.Now 
        WriteLine($"Time now is: $dtm") 
                  // 9998876655423101
        //Test Nums: 99998877665542310
        def rnd = Random()
        
        def Generate(tx, l = [])
            match(tx)
                | 0 => l 
                | _ => Generate(tx - 1, Number.factors( rnd.Next(1000000, int.MaxValue) )::l) 
            
        def list_of_primefactors = Generate(152)//Number.factors(9766427) 
       
        def dtm2 = DateTime.Now       
        
        foreach(pfactors in list_of_primefactors)
            foreach(num in pfactors)
               Write($"$num | ") 
            WriteLine("")       */
        
        WriteLine($"Time Now is: $dtm2, Took $(dtm2 - dtm)")
        ReadLine()

While for example in the F# code I had only functions and general functionality I had to package the code into appropriate classes in nemerle and to have behaviour sort of baked into those data types (for example I could not unfold into a generic list of primes, I had to build a next mechanism into the lazy prime class). The nemerle implementation (algorithim not language) is quite a bit less inefficient. But this is because I did not really redress the design to go with objects. For example in F# I could afford mutual recursion since F# has light weight <fast> functions and has the caveat that the lazy list caches its data.

In Nemerle the Primality check in IsPrime requires more and more objects to be created until the test is passed (note the circularity wher ld looks for a next prime which in turn calls ld to find if its prime) so it bogs down quite quickly. Indeed for small numbers (less than 10 digits) the performance is quite close – implying that the actual languages are not far apart in speed. Nonetheless the rate of increase in time usage for Nemerle is much steeper (by a factor of ~14 before change but dropping to near F#’s after for single iterations) than for F# due to the object thrashing I was doing. For example by merely injecting the following code

private ldf(k : decimal,n : decimal) : decimal
        match(k) 
            | m when n % m == 0 => m
            | m when m * m > n => n
            | _ => ldf(k + 1, n) 

private ld(n : decimal) : decimal
        ldf(2,n)  

and replacing the appropriate function in IsPrime, factoring 99998877665542310 went from taking 25 seconds to 3 seconds. A similar injection to F# increased the speed from 2 seconds to 8. F# certainly benefits from the caching in its Lazy list implementation. Both languages are eagerly evaluated except in small localized places. In effect the evaluation is more delayed than it is lazy in the true sense that one would find in Haskell. Thus for example this:

let rec sieve function = LazyList.Cons(z, zs) -> z +: sieve (LazyList.filter (fun n -> (n % z) <> 0I) zs

would fail to terminate when given sieve Z3, while similar code in Haskell knows where to stop evaluation.

Speed

As Noted earlier the F# code was fairly fast (helped, I suspect because of it caching, thus larger numbers benefited from previous computations and in having to do less work. One can really tell over multiple iterations where past iterations aid future ones. For example it took 3 minutes to factor 100,000 numbers between, 1,000,000 and 2^32. While it takes 15 secs (down from ~ 60 secs) in Nemerle to factor 120 nums, it takes F# 3 secs. In the next post I will post on Visual Studio integration, some graphs and data and improvements in the arrangement of code and primality testing for Nemerle.

One note is that F# sometimes generates confusing error messages. This error was due to using an int in place of a bigint i.e. n % 0 vs n % 0I. Error 1 Type error in the use of the overloaded operator ‘( % )’. No operator ‘%’ (full name ‘op_Modulus’) supported by the type ‘bigint’ matches the argument types. See also C:\projects\prime\prime\prime.fs(12,23)-(12,24). See also . Note the nice type system at work =)

As well, sometimes when you dont define your pattern matching cases properly it fails to build yet gives no error. Still some ways to go before being commercial. But hope it doesnt sell out when it does.

Interestingly .NET had no built in arbitrary precision integer data type (had because they just put it in for 3.5). F# does but Nemerle had to use decimal. Note though that to change I but have to rename type annotations. The code is general. Excluding the modules and classes Nemerle code and F# are very much on par.

Functional Programming on .NET – Part 1

So it seems that functional programming is the new hype. This could be a good thing but it could also be a sad/bad thing. Looking at the last major hype – object oriented programming and seeing what was lost from Smalltalk to C++ one can only hope that although concepts are brought in section by section they are done faithfully rather than as washed down ugly caricatures.

At the moment there are only 2 real offerings for functional programming on .NET and those are F# and Nemerle. There are other languages:

Scala is capable of targeting IL but I do not know its interop capabilities since it is primarily a consumer of the JVM. There is the new initiative with IronScheme but it is too early yet. As well there is the language L# but it is meant as a lightweight embeddable lisp like scripts eater. Finally there is Hugs98.NET which does not target IL but can still consume .NET code and present Haskell code for consumption. Nonetheless the lack of built in interop and the requirement to (semi)manually wrap all .NET classes to a format understood by Haskell is cumbersome. As well due to the vastly different mindsets of both platforms trying to get them to work along side each other is un-natural – like trying to get Orcs and Elves to work together.

So for now the only real contenders are F# and Nemerle. So what is it like to use each? I will not compare since that would be futile but I will note differences and such.

Firstly I will note that these languages are constrained by the platform under the hood, they are not really functional but merely compiling to .NET objects, arrays and similar. But that is not the problem (i.e. at the end of the day haskell still compiles to a bunch of gotos and alters CPU state), functional programming is more a mentality than anything. However since the functional methodologies are at the moment still not first class paradigms, to interop properly with the platform certain departures must be made from pure functional concepts in favour of a more object friendly representation. Detracting from the advantages offered by functional languages like Haskell and ML. I also suspect that the underlying “dynamic” objects (e.g. availability of reflection <- good thing?, late binding, type casting >_<) nature of the platform makes implementing a proper [static] type system a bit more of an art than necessary. Nonetheless these are all solvable issues to be addressed by Microsoft and the language designers. But at the moment there is still a fair jump down in expressive power from abstraction when going from Haskell to either of these languages.

If you go to the main Nemerle site you it will seem to be dead. One needs to look at the mailing lists to realize that the language is still being actively developed. The only detracting issue is that the language is not the focus of the developers even though it is still moving forward (amusingly, the project seems to also be very eastern with mostly eastern europe and Japan being active users). The language is very meta-powerful, allowing one to extend is capabilities using macros. Some of the things that have been done include a join calculus for concurrency, design by contract type verification support and multi-stage programming support. As a language it differs from F# as it is a bit more object oriented in the traditional sense. This I suspect may be related to why its type inference is inferior to F#’s, requiring quite a bit more type annotations. Both F# and Nemerle are on the same level of abstraction (however that would be judged) with support for succinct lightweight syntax and whitespace based formatting. Nemerle also has support for traditional ugly curly brace syntax to help bring over C# programmers. Indeed Nemerle is capable of looking very much like C# or very much like ML to suite the programmer’s tastes, making it a good candidate to act as a bridging language to functional programming.

The languages are fairly equi-capable, with the main differences between the languages being the more object oriented mentality of Nemerle (thus distracting from the functional paradigms and making its type system arguably less elegant than F#’s) and the stronger meta system of Nemerle. Finally F# is also more mature, with it being a research focus of a group of people, and production ready – it has recently been branded as an official product. Hence you are more likely to hit bugs and stumble on language inconsistencies in Nemerle than in F#. Nonetheless Nemerle is not an inferior language. It has a slightly different mentality and is an interesting combination of ideas that whose full implementation will make it a very interesting language. I feel it to be a mix of scheme, haskell and err C#.

I have split this post to reduce its size, the next post will be on a silly little lazily evaluated program in both languages I wrote which gives the prime factorization of a number. I will give my very informal speed comparisons and how each language’s mentality affected implementation.

Part II: Choosing a language

Having chosen a graphics engine I have now decided on what language I wish to use. Part of the many benefits of developing on .NET or Mono is the ability to defer the language choice. Because of the types of games and simulations I wish to make, the language I want has to be flexible, well suited to abstraction and strongly mathematical. This immediately eliminates much of the .NET languages, including C#. Now, C# 3.0 is better than ever with many decades old modern features but still only seems to have done them half-heartedly.

The language I chose was F#. On top of Nemerle. What does this mean? I do not know software engineering nor do I have the time to learn it. So I use something I am more comfortable with, abstract maths as a crutch to help make things go smoothly. Most of the code will be written in F# with Nemerle used to implement the framework or more specifically, the platform. First on F#.

F# is a powerful, succinct, functional, well abstracted language that is very good at large data manipulation and handling complex data-structures. Well suited to doing mathematical heavy lifting. F# is also at least as fast as C# on average (faster on some things, slower at a few). F# is also a well maintained and updated language and remains a priority for the developer(s) who works on it. Next.

Nemerle is also a succinct, functional, powerful hygenic meta-capable language. It is also a language designed with much insight and foresight. However, although it is still being actively updated it is not improving at a very encouraging rate. The language has sort of taken a backseat to other projects for the developers. The core of the language is well founded. However, venturing far outside that core is risky as the edges of the language are still unstable. Nonetheless it remains a powerful well thought out language.

Because of what I plan to do and how I plan to do it, I need as a base a language that is very close to its own specification. As a language which exposes its entire syntax tree, Nemerle fits that bill quite well. I plan to use it to create an environment where I can easily explore and implement my ideas, with natural self documenting code. As stated, most of the programming – data structures and algorithims – shall be done in F#. Nemerle will be used to tie things together since it can be pruned and easily adjusted to be more like one prefers. Including making it operate seamlessly with F#. I think. I plan to leverage and mainly use Nemerle meta-capabilites to help more easily implement my “nonstandard” approach.

Oh yes. the basic structure of the engine is a category.

Wonderment

I wonder which is more complex. A collection of interacting brains or the universe. I also wonder which allows whom.

rndm thuts on cmunictin

The other day I was thinking about hours and hotels before stumbling upon a brilliant discovery. Grammar Nazis are Champions of Inconsistency.

The rules of syntax of natural languages are filled with exceptions and inconsistencies due to their organic manner of growth. Thus, anyone who champions the grammar of a natural language such as English must necessarily be a Champion of Inconsistency.

For example, H is not a vowel. But no one ever says a hour, its an hour. But you say a hotel. Cause an hotel sounds weird. []

This is why I prefer to have language serve me and not be its servant. The ultimate purpose of language is to allow communication between two objects capable of processing and acting on it, so long as it does this then it suffices. Natural Language carries thoughts from the human mind to the external, so it will always be imperfect. It may only suffice. Hence it seems silly to get annoyed when ppl – kids looking to display identity/membership – arbitrarily drp vwls and cnsnants from wrds. These people may use language as they see fit, it is merely an imperfect human tool.

If they are incomprehensible to me I say simply, I am sorry but I do not speak that language. I can only assume that their urgency to communicate outside their native group is minimal.

Eating NP-completely at Mcdonalds

Ever since I was a child I have always been aware of and appreciated the difficulty involved in solving NP-complete problems. While the other children were out at their tables eating their food, I would stand often, trying to decide just what choices would allow me to get the most value for my money. It was a treat you see, so we didnt get to do it all the time. I used to take a long time making decisions, over analyzing decision paths whose relevance might be deemed questionable. I still do this actually, much to the amusement (and often frustrated bemusement of my friends). As an example, one of my favourite eat out treats was going to McDonalds. I realized that rather than buying unfilling happy meals I could do better by buying a number of individual sandwiches and fries separately for a similar price.

I still like to go to mcdonalds and still take time (counted in minutes) trying to optimize my cost-value ratio. Having recently gotten an Acer n310, the solution was simple. Use the knapsack algorithim to decide how to pack as much McDonalds for the price I wish to pay into my stomach while also cutting time and ensuring that I am actually making a good choice. So I did that.

The program was written on .NET 2.0, in F# and it runs on both my PocketPC and on my PC. I built the F# dll and then slapped a GUI on it using Visual C# for both versions.

At the moment the menu is hard-coded in and so are the costs and value function. The program works well enough. It validated some of my choices (3 hamburgers and 1 fillet, 1 small fries was fair for a £5 limit) while showing that with other choices by varying a single item I could have gotten more value for a bit less. The code is not very long, the knapsack contents function and .net interfaces are given below:

let rec bag_contents cost_i (best_items_per_cost : int array) =     

    match cost_i with
        | _ when cost_i <= 0 -> []
        | cost_current -> cost.[0] <- cost_current
                          let next_item = cost_current - cost.[best_items_per_cost.[cost_current]]               
                          best_items_per_cost.[cost_current]::(bag_contents next_item  best_items_per_cost)

//....
//Exposed using:
let rec mkString xs = 
    match xs with
        | [] -> ""
        | x :: xs ->  if x > 0 then assoc_list.[x-1] + " | " + (mkString xs) else " | " + (mkString xs)

type Knap = class
     new () = {}
     member this.Packed_Bag cost_size_preffered = mkString (best_bag cost_size_preffered size_menu)
end

Some things I wish to do is allow feeding of textfiles of items and cost/value functions (merely tables). As well I would like to do suggestions and variety. At the moment for example it tells me that Fries,Fries,Fries,Fries is good for £3.56. This is to be expected given the nature of the algorithm. But something like, for Np (where N is an integer) more or less you might try this combination or getting this or that item. So it’d also take a range |k| when making suggestions.

Defining value is tricky as well but that cant be helped.

Numeric updown in .NET compact doesnt support decimals.