WolframAlpha

Home

WolframAlpha to ambitny projekt stworzenia silnika, który umiałby odpowiadać na pytania wyrażone w języku naturalnym, a co więcej odpowiedzią nie byłaby sucha lista stron w Internecie, ale zbiór faktów stanowiących odpowiedź na pytanie. O tym przedsięwzięciu wiedziałem już od dłuższego czasu, ale traktowałem je raczej jako nowinkę i go nie używałem.

Ostatnio kolega zwrócił mi jednak uwagę na możliwość rozwiązywania równań przy pomocy tego silnika. Od tej pory przestałem traktować go tylko jako ciekawostkę i jest pod ogromnym wrażeniem tego projektu, zastosowanych w nim algorytmów, no i oczywiście umiejętności programistów.

Może mały przykład. Jakiś czas temu inny kolega wysłał mail'a z zaproszeniem do poczęstunku z okazji urodzin, ale swój wiek podał w taki oto sposób:



Prawa część równania nie stworzy chyba nikomu problemów. Gorzej jednak z tą całką i sumą szeregu matematycznego, chociaż wyglądają znajomo. Kiedy byłem świeżo po kursie analizy matematycznej pewnie obudzony w środku nocy, po libacji alkoholowej, podałbym wynik bez zastanowienia ;) Teraz jednak, zamiast przypominać sobie wzory, wklepałem to równanie do WolframAlpha:

sum x = 1 to infinity 1/x^2)/(integral from -1 to 1 (1-x^2)^0.5)^2*(2^2^3 - 2^2^2)/2^2

i w mgnieniu oka uzyskałem wynik. Silnik potrafi również rysować wykresy, rozpoznaje rodzaje funkcji np.: powie, że zadane równanie to paraboloida, liczy pochodne, wyznacza nie tylko wartość całki oznaczonej, ale również potrafi policzyć całkę nieoznaczoną, rozwiązuje równania różniczkowe oraz robi pewnie setki innych rzeczy, o których jeszcze nie mam pojęcia. W każdym razie WolframAlpha na stałe zagości w moim przyborniku.

Mono C# compiler as a service 3

Home

Ponownie wrócę do tematyki kompilowania C# w locie. Pisałem wcześniej, że potrzebowałem takiej funkcji aby użytkownicy mojej aplikacji mogli w dowolnym momencie zdefiniować własny algorytm obliczania odległości między dwoma wektorami.

Po kilku próbach już wiedziałem jak to zrobić, a chwilę później miałem już zaimplementowaną pierwszą wersję rozwiązania. Przyszła pora wypróbowania nowej zabawki na prawdziwych danych. Uruchomiłem więc aplikację, napisałem krótki skrypt i wystartowałem obliczenia. W tym momencie aplikacja zamarła i było widać, że pożera wszelkie dostępne zasoby. Spodziewałem się czegoś innego :). Skończyło się zabiciem aplikacji. Co zrobiłem nie tak?

Dane jakich użyłem zawierały kilkaset tysięcy wektorów. Oznacza to, że odległość między wektorami musiała zostać obliczona "dużoooooooooooooooooooooo" razy. Każda taka operacja powodowała wywołanie omówionej już metody Evaluator.Run, czyli za każdym razem ten skrypt był ponownie kompilowany, a to trochę trwa. Ziarnko do ziarnka, a zbierze się miarka jak mówi przysłowie. Co więcej każde wywołanie Evaluator.Run powoduje załadowanie do pamięci kolejnego dynamicznie utworzonego modułu. Moduły te są potem usuwane ale to też trwa. W ramach eksperymentu proponuję uruchomić pod kontrolą debugger'a taki kod:

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

for (int i = 0; i < 1000; ++i)
 ev.Run("System.Console.WriteLine(\"Hello!\");");

Zamiast zobaczyć, że kod wykonuje się błyskawicznie, zaobserwujemy jak VS próbuje załadować symbole dla kolejnych modułów (komunikat w rodzaju Loading symbols for eval-120... na pasku stanu). Jeśli postawimy pułapkę wewnątrz pętli i otworzymy okno Modules to na liście znajdziemy np.: eval-100, eval-101, eval-102...

W takiej sytuacji skrypt należy skompilować raz, a potem wielokrotnie używać wyniku kompilacji. Służy do tego metoday Evaluator.Compile, która zwraca instancję klasy CompiledMethod. Jeśli chcemy wywołać tak przygotowany skrypt korzystamy z metody CompiledMethod.Invoke. Nic trudnego. Parametry do takiego skompilowanego skryptu można przekazać w dokładnie taki sam sposób jak opisałem w poprzednim poście. Po zmianach powyższy kod będzie wyglądał jak poniżej i wykona się błyskawicznie:

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

var method = ev.Compile("System.Console.WriteLine(\"Hello!\");");

object o = null;
for (int i = 0; i < 1000; ++i)
 method.Invoke(ref o);

