Posts tagged ‘Python’

Decorators with Optional Arguments in Python

2011-12-13 18:34

It is common that features dubbed ‘syntactic sugar’ are often fostering novel approaches to programming problems. Python’s decorators are no different here, and this was a topic I touched upon before. Today I’d like to discuss few quirks which are, unfortunately, adding to their complexity in a way that often doesn’t feel necessary.

Let’s start with something easy. Pretend that we have a simple decorator named @trace, which logs every call of the function it is applied to:

  1. @trace
  2. def some_function(*args):
  3.     pass

An implementation of such decorator is relatively trivial, as it wraps the decorated function directly. One of the possible variants can be seen below:

  1. def trace(func):
  2.     def wrapped(*args, **kwargs):
  3.         logging.debug("Calling %s with args=%s, kwargs=%s",
  4.                       func.__name__, args, kwargs)
  5.         return func(*args, **kwargs)
  6.     return wrapped

That’s pretty cool for starters, but let’s say we want some calls to stand out in the logging output. Perhaps there are functions that we are more interested in than the rest. In other words, we’d like to adjust the priority of log messages that are generated by @trace:

  1. @trace(level=logging.INFO)
  2. def important_func():
  3.     pass

This seemingly small change is actually mandating massive conceptual leap in what our decorator really does. It becomes apparent when we de-sugar the @decorator syntax and look at the plumbing underneath:

  1. important_func = trace(level=logging.INFO)(important_func)

Introduction of parameters requires adding a new level of indirection, because it’s the return value of trace(level=logging.INFO) that does the actual decorating (i.e. transforming given function into another). This might not be obvious at first glance and admittedly, a notion of function that returns a function which takes some other function in order to output a final function might be – ahem – slightly confusing ;-)

But wait! There is just one more thing… When we added the level argument, we not necessarily wanted to lose the ability to invoke @trace without it. Yes, it is still possible – but the syntax is rather awkward:

  1. @trace()
  2. def some_function(*args):
  3.     pass

That’s expected – trace only returns the actual decorator now – but at least slightly annoying. Can we get our pretty syntax back while maintaining the added flexibility of specifying custom arguments? Better yet: can we make @trace, @trace() and @trace(level) all work at the same time?…

Looks like tough call, but fortunately the answer is positive. Before we delve into details, though, let’s step back and try to somewhat improve the way we are writing our decorators.

Tags: , , , ,
Author: Xion, posted under Programming » 2 comments

Synchronization Through Memcache

2011-12-10 18:11

In web and server-side development, a memcache is a remote service that keeps transient data in temporary, in-memory store and allows for fast access. It is usually based on keys which identify values being stored and retrieved. Due to storing technique – RAM rather than actual disks – it offers great speed (often less than few milliseconds per operation) while introducing a possibility for values to be evicted (deleted) if memcache runs out of space. Should that happen, oldest values are usually disposed of first.

This functionality makes memcache a good secondary storage that complements the usual persistent database, increasing the efficiency of the system as a whole. The usual scenario is to poll memcache first, and resort to querying the database only if the result cannot be found in cache. Once the query is made, its results are memcached for some reasonable amount time (usually called TTL: time to live), depending on allowed trade-offs between speed and being up-to-date with our results.

While making applications more responsive is the primary use case for memcache, it turns out that we can also utilize it for something completely different. That’s because memcache implementations offer something more besides the obvious get/set commands. They also have operations which make it possible to use memcache as synchronization facility.

Klasy bardziej meta

2011-11-08 21:57

W językach ze skrzywieniem obiektowym klas używa się często i gęsto. Nieco inaczej jest z innym, o wiele mniej znanym pojęciem: metaklasami. Przedrostek meta- sugeruje tu od razu nieco wyższy poziom abstrakcji, co jest generalnie słusznym podejrzeniem. Dokładne znaczenie kryjące się za tym terminem w pewnym stopniu zależy od języka programowania, lecz w każdym przypadku chodzi o narzędzie związane z manipulowaniem samymi klasami. Zupełnie intuicyjnie jest to więc “jeden poziom meta więcej” :)
Jako nieco bardziej zaawansowana funkcjonalność, metaklas nie wykorzystuje się codziennie. Tym bardziej jednak warto wiedzieć przynajmniej z grubsza, jak działają, aby poprawnie rozpoznawać sytuacje, w których są one użyteczne. I dlatego właśnie dzisiaj przyjrzymy się metaklasom w trzech wariantach, specyficznych dla popularnych języków programowania.

