Programowanie w Scheme

Scenariusz 5: Kontynuacje

Często podczas projektowania funkcji jakiegoś systemu stajemy przed dylematem, co robić w sytuacji nietypowej, która nie odpowiada podstawowej definicji funkcji. Najprostszymi przykładami mogą tu być usuwanie wierzchołka stosu, gdy stos jest pusty, czy wyszukiwanie opisu symbolu w słowniku, w którym ten symbol nie występuje. Możemy oczywiście przerwać obliczenia i przekazać użytkownikowi odpowiedni komunikat korzystając z formy specjalnej

(error komunikat wyrażenie ...)}

(define (odszukaj1 symbol słownik)
  (cond ((null? słownik)
         (error "Nie występuje " symbol))
        ((eq? symbol (caar słownik))
         (cdar słownik))
        (else (odszukaj1 symbol (cdr słownik)))))

Jednakże w konkretnym przypadku zastosowania systemu nietypowa sytuacja wcale nie musi być błędna! Może się zdarzyć, że jeśli symbol nie został odnaleziony w słowniku, to należy go tam dołączyć. W tym wypadku funkcja odszukaj1 nie jest przydatna, gdyż przerywa obliczenia. Tak więc nie znając zastosowania, rozwiązanie z użyciem error powinniśmy raczej odrzucić.

Często przyjmowanym rozwiązaniem jest wybór pewnej ustalonej wartości (zwykle wartości oznaczającej fałsz) jako wyniku funkcji w sytuacji nietypowej. Tak działa na przykład systemowa funkcja member dla niezdefiniowanej własności. Gdy jednak ta sama wartość może być przyjmowana również w sytuacji typowej, takie rozwiązanie ma poważne wady. Można ich uniknąć, przekazując jako wynik funkcji parę: informację o rodzaju wyniku i ewentualną wartość w sytuacji typowej

(define (odszukaj2 symbol słownik)
  (cond ((null? słownik)
         (cons '*BŁĄD*
               (list symbol 'nie 'występuje)))
        ((eq? symbol (caar słownik))
         (cons 'OK            ; --- to nie jest błąd
               (cdar słownik)))
        (else (odszukaj2 symbol (cdr słownik)))))

Podane rozwiązanie powoduje pewne niedogodności w korzystaniu z funkcji: przed skorzystaniem z przekazanej wartości, należy sprawdzić, czy nie wykryto sytuacji nietypowej. Oznacza to, że nie można korzystać ze zwykłego składania funkcji i zamiast

(przetwórz (odszukaj 'Kowalski Grupa15))

... (let ((opis (odszukaj2 'Kowalski Grupa15)))
      (if (car opis)
          (error "Zły opis" opis)
          (przetwórz (cdr opis))))) ...

Podobne kłopoty mieli twórcy Lispu z odzyskiwaniem pamięci. Jawne zwalnianie pamięci w wyrażeniach zaburzało naturalną strukturę składania funkcji; rozwiązaniem stało się dokonywanie tego w sposób ukryty --- tak narodził się pomysł odśmiecania.

Najlepszym wyjściem z tej kłopotliwej sytuacji jest przekazywanie funkcjom systemu dodatkowych parametrów funkcyjnych, które określają, co należy robić w sytuacji typowej i nietypowej. Często takie funkcje są nazywane \emph{funkcjami sukcesu} i \emph{funkcjami porażki}. Pierwsza z nich jest stosowana w sytuacji typowej dla argumentu będącego właściwym wynikiem. Drugą stosujemy w sytuacji nietypowej z argumentami, które pozwolą nam wykonać jakieś dodatkowe akcje. Oczywiście jeśli sytuacji nietypowych jest więcej, możemy mieć więcej funkcji porażki.

Sama funkcja porażki nie wystarcza, bo po zakończeniu jej wywołania program wróciłby w to samo miejsce. Później zobaczymy, jak można temu zapobiec. A na razie używajmy obu funkcji.

Funkcja odszukaj może być zapisana w tym stylu w następujący sposób

(define (odszukaj symbol słownik sukces porażka)
  (cond ((null? słownik)
         (porażka symbol))
        ((eq? symbol (caar słownik))
         ;tu przekazujemy opis łącznie z symbolem,
         ;gdyż da nam to większe możliwości
         (sukces (car słownik)))
        (else (odszukaj symbol (cdr słownik)
                        sukces porażka))))

Skorzystajmy teraz z tej funkcji przy rozwiązywaniu kilku zadań. Pierwszym niech będzie funkcja opis, która ma dostarczyć opis odpowiadający symbolowi. Jeśli symbol nie występuje w słowniku, powinniśmy zasygnalizować błąd:

(define (opis symbol słownik)
  (odszukaj symbol słownik
            ;funkcja sukcesu: należy pobrać opis hasła
            (lambda (hasło) (cdr hasło))
            ;funkcja porażki: należy zasygnalizować błąd
            (lambda (s)
              (error "Nie występuje " symbol))))

Funkcja odszukaj może być też użyta do wprowadzenia nowego symbolu i jego opisu do słownika. Tym razem sytuacją błędną jest przypadek, gdy wprowadzany symbol występuje w danym słowniku:

(define (rozszerz-słownik słownik symbol opis)
  (odszukaj symbol słownik
            ;funkcja sukcesu dla odszukaj: błąd dla funkcji
            ;rozszerz-słownik
            (lambda (h)
              (error "Już występuje  " symbol))
            ;funkcja porażki dla odszukaj: wprowadzenie
            ;opisu nowego symbolu
            (lambda (s)
              (cons (cons symbol opis)
                    słownik))))

Zdefiniujmy jeszcze funkcję zmieniającą opis symbolu na nowy. Ma ona sens tylko wtedy, gdy symbol występuje w słowniku

(define (zmień-opis symbol słownik nowy-opis)
  (odszukaj symbol słownik
            ;funkcja sukcesu: zmieniamy opis
            (lambda (hasło) (set-cdr! hasło nowy-opis))
            ;funkcja porażki: sygnalizacja błędu
            (lambda (s)
              (error "Nie występuje " symbol))))

Czasami mamy więcej niż jeden słownik (np. interpreter może mieć: słownik symboli lokalnych, słownik symboli globalnych oraz słownik symboli prymitywnych i systemowych). Wyszukanie symbolu polega wtedy na przeglądaniu kolejnych słowników

(define (odszukaj* symbol słowniki sukces porażka)
  (if (null? słowniki)
      (porażka symbol)
      (odszukaj symbol (car słowniki)
                ;funkcja sukcesu dla jednego słownika
                ;jest taka sama jak dla całego zadania
                sukces
                ;funkcja porażki dla jednego słownika: należy 
                ;kontynuować poszukiwania w pozostałych słownikach
                (lambda (s)
                  (odszukaj* symbol (cdr słowniki)
                             sukces porażka)))))

Teraz funkcja pobierająca wartość związaną z danym symbolem wygląda następująco

(define (wartość symbol)
  (odszukaj* symbol
             (list LOKALNE GLOBALNE SYSTEMOWE)
             (lambda (hasło) (cdr hasło))
             (lambda (s)
               (error "*NIEZADEKLAROWANE* " symbol))))

Kontynuacje systemowe

Każda wywoływana funkcja jako dodatkowy ukryty parametr otrzymuje kontynuację: informację co zrobić z wynikiem. Na przykład dla wyrażenia

(let ((x 3))
  (set! x (f1 (f2 x) (f3 x)))
  (display x) 
  (newline))

(let ((x 3))
  (set! x <wynik>)
  (display x) 
  (newline))

Kontynuację taką można zapisać jawnie jako funkcję. Jeśli definicją funkcji f1 byłoby

(define (f1 x y)
  (+ x y))

(define (f1 x y kont)
  (kont (+ x y)))

Trzeba jednak również nieco zmienić otaczający kontekst

(let ((x 3))
  (f1 (f2 x) (f3 x)
      (lambda (wynik)
        (set! x wynik)
        (display x) 
        (newline))))

Scheme udostępnia kontynuacje systemowe za pomocą wbudowanej funkcji call-with-current-continuation (call/cc) oraz pozwala z nich korzystać jak z normalnych procedur jednoargumentowych.

(call-with-current-continuation (lambda (nazwa-kontynuacji) wyrażenie ...))
(call/cc (lambda (nazwa-kontynuacji) wyrażenie ...))

System wywołuje wtedy funkcję będącą argumentem call/cc, przekazując jej jako argument bieżącą kontynuację. W normalnej sytuacji wartością (call/cc ...) jest wartość ostatniego wyrażenia w treści. Jeśli w trakcie obliczania któregoś z tych wyrażeń napotkamy wywołanie

(nazwa-kontynuacji wynik)

> (call/cc (lambda (powrót)
             (print 1) (print 2) (powrót 3) (print 4))
1
2
3

No to pora na coś ciekawszego (kont1.scm)

(let ((i 0) (kont #f))
  (call/cc (lambda (k1) (set! kont k1)))
  (when (< i 10)
    (set! i (+ i 1))
    (kont i))
  i)

Popatrzmy, jak można zastosować kontynuacje systemowe w definicjach funkcji odszukaj, opis, zmień, rozszerz-słownik, odszukaj* i wartość, omówionych w poprzednim rozdziale.

Zacznijmy od odszukaj. W przypadku, gdy symbol został odnaleziony, stosujemy kontynuację (lub funkcję) sukces. Gdy symbol nie został odnaleziony, wartością odszukaj może być dowolna wartość --- wybieramy #f

(define (odszukaj symbol słownik sukces)
  (cond ((null? słownik) #f)
        ((eq? (caar słownik) symbol)
              (sukces (car słownik)))
        (else (odszukaj symbol (cdr słownik) sukces))))

Funkcja opis, sygnalizująca błąd w przypadku, gdy symbol nie został odnaleziony, jest następująca

(define (opis symbol słownik)
  (cdr (call/cc (lambda (znaleziony)
                  (odszukaj symbol słownik znaleziony)
                  (error "Nie występuje" symbol)))))

W przypadku, gdy symbol został odnaleziony, funkcja opis przekazuje hasło do kontynuacji znaleziony. Oznacza to zakończenie obliczania wyrażeń występujących w call/cc. Tak więc wyrażenie error nie jest obliczane. Wartością całego wywołania call/cc jest przekazane hasło. Z przekazanego hasła funkcja cdr pobiera opis. Podobnie definiujemy zmień

(define (zmień symbol słownik nowyopis)
  (set-cdr! (call/cc (lambda (znaleziony)
                       (odszukaj symbol słownik znaleziony)
                       (error "Nie występuje" symbol)))
            nowy-opis))

W przypadku funkcji rozszerz-słownik musimy postąpić inaczej: powrót przez kontynuację sukces w funkcji odszukaj ma sygnalizować błąd, natomiast w przypadku zakończenia obliczeń z wartością #f należy wprowadzić symbol.

Możemy to rozwiązać, korzystając z dwóch kontynuacji systemowych lub formy error w kontynuacji sukces. Przedstawimy oba rozwiązania.

Wariant pierwszy: dwie kontynuacje: znaleziony i zmodyfikowany

(define (rozszerz-słownik słownik symbol opis)
  (call/cc
    (lambda (zmodyfikowany)
      (call/cc
        (lambda (znaleziony)
          (odszukaj symbol słownik znaleziony)
          (zmodyfikowany (cons (cons symbol opis)
                               słownik))))
      (error "Już występuje" symbol))))

Prześledźmy zachowanie tej wersji. Jeśli symbol występuje w słowniku, funkcja odszukaj oblicza wyrażenie (znaleziony (car słownik)). Obliczanie tego wyrażenia oznacza zakończenie obliczania pierwszego wyrażenia z listy w (call/cc (lambda (zmodyfikowany) ...)). Po nim następuje obliczanie drugiego wyrażenia, (error ...). Tak więc odpowiedni błąd jest zasygnalizowany, a interpretacja bieżącego wyrażenia kończy się.

Natomiast jeśli symbol nie występuje w słowniku, wartością odszukaj jest #f. Przechodzimy więc do obliczania kolejnego wyrażenia z listy w (call/cc (lambda (znaleziony) ...)). Rozszerzony słownik przekazany jest kontynuacji zmodyfikowany. To kończy obliczanie (call/cc (lambda (zmodyfikowany) ...)) z wartością będącą nowym słownikiem. W tym przypadku wartością rozszerz-słownik jest więc ten nowy słownik.

Wariant drugi: sukces nie jest kontynuacją systemową

(define (rozszerz-słownik słownik symbol opis)
  (odszukaj symbol słownik
            (lambda (hasło)
              (error "Już występuje" symbol)))
  (cons (cons symbol opis)
        słownik))

Podobnie, możemy mieć kilka wersji funkcji odszukaj*. Pierwsza jest poprawna jedynie wówczas, gdy parametrem /code>sukces jest kontynuacja systemowa

(define (odszukaj* symbol słowniki sukces)
  (if (null? słowniki)
      #f
      (begin
        (odszukaj symbol (car słowniki) sukces)
        (odszukaj* symbol (cdr słowniki) sukces))))

Parametr sukces musi być koniecznie kontynuacją systemową (lub stosować formę error), gdyż zwykłe przekazanie wartości oznaczałoby zakończenie obliczania (odszukaj ...) i obliczanie (odszukaj* ...) dla reszty słowników.

W drugiej wersji odszukaj*, parametrem sukces może być również funkcja. Należy teraz zatroszczyć się o to, by kontynuacja stosowana wówczas, gdy symbol jest odnaleziony, pozwalała na zastosowanie kontynuacji bądź funkcji sukces i jednocześnie zapobiegała obliczaniu odszukaj* dla niesprawdzonych jeszcze słowników.

Możemy to osiągnąć wprowadzając --- podobnie jak to było w przypadku poprzednich funkcji --- nową kontynuację znaleziony i przekazując ją przez funkcję (lambda (hasło) (znaleziony (sukces hasło))) jako parametr sukces wyszukiwania w jednym słowniku. Zastanówmy się, jak wygląda zastosowanie tej funkcji do odnalezionego hasła.

Jeśli sukces jest kontynuacją systemową, to wówczas obliczanie wyrażenia (sukces hasło) zakończy jednocześnie obliczanie wszystkich odszukaj*, gdyż jest to kontynuacja jakiegoś wyrażenia na zewnątrz użycia odszukaj*. Jeśli natomiast sukces jest funkcją, to hasło zostanie przez nią przekształcone i zmodyfikowana wartość będzie przekazana kontynuacji znaleziony, która zakończy obliczenia ostatniego wywołania odszukaj*. Po tych rozważaniach możemy zdefiniować odszukaj* jako

(define (odszukaj* symbol słowniki sukces)
  (if (null? słowniki)
      #f
      (call/cc
        (lambda (znaleziony)
          (odszukaj symbol (car słowniki)
                    (lambda (hasło)
                      (znaleziony (sukces hasło))))
          (odszukaj* symbol (cdr słowniki)
                     sukces)))))

Ostatnia wersja również wprowadza lokalną kontynuację znaleziony. Tym razem chcemy, by była to kontynuacja sukcesu dla odszukaj. Aby to osiągnąć, musimy wprowadzić lokalną funkcję wyszukiwania w słownikach. Sytuację, gdy symbol nie występuje w żadnym słowniku, obsłużymy za pomocą kontynuacji nieznaleziony. Otrzymujemy następującą postać

(define (odszukaj* symbol słowniki sukces)
  (call/cc
    (lambda (nieznaleziony)
      (sukces
        (call/cc
          (lambda (znaleziony)
            (letrec ((wyszukuj
                      (lambda (słowniki)
                        (cond ((null? słowniki)
                               (nieznaleziony #f))
                              (else
                               (odszukaj symbol
                                         (car słowniki)
                                         znaleziony)
                               (wyszukuj (cdr słowniki)))))))
              (wyszukuj słowniki))))))))

Analiza tej wersji jest podobna do analizy przeprowadzonej dla funkcji rozszerz-słownik. Zauważmy tylko, że tu przekazanie wartości do kontynuacji znaleziony lub nieznaleziony kończy cały łańcuch rekurencyjnych wywołań funkcji wyszukuj.

Przedstawmy jeszcze definicję funkcji wartość korzystającej z odszukaj*

(define (wartość symbol sukces)
  (sukces
    (cdr (call/cc (lambda (znaleziony)
                    (odszukaj* symbol
                               (list LOKALNE GLOBALNE
                                     PRYMITYWNE)
                               znaleziony)
                    (error "*NIEZADEKLAROWANE*"
                           symbol))))))

Przy okazji możemy teraz precyzyjnie określić wywołanie redukcyjne. Wywołanie jest redukcyjne, gdy jako domyślną kontynuację otrzymuje kontynuację wyrażenia otaczającego.