Poza nawiasem

Definiowanie funkcji w Scheme jest rzeczÄ? naprawdÄ? piÄ?knÄ?. Podczas czytania pierwszych przyk??ad??w kodu, jak i p????niej, podczas pisania w??asnych kawa??k??w rozwiÄ?zujÄ?cych zadane problemy, towarzyszy??o mi uczucie panowania nad ??rodowiskiem wykonania programu. Swoboda wyra??ania my??li przy pomocy prostych konstrukcji dawa??a (i wciÄ??? daje) mi ogromnÄ? satysfakcjÄ?. Dzisiaj dopiero u??wiadomi??em sobie skÄ?d to wra??enie siÄ? bierze.

Po pierwsze, zdefiniowane przez nas funkcje u??ywa siÄ? dok??adnie w ten sam spos??b, jak te predefiniowane w u??ywanym przez nas ??rodowisku. We??my na przyk??ad prostÄ? definicjÄ? funkcji podnoszÄ?cej liczbÄ? do dowolnego naturalnego wyk??adnika.

(define (** a b)
  (if (= b 0)
      1
      (* a (** a (- b 1)))))

Definiujemy funkcjÄ? o nazwie ** (tak, to nie pomy??ka) przyjmujÄ?cÄ? dwa argumenty. Je??eli drugi argument jest zerem, zwracamy jeden (bo cokolwiek do potÄ?gi zerowej to jeden), w przeciwnym wypadku wynikiem jest a przemno??one przez a do potÄ?gi (b-1). Bardzo proste, a jednocze??nie otwierajÄ?ce oczy na prawdziwe wykorzystanie rekurencji. Ale do tego jeszcze wr??cimy p????niej. Symbol podw??jnej gwiazdki spodoba siÄ? zapewne programistom Pythona, ale niekt??rzy woleliby np. ^. Nie ma ??adnego problemu.

(define (^ a b)
  (if (= b 0)
      1
      (* a (^ a (- b 1)))))

W tej postaci funkcja wciÄ??? dzia??a poprawnie:

(^ 2 128)
340282366920938463463374607431768211456

Nic nie stoi oczywi??cie na przeszkodzie, by przedefiniowaÄ? funkcje wbudowane. Co wiÄ?cej, mo??na nawet prze??adowaÄ? definicjÄ? form specjalnych! Co powiecie na to?

(define (define a)
  (* a a))

W??a??nie zdefiniowali??my funkcjÄ? o nazwie define, kt??ra podnosi sw??j argument do kwadratu. Oczywi??cie tym sposobem pozbawili??my siÄ? sposobu na u??ywanie wbudowanego define, potencjalnie psujÄ?c ca??Ä? resztÄ? kodu, kt??ra zapewne na domy??lnym zachowaniu define polega. Ale z drugiej strony nikt nie powiedzia??, ??e programujemy na powa??nie. ;-)

Drugim czynnikiem, kt??ry powoduje, ??e tak bardzo polubi??em nawiasy jest piÄ?kno jakie tkwi w prostocie sk??adni Scheme. Ta prostota naprawdÄ? zachÄ?ca i o??miela do programowania. I o ile ju?? s??ysza??em o programowaniu bottom-up i wydawa??o mi siÄ?, ??e rozumiem to pojÄ?cie, dopiero po do??wiadczeniu lekko??ci i swobody pisania w Scheme poczu??em na w??asnej sk??rze co ono oznacza. Chocia?? lubiÄ? programowaÄ?, Scheme powoduje, ??e nie mogÄ? przestaÄ? definiowaÄ?, wyszczeg??lniaÄ?, abstrahowaÄ? i tak a?? do osiÄ?gniÄ?cia idea??u… Paul Graham znowu mia?? racjÄ?.

Nie trzeba daleko szukaÄ?, by przekonaÄ? siÄ? o tym, co napisa??em. RozwiÄ???my wsp??lnie Ä?wiczenie 1.3. Jego tre??Ä? brzmi nastÄ?pujÄ?co:

Zdefiniuj procedurÄ? o trzech argumentach bÄ?dÄ?cych liczbami, kt??rej wynikiem jest suma kwadrat??w dw??ch wiÄ?kszych argument??w.

Zanim zdefiniujemy zadanÄ? funkcjÄ?, potrzebne nam bÄ?dzie kilka funkcji pomocniczych. Potrzebujemy z pewno??ciÄ? funkcji znajdujÄ?cej dwa wiÄ?ksze elementy spo??r??d trzech zadanych argument??w. Ja zdefiniowa??em jÄ? tak:

(define (max-two a b c)
  (if (< a b)
      (list b (if (< a c)
          c
          a))
      (list a (if (< b c)
          c
          b))))

W kodzie wykorzysta??em funkcjÄ? wbudowanÄ? list, kt??ra ze wszystkich podanych argument??w tworzy listÄ?. Kod jest prosty, ale dla tych, kt??rzy jeszcze nie przyzwyczaili siÄ? do nawias??w, oto wersja w Pythonie:

def max_two(a, b, c):
    if a < b:
        if a < c:
            return [b, c]
        else:
            return [b, a]
    else:
        if b < c:
            return [a, c]
        else:
            return [a, b]

Nie jest on szczeg??lnie pythonowy, ale obrazuje ideÄ?. Za pomocÄ? dw??ch warunk??w znajdujemy najmniejszy element spo??r??d trzech i zwracamy listÄ? z??o??onÄ? z pozosta??ych dw??ch. Drugi warunek mo??na jednak upro??ciÄ?. Potrzebna nam bÄ?dzie funkcja zwracajÄ?cÄ? element wiÄ?kszy spo??r??d dw??ch zadanych. Nazwiemy jÄ? greater.

