Drzewo wywołań funkcji

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Drzewo wywołań funkcji (ang. call tree) to drzewo przedstawiające proces obliczania wartości wyrażenia. Liście drzewa wywołań zawierają niepodzielne części wyrażenia, czyli stałe i zmienne. Węzły wewnętrzne i korzeń odpowiadają wywołaniu funkcji (lub operatorów) z argumentami obliczonymi przez ich poddrzewa.

Drzewa wywołań rozpatruje się przede wszystkim w konstrukcji kompilatorów języków programowania, ale także w analizie programów (ang. program analysis), oraz w konstrukcji i analizie algorytmów. Najczęściej używa się takich drzew dla wyrażeń, które zawierają wywołania funkcji, lub drzewa dla obliczania wartości funkcji rekurencyjnych.

W typowych językach programowania wyrażenia mogą generować skutki uboczne. Zazwyczaj drzewo wywołań nie uwzględnia tego faktu i obrazuje jedynie strukturę obliczania. Szczególnie interesujące są drzewa wywołań dla funkcji rekurencyjnych nieposiadających skutków ubocznych. Drzewa takie można przekształcić zwykłymi metodami matematycznymi (zob. np. programowanie dynamiczne) w skierowany graf acykliczny (DAG), co umożliwia optymalizację.

Przykład[edytuj | edytuj kod]

Drzewo wywołań dla obliczania F(6)

Jako przykład rozważmy drzewo wywołań dla funkcji obliczającej wartość n-tego wyrazu ciągu Fibonacciego:

 fun F (n :int) :int = 
     if n=1 or n=2 then 1
     else F (n-1) + F (n-2)

Diagram po prawej stronie prezentuje drzewo wywołań dla wyrażenia . Dla uproszczenia pominięto tu wartości wyrażeń pośrednich, pokazując jedynie wywołania funkcji. Łatwo zauważyć, że drzewo to zawiera wiele zbędnych obliczeń, na przykład jest obliczane pięciokrotnie a trzykrotnie, pomimo tego, że wartość funkcji dla zadanych parametrów jest zawsze taka sama.

Zredukowane drzewo wywołań (skierowany graf acykliczny) dla obliczania F(6)

Kolejny diagram pokazuje jak powyższe drzewo może zostać zredukowane do grafu skierowanego za pomocą technik typu programowanie dynamiczne lub memoizacja.