Angel \”Java\” Lopez on Blog

January 27, 2010

Queue Channels in AjSharp

Filed under: .NET, AjSharp, Open Source Projects, Programming Languages — ajlopez @ 10:50 am

Some weeks ago, I implemented channels in my AjSharp interpreter. You can read about that implementation:

Channels and GoRoutines in AjSharp (part 1)
Channels and GoRoutines in AjSharp (part 2)

If you read the value of a channel, and there is no value, the read thread is blocked until a value is available. This is a way to synchronize the consumers and producers that operates over the channel. But sometimes, you want to put a value on a channel and continue. So, I added a “queue channel” (I could named it queued channel): you can put N values in the channel without blocking, saving them in an internal queue. The size of the queue is set in the constructor of the channel. The queue is limited in size, in order to preserve the synchronization features.

The name of the new class is QueueChannel. A test:

        [TestMethod]
        public void CreateAndUseQueueChannelWithTenElements()
        {
            QueueChannel channel = new QueueChannel(10);
            for (int k = 1; k <= 10; k++)
                channel.Send(k);
            for (int k = 1; k <= 10; k++)
                Assert.AreEqual(k, channel.Receive());
        }

The channel receives 10 values without blocking. If you send more values, you should use another thread:

        [TestMethod]
        public void CreateAndUseQueueChannelWithMoreEntriesThanSize()
        {
            QueueChannel channel = new QueueChannel(10);
            Thread thread = new Thread(new ThreadStart(delegate()
            {
                for (int k = 1; k <= 20; k++)
                    channel.Send(k);
            }));
            thread.Start();
            for (int k = 1; k <= 20; k++)
                Assert.AreEqual(k, channel.Receive());
        }

I rewrote my prime example using queue channels:

numbers = new QueueChannel(10);
running = true;
k = 1;
go while(running) { k++; numbers <- k; }
function filter(in, out, prime)
{
  while (true) 
  {
    value = <-in;
    if (value % prime)
      out <- value;
  }
}
function makefilter(channel, number)
{
  newchannel = new QueueChannel(10);
  go filter(channel, newchannel, number);
  return newchannel;
}
channel = numbers;
number = <-channel;
while (number < 1000) 
{
  PrintLine("Prime " + number);
  
  channel = makefilter(channel, number);
  
  number = <-channel;
}
running = false;

The code is in my Google code project:

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

My motivation for a queue channel, is that I'm writing a parallel genetic algorithm example, that suffered of too many blockings. I feel that a good algorithm doesn't need queues, but if you have many consumers and producers, and one thread produce many values to various channels, using common channel could raise blockings. Another way, to avoid blocking, is using the go command:

go channel <- newvalue;

But I guess it's over killing to launch a goroutine only to feed a channel.

I should present the parallel genetic algorithm, write about ideas of implementing actor model in AjSharp, and about distributed agents.

Keep tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

January 25, 2010

AjSharp: Implementing Futures

Filed under: .NET, AjSharp, Open Source Projects, Programming Languages — ajlopez @ 10:55 am

I implemented channels in my AjSharp interpreter. I wrote about it in:

Channels and GoRoutines in AjSharp (part 1)
Channels and GoRoutines in AjSharp (part 2)

I could use channels to implement futures. One option is to add Task Parallel Library from Microsoft, but I should use .NET 4: apparently, the original library is no more available. I guess I could leverage the new classes in the upcoming framework, but meanwhile, I want to explore the ideas of futures programming.

Channels can be used to implement some future process:

channel = new Channel();
go channel <- SomeLengthlyCalculation();
// .. more process
result = <- channel;

But channels are designed to resolve other problems: to have many values during its life, and be used as sync objects between producers and consumers of such values. The above channel variable, if used as a future, could be consulted only one. This is a minor issue, but signals a difference between channels and futures.

So, I wrote a new native classes, accessible by AjSharp programs, Future:

    public class Future : IReference
    {
        private object value;
        private ManualResetEvent handle = new ManualResetEvent(false);
        private bool set = false;
        public void SetValue(object value)
        {
            lock (this)
            {
                if (this.set)
                    throw new InvalidOperationException("Future value already calculated");
                set = true;
                this.value = value;
                this.handle.Set();
            }
        }
        public object GetValue()
        {
            this.handle.WaitOne();
            return this.value;
        }
    }

In the current version at trunk, IReference interface (SetValue, GetValue) is implemented by Channel class. AjSharp operators a <- b, a = <-b, are mapped to those methods. So, I can use Futures in this way:

