Mono C# compiler as a service

Home

Od jakiegoś czasu pracuję nad aplikacją do generowania i analizowania wykresów rekurencyjnych. Temat sam w sobie jest bardzo ciekawy, więc może do niego wrócę w przyszłości, ale dzisiejszy post będzie o czymś innym.

Moja aplikacja między innymi wykonuje obliczenia na wektorach np.: oblicza różne odległości (euklidesową, Manhattan czy normę maksimum) między nimi. Dodawanie kolejnych algorytmów wymagało jednak każdorazowej rekompilacji aplikacji. Zacząłem więc szukać sposobu aby umożliwić użytkownikowi dodawanie własnych algorytmów w sposób dynamiczny. Innymi słowy potrzebowałem jakiegoś silnika skryptowego.

Początkowo pomyślałem o PowerShell'u, rozważałem również IronPython'a. Trafiłem jednak na krótki i treściwy post na temat biblioteki Mono.CSharp.dll, która stanowi część dobrze znanego projektu Mono. Opis wyglądał obiecująco dlatego postanowiłem wypróbować tą bibliotekę i był to strzał w dziesiątkę.

Jądrem biblioteki jest klasa Mono.CSharp.Evaluator, która służy do dynamicznego kompilowania i wykonywania kodu C#. Jej użycie jest wręcz trywialne. Oto prosty przykład Hello World!:

var settings = new CompilerSettings();
var ev = new Evaluator(new CompilerContext(settings, new ConsoleReportPrinter()));

ev.Run("using System;");
ev.Run("Console.WriteLine(\"Hello World!\");");

Użycie ConsoleReportPrinter powoduje, że wszelkie komunikaty kompilatora zostaną wypisane na ekran konsoli. Możemy też użyć klasy StreamReportPrinter, wtedy komunikaty zostaną zapisane do wskazanego strumienia. Klasa CompilerSettings pozwala natomiast skonfigurować różne aspekty pracy kompilatora. Kolejny prosty przykład pokazuje, jak zwrócić wynik ze skryptu:

ev.Run("Console.Write(\">\")");
ev.Run("var s = Console.ReadLine();");
var s = (string)ev.Evaluate("s;");

Ciekawe jest to, że możemy zmienić typ raz zadeklarowanej zmiennej np.:

ev.Run("int s = 1;");
ev.Run("Console.WriteLine(s);");
ev.Run("string s = \"Hello!\";");
ev.Run("Console.WriteLine(s);");
ev.Run("bool s = true;");
ev.Run("Console.WriteLine(s);");

Możliwe jest również zdefiniowanie klasy:

ev.Run("class Test { public string Fun(int i) { return \"Hello \" + i; } }");
ev.Run("Console.WriteLine(new Test().Fun(1));");

Załóżmy, że w oddzielnym projekcie mamy zdefiniowaną klasę Test2. Poniższy przykład pokazuje jak użyć jej w skrypcie:

ev.ReferenceAssembly(typeof(Test2).Assembly);
ev.Run("using TestLib;");
ev.Run("Console.WriteLine(new Test2().Welcome(\"Kate\"));");

Praca z klasą Mono.CSharp.Evaluator bardzo mi się podoba. To kawał dobrej roboty, zachęcam więc do wypróbowania. W kolejnych postach opiszę, jak w elegancki sposób przekazać argumenty do skryptu oraz kiedy warto skorzystać z metody Compile zamiast Run lub Evaluate.

Uwaga instalacyjna

Pisząc ten post korzystałem z wersji beta 3.0.3 Mono. Ostatnia dostępna stabilna wersja 2.10.9 zawiera bowiem błąd, który objawia się komunikatem:

Method 'Mono.CSharp.Location.ToString()' is security transparent, but is a member of a security critical type.

przy pierwszej próbie użycia klasy Evaluator.  Nie sprawdzałem ale możliwe, że z github'a można ściągnąć wersję bez tego błędu.

Jeszcze o radzeniu sobie z głęboką rekursją

Home

W poście opisałem ogólne podejście to radzenia sobie z bardzo głęboką rekursją, która prowadzi do StackOverflowException. Dzisiaj powrócę do tematu. Od czasu do czasu, oprócz pogłębiania wiedzy na temat bibliotek, framework'ów itd. lubię rozwiązywać różnego rodzaju algorytmiczne zadania programistyczne. Jakiś czas temu rozwiązywałem takie zadanie:

Zadana jest mapa świata w postaci prostokątnej tablicy dwuwymiarowej. Każdy element tablicy ma swój kolor. Sąsiadujące (stykające się jednym z boków) z sobą elementy tego samego koloru należą do jednego kraju. Należy policzyć liczbę krajów na tej mapie. Jeśli dwa elementy tablicy mają ten sam kolor, ale nie znajdują się w jednym ciągłym obszarze, to należą do różnych krajów. 

Poniższy rysunek przedstawia przykładową mapę takiego świata, na który składa się 6 krajów.



Zacznijmy od głównej metody wykonującej obliczenia. Koncepcja jest prosta. Nie ulega wątpliwości, że należy odwiedzić wszystkie elementy tablicy aby móc zwrócić poprawny wynik. Aby nie zliczać tego samego elementu dwa razy używam wartości Int32.MaxValue jako znacznika już odwiedzonych elementów. Jeśli odwiedzając kolejny element znajduję wartość inną niż Int32.MaxValue to znaczy, że danego elementu jeszcze nie odwiedziłem i zwiększam licznik krajów.

public int Count(int[][] map)
{
 if (map == null) return 0;
 
 if (map.Length == 0) return 0;

 var numberOfCountries = 0;

 for (var y = 0; y < map.Length; ++y)
 {
  for (var x = 0; x < map[0].Length; ++x)
  {
   if (map[y][x] != Int32.MaxValue)
   {
    numberOfCountries++;
    /* Zaznacz elementy należące do danego kraju */
    VisitCountry(map, map[y][x], y, x);
   }
  }
 }

 return numberOfCountries;
}

Co kryje się pod tajemniczym Zaznacz elementy należące do danego kraju? W pierwszym podejście napisałem funkcję rekurencyjną, która począwszy od zadanego elementu odwiedzała wszystkie pola należącego do danego kraju i oznaczała je jako odwiedzone.

public void VisitCountry(int[][] map, int currentColor, int y, int x)
{
 if (y < 0 || x < 0 || y >= map.Length || x >= map[0].Length) return;

 if (map[y][x] != currentColor) return;
            
 map[y][x] = Int32.MaxValue;

 VisitCountry(map, currentColor, y + 1, x);
 VisitCountry(map, currentColor, y, x + 1);
 VisitCountry(map, currentColor, y - 1, x);
 VisitCountry(map, currentColor, y, x - 1);
}

Poniżej kod testujący dla przykładu z początku postu:

int[][] map = new int[5][];

for (int i = 0; i < map.Length; ++i)
 map[i] = new int[4];

map[0][0] = 1; map[0][1] = 3; map[0][2] = 3; map[0][3] = 2;
map[1][0] = 1; map[1][1] = 2; map[1][2] = 3; map[1][3] = 2;
map[2][0] = 1; map[2][1] = 1; map[2][2] = 1; map[2][3] = 1;
map[3][0] = 2; map[3][1] = 3; map[3][2] = 3; map[3][3] = 1;
map[4][0] = 2; map[4][1] = 2; map[4][2] = 2; map[4][3] = 2; 

var result = Count(map);

W warunkach zadania było jednak napisane, że szerokość/wysokość mapy może znajdować się w przedziale od 1 do 1000000. Sprawdźmy, więc czy kod ten obsłuż dużo większą mapę:

int[][] bigMap = new int[10000][];
for (int i = 0; i < bigMap.Length; ++i)
{
 bigMap[i] = new int[10000];
 for (int j = 0; j < bigMap.Length; ++j)
  bigMap[i][j] = i;
}

var result = Count(bigMap);

Na mojej maszynie wystarczy już mapa 10000 x 10000 aby pojawił sie wyjątek StackOverflowException. Zgodnie z tym co napisałem we wcześniejszym poście metoda VisitCountry powinna więc wyglądać tak:

public void VisitCountry(int[][] map, int startY, int startX)
{
 var toCheck = new Queue<Tuple<int, int>>();
 toCheck.Enqueue(new Tuple<int, int>(startY, startX));

 var currentColor = map[startY][startX];

 while (toCheck.Count > 0)
 {
  var t = toCheck.Dequeue();

  if (t.Item1 < 0 || t.Item2 < 0 || t.Item1 >= map.Length || t.Item2 >= map[0].Length) continue;

  if (map[t.Item1][t.Item2] != currentColor) continue;

  map[t.Item1][t.Item2] = Int32.MaxValue;

  toCheck.Enqueue(new Tuple<int, int>(t.Item1 + 1, t.Item2));
  toCheck.Enqueue(new Tuple<int, int>(t.Item1, t.Item2 + 1));
  toCheck.Enqueue(new Tuple<int, int>(t.Item1 - 1, t.Item2));
  toCheck.Enqueue(new Tuple<int, int>(t.Item1, t.Item2 - 1));
 }
}

Tym razem mapa 10000 x 10000 i większe zostanie poprawnie obsłużona. Kod ten można jeszcze optymalizować. Na przykład zliczać ile pól się już odwiedziło i przerwać dalsze przetwarzanie, jeśli odwiedziło się wszystkie. Dalszą optymalizację kodu można potraktować jako ćwiczenie.

Go

Home

GO to komenda, która sygnalizuje, że narzędzie takie jak sqlcmd powinno wysłać bieżący batch kodu T-SQL do instancji SQL Server'a. Do tej pory nie przywiązywałem do niej dużej uwagi, skupiając się na właściwym kodzie. Pominięcie GO może jednak doprowadzić do kłopotów. Popatrzmy na poniższy skrypt, który tworzy procedurę składowaną pr_Fun.

IF OBJECT_ID(N'dbo.pr_Fun') IS NOT NULL
BEGIN
      DROP PROCEDURE dbo.pr_Fun
END
GO

CREATE PROCEDURE dbo.pr_Fun
AS
BEGIN
      /*...*/
      RETURN
END

GRANT EXECUTE ON dbo.pr_Fun TO public
GO

Na pierwszy rzut oka wygląda prawidłowo i jeśli spróbujemy go uruchomić wykona się bez żadnych problemów. Niestety ale zawiera błąd, który pojawi się dopiero kiedy z procedury pr_Fun spróbuje skorzystać użytkownik z ograniczonymi uprawnieniami. Otrzyma taki komunikat:

Msg 229, Level 14, State 5, Procedure pr_Fun, Line 1
The EXECUTE permission was denied on the object 'pr_Fun', database 'Test', schema 'dbo'.

Dlaczego? Stanie się tak ponieważ wbrew pozorom powyższy skrypt nie nada uprawnień do wykonywania procedury pr_Fun użytkownikom z rolą public. Dzieje się tak z powodu braku komendy GO w odpowiednim miejscu.

Jeśli uruchomimy powyższy skrypt, a potem podejrzymy kod procedury (np.: sp_helptext pr_Fun) to okaże się, że polecenie GRANT EXECUTE zostało dołączone do kodu procedury, zamiast zostać wykonane. Prawidłowa wersja powyższego skryptu powinna wyglądać tak:

...
END
GO

GRANT EXECUTE ON dbo.pr_Fun TO public
GO

Niestety ale uruchamiając skrypt z takim błędem nie zostaniemy o tym poinformowani, ani ostrzeżeni. Jest to dla mnie o tyle dziwne, że słowo kluczowe END jawnie wskazuje koniec kodu procedury, a skoro GO jest wymagane to można by o tym poinformować. Po drugie próba uruchomienia skryptu z takim samym błędem, ale tworzącego funkcję nie powiedzie się z powodu takiego błędu:

Msg 156, Level 15, State 1, Procedure fn_Fun, Line 8
Incorrect syntax near the keyword 'GRANT'.

Mała rzecz ale na wszelki wypadek dobrze o tym wiedzieć.

Code Retreat

Home

O Code Retreat, czyli swego rodzaju warsztatach programistycznych, usłyszałem po raz pierwszy całkiem niedawno, kiedy dyrektor działu, w którym pracuję, rzucił pomysł zorganizowania czegoś takiego w firmie. Od pomysłu do realizacji nie minęło dużo czasu i w ostatnią sobotę wraz z kolegami i koleżankami z pracy (około 20 osób) wzięliśmy udział w takich warsztatach prowadzonych przez Michała Taszyckiego.

Z czym to się je? Celem Code Retreat jest wymiana wiedzy pomiędzy uczestnikami warsztatów oraz nauka nowych rzeczy, których na co dzień nie używa się w pracy. Warsztaty takie składają się z kilku krótkich sesji, w moim przypadku było to 6 sesji po 45 minut, podczas których rozwiązuje się jakieś problemy programistyczne. Pracowaliśmy w parach i co jakiś czas wymienialiśmy się klawiaturą. W czasie każdej z sesji pary były różne, a ponieważ w wydarzeniu brali udział programiści C# i Java, czasami trzeba było programować w języku, którego nie używa się na co dzień.

Tematem przewodnim tego Code Retreat była gra w życie. W czasie każdej z sesji mieliśmy za zadanie zaprogramować taką grę, ale za każdym razem wymagania na metodykę pracy i użyte techniki programistyczne były inne. Co istotne, każda sesja kończy się usunięciem całego kody. Pogrubienie oznacza fizyczne, trwałe usunięcie kodu, a więc za każdym razem pracę rozpoczynaliśmy się od początku.

Należy podkreślić, że celem nie jest tak naprawdę napisanie działającej gry. Temat nie jest trudny, ale 45 minut to nie jest dużo czasu zważywszy na to, że przy okazji uczymy się nowych rzeczy. Główny cel to nauka, nauka i jeszcze raz nauka, w sprzyjających warunkach i bez stresu, a gra w życie czy inne zadanie to tylko pretekst.

Czego się nauczyłem? W czasie jednej z sesji mieliśmy na przykład zastosować czysto purystyczne podeście to Test Driven Development, czyli nie mogliśmy napisać linijki kodu bez testów. W innej sesji programując nie mogliśmy w ogóle używać myszki, no ewentualnie po to aby raz sprawdzić skrót i potem już go używać. W jeszcze innej sesji pisany kod powinien zawierać minimalną liczbę klauzul sterujących if, a najlepiej w ogóle itd. Zadania mogą być najróżniejsze.

Czy purystyczne trzymanie się TDD jest dobre? Uważam, że nie. Czy używanie tylko i wyłącznie klawiatury nie jest przesadę? Uważam, że dobrze znać skróty klawiaturowe i starać się minimalizować używanie myszki ale ona się też się przydaje. Czy programowanie bez if'ów ma sens, czy tak w ogóle się da? Ano da się, nie jest to może proste, ani oczywiste ale da się.

Zadania z takimi skrajnymi wymaganiami wyrywają jednak z rutyny, pokazują, że coś można zrobić inaczej, pobudzają do myślenia, rozszerzają horyzonty i to jest moim zdaniem SUPER. Niewątpliwą zaletą jest również integracja zespołu. Co by nie mówić, Code Retreat to po prostu świetna zabawa.

Podsumowując jestem bardzo zadowolony z udziału w Code Retreat. Przyznam, że początkowo byłem trochę sceptyczny, nie wiedziałem czego tak naprawdę się spodziewać, ale nie żałuję ani minuty spędzonej w sobotę w biurze :), w czym niewątpliwą zasługę ma również prowadzący Michał Taszycki.

Polecam Code Retreat!!!

StackOverflowException - jak sobie z nim radzić

Home

Każdy programista, czy to C#, C++ czy Java, musiał się kiedyś spotkać z przepełnieniem stosu, który, w przypadku platformy .NET, objawia się wyjątkiem StackOverflowException. Najłatwiej do takiego błędu doprowadzić pisząc nieskończoną rekursję. W tym poście zajmę się jednak tym jak poradzić sobie z przepełnieniem stosu, kiedy napisana metoda rekurencyjna wcale nie jest nieskończona. Zacznijmy od przykładu. Załóżmy, że mamy klasę Node i przy jej pomocy tworzymy drzewo binarne, w którym dla uproszczenia będziemy przechowywać liczby. Drzewa, które rozpatrujemy w tym przypadku nie są drzewami przeszukiwań i mogą być niezrównoważone.

public class Node
{
 public uint Data { get; set; }

 public Node Left { get; set; }
 public Node Right { get; set; }
}

Napisaliśmy również metodę rekurencyjną przeszukującą zadane drzewo w poszukiwaniu węzła przechowującego określoną wartość.

public static Node FindRec(Node root, uint i)
{
 if (root == null)
  return null;

 if (root.Data == i)
  return root;

 var res = FindRec(root.Right, i);

 if (res != null)
  return res;

 return FindRec(root.Left, i);
}

Metoda ta będzie działać, ale do czasu. Utwórzmy zdegenerowane drzewo czyli takie, które w rzeczywistości jest listą. Do wygenerowania takiego drzewa użyjemy następującego kodu:

public static Node CreateDegeneratedTree(uint noOfNodes)
{
 Node root = new Node() { Data = 0 };
 Node temp = root;

 for (uint i = 0; i <= noOfNodes; ++i)
 {
  temp.Right = new Node() { Data = i };
  temp = temp.Right;
 }

 return root;
}

W przypadku wystarczająco dużej liczby węzłów w zdegenerowanym drzewie (patrz parametr noOfNodes) wywołanie FindRec zakończy się wyjątkiem StackOverflowException. Wbrew pozorom, nie musi to być jakaś ogromna wartość. Na komputerze, na którym testowałem ten kod, wystarczyło aby drzewo zawierało 10 tyś węzłów. Trochę mało, czyż nie?

W takiej sytuacji musimy zrezygnować z rekursji na rzecz poczciwej pętli. Ja bym napisał taki kod:

public static Node Find(Node root, uint i)
{
 Queue<Node> toCheck = new Queue<Node>();
 toCheck.Enqueue(root);

 while (toCheck.Count > 0)
 {
  var node = toCheck.Dequeue();

  if (node != null)
  {
   if (node.Data == i)
    return node;
    
   toCheck.Enqueue(node.Right);
   toCheck.Enqueue(node.Left);
  }
 }

    return null;
}

Korzystam w nim z pomocniczej kolekcji, do której wrzucam kolejne węzły do sprawdzenia. Pętla kręci się dopóki nie zostanie znaleziony szukany węzeł albo dopóki wszystkie węzły nie zostaną sprawdzone. Podobne podejście możemy zastosować dla innych dla innych zagadnień tego typu.

Problem z StackOverflowException można również rozwiązać w sposób nie algorytmiczny, poprzez zwiększenie domyślnego rozmiaru stosu (1MB) przy pomocy narzędzia editbin albo tworząc nowy wątek o odpowiedniej wielkości stosu. Ja był jednak tego nie robił. Jeśli można osiągnąć jakiś efekt pisząc kod w odpowiedni sposób, to należy tak zrobić. W swojej karierze nie spotkałem jeszcze przypadku kiedy musiałbym zwiększyć wielkość stosu.

Na koniec załączam jeszcze kod metody Main. Cały program pozwala pobawić się pokazanymi powyżej metodami do wyszukiwania (iteracyjną i rekurencyjną) dla zdegenerowanego drzewa o zadanej liczbie węzłów. Program umożliwia również ustalenie wielkości stosu (w celach edukacyjnych :)). Kod może i jest trochę pokraczny, ale dla celów edukacyjnych się nada. Uwaga! Podanie zbyt dużej wartości jako Stack size in kilobytes (0 for default): albo Number of nodes in tree: może zakończyć się OutOfMemoryException.

static void Main(string[] args)
{
    Console.Write("Do you want to use recursion (Y for yes)?: ");
    
    string line = Console.ReadLine();
    bool useRecursion = String.Equals(line, "Y", StringComparison.OrdinalIgnoreCase);

    if(useRecursion)
        Console.WriteLine("Recursion search will be used");

    Console.Write("Stack size in kilobytes (0 for default): ");

    line = Console.ReadLine();
    uint stackSize;
    if (!UInt32.TryParse(line, out stackSize))
        stackSize = 1024

    Console.WriteLine("Stack size is {0} kilobytes ", stackSize);

    var th = new Thread(
  new ThreadStart(() =>
  {
   Console.Write("Number of nodes in tree: ");

   while ((line = Console.ReadLine()) != String.Empty)
   {
    uint noOfNodes;
    if (UInt32.TryParse(line, out noOfNodes))
    {
     Node root = CreateDegeneratedTree(noOfNodes);

     Stopwatch sw = new Stopwatch();

     if (useRecursion)
     {
      sw.Start();
      var res = FindRec(root, noOfNodes);
      sw.Stop();
     }
     else
     {
      sw.Start();
      var res = Find(root, noOfNodes);
      sw.Stop();
     }

     root = null;
     Console.Write("Processing time (ms): {0}\n\n", sw.ElapsedMilliseconds);
    }

    Console.Write("Number of nodes in tree: ");
   }
  }), (int)stackSize * 1024);

 th.Start();
}