Funny Prolog

Hello. Today I would like to speak a little bit not about C#. We will talk about strange language Prolog. At first I was interacted with it I was impressed that... there is no assignment operator in Prolog! Yes, that looks ugly, but even in general Prolog is not kind of languages we aware of.

Here's a short look at how Prolog differs from traditional programming languages.
Prolog is descriptive.
Instead of a series of steps specifying how the computer must work to solve a problem, a Prolog program consists of a description of the problem.
Conceptually, this description is made up of two components:
1.  descriptions of the objects involved in the problem
2.  facts and rules describing the relations between these objects
The rules in a Prolog program specify relations between the given input data and the output which should be generated from that input.

Source: "C:\Program Files\VIP52\DOC\Getstart.doc"

Actually there are operator like ‘=’, but we can use it only to not assigned before variables. But this is not matter of this short article. Its matter is just to describe few tasks solved by me, so they could provide some examples to you.

Let us start with following task: We need to build binary searching tree using data in file and then we will need to traverse tree to get sorted list.
As you see in this we will figure out how to work with files, lists in Prolog and also we will find out how build such structure as tree. Before we will start with this task I would like to mention that I’m using Prolog v5.2.

Next two lines are enough to have compliable program:

goal
write("hey, there!").

Now we will add treetype to domains. Following declaration means that tree can be written as functor tree or as functor empty. empty is required to mark empty leaf.

domains
treetype = tree(string,treetype,treetype);empty

As we are going to have binary tree we need to implement inserting strategy. At first it will insert value into empty tree, or if it is not empty it will insert in right if value is greater than current tree node otherwise it will insert into left one. So insert statements will look like:

predicates
  insert(string, treetype, treetype)
clauses
  % if current node is empty we will insert NewItem instead of it
  insert(NewItem, empty, tree(NewItem,empty,empty)):-!.
  % if NewItem is less than Element we insert it to left tree
  insert(NewItem, tree(Element,Left,Right), tree(Element,NewLeft,Right)):-
                NewItem < Element,
                !,
                insert(NewItem,Left,NewLeft).
  % otherwise we will insert it to the right tree
  insert(NewItem, tree(Element,Left,Right), tree(Element,Left,NewRight)):-
                insert(NewItem,Right,NewRight).

Next step is traversing. (If you could remember there are three types of traversing.) Let us imagine root node T with left tree L and right one R. Then traversing like T -> L -> R will be called preorder traversing. Code will look like:

predicates
traverse(treetype)
clauses
traverse(empty).
traverse(tree(Element,Left,Right)):-
write(Element, '\n'),
traverse(Left),
traverse(Right).

New step was to read data from the file... And here I got puzzled being. I played with not(eof(input)) few hours and got nothing. What solved my issue was funny - I looked into folder 'EXAMPLES' with searching for 'file' string and found my answer, I will describe below, but one note here: Always when you are blocked or feel angry because you cannot resolve that bad error first thing go to examples especially if technology is new for you, otherwise search internet, but do not bump the wall during few hours.

So, when readln(S) fails at EOF we need only another similar clause which do nothing to be ok with our processing. See:

  read_input(Tree):-
                read_input_aux(empty,Tree).

  read_input_aux(Tree, NewTree):-
                readln(Ln),
                !,
                insert(Ln, Tree, Tree1),
                read_input_aux(Tree1, NewTree).

  read_input_aux(Tree, Tree). /* The first clause fails at EOF. */

To easily work with list I wrote following clauses. Would like to mention that Lists in Prolog goes with paradigm of Head and Tail. So having list = integer*, we could write [H|T] for our usings, and H always is one element, T is ending list. To mark emtpy we need [].

  write_list([]).
  write_list([H|T]):-
                write(H,' '),
                write_list(T).
               
  append([],SecondList,SecondList).
  append([H|L1],SecondList,[H|L3]):-
                append(L1,SecondList,L3).

I changed traversing to pass ther List which I want to fill in with elements. To work with files you also need few lines. It is put global file variable, then use openread to open file, use readdevice to redirect standard input.

goal
  openread(input,"input.txt"),
  readdevice(input),
 
  read_input(Result),
  traverse(Result,OrderedList), 
  write_list(OrderedList),
 
  closefile(input).

