Angel \”Java\” Lopez on Blog

January 30, 2009

Dynamic Expressions Example

Filed under: .NET, C Sharp, Programming Languages — ajlopez @ 6:26 am

Yesterday, I was preparing a presentation for today, explaining lambda calculus, its history, and lambda application in languages. At the end of presentation, I’ll discuss lambda ideas in .NET: delegates, lambda notation, and lambda expression.

During a quick research, I found a really cool implementation of dynamic expression parsing, in the example:

DynamicLinq.cs

That code points as source the “the Gu” blog post:

Dynamic LINQ (Part 1- Using the LINQ Dynamic Query Library)

The code is included in the DynamicQuery directory in:

C# Dynamic Query Library (included in the -LinqSamples-DynamicQuery directory)

My initial idea was to write a formula graph winform app, using System.Linq.Expressions. But the above implementation has a notable feature: instead of buildin an expression tree composing a expressions, it takes an string (!!!) and parse on the fly, converting to a compiled version.

OK, this trick is used by many Linq query implementations, but I didn’t know that the code samples from Microsoft include this code.

Using the DynamicLinq.cs, I was able to create a Win Form app:

Note that you can use classes from .NET. “x” is the parameter I use to calculate the formula.

This is a key code in the Calculator.cs file:

 

public Delegate CompileFormula(string formula) { ParameterExpression x = Expression.Parameter(typeof(double), "x"); LambdaExpression e = DynamicExpression.ParseLambda(new ParameterExpression[] { x }, null, formula); return e.Compile(); }

The compiled Delegate, can be invoked, provided the “x” parameter value:

 

public double[] Calculate(Delegate formula, double from, double to, double step) { List<double> values = new List<double>(); for (double x = from; x <= to; x += step) values.Add((double) formula.DynamicInvoke(x)); return values.ToArray(); }

You can download this sample code from:

http://code.google.com/p/ajcodekatas/source/browse#svn/trunk/DynamicExpressionsExample

Another dynamic implementation:

To Bind or Not To Bind – Dynamic Expression Trees – Part 3 – B# .NET Blog
To Bind or Not To Bind – Dynamic Expression Trees – Part 2 – B# .NET Blog
To Bind or Not To Bind – Dynamic Expression Trees – Part 1 – B# .NET Blog

Some ideas:

- Extend the example to 3D (I could use the F#/DirectX visualization demo as a base code)

- Send a formula as text, to be processed in a distributed application, grid, or HPC cluster.

- Code kata writing a .Parse and .Compile to any of my scripting languages

If you need more power, the next level of dynamic languages and their compilation, using .NET, is the Microsoft.Scripting namespace in IronPython source code:

http://www.codeplex.com/IronPython/SourceControl

Introductions to IronPython, DLR initiative:

CLR Inside Out- IronPython and the Dynamic Language Runtime
CLR Inside Out- Dynamic Languages and Silverlight
InfoQ- Microsoft Surpasses Java’s Dynamic Language Support-
CLR Inside Out – IronPython

Related links about lambda, Dynamic Language Runtime, and dynamic languages in general:

http://delicious.com/ajlopez/lambda
http://delicious.com/ajlopez/dlr
http://delicious.com/ajlopez/dynamiclanguages

Angel “Java” Lopez
http://www.ajlopez.com/en
http://twitter.com/ajlopez

January 27, 2009

AjGa: a genetic algorithm library

Filed under: Artificial Intelligence, C Sharp, Software Development — ajlopez @ 7:15 am

I was coding a genetic algorithm library, using C#. The code is in my AjCodeKatas Google Code project, at:

http://code.google.com/p/ajcodekatas/source/browse/#svn/trunk/AjGa

The main project is AjGa (with AjGa.Tests for testing):

The main interfaces are:

I use generics, with two generic types: G, as the gene implementation type, and V, as the value type (e.g. int, double), that it will be used to catalog the genomes.

IPopulation is a colletion of genomes.

IGenome  is a collection of genes, that is evaluated to value.

IEvaluator is in charge of evaluate a genome.

The implementation of IEvolution runs generations over a population, employing mutator, crossover operators, to change the population composition after each run.

There are operator interfaces, to generate one genome, mutate an existing one, or apply a crossover over two genomes.

To test the ideas, I implemented a project with gene, genome, and operators, to attack the classical Travelling Salesman Problem:

In this example, an evaluator has a list of positions of cities to visit:

 

public class Evaluator : IEvaluator<int, int> { private List<Position> positions; public Evaluator(List<Position> positions) { this.positions = positions; }

The gene type is int, and tha value of each genome is expressed as a int. The genome keeps a list of integers, representing the ordinal number of the cities to visit:

 

using AjGa; public class Genome : BaseGenome<int, int> { public Genome(int size) { for (int k = 0; k < size; k++) { AddGene(k); } }

That is, each gene is an int, and a genome with 2, 0, 1 represents: visit the third city, then the first one, and finish the trip in the second city.

You can run the WinForm project, to test the library:

The above run has a random distribution of cities. The cities can be distributed in a grid:

This way, you can test the efficient of the algorithm to reach the optimum solution.

If you want to implement a new GA project, you should:

- Define the gene type

- Define the value type

- Some operators (creators, mutators, crossovers)

Tests are green:

Code coverage in fine:

I spent 4 hours in the first version, 3 hours exploring TSP, and around 8 hours preparing and tuning the TSP WinForm application.

As usual, I enjoyed write this software!

Angel “Java” Lopez
http://www.ajlopez.com/en
http://twitter.com/ajlopez

January 25, 2009

Presenting AjSoda

Filed under: Smalltalk, Software Development — ajlopez @ 6:38 pm

A year ago, I wrote a post, in Spanish, commenting Ian Piumarta work:

Self-sustaining sysmtes, Cola, Pepsi y Mate

I proposed that an implementation of Ian Piumarta ideas, in .NET or Java, could be possible. Instead of using C as underlying language, it could be reimplemented over a virtual machine language, with a rich class framework, and an automatic garbage colector. For me, it looks as an interesting idea, that deserves some attention.

To understand Piumarta and Warth ideas, they described a minimal implementation at:

http://piumarta.com/pepsi/objmodel2.pdf
http://piumarta.com/pepsi/objmodel.pdf

You’ll find minimal object implementation, in those papers. A diagram:

(taken from

Open Extensible Dynamic Programming Systems Dls

)

This past week, I was working on an implementation in C# of such ideas. I commited my work in my AjCodeKatas Google Code project, at:

http://code.google.com/p/ajcodekatas/source/browse#svn/trunk/AjSoda

The solution has four projects (two library classes, and the respective test suites). The main project is AjSoda:

 

An introductory diagram:

IObject is the interface I wrote to represent a generic object. It has a payload, an array of references to arbitrary .NET objects:

One alternative I considered, was to point only to IObject. But I want to have the feature of access directly to native .NET objects (or Java ones, if I change the implementation language).

The more important method in IObject is Send. Using this method, you can send a message (selector plus arguments) to any IObject instance.

IBehavior is my implementation of what Piumarta/Warth named a vtable. It is the object that containts the list of method that can attend the messages sent to an IObject.

Each IObject has a Behavior property that points to an IObject. I could had choose to point to an IBehavior, but in this way, the Behavior of an object can be replaced by any object that understand a #lookup: message selector.

I don’t need to implement the closure concept, as described in Piumarta/Warth papers. Using closures, they implemented slots a la Javascript or Selft. But I have no need to take that approach in my experiments, yet.

The main implementation classes are:

Each BaseObject implements IObject, having an internal array of objects:

public class BaseObject : IObject { private object[] values; public BaseObject() { } public BaseObject(int size) { this.values = new object[size]; } public int Size { get { if (this.values == null) { return 0; } return this.values.Length; } } public IObject Behavior { get; set; }

(Note that Behavior property is an IObject, as I explained above).

The more interesting method is Send:

 

public virtual object Send(string selector, params object[] arguments) { if (selector == null) { throw new ArgumentNullException("selector"); } if (this.Behavior == null) { throw new InvalidOperationException("No behavior in object"); } IMethod method = (IMethod) this.Behavior.Send("lookup:", selector); if (method == null) { throw new InvalidOperationException(string.Format(CultureInfo.InvariantCulture, "Unknown message '{0}'", selector)); } return method.Execute(this, arguments); }

I don’t use this.Behavior.Lookup to get the method associated with message selector. Instead, I’m using directly the Send method, so obj.Behavior can be mapped to any IObject that knows how to implement a method lookup. This feature has a performance impact, but it ables to implements new ways of dispatching a message. You can find in the cited papers, multiple inheritance and traits implemented using this extensibility.

AjPepsi

In the code, you’ll see an additional project, called AjPepsi, where I’m implementing a parser and a byte code interpreter, of the language Piumarta/Warth used as a proof of concept in their papers. It accepts code like:

Object new [^self class basicNew initialize] Object initialize [] List : Object(head tail) List head [^head] List tail [^tail] List head: newHead [head := newHead] List tail: newTail [tail := newTail] list1 := [^List new] list2 := [^List new] [list1 head: 'Hello'] [list2 head: 'World'] [list1 tail: list2]

Object and List are prototypes, but I should pospone any detailed discussion to a future post. AjPepsi is still under development; probably, I’ll make major refactoring and implementation in the next week. I took AjTalk code as a base, but I don’t sure it was a clever decision: AjPepsi is strong prototype oriented, so I spent ten hours refactoring AjTalk to fit AjSoda ideas.

One big next feature: as in the current implementation of Pepsi/Id/Cola, I’m thinking in automatic generation of underlying language code (in this case, C# code), representing the state of a machine (classes, methods, instances).

Test are green:

Code coverage is fair:

There are some smell code to refactoring, yet. Classical example: a big switch with lot of code in byte code interpreter. But the majority of such smell is inside AjPepsi code. AjSoda is taking form, going to an stable version. It took only 4 hours of my time to write AjSoda current code, but I’m spending a lot of time writing a complete AjPepsi interpreter/parser/machine (10 hours until today).

As usual, I had a lot of fun writing all this code!

More links about Piumarta/Warth ideas:

http://lambda-the-ultimate.org/node/2483
http://piumarta.com/
http://piumarta.com/pepsi/pepsi.html
http://piumarta.com/software/cola/

Comments, suggestions, welcome.

Angel “Java” Lopez
http://www.ajlopez.com/en
http://twitter.com/ajlopez

January 10, 2009

Microsoft Tag, a new world to make

Filed under: Software Development — ajlopez @ 10:29 am

If you have so many years in software development like me, you probably remember that, for a few months, at middle 80s I guess, software development maganizes began to include a printed long vertical rectangle with little squares, at the margin of an article’s page. In that way, the authors published source code: that image could be scanned and transformed to text files. It was a great idea, that it was forgotten after the distribution of diskettes (and years after, CDs, DVDs) in the software magazine issue.

This year 2009, Microsoft launched an IPhone application, with an wide set of uses: Microsoft Pad

One idea: every object, post package, mechandise, traveling stuff, could be coded with this tag, pointing to an URL with a REST/Web Service interface, where we can update the state/position of the object, using a simple app in our mobile devices. The endpoint could describe itself, the available operations to perform on object status. Each physical object could have an updatable state in the cloud, pointed by its own tag drawing.

My first contact with this tech, was via a twitter from @MartinSalias (another use of twitter: quick and light way of getting interesing news, it could replace the RSS readers of hundreds of blogs). These days, Arvindra Sehmi published a blog post:

Microsoft Tag – Snap. Blink. Wow!

More general info at Microsoft Tag home page:

http://www.microsoft.com/tag/

To make tags go:

tag.microsoft.com

and go to gettag.mobi to download the scanning application.

Other posts:

Microsoft Releases Tag, Its Second iPhone Application

Another Useless iPhone App From Microsoft- ‘Tag’ (MSFT)

Microsoft Joins the Physical World Connections and Interactions Space with Microsoft Tag

Angel “Java” Lopez
http://www.ajlopez.com/en
http://twitter.com/ajlopez

January 9, 2009

The Clean Code Talks — Inheritance, Polymorphism, & Testing

Filed under: .NET, Programming, Software Development — ajlopez @ 8:55 am

I’m a fan of Twitter. One account I’m following to, is @delicious_prog, that sends many tweets each day, related to programming and software development in general. In one of that tweets, I found the post

The Clean Code Talks — Inheritance, Polymorphism, & Testing

by Daniel Wild, where he includes a Google Talk video:

by Misko Hevery in Google Tech Talks.

It’s very clear and interesting. It’s a talk explaining the uses of polymorphism, and the way to test it. I pleased to find in this video many similar arguments to the ones I use in my dev talks. Recently, I was using polymorphism in my AjCat interpreter (a cat-like programming language interpreter written in C#)

http://code.google.com/p/ajcodekatas/source/browse/#svn/trunk/AjCat

This is my Integer Binary Operation: 

public abstract class IntegerBinaryOperation : Expression { public abstract int Apply(int op1, int op2); public override void Evaluate(Machine machine) { int op2 = (int) machine.Pop(); int op1 = (int) machine.Pop(); machine.Push(this.Apply(op1, op2)); } }

The Add and Subtract operations override the Apply method:

public class IntegerAddOperation : IntegerBinaryOperation { private static IntegerAddOperation instance = new IntegerAddOperation(); private IntegerAddOperation() { } public static IntegerAddOperation Instance { get { return instance; } } public override int Apply(int op1, int op2) { return op1 + op2; } public override string ToString() { return "add_int"; } }
public class IntegerSubtractOperation : IntegerBinaryOperation { private static IntegerSubtractOperation instance = new IntegerSubtractOperation(); private IntegerSubtractOperation() { } public static IntegerSubtractOperation Instance { get { return instance; } } public override int Apply(int op1, int op2) { return op1 - op2; } public override string ToString() { return "sub_int"; } }

It’s very similar to the example presented in the video. I was a bit lazy in my operator implementation in AjPython (an interpreter, again, in C#, work in progress):

http://code.google.com/p/ajcodekatas/source/browse/#svn/trunk/AjPython

 

public class BinaryOperatorExpression : BinaryExpression { private Operator @operator; public BinaryOperatorExpression(Expression left, Expression right, Operator oper) : base(left, right) { this.@operator = oper; } public override object Evaluate(Environment environment) { object leftvalue; object rightvalue; leftvalue = this.Left.Evaluate(environment); rightvalue = this.Right.Evaluate(environment); switch (this.@operator) { case Operator.Add: return (int)leftvalue + (int)rightvalue; case Operator.Subtract: return (int)leftvalue - (int)rightvalue; case Operator.Multiply: return (int)leftvalue * (int)rightvalue; case Operator.Divide: return (int)leftvalue / (int)rightvalue; case Operator.Power: return System.Convert.ToInt32(System.Math.Pow((int)leftvalue, (int)rightvalue)); } throw new System.InvalidOperationException(); } }

but I’m confident in refactoring, I have a test base covering this operators.

It’s good to find this talk, I recommend it, thanks to @delicious_prog and Daniel Wild!

Angel “Java” Lopez
http://www.ajlopez.com/en
http://twitter.com/ajlopez

The Shocking Blue Green Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 68 other followers