3148972472

Kombinatory punktu stałego

Przykład użycia kombinatora punktu stałego: silnia.

Teraz możemy zdefiniować lambda term dla silni jako:

s = Y F gdzie F = A/n.if n — 0 then 1 else n * /(n — 1)

Uwaga. Przy wartościowaniu tego termu należy stosować redukcję normalną.

s n = (Y F)n =p F(Y F) n

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

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

Oczywiście, możliwa jest inna definicja silni za pomocą iteratora, co odpowiadałoby rekursji ogonowej.

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