[nem-pl] in_tail_position

[Lukasz Kaiser]

Hej.

Dzieki za wyjasnienie ITP, juz rozumiem. To teraz ja napisze dwie 
brednie o tail callach. Brednie sa funkcjonalnie nastawione i pewnie
lepiej o nich myslec jako o mozliwych optymalizujacych makrach niz
ogolnych optymalizacjach. To jest pierwsza wersja alfa bredni i prosze pytac
i napisac co myslicie. Bede sie staral pisac jasno, ale nie koniecznie
skladniowo poprawnie.

Brednia 1:

Zalozmy, ze mamy funkcje taka:
f(x) = match x with
  | p1 => cons1
  | ...
  | pK => consK
  | p(K+1) => h ( f(g_1(x)) ) lub { z <- g_1(x); y <- f(z); h(y) ; }
  | ...
  | pN => h ( f(g_L(x)) ) czyli ( z <- g_L(x); y <- f(z); h(y) ; }

Jesli patrzec na ta funkcje zupelnie funkcjonalnie, tzn. zakladac,
ze zarowno h jak i g nie maja efektow ubocznych, to taka funkcja
liczy h ( h ( ... h ( consM )  ... ), przy czym co to jest M i ile 
jest tych h to zalezy od tych g.
Prosty przyklad f(x) = | 0 => 1 | n => 2*f(n-1) ; h(x)=2x; g(x) = x-1.

Taka funkcje da sie policzyc "od dolu" ogonowo w nastepujacy sposob:
def f (x) {
  def f_rec ( acc1, ..., accK, x ) { match x with
    | p1 => acc1
    | ...
    | pK => accK
    | p(K+1) => f_rec ( h(acc1), ..., h(accK), g_1(x) )
    | ...
    | pN => f_rec ( h(acc1), ..., h(accK), g_L(x) )
  } ;
  f_rec ( cons1, ..., consK, x ) ;
}
Przyklad sie przepisuje:
f_rec = | ( _, 0 ) => 1 | ( k, n ) => f_rec ( 2k, n-1 ) in f_rec (1,x);

Takie obliczenie robi troche wiecej, bo liczy w zasadzie dla wszystkich
wariantow, wiec pewnie nie oplaca sie dla K > 3. Problem z nim polega na
tym, ze ma inna kolejnosc obliczen niz wersja oryginalna. W wersji 
oryginalnej na poczatku licza sie same g, potem h, tutaj liczy sie g, h, g, h
itd., co bedzie problemem gdy te funkcje nie sa czysto funkcjonalne.
Poniewaz wykrycie jakie funkcje sa jest trudne, to mysle ze to nie ma szans
jako ogolna optymalizacja, ale moze warto zrobic makro, ktore na zyczenie
bedzie robic cos takiego zdejmujac z czlowieka piszacego funkcjonalnie
koniecznosc dopisywania akumulatorow recznie, dajac mozliwosc po prostu
napisania [accumulable] f (x) ... . Co o tym myslicie ?

Mozliwe zastosowanie: 
latwiejsze pisanie akumulatorow, makro zamiast recznej edycji.

Brednia 2:

Nazwijmy to rekrsja konstruktorowa, tzn. pytanie jest takie jak sie tlumacza
wywolania konstruktorow ? Jak mamy:
f = | 0 => Cons ( B, B ) | x => Cons ( f (x-1), B )
to pewnie ta druga galaz sie przeklada na
x => { y <- f(x-1) ; z <- Cons (x, 1) ; Cons ( y, z ) }.

Jako ze konstruktor w ogolnosci moze robic rozne dziwne rzeczy to jest
to konieczne w pewnym sensie, ale dla konstruktorow ktore sa funkcjonalne,
czyli nie maja skutkow ubocznych da sie zrobic lepiej, chociaz nie do konca 
latwo.

Po pierwsze trzeba zmienic typ, jesli bylo
variant foo = | Cons { a : foo ; b : foo ; } | B
to potrzeba
variant mut_foo = | ConsM { mutable a : foo ; mutable b : foo ; } | BM
i wtedy
f (x) {
  def f_ptr ( ptr, n ) { match n with
    | O => { ptr <- ConsM ( BM, BM ) } 
    | x => { def mutable nptr = NULL ; 
             ptr <- ConsM ( nptr, BM ) ; 
	     f_ptr ( nptr, x-1 ) }
  }
  { def mutable res = NULL ; f_ptr ( res, x ) ; unMutable ( res ) }
}

Nie wiem czy jest do konca jasne o co chodzi, po prostu zamiast wywolywac
konstruktor jako funkcje obiciazajac stos najpierw tworzymy strukture
i potem przekazujemy wskaznik. To zmienia kolejnosc wywolan o tyle, ze
teraz najpiew wywolywany jest konstruktor z jakims wskaznikiem a potem
dopiero ten wskaznik jest wypelniany wlasciwym obiektem przez f_ptr.
Mysle, ze to tez mogloby sie dac zaimplementowac jako dwa makra, jedno
na typach tworzace nowy typ, drugie na funkcji kontruktorowej. Co myslicie?

Mozliwe zastosowanie: 
Mozna wtedy zrobic zeby np. taka funkcja nie byla rekurencyjna:
insertTree ( n, t ) { match t with 
  | Leaf => Tree ( n, Leaf, Leaf )
  | Tree ( i, l, r ) => if (i < n) 
                          Tree ( i, l, insertTree ( n, r ) )
			else 
			  Tree ( i, insertTree ( n, l ), r )
  }
}

Napiszcie czy da sie z tego cos zrozumiec i prosze Kamil, napisz czy
przy obecnym stanie makr moge zaczac probowac implementowac brednie 1,
czy tez lepiej zebym jeszcze poczekal ?

- lk