Etykiety też mają adresy

2011-08-12 21:25

Natrafiłem niedawno na kapitalną ciekawostkę, sponsorowaną przez literkę C – język C, rzecz jasna. A jeśli już o C mowa, to jednym z pierwszym skojarzeń są oczywiście wskaźniki; prawdopodobnie nie jest ono zresztą specjalnie pozytywne ;) Wśród nich mamy wskaźniki na funkcje, które znane są z kilku nieocenionych zastosowań (weźmy na przykład funkcję qsort), ale przede wszystkim z pokrętnej i niezbyt oczywistej składni.

Zalecam jednak przypomnienie jej sobie, bo dzisiaj będzie właśnie o wskaźnikach na funkcje, tyle że pokazujących na… etykiety. Tak, te właśnie etykiety (labels), które normalnie są celem instrukcji gotozłej, niezalecanej, i tak dalej. Okazuje się bowiem, że etykiety też mają swoje adresy, które w dodatku można pobrać i wykorzystać jako wskaźniki:

  1. #include <stdio.h>
  2.  
  3. int main() {
  4.     first:
  5.     second:
  6.     printf("first = %p, second = %p, last = %p", &&first, &&second, &&last);
  7.     last:
  8.     return 0;
  9. }

Wymagany jest do tego podwójny znak ampersandu (&), co można traktować jako osobny operator lub rodzaj specjalnej składni… W każdym razie jest on konieczny, aby kompilator wiedział, że następująca dalej nazwa jest etykietą. Mają one bowiem swoją własną przestrzeń nazw, co oznacza, że możliwe jest występowanie np. zmiennej start i etykiety start w tym samym zasięgu.
Przykładowym wynikiem działania programu jest poniższa linijka:

first = 0x4004f8, second = 0x4004f8, last = 0x400519

Pierwsze dwa adresy są sobie równe i nie powinno to właściwie być zaskakujące. Jak można się bowiem łatwo domyślić, adresy etykiet to w istocie adresy instrukcji, które są nimi opatrzone. Dla osób programujących w asemblerze powinno być to dziwnie znajome :) W powyższym przykładzie zarówno first, jak i second mają adresy odpowiadające położeniu w pamięci kodu wywołania funkcji printf.

Wróćmy jednak do wspomnianych wcześniej wskaźników na funkcje. Mając bowiem pobrany adres etykiety, możemy go przypisać do takiego właśnie wskaźnika. Dzięki temu możemy etykiety możemy “wywoływać”, i to nawet z innych funkcji!
Jak to jednak w ogóle działa? Ilustruje to poniższy przykład, w którym funkcja wywołuje w ten sposób sama siebie:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4.  
  5. typedef int (*find_func)(int*, int, int);
  6. int find(int* tab, int n, int x) {
  7.     int i = 0;
  8.     top:
  9.     if (n == 0) return -1;
  10.     else {
  11.         if (*tab == x)  return i;
  12.         ++i; ++tab; --n;
  13.  
  14.         find_func tail_call = (find_func)&&top;
  15.         tail_call(tab, n, x);
  16.         return -2;  // nieosiągalne
  17.     }
  18. }
  19.  
  20. int main(int argc, char* argv[]) {
  21.     int tab[10] = { 2, 3, 6, 4, 8, 3, 9, 1, 7, 0 };
  22.     printf ("Element '%d' znaleziony na pozycji %d\n", 1, find(tab, 10, 1));
  23. }

Po pobieżnym przyjrzeniu się widać, że jest to zwykłe liniowe przeszukiwanie tablicy, w dodatku w sposób który wygląda na rekurencyjny… Jest to jednak specjalny rodzaj tzw. rekurencji ogonowej (tail recursion). Występuje ona wówczas, gdy wywołanie rekurencyjne jest ostatnią instrukcją funkcji. Taki przypadek może być wówczas zoptymalizowany przez co sprytniejsze kompilatory poprzez wyeliminowanie konieczności ponownego odkładania argumentów na stos. Kolejny poziom rekursji wykorzystuje po prostu te same argumenty – jest to możliwe, o ile nie ma konieczności rekurencyjnych powrotów i składania kolejnych wyników.
W powyższym przykładzie rekursja ogonowa występuje jednak niezależnie od jakichkolwiek optymalizacji, gdyż jest ona zawarta w “wywołaniu” etykiety top. Chociaż pozornie wygląda to jak wywołanie funkcji, nie powoduje utworzenia dodatkowej ramki stosu ani ponownego odłożenia na nim argumentów. Docelowa “funkcja” operuje na istniejącym stosie. W istocie więc mamy tu do czynienia z pewną wersją instrukcji goto, czyli zwykłego skoku.