(define (greater a b)
  (if (> a b)
      a
      b))
 
(define (max-two a b c)
  (if (< a b)
      (list b
            (greater a c))
      (list a
            (greater c b))))

Tak, teraz to wyglÄ?da o wiele lepiej. Problem w og??lnym przypadku (dla dowolnej ilo??ci liczb) sprowadza siÄ? do posortowania listy i wybrania kilku element??w z poczÄ?tku/ko??ca. Na tÄ? chwilÄ? jest to zadanie wykraczajÄ?ce poza moje mo??liwo??ci programowania w Scheme. Ale obiecujÄ?, ??e do tematu jeszcze wr??cÄ?.

Gdyby??my teraz spr??bowali stworzyÄ? funkcjÄ? rozwiÄ?zujÄ?cÄ? podane zadanie, zauwa??yliby??my, ??e czego?? nam brakuje.

(define (fun a b c)
  (+ (square …?

Problemem jest funkcja max-two, kt??ra zwraca listÄ?. Wiemy, ??e lista jest dwuelementowa, musimy jeszcze dobraÄ? siÄ? do kolejnych warto??ci. Scheme nie ma dla nas indeksowania, ale specyficzne operatory car i cdr. car zwraca pierwszy element listy, za?? cdr listÄ? z usuniÄ?tym pierwszym elementem. Inaczej m??wiÄ?c, przy pomocy tych dw??ch funkcji potrafimy roz??o??yÄ? listÄ? na g??owÄ? i ogon. Jeste??my ju?? coraz bli??ej rozwiÄ?zania.

(define (fun a b c)
  (+ (square (car (max-two a b c)))
      (square (car (cdr (max-two a b c))))))

Od razu widaÄ? brzydotÄ? tego rozwiÄ?zania, bo musimy dwa razy wywo??aÄ? funkcjÄ? max-two. W tym momencie istnieje pokusa, by obliczyÄ? listÄ? dw??ch najwiÄ?kszych element??w i zwiÄ?zaÄ? jÄ? z jakÄ??? lokalnÄ? nazwÄ? we wnÄ?trzu funkcji. Jako argumenty car i cdr wykorzystaliby??my wtedy zawczasu obliczonÄ? warto??Ä?. W Pythonie by??oby to ca??kiem naturalne:

def fun(a, b, c):
    # przechowanie wartosci w tymczasowej zmiennej
    L = max_two(a, b, c)
    return square(L[0]) + square(L[1])

Jednak to rozwiÄ?zanie jest ma??o lispowe (o ile mo??na m??wiÄ? o wyczuciu stylu Lispa w tak wczesnym okresie nauki). Na usta (a raczej pod palce) ci??nie siÄ? wiÄ?c definicja nowej funkcji.

(define (sum-of-squares L)
  (+ (square (car L))
      (square (car (cdr L)))))
 
(define (fun a b c)
  (sum-of-squares (max-two a b c)))

CzyniÄ?c listÄ? argumentem funkcji zwalniamy interpreter z obowiÄ?zku dwukrotnego obliczania jej warto??ci (chocia?? to te?? zale??y od sposobu dzia??ania interpretera, co mam nadziejÄ? opisaÄ? nastÄ?pnym razem). Oczywi??cie do szczÄ???cia brakuje nam jeszcze funkcji square, obliczajÄ?cej kwadrat podanego argumentu.

(define (square a)
  (* a a))

I w ten oto spos??b otrzymali??my dzia??ajÄ?cÄ? funkcjÄ?, obliczajÄ?cÄ? sumÄ? kwadrat??w dw??ch wiÄ?kszych argument??w. Po napisaniu tego kodu pomy??la??em, ??e ciekawie by??oby uog??lniÄ? funkcjÄ? sum-of-squares, tak by oblicza??a sumÄ? kwadrat??w wszystkich element??w listy, bez wzglÄ?du na to ile by ich nie by??o. W zwiÄ?zku z tym, ??e funkcja ta przetwarza listÄ?, najbardziej naturalnie bÄ?dzie zapisaÄ? jej definicjÄ? rekurencyjnie. Jak w ka??dej funkcji rekurencyjnej potrzebujemy wiÄ?c warunku zako??czenia rekursji. W tym przypadku bÄ?dzie to lista pusta. Suma kwadrat??w listy pustej wyniesie oczywi??cie zero. Listy posiadajÄ?ce przynajmniej jeden element bÄ?dÄ? za?? rozwijane rekurencyjnie, poprzez ucinanie kolejnych g????w operatorem car. Z resztÄ? nie ma co t??umaczyÄ?, kod jest naprawdÄ? prosty. Oto on:

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

Wyja??nienia wymaga jeszcze tylko funkcja equal?. Zwraca ona warto??Ä? prawda, gdy podane jej dwa argumenty sÄ? r??wne. Na jej podstawie zdefiniowali??my funkcjÄ? empty? okre??lajÄ?cÄ? czy lista jest pusta. Mo??liwo??Ä? u??ywania znak??w takich jak wykrzyknik czy znak zapytania jest bardzo przydatnÄ? cechÄ? Scheme. Zalety sÄ? wyra??nie widoczne.

W tym miejscu w zasadzie mo??na by pokusiÄ? siÄ? o implementacjÄ? og??lnych funkcji takich jak map, czy reduce, ale w ten spos??b nie zosta??o by nic na p????niej. ;-) Na dzisiaj to wszystko. Do us??yszenia.