Ten wpis jest tłumaczeniem części artykułu pt. "MVP-Submitted: Calculating with Infinite Sequences in C#" zamieszczonego na stronach Visual C# Developer Center. Powstało ono jako część zaliczenia jednego z przedmiotów na studiach. Początkowo nie miałem zamiaru upubliczniać tej pracy. Dlaczego? Ponieważ to tłumaczenie nie kładzie nacisku na ściśle techniczny język. Starałm się raczej uchwycić główną ideę przekazywanych myśli i pisać tak, aby zrozumiał laik :).

Zmotywował mnie jeden z kolegów, chociaż muszę przyznać, że nie bez znaczenia był też e-mail od Tomasa: "I'd definitely love to see a link to the translated article once it is published!".

Autor: Tomas Petricek.

Tłumaczenie: Karol Chęciński

 

Mój poprzedni artykuł traktował o opóźnionym wykonywaniu i skupiał się na tym jak się je symuluje w C#. Zaimplementowaliśmy klasę Lazy<T>, która reprezentuje wartość obliczaną na żądanie –oznacza to, że klasa „wie” jak obliczyć wartość wyrażenia, ale nie robi tego dopóki faktycznie nie jest ona potrzebna w programie. Bardzo interesującą strukturą danych, znaną z programowania funkcjonalnego, którą można zaimplementować używając tej opóźnionej komórki jest opóźniona lista. Każdy element tej listy zawiera wartość związaną numerem (na przykład liczbę) i wie jak przeliczyć następny element na liście, ale jest opóźniony co oznacza, że kolejny element nie zostanie obliczony, dopóki program nie odwoła się do jego wartości. Najbardziej interesującym aspektem opóźnionych list  jest to, że mogą by użyte do reprezentowania sekwencji nieskończonych – jest to możliwe ponieważ elementy są przeliczane tylko jeśli są potrzebne i dlatego lista zawsze będzie zawierać tylko skończoną liczbę elementów i ciągle będzie mogła przeliczać kolejne jeśli będzie to konieczne.

                 W tym artykule pokażę, że opóźnioną listę można zaimplementować używając typu IEnumerable<T>, a także zademonstruję jak operacje na zapytaniach LINQ mogą być użyte do manipulowania nieskończoną listą. Ostatecznie spojrzymy na implementacje sekwencji Mandelbrota (widać go na obrazku obok) używając technik opisanych w tym artykule.

 

Wprowadzenie do IEnumerable.

 

                Większość z Was najpewniej wie, że sekwencje w .NET można reprezentować używając interfejsu IEnumerable<T>. Można go użyć do enumerowania jednostek w standardowych kolekcjach takich jak tablice, listy, słowniki oraz w specjalnych kolekcjach. Tego interfejsu używa się często razem z pętlą foreach. Przejrzyjmy najpierw metody tego interfejsu. (Inne metody takie jak te dziedziczone po IDisposable nie są ważne dla naszego przykładu):

 

interface IEnumerable<T> : IDisposable<T>
{
  public void Reset();
  public bool MoveNext();
  public T Current { get; }
  // ... other methods omitted ...
}

 

                Enumerowanie w strukturze danych robi się używając trzech metod pokazanych w poprzednim przykładzie kodu. Najpierw wywoływana jest metoda Reset aby przesunąć wskaźnik enumeratora przed pierwszy element. Potem metoda MoveNext przesuwa enumerator do następnego elementu w sekwencji albo zwraca fałsz jeśli nie ma więcej elementów. Podczas enumeracji można dostać się do wybranego elementu używając właściwości Current.

 

class MyList {
  int[] elements;
  IEnumerabl<int> GetEnumerable() {
    for(int i=0; i<elements.Length; i++)
      yield return elements[i];
  }
}

                Przed wersją 2.0 C#, trzeba było zaimplementować ten interfejs gdy chciało się pozwolić na enumerację własnej kolekcji danych. To wprowadzało niepotrzebne skomplikowanie, więc w C# 2.0 wprowadzono zwracanie wartości yield. Używając tego słowa kluczowego, implementacja własnego numeratora jest tak łatwa jak iterowanie po wszystkich elementach w pętli. Spójrzmy bardzo prosty przykład:

 

var en = myList.GetEnumerable(); 

 

                Ta klasa pokazuje jak metoda która zwraca implementację IEnumerable<T> może być używana do enumerowania wszystkich elementów w tablicy. Ciało tej metody nie zwraca bezpośredniej implementacji interfejsu - zamiast tego używa zwracania yield, które jest kompilowane do implementacji interfejsu przez kompilator C#. Zrozumienie czym jest ten kod jest łatwe (po prostu iteruje po wszystkich elementach i zwraca każdy element oddzielnie z tablicy używając yield), ale wyjaśnienie jak ten kod jest używany do implementacji interfejsu IEnumerable<T> wymagałoby kolejnego artykułu. Ważną rzeczą do zrozumienia jest to co się dzieje podczas wywoływania metody zaimplementowanej przy pomocy zwracania yield jak w przykładzie poniżej:

                Kiedy wykonuje się to wywołanie, obiekt generowany przez kompilator jest tworzony, ale ani jedna linia (z napisanego przez ciebie kodu) nie jest realizowana! Realizacja kodu zaczyna się po użyciu metody MoveNext. Wchodzi ona do pierwszego wystąpienia zwracania yield a następnie „porzuca” metodę, a kontrola jest przekazywana z powrotem do metody wzywającej metodę MoveNext. Oczywiście nie jest możliwe wyjście z realizowanej metody i ponowne „wskoczenie” (utrzymywanie oryginalnych stanów zmiennych w metodzie), więc kompilator musi przetłumaczyć kod w metodzie na klasę, podnieść rangę zmiennych i skonwertować na właściwości klasy oraz wygenerować kod implementujący przejście między każdym użyciem zwracania yield. Kompilator C# tłumaczy kod metody na stan maszynowy gdzie każde użycie zwracania yield odpowiada pojedynczemu stanowi.

Nieskończone sekwencje i operacje na zapytaniach LINQ

                Najważniejszą rzeczą jaką chciałem uwypuklić w poprzedniej części jest to, że całe ciało metody nie jest realizowane dopóki nadrzędna metoda powtarzająco wykonująca MoveNext nie dojdzie do końca (i zwróci fałsz). To oznacza, że jeśli napiszemy kod, który wykonywał by się bez końca, ale zawrzemy wywołanie zwracania yield wewnątrz tego kodu, nie spowodujemy pętli nieskończonej. Spójrzmy na najprostszy z możliwych przykład:

 

IEnumerable<int> GetNumbers()
{
  int i = 0;
  while(true) yield return i++;
}

// Create an infinite sequence of integers
var nums = GetNumbers();

                Metoda GetNumbers w prezentowanym kodzie zwraca implementację IEnumerable<int>, która może być używana do przechodzenia w pętli po wszystkich typach liczbowych zaczynając od 0. Ponieważ typ liczbowy ma ograniczony zasięg, wartości zostaną przeładowane, a enumerowanie zacznie się znowu od Int32.MinValue.

                W powyższym przykładzie używamy tej metody do stworzenia zmiennej nums. Jej wywołanie zwyczajnie zwraca liczbę kiedy wykonujemy MoveNext – ani w środku, ani sama z siebie nie powoduje żadnych nieskończonych pętli. Jednakże ciągle trzeba być ostrożnym używając tego kodu. Podanie go jako argument do foreach spowoduje nieskończoną pętlę, ponieważ foreach będzie kontynuować wzywanie MoveNext dopóki ta metoda nie zwróci fałszu, co nigdy się nie stanie w przypadku sekwencji generowanej przez metodę GetNumbers!

 

var sq = GetNumbers().Where(n => n % 2 == 0).Select(n => n * n);

                Teraz spójrzmy na to, co się stanie gdy użyjemy zapytania LINQ operującego na nieskończonej sekwencji, którą właśnie zdeklarowaliśmy. W poniższym przykładzie używamy metody Where rozszerzenia, żeby odfiltrować tylko równe liczby i metody Select rozszerzenia żeby obliczyć kwadrat odfiltrowanej (równej) liczby:

 

var sq = from n in GetNumbers() where n % 2 == 0 select n * n;

Możemy użyć zrozumiałego zapytania z C# 3.0, żeby napisać semantycznie taki sam kod:

                Czy to spowoduje nieskończoną pętlę? Nie, ponieważ ciągle pracujemy z opóźnionymi wykonaniami sekwencji reprezentowanych przez IEnumerable<int>. Wywołanie operatora Where zapytania zwraca nową sekwencje z metodą MoveNext, z tym, że ta, wywoływana, iteruje po danej sekwencji dopóki nie znajdzie równej liczby. Podobnie, pojedynczy krok w sekwencji zwracany przez operator Select polega tylko na przeliczeniu kwadratu wziętego elementu. Jedynym pozostającym problem jest to, że musimy być ostrożni podczas wyświetlania sekwencji, ponieważ nie możemy po prostu użyć foreach. Na szczęście LINQ dostarcza operator zapytania Take, który zwraca sekwencję zawierająca pierwszych X elementów, więc można napisać taki kod:

 

foreach(int n in sq.Take(10))
  Console.WriteLine(n);
            

                Widać wyraźnie, że Where i Select to nie wszystkie operatory zapytania, których można używać z nieskończonymi sekwencjami, ale trzeba być ostrożnym: na przykład Aggregate, Reverse albo inne operatory łączące muszą iterować po wszystkich elementach, co nie jest możliwe pracując z sekwencjami nieskończonymi. Ostatecznie, można implementować własne iteratory do wykonywania operacji, które nie są dostępne w standardowych operacjach zapytań LINQ – po więcej informacji można zajrzeć do artykułu „Własne interatory” Billa Wagnera w Centrum Programistów C#.

[Koniec tłumaczenia części pierwszej :). Są chętni na drugą?]