[nem-pl] Re: Fwd: Nemerle

[Kamil Skalski]

On Thu, 16 Dec 2004 22:17:50 +0000, Marcin Grzeskowiak
<fnord at silesianet.pl> <fnord at silesianet.pl> wrote:
> Hej
> 
> przeczytania no i z tego co poklikałem w googlach to można też coś
> znaleźć o innych implementacjach do poczytania. No i zlokalizowałem
> MatchingCompiler.n ;-) więc jeszcze pooglądam jak jest to zrobione
> w obecnej wersji.

Tamten kod momentami może być niezrozumiały, ale być może uda się z
niego wynieść jakiś
pogląd na sprawę. Możesz też spojrzeć na ncc/temp/matching.n, to szkic
nowej implementacji, za którą zabrał się Paweł (coś wg tego opisanego
w jego pracy), ale już nie skończył.
Aktualnie to co robi matching jest trochę rozbudowanym najprostszym
rozwiązaniem. Z tego co wiem są optymalizacje (choć ograniczone) dla
przypadków matchingu na boolach, stringach i liczbach oraz gdy w
głowie wzorca jest któraś z opcji variantu:
match (x) {
  | A (parametry) =>
  | B (...)  =>
  | C =>
}

varianty mają specjalną metodę GetVariantCode (), która zwraca inta,
po którym można zrobić już switcha. Ta metoda jest efektywna kiedy
jest co najmniej kilka opcji, bo inaczej opłaca się po prostu
sprawdzić serią ifów jaki jest typ obiektu.
To co trzeba zrobić przede wszystkim w matchingu to
- opracować dość ogólny engine matchingu (wykorzystujący np. skoki,
których aktualnie nie mamy explicite w żadnym przejściu kompilatora),
tak żeby dało się łatwo dokonywać optymalizacji typu
match ((1,2,3)) {
  | (x,y,5) => ...
  | 
}
na
if (3 == 5) {
 def x = 1;
  def y = 2;
 ...
}
else { 
def z = 3; 
..
}
co oczywiście zmieni się w def z = 3;... (ale to już nieistotne)

Teraz robimy to dość beznadziejnie, czyli tworzony jest nowy obiekt
trójki, a potem są z niego wyciągane te trzy pola.

- to na czym skupiał się pod względem teoretycznym Paweł w pracy:
match (x) {
  A (5, u, 4, z) =>
  A (x, 6, 4, z) =>
  A (x, y, 4, z) =>
  A (5, y, u, z) =>
  B (.. ) =>
  ...
}

czyli wybór które pozycje opłaca się najpierw odczytać i zdecydować co
matchować. Trzeba oczywiście też spamiętywać co już się dowiedzieliśmy
i budować drzewo superpozycji, czy jak to się nazywało.

- efektywne foldowanie stałych wyrażeń z udziałem matchingu, teraz
często generujemy jakiś beznadziejny kod, typu
if (if (x == true) true else false; ) jump ...


> Też interesowałyby mnie optymalizacje w kompilatorze. Czy mógłbyś
> coś więcej napisać na temat "przejścia kompilatora upraszczającego
> drzewo programu" ? Czy masz na myśli jakieś konkretne optymalizacje
> które można tam zastosować ? Moje pojęcie o kompilatorach optymali-

Chodzi o drzewo CExpr, czyli to co jest pomiędzy typowaniem, a
generowaniem asemblera. To drzewo jest reprezentacją pośrednią, w
której wiadomo już dokładnie co i jak wywołujemy (czy to metoda
statyczna, pole, zmienna lokalna, gdzie zefiniowana, warunki, itd.).
Zanim z niego wygenerujemy asembler, można by je trochę
poprzekształcać, właśnie coś propagując, upraszczając, itd. Nie wiem
dokładnie jakie by tu można optymalizacje robić - pewnie trzebaby się
przyjrzeć postaci drzewa, które jest generowane w średnim przypadku i
wymyśleć (zastosować znane) metody przekształcania.
Wiąże się to dość mocno z kompilatorem matchingu, bo to głównie jego
output jest optymalizowalny (ale nie tylko, np. pętle). Na dzień
dzisiejszy większe może nawet znaczenie miałoby zoptymalizowanie
różnych pomocniczych rzeczy które generujemy, jak closures, funkcje
lokalne, itd. - idealnie trzebaby więc przepisać dużą część generacji
kodu (MatchingCompiler.n i CompileTypedTree.n, czystszym i bardziej
przemyślanym podejściem) i ew. dodanie przejścia optymalizującego
(OptimizeCostam.n ;))

> zujących ogranicza się w tej chwili do dość podstawowych technik
> w rodzaju propagacji kopii, redukcji mocy,  eliminacji zmiennych
> indukcyjnych itp. Plus trochę więcej o eliminowaniu wspólnych
> podwyrażeń, też trochę o SSA. Przy czym to wszystko raczej

Hehe, to wiesz wiecej niz ja, nie chodziłem nigdy na kurs z omawianymi
optymalizacjami, poza podstawami na Metodach Translacji. ;)

> w kontekście kompilatorów dla języków imperatywnych, nie wiem
> jak wygląda sytuacja dla języków funkcjonalnych i hybrydowych,
> czy trzeba modyfikować algorytmy. W tej chwili nie wiem nawet
> jakiej reprezentacji wewnętrznej używacie (poza tym że "drzewo
> programu" ;-) ). Jeżeli możesz coś tutaj podpowiedzieć to
> może by mi to trochę rozjaśniło :-) .

Spójrz sobie na CompiledTree.n - to drzewo ma już postać raczej
imperatywnego programu i wszystkie optymalizacje do nich sie
stosujące, powinny tutaj też działać. Trzeba je też zdecydowanie
rozszerzyć (i może uprościć) o skoki itd.

A może się zastanowić nad czymś bardziej odmiennym? Żeby drzewo i
filozofia CExpr była całkiem inna (a może żeby w ogóle go nie było i
wszystko działo się na Typedtree).

-- 
Kamil Skalski
http://nazgul.omega.pl