future = new Future();
go future <- SomeLenghtlyProcess();
// ... more process
result = <-future;
result2 = <-future;

Consulting the future value is explicit. So, you can pass the variable future to any other function, by name, without viewing its value. I could drop the go in the set of the future, assuming the right value were computed in parallel. But I prefer to make parallelism explicit, using the go command.

This is a minor improvement in parallel features in AjSharp. I was working on queue channels: channels that support the storage of more than one value. You can check the code at:

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

I want to implement agents, to support actor model programming. It could be nice to have agent as keyword, as class keyword. And that the agents could be run in remote machines.

Keep tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

January 19, 2010

Tales from the Scrum: Is Agile/Scrum Hard?

Filed under: Agile Software Devevelopment, Scrum, Software Development — ajlopez @ 10:02 am

Recently, via some messages at Twitter, I found the post Agile/Pervagile on Slashdot in the multi-author blog Agile Advice – Working With Agile Methods (Scrum, OpenAgile, Lean). It’s an interesting reading, presenting Pervagile, the Perverted Agile. Most companies claims that they are using Agile, with Scrum or something alike, but, really, their adoption is partial. The author mention other deviations: Scrumbutt, Waterscrum, Scrummerfall, that deserve more comments here.

But today, I want to comment about the paragraph:

Agile is Hard

Okay, I’m actually being a little dis-honest.  The real truth is that doing agile is extremely, exceptionally, agonizingly difficult (for most people in most  organizations).  Why?  Because agile is not just another process to roll out.  It is, as has been mentioned in numerous places, a deep cultural change.  Agile is actually a liberation movement for people involved in software development.  Like most movements, however, it has been subject to corruptive forces.

Yes, true, but… I want to moderate above assertions, in the context of Scrum application (not Agile in general). If you are involved to introduce Scrum first time in your company, you need a cultural change, but I guess it could be not so deep. You need a proactive group of team members, a good ScrumMaster and Product Owner. AND (a no small and) the support from the management, to protect the team of outer interference, AND SPECIALLY the support of the Product Owner (protect him/her from other managers pressures, political forces, that could alter the priorities in product backlog, or that could interfere in the middle of the Sprint). The rest of your company can run in the old regime. But you need that your first project be protected. It needs nurturing and protection. Not a deep cultural change. The change in the rest of the company could be progressive. And the change in the team (I guess this is the first encounter of the members with Scrum) should be progressive, helped by an experienced ScrumMaster.

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

January 13, 2010

AjClipper: a Clipper-like interpreter that uses .NET

Filed under: .NET, AjClipper, ASP.NET, Open Source Projects — ajlopez @ 10:57 am

You can find a Clipper-like (I wrote Remember Clipper; you’ll find more links in that post) interpreter source code at my Code Katas Google project:

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

It’s an interpreter, written in C#, that can create and use native .NET objects. I wrote the interpreter to:

- Practice TDD
- Create a simple tool to leverage Clipper knowledge in one of my teams, to learn more .NET concepts

I should write posts about internal implementation, access to .NET objects, manage of work areas, etc… One idea I’m exploring, is running the interpreter from an ASP.NET web page:

 

(There is a web app in the project containing the above test page).

My collected links about Clipper:

http://delicious.com/ajlopez/clipper

I should improve the access to database, and complete language command and features. Keep tuned!

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

January 9, 2010

Refactoring AjLisp: a lisp interpreter written in C#

Filed under: AjLisp, C Sharp, Open Source Projects — ajlopez @ 11:47 am

These days I was working on reimplementing the core of my open source AjLisp lisp interpreter. I wrote about the previous version in my 2008 post:

AjLisp: a Lisp interpreter in .NET

The work is in progress. You can download the current code from:

http://code.google.com/p/ajlisp/source/browse/#svn/trunk/AjLisp

(there are two other implementations in that repository, work in progress: AjScheme, an Scheme-like lisp, and AjSharpure, following Clojure ideas). I should write more about these implementations. This post is the initial one in a series about this new AjLisp. It’s a short introduction to the current status of the project.

The main change in the new version: the interpreter can manage native objects and values. The alternative was to point to such objects using a wrapper, a class that implements SymbolicExpression or something similar. But I choose to point and manage direct native object and values. So, I changed the primitives and related classes to receive objects instead of IExpression. Now, there is an interface IExpression, that is defined:

    public interface IExpression
    {
        object Evaluate(ValueEnvironment environment);
    }

The ValueEnvironment (I'm planning to rename it to BindingEnvironment, and to derive from it an interface IBindingEnvironment) keeps nested association of names to values:

There is an interface IFunction:

    public interface IFunction
    {
        object Apply(List arguments, ValueEnvironment environment);
    }

that it should be implemented by any form expression (the head of a list to evaluate).

There are two main classes that represent the core types in AjLisp: identifiers and lists:

All the project was built using Test-Driven Development, so I could change the previous versions with courage: I had my battery of tests ready to help me in the refactoring process. This is the current status:

I should write about:

- ValueEnvironment implementation

- Native objects and values management

- List type and evaluation

- Identifier evaluation

- Implemented primitives

- Lexer and Parser

- Numeric operations

- Rational numbers (AjLisp can manage integral numerator/denominator pairs)

Currently, after the wisdom gained developing these projects (AjLisp, AjScheme, AjSharpure), I’m writing a minimal core AjCoreLisp, to show what are the minimal primivites we need to create a Lisp interpreter. Armed with such implementation, I would like to explore compilation alternatives (Dynamic Language Runtime is my first candidate). It could be overwhelming to me do such exploration based on a “bigger” interpreter like AjLisp. First, I’ll try to compile an interpreter with few primitives.

Keep tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

January 7, 2010

Agile Estimation by Mike Cohn

Filed under: Agile Software Devevelopment, Scrum, Software Development, Video — ajlopez @ 10:09 am

One of the frequent question from the attendees to my Scrum talks, is how to estimate an agile/Scrum project? Some month ago, I found this videos. I want to share with you. Mike Cohn is a recognized expert in Agile and Scrum world. You can visit his blog to learn more from him. In this two videos, he explain clearly what it means estimation in an agile project (involving the team, doing iterations, poker planning, all the Scrum practices…):

High resolution: http://www.youtube.com/watch?v=jeT0pOVg0EI

High resolution: http://www.youtube.com/watch?v=jeT0pOVg0EI

The video was taken in the March 20, 2007 Bay XP Meeting.

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

January 4, 2010

AjLisp family: implementing lisp interpreters in C#

Filed under: .NET, AjCoreLisp, AjLisp, AjScheme, AjSharpure, Lisp, Programming Languages — ajlopez @ 3:22 am

In the last months, I was active written Lisp interpreters. Since the eighties, I like to write such interpreters. One of my preferred exercises when I study a new programming language, is to write a Lisp interpreter.

In 2008, I published a code written in C#, AjLisp:

AjLisp: a Lisp interpreter in .NET

At mid of 2009, I started to research Clojure. Then, I decide to explore the news ideas of that language, reimplemeting it in C# (original Clojure is written in Java, but there is a version written in .NET, that compiles to .NET using Dynamic Language Runtime). It’s only an interpreter (I should study more about DLR or .NET compilation, to write down a compiler; and about how to do it… ;-). The result is work in progress, named AjSharpure (I named it AjClojure, but I had to change the name). You can see the code, under development:

http://code.google.com/p/ajlisp/source/browse/#svn/trunk/AjSharpure

Initially, my idea was to port “one-to-one” Clojure java code, but I realized that its code is not easily read, no test on code, no spefication about the behavior of dozens of methods, so I stopped, and rethinked my way. I took courage, forget my initial code, and start bottom-up, full TDD, implementing piece by piece, only trying to follow the external behavior of the language, instead of its internal implementation.

I stopped AjSharpure development, to study more about variables in Clojure, Shared Transactional Memory, and other topics. Then I back to 2008 version of AjLisp. I write a new version in 2009, with major refactoring of the previous one. Now, it can manage native objects and values. The trunk is at:

http://code.google.com/p/ajlisp/source/browse/#svn/trunk/AjLisp

There is no “plain vanilla” Lisp, and there are TWO main dialects: Common Lisp and Scheme. I don’t like Common Lisp (I should write a post about my reasons), so, in order to know more about Clojure and current Lisp development, I started AjScheme, an interpreter that implements most of the Scheme reference (I give up to implement macros as in Scheme, I back to mlambdas and alike):

http://code.google.com/p/ajlisp/source/browse/#svn/trunk/AjScheme

AjLisp was born following an old Christian Queinnec book (I didn’t find the code of that book in the web). He wrote a Lisp interpreter in Lisp itself. Queinnec use a simplified Lisp. But I want to study more about the minimal needed kernel. So, now I’m working on AjCoreLisp:

http://code.google.com/p/ajlisp/source/browse/#svn/trunk/AjCoreLisp

It has no parser or lexer. The idea is implement an minimal interpreter using AjCoreLisp as the basis: the result is named MinimaLisp, and it’s included in the trunk. I’m implementing few primitives, and I’m trying to write the rest of the common forms as functions or macros. A geeky decision: implement backspace macro expansion as a macro! See code at:

http://pastie.org/765371

Once I have AjCoreLisp stabilized, I will refactor AjLisp, AjScheme, to use a more slim kernel, but re-implementing the most used forms as primitives. I should measure the impact of using most used forms as macro. I’m confident on the successful of changes, since all is backed by a battery of test (TDD and tests save my day many times, when I refactored much of this code base).

I will write detailed posts about these different interpreters, variations over a leit motiv: the beautiful ideas of Lisp language.

Keep tuned!

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

January 2, 2010

GoRoutines and Channels in C#

Filed under: .NET, C Sharp — ajlopez @ 10:56 am

In my previous posts:

Channel and GoRoutines in AjSharp (Part 1)
Channel and GoRoutines in AjSharp (Part 2)

I described the implementation of goroutines and channels in my AjSharp interpreter. At the end of last year, I wrote a quick spike, implementing the same concepts, but this time directly in C#. You can download the code from

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

First, I port the Channel class:

public class Channel
{
    private AutoResetEvent sethandle = new AutoResetEvent(false);
    private AutoResetEvent gethandle = new AutoResetEvent(false);
    private object value;

    public void Send(object value)
    {
        this.gethandle.WaitOne();
        this.value = value;
        this.sethandle.Set();
    }

    public object Receive()
    {
        this.gethandle.Set();
        this.sethandle.WaitOne();
        object result = this.value;
        return result;
    }
}

The code has an static class GoRoutines, with methods like:

public static void Go(Action action)
{
    Thread thread = new Thread(new ParameterizedThreadStart(GoRoutines.RunAction));
    thread.IsBackground = true;
    thread.Start(action);
    //ThreadPool.QueueUserWorkItem(new WaitCallback(RunAction), action);
}

public static void Go(ITask task)
{
    Thread thread = new Thread(new ParameterizedThreadStart(GoRoutines.RunTask));
    thread.IsBackground = true;
    thread.Start(task);
    //ThreadPool.QueueUserWorkItem(new WaitCallback(RunTask), task);
}

You can launch an Action (a delegate System.Action<>, already defined in .NET framwork), in a new thread (I tried to put it in the queue tasks of ThreadPool, but, I don’t know why, the performance was too low; see my attemp in the comments in GoRoutines code).

When an action receives parameters, I encapsulated both in a Task<>, like this:

public class Task<T1, T2> : ITask
{
    private Action<T1, T2> action;
    private T1 parameter1;
    private T2 parameter2;

    public Task(Action<T1, T2> action, T1 parameter1, T2 parameter2)
    {
        this.action = action;
        this.parameter1 = parameter1;
        this.parameter2 = parameter2;
    }

    public void Run()
    {
        this.action(this.parameter1, this.parameter2);
    }
}

(there are Task classes for one, two and three parameters).

You can invoke GoRoutines.Go directly specifying an action and its parameters:

public static void Go<T1, T2>(Action<T1, T2> action, T1 parameter1, T2 parameter2)
{
    Go(new Task<T1, T2>(action, parameter1, parameter2));
}

You can write the invoke using lambda expressions:

[TestMethod]
public void RunGoRoutineWithTwoParameters()
{
    int i = 0;
    AutoResetEvent handle = new AutoResetEvent(false);
    GoRoutines.Go((x, y) => { i = x + y; handle.Set(); }, 2, 3);
    handle.WaitOne();
    Assert.AreEqual(5, i);
}

With all this implemented, I wrote a console application AjConcurr.Primes, reimplementing the primes examples of my previous post:

Channel numbers = new Channel();
GoRoutines.Go(() => { for (int k = 2; ; k++) numbers.Send(k);  });
Channel channel = numbers;
int prime = 0;
while (prime < 1000)
{
    prime = (int)channel.Receive();
    Console.WriteLine(prime);
    Channel newchannel = new Channel();
    GoRoutines.Go((input, output, p) =>
    {
       while (true)
       {
           int number = (int)input.Receive();
           if ((number % p) != 0)
               output.Send(number);
       }
    }, channel, newchannel, prime);
    channel = newchannel;
}

I love to see this code formatted in pastie:

http://pastie.org/761916

Next steps:

- Improve Channel to support multiple simultaneous producers and consumers.

- Add Futures support

- Add reactive programming features.

Keep tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

Theme: Shocking Blue Green. Get a free blog at WordPress.com

Follow

Get every new post delivered to your Inbox.

Join 67 other followers