Pierwszy z nich dotyczy systemów refleksji, czyli przydatnego mechanizmu językowego, pozwalającego programowi na wgląd w swoją wewnętrzną strukturę. W językach obiektowych oznacza to przede wszystkim możliwość posługiwania się klasami na bardziej dynamicznym poziomie. Są one wtedy reprezentowane przez obiekty, i właśnie te reprezentacje – używane poprzez moduły refleksji – nazywa się czasem metaklasami.
W wielu językach wyglądają one podobnie. Java ma na przykład klasę java.lang.Class, zaś C# – System.Type. Zyskując dostęp do instancji tychże klas (np. poprzez Class.forName albo Type.GetType) otrzymujemy możliwość wykonywania operacji na klasach, które one reprezentują. I tak możliwe jest chociażby tworzenie ich obiektów, wywoływanie metod, dostęp do pól. Dzięki temu możemy na przykład w (miarę) łatwy sposób zaimplementować proste rozwiązania wspierające pluginy, tj. dynamicznie ładowane wtyczki do naszych aplikacji.

Drugie znaczenie pojęcia metaklasy opisuje referencje do klas. Ideą jest tu traktowanie klas jako wartości pierwszego rodzaju (first-class value), które można przypisywać do zmiennych i w uogólniony sposób przekazywać między różnymi miejscami w kodzie. Specjalne zmienne, do których możemy “przypisywać” klasy są w co najmniej jednym języku nazywane właśnie metaklasami.
Przydatność tego typu rozwiązania zależy głównie od tego, jak wielkimi jesteśmy fanami wzorców typu fabryka abstrakcyjna :) Być może podstawową funkcjonalnością takich metaklas jest bowiem abstrakcja procesu tworzenia (lub ogólniej: pozyskiwania z zewnątrz) nowych obiektów. Pozostałe przypadki użycia metaklas są pokrywane zwykle przez szablony (C++), typy generyczne (C#, Java, itp.) lub podobne mechanizmy tworzenia kodu, który w pewien określony sposób jest niezależny od dokładnego typu obiektów, którymi operuje.

Czas wreszcie na trzeci wariant metaklas. Jest on zdecydowanie najciekawszy, ale też najbardziej skomplikowany i w pewien sposób wysublimowany – mimo swojej niewątpliwej użyteczności. Mam tutaj na myśli metaklasy w Pythonie.

Tags: , , , , ,
Author: Xion, posted under Programming » 1 comment

Proste haszowanie obiektów

2011-10-15 19:37

W językach wspierających obiektowość zwykle mamy do czynienia z uniwersalną klasą bazową (Object), od której wszystkie inne muszą dziedziczyć. Składniki tej klasy są więc wspólne dla wszystkich obiektów. Czasami ma to negatywne skutki (vide wait i notify w Javie), ale zazwyczaj jest przydatne, bo wspólne składniki – takie jak toString – są często niezwykle użyteczne.
Istnieje jednak pewna metoda bazowa obiektów, której przeznaczenie nie musi być od razu oczywiste. Nazywa się ona dość podobnie w różnych językach: GetHashCode w C#, hashCode w Javie, zaś w Pythonie jest to po prostu __hash__. Nietrudno się więc domyślić, że ma ona coś wspólnego z hashem obiektu :) O co jednak dokładnie chodzi?

Hash to kompaktowa reprezentacja pewnej porcji danych, uzyskana za pomocą określonego algorytmu. Takim algorytmem może być na przykład MD5, SHA1, SHA256 i inne. Podstawowym wymaganiem, jakie stawia się takim funkcjom, jest determinizm: dla identycznych danych powinny one zwracać dokładnie te same wyniki.
Do czego jednak przydaje się możliwość haszowania< dowolnych obiektów? Otóż pozwala to na tworzenie kontenerów haszujących, takich jak zbiory i mapy. W Javie na przykład chodzi tu o pojemniki HashSet i HashMap, będące jednymi z możliwych implementacji ogólnych interfejsów Set i Map. Takie kontenery używają hashy jako podstawy swojego działania, zakładając, że ich porównywanie jest szybsze niż branie pod uwagę całych obiektów. Dopiero równość ich hashy pociąga za sobą konieczność porównania samych obiektów.

Być może nasuwa się tu od razu słuszny wniosek, że hashe dla obiektów potrzebne są wobec tego jedynie wtedy, gdy implementujemy własny sposób ich porównywania. (Opisywałem kiedyś, jak to się robi w języku C#). Często powinniśmy wtedy zapewnić taką implementację ekwiwalentu metody hashCode, która będzie spójna ze sposobem porównywania. Z grubsza chodzi o to, aby na hash wpływały pola, które bierzemy pod uwagę w metodzie equals/Equals/__eq__ – i tylko one.

W jaki sposób miałyby jednak to robić? No cóż, w teorii możemy zaprząc do pracy wymienione wyżej algorytmy i potraktować nimi połączone wartości pól obiektu (albo po prostu kawałek pamięci, w którym on rezyduje). W praktyce to bardzo kiepskie rozwiązanie (zwłaszcza wydajnościowo), bowiem wspomniane funkcje haszujące niezupełnie do tego służą. Istnieje bowiem różnica między kryptograficzną funkcją haszującą a zwykłą: ta pierwsza ma na celu przede wszystkim uniemożliwienie odtworzenia oryginalnych danych, jeśli znany jest tylko ich hash. W przypadku funkcji używanych wraz z pojemnikami haszującymi bardziej interesuje nas jednorodność, co (w uproszczeniu) oznacza, że hash obiektu powinien być wrażliwy na wartości poszczególnych pól tego obiektu. Z tego też powodu poniższe rozwiązanie:

  1. @Override
  2. public int hashCode() {
  3.     return 42;
  4. }

jest do niczego, mimo że świetnie spełnia teoretyczne wymaganie, aby dwa równe obiekty miały równe hashe.

Dostępna jest oczywiście wyrafinowana wiedza na temat konstruowania dobrych (a nawet doskonałych) funkcji haszujących, ale dokładnie rachunki prawdopodobieństwa kolizji nieczęsto nas interesują – zwłaszcza, jeśli właściwie nie wiemy, w jakich pojemnikach i wśród jakich innych obiektów skończą te nasze. Na szczęście mamy też prostsze warianty. Wśród nich interesująco wygląda na przykład sposób pokazany w znanej książce Effective Java, który wygląda mniej więcej w ten sposób:

  1. Zaczynamy od dowolnej liczby dodatniej.
  2. Dla każdego znaczącego pola w obiekcie:
    1. bierzemy jego 32-bitową reprezentację (w razie potrzeby używając operacji bitowej xor dla większych pól)
    2. dodajemy ją do wyniku, uprzednio pomnożonego przez małą liczbę pierwszą

Zastosowanie go np. do prostej klasy punktu 3D wyglądałoby na przykład tak:

  1. public class Point3D {
  2.     private float x, y, z;
  3.     // ...
  4.     @Override public int hashCode() {
  5.         int res = 23;
  6.         res = 31 * res + Float.floatToIntBits(x);
  7.         res = 31 * res + Float.floatToIntBits(y);
  8.         res = 31 * res + Float.floatToIntBits(z);
  9.         return res;
  10.     }
  11. }

Wybór 23 jest raczej arbitralny, natomiast 31 ma tę zaletę, że mnożenie przez nią liczby x jest równoważne przesunięciu bitowemu i odejmowaniu, tj. (x << 5) - x. Analogicznie jest zresztą dla innych liczb o jeden mniejszych od potęg dwójki.

Tags: , , ,
Author: Xion, posted under Programming » Comments Off on Proste haszowanie obiektów

Trzy rodzaje metod w Pythonie

2011-10-03 23:05

Obiekty mają metody. Tak, w tym stwierdzeniu nie należy doszukiwać głębokiego sensu – jest ono po prostu prawdziwe :) Gdy mówimy o metodach obiektów czy też klas, zwykle mamy jednak na myśli tylko jeden ich rodzaj: metody instancyjne. W wielu językach programowania nie jest to aczkolwiek ich jedyny rodzaj – z takim przypadkiem mamy do czynienia chociażby w Pythonie.

Jak zawsze metody instancyjne są domyślnym typem, który tutaj jest dodatkowo zaznaczony obecnością specjalnego parametru – self – występującego zawsze jako pierwszy argument. To odpowiednik this z języków C++, C# czy Java i reprezentuje instancję obiektu, na rzecz której wywoływana jest metoda:

  1. class Counter(object):
  2.     def __init__(self, value = 0):
  3.         self._value = value
  4.     def increment(self, by = 1):
  5.         self._value += by

Fakt, że musi być on jawnie przekazany, wynika z zasad tworzenia zmiennych w Pythonie. Nie muszą być one jawnie deklarowane. Dlatego też odwołanie do pola obiektu jest zawsze kwalifikowane, gdyż przypisanie do _value zamiast self._value stworzyłoby po prostu zmienną lokalną.

Istnieją jednak takie metody, które nie operują na konkretnej instancji klasy. Typowo nazywa się je statycznymi. W Pythonie nie posiadają one parametru self, lecz są opatrzone dekoratorem @staticmethod:

  1. @staticmethod
  2. def format_string():
  3.     return "%d"

Statyczną metodę można wywołać zarówno przy pomocy nazwy klasy (Counter.format_string()), jak i jej obiektu (Counter().format_string()), ale w obu przypadkach rezultat będzie ten sam. Technicznie jest to bowiem zwyczajna funkcja umieszczona po prostu w zasięgu klasy zamiast zasięgu globalnego.

Mamy wreszcie trzeci typ, mieszczący się w pewnym sensie pomiędzy dwoma opisanymi powyżej. Nie wydaje mi się jednak, żeby występował on w żadnym innym, popularnym języku. Chodzi o metody klasowe (class methods). Nazywają się tak, bo są wywoływane na rzecz całej klasy (a nie jakiejś jej instancji) i przyjmują ową klasę jako swój pierwszy parametr. (Argument ten jest często nazywany cls, ale jest to o wiele słabsza konwencja niż ta dotycząca self).
W celu odróżnienia od innych rodzajów, metody klasowe oznaczone są dekoratorem @classmethod:

  1. @classmethod
  2. def from_other(cls, counter):
  3.     return cls(counter._value)

Podobnie jak metody statyczne, można je wywoływać na dwa sposoby – przy pomocy klasy lub obiektu – ale w obu przypadkach do cls trafi wyłącznie klasa. Tutaj akurat będzie to Counter, lecz w ogólności może to być także klasa pochodna:

  1. class BoundedCounter(Counter):
  2.     MAX = 100
  3.  
  4.     def __init__(self, value = 0):
  5.         if value > self.MAX:
  6.             raise ValueError, "Initial value cannot exceed maximum"
  7.         super(BoundedCounter, self).__init__(value)
  8.  
  9.     def increment(self, by = 1):
  10.         super(BoundedCounter, self).increment(by)
  11.         self._value = min(self._value, self.MAX)
  12.  
  13.     @classmethod
  14.     def from_other(cls, counter):
  15.         value = min(counter._value, cls.MAX)
  16.         return cls(value)

Powyższy kod – będący przykładem dodatkowego sposobu inicjalizacji obiektu – to dość typowy przypadek użycia metod klasowych. Korzystanie z nich wymaga aczkolwiek nieco wprawy w operowaniu pojęciami instancji klasy i samej klasy oraz ich poprawnego rozróżniania.
W gruncie rzeczy nie jest to jednak nic trudnego.

Tags: , , ,
Author: Xion, posted under Programming » 4 comments

pyduck – biblioteka do interfejsów w Pythonie

2011-09-26 22:16

Czas pochwalić się swoim nowym dziełem. Nie jest ono bardzo imponujące ani specjalnie duże. Mam jednak nadzieję, że będzie ono przydatne dla tego (wąskiego) grona odbiorców, do którego jest skierowane.

Mam tu na myśli niewielką biblioteką do Pythona, która ma na celu poprawienie użyteczności jednej z głównych, ideowych cech języka – tak zwanego typowania kaczkowego (duck typing). Geneza tego terminu jest oczywiście wielce intrygująca, ale założenie jest proste. Zamiast czynić obietnice i jawnie deklarować implementowane interfejsy, obiekty w Pythonie “po prostu są” i zwykle próbują być od razu używane do założonych celów. Jeśli okażą się niekompatybilne (np. nie posiadają żądanej metody), wtedy oczywiście rzucany jest wyjątek. Pythonowska praktyka polega więc na przechodzeniu do rzeczy bez zbędnych ceregieli i obsłudze ewentualnych błędów.

Ma to rzecz jasna swoje zalety, ma też wady, a czasami może również rodzić problemy, jeśli błąd spowodowany niekompatybilnością obiektu ujawni się za późno. Z drugiej strony brak konieczności jawnego specyfikowania implementowanych interfejsów to spora zaleta. Najlepiej więc byłoby jakoś połączyć te dwa światy i umożliwić wcześniejsze sprawdzenie możliwości obiektu…

Jak można się pewnie domyślić, to właśnie próbuje umożliwić mój framework, noszący wdzięczną nazwę pyduck. Dodaje on do Pythona mechanizm interfejsów bardzo podobny do tego, który obecny jest w języku Go. Najważniejszą jego cechą jest właśnie fakt, że w konkretnych typach interfejsy są implementowane niejako automatycznie – wystarczy, że mają one odpowiednie metody. Samo sprawdzenie, czy obiekt implementuje dany interfejs polega zaś na faktycznym zaglądnięciu w listę jego metod, a nie weryfikacji jakichś jawnych deklaracji.

Inaczej mówiąc, nie czynimy tutaj żadnych obietnic odnośnie obiektu, ale wciąż mamy możliwość kontroli, czy nasze wymagania są spełnione. Najlepiej ilustruje to oczywiście konkretny przykład:

  1. from pyduck import Interface, expects
  2.  
  3. class Drawable(Interface):
  4.     def get_bounds(self): pass
  5.     def draw(self, canvas): pass
  6.  
  7. class Canvas(object):
  8.     @expects(Drawable)
  9.     def draw_object(self, obj):
  10.         bounds = obj.get_bounds()
  11.         self.set_clipping_bounds(bounds)
  12.         obj.draw(self)

Zaznaczamy w nim, że metoda Canvas.draw_object spodziewa się obiektu zgodnego z interfejsem Drawable. Jest on zdefiniowany wyżej jako posiadający metody get_bounds i draw. Sprawdzenie, czy rzeczywisty argument funkcji spełnia nasze wymogi, zostanie wykonane przez dekorator @expects. Zweryfikuje on obecność i sygnatury metod wspomnianych metod.
Dzięki temu będziemy mogli być pewni, że mamy do czynienia z obiektem, który rzeczywiście potrafi się narysować. Jego konkretna klasa nie będzie musiała natomiast nic wiedzieć na temat interfejsu Drawable ani jawnie deklarować jego wykorzystania.

Po więcej informacji zapraszam oczywiście na stronę projektu na GitHubie. Ewentualnie można też od razu zainstalować paczkę, np. poprzez easy_install:

  1. $ sudo easy_install pyduck

A ponieważ wszystko open source jest zawsze wersją rozwojową, nie muszę chyba wspominać, że z chęcią witam pull requesty z usprawnieniami i poprawkami :>

Tags: , , , ,
Author: Xion, posted under Programming » 1 comment

Eksperyment z losowymi ciągami

2011-09-06 20:51

Zdarzyło się dzisiaj, że musiałem zaimplementować rozwiązanie wyjątkowo klasycznego problemu. Siląc się matematyczny formalizm, mógłbym go zdefiniować następująco:

  • Mamy dany zbiór A=\{a_1, \ldots, a_n\} dowolnych elementów a_i oraz liczbę naturalną k \in N.
  • Szukamy ciągu S=<s_1 , \ldots, s_k> k elementów s_i \in A.

Krótko mówiąc, chodzi o trywialną wariację z powtórzeniami. Ambitne to zadanie jest w sumie nawet mniej skomplikowane niż częste ćwiczenie dla początkujących pt. losowanie Lotto, więc po chwili wyprodukowałem coś podobnego do kodu poniżej:

  1. import random
  2.  
  3. def k_permutation(elems, k=None):
  4.     k = k or len(elems)
  5.     res = []
  6.     while k > len(res):
  7.         next = elems[random.randrange(0, len(elems)]
  8.         res.append(next)
  9.     return res

I na tym pewnie historia by się zakończyła, gdybym nie przypomniał sobie, że Python domyślnie potrafi obsługiwać naprawdę duże liczby. (Może nie aż tak duże jak te tutaj, ale jednak dość spore ;]). Obserwacja ta daje się bowiem połączyć z inną: taką, iż ciąg elementów z pewnego zbioru jest równoważny liczbie w systemie o podstawie równej mocy tego zbioru. Taka liczba jest oczywiście bardzo duża w prawie każdym praktycznym przypadku, lecz to nie umniejsza w niczym prawdziwości stwierdzenia. Jest ono zresztą z powodzeniem wykorzystywane w systemach kryptograficznych w rodzaju RSA.

Postanowiłem więc i ja z niego skorzystać. Przynajmniej teoretycznie fakt ten powinien dawać lepsze rezultaty, zamieniając k losowań na tylko jedno – tak jak poniżej:

  1. def k_permutations_bignum(elems, k=None):
  2.     k = k or len(elems)
  3.     max_seq_num = len(elems) ** k
  4.     seq_num = random.randrange(0, max_seq_num) # (zob. 3. komentarz)
  5.     res = []
  6.     while seq_num > 0:
  7.         seq_num, next = divmod(seq_num, len(elems))
  8.         res.append(elems[next])
  9.     return res

Doświadczenie z kolei uczyłoby, że bezpośrednie aplikowanie dziwnych matematycznych koncepcji do programowania rzadko miewa dobre skutki ;) Jak więc jest w tym przypadku?…

Tags: , , , ,
Author: Xion, posted under Math, Programming » 4 comments
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.