3148972488

Kombinatory punktu stałego

Równania stałopunktowe w programowaniu.

Podobny problem pojawia się przy definicjach funkcji rekurencyjnych, np.

s(n) = if n = 0 then 1 else n * s(n — 1)

lub inaczej:

s = An.if n = 0 then 1 else n * s(n — 1)

Z matematycznego punktu widzenia jest to równanie (wyższego rzędu) z jedną niewiadomą s. Symbol = oznacza tu (3 (lub Prj) konwersję. Problem rozwiązania tego równania, tj. znalezienia lambda termu, spełniającego równanie, sprowadza się do znalezienia punktu stałego funkcjonału:

F = A/n.if n = 0 then 1 else n * f(n — 1)

Zdzisław Spławski: Teoretyczne Podstawy Języków Programowania, Wykład 4. Siła wyrazu rachunku