GCC a tail-call recursion

GCC so zapnutými optimalizáciami dokáže preložiť nasledujúci kód (ktorý nie je správne napísaná tail-call recursion) optimalizovane:

long fact(long x) {
    if (x <= 0)
        return 1;
 
    return x*fact(x-1);
}

Výsledok:

0000000000400494 <fact>:
  400494:	b8 01 00 00 00       	mov    $0x1,%eax
  400499:	48 85 ff             	test   %rdi,%rdi
  40049c:	7e 09                	jle    4004a7 <fact+0x13>
  40049e:	48 0f af c7          	imul   %rdi,%rax
  4004a2:	48 ff cf             	dec    %rdi
  4004a5:	eb f2                	jmp    400499 <fact+0x5>
  4004a7:	c3                   	retq   

Zdroj tohoto zázraku:

In addition to the standard tail recursion elimination, we handle the most trivial cases of making the call tail recursive by creating accumulators. For example the following function
int sum (int n)
{
  if (n > 0)
    return n + sum (n - 1);
  else
    return 0;
}


is transformed into

int sum (int n)
{
  int acc = 0;
 
  while (n > 0)
    acc += n--;
 
  return acc;
}

(http://gcc.gnu.org/viewcvs/trunk/gcc/tree-tailcall.c?revision=151935&view=markup)

Ukážka vývoja DSL v Lispe

V súvislosti s posledným zápisom som našiel ukážkové video vývoja DSL v Common Lispe, pre záujemcov to budem nejaký čas seedovať (125 MiB, 19 min.):

dsl_domain_specific_language_in_lisp.3735468.tpb.torrent

dsl-in-lisp-small.jpg

Ruby a DSL

Už je to nejaký čas čo sa cez Ruby prevalila móda Domain Specific Languages, až dodnes som tomu nevenoval pozornosť. Keďže som na zmienku o Ruby DSL natrafil znova, išiel som pohladať nejaké príklady, pretože mi nebolo celkom jasné ako to vôbec myslia.

Na výrobu DSL je zvyčajne potrebné skonštruovať akýsi parser tohoto špecializovaného jazyka. Také niečo samozrejme nie je triviálne, preto som si DSL asocioval najmä s Common Lispom, ktorý má v tomto navrch, pretože nepotrebuje žiaden špeciálny parser a tak je možné tieto DSL využívať priamo v programe. Program v programe, na to je Lisp špecialista.

Krásnym príkladom sú argumenty makra loop 1). Toto makro dovoľuje jednoducho a čitateľne zapísať veľké množstvo rôznych iterácií. Napríklad faktoriál:

(loop for i from 1 to n
      for acc = 1
      then (* acc i)
      finally (return acc))

Tento zápis pripomína iné jazyky z rodiny Algol, ale samotný Lisp ani náhodou. Je to DSL, konkrétne jazyk na zápis iterácií rôznej podoby a rôznych výsledkov. Makrá v Lispe sa prekladajú rovnako ako v C ešte pred vykonaním programu, takže použitie loop je vlastne zadarmo, neprináša žiadnu výkonnostnú penalizáciu.

Samozrejme keď mi podobný obraz behal po rozume, nebolo mi celkom jasné ako niečo také jednoducho a efektívne spraviť v Ruby. Dôvod bol omnoho prozaickejší – DSL v Ruby nie sú DSL v pravom slova zmysle.

Ukážky čo som našiel mali spoločné črty – snažili sa vyzerať ako angličtina a využívali benevolentnosť v syntaxi Ruby aby vynechali zátvorky. Prvá črta môže byť rozhodne príjemná pre používateľa, ale v žiadnom prípade to nie je nutná podmienka DSL. Tá druhá je len dôkazom, že je to stále len Ruby.

DSL je naozaj doménovo špecifický a mal by vychádzať z toho čo chceme dosiahnuť. Najskôr sa teda navrhne ako má taký zápis vyzerať a potom sa to implementuje.

Ruby je celkom praktický jazyk a toto pripodobenie DSL v konečnom dôsledku pomáha vytvárať použiteľný a konzistentný interface (názvy metód, keywords a pod.), čo je rozhodne dobrá vec. Takže nakoniec tento hype, nebol celkom zbytočný, a tým nemyslím len ako cieľ vtipkovania 2).

weblog.txt · Last modified: 2010/08/03 06:21 by 127.0.0.1