Na koniec dodam, że po zastosowaniu takiego zabiegu nie widzę różnicy w czasie odpowiedzi pomiędzy przypadkiem kiedy używam algorytmu osadzonego/wkompilowanego w aplikację, a algorytmu dostarczonego przez użytkownika.

Mono C# compiler as a service 2

Home

Dzisiaj wrócę do tematu użycia języka C# jako języka skryptowego przy pomocy Mono.CSharp.dll i opiszę w jaki sposób przekazać parametry do takiego skryptu. Pominę podejście opierające się o wklejanie do skryptu string'owej reprezentacji takich parametrów i od razu przejdę do bardziej eleganckiego rozwiązania. Bazuje ono na tym co przeczytałem w tym poście.

Zaczynamy od utworzenia statycznej klasy ScriptContext, która posłuży nam do wymiany danych pomiędzy skryptem, a naszym programem.

namespace Scripting
{
    public static class ScriptContext
    {
        static ScriptContext()
        {
            Items = new Dictionary<string, object>();
        }

        public static object Result { get; set; }

        public static IDictionary<string, object> Items { get; set; }
    }
}

Użycie jej nie jest trudne. Mały przykład:

var settings = new CompilerSettings();
var ev = new Evaluator(new CompilerContext(settings, new ConsoleReportPrinter()));
            
//Informujemy silnik skryptowy gdzie została zdefiniowana klasa ScriptContext
ev.ReferenceAssembly(typeof(ScriptContext).Assembly);

//Ustawiamy parametry
ScriptContext.Items["param1"] = new List<string> { "Hello!", "Welcome!", "Hi!" };

ev.Run("using System;");
ev.Run("using Scripting;");
//Korzystamy z przekazanych parametrów
ev.Run("foreach(var s in (System.Collections.Generic.IEnumerable<string>)ScriptContext.Items[\"param1\"]) Console.WriteLine(s);");

Właściwość ScriptContext.Result dodałem aby nie musieć zastanawiać się kiedy wywołać metodę Evaluator.Run, a kiedy Evaluator.Evaluate. Zawsze używam tej pierwszej, zakładając, że wynik ze skryptu zwracany jest przy użyciu tej właściwości np.:

ev.Run("ScriptContext.Result = 1;");
Console.WriteLine(ScriptContext.Result);

Do szczęścia brakowało mi jednak jeszcze jednej rzeczy. Jak pokazuje pierwszy przykład musiałem użyć rzutowania do IEnumerable<string> aby cieszyć się silnie typowanym parametrem. Napisałem więc metody pomocnicze, które przygotowują silnie typowane parametry:

public static class ScriptingHelper
{
 public static StringBuilder PrepareParameters(IDictionary<string, object> parameters)
 {
  ScriptContext.Items = parameters;

  var sb = new StringBuilder();

  if (parameters != null)
  {
   foreach (var kvp in parameters)
   {
    var typeName = ExtractTypeName(kvp);

    sb.AppendFormat("var {0} = ({1}){2}.Items[\"{0}\"];", kvp.Key, typeName, typeof(ScriptContext).Name);
    sb.AppendLine();
   }
  }

  return sb;
 }

 private static string ExtractTypeName(KeyValuePair<string, object> kvp)
 {
  if (kvp.Value == null)
   throw new Exception("null parameters are not supported!");
   
  var type = kvp.Value.GetType();

  using (var provider = new CSharpCodeProvider())
  {
   var typeRef = new CodeTypeReference(type);
   return  provider.GetTypeOutput(typeRef);
  }
 }
}

Nic bardzo skomplikowanego ale warto zwrócić uwagę na użycie klasy CSharpCodeProvider. Dzięki niej uzyskuję poprawną, pełną nazwę typów, również tych generycznych. Gdybym na przykład dla listy int'ów spróbował użyć czegoś w rodzaju list.GetType().Name to w wyniku otrzymałbym List`1, co do rzutowania się nie nadaje. Wcześniejszy przykład można więc napisać teraz w taki sposób:

//Ustawiamy parametry
var parameters = ScriptingHelper.PrepareParameters(new Dictionary<string, object>
{
 {"param1", new <string> { "Hello!", "Welcome!", "Hi!" } }
});

ev.Run("using System;");
ev.Run("using Scripting;");
ev.Run(parameters.ToString());
//Korzystamy z przekazanych parametrów ale już bez rzutowania
ev.Run("foreach(var s in param1) Console.WriteLine(s);");

Wracając do mojej aplikacji, w której chciałem umożliwić użytkownikowi definiowanie własnych algorytmów obliczania odległości między wektorami. Dane wejściowe to oczywiście dwa wektory. Dzięki takiemu podejściu, zamiast zmuszać użytkownika to rzutowania parametrów na określony typ, używam konwencji czyli: wektor numer 1 znajduje się w zmiennej vector1 itd.

Klasa ScriptingHelper jest również doskonałym miejsce na dodawanie różnych innych "przydasiów" ułatwiających pracę użytkownikowi.

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.