SBQL AST Visualizer

Napisałem na szybko wizualizator do drzew składniowych zapytań SBQL: tutaj! (do odpalenia wymagany pydot) W środku jest kilka obrazków z drzewkami.
Ostatecznie gramatyka wyszła mi taka:


Rule 1 query -> LPAREN query RPAREN
Rule 2 query -> LITERAL
Rule 3 query -> NUMBERLITERAL
Rule 4 query -> STRINGLITERAL
Rule 5 query -> UNARYOP query
Rule 6 query -> query SIMPLEBINARYOP query
Rule 7 query -> query DOT query
Rule 8 query -> query COMMA query
Rule 9 query -> query AS query
Rule 10 query -> query JOIN query
Rule 11 query -> query WHERE query
Rule 12 query -> query AND query
Rule 13 query -> query OR query

z kolejnością wiąząń:
precedence = (
('left', 'WHERE', 'JOIN') ,
('left', 'AND', 'OR'),
('left', 'SIMPLEBINARYOP'),
('left', 'AS', 'DOT')
)

na końcu pliku są takie przykłady:
data = {
"01simple": "(2+2 < 4) and 1",
"02projection" : '(Employee where salary < 200).(name, surname)',
"03more" :'(Employee where surname = "Kowalski" and salary < 200).name',
"04MappedJoin" : 'Employee.worksIn.Dept',
"05forjoin" : '(Employee where surname = "Kowalski" and worksIn.Departmet.isLocatedIn.Location.name = "Lodz").(surname, birthdate)',
"06join" : '(Employee as e join e.worksIn.Department as d join d.isLocatedIn.Location as l).(e.surname, l.name)',
"07join2" : '(Employee where surname = "Kowalski" and worksIn.Department.name = "Production").(surname, birthdate)'
}

Citations for today

“Multicore architectures will (finally) bring parallel
computing into the mainstream. To effectively
exploit them, legions of programmers must
emphasize concurrency.”

"Nontrivial software written with threads,
semaphores, and mutexes are
incomprehensible to humans and cannot
and should not be trusted!"

Edward A. Lee

prezentacja - świetny przykład z wzorcem observera



thinking, learning, thinking... argh

Query Language in Java

Dzisiaj nie będzie nic własnoręcznie stworzonego - zamiast tego mała definicja:

Domain Specific Language
The basic idea of a domain specific language (DSL) is a computer language that's targeted to a particular kind of problem, rather than a general purpose language that's aimed at any kind of software problem. blog:DSL

Pewnym uszczegółowieniem tej koncepcji jest pomysł aby w języku konkretnego przeznaczenia (np. języku programowania) stworzyć wrażenie innego języka (wspominałem juz o LINQ?). Bardzo ciekawe jak te mainstreamowe języki ewoluują. Ostatnio natknąłem się na querydsl (warto jest to póki co najlepszy projekt z tym pomysłem). Niewątpliwie i tak tutaj najbardziej narozrabiał Microsoft ze swoim rozszerzeniem LINQ, ale projekty próbujące tego samego w JAVA rosną ostatnio jak grzyby po deszczu; a ja mam wrażenie jakby powstał taki lepszy, mocno typowany JDBC - nice.

LINQ Decomposed

LINQ (Language Integrated Query), to bardzo przydatne rozszerzenie języków z platformy .NET o "generyczne operacje na kolekcjach". Chodzi mniej więcej o to, że wprowadzono do języka programowania elementy języka zapytań (formuły LINQ). Zamiast jes skrupulatnie opisywać odsyłam w tym momencie do msdn:linq.

Wygląda całkiem fajnie - proste operacja agregowania, selekcji i projekcji w samym języku i to całkiem elegancko, szybko i jeszcze type-safe - no tak przecież powinno być już dawno.
Na tym niespodzianki się jednak nie kończą, okazuje się bowiem, że jest to również pewien rodzaj vendor-dependent middleware! Formuła LINQ może zostać przetłumaczona na zapytanie do bazy danych. Jak to możliwe? Scenariusz mamy podzielony na dwie części:

Cz.1
Sama formuła LINQ w czasie kompilacji jest tłumaczona na natywne zapytanie, czyli zapytanie zadane obiektem (coś na kształt db4o:tutorial). W trakcie kompilacji formuły zostaną przepisane mniej więcej w ten sposób.

    Dim formula_query = From emp In db_context.Employees _
                            Where emp.Country = "USA" _
                            Select emp.FirstName, emp.LastName

    Dim native_query = db_context.Employees. _
                            Where(Function(empl) empl.Country = "USA"). _
                            Select(Function(empl) New With {.FirstName = empl.FirstName, .LastName = empl.LastName})

Obiektem zapytania jest w przypadku pracy z samymi kolekcjami jest IEnumerable a w przypadku źródła danych jej specjalizacji IQueryable (a właściwie specjalizacji IQueryable, dostarczonej przez dostawce sterownika)

Cz. 2
Zapytanie jest realizowane leniwie czyli dopiero wtedy gdy poprosimy obiekt zapytania o enumerator dzieje się cała akcja, która opiera się na mechanizmie przepisywania drzew składniowych. W trakcie wykonania silnik dostawcy dostaje AST, który sobie jakoś tam analizuje i to co może zrobić to np. wygenerować zapytanie sql w postaci stringa i posłać go do bazy, odczytać a potem utworzyć kolekcję tych obiektów i zwrócić programiście (no ale oczywiście może o wiele wiele więcej). Napisałem prosty programik na podstawe tego blog:msdn:linq (copy-paste programming), który zamiast robić cokolwiek, to po prostu wypisuje info o każdym węźle. Troche bardziej user-friendly wyjaśnienie jest tutaj codeguru.

var q = from el in context.Data where el +1 > 5 select el;

Call Data.Where(el => ((el + 1) > 5))
Constant Data
Quote el => ((el + 1) > 5)
Lambda el => ((el + 1) > 5)
GreaterThan ((el + 1) > 5)
Add (el + 1)
Parameter el
Constant 1
Constant 5

Pare przykładów.

Dim q = (From order In db_context.Orders Join detail In db_context.Order_Details _
  On detail.OrderID Equals order.OrderID _
  Select order.ShipName, detail.Quantity).Take(10)

przepisane jest na zapytanie:

SELECT TOP (10) [t0].[ShipName], [t1].[Quantity]
FROM [dbo].[Orders] AS [t0]
INNER JOIN [dbo].[Order Details] AS [t1] ON [t0].[OrderID] = [t1].[OrderID]

późne wiązanie

Dim q = From el In db_context.Employees _
             Select el.FirstName, el.LastName, el.Country, el.City
q = From el In q Where el.Country = "USA"
q = From el In q Where el.City = "Seattle"

przepisane jest na zapytanie:

SELECT [t0].[FirstName], [t0].[LastName], [t0].[Country], [t0].[City]
FROM [dbo].[Employees] AS [t0]
WHERE ([t0].[City] = @p0) AND ([t0].[Country] = @p1)

Warto zauważyć, że w przypadku pracy z kolekcjami silnik jest już w samym standardzie LINQ i zachowuje się dosyć inteligentnie wykorzystując yield. Możemy sobie zdefiniować mniej lub bardziej skomplikowaną "transformacje" (tak to nazwijmy) kolekcji w postaci obiektu, a wykonanie jej nie będzie tworzyło stosów pośrednich podczas obróbki, co znaczy tyle, żedla każdego elementu wykona wszystkie kroki transformacji od początku do końca (można powiedzieć, że tworzymy wrażenie składania funkcji i foldowania.

Jeszcze na koniec pare wniosków i faktów:

• Wygląda to wszystko całkiem fajnie, bo dostajemy bardzo użyteczne rozszerzenie języka programowania. Osobiście bardzo często to wykorzystuje i co ciekawsze nie jako middleware, ale właśnie do pracy z kolekcjami i wcześniej gdy naiwnie pisałem jakieś tam zapętlające się pętle tak teraz dostaje bardzo czytelny i efektywny kod.
• LINQ nie jest córą Microsoftu, tylko urodziła się jako koncepcja akademicka, która przechodzi tez do innych języków ruby:rinq, php, js:jslinq, i nawet rozaważa się aby do JAVA wstawić jakieś LINQ, zwłaszcza gdy mają zostać dodane domknięcia (closures) w JAVA 1.7
  
• Zarzutem dla LINQ jest kiepska wydajność. Jako, że zapytanie jest generowanie w czasie wykonania w istocie robi to pewien narzut, który z powodzeniem można było zrobić w czasie projektowania, no ale ze swego doświadczenia mogę stwierdzić, że dopóki nie będzie się uzywało formuły linq w pętli nie stanowi to aż tak dużego narzutu
• Koncepcja linq doskonale nadaje się do rozszerzenia jej do PLINQ (Parallel LINQ) o tym będzie później
• Microsoft zrobił coś co robił już bardzo często, czyli stworzył naprawdę ładny kawałek oprogramowania, a potem zaprezentował jego jeden mały fragment. Warto zauważyć , że przecież w czasie wykonania dostajemy AST pewnych struktur języka, możemy je analizować i jeszcze dodatkowo mieć wypływ na to co wypluwają - no to przecież nie trywialny mechanizm, a jak wiemy może być całkiem użyteczny również.
  

Home cooking: metaprogramming a'la Python

Metaprogramowanie to najprościej rzecz ujmując pisanie programów, które piszą programy. Lekki wstęp można znaleźć tutaj wikipedia:Metaprogramming, a całą koncepcję najłatwiej wyjaśnić na przykładzie LISPA, w którym program piszę się bezpośrednio w drzewie składniowym a kod programu jest listą. Zatem przy niewielkiej zmianie w syntaktyce można stworzyć konstrukcje (tutaj: makro), które w momencie uruchomienia generuje inną listę i ją wywołuję jako program.

No dobra, ale po co to wszystko? Okazuje się, że to bardzo potężny mechanizm, a Paul Graham twierdzi, że jego programy w LISP były złożone w około 40% z makr, co pozwalało mu tworzyć web-dwa-zero projekt (który został ostatecznie wykupiony przez Yahoo) znacznie szybciej niż jego ówczesna konkurencja.

No wielkim zaskoczeniem nie będzie, że metaprogramowanie zostało dorzucone również do Pythona, a konstrukcja, która na to pozwala to Metaclasses. Na sam początek:

Metaclasses are deeper magic than 99% of users should ever worry about. If you wonder whether you need them, you don't (the people who actually need them know with certainty that they need them, and don't need an explanation about why). -- Tim Peters

A więc motywacje już mamy (!)

Na początek problem: Stworzyć interpreter zapytań podobnych do tych tutaj sbql:examples. Dodatkowo niech program nie będzie dłuższy niż cztery ekrany. Oczywiście podobieństwo naszych zapytań do zapytań języka SBQL jest mocno naciągane, niemniej jednak przyjrzyjmy się:

class Osoba():
__metaclass__ = pql_memorystore

imie     = Attribute(str, "[*..2]")
nazwisko = Attribute(type = str, card = "[1..1]")
wiek     = Attribute(int)

def __init__(self, imie, nazwisko):
self.imie = imie
self.nazwisko = nazwisko

w drugiej linijce określamy tylko metaklasę dla naszej, klasy co sprawia, że nasza żmudnie tworzona klasa Osoba po zakończeniu jej definicji staje sie już zupełnie czymś innym. A w naszym przypadku będzie listą. Czyli mamy klasę, która jest jednocześnie listą i dodatkowo każda nowa instancja tej klasy odkłada się do siebie... weird kind of magic
hmmm sprawdźmy:

Możemy zatem tworzyć obiekty:

o1 = Osoba(imie = "Adam", nazwisko = "Janskowski")
o2 = Osoba(imie = "Janek", nazwisko = "Wlodarczyk")
Osoba("Sigmun", "Freud")
Osoba(imie = "Adam", nazwisko = "Malysz")
Osoba("Tolek", "Skoczylas")

i wykonywać na nich coś w rodzaju zapytań, które operują na instancjach własnych klas:

Osoba
Osoba.imie
[o for o in Osoba if o.imie == ['Adam']]
pql_list([o for o in Osoba if o.imie == ['Adam']]).Nazwisko

Pewnie podobieństwo do SBQL można by jeszcze trochę podciągnąć w ramach samego Pythona przeciążając operatory; znacznie więcej dałoby rade pewnie podciągnąć pewnie evalem, ale przecież to nie o to chodziło.

Program jest tutaj. Napisałem go dawno temu (w czasach gdy jeszcze pterodaktyle latały po niebie) i nigdy nie skończyłem ale w sumie mniej więcej działa, a w pliku jest więcej przykładów. Jest tam nawet wstęp do stworzenia kontroli typów i kardynalności atrybutów.