Ciekawiej zaczyna się robić wtedy, gdy spróbujemy “wywołać” etykietę z innej funkcji, co – jak wspomniałem – jest zupełnie możliwe. Możliwe jest wówczas gładkie przekazanie jej wszystkich parametrów oraz zmiennych lokalnych, co automatycznie podpada pod kategorię Rzeczy Podejrzanych i Potencjalnie Niebezpiecznych :) Niemniej jednak jest to możliwe:
#include

int foo = 1, i;

typedef int (*args_func)(int argc, char* argv[]);
args_func process(int argc, char* argv[]) {
if (foo == 1) {
return &&inside;
}
if (foo == -1) {
inside:
for (i = 1; i < argc; ++i) printf("Arg #%d: %s\n", i, argv[i]); } return 0; } int main(int argc, char* argv[]) { process(0, NULL)(0, NULL); // sic }[/c] Powyższy program przekazuje swoje argumenty do funkcji process (która je wypisuje) mimo iż zupełnie tego nie widać w jej wywołaniu. Zresztą normalne wywołanie tej funkcji jedynie zwraca adres jej etykiety, pod który później skaczemy z maina bez dokładania nowej ramki do stosu.

W tym kodzie jest też kilka innych smaczków (jak chociażby rola zmiennej foo), których odkrycie pozostawiam jednak co bardziej dociekliwym czytelnikom :) Zaznaczę tylko, że cała ta (chyba) niezbyt praktyczna zabawa z pobieraniem adresów etykiet jest w gruncie rzeczy rozszerzeniem GCC i nie jestem pewien, czy będzie działać w jakimkolwiek innym kompilatorze.

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


11 comments for post “Etykiety też mają adresy”.
  1. Sebas86:
    August 12th, 2011 o 22:00

    Jeśli goto jest złe i be, to za to, najpewniej, wieszają za jajka, a jak już się urwą to posypują jeszcze solą. ;)

  2. Sebas86:
    August 12th, 2011 o 22:07

    A zmienna foo jest na 99% po to aby kompilator niechcący nie zoptymalizował funkcji. Gdyby zmienna foo było oznaczona jako statyczna, najpewniej GCC zrobiłby z niej stałą czasu kompilacji i później uprościł co nieco samą funkcję.

  3. Kacper Kołodziej:
    August 12th, 2011 o 22:28

    Mi tam wskaźniki wcale się źle nie kojarzą :) Wszystko dzięki Panu J. Gręboszowi i Jego “Symfonii” :)

  4. Xevaquor:
    August 13th, 2011 o 11:16

    Osobiście bardzo lubię wskaźniki, w C++ od razu widzę które parametry są przekazane przez wartość, czy są modyfikowalne, brakuje mi tego w C# gdzie zawsze muszę się chwilę nad tym zastanowić :(

    A odnośnie tematu posta: jest jakieś praktyczne zastosowanie tego ficzera?

  5. olo16:
    August 13th, 2011 o 14:18

    @Xevaquor – praktyczne zastosowania – konkursy na zaciemniony kod.

    Taa, nie ma to jak assembler w C…

  6. Xion:
    August 13th, 2011 o 18:13

    @Xevaquor: W C# są parametry ref i out.
    Co do praktycznych zastosowań adresów etykiet, to można by się bawić w jakieś tablice skoków, jak to zostało opisane choćby tutaj.

  7. MSM:
    August 14th, 2011 o 23:17

    `brakuje mi tego w C# gdzie zawsze muszę się chwilę nad tym zastanowić` – dziwne, szczególnie że o ile nie ma out albo ref to odpowiedzią zawsze jest ‘przez referencję’ :P (ok, chyba że przekazujesz value type, ale to głównie int, char etc)
    Mi się tam feature podoba, w sam raz do pisania kodu na co dzień w pracy ;).

  8. dmp:
    August 15th, 2011 o 11:29

    Ciekawostka, bez sensownego zastosowania – podoba mi się ;)

  9. olo16:
    August 21st, 2011 o 23:48

    Jeszcze jedno: skoro funkcja operuje na istniejącym stosie, to przejmuje nie tylko parametry, ale i zmienne lokalne.

  10. olo16:
    August 21st, 2011 o 23:50

    (Ech, właściwie z tymi zmiennymi lokalnymi to powtórzyłem to co było w poście, niedokładnie coś go przeczytałem…)

    Tak czy inaczej naprawdę ciekawa konstrukcja…

  11. Łukasz Grądzik:
    August 30th, 2011 o 12:13

    Ha,
    a jednak nie wiedziałem jeszcze wszystkiego o C.
    Jak to w pracy zastosuję to na code review chyba mnie podpalą i wyrzucą przez okno :)

    Swoją drogą ciekawe co na to narzędzia do statycznej analizy kodu.

Comments are disabled.
 


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