Poza nawiasem

Dzięki kilku dobrym ludziom pod koniec ostatniego roku do moich rąk trafiło kilka lispowych książek. Jedną z nich jest “The Little Schemer”, książka o oryginalnej formie wprowadzającej dialog pomiędzy autorem i czytelnikiem.

Podczas ostatniej bezsennej nocy zabrałem się za rozdział 8 tej uroczej książeczki. Nazywa się on znacząco: Lambda the Ultimate. Zaczyna się od rozważań nad procedurami wyższego rzędu (ang. higher-order functions). Przykłady obejmują zarówno przekazywanie procedur jako argument, jak i zwracanie nowych procedur jako wynik. Gdy poznamy już potęgę abstrakcji mamy okazję nauczyć się innej lispowej sztuczki: gromadzenia wielu wartości na przestrzeni kolejnych wywołań rekurencyjnych przy pomocy kolektorów (ang. collectors). Przykładowa funkcja wykorzystująca kolektor poniżej:

(define multiinsertLR&co
  (lambda (new oldL oldR lat col)
    (cond
     ((null? lat)
      (col lat 0 0))
     ((eq? (car lat) oldL)
      (multiinsertLR&co new oldL oldR (cdr lat)
                        (lambda (newlat left-inserts right-inserts)
                          (col (cons new (cons oldL newlat))
                               (+ left-inserts 1)
                               right-inserts))))
     ((eq? (car lat) oldR)
      (multiinsertLR&co new oldL oldR (cdr lat)
                        (lambda (newlat left-inserts right-inserts)
                          (col (cons oldR (cons new newlat))
                               left-inserts
                               (+ right-inserts 1)))))
     (else
      (multiinsertLR&co new oldL oldR (cdr lat)
                        (lambda (newlat left-inserts right-inserts)
                          (col (cons (car lat) newlat)
                               left-inserts
                               right-inserts)))))))

Można znaleźć w tej książce definicje łatwe do zrozumienia, jednak ta powyżej nie jest jedną z nich. Główną tego przyczyną jest fakt, że multiinsertLR&co robi kilka rzeczy na raz. Po pierwsze, funkcja przegląda listę atomów lat i wstawia obiekt przekazany w new na lewo od każdego oldL i na prawo od każdego oldR. Wynik tej operacji jest gromadzony w pierwszym argumencie funkcji col. Oprócz tego, multiinsertLR&co podlicza ilość wykonanych wstawień. Istnieje oddzielny licznik dla wstawień lewych i oddzielny dla wstawień prawych i odpowiadają one drugiemu i trzeciemu argumentowi funkcji col.

Ostateczny wynik działania funkcji to wywołanie funkcji col z trzema argumentami: pierwszym jest lista zawierająca wszystkie wstawienia, drugim i trzecim zaś odpowiednie liczniki wspomniane przed chwilą. Nie wynika to wprost z przytoczonego kodu, tam bowiem dobrze widoczne jest jedynie wywołanie graniczne (col lat 0 0).

Jest jeszcze jedna niepokojąca rzecz w powyższych 23 linijkach kodu. Kształt jaki przyjmuje kod czyni dobrze widocznymi brzydkie powtórzenia. Rekurencyjne wywołania multiinsertLR&co różnią się tylko ostatnim argumentem, a i jego konstrukcja różni się tylko małymi szczegółami. Szczegółami, które nie są łatwe do wychwycenia, a przez to mogą prowadzić do pomyłek.

Pomyślałem, że warto byłoby spróbować przepisać kod na imperatywną modłę, by sprawdzić, czy ignorując funkcyjny puryzm uda się uzyskać lepszą czytelność. Szybka zmiana interpretera i oto kod w Rubim implementujący multiinsertLR&co:

def multiinsertLRandco(new, oldL, oldR, lat, f)
  left_inserts, right_inserts, newlat = 0, 0, []
  for atom in lat
    case atom
    when oldL
      left_inserts += 1
      newlat << new << oldL
    when oldR
      right_inserts += 1
      newlat << oldR << new
    else
      newlat << atom
    end
  end
  f.call(newlat, left_inserts, right_inserts)
end

Na pierwszy rzut oka widać zredukowane powtórzenia. Imperatywny styl ułatwia również zrozumienie działania funkcji. Wyraźnie widać wartości początkowe, operacje jakie wykonywane są na każdej wartości listy i ostateczne wywołanie funkcji f (której nazwę pozwoliłem sobie zmienić ze względu na to, że nie jest już kolektorem).

Chociaż jest bliższe, temu rozwiązaniu nadal brakuje trochę do ideału. Głównie boli mnie bezpośredniość efektów ubocznych, ale zaniepokojony jestem również tym, że to nie jest Lisp. ;-) Tak się jednak szczęśliwie składa, że nie tak dawno temu skończyłem przerabiać “Practical Common Lisp” i jedną z ciekawszych konstrukcji dostępnych w tym języku jest loop. Makro to pozwala w zwięzły sposób zapisać różne rodzaje pętli. Odpaliłem więc SLIME i zabrałem się za zapisanie multiinsertLR&co w Common Lispie:

(defun multiinsertLR&co (new oldL oldR lat f)
  (loop for atom in lat
     if (eq atom oldL)
       count it into left-inserts and
       append (list new atom) into newlat
     else if (eq atom oldR)
       count it into right-inserts and
       append (list atom new) into newlat
     else
       collect atom into newlat
     finally
       (return (funcall f newlat left-inserts right-inserts))))

Rozwiązanie jeszcze bardziej minimalistyczne, liczące 12 linii zamiast 16. Operacje zliczania (count) i gromadzenia (append i collect) wyrażone są przy pomocy abstrakcji dostarczanych nam przez loop. Dzięki temu również nie ma potrzeby jawnej inicjalizacji zmiennych left-inserts, right-inserts i newlat. Całość zaś czyta się niemalże jak zwykły tekst w języku angielskim. Wydaje się, że każde słowo w powyższym kodzie ma znaczenie. Bliski perfekcji jest kod, z którego nie ma już czego odjąć.

Dzisiejszy tekst pozwolę sobie zakończyć cytatem z Małego Schemera: