Monthly Archives: January 2011

Playing with Node.js, Ubuntu, Sqlite3 and node-Sqlite

I was playing with Node.Js, the Javascript library that can be used to create web server applications. Because it could be a nightmare to install it under Windows, I installed it at Ubuntu. I downloaded the code from:

http://nodejs.org/#download

After expanding the file, I switched to the directory and execute:

./configure
make
sudo make install

(Note that is a bit different from one of my sources Learning Server-Side Javascript with Node.js)

Then, I installed Sqlite3 in my Ubuntu box (not Sqlite, the node-sqlite library uses Sqlite3):

sudo apt-get install sqlite3

In a worker directory, I executed:

sqlite3 test.db

This a command line tool (no server to start, it goes directly to a file just created, named test.bd). Then, I enteder:

create table customers(id int, name varchar(30), address varchar(30));
insert into customers(id, name, address) values (1, ‘Customer 1’, ‘Address 1’);
insert into customers(id, name, address) values (2, ‘Customer 2’, ‘Address 2’);
insert into customers(id, name, address) values (3, ‘Customer 3’, ‘Address 3’);

My creativity for test data is proverbial 😉

There is a list of modules for Node.js:

https://github.com/ry/node/wiki/modules

I wanted to use express node.js module, then I downloaded from Express. Expanded it under my worker directory, as express. In that directory, I executed:

./install.sh

Now, I downloaded the source of node-sqlite from grumdig github. (I should try the other implementation: http://github.com/orlandov/node-sqlite).

I expanded in a subdirectory of my work directory, switch to such subdirectory, and try the installation instructions:

node-waf configure
node-waf build

But the second one failed. The build of the c++ binding to Sqlite3 required the source code of the database. So, I go again to:

sudo apt-get install libsqlite3-dev

and try again. All OK.

After some mini examples, I wrote a simple web app:

/**
 * Module dependencies.
 */
var express = require('./express/lib/express');
var sqlite = require("./node-sqlite/sqlite");
var sys = require('sys');
/*
 * Open the database
 */
var db = sqlite.openDatabaseSync("test.db");
/*
 * Creates the web server
 */
var app = express.createServer();
app.get('/', function(req, res){
  res.send('Hello World');
});
app.get('/customers', function(req, res){
  res.writeHead(200, { 'Content-Type': 'text/html' });
  db.query("SELECT id, name, address from customers", function (records) {
    res.write('<h1>Customers</h1>\n');
    res.write('<table>\n');
    for (var i = 0; i < records.length; i++) {
        res.write('<tr>\n');
        res.write('<td>' + records[i].id + '</td>\n');
        res.write('<td>' + records[i].name + '</td>\n');
        res.write('<td>' + records[i].address + '</td>\n');
        res.write('</tr>');
    }
    res.write('</table>\n');
    res.end();
  });
}); 
/*
 * Start web server
 */
app.listen(3000);

This is the output of http://localhost:3000/customers page:

What an app! 😉 😉

My links about Node.Js:

http://delicious.com/ajlopez/nodejs

My plan: implement the server in AjSharp; go for a complete CRUD pages for a table using Node.js and Sqlite3; switch to the other node-sqlite3 binding; generate code for all.

Keep tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

Writing an Interpreter in .NET (Part 9)

Previous Post
First post of the series

This time, I want to add a missing part: composite command. The interpreter needs a way to execute a list of commands, at any point: at if/then, if/else, while, etc… First, I wrote a test (this is not the initial version; it’s the current one):

        [TestMethod]
        public void CreateAndEvaluateCompositeCommand()
        {
            BindingEnvironment environment = new BindingEnvironment();
            environment.SetValue("a", 0);
            ICommand add1 = this.MakeAddCommand("a", "a", 1);
            ICommand add2 = this.MakeAddCommand("a", "a", 2);
            CompositeCommand cmd = new CompositeCommand(new ICommand[] { add1, add2 });
            Assert.IsNotNull(cmd.Commands);
            Assert.AreEqual(2, cmd.Commands.Count);
            Assert.AreEqual(add1, cmd.Commands.First());
            Assert.AreEqual(add2, cmd.Commands.Skip(1).First());
            cmd.Execute(environment);
            Assert.AreEqual(3, environment.GetValue("a"));
        }
        private ICommand MakeAddCommand(string target, string source, int number)
        {
            IExpression add = new BinaryArithmeticExpression(new VariableExpression(source), new ConstantExpression(number), ArithmeticOperator.Add);
            ICommand set = new SetCommand(target, add);
            return set;
        }

Then, I added a new ICommand, the CompositeCommand, refined until it pass the test:

I need to support the parse of a composite command. I decided to use the C#/Javascript syntax: the composite command should be delimited by { and }. I realized that I had no support of such characters in Lexer, so I wrote this test:

        [TestMethod]
        public void ProcessCurlyBrackets()
        {
            Lexer lexer = new Lexer("{}");
            Token token = lexer.NextToken();
            Assert.IsNotNull(token);
            Assert.AreEqual(TokenType.Separator, token.TokenType);
            Assert.AreEqual("{", token.Value);
            token = lexer.NextToken();
            Assert.IsNotNull(token);
            Assert.AreEqual(TokenType.Separator, token.TokenType);
            Assert.AreEqual("}", token.Value);
            Assert.IsNull(lexer.NextToken());
        }

Then, I modified the Lexer source, simply adding the new separators:

private static string[] separators = new string[] { ";", "(", ")", "{", "}" };

Next step: to add support of composite commands in Parser. As usual, the test to exercise the Parser:

        [TestMethod]
        public void ParseCompositeCommand()
        {
            Parser parser = new Parser("{ a = a+1; a = a+2; }");
            ICommand command = parser.ParseCommand();
            Assert.IsNotNull(command);
            Assert.IsInstanceOfType(command, typeof(CompositeCommand));
            CompositeCommand ccmd = (CompositeCommand)command;
            Assert.IsNotNull(ccmd.Commands);
            Assert.AreEqual(2, ccmd.Commands.Count);
            Assert.IsInstanceOfType(ccmd.Commands.First(), typeof(SetCommand));
            Assert.IsInstanceOfType(ccmd.Commands.Skip(1).First(), typeof(SetCommand));
        }

Then I added the code in Parser.ParseCommand (partial listing):

    if (token.TokenType == TokenType.Separator && token.Value.Equals("{"))
        return this.ParseCompositeCommand();

The new method:

    private ICommand ParseCompositeCommand()
    {
        IList<ICommand> commands = new List<ICommand>();
        Token token = this.NextToken();
        while (token != null && !(token.TokenType == TokenType.Separator 
             && token.Value.Equals("}")))
        {
            this.PushToken(token);
            commands.Add(this.ParseCommand());
            token = this.NextToken();
        }
        if (token == null)
            throw new ParserException("Expected '}'");
        return new CompositeCommand(commands);
    }

I tested the unclosed command:

        [TestMethod]
        [ExpectedException(typeof(ParserException))]
        public void RaiseIfCompositeCommandNotClosed()
        {
            Parser parser = new Parser("{ a = a+1; a = a+2; ");
            parser.ParseCommand();
        }

And the evaluation of simple composite commands, using if and while commands (no change in those command implementation: they can manage any ICommand, and our new CompositeCommand implements the interface):

        [TestMethod]
        public void ParseAndEvaluateSimpleIfWithCompositeCommand()
        {
            Parser parser = new Parser("if (1) { a = a+1; a = a+2; }");
            ICommand command = parser.ParseCommand();
            Assert.IsNotNull(command);
            Assert.IsInstanceOfType(command, typeof(IfCommand));
            IfCommand ifcmd = (IfCommand)command;
            Assert.IsInstanceOfType(ifcmd.ThenCommand, typeof(CompositeCommand));
            BindingEnvironment environment = new BindingEnvironment();
            environment.SetValue("a", 2);
            command.Execute(environment);
            Assert.AreEqual(5, environment.GetValue("a"));
        }
        [TestMethod]
        public void ParseAndEvaluateSimpleWhileWithCompositeCommand()
        {
            Parser parser = new Parser("while (a) { a = a-1; b=b+1; }");
            ICommand command = parser.ParseCommand();
            Assert.IsNotNull(command);
            Assert.IsInstanceOfType(command, typeof(WhileCommand));
            WhileCommand whilecmd = (WhileCommand)command;
            Assert.IsInstanceOfType(whilecmd.Command, typeof(CompositeCommand));
            BindingEnvironment environment = new BindingEnvironment();
            environment.SetValue("a", 2);
            environment.SetValue("b", 0);
            command.Execute(environment);
            Assert.AreEqual(0, environment.GetValue("a"));
            Assert.AreEqual(2, environment.GetValue("b"));
        }

The above code is the CURRENT version. During the development, and using TDD, I wrote the code by steps, and then, I did some refactoring. But the lesson is: use the tests to guide your development.

All tests in green:

Good code coverage:

You can download the current version from InterpreterStep09.zip. If you want to see all the steps, I commit the code in under trunk/Interpreter in my AjCodeKatas Google code project.

Next steps: foreach command, for command, function declaration, etc…

Keep tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

Writing an Interpreter in .NET (Part 8)

Back to this project! Writing an interpreter, using C# and TDD. In this step, I added a new ICommand, the WhileCommand:

You can download the current version from InterpreterStep08.zip. If you want to see all the steps, I commit the code in under trunk/Interpreter in my AjCodeKatas Google code project.

The code for WhileCommand is simple:

    public class WhileCommand : ICommand
    {
        private IExpression condition;
        private ICommand command;
        public WhileCommand(IExpression condition, ICommand command)
        {
            this.condition = condition;
            this.command = command;
        }
        public IExpression Condition { get { return this.condition; } }
        public ICommand Command { get { return this.command; } }
        public void Execute(BindingEnvironment environment)
        {
            while (BooleanPredicates.IsTrue(this.condition.Evaluate(environment)))
                this.command.Execute(environment);
        }
    }

Note that I added a BooleanPredicates class. It was born as a refactor of previous code I used in IfCommand implementation. I wrote in the previous post about my intentions of such refactoring. Using TDD, I have tests of the new class, an example:

        [TestMethod]
        public void IsFalse()
        {
            Assert.IsTrue(BooleanPredicates.IsFalse(null));
            Assert.IsTrue(BooleanPredicates.IsFalse(string.Empty));
            Assert.IsTrue(BooleanPredicates.IsFalse(0));
            Assert.IsTrue(BooleanPredicates.IsFalse((short)0));
            Assert.IsTrue(BooleanPredicates.IsFalse((long)0));
            Assert.IsTrue(BooleanPredicates.IsFalse(0.0));
            Assert.IsTrue(BooleanPredicates.IsFalse((float)0.0));
            Assert.IsFalse(BooleanPredicates.IsFalse(new object()));
            Assert.IsFalse(BooleanPredicates.IsFalse("foo"));
            Assert.IsFalse(BooleanPredicates.IsFalse(1));
            Assert.IsFalse(BooleanPredicates.IsFalse((short)2));
            Assert.IsFalse(BooleanPredicates.IsFalse((long)3));
            Assert.IsFalse(BooleanPredicates.IsFalse(4.0));
            Assert.IsFalse(BooleanPredicates.IsFalse((float)5.0));
        }

The test is, then, a kind of specification: what is false for my interpreter?

I tested the new command in isolation:

        [TestMethod]
        public void EvaluateWhileCommandUsingDecrement()
        {
            BindingEnvironment environment = new BindingEnvironment();
            environment.SetValue("a", 2);
            IExpression condition = new VariableExpression("a");
            ICommand command = new SetCommand("a", new BinaryArithmeticExpression(new VariableExpression("a"), new ConstantExpression(1), ArithmeticOperator.Subtract));
            WhileCommand wcommand = new WhileCommand(condition, command);
            Assert.AreEqual(command, wcommand.Command);
            Assert.AreEqual(condition, wcommand.Condition);
            wcommand.Execute(environment);
            Assert.AreEqual(0, environment.GetValue("a"));
        }

Then, I added support for the process of the command in the Parser:

        private ICommand ParseWhileCommand()
        {
            IExpression condition;
            ICommand cmd;
            this.ParseToken(TokenType.Separator, "(");
            condition = this.ParseExpression();
            this.ParseToken(TokenType.Separator, ")");
            cmd = this.ParseCommand();
            return new WhileCommand(condition, cmd);
        }

Obviously, with tests 😉 :

        [TestMethod]
        public void ParseAndEvaluateSimpleWhileCommand()
        {
            Parser parser = new Parser("while (a) a = a-1;");
            ICommand command = parser.ParseCommand();
            Assert.IsNotNull(command);
            Assert.IsInstanceOfType(command, typeof(WhileCommand));
            BindingEnvironment environment = new BindingEnvironment();
            environment.SetValue("a", 2);
            command.Execute(environment);
            Assert.AreEqual(0, environment.GetValue("a"));
        }

I could add more tests, but now, the new command is in good health. All tests still in green:

Good code coverage:

Next steps: composite commands, for/foreach commands, function declaration…

Keep tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

NHibernate 3 (Part 1) Simple Mapping

Next post

Year and half ago I wrote an example:

First NHibernate 2.x Example

This year, I want to explore the new release: NHibernate 3.0. You can download the current version from:

http://sourceforge.net/projects/nhibernate/files/

I get NHibernate-3.0.0.GA-bin.zip to use in this solution:

I keep the source code at my AjCodeKatas Google code project, under trunk/NHibernate/SimpleMapping. The code doesn’t include the NHibernate libraries, so you must add the references to the solution. I added all libraries from the NHibernate folders Required_Bins and Required_For_LazyLoading\Castle.

If you are lazy, like me, and you want a ready-to-build solution, you can download the complete example with NHibernate required files from my Skydrive: NHibernate3SimpleMapping.zip.

Note that I created a solution folder Schemas, and add the .xsd files I found at NHibernate distribution in Required_Bins folder.

The SimpleMapping.Domain contains only a class:

    public class Customer
    {
        public virtual Guid Id { get; set; }
        public virtual string Name { get; set; }
        public virtual string Address { get; set; }
        public virtual string Notes { get; set; }
    }

This class library has no reference to NHibernate. I wrote an app.config file for the console application:

<?xml version="1.0" encoding="utf-8" ?>
<configuration>
  <configSections>
    <section
    name="hibernate-configuration"
    type="NHibernate.Cfg.ConfigurationSectionHandler, NHibernate"
/>
  </configSections>
  <hibernate-configuration xmlns="urn:nhibernate-configuration-2.2">
    <session-factory>
      <property name="dialect">NHibernate.Dialect.MsSql2000Dialect</property>
      <property name="connection.provider">NHibernate.Connection.DriverConnectionProvider</property>
      <property name="connection.connection_string">Data Source=.\SQLEXPRESS;Initial Catalog=NHibernate3SimpleMapping;Integrated Security=True</property>
      <property name="proxyfactory.factory_class">
        NHibernate.ByteCode.Castle.ProxyFactoryFactory, NHibernate.ByteCode.Castle
      </property>
      <mapping assembly="SimpleMapping.Console" />
    </session-factory>
  </hibernate-configuration>
</configuration>

I wrote a Customer.hbm.xml file and mark it as Embedded Resources in his properties window (don’t forget this step: this is the way the example uses to tell NHibernate what classes to map):

<?xml version="1.0" encoding="utf-8" ?>
<hibernate-mapping xmlns="urn:nhibernate-mapping-2.2"
assembly="SimpleMapping.Domain"
namespace="SimpleMapping.Domain">
  <class name="Customer" table="Customers">
    <id name="Id">
      <generator class="guid.comb" />
    </id>
    <property name="Name" not-null="true" />
    <property name="Address" />
    <property name="Notes" />
  </class>
</hibernate-mapping>

To create the database, run Sql\ExecuteAll.cmd (see Readme.txt for more details).

The console program only creates a customer, save it in the database, and retrieve all existing customer:

    ISessionFactory sessionFactory = new Configuration().Configure().BuildSessionFactory();
    using (ISession session = sessionFactory.OpenSession())
    {
        using (ITransaction tx = session.BeginTransaction())
        {
            Customer customer1 = new Customer();
            customer1.Name = "Customer 1";
            customer1.Address = "Address 1";
            customer1.Notes = "Notes 1";
            session.Save(customer1);
            IQuery query = session.CreateQuery("from Customer");
    
            foreach (Customer c in query.List<Customer>())
                System.Console.WriteLine(string.Format("Customer {0}", c.Name));
            tx.Commit();
            session.Close();
        }
    }

(Sorry, I’m not very creative in the values of the properties 😉

There are many details to discuss: Why Castle bytecode? what does each property in configuration mean? What is a session? An  a transaction? What is an Id? What is a guid.comb? Options instead of guid.comb? How to map other kind of properties (currency values? dates?).

And what if we need more classes? Inheritance mapping? One to many? Lot of stuff to explore in upcoming posts.

Meanwhile, some resources:

Online NHibernate Documentation

NHibernate available resources

SourceForge project

Book: Jason Dentler’s NHibernate 3.0 Cookbook

http://delicious.com/ajlopez/nhibernate+tutorial

Keep tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

Design Patterns in an Interpreter, using TDD

Past October, I participated in an ALT.NET Hispano VAN about Design Patterns. I presented some of the classic design patterns of the GangOfFour book. My presentation (Spanish) DesignPatterns.pptx The VAN video (Spanish voice) and resources.

During the VAN, I explain and use some of the design patterns, but with a key idea: use all of them in the same example: an interpreter. You can download the C# code from my Google Code Project AjCodeKatas at Patterns folder.

Maybe, that code evolve, but you can download the VAN original code from Patterns20101017.zip.

Note: the namespaces that I used are related to the patterns. The code was developed using TDD (Test-Driven Design).

This is the list of patterns:

Interpreter: used in a expression interpreted, base of all the example.

Composite: with commands in the interpreter. There is a composite comamnd that contains a list of commands.

Template Method: it is in the method .Evaluate of the BinaryExpression: it evaluated two expressions and the results is used in the method .Apply, that is implemented at each of the subclasses.

Strategy: Instead of writing a class, I use Func<obj,obj,obj> to apply in the evaluation of ArithmeticBinaryExpression.

Decorator: An IContext is passed to each command and expressiona. It has the responsability of keep the values of the variables. I decorated it to have a new IContext implementation that raise events with info about what variables and values are read and changed.

Observer: Events in .NET, an evolution of the original pattern.

Adapter: I want to consume a file with code of the language to interpret, using a TextReader. But I need to read words, tokens (see Token class). Lexer class is an adapter around the TextReader. It has new method to read the next token in the stream.

Abstract Factory: The example is not in the interpreter. There is code that use ADO.NET providers, that act as an abstract factory.

Facade: with Strategy, it’s one of the most important pattern to learn and employ. All Strategy derives to composition instead inheritance, and to Dependency Injection, Inversion of Control and IoC containers. For me, Facade is like the “API” of our business, domain. A classic example: ISession in NHibernate.

Machine class is a kind of Facade. It is the entry point to the interpreter. It coordinate and delegate work to Parser (another adapter example), Lexer, files, Context. The interpreter consumer can invoke this object without direct interaction with the internal implementation.

Visitor: I wrote a class, that takes an instance of the Interpreter (as a tree to execute) and decompiles it to text.

You have more examples and UML diagrams at:

http://www.dofactory.com/Patterns/Patterns.aspx

Thanks to the ALT.NET Hispano for the opportunity to talk about this topic. I should publish more advances of my series about writing an interpreter using TDD.

Keep tuned!

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

Abstract Elements in AjGroups

I wrote about my AjGroups finite groups library in my previos posts:

Presenting AjGroups: Finite Groups Library
Permutations in AjGroups

Now, I want to present the other internal implementation of a finite group in the solution: based, not in permutations, but in abstract elements.

An abstract element is identified by a name:

The names are letters: a, b, c, …. By convention, element e is the identity. Then

a * e = e * a

But, what is the result of a * b in a group? The results are stored in an OperationTable:

The OperationTable keeps a list of elements and a matrix. The cell of a matrix is the result of the multiplication of two elements:

public void SetValue(IElement left, IElement right, IElement value)
{
    this.SetValue(elements.IndexOf(left), elements.IndexOf(right), value);
}
public IElement GetValue(IElement left, IElement right)
{
    return this.GetValue(elements.IndexOf(left), elements.IndexOf(right));
}
internal void SetValue(int leftpos, int rightpos, IElement value)
{
    cells[leftpos, rightpos] = value;
}
internal IElement GetValue(int leftpost, int rightpos)
{
    return cells[leftpost, rightpos];
}
		

The OperationTable can be built using permutation elements. A test:

[TestMethod]
public void CalculateSymmetricGroupTable()
{
    IGroup group = new SymmetricGroup(3);
    OperationTable table = new OperationTable(group.Elements);
    table.Calculate();
    foreach (IElement left in group.Elements)
        foreach (IElement right in group.Elements)
            Assert.AreEqual(left.Multiply(right), table.GetValue(left, right));
}

But it is not the idea: I want to use OperationTable with named elements, and construct by hand or calculation the multiplication matrix.

The OperationTable has methods: .HasIdentity, .IsAssociative, .IsConmutative, to determine its properties. A test:

[TestMethod]
public void SymmetricGroupThreeOperationIsAssociative()
{
    OperationTable table = new OperationTable((new SymmetricGroup(3)).Elements);
    table.Calculate();
    Assert.IsTrue(table.IsAssociative);
}

Notably, the OperationTable can be incomplete: some cells can be still undefined. The method .IsClosed returns true if the multiplication matrix is completely defined: every result is know.

The OperationTable can be built by hand. The table:

is built and tested in:

[TestMethod]
public void CreateWithNamedIdentityAndOneElement()
{
    NamedElement identity = new NamedElement('e');
    NamedElement aelement = new NamedElement('a');
    OperationTable table = new OperationTable(new List<IElement>() { identity , aelement}, true);
    identity.OperationTable = table;
    aelement.OperationTable = table;
    table.SetValue(aelement, aelement, identity);
    Assert.IsTrue(table.HasIdentity);
    Assert.IsTrue(table.IsAssociative);
    Assert.IsTrue(table.IsClosed);
    Assert.IsTrue(table.IsCommutative);
    Assert.AreEqual(2, table.Elements.Count);
    Assert.AreEqual(identity, table.GetValue(identity, identity));
    Assert.AreEqual(aelement, table.GetValue(aelement, identity));
    Assert.AreEqual(aelement, table.GetValue(identity, aelement));
    Assert.AreEqual(identity, table.GetValue(aelement, aelement));
    Assert.AreEqual(1, identity.Order);
    Assert.AreEqual(2, aelement.Order);
}

But my preferred method in OperationTable is .GetSolutions(). From an incomplete OperationTable, it returns a list of complete OperationTables that are compatible with group axioms. Let this initial incomplete operation table:

Applying .GetSolutions() to this operation table returns the only one compatible group (the unique finite group of order 3):

Note: every row and column IS A permutation of the original elements. That rule resumes the group axioms.

A test:

[TestMethod]
public void GetGroupsOfOrderThree()
{
    NamedElement identity = new NamedElement('e');
    NamedElement aelement = new NamedElement('a');
    NamedElement belement = new NamedElement('b');
    OperationTable table = new OperationTable(new List<IElement>() { identity, aelement, belement }, true);
    IList<OperationTable> solutions = table.GetSolutions().ToList();
    Assert.IsNotNull(solutions);
    Assert.AreEqual(1, solutions.Count);
    Assert.IsTrue(solutions[0].IsClosed);
}

But OperationTable is not an IGroup. There is a TableGroup:

Its constructor receives an OperationTable: it clones the elements and OperationTable, to makes a new abstract group.

The tables returned by .GetSolutions() are not all different via isomorphism. I have a method, used internally by tests, to return all the essentially distinct groups of order n:

private static IList<IGroup> GetGroupsOfOrder(int order)
{
    IList<IElement> elements = new List<IElement>();
    for (int k = 0; k < order; k++)
        elements.Add(new NamedElement(k));
    OperationTable table = new OperationTable(elements, true);
    IList<OperationTable> solutions = table.GetSolutions().ToList();
    foreach (OperationTable solution in solutions)
    {
        Assert.IsTrue(solution.HasIdentity);
        Assert.IsTrue(solution.IsAssociative);
        Assert.IsTrue(solution.IsClosed);
    }
    IList<IGroup> groups = new List<IGroup>();
    foreach (OperationTable ot in solutions)
        groups.Add(new TableGroup(ot));
    IList<IGroup> dgroups = GroupUtilities.GetNonIsomorphic(groups);
    return dgroups;
}

The .GetSolutions() method heavily relies on method .GetCompatibleTable(a,b,c) that tries to add the equation:

a * b = c

to an OperationTable, without breaking group axioms. If a compatible table exists, it is returned; if not, null is the result.

All these features were constructed using TDD. Notably, the original design didn’t include named elements and operation tables: it was totally based in permutations. My next post: the way TDD saved my day, when I added named elements.

Keep tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

Permutations in AjGroups

In my previous post I presented AjGroups, a class library written in C# that implements finite group concepts and operations. Source code at my AjCodeKata Google Project, under trunk/AjGroups.

In this post, I want to explain one of the implementations inside AjGroups: groups based on permutation.

A permutation is a bijective application of a set S over S. Say S is

S = { 0, 1, 2, 3, 4 }

Then, an permutation example is:

i(0)=0, i(1)=1, i(2)=2, i(3)=3, i(4)=4

It is the identity permutation. Other example:

s(0)=1, s(1)=0, s(2)=2, s(3)=3, s(4)=4

It is a swap, interchange of the first two elements. A rotation permutation:

r(0)=1, r(1)=2, r(2)=3, r(3)=4, r(4)=0

Permutations can be combined r*s:

(r*s)(n) = r(s(n))

The permutations of S are the elements of a group using the * operation. AjGroups implements a permutation using the Element class:

    public class Element : AjGroups.IElement
    {
        private byte[] values;
        public Element(params byte[] values)
        {
//....
    }

The permutation is represented in a byte array, where values[k] is the result of f(k), being f the permutation represented by the Element.

Element.Multiply(Element element) implements the multiplication:

 

Element.CreateIdentity generates an identity element, of size n:

       public Element Multiply(Element element)
        {
            int k;
            int length1 = this.values.Length;
            int length2 = element.values.Length;
            int newlength = Math.Max(length1, length2);
            byte[] newvalues = new byte[newlength];
            for (k = 0; k < newlength; k++)
            {
                if (k >= length2)
                {
                    newvalues[k] = this.values[k];
                }
                else if (element.values[k] >= length1)
                {
                    newvalues[k] = element.values[k];
                }
                else
                {
                    newvalues[k] = this.values[element.values[k]];
                }
            }
            return new Element(newvalues);
        }

Note that the method supports the multiplication of different size permutations.

Creating a swap of first two positions:

        public static Element CreateSwap(int size) 
        {
            Element element = CreateIdentity(size);
            element.values[0] = 1;
            element.values[1] = 0;
            return element;
        }

Creating a swap at position:

        public static Element CreateSwap(int size, int position)
        {
            Element element = CreateIdentity(size);
            element.values[position] = (byte) (position+1);
            element.values[position+1] = (byte) position;
            return element;
        }

Creating a rotation:

        public static Element CreateRotation(int size)
        {
            byte[] values = new byte[size];
            for (int k = 0; k < size; k++)
            {
                values[k] = (byte)(k == size - 1 ? 0 : k + 1);
            }
            return new Element(values);
        }

A CompleteGroup is a group with all its elements given in the constructor:

    public class CompleteGroup : BaseGroup
    {
        private List<IElement> elements;
        public CompleteGroup(List<IElement> elements)
        {
            this.elements = elements.Distinct().ToList();
        }
//...
    }

A GeneratedGroup is the result of combining a set of generator elements:

    public class GeneratedGroup : CompleteGroup
    {
        public GeneratedGroup(params IElement[] generators)
            : base(ElementUtilities.ElementsClosure(generators))
        {
        }
    }

ElementsUtilities.ElementsClosure generated by all the multiplication (a(a*b, b*a, a*b*b, a*c*b… ) generated by a set of initial elements (a, b, c, …)

Notably, the permutations of S are generated using a swap and a rotation:

    public class SymmetricGroup : GeneratedGroup
    {
        public SymmetricGroup(int size)
            : base(Element.CreateSwap(size), Element.CreateRotation(size))
        {
        }
    }

It can be proved that every finite group is a subgroup of a group generated by those two elements: a symmetric group of order n.

As I mentioned in my previous post, there is another implementation of finite groups in AjGroups: using abstract elements, not concrete permutations. That will be the topic for upcoming post.

Keep tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez