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: