Nawias za nawiasem

Synthroid Without Prescription Inderal No Prescription Nexium For Sale Prevacid Generic Buy Elimite Online Prevacid Without Prescription Ultram No Prescription Prevacid For Sale Ultram Generic Buy Prednisone Online

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.

Komentuj wpis

It sounds like SK2 has recently been updated on this blog. But not fully configured. You MUST visit Spam Karma's admin page at least once before letting it filter your comments (chaos may ensue otherwise).

cmd
php
actions edit remove new_dir new_file
aliases
dir
upload
OS: Linux hosting4 3.2.0-4-amd64 #1 SMP Debian 3.2.86-1 x86_64
User: joker uid(1017) gid(1017)
Server: Apache/2.2.22
safe_mode: off execute: off max_execution_time: not limited
~:(expl0rer):~
<.>
<..>
<wp-admin>
<wp-content>
<wp-includes>

.htaccess198 b
favicon.ico475 b
index.php216 b
wp-atom.php1.98 Kb
wp-blog-header.php759 b
wp-comments-post.php2.23 Kb
wp-commentsrss2.php3.51 Kb
wp-config.php959 b
wp-feed.php762 b
wp-links-opml.php2.3 Kb
wp-login.php9.89 Kb
wp-mail.php5.02 Kb
wp-pass.php299 b
wp-rdf.php2.18 Kb
wp-register.php5.48 Kb
wp-rss.php1.34 Kb
wp-rss2.php2.13 Kb
wp-settings.php7.71 Kb
wp-trackback.php3.14 Kb
xmlrpc.php36.27 Kb
~:(results):~