Poza nawiasem

Na wyk??adzie 1b pan Sussman wprowadza nas w tematykÄ? z??o??ono??ci obliczeniowej. Mimo tego, ??e jest to domena informatyki teoretycznej, robi to na tyle przystÄ?pnie, ??e nawet najbardziej oporni sÄ? w stanie co?? z tego wynie??Ä?. To, na co chcia??bym zwr??ciÄ? uwagÄ?, to spos??b w jaki jÄ?zyk Scheme u??atwia dos??owne pokazanie rozwoju procesu podczas wykonania. Przyk??ad u??yty na wyk??adzie znale??Ä? mo??na w ksiÄ???ce jako Ä?wiczenie 1.9. Pe??na jego tre??Ä? podana jest na ko??cu czÄ???ci 1.2.1, ja przytoczÄ? tylko odpowiednie kody ??r??d??owe. Zadanie polega na opisaniu procesu generowanego przez ka??dÄ? z procedur. Pierwszy kod ??r??d??owy wyglÄ?da nastÄ?pujÄ?co:

(define (+ a b)
  (if (= a 0)
      b
      (+ (dec a) (inc b))))

Procedury inc i dec odpowiednio zwiÄ?kszajÄ? i zmniejszajÄ? sw??j argument o jeden. Ta definicja dodawania m??wi wiÄ?c, ??e sumÄ? a i b jest b je??eli a jest r??wne zero, w przeciwnym razie jest to suma a-1 i b+1. Stary problem jest wiÄ?c zastÄ?powany przez nowy problem. Proces kolejnych redukcji problemu do problem??w je zastÄ?pujÄ?cych jest przedstawiony na obrazku poni??ej. Wykonywana operacja to (+ 3 4).

Jak wyra??nie widaÄ?, ta technika upraszczania problemu, chocia?? korzysta z definicji rekurenycjnej (funkcja + wywo??uje samÄ? siebie) generuje proces iteracyjny. Dzieje siÄ? tak dlatego, bo w momencie wywo??ania (+ (dec a) (inc b)) iterpreter wie, ??e mo??e zastÄ?piÄ?, “nadpisaÄ?” oryginalne wywo??anie tym nowym. A ma takÄ? mo??liwo??Ä?, bo wynik tego wywo??ania jest jednocze??nie wynikiem oryginalnego wywo??ania. Dlatego (+ 3 4) znaczy to samo co (+ 2 5), co znaczy to samo co (+ 1 6), itd. a?? do momentu, gdy problem upro??ci siÄ? do postaci, w kt??rej jeste??my w stanie udzieliÄ? jednoznacznej odpowiedzi (w tym przypadku nastÄ?pi to, gdy a dojdzie do zera). Inaczej jednak jest dla drugiego kodu.

(define (+ a b)
  (if (= a 0)
      b
      (inc (+ (dec a) b))))

Tutaj definiujemy sumÄ? a i b jako zwiÄ?kszonÄ? o jeden sumÄ? a-1 i b. Kszta??t procesu generowanego przez tÄ? procedurÄ? jest zupe??nie inny.

W tym przypadku nie zastÄ?pujemy starego problemu nowym problemem, ale definiujemy dla niego zupe??nie nowy podproblem, kt??rego rozwiÄ?zanie pomo??e nam w rozwiÄ?zaniu. Musimy wiÄ?c ze zwr??ceniem wyniku poczekaÄ?, a?? interpreter obliczy (+ (dec a) b). Dopiero, gdy ten podproblem zostanie rozwiÄ?zany, bÄ?dziemy mogli zwiÄ?kszyÄ? zwr??cony przez wywo??anÄ? podprocedurÄ? wynik o jeden i og??osiÄ? nasze rozwiÄ?zanie. Fakt, ??e musimy pamiÄ?taÄ? o wykonaniu dodatkowych operacji, powoduje, ??e interpreter nie mo??e zastÄ?piÄ? starego problemu nowym, jak to uprzednio siÄ? odbywa??o. Co wiÄ?cej, dla ka??dego wywo??ania naszej sumy musi pamiÄ?taÄ?, w jakie miejsce wr??ciÄ?. I to jest przyczynÄ? liniowej pamiÄ?ciowej z??o??ono??ci tego procesu. Liniowy proces rekurencyjny nie tylko generuje liczbÄ? krok??w liniowo zale??nÄ? od danych wej??ciowych (stÄ?d liniowa z??o??ono??Ä? czasowa), ale i potrzebuje dodatkowej pamiÄ?ci dla ka??dego wywo??ania rekurencyjnego.

Je??eli wiÄ?c chcemy, by nasze programy by??y jak najszybsze i jak najmniejsze powinni??my, gdzie to jest mo??liwe, zastÄ?powaÄ? procesy rekurencyjne iteracyjnymi. Uwa??ni czytelnicy zapewne pamiÄ?tajÄ?, jak dla zabawy definiowa??em funkcjÄ? sum-of-squares obliczajÄ?cÄ? sumÄ? kwadrat??w wszystkich swoich element??w. Dla przypomnienia, kod wyglÄ?da?? nastÄ?pujÄ?co:

(define (sum-of-squares L)
  (if (null? L)
      0
      (+ (square (car L)) (sum-of-squares (cdr L)))))

Jako, ??e jÄ?zyki, na kt??rych uczy??em siÄ? programowaÄ? wpoi??y mi iteracjÄ? jako najnaturalniejszy z modeli oblicze??, nie trudno mi by??o wyobraziÄ? sobie iteracyjny spos??b obliczania tej funkcji. Przyk??adowo w Pythonie zapisa??bym to tak:

def sum_of_squares(L):
    sum = 0
    for el in L:
        sum += el**2
    return sum

Czyli, og??lnie rzecz biorÄ?c, w ka??dym momencie iteracji przechowujÄ? dotychczas obliczonÄ? sumÄ? element??w w specjalnej zmiennej sum. W Scheme do dyspozycji mamy tylko definicje rekurencyjne, wiÄ?c rozwiÄ?zanie jest odrobinÄ? d??u??sze:

(define (sum-of-squares L)
  (define (sos L sum)
    (if (null? L)
        sum
        (sos (cdr L) (+ sum (square (car L))))))
  (sos L 0))

Zdefiniowa??em pomocniczÄ? funkcjÄ? sos, kt??ra jako drugi argument przechowuje sumÄ?, kt??rÄ? nale??y dodaÄ? do ostatecznego wyniku. IteracjÄ? zaczynamy od sumy r??wnej zero, stÄ?d warto??ciÄ? wywo??ania (sum-of-squares L) jest (sos L 0). Proces jest iteracyjny, bo za ka??dym razem stare wywo??anie funkcji sos jest zastÄ?powane przez nowe. Nie ma dodatkowych oblicze?? do wykonania, ani miejsca powrotu do zapamiÄ?tania. Nowa definicja procedury sum-of-squares generuje wiÄ?c proces iteracyjny.