Z pogranicza

Programowanie w jezyku Scheme

  • 2006-02-24 14:06
  • 4 komentarze
  • 1840 odsłon
  • Oceń ten tekst jako pierwszy



Wprowadzenie i kilka słów o cyklu artykułów


Moja przygoda z językiem Scheme zaczęła się na jednym z przedmiotów na studiach. Ponieważ nie studiuje w Polsce program różni się nieco od tego na polskich uczelniach i także rozwiązania prezentowane na studiach dostosowane są do rozwiązań używanych i stosowanych w konkretnym kraju. Język Scheme nie przypadł mi do gustu, ale ponieważ reprezentuje dość specyficzne podejście do programowania postanowiłem napisać cykl artykułów o programowaniu w tym języku. W końcu to także informatyka, a ja mam egzamin pojutrze i traktuje to jako ostateczne powtórzenie i utrwalenie wiadomości. Z pewnością dla ludzi programujących na codzień interacyjnie, linijka po linijce, chcących nauczyć się Scheme, zepsuje to wiele krwi, ale nie łamcie się, ja też zawsze skrobie linijka po linijce i jakoś mi się udało.

Język Scheme bazuje na dość dojrzałym języku LISP, jest jednak osobnym językiem i w żadnym razie nie stanowi podzbioru LISP. Wiadomo mi, że nauczany jest jako normalny kurs na University of Rice oraz MIT, wiem też że istnieje u mnie. Normalnie język Scheme stosuje się do programowania sztucznej inteligencji, dość łatwo można nawiązać w nim dialog z użytkownikiem, poza tym składnia jego nie jest skomplikowana, jest to język zorientowany na użytkownika. Z drugiej strony wymaga bardzo dokładnego rozumienia problemu jaki rozwiązujemy oraz zrozumienia struktur i typów danych jakie będziemy używać (liczby, listy, własne struktury itp), dlatego dla programistów, którzy lubią pisać "na żywca" może trochę ostudzić ich zapał, niemniej jednak warto się z nim zapoznać bo to ciekawe doświadczenie.

Pierwotną wersją jaką zrobiłem był kurs tego języka w całej okazałości, jednak ponieważ to ma być przejrzyste podzieliłem to na cykl artykułów, które sukcesywnie postaram się konwertować i dodawać, póki co pierwszy artykuł powinien pomóc wam w wyborze czy chcecie czytać następne.

Interpreter oraz teachpacs


Do języka Scheme najpopularniejszym interpreterem jest Dr.Scheme. W licencji freeware można go pobrać ze strony http://www.htdp.org>http://www.htdp.org, istnieje z pewnością dla Linux oraz Windows i prawdopodobnie MAC. Obsługa jest wyjątkowo prosta. Interpreter dzieli okno na dwa mniejsze. W jednym umieszczamy kod programu (tym górnym) a w drugim testujemy program. Przy pierwszym uruchomieniu kompilator nakaże także wybór języka. Proponuje wybrać "Beginning student", a od podpunktu 5. przejść na "Intermediate Student with Lambda", tak na wszelki wypadek. Różnica jest w sygnalizacji błędów oraz, że niektóre procedury zdefiniowane odgórnie w języku "Beginning Student" nie istnieją.

Teachpacs są to pakiety do nauki dodane przez twórców interpretera, zawierają gotowe przykłady i procedury. Coś jak moduły np. w Delphi. My będziemy używać głównie modułu graficznego (w późniejszych etapach) oraz modułu GUI, ale napisze odpowiednią wstawkę kiedy i jak należy je dodać i jak z nich korzystać. Ogólnego opisu możliwości pakietów szkoleniowych (teachpacs) należy szukać w dokumentacji dostępnej w kompilatorze. Znajdują się tam wszystkie dostępne procedury dla każdego z nich.

Proste typy danych


Pierwszym, chyba najprostszym do omówienia tematem w programowaniu w Scheme są działania i przetwarzanie prostych typów danych. Do takich należą  przede wszystkim liczby (wyrażenia arytmetyczne), wyrażenia logiczne oraz symbole czy ciągi znaków. Bez pisania właściwego programu Dr.Scheme jest w stanie podać nam wynik nawet najbardziej zagnieżdżonych wyrażeń (równań itp.). Spróbujmy rozwiązać kilka przykładów. Używamy do tego celu górnego okna. Następne po wpisaniu przykładu naciskamy przycisk "Run" w prawym górnym rogu i obserwujemy reakcje w dolnym oknie.

