Ćwiczenia na deser

Jedną z zalet Lispa jest to, że jest niezniszczalny. Od jego powstania trzon języka pozostaje niezmienny; minimalistyczny, ale na tyle potężny, by inne języki programowania czerpały z niego aż do teraz. Oznacza to również, że można zostawić Lispa na kilka miesięcy i po tym wrócić do niego, mając pewność, że zbyt wiele się nie zmieniło. Muszę przyznać, że pod względem dydaktycznym jest to ogromna zaleta. Tym samym wracamy do końcówki pierwszego rozdziału Wizard Booka.

Lisp machine W miarę jak autorzy przedstawiają procedury wyższego rzędu można zrozumieć, że procedura jest czymś więcej, niż ktoś wychowany na C/C++/Javie mógłby podejrzewać. Nie jest to bowiem zwykły kawałek kodu, kontener dla ciągu instrukcji, które mamy zamiar wiele razy wywołać. Procedura nie przedstawia tylko obliczeń wykonywanych na liczbach i strukturach - jest raczej formalnym sposobem zapisu metody postępowania, która sama w sobie może korzystać nie tylko z liczbowych argumentów, ale i z innych metod. Ukazuje to wyraźnie stopnie abstrakcji, po których możemy się wspinać, definiując kolejne procedury na szczycie innych procedur. Szybko odrywamy się od pojęcia funkcji operującej na liczbach na rzecz ogólniejszej metody, sposobu postępowania, algorytmu, który możemy zapisać w postaci kodu.

Wykorzystajmy tę wiedzę w praktyce. Poniżej rozwiązanie kilku ćwiczeń rozdziału pierwszego.

Ćwiczenie 1.16

W zadaniu tym należy przekształcić podaną wcześniej definicję procedury potęgowania z formy generującej proces rekurencyjny na proces iteracyjny. Dzięki wskazówce zadanie to jest całkiem proste. Dla parzystych n liczbę b podnosimy do kwadratu, zaś dla n nieparzystych a mnożymy przez b, zachowując w ten sposób stałą wartość wyrażenia a*b^n. Poniżej pełne rozwiązanie:
(define (fast-expt a b n)
  (cond ((= n 0) a)
        ((even? n) (fast-expt a (square b) (/ n 2)))
        (else (fast-expt (* a b) b (- n 1)))))

Ćwiczenie 1.17

Tutaj autorzy proszą nas o zdefiniowanie operacji mnożenia korzystającą jedynie z dodawania, ale w taki sposób, by procedura wykonywała logarytmiczną liczbę kroków ze względu na argumenty a i b. Logarytmiczna liczba kroków w stosunku do argumentu oznacza, że przy dwukrotnym (lub w ogólności n-krotnym) wzroście argumentu liczba kroków zwiększa się o jeden. W rozwiązaniu wykorzystać mamy dwie pomocnicze funkcje double i halve, które odpowiednio podwajają i dzielą na dwa swoje argumenty:
(define (double n) (+ n n))
 
(define (halve n) (/ n 2))
Rozwiązanie:
(define (fast-mul a b)
  (cond ((= b 0) 0)
        ((even? b) (double (fast-mul a (halve b))))
        (else (+ a (fast-mul a (-  b 1))))))

Ćwiczenie 1.30

W tym ćwiczeniu wystarczy uzupełnić kod. Mając już za sobą pewne doświadczenie w przekształcaniu procesu rekurencyjnego w iteracyjny, znalezienie prawidłowego rozwiązania nie jest żadnym wyzwaniem:
(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ (term a) result))))
  (iter a 0))

Ćwiczenie 1.31

Należy zdefiniować podobną do sum procedurę product, która zwraca iloczyn wartości funkcji w punktach zadanego zakresu. Oto wersja rekurencyjna:
(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))
A to wersja iteracyjna:
(define (product term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a)
              (* (term a) result))))
  (iter a 1))
Na podstawie product definicja silni jest trywialna:
(define (identity x) x)
(define (inc n) (+ n 1))
 
(define (factorial n)
  (product identity 1 inc n))
Równie łatwo jest zapisać funkcję liczącą przybliżenie liczby π na podstawie wzoru Johna Wallisa:
(define (pi-wallis n)
  (define (pi-term n)
    (/ (square (* 2 n))
       (* (+ (* 2 n) 1)
          (- (* 2 n) 1))))
  (* (product pi-term 1 inc n) 2.0))
Przy dziesięciu tysiącach kroków funkcja ta przybliża π do czterech miejsc po przecinku, co nie jest wynikiem zbyt imponującym:
> (pi-wallis 10000)
3.141514118681922

Podsumowanie rozdziału pierwszego

Wpisem tym chciałbym zakończyć i podsumować pierwszy rozdział Wizard Booka, zatytułowany “Budowanie abstrakcji za pomocą procedur”. Materiał tego rozdziału został omówiony na wykładach wideo o numerach 1a, 1b i 2a. Poniżej lista pojęć, które udało nam się poznać:
  • Inżynieria oprogramowania różni się od innych dziedzin inżynierii tym, że największym ograniczeniem nie są prawa fizyki, ale nasze własne umysły. Innymi słowy, zbudować możemy wszystko to, co jesteśmy w stanie sobie wyobrazić.
  • Abstrakcja jest sposobem na radzenie sobie ze złożonością dużych systemów. Zamykanie funkcjonalności w “czarnych skrzynkach” pozwala nam skupić się na problemie, pomijając nieistotne szczegóły.
  • Procedury generują (czy też opisują) procesy. Procesy podczas wykonania mogą rozwijać się na różne sposoby - “kształt” procesu iteracyjnego jest inny niż “kształt” procesu rekurencyjnego.
  • Procedury reprezentują ogólne metody obliczeń, mogą więc przyjmować inne procedury jako argumenty i zwracać procedurę jako wynik.
Prócz tych ogólnych zagadnień poznaliśmy kawałek języka Scheme: W moich wpisach pojawiły się również elementy wykraczające poza pierwszy rozdział Wizard Booka, a mianowicie: Tym samym ostatecznie żegnamy się z rozdziałem pierwszym i przechodzimy do rozdziału drugiego, gdzie zajmiemy się budowaniem struktur danych.

Komentuj wpis


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):~