For input file like "q w e r t y u i o p a ...." (new line instead of ' ') result will be "a b c d e f g ...".

 

Task number 2 is: Write Quick Sort agrorithm and apply it to some list. Yes, I know that there are lot of QuickSort examples in internet, but I haven't used them - I just wrote my own and I think it is somekind unique. Here is code:

domains
  item = integer
  list = item*
predicates
  nondeterm write_list(list)
  nondeterm append(list,list,list)
  nondeterm quicksort(list, list)
  nondeterm partition(list, item, list, list)
clauses
  write_list([]).
  write_list([H|T]):-
                write(H,' '),
                write_list(T).
  append([],SecondList,SecondList).
  append([H|L1],SecondList,[H|L3]):-
                append(L1,SecondList,L3).

partition([], Pivot, Smalls, Bigs).
partition([X|Xs], Pivot, Smalls, Bigs):-
                X < Pivot,
                !,
        partition(Xs, Pivot, Rest, Bigs),
        Smalls=[X|Rest].
partition([X|Xs], Pivot, Smalls, Bigs):-
        partition(Xs, Pivot, Smalls, Rest),
        Bigs=[X|Rest].

quicksort([],[]).
quicksort([X|Xs], SortedList):-
    partition(Xs, X, Smaller, Bigger),
    quicksort(Smaller, SortedSmaller),
    quicksort(Bigger, SortedBigger),
    append(SortedSmaller,[X|SortedBigger],SortedList).
goal
  quicksort([4,5,6,3,9,3,2,87,7,8], SortedList),
  write_list(SortedList).

Next 3rd task looks funny to work with it. It asks me to: Move List in Cycle for given number of elements in given direction.

domains
  item = integer
  list = item*
predicates
  nondeterm getNeededTail(list, integer, list, list)
  nondeterm append(list,list,list)
  nondeterm write_list(list)
  nondeterm listLen(list,integer)
  nondeterm moveList(list, integer, integer, integer, list, list)
clauses
  listLen([],0).
  listLen([H|T],N):-
                listLen(T,TailLen),
                N = TailLen+1.   
  append([],SecondList,SecondList).
  append([H|L1],SecondList,[H|L3]):-
                append(L1,SecondList,L3).
  write_list([]).
  write_list([H|T]):-
                write(H,' '),
                write_list(T).
               
  getNeededTail(InputTail, 0, NeededTail, NeededHead):-
                NeededTail = InputTail.
  getNeededTail([H|T], N, NeededTail, NeededHead):-
                N1 = N-1,
                getNeededTail(T, N1, NeededTail, NotDiscoveredHead),
                NeededHead = [H|NotDiscoveredHead].
               
  moveList(ListToMove,N,Direction,Len,GoodTail, GoodHead):-
                Direction < 0,
                !,
                getNeededTail(ListToMove,N,GoodTail, GoodHead).
  moveList(ListToMove,N,ToRight,Len,GoodTail, GoodHead):-
                N1 = Len - N,
                getNeededTail(ListToMove,N1,GoodTail, GoodHead).

goal
  write("Please enter direction. Number > 0 to right:"),
  readint(Direction),
  write("N:"),
  readint(N),
  ListToMove = [1,2,3,4,5,6,7,8,9,0],
  listLen(ListToMove,Len),
  CorrectedN = N mod Len,
  moveList(ListToMove,CorrectedN,Direction,Len,GoodTail, GoodHead),
  append(GoodTail,GoodHead,MovedList),
  write_list(MovedList).

4th task is quite also easy. Next clauses allow me to have new list formed out of my input by cutting positive values and squaring negative ones:

  modifyList([],[]).
  modifyList([H|T], ResultList):-
                H > 0,
                !,
                modifyList(T,ResultList).
  modifyList([H|T], ResultList):-
                modifyList(T,ModifiedList),
                HSquared = H*H,
                ResultList = [HSquared|ModifiedList].

Do you know what is Expert System? Ok. I do not want to write some real word expert system, but I need at least some to try how it works. So I took example out of examples folder and tried to change it to solve some other problem. Example I took has system which decides what kind of animal is animal you have in mind. It asks few simple questions and saves them to answers database. Then using backtracking if it fails on facts of current checkin' animal it goes to next animal and asks questions you haven't answered yet. note here: You should NOT always trust examples which are provided to you, even if they comes with commercial product.Why? Example I found there has one bug: it doesn't save negative answer for positive question. Understand? Ok... If you have question "Does it fly?" and answer is Yes system saves it to database so will not ask the same question, but if answer is No system will not save opposite and will ask same when will be checking other bird. This is code I'm talking about:

  ask(X,Y,yes):-
                !,
                write(X," it ",Y,'\n'),
                readln(Reply),nl,
                frontchar(Reply,'y',_),
                remember(X,Y,yes).

as you see if it fails on frontchar(Reply,'y',_) it will save nothing. So this was what I changed to example by introducing new clause rememberYesAnswer, which saves Yes and allow go further or saves No and fail checking of current item.

  ask(X,Y,yes):-
                !,
                write(X," it ",Y,'\n'),
                readln(Reply),nl,
                rememberYesAnswer(X,Y,Reply).
  rememberYesAnswer(X,Y,Reply):-
                frontchar(Reply,'y',_),
                !,
                remember(X,Y,yes).

  rememberYesAnswer(X,Y,Reply):-
                remember(X,Y,no),
                fail.

My expert system might be useful :) for grand master who forgot name of chess figure but know how it looks. It desides what chess figure are you trying to describe, by asking quesitons like "Is figure tall?" or "Is it first row figure?". BTW: Windows 7 has very great game called "Chesss Titans". I played it when writing this:

global facts
  xpositive(symbol,symbol)
  xnegative(symbol,symbol)
predicates
  figure_is(symbol) - nondeterm (o)
  ask(symbol,symbol,symbol) - determ (i,i,i)
  rememberYesAnswer(symbol,symbol,symbol)
  rememberNoAnswer(symbol,symbol,symbol)
  remember(symbol,symbol,symbol) - determ (i,i,i)
  positive(symbol,symbol) - determ (i,i)
  negative(symbol,symbol) - determ (i,i)
  clear_facts - determ ()
  run - determ ()

clauses
  figure_is(king):-
                positive(is,tall),
                positive(is,at_firts_row),
                positive(has,cross_at_the_top),
                positive(does,move_few_cells).

  figure_is(queen):-
                positive(is,tall),
                positive(is,at_firts_row),
                positive(does,move_very_well).
 
  figure_is(rook):-
                negative(is,tall),
                positive(is,at_firts_row),
                positive(does,move_forward_backward_sideway).

  figure_is(bishop):-
                positive(is,tall),
                positive(is,at_firts_row),
                positive(does,move_diagonally_only).

  figure_is(knight):-
                positive(is,at_firts_row),
                positive(is,short),
                positive(does,move_like_letter_L).
               
  figure_is(pawn):-
        negative(is,tall),
                negative(is,at_firts_row),
                positive(does,move_step_forward).     
               
  positive(X,Y):-
                xpositive(X,Y),!.
  positive(X,Y):-
                not(xnegative(X,Y)),
                ask(X,Y,yes).

  negative(X,Y):-
                xnegative(X,Y),!.
  negative(X,Y):-
                not(xpositive(X,Y)),
                ask(X,Y,no).

  ask(X,Y,yes):-
                !,
                write(X," it ",Y,'\n'),
                readln(Reply),nl,
                rememberYesAnswer(X,Y,Reply).
  ask(X,Y,no):-
                !,
                write(X," it ",Y,'\n'),
                readln(Reply),nl,
                rememberNoAnswer(X,Y,Reply).
               
  rememberYesAnswer(X,Y,Reply):-
                frontchar(Reply,'y',_),
                !,
                remember(X,Y,yes).
  rememberYesAnswer(X,Y,Reply):-
                remember(X,Y,no),
                fail.
                               
  rememberNoAnswer(X,Y,Reply):-
                frontchar(Reply,'n',_),
                !,
                remember(X,Y,no).
  rememberNoAnswer(X,Y,Reply):-
                remember(X,Y,yes),
                fail.
               
  remember(X,Y,yes):-
                assertz(xpositive(X,Y)).
  remember(X,Y,no):-
                assertz(xnegative(X,Y)).

  clear_facts:-
                write("\n\nPlease press the space bar to exit\n"),
                retractall(_,dbasedom),
                readchar(_).

  run:-
                figure_is(X),!,
                write("\nYour figure may be a (an) ",X),
                nl,
                clear_facts.
  run:-
                write("\nUnable to determine what"),
                write("your figure is.\n\n"),
                clear_facts.

goal
  run.

Also I have few other tasks, but will put them some other time. Thank you for attention.

 

Inversion Of Control and Dependency Injection

At first I would like mention that I'm not first who writes such article, but I find this to be very interesting. I will start with describing of Inversion Of Control in theory starting from easy, then I will move to usage of StructureMap.

I interacted with Inversion Of Control Containers aka StructureMap when I even haven't understanding what is it and why is it needed. I got few UT failures, saying that something is wrong with IoC setup. And I spent a lot of time figuring out what is that bootstrap class doing. So this was my first interaction. Then I decided to prepare Developers Meeting on this theme.


Inversion of Control and Dependency Injection


We will start with example which is very similar to Martin Fowler's (http://martinfowler.com/articles/injection.html) and then will move to StructureMap using. So let us imagine that we have class MusicPlayer, which has method GetBandSongs. That method will work with SongFinder to get all songs and then will filter out songs which are created by some particular band.

public class MusicPlayer
{
    private SongFinder songFinder;
    public MusicPlayer()
    {
        songFinder = new SongFinder();
    }
    public Song[] GetBandSongs(String band)
    {
        var allsongs = songFinder.FindAllSongs();
        return allsongs.Where(x => x.Band == band).ToArray();
    }
}

As we see Music Player is coupled to SongFinder and this is not good thing. Why? At first because of extensibility issue. If SongFinder will need to use plain text file instead of XML we will need rewrite body of SongFinder, at second testability is low because we cannot pass songs into PlayBandSongs method to test it, and at third reusability is also low because logic is too generic…
Let us do some refactoring with introducing interface for SongFinder, let us call it ISongFinder.

public interface ISongFinder
{
    Song[] FindAllSongs();
}

Now we will have MusicPlayer with member of this interface type. So this allows us work with different sources of data. i.e. logic no longer depend on concrete realization.

private ISongFinder songFinder;
public MusicPlayer()
{
    songFinder = new  SongFinder();
}

But the Music Player is still coupled to concrete realization of finder. Current design looks like:

I do think that you want to say “Hey, put finder into player constructor!”, and you are very right here. This is one of ways how to inject dependency here. And this is pure good idea, but there are other ones which leads us to something which will give possibility to inverse controlling.
Ok, let us create factory which will create for us instances of ISongFinder. See:

public class SongFinderFactory
{
   public ISongFinder GiveUsDatabaseSongFinder()
   {
      return  new SongFinder();
   }
}
public  MusicPlayer()
{
   songFinder =  SongFinderFactory.GiveUsDatabaseSongFinder();
}

And the UML:

Now we have Player decoupled from SongFinder, because creation is redirected to Factory.
Another way to have decoupled code is to introduce here Service Locator. Using Service Locator we can register couple of services and then use one of the registered somewhere we need. So we have some code which registers services we will use, let call it Assembler, and we have code where we are using particular services. Easy! See:

///
/// Using Service Locator we can register services for our application.This should be one storage,
/// so we make methods static
///
public static class ServiceLocator
{
    private static Dictionary m_services = new Dictionary();
    public static void RegisterService(Type type, Object implementation)
    {
        m_services.Add(type, implementation);
    }
    public static Object GetService(Type type)
    {
       if(m_services.ContainsKey(type))
       {
          return m_services[type];
       }
       return null;
    }
}
// Services Registering code
// It decoupled to ISongFinder, SongFinder and to ServiceLocator,
// but this is Assembler code, and that is good
static void RegisterServicesNeeded()
{
   ServiceLocator.RegisterService(typeof(ISongFinder), new SongFinder());
   //register another services as needed
}

Let us now take a look at constructor of MusicPlayer:

public  MusicPlayer()
{
   var fiderService =  ServiceLocator.GetService(typeof (ISongFinder));
   songFinder =  (ISongFinder)fiderService;
}

And the design with ServiceLocator will look like here:

Now we got testable, reusable and extensible code. Looks very fine, but doesn’t it look difficult? Could be, because after we got decoupling of MusicPlayer and SongFinder we also got sequence dependence, our service depends on infrastructure code and we need to do cumbersome setup in tests. Actually that is correct, but system with possibility to setup Dependencies somewhere in one place is much better. That is not all. This times we have lot of IoC containers, so they allow us to configure dependency via config file or either through reflection in code during run-time!
We continue with adding to our project one of the IoC containers – StructureMap. (http://structuremap.sourceforge.net/Default.htm) With this we will no longer need our own Service Locator. So now we can setup dependencies in some Bootstrap once, but this is not static dependencies setup - we can use different implementations for different scenarios.
Let us refactor MusicPlayer with StructureMap. Registration code will look like:

ObjectFactory.Initialize(x =>x.ForRequestedType<ISongFinder>).TheDefaultIsConcreteType<SongFinder>());

And MusicPlayer constructor will be like:

public MusicPlayer()
{
     songFinder = ObjectFactory<ISongFinder>.GetInstance();
}

So, with these two lines of code we replaced functionality of ServiceLocator. Ok let us imagine that we have Constructor dependency:

public MusicPlayer(ISongFinder sngFinder)
{
     songFinder = sngFinder;
}

Now we can setup dependencies like here:

ObjectFactory.Initialize(x =>
{
    x.ForRequestedType<MusicPlayer>().TheDefaultIsConcreteType<MusicPlayer>();


    x.ForRequestedType<ISongFinder>().TheDefaultIsConcreteType<SongFinder>();


});

And get instance of MusicPlayer by ObjectFactory. And this is quite amazing thing here, because our IoC Container built dependencies tree and did all required initialization.

var musicPlayer = ObjectFactory<MusicPlayer>.GetInstance();

In real world applications we could have framework built on interfaces and we could have couple of the pluggable assemblies which goes with IoC configuration, so IoC Containers make difference between framework and library.
CodeProject

Measure execution time

Today I was asked to find the best way of measuring execution time of DoSomeWork() method.

MSDN gives the pretty fine answer for this, but google gives too much links with using DateTime.Now to measure execution time.

System.Environment.TickCount and the System.Diagnostics.Stopwatch class are two that work well for finer resolution and straightforward usage.

Stopwatch Class provides a set of methods and properties that you can use to accurately measure elapsed time.

See MSDN:

http://msdn.microsoft.com/en-us/library/system.diagnostics.stopwatch.aspx

http://msdn.microsoft.com/en-us/library/system.environment.tickcount.aspx

Example code:

1. using System;
3. using System.Diagnostics;
5. using System.Threading;
7. class Program
9. {
11.     static void Main(string[] args)
13.     {
15.         Stopwatch stopWatch = new Stopwatch();
17.         stopWatch.Start();
19.         DoSomeWork();
21.         stopWatch.Stop();
23.         // Get the elapsed time as a TimeSpan value.
25.         TimeSpan ts = stopWatch.Elapsed;
27.         // Format and display the TimeSpan value.
29.         string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",
31.             ts.Hours, ts.Minutes, ts.Seconds,
33.             ts.Milliseconds / 10);
35.         Console.WriteLine(elapsedTime, "RunTime");
37.     }
39.     static void DoSomeWork()
41.     {
43.       // code does hard work here :)
45.     }
47. }

First Blog or why did I start this?

Hello,

Me, being a student, started to work early in one really dedicated company. That company made me very pragmatic. I found that there are people that want to got to success and there are others who likes to swim easily as the river says.

I'm not a kind of such people. After I read couple of books on success (Robert Kiosaki, Bodo Scheffer, Napoleon Hill) and at the same moment my company started to develop our own certification model for Developers. I found a target for myself in my life.

Sometimes people needs promotion, when they work for it. And this is what I got in the middle of Spring 2009. I was promoted to Intermediate Developer, after working 11 months as Junior Developer.

My next target is to became Senior Developer before I'll get Master Diploma. You would say my company is poor if it will promote you or your University is bad as it allows you to work at the time you are learning. What I would say is: I'm pragmatic and this is my way to Success, so I will broke any wall you will put on my way.

First purpose of this blogging is to have place where I can put my Developer founds, investigations, thoughts on different technologies, etc. 

Second purpose it to help you in your findings over Internet. I know that google knows all, but  google doesn't know things that only particular persons found and did not post it somewhere. I will be posting my founds so google will know more. 

I hope this will help you and me.