Przykład
Zakładamy, że chcemy obliczyć najprostsze z możliwych wyrażeń. Chcemy wykonać dodawanie dwóch cyfr: 5 oraz 7. Matematycznie zapisujemy to w wiadomy sposób: 5 + 7 = 12. W języku Scheme szablon wygląda tak:

(operator x y)

gdzie operator to operator matematyczny jak np. (+ - * /) a x oraz y to liczby na których chcemy operacje matematyczną wykonać. Dla powyższego przykładu poprawny będzie zapis:
(+ 5 7)

po skompilowaniu przyciskiem RUN, w dolnym  oknie pojawi się wynik 12. Wprowadź następujące przykłady do kompilatora (mogą być pod sobą) oraz oblicz samemu ich wartość:
  • (+ 4 5 6)
  • (+ 4 (* 3 3))
  • (- 1 (* (/ 3 3) 1))
  • (+ 2 (* 3 (+ 4 (- 5 1)) 2 4))

Początkowo metoda ta może wydawać się nieco złożona, ale w rzeczywistości postępujemy tu dokładnie tak samo jak w matematyce. Najpierw obliczamy najbardziej zagnieżdżone działania (ad3. najpierw wykonywane jest dzielenie 3 przez 3, później mnożenie wyniku tego dzielenia * 1, a dopiero na końcu odejmowanie całego poprzedniego wyrażenia od jedynki na początku. Jest to dokładne wyrażenie kolejności wykonywania działań zgodnej z matematyką, regulowane przez nawiasy.

Dla uzupełnienia tej wiedzy dodam, że Scheme oferuje szereg stałych, oraz predefiniowanych wyrażeń do obliczeń matematycznych (jak pierwiastkowanie, potęgowanie itp.) Kilka najbardziej użytecznych zamieszczam poniżej. Możesz wypróbować ich działanie w kompilatorze.

  • Stała pi (3.141592653589793) (#i oznacza, że wyrażenie jest liczbą)
    • np. (2 * pi)
  • Stała e (2.718281828459045)

    • np. (4 * e)
  • (sqrt A) - Pierwiastek kwadratowy z A

    • np. (sqrt 4)
  • (expt A B) - Oblicza AB

    • np. (expt 2 3)
  • (remainder A B) - Oblicza resztę z dzielenia całkowitego A przez B

    • np. (remainder 5 3)
  • (log A) - Oblicza logarytm naturalny z A

    • np. (log e)
  • (sin A) - Oblicza sinus kąta A podanego w radianach

    • np. (sin 0)
  • (max A B) - Wskazuje na większą pośród podanych liczb

    • np. (max 3 4)

Napisz w języku Scheme działanie obliczające pole koła o promieniu 4.
Prawidłowa odpowiedź: (* (* 4 4) pi) bądź (* pi (* 4 4))

Wyrażenia logiczne


Dobrze znane programistom są wyrażenia logiczne zwracające prawdę lub fałsz danego zapytania czy warunku (true / false). W języku Scheme także istnieją i są dość powszechnie używane. Skupimy się jednak na nich podczas omawiania predykantów kilka linijek niżej.

Symbole i ciągi znaków


Symbole są dość prostym do zrozumienia typem danych. Umożliwiają jednak wykonywanie wielu typów operacji na nich (między innymi ich porównywanie, łączenie, są też dobrym elementem wyrażeń warunkowych). Generalnie symbol w języku Scheme traktujemy jako ciąg znaków, wyraz, słowo (word), które nie zawiera spacji. Dodatkowo wyróżniamy je w Scheme znakiem apostrofu (').

Przykładowe symbole to:

  • 'mama
  • 'kot
  • 'nie-zawiera-spacji
  • '@@
  • '@

Jak pewnie słusznie zauważyliście symbol także jest czasami ciągiem znaków (ad 3.), jednak jak wspomniałem symbole nie mogą zamierać spacji (ani innych niektórych znaków specjalnych jak np. # czy nawias). Natomiast właściwe ciągi znaków nazywamy stringami :) Ogólnie deklarujemy je w postaci "wyr", jednak to tylko wprowadzenie do języka i nie będziemy się w zasadzie nimi zajmować. Stosują rozszerzenie symboli, które jednak w zupełności nam wystarczą.

O operacjach na symbolach już za chwilę.

Predykanty


Predykanty to wyrażenia, które w języku Scheme mają za zadanie zwracać logiczną wartość (patrz wyżej: "Wyrażenia logiczne") zapytania które reprezentują w zależności od podanych parametrów. Są bardzo użyteczne, często występują jako pierwsza część wyrażeń warunkowych i są łatwe w użyciu. Zwykle kończą się znakiem zapytania (?), co wskazuje że tak jak pytanie zwracają wartość true lub false. Przykłady zaprezentowałem poniżej:

  • (number? A)- sprawdza czy A jest liczbą, jeśli tak zwraca true, w przeciwnym razie false
  • (boolean? A) -sprawdza czy A jest typem logicznym (true lub false), jeśli tak zwraca true, w przeciwnym razie false
  • (symbol? A)- sprawdza czy A jest symbolem, jeśli tak zwraca true, w przeciwnym razie false
  • (struct? A)- sprawdza czy A jest strukturą, jeśli tak zwraca true, w przeciwnym razie false
  • (even? X)- weryfikuje czy X jest liczbą parzystą, jeśli tak zwraca true, w przeciwnym razie false
  • (odd? X)- weryfikuje czy X jest liczbą nieparzystą, jeśli tak zwraca true, w przeciwnym razie false
  • (equal? X Y)- weryfikuje czy liczby X i Y są sobie równe, jeśli tak zwraca true, w przeciwnym razie false
  • (symbol=? A B)- weryfikuje czy symbole A i B są sobie równe.
  • (string=? A B)- weryfikuje czy stringi A i B są sobie równe

Przykład
Wprowadź poniższe przykłady do kompilatora i postaraj się przewidzieć ich rezultat.

  • (number? 'c)
  • (odd? 3)
  • (even? 3)
  • (even? 2)
  • (equal? 4 4)
  • (string=? "mama" "tata")
  • (boolean? true)
  • (boolean? false)
  • (equal? 4 (+ 2 2))
  • (boolean? (equal? 6 (* 2 (+ 2 1))))


Jak widzimy ostatni przykład pozwala zastosować wcześniej poznane operacje matematyczne, w tym właśnie Scheme jest dość uniwersalny, możemy łączyć takie wyrażenia. Oczywiście na wyjściu pojawi się wartość true, ponieważ nie ważne jaki rezultat przyniosło by equal? to i tak będzie on boolean (zarówno true czy false), ponieważ equal? jako że jest predykantem zwracam również boolean.

Definicje i funkcje


Istnieją sytuacje, w których nasze środowisko zawiera więcej niż jeden program czy funkcje dla jednego problemu. W późniejszych przykładach i problemach będzie to nieuniknione rozwiązanie, które także znacznie poprawia czytelność kodu programu w języku Scheme. Właśnie w takich sytuacjach musimy używać niekiedy po kilka razy tych samych danych, ponadto dane wejściowe mogą różnić się od siebie. Wtedy korzystamy z definicji.

Aby przydzielić wyrażeniu stałą wartość korzystamy z polecenia define. Dodam, że wyrażenia definiowane również możemy zagnieżdżać, jak powyżej.

Przykład
Jak widzieliśmy w poprzednich przykładach wartość wyrażenia stałej pi zdefiniowanej w Dr.Scheme jest dość dokładna i rozwinięta daleko poza setną część liczby. W prostych obliczeniach np. nie potrzebujemy tak rozwiniętej wartości, zależy nam jedynie na wyniku do setnej części np. 21.39 zamiast 21.38728174. Zdefiniujemy zatem nasze_pi, o wartości 3.14.
(define nasze_pi 3.14)

W tym momencie Dr.Scheme traktuje nasze_pi jako taką samą "stałą" jak pi czy e. Spróbujmy tym razem stworzyć działanie obliczające obwód koła o promieniu  10, a następnie jego pole, używając przy tym definicji naszego nowego pi. Zapiszemy to następująco:
; definiujemy nasze pi
(define nasze_pi 3.14)

; tak sygnalizujemy komentarz
; obwód koła r=10
(* 2 nasze_pi 10)

; teraz obliczamy pole koła r=10
(* nasze_pi (* r r))


Oczywiście moglibyśmy zamiast nasze_pi wpisać dwa razy 3.14, ale funkcjonalność tego nie byłaby najlepsza, poza tym zapis poprzez nasze_pi jest bardziej czytelny. Wynikiem jest co najwyżej liczba z drugim miejscem po przecinku. Zwróćmy uwagę, że gdy w dolnym okienku napiszemy: nasze_pi wartością zwrotną będzie 3.14

Podobny zabieg możemy zastosować aby zdefiniować ogólne schematy działań czyli funkcje. W dużej części całe środowisko Scheme opiera się na funkcjach. Najważniejsze co musimy o nich wiedzieć to to, że funkcje zwracają wartości. W przypadku innych jezyków programowania np. Delphi zapisywaliśmy je w następujący sposób:

function NazwaFunkcji : typ_wartosci_zwracanej_przez_funkcje;

gdzie typem wartości był np. integer, real, boolean, string itp. W Scheme nie istnieje podobne rozwiązanie. Funkcja zwraca to co jej narzucimy w trakcie jej przetwarzania, nie definiujemy tego w nagłówku. Zaraz pokaże w czym rzecz. Funkcje stosujemy przede wszystkim aby uogólnić problemy, tworzyć wzory (dla przykładu chcemy obliczyć pole koła nie tylko dla promienia 10, ale dla każdego dowolnego). Semantyka funkcji w Scheme wygląda następująco:


(define (NazwaFunkcji par1...par n)
 (ciało funkcji))


gdzie par to parametr (minimum jeden) funkcji, zauważmy, że przed NazwaFunkcji występuje nawias, tworzy on nagłowek funkcji (który kończy się po ostatnim parametrze zamknięciem nawiasu), następny nawias tworzy część właściwą funkcji, czyli zostawia nam miejsce na procedury.

Przykład
Tworzymy funkcję obliczającą promień koła a następnie funkcję obliczającą obwód koła dla dowolnego r. Użyjemy poznanej definicji nasze_pi oraz określimy tak zwany kontrakt funkcji.


; Definiujemy nasze_pi = 3.14 (define nasze_pi 3.14)
; Tworzymy kontrakt funkcji (nazwa: par1...par n -> zwracana_wartosc) ; Kontrakt to jedynie komentarz dla nas o tym, jak działa funkcja ; PoleKola: number -> number (define (PoleKola promien) (* nasze_pi (* promien promien)))
; ObwodKola: number -> number (define (ObwodKola promien) (* 2 nasze_pi promien)))


Kompilujemy i wpisujemy w dolnym oknie w celu sprawdzenia:
(PoleKola 5)
(ObwodKola 7)

Wszystko w porządku, jak widać pod zmienną promień raz zostało podstawione 5, a drugi raz 7. Funkcja działa poprawnie ponieważ zgodnie z kontraktem zwróciła number (w naszym wypadku wartość pola lub obwodu). Oczywiście można to dalej skracać, np. poprzez stworzenie definicji dla kwadratu promieni, lub definiując promień tak jak nasze_pi, jeśli wiemy, że chcemy obliczać pole i obwód dla koła o tym samym promieniu.

Zadanie
Napisz funkcję, która obliczy pole prostokąta o bokach A i umownym B, przy wiedzy, że B jest dwa razy większy od A. Zwróć uwagę na kontrakt funkcji, który zakłada, że podajemy tylko jeden parametr A, z którego B jest obliczany.

; Oto kontekt funkcji PoleProstokata ; PoleProstokata: number -> number ; na przykład: ; (PoleProstokata 5) -> 50
; Rozwiązanie: (define (PoleProstokata a) (* a (* a 2)))


</kbd>
Dzieki powyzszemu wprowadzeniu mozecie pocwiczyc tworzenie wlasnych funkcji, obliczajacych podstawowe zadania matematyczne, lub operacje na zmiennych logicznych czy symbolach. Postaram sie w najblizszym czasie kontynuowac cykl artykulow i poprawiac na biezaco bledy w juz dodanych.

4 komentarze

Assa 2011-09-07 20:30

Scheme to nie jako rozwinięcie Lispu. A więc wystarczy tutek Lispu i manual Scheme by się pobawić :)

Marooned 2006-02-23 18:02

Polecam zapoznać się ze znacznikiem

Spis treści

- generuje on automatycznie spis treści wraz z odnośnikami.

miner 2006-02-23 17:52

Niezle, szybko mozna sie nauczyc sheme (przynajmniej podstaw). Dzieki tobie chyba sie tym zainteresuje. Sciagnalem program i... jestem zadowolony.

  • Idzie ćwiczyć pisanie własnych funkcji i googlować w poszukiwaniu kursu Scheme *

intacto 2006-03-12 15:56

Nie ma w języku polskich żadnych kursów języka Scheme z tego co mi wiadomo. Jest książka pt. "Projektowanie oprogramowania. Wstęp do programowania i techniki komputerowej" wyd. Helion, gdzie zawiera się kurs Scheme (choć jak autor wspomina, nie jest to książka przedstawiająca kurs języka), jednak to tłumaczenie "How to design programs" o którym pisałem w artykule. Na internecie jest jeden kurs, bardzo skrótowy, z przykładami ale dość niejasny. Już za tydzień kolejna seria.