Lisp

LAB 01 - Wprowadzenie

Programowanie funkcyjne – Co to jest?

Paradygmat funkcyjny polega na tym, że pisząc program, tworzymy coraz bardziej skomplikowane pojęcia matematyczne, aż do osiągnięcia celu. Pojęcia te mają postać stałych i funkcji, stąd nazwa programowanie funkcyjne. Oczywiście tworzone funkcje są wykonywalne, tzn. dostarczając argumentów możemy obliczyć ich wartości.

W "czystym" programowaniu funkcyjnym nie występuje jednak pojęcie zmiennej ani przypisania. Nie ma też pętli jako konstrukcji związanych z czasem i zmianą. Tworzenie programu polega na tworzeniu coraz to bardziej złożonych funkcji i stałych oraz na obliczaniu wartości wyrażeń.

Jeśli nie ma zmiennych, przypisania ani pętli, to co jest? Zamiast operacji mamy obliczanie wyrażeń. Zamiast przypisań mamy definiowanie stałych i funkcji (funkcje to w pewnym sensie też stałe, tylko o bardziej skomplikowanej naturze). Zamiast pętli mamy rekurencję.

Charakterystyczne dla programowania funkcyjnego jest to, że często bardzo łatwo jest napisać poprawny program, przepisując sformułowanie problemu, choć zwykle nie jest to najefektywniejszy program.

LISP (ang. LISt Processing) jest językiem programowania zorientowanym na programowanie funkcyjne. Jest to jeden z najstarszych języków programowania (pochodzi z tych samych czasów co Algol, Fortran). Prace nad Lispem, traktowanym, jako narzędzie do obliczeń na strukturach symbolicznych, rozpoczęto w 1958 w MIT, pod kierunkiem Johna McCarthy’ego. Pierwsza implementacja powstała w 1960 roku. Na początku był popularny tylko w kręgach akademickich, obecnie cieszy się coraz większą popularnością. Spośród wielu dialektów tego język najpopularniejszym stał się dialekt Scheme.

Matematyczne podstawy języka Lisp stanowi rachunek lambda wprowadzony przez Churcha. Podstawowe cechy języka to:

- złożenie funkcji to podstawowa struktura sterowania

- obliczenia powtarzalne są opisywane jedynie przy pomocy rekursji

- użycie dynamicznych struktur listowych, jako podstawowych elementów języka

Program w Lispie jest ciągiem wyrażeń i definicji. Definicje są interpretowane deklaratywnie tzn., są zapamiętywane i od razu można z nich skorzystać. Wyrażenia interpretowane są imperatywnie, co oznacza, że są obliczane natychmiast.

- reprezentacja programów, jako obiektów języka, co pozwala na wygodną manipulację nimi przy tworzeniu bardziej złożonych struktur.

Podstawy programowania w Lispie

Notacja prefiksowa W powszechnej praktyce stosuje się notację infiksową. Polega ona na tym, że funktory od dwóch argumentów wpisuje się pomiędzy nimi np. 7+3 Notacja prefiksowa polega na wpisywanie funktora przed jego argumentami (używane jest to matematyce i w analizach teoretycznych). Np.≤7 + 2 5 oznacza 7≤2+5 Tradycyjnemu zapisowi f(x,y) odpowiada (f x y)

Podstawowe obliczenia

W najprostszy sposób możemy pracować z Lispem w trybie interpretera:

> znak zachęty, po którym wprowadzamy formuły,
rezultat obliczeń.

Na przykład:

> (+ 4 9)
13

> (- 5 7)
-2

> (/ 15.0 2)
7.5

W każdym powyższym przypadku, wprowadzona formuła to tak naprawdę lista, której pierwszym elementem jest symbol funkcji, a pozostałe elementy to argument tej funkcji.

Kilka dodatkowych przykładów:

> (atom 123)
T

> (numberp 123)
T

> (atom :foo)
T

ATOM i NUMBERP to predykaty. Predykaty zwracają wartość prawda (T) lub fałsz. NIL to jedyna wartość fałsz w LISPIE, wszystkie inne jest prawdą. Jeśli predykat nie ma innych użytecznych wartości do zwrócenia, zazwyczaj zwraca wartość T (prawda). ATOM zawraca wartość T jeśli jego argumentem jest atom. Analogicznie NUMBERP zwraca T jeśli jego argumentem jest liczba.

Do wyliczenia wartości każdej z powyższych form, LISP najpierw ocenia argumenty (od lewej do prawej), następnie ocenia pierwszy element, żeby pobrać jego funkcję, następnie stosuje funkcję do jej argumentów. Poza pewnymi wyjątkami, żeby obliczyć wartość listy LISP zawsze:

1) Oblicza argumenty z lewej do prawej

2) Pobiera funkcję związana z pierwszym argumentem

3) Stosuje znalezioną funkcję do jej argumentów.

Pamiętajmy, że atomy mogą być również formami LISPU. Kiedy chcemy obliczyć atom, po prostu dostajemy jego wartość:

> 17.95
17.95

>*FEATURES*
(:ANSI-CL :CLOS :COMMON-LISP)

>"Hello, world!"
"Hello, world!"

Zmienna *FEATURES* jest predefiniowana w LISPIE – jej wartość zależy od system, w którym się pracuje.

Funkcja może zwracać każdą ilość liczb albo wartości (jak?)

Żeby zwrócić wiele wartości należy użyć formy VALUES. Przykład:

> (values 1 2 3 :hi "Hello")
1
2
3
:HI

"Hello"

Zauważmy, ze każda wartość występuje w nowej linii.

Standardowe funkcje

Funkcje matematyczne - W tej grupie znajdują się funkcje o argumentach i wartościach liczbowych, między innymi obliczające wartości matematycznych funkcji elementarnych, takich jak funkcja potęgowa, wykładnicza i logarytmiczna, funkcje trygonometryczne itd. W większości mają one łatwe do odgadnięcia nazwy i sposób działania zgodny z oczekiwaniami. Wymieniamy tylko kilka z nich.

• abs (x) — zwraca wartość bezwzględną argumentu x:
  > (abs -1.2)
  1.2

• evenp, oddp (x) — zwracają t jeśli argument jest odpowiednio liczbą parzystą i nieparzystą oraz nil w przeciwnym przypadku:
  > (oddp 251)
  NIL
  > (evenp 251)
  T

• floor, ceiling (x) — zwracają wartość argumentu zaokrąglona odpowiednio w dół i w górę do najbliższej liczby całkowitej jako pierwszą wartość oraz resztę jako drugą wartość:
  > (floor 3.75)
  3 ;
  0.75
  > (ceiling 3.25)
  4 ;
  -0.75

• round (x) — zwraca wartość argumentu zaokrąglona do najbliższej liczby całkowitej jako pierwszą wartość oraz resztę jako drugą wartość:
  > (round 3.75)
  4 ;
  -0.25
  > (round 3.25)
  3 ;
  0.25

• exp (x) — zwraca wartość funkcji wykładniczej dla argumentu x, czyli wartość e podniesioną do potęgi x:
  > (exp 1)
  2.7182817

• expt (x y) — zwraca wartość x podniesioną do potęgi y:
  > (expt 27 0.33)
  2.9672222

• log (x) — zwraca logarytm naturalny z argumentu x:
  > (log 2.7182818)
  0.99999994

• max (x1 x2 ...) — zwraca maksymalną z wartości dowolnej liczby argumentów:
  > (max -1 3 18 -5 4)
  18

• min (x1 x2 ...) — zwraca minimalną z wartości dowolnej liczby argumentów:
  > (min -1 3 18 -5 4)
  -5

• mod (x y) — zwraca wartość x modulo y:
  > (mod 23 4)
  3

• sin, cos, tan (x) — zwracają wartość funkcji sinus, cosinus, tangens dla argumentu x:
  > (sin 3.14)
  0.001592548

• sqrt (x) — zwraca pierwiastek kwadratowy z argumentu x:
  > (sqrt 2)
  1.4142135

• random (x) — zwraca nieujemną liczbę pseudolosową mniejszą od wartości x i typu takiego jak x:
  > (random 10)
  4
  > (random 10.0)
  6.800773

• rem (x y) — zwraca wartość reszty z dzielenia podanego argumentu