Lisp

Lisp (List procesor) jest językiem operującym na listach. Jest językiem w którym nie istnieją inne typy danych niż lista, oraz atom – liczba lub tekst, używany najczęściej jako element listy. W pierwotnej wersji – LISP nie oferuje sekwencyjnego wykowywana instrukcji – a jedynie superpozycję – czyli składanie funkcji. Czy w ten sposób daje się programować? Czy można budować promy opisując jedynie co zwraca funkcja?

Podstawowymi pojęciami w programowaniu w Lispie są lista asocjacji i wartościowanie form. Jeśli to zrozumiemy – to będziemy już blisko.

Lista asocjacji – jest zbiorem symboli i ich wartości. Każdy element tej listy posiada nazwę – która jest atomem, oraz wartość – która jest dowolną daną Lispa. Jeśli do tego dodamy jeszcze informację, że w Lispie wszystko jest daną – nawet funkcja – to możemy zaryzykować twierdzenie, że lista asocjacji jest zbiorem wszystkiego co w programie zdefiniowano – nadając temu nazwę czyli zbiór wszystkich funkcji i zmiennych.

W Lispie trudno oddzielić dane od funkcji. Podobnie jak możemy zmienić zawartość zmiennych – tak możemy przedefiniować treść funkcji – zmieniając jej działanie. Program może tu operować nie tylko na zmiennych – ale także na swojej treści.

Wartościowanie – to obliczanie wartości symboli. W przypadku zmiennych – nie ma problemu – wartością zmiennej jest po prostu przypisana do niej dana. Jeśli jednak wartościujemy symbol który jest funkcją – obliczane są wartości jej parametrów, a ich wartości skojarzane z lokalnymi nazwami tych parametrów a następnie obliczana jest treść funkcji.

Celowo piszę to o obliczaniu a nie wykonywaniu, gdyż ciało funkcji nie jest listą instrukcji ale pojedynczą formą – czyli czymś czego wartość można policzyć. Wartością funkcji jest więc forma stanowiąca jej treść po podstawieniu wartości pod symbole odpowiadające parametrom funkcji.

Jeśli do tego wszystkiego dodamy jeszcze, że Lisp jest językiem interpretowanym – mamy całkowite zaprzeczenie wszystkiego czego uczyliśmy się do tej pory.

Ale po kolei...

Atomy, listy i funkcje

Podstawową formą danej jest atom. Atomem jest dowolna dana będąca tekstem lub liczbą (w dowolnym formacie)  - jednym słowem wartość prosta, nie będąca obiektem, strukturą, listą itp. W Lispie atomem jest pojedyncze słowo nie zawierające spacji, lub dowolny tekst zapisany w cudzysłowach[1].

Atom może być użyty jako wartość lub jako nazwa danej. Dana może być również atomem – lub czymś bardziej skomplikowanym: listą lub funkcją – także zapisaną w postaci listy.

Jeśli w tekście programu umieścimy atom – jest on oznaczeniem zmiennej o takiej nazwie. Wyznaczanie wartości atomów jest podstawowym sposobem pracy interpretera Lispa. W zasadzie jedyne co potrafi interpreter to wyznaczać wartości atomów.

Niektóre atomy – są swoimi wartościami. Do takich atomów należą:

·         Atom nil – reprezentujący pusty element, fałsz, pustą listę, nieprawdę

·         Atom t – symbolizujący prawdę logiczną

·         Wszystkie liczby – reprezentujące swoje wartości.

Strukturą z której tworzone są wszystkie bardziej skomplikowane struktury danych jest para. Elementami pary mogą być dowolne dane – atomy, pary i struktury składające się z wielu par. Parę zapisujemy jako dwie oddzielone kropką zapisane w nawiasie:

( A . B )           ; jest parą atomów A i B

( A . ( B . C) )    ; jest parą której pierwszym elementem jest para a drugim atom.

Para jest elementem z którego tworzona jest lista – najczęściej używany typ danych. Listę zapisujemy jako ciąg elementów, oddzielonych odstępami (spacjami), ujęty w nawiasy. Lista jest parą złożoną z głowy listy i jej ogona. Lista pusta – to po prostu atom nil.  Lista jednoelementowa – para w której drugi element jest atomem nil. Tak więc

(A)           º ( A . nil )

()            º nil

( A B C D E )         º ( A . ( B C D E )

              º ( A . ( B . ( C . ( D . ( E . nil ) ) ) ) )

 

Zapis listowy w stosunku do kropkowego jest szczególnie wygodnym uproszczeniem w przypadku struktur bardziej skomplikowanych – takich jak lista list:

( (a b) (c d) (e f) ) º ( (a. (b . nil)) . ( (c . (d . nil) . ( (e . (f . nil)) . nil)))

W przypadku gdy dana nie jest listą, ale różni się od niej jedynie końcowym elementem, można skrócić zapis pisząc kropkę oddzielającą ostatnie elementy:

(a.(b.(c.(d.e)))) º (a b c d.e )

Listy prezentowane były często w postaci tzw. Diagramów pudełkowych w których para (a . b) była reprezentowana przez pudełko:

A para której elementem jest para (a . (b . c)) – w postaci dwu pudełek połączonych strzałką.

W takim zapicie lista ( a b c d e ) ma zapis:

Gdzie symbol przekreślonego prostokąta odpowiada atomowi nil. Diagramy pudełkowe wskazują na sposób implementacji list – para jest strukturą zawierającą, albo daną atomową, albo wskaźnik na następny element listy.

Struktury w wyglądające jak listy, ale nie zakończone atomem nil – nie są listami.

Wywołanie funkcji lub policzenia wartości jest w Lispie dość dziwne. Pisząc nazwę wartości zmiennej – otrzymujemy jej wartość. Wywołanie funkcji zapisujemy podobnie jak w innych językach, jednak w nawiasie zapisujemy nie tylko parametry – ale także nazwę funkcji. Ponadto nie mamy tu operatorów zapisywanych w taki sposób jak w wyrażeniach algebraicznych – a jedynie funkcje których nazwami są symbole operatorów.

 

C++

Lisp

sin(x)

(sin x)

a + b

(+ a b)

a + b + c + d

(+ a b c d)

f(g(x))

(f (g x))

a * b + c * d

(+ (* a b) (* c d) )

a * ( b + c)

(* a (+ b c) )

 

Na początku, szczególnie w skomplikowanych wyrażeniach, może to być mylące, ale odrobina praktyki pozwoli nam na bezbłędne operowanie tym sposobem zapisu. Jednak co bardziej skomplikowane operacje zapisuje się dość prosto, a raczej w sposób równie skomplikowany co prostsze.

Lista może zawierać elementy będące listami. Nie ma żadnego ograniczenia na skomplikowanie i ilość zagnieżdżeń list. Jedynym ograniczeniem jest to – by lista nie zawierała samej siebie. Lista nie może zawierać struktur rekurencyjnych. Co nie znaczy, że struktury danych nie mogą być podobne, ale o to by nie występowały w liście pętle.

Funkcja jest także listą zawierającą 3 elementy:

1.        Nazwę funkcji

2.        Listę parametrów

3.        formę (wyrażenie) które funkcja zwraca.

Funkcja może jedynie zawierać jedną formę, i wynik jej obliczania jest jednocześnie wynikiem działania funkcji. Przy wywoływaniu funkcji – wartości przekazywane jako parametry do funkcji, są skojarzane z nazwami parametrów na liście, a następnie obliczana jest wartość formy. Funkcje tworzymy funkcją defun przyjmującą jako argumenty: nazwę funkcji, listę parametrów i formę służącą  do obliczania jaj wartości.

Lista asocjacji

Wszystkie symbole dostępne w programie znajdują się na liście asocjacji[2]. Lista ta zawiera listę par: nazwa-wartość, gdzie nazwa jest dowolnym atomem, natomiast wartość – dowolną wartością: atomem, listą, daną nie listową, lub funkcją.

Wszystkie skojarzenia nazwy z wartością są dopisywane na początku tej listy. Wartości parametrów funkcji są również wartościowane, i dopisywane na początku tej listy, a przy opuszczaniu funkcji, są usuwane. W ten sposób nie ma problemu z wartościami lokalnymi wewnątrz funkcji i nie ma problemu z implementacją interpretera Lispu – w samym Lispie.

Przykładowa lista asocjacji zawierająca dwie zmienne: a=5 i b=(a b (x . y) c) i funkcję silnia wygląda tak:

( (silnia (lambda ( (x) (if (< x 2) 1 (* x (silnia (- x 1))))))) ( a 5) (b (a b (x . y) c) )

Odpowiednik w zapisie pudełkowym może być, przy odrobinie inwencji, nieco bardziej czytelny:

Słowo lambda jest (przynajmniej w starszych implementacjach Lispu) określeniem funkcji.

Jak widać, nawet najprostsze postacie listy asocjacji są na tyle skomplikowane, że trudno nimi operować. W Lispie, będziemy musieli się przyzwyczaić, do pracy na fragmentach list i do fragmentacji zadań w naszym programie. Z jednej strony będzie to ciekawe ćwiczenie, z drugiej – nauczymy się dbać o porządek w kodzie programu i nie pisać zbyt skomplikowanych funkcji.

Programy pisane w języku Lisp może nie są tak nieczytelne jak te w języku FORTH, ale niewiele im do nich brakuje.

Funkcje i makra

W języku Lisp, możemy definiować zarówno funkcje jak i makra. Różnice między nimi są niewielkie ale istotne:

1.        W przypadku wywołania funkcji – wszystkie wartości wszystkich jej argumentów są obliczane przed wywołaniem funkcji. Wartości argumentów są liczone (wartościowane) tylko raz.

2.        W przypadku makra – wartości argumentów są obliczane w trakcie ich użycia – a więc dopiero wtedy gdy staramy się coś z nimi zrobić. Wartości przy nieumiejętnie i nie efektywnie pisanym kodzie – mogą być liczone wielokrotnie.

Przykładami funkcji są funkcje matematyczne, operatory arytmetyczne – czyli wszystkie takie funkcje które do policzenia wartości potrzebują znać wszystkie wartości swoich parametrów. Makra są użyteczne wszędzie tam, gdzie nie trzeba liczyć wszystkich argumentów, żeby otrzymać wartość – na przykład przy liczeniu wartości funkcji and – wystarczy znaleźć pierwszy argument o wartości nil by wynikiem było nil. Podobnie, dla funkcji or, wystarczy znaleźć pierwszą wartość różną od nil by być pewnym, że wynik jest t.

Funkcje podstawowe

W Lispie funkcje tworzone są przez superpozycję innych funkcji. Muszą jednak istnieć funkcje pierwotne, z których możemy tworzyć inne funkcje, aż do momentu kiedy całą funkcjonalność programu umieścimy w jednej funkcji. W języku Lisp – kilka bardzo prostych funkcji tworzy zestaw pozwalający na pisanie programów. W różnych nutacjach tego języka podawane są różne zestawy tych funkcji. W niniejszym skrypcie, chciałbym wybrać takie, które stanowią podstawowy zestaw, ale zostały zaimplementowane w języku  CLisp:

car

Funkcja zwracająca pierwszy element pary która została podana jako argument. Dla argumentu który nie jest parą, funkcja nie jest określona, czyli program po prostu zatrzymuje się wyświetlając informację o napotkanym błędzie. Dla listy funkcja ta zwraca głowę listy – czyli jej pierwszy element.

a := (a b c d)

(car a) -> a

cdr

Funkcja zwraca drugi element pary podanej jako argument. Podobnie jak car, dla argumentu który nie jest parą, funkcja kończy swoje działanie – błędem. Dla argumentu listowego, funkcja zwraca ogon listy, czyli listę która została przekazana jako argument, po obcięciu z niej pierwszego elementu.

a := (a b c d)

(car a) -> (b c d)

Wielokrotne wywołanie funkcji car i cdr może być zastąpione funkcją której pierwsza litera to ‘c’, ostatnia ‘r’, a w środku znajduje się ciąg liter ‘a’ i ‘d’. Funkcja taka jest wielokrotnym złożeniem funkcji car i cdr.

(caadr x) = (car (car (cdr x)))

Taki rodzaj zapisu ułatwia dostęp do elementów listy, jednocześnie nie komplikując zapisu

cons

Funkcja tworząca parę z podanych argumentów. Funkcja ta pozwala na generowanie dowolnie skomplikowanych struktur danych.

a := (a b)

b := x

(cons a b) -> ( (a b) . x)

(cons b nil) -> (x)

Dla przykładu możemy z przy użyci funkcji cons budować listę jednoelementową z podanego argumentu:

(defun list1 (x) (cons x nil) )

(list1 b) -> (x)

(list1 a) -> ((a b))

atom

Funkcja atom sprawdza czy jej argument jest daną atomową czy też daną o nieco bardziej skomplikowanej strukturze. Jeśli argument jest atomem, funkcja zwraca atom t, jeśli argument nie jest atomem, funkcja zwraca atom nil.

a := (a b)

b := x

(atom a) -> nil

(atom b) -> t

eq

funkcja przyjmująca dwa parametry. Wartości obu parametrów muszą być atomami. Jeśli są one równe – to funkcja zwraca atom t, jeśli są różne – atom nil. Forma ta służy do porównywania wartości. Korzystając z tej formy, możemy napisać funkcję porównującą dowolnie złożoną daną języka Lisp.

a := (a b)

b := b

(eq a b) -> nil

(eq a (quote (a b)) -> błąd

(eq b (quote b) ) -> t

(eq b (cdr (car b))) -> t

if

Forma warunkowa. Forma ta przyjmuje trzy parametry. Jej konstrukcja jest podobna do operatora ? z języka C++ - przyjmuje ona trzy parametry. Jeśli wartość pierwszego parametru jest różna od nil – wartościowana i zwracana jest forma będąca drugim parametrem. Jeśli wartość pierwszego parametru jest nil – to wartościowana i zwracana jest trzecia forma.

W niektórych implementacjach Lispu podstawową funkcją jest nie if ale cond, która przyjmuje jako parametr listę par. Jeśli pierwszy element pary jest różny od nil to zwracana jest wartość drugiego elementu pary Jeśli nie – to powtarzamy operację dla następnej pary.

Funkcję if daje się zapisać poprzez funkcję cond i odwrotnie.

a := (a b)

b := b

(if t a b) -> (a b)

(if nil a b) -> b

defun

Funkcja ta pozwala na definiowanie nowych funkcji. Funkcja przyjmuje trzy parametry:

1.        Nazwę funkcji – nazwa musi być atomem. Nazwa nie jest wartościowana, nie może więc być umieszczona w zmiennej.

2.        Listę parametrów – listę nazw parametrów lokalnych, czyli nazw z jakimi zostaną skojarzone wartości parametrów funkcji w chwili jej wywołania (wartościowania). Również tu, nazwy te nie są wartościowane.

3.        Formę będącą wynikiem funkcji – formę której wartość będzie zwracana jako wynik dziania funkcji.

Wynikiem działania tej  jest dopisanie do listy asocjacji nowej funkcji. W starszych wersjach Lispa funkcję definiujemy przy użyciu słowa kluczowego lambda, które pozwala na zdefiniowanie nienazwanej funkcji, poprzez podanie jedynie listy parametrów i formy która pozwala na obliczenie wartości funkcji. Aby takiej funkcji nadać wartość – trzeba buło użyć funkcji define, której pierwszym parametrem jest nazwa funkcji, a drugim – funkcja zdefiniowana funkcją lambda.

(defun porownaj (a b)

    (if (atom a)

        (if (atom b)

            (eq a b)

            nil

        )

        (if (atom b)

            nil

            (if (porownaj (car a) (car b))

                (porownaj (cdr a) (cdr b))

                nil

            )

        )

    )

)

Przedstawiona tu funkcja porównuje czy wartości podane jako parametry są równe, zachowując się tak jak funkcja eq, ale zwracająca poprawne wartości dla dowolnych wartości parametrów.

Wartościowanie

Każdy atom, czy lista jaką przekażemy interpreterowi jest wartościowana. Jeśli wywołamy funkcję sinus pisząc:

(sin a)

 

To symbol sin zostanie potraktowany jak nazwa funkcji i interpreter odszuka tą funkcję i znajdzie sposób wyznaczania jej wartości, następnie spróbuje odszukać wartość o nazwie a. W przypadku funkcji których argumenty muszą być liczbami – nie ma z tym problemu. Nazwy traktowane jak nazwy zmiennych nie są niczym zaskakującym. Ale jeśli parametrem ma być tekst? Jeśli chcemy przekazać jako argument po prostu literę „a” ?

Jeśli napiszemy ją w cudzysłowach – to będzie ona tekstem, i jej wartością będzie litera „a” – ale również w cudzysłowach. Po prostu będzie to wtedy tekst, który podobnie jak liczby oraz wartości t i nil przedstawiają zawsze same siebie. To tak jakby istniała zmienna o nazwie t mająca wartość t.

Jeśli chcemy przekazać nie wartość – ale symbol – to musimy użyć słowa kluczowego quote:

 

(quote a) -> A

 

Można również użyć postaci skróconej: - pojedynczego apostrofu:

 

‘a -> A

 

Zarówno quote jak i pojedynczy apostrof – mogą spowodować nie wartościowanie bardziej złożonych struktur, takich jak listy. O ile ujęcie takiej listy w cudzysłowy – zrobi z niej pojedynczy tekst – to użycie apostrofu lub quote – zachowa strukturę listy, chroniąc nas przed jej wartościowaniem.

 

(quote (a b c) )      -> (A B C)

‘(a b c)              -> (A B C)

 

Przy cytowaniu małe litery zamieniane są na ich wielkie odpowiedniki. W języku LISP małe i wielkie litery nie są rozróżniane, a zwyczajowo małymi literami oznacza się nazwy wartości, natomiast wielkimi – same wartości.

eval

Wartościowanie jest wykonywane funkcją eval – która zachowuje się dokładnie tak jak interpreter języka Lisp – wartościuje formę która jest przekazana jako argument. Przykład prostej funkcji eval znajduje się w jednym przedostatnim paragrafie części poświęconej językowi Lisp.

Definiowanie funkcji i makr

Funkcje jak już wspominaliśmy, definiujemy makra defun. Przyjmuje ona 3 argumenty – nazwę funkcji, listę argumentów oraz ciało funkcji. Lista argumentów może zawierać, oprócz nazw parametrów lokalnych, słowa kluczowe, które pozwalają na dodatkową interpretację argumentów. Obowiązują one od miejsca w którym wystąpią – do końca listy argumentów. Słowa te pozwalają na:

&rest

Przypisanie do symbolu całej reszty argumentów w postaci listy. Jeśli zadeklarujemy funkcję

 (defun and (a &rest r) ( ... ) )

To funkcja ta może zostać zawołana z jednym lub wieloma argumentami. Przy wywołaniu tak zadeklarowanej funkcji and z czterema argumentami – pierwszy będzie dostępny jako symbol a, zaś kolejne trzy argumenty będą dostępne jako lista – nazwana r.

Używając &rest – bardzo łatwo napisać funkcję tworzącą listę:

(defun list (&rest l) l)

&optional

Oznacza, że następujące po nim argumenty są opcjonalne. Dla argumentów opcjonalnych możemy określić – jakie wartości będą im przypisane gdy argument nie zostanie przekazany. Dla wartości domyślnych – zamiast nazwy parametru – podajemy listę zawierającą 2 elementy: nazwę parametru oraz wartość która zostanie nadana argumentowi, wtedy gdy nie zostanie przekazany przy wywołaniu funkcji.

&key

Pozwala na określenie nazwanych argumentów. Argumenty nazwane nie muszą w wywołaniu funkcji być podawane w takiej kolejności jak w definicji funkcji. Ale oczywiście mogą. Pozwala to na budowanie funkcji z argumentami domyślnymi, które mogą być opuszczane, przy określaniu wartości argumentów które stoją za nimi. Trochę to skomplikowane, ale pozwala na, na prawdę niezłe kombinowanie z argumentami funkcji.

Przy wywoływaniu funkcji – przed argumentem możemy określić nazwę argumentu który określamy:

(defun f (&key x y (z 12)) (list x y z))

(f 1 2 3) -> (1 2 3)

(f :y 5) -> (nil 5 12)

(f :z 1 :y 2 :x 3) -> (3 2 1)

Podobnie jak w przypadku parametrów &optional – można tu podać zamiast nazwy parametru listę zawierającą dwa elementy – nazwę argumentu oraz wartość domyślną która zostanie użyta jeśli wartość parametru nie jest określona.

&aux

W zasadzie nie odnosi się do parametrów funkcji, ale pozwala na budowę pseudoparametrów, których wartości są określone podobnie jak w przypadku &key i &optional. Parametrów określonych po słowie &aux nie można podawać przy wywołaniu funkcji, jednak w ciele funkcji są one dostępne – tak jak inne argumenty funkcji.

Makra

Makra definiujemy podobnie jak funkcje. Możemy u definiować argumenty podobnie jak to mam miejsce w funkcjach – stosując takie same specyfikatory dla argumentów jak omówione powyżej, oraz dodatkowo &body, &whole i &enviroment. Oznaczające:

·         &body – podobnie jak &rest, ale bez wartościowania poszczególnych elementów listy. Na liście nie może wystąpić wspólnie z &rest.

·         &whole – do zaznaczenia, że wszystkie parametry mają być dostępne jako list o określonej nazwie. &whole musi być pierwszym elementem listy parametrów i może po nim wystąpić tylko jedna nazwa parametru.

·         &enviroment – pozwala na dostęp do środowiska (listy asocjacji) w której makro zostało zawołane. Można tu podać tylko jedną nazwę parametru.

Operatory

W języku Lisp, operacje arytmetyczne i relacje są takimi samymi funkcjami jak funkcje mające nazwy złożone z symboli operacji arytmetycznych lub logicznych. Większość operatorów potrafi działać na liście argumentów – inaczej niż to jest w tradycyjnych językach programowania. Pisząc symbol dodawania – możemy od razy zsumować całą listę wartości – wystarczy napisać:

(+ 10 4 2 1 6 3 1) -> 27

A nie jak w C++:

10+4+2+6+3+1 /*co de facto oznacza*/  ((((10+4)+2)+6)+3)+1

operatory arytmetyczne

Operatory arytmetyczne są w zasadzie funkcjami, zachowującymi się jak normalne funkcje języka Lisp. W tym języku symbole mogą być elementami nazw podobnie jak litery i cyfry.

Podstawowe działania arytmetyczne są dostępne jako operatory – ale przyjmują one dowolną ilość argumentów. O ile w przypadku dodawania i mnożenia interpretacja listy argumentów jest oczywista – o tyle w przypadku odejmowania i dzielenia – dopiero po chwili zastanowienia zauważamy, że:

(/ 1 2 3 4 ) = 1 / 2 / 3 / 4

(- 1 2 3 4) = 1 – 2 – 3 – 4

Mamy więc dostępne operatory dodawania, odejmowania, mnożenia i dzielenia:

(+ 1 2 3) => 1 + 2 + 3

(* 1 2 3) => 1 * 2 * 3

(– 1 2 3) => (1 – 2 ) – 3

(/ 1 2 3) => (1 / 2) / 3

operatory logiczne

Operatory logiczne działają na wartościach logicznych. W języku Lisp, nie ma specjalnego typu logicznego – zamiast tego dowolna wartość poza atomem nil jest traktowana jako wartość prawdziwa, natomiast atom nil – jako fałsz. Jeśli operator ma zwrócić wartość logiczną – to zwróci dla prawdy – atom t., dla fałszu – oczywiście atom nil.

W Lispie zaimplementowano podstawowe trzy operatory logiczne. Operator jednoargumentowy not oraz dwa makra wieloargumentowe and i or.  Operator not jest funkcją – jego argument jest wartościowany przy obliczaniu wartości operatora. Operatory and i or wartościowane są do momentu kiedy wynik operacji jest znany. Dla operatora and – do pierwszego argumentu którego wartością jest nil – wiadomo wtedy, że wynikiem jest nil.

Podobnie dla operatora or – argumenty wartościowane są do momentu gdy pojawi się jakakolwiek różna od nil. Wtedy od razy wiadomo, że wynik jest t.

(not ‘x) ->nil

(not ()) -> t

(and t t) -> t

(and ‘a 5 12.665 pi) -> t

(and ‘a nil (f x)) -> nil  ; (f x) nie będzie wartościowane

(or nil nil ‘a f(x)) -> t ; (f x) nie będzie wartościowane

operatory relacji

Operatory relacji znane z innych języków programowania, w języku Lisp mają trochę więcej zastosowań niż tylko porównywanie wartości. Każdy z operatorów relacji może przyjmować całą listę argumentów. Podobnie jak w innych językach mamy tu sześć operatorów relacji:

·         < - sprawdzający czy wartości przekazane jako argumenty są uporządkowane rosnąco

·         <= - sprawdzający czy wartości są uporządkowane nie malejąco

·         = - sprawdzający czy wszystkie wartości znajdujące się na liście argumentów są równe.

·         /= - trochę dziwny zapis operatora nierówności – wszystkie argumenty muszą mieć różne wartości

·         >= - wartości muszą być uszeregowane nie rosnąco

·         > - lista argumentów jest malejąca

Zauważmy jakie silne warunki są sprawdzane tymi operatorami relacji. Nie są potrzebne dodatkowe operacje na zapisanie warunku 0<= x <=1 który w C++ napisalibyśmy jako:

(0<=x) && (x<=1)

W języku lis wystarczy napisać:

(<= 0 x 1)

I wszystko jasne.

Ponadto zauważmy, że operatory relacji nie są już tak mocno ze sobą powiązane. W przypadku operatorów dwuargumentowych – jeśli argumenty nie były równe – to na pewno były różne. W przypadku większej liczby argumentów – zarówno = jaki i /= mogą być nieprawdziwe:

 

(= 1 1 0) -> nil    ; bo ostatnia wartość jest różna

                    od dwu pierwszych

(/= 1 1 0) -> nil   ; bo pierwsze dwie wartości są równe

 

Można nawet napisać taką listę argumentów dla której wszystkie relacje będą fałszywe.

Rekurencja

Dotychczas mówiliśmy jedynie o superpozycji funkcji. W takiej sytuacji nie ma możliwości wykonywania ciągu operacji – jedna po drugiej. Oczywiście można sobie coś takiego samodzielnie przygotować i napisać korzystając z wcześniej poznanych funkcji i makr. Dla Lispu, skonstruowanego jako narzędzie dla matematyków prowadzących obliczenia symboliczne, naturalnym sposobem pisania definicji funkcji jest definiowanie rekurencyjne. Jest to w pewnych sytuacjach znacznie prostsze niż pisanie programu który będzie coś liczył krok po kroku. Oczywiście rekurencja nie jest sposobem na wszystkie problemy i można przy jej pomocy zrobić na prawdę ciekawą głupotę, jednak rozwiązania iteracyjne też nie są doskonałe.

Typowym przypadkiem rekurencyjnego obliczania – jest liczenia wartości funkcji silnia. Można ją policzyć korzystając ze wzoru pozwalającego dość sprawnie liczyć funkcję silnia:

O ile silnia liczy się rekurencyjnie – dość dobrze, o tyle obliczanie wartości elementów ciągu Fibonacciego jest najmniej efektywnym sposobem na ich liczenie:

Tu z każdym krokiem rekurencji – musimy podwajać liczbę wywołanych rekurencyjnie funkcji, co nawet dla niewielkich wartości indeksu n prowadzi do bardzo złożonych obliczeń.

Jednak rekurencja może być silnym narzędziem we wprawnych rękach. Typowym problemem rekurencyjnym jest problem rozwiązania zagadnienia tak zwanej „Wieży Hanoi”, zabawki składająca się z kilku krążków o różnej średnicy i trzech miejsc na których krążki te można ustawiać.

Zadanie polega na przeniesieniu wszystkich krążków z pierwszego miejsca na ostatnie, przy czym nie wolno o kłaść krążka większego na mniejszy i nie wolno odkładać krążków w inne miejsca niż na stosy stojące w jednym z trzech wyznaczonych miejsc.

Iteracyjne rozwiązanie tego zagadnienia jest trudne. Ale jeśli spróbujemy zastosować indukcję matematyczną – problem staje się trywialny:

1.        Załóżmy, że mamy n krążków przenieś ć z miejsca A do C, korzystając jedynie z miejsca B jako pomocniczego

2.        Złóżmy, ze umiemy przenieść n-1 krążków z miejsca A na B korzystając z C. Wtedy przenosimy n-1 z A na B, następnie n-ty – największy krążek z A na C, a następnie przenosimy n-1 z B na C

3.        Ale jak przenieść n-1 krążków? To proste: przenosimy n-2 z A na C, następnie n-1-szy z A na B a potem n-1 z C na B. Zauważmy, że za każdym razem – największy krążek zawsze trafia na spód i nie przeszkadza w manipulacjach.

4.        Operacje przeprowadzamy tak długo, aż będziemy musieli przenieść jedne krążek – a to potrafimy zrobić.

Każdy problem daje się rozwiązać zarówno w sposób iteracyjny jak i rekurencyjny, ale zazwyczaj jedna z tych metod jest dla rozwiązania naturalna a inna – nie. Spróbujmy napisać rekurencyjną funkcję która zwróci  ilość elementów znajdujących się na podanej liście:

 

(defun liczlen (a)

  (if (equal a nil)

    0

    (+ 1 (liczlen (cdr a) ) )

  )

)

 

Ciekawym ćwiczeniem byłoby napisanie funkcji która zwraca listę zawierającą stany stosów krążków w poszczególnych krokach.

Funkcje sterujące

Funkcje sterujące warunkowym wykonaniem procesu wartościowania pozwalają na wartościowanie pewnych form, w  zależności od wartości innych. Na początku nauki programowania w Lispie – zapomnijmy o innych ciekawych sposobach na zmianę metody wykonywania programu poza formami warunkowymi.

Jedną formę warunkową jaką poznaliśmy jest forma if. Innymi formami pozwalającymi na wartościowanie warunkowe są formy and oraz or. Zauważmy, że formy te wartościują swoje argumenty: and – tak długo jak długo formy są różne od nil. W przypadku or – dopóki są równe nil.

Inne formy dają się wyrazić przez formę if, ale ich użycie może znacznie uprościć program.

when

Forma when ma postać:

 

(when warunek forma1 forma2 ...)

 

Pozwala ona na wartościowanie ciągu form jeśli spełniony jest warunek. Funkcja wymaga podania co najmniej dwóch parametrów – warunku który jest sprawdzany, oraz formy której wartość będzie zwrócona jeśli warunek jest spełniony. Jeśli nie jest spełniony – zwracana jest wartość nil. Jeśli podano więcej niż dwa parametry, kolejne są wartościowane sekwencyjnie a wynikiem jest wartość ostatniej formy. Funkcja ta nie powinna być używana gdy zwracana wartość jest potrzebna. W takim wypadku bezpieczniej jest używać funkcji if.

Funkcja when może być zapisana przy użyciu form if oraz prog:

 

(defmacro when (a &rest c)

      (if a   (prog c)

              nil

      )

)

unless

Funkcja unless ma postać:

 

(unless warunek forma1 forma2 ...)

 

Forma ta wartościuje formy będące argumentami, jeśli warunek nie jest spełniony. W zasadzie jest to po prostu zaprzeczenie funkcji when.

cond

Forma cond pozwala na implementowanie nawet bardzo skomplikowanych warunków. Forma powala na sprawdzenie wielu warunków, przy czym spełnienie pierwszego z nich – kończy wartościowanie formy. Konstrukcja taka znana jest z C++ jako if ... else if ... else if ... .

Cond ma postać:

 

(cond (warunek1 forma11 forma12 ...)

      (warunek2 forma21 forma22 ...)

      ... )

 

Forma wartościuje warunek i jeśli jego wartość jest różna od nil – wartościowane są formy następujące po tym warunku i wartościowanie formy się kończy. Jeśli warunek nie jest spełniony – sprawdzany jest kolejny warunek. Cond można zapisać przez funkcję if:

 

(defmacro cond (l &rest r)

      (if (car l)

              (prog (cdr l)

              (cond (car r) (cdr r)

      )

)

 

Natomiast funkcję if można zapisać przez cond:

 

(defmacro if (w then else)

      (cond   (w then)

              (t else)

      )

)

 

UWAGA: Forma cond nie jest określona (jej działanie kończy się błędem) jeśli żaden warunek nie będzie spełniony. Dlatego dobrze kończyć listę list warunków listą (t nil), zwracającą nil – gdy żaden warunek nie jest spełniony.

case

Najbardziej skomplikowaną instrukcją warunkową jest forma case. Przypomina ona instrukcję case z języka C++, czy też innych języków w których programujemy proceduralnie. Case ma formę:

 

(case wyrazenie

      (listaWartości1 forma11 forma12 ...)

      (listaWartości2 forma21 forma22 ...)

      ...

)

 

Przy wartościowaniu tej formy, wartościowane jest wyrażenie, którego wartość jest porównywana z wartościami znajdującymi się na liście wartości. Elementy tej listy nie są wartościowane – ale traktowane tka jakby były umieszczone w formie quote. Jeśli lista wartości zawiera jeden element – nie musi być on zapisany jako lista jednoargumentowa, ale jako pojedyncza dana. Jeśli porównanie wypadnie pozytywnie – to wartościowane są wszystkie formy na liście które jest stowarzyszona z porównywaną wartością.

a := 2

(case a ((1 2 3) (* 2 a)) (4 12)) -> 4

do

Forma do pozwala na wykonywanie pętli. Funkcjonalnie odpowiada ona instrukcji for z języka C++, ale pozwala na użycie wielu zmiennych kontrolnych. Forma ta ma postać:

 

(do ( (zmienna1 wartoscPoczątkowa1 krok1)

      (zmienna2 wartoscPoczątkowa2 krok2)

      ... )

    (warunek)

      forma1

      forma2

      ...

)

 

Formy forma1, forma2, ... wykonywane są w pętli, przy zmiennych zadeklarowanych na początku pętli zmieniających się od zadanych wartości początkowych, tak długo jak długo warunek jest spełniony. Po każdym obiegu pętli, wartość zmiennej jest przeliczana przez wyrażenie określone tu jako krok.

Jeśli zadeklarowano więcej niż jedną zmienną – wszystkie zmienne są przeliczane w pojedynczym kroku pętli. Nie jest to więc pętla wielokrotna czy zagnieżdżona.

Sekwencyjne wykonywanie instrukcji

Lisp to listy, oraz superpozycje funkcji. Ale niestety programiści przyzwyczajają się do sekwencyjnego wykonywania instrukcji i bardzo trudno im to wybić z głowy. Matematyczna konstrukcja wyrażeń w języku Lisp, jest bardzo elegancka, ale przydałaby się możliwość pisania programów w sposób tradycyjny – jako ciągu instrukcji wykonywanych jedna po drugiej.

prog1, prog2, progn

Najprostszymi formami które pozawalają na sekwencyjne wartościowanie form są formy prog1, prog2, i progn. W konstrukcji:

 

(progn forma1 forma2 forma3 ... formai)

 

Formy wartościowane są jedna po drugiej a ich wartości są zapominane, gdy tylko kolejna forma będzie wartościowana. Formę taką łatwo napisać jako makrodefinicję:

 

(defmacro progn (&rest l) (prognx nil l ) )

(defun prognx (result rest)

      (if rest

              (prognx (eval (car rest)) (cdr rest))

              result

      )

)

 

Konstrukcja wydaje się oczywista. Do napisanie funkcji, posłużyliśmy się jedna funkcją pośrednią – która wylicza wartościuje poszczególne formy, przygotowując wynik do zwrócenia – przekazując go do kolejnej rekurencji. Proste i po Lispowemu.

Funkcja prog1 zachowuje się tak samo jak progn, ale zwraca nie wynik ostatniego, ale pierwszego wartościowania. Wszystkie formy są wartościowane, ale zwracana jest wartość pierwszej z nich. Podobnie makro prog2 zwraca wartość drugiej formy z listy argumentów. Obie makrodefinicje łatwo napisać używając zmiennych tymczasowych, ale jak to zrobić korzystając wyłącznie z superpozycji funkcji? Podobnie jak w poprzednim przypadku użyjemy funkcji pośredniej dla której przygotowujemy parametry we właściwej funkcji. Konstrukcja jest to trochę zakręcona, ale myślę, że nie czytelnik nie powinien mieć dużych problemów z jej rozszyfrowaniem:

 

(defmacro prog1 (optional& (a nil) &rest l) (prog1x a nil l) )

(defun prog1x (wynik x rest)

      (if rest

              (prog1x wynik (eval (car rest)) (cdr rest))

              wynik

      )

)

 

(defmacro prog2 (&optional (a nil) (b nil) &rest l)

      (progn a (prog1x b nil l))

)

let

Forma let pozwala na określanie zmiennych lokalnych dla ciągu form wartościowanych sekwencyjnie. Powoli Lisp zaczyna wyglądać jak C++ pozwalając na definiowanie form wyglądających jak typowy zakres  { ... }”. Forma let ma postać:

 

(let ( (zmienna1 wartość1)

      (zmienna2 wartość2)

      ...)

      forma1

      forma2

      ...

)

 

Forma ta zachowuje się tak samo jak forma progn jeśli chodzi o wartościowanie form składających się na jej ciało. Przedtem jednak wartościowane są wszystkie formy określające wartości, a następnie są przypisywane do zmiennych o zadeklarowanych nazwach. Zmienne te są lokalne w formie let – to znaczy, że po wyjściu z tej formy – wszystkie te zmienne są niszczone a pamięć 0 zwalniana.

O ile wartościowanie form tworzących ciało formy let – są wartościowane po kolei – o tyle wartości zmiennych – nie musza być wartościowane kolejno a ponadto, wartości same zmienne nie są dostępne zanim nie zakończy się definiowanie wszystkich zmiennych lokalnych.

Aby móc obliczać wartości definiowane lokalnie – należy użyć funkcji let*. Ma ona taką samą składnię, ale wszystkie zmienne są deklarowane sekwencyjnie – jedno po drugim.

Jeśli pominiemy wartość przy deklarowaniu zmiennej – to zmienna jest inicjowana z wartością nil. Pamiętajmy: w języku Lisp nie ma takiego pojęcia jak zmienne która nie ma wartości. Albo zmienna nie jest zadeklarowana, czyli nie może być wartościowana, albo ma wartość.

Jak zmieniać wartości zmiennych – dowiemy się przy okazji omawiania innych ciekawych funkcji.

tagbody

Forma tagbody pozwala na sekwencyjne przetwarzanie jej form składowych, podobnie jak formy prog1, prog2 i progn, ale zawsze zwraca wartość nil. Ponadto wewnątrz formy tagbody mogą występować, poza formami do wartościowania – także etykiety określające miejsca do których można skoczyć instrukcją (formą) go. Etykiety nie są w żaden konkretny sposób oznaczone nie ma tu deklaracji etykiet czy wyróżniania ich jakimś specjalnym znakiem (jak np. w C++ - etykiety zawsze kończą się dwukropkiem).

Ty zasada jest prosta – jeśli element formy tagbody jest listą – to jest wartościowany. Jeśli jest atomem – to jest traktowany jak etykieta.

Instrukcja skoku ma format:

 

(go etykieta)

 

Forma tagbody ma postać:

 

(tagbody

      forma1

      forma2

      ...

      etykieta1

      ...

      formai

      ...

      etykietan

      ...

)

prog

Forma prog jest połączeniem form let i tagbody. Jej składnie jest taka sama jak formy let jednak w ciele formy – można yzywać etykiet oraz instrukcji skoku. Podobnie jak w przypadku formy let zmienne lokalne nie są wartościowane i definiowane sekwencyjnie. Aby wymusić sekwencyjne definiowanie zmiennych lokalnych – należy użyć formy prog*.

Forma prog ma postać:

 

(porg ( (zmienna1 wartość1)

      (zmienna2 wartość2)

      ...)

      forma1

      forma2

      ...

      etykieta1

      ...

      formai

      ...

      etykietan

      ...

)

Inne ciekawe funkcje implementacji Lisp

Liczba funkcji konkretnej implementacji języka Lisp może być bardzo duża. Funkcje te mają często po kilkanaście wariantów, lub pozwalają na dość dziwne specyfikacje argumentów jako funkcji, słów kluczowych itp. Poniżej chciałbym pokazać kilka-kilkanaście użytecznych funkcji jakie możemy znaleźć w większości implementacji.

W przykładach założymy, że:

a := (1 2 3)

b := ‘B

c := ()

d := ‘(x y z)

e := (30 . (1 . 1) )

f := (1 2 3 4 5 6 7 8 9 0)

Posłużymy się tu także z nieco bardziej złożonym przekazywanie argumentów. Oprócz argumentów które są wartościowane oraz takich które są traktowane dosłownie (występuje przed nimi pojedynczy apostrof, lub są argumentem formy quote) – poznamy jeszcze jedną – wartościowanie nazwy funkcji. Normalnie jeśli podamy nazwę punkcji – interpreter będzie próbował ją obliczyć. A co zrobić jeśli chcemy przekazać, jako argument, nie wartość funkcji – ale samą funkcję? W takim wypadku użyjemy znaku # - by określić, że chodzi nam o wartość która jest ciałem funkcji o podanej nazwie.

Konstrukcja #’funkcja – oznacza po prostu ciało funkcji której nazwą jest ‘funkcja’.

Po tych wyjaśnieniach zobaczmy kilka przykładów funkcji:

Funkcje testujące

Funkcje testujące mają nazwy kończące się literą „p”. Początek nazwy funkcji – określa co jest sprawdzane.

·         (endp dana) – funkcja zwraca wartość t jeśli dana przekazana jako argument jest pustą listą, oraz nil jeśli jest jakąkolwiek daną różną od pustej listy. Funkcja bardzo przydatna gdy chcemy sprawdzić, czy zakończyliśmy już przeglądanie listy dochodząc do jej końca. Można w tym celu używać także funkcji
(if ( and (atom dana) (eq dana nil)) t nil), ale (endp dana) wygląda nieco prościej.

(endp a) -> nil

(endp b) -> nil

(endp c) -> t

·         (consp dana) – funkcja sprawdzająca czy wartość podana jako dana jest parą. Jeśli nie wprowadzamy do naszych programów innych typów danych niż atomy i pary[3] - to consp jest równoważne (not (atom ... )).

(consp a) -> t

(consp b) -> nil

(consp c) -> nil

·         (listp dana) – funkcja sprawdzająca czy dana jest listą. To znaczy – czy jest ciągiem par w którym ostatnim elementem jest para której drugim elementem jest nil. Ponadto funkcja ta zwraca t przy przekazaniu atomu nil jako argumentu. Pamiętajmy że atom nil odpowiada liście pustej.

(listp a) -> t

(listp b) -> nil

(listp c) -> t

(listp e) -> nil

·         (zerop dana) – funkcja sprawdzająca, czy podany argument ma wartość zero – bez względu na jego typ. Argument może być liczbą całkowitą, zmiennopozycyjną, ułamkową a nawet – zespoloną. Jeśli liczba to ma wartość zero – to wynikiem działania funkcji jest t, jeśli jest niezerowa – nil.

(zerop 0/12) -> t

(zerop 0.00001) -> nil

·         (numberp dana) (integerp dana) (rationalp dana) (floatp dana) (realp dana)  – funkcje sprawdzające typ podanego argumentu. Funkcje te zwracają wartość t jeśli argument jest odpowiednio typu – liczbowego (dowolnego podtypu typu liczbowego), całkowitego, ułamkowego, zmiennopozycyjnego i rzeczywistego.

(numberp ‘a) -> nil

(integerp 123) -> t

(rationalp 10) -> nil

·         (plusp dana) (minusp dana) (oddp dana) (evenp dana)  – funkcje sprawdzające czy przekazana dana jest odpowiednio dodatnia, ujemna, nieparzysta lub parzysta. Dwie ostatnie funkcje wymagają podania argumentu całkowitego.

(oddp 12) -> nil

(evenp 12356) -> t

(plusp 23) -> t

Funkcje operujące na listach

Język Lisp oferuje bardzo dużo funkcji pracujących na listach. Tu przedstawimy kilka najbardziej popularnych:

·         (list-length lista) – funkcja zwraca długość listy – ilość jej elementów.

(list-length ‘(a b c (d e) f)) -> 5

·         (nth numer lista) – funkcja zwracająca n-ty element podanej listy. Funkcja może służyć do swobodnego dostępu do listy, pozwalając na traktowanie jej jak normalnej tablicy. Funkcję taką bardzo łatwo zaimplementować samodzielnie, jednak jej wbudowana wersja jest znacznie bardziej efektywna.

(nth 2 b) -> Y

(nth 1 b) -> X

·         (first lista) – funkcja zwraca pierwszy element listy – działa tak samo jak car

·         (rest lista) – funkcja zwraca ogon listy – działając tak samo jak cdr, od której różni się nieco więcej znaczącą, i łatwiejszą do zapamiętania nazwą.

·         (nthcdr numer lista) – funkcja jest wielokrotnością funkcji cdr.

(nthcdr 1 f) -> (2 3 4 5 6 7 8 9 0)

(nthcdr 5 f) -> (6 7 8 9 0)

·         (last lista &optional (numer 1)) – funkcja zwracająca ostatni element lub elementy podanej listy. Jeśli określimy wyłącznie listę – to zwrócony zostanie ostatni element listy. Jeśli dodatkowo podamy liczbę – funkcja zwróci zadaną ilość elementów z końca listy.

(last f) -> 0

(last f 3) -> (8 9 0)

·         (list &rest elementy) - funkcja zwraca listę złożoną z wszystkich argumentów przekazanych do funkcji

(list a b c) -> ( (1 2 3) B () )

·         (concatenate &rest elementy) - funkcja zwraca listę która jest połączeniem wszystkich list i atomów podanych jako argumenty tej funkcji, sklejając je w jedną listę.

(concatenate a b c) -> (1 2 3 B)

·         (butlast lista &optional numer) – funkcja zwraca początek listy – listę nie zawierającą ostatniego, lub ostatnich elementów listy.

(butlast f) -> (1 2 3 4 5 6 7 8 9)

(butlast f 4) -> (1 2 3 4 5 6)

Modyfikacja wartości

·         (setq nazwa wartosc) – funkcja ustawiająca wartość zmiennej na liście asocjacji. Funkcja ta modyfikuje lub tworzy wartość globalną, dostępną z każdego miejsca programu. Nazwa zmiennej nie jest wartościowana, zachowuje się ona jak zapisana wewnątrz formy quote. Nazwa określa nazwę zmiennej, wartość – jest dowolną formą o dowolnej wartości dowolnego typu. Jeśli wartość jest wyrażeniem – to jest ono obliczane w momencie przypisywania. Jeśli nie chcemy wartościowania – musimy zamknąć wartość wewnątrz formy quote.

(setq x 12)           x -> 12

(setq x ‘(a b c))     x -> (A B C)

(setq x f)            x -> (1 2 3 4 5 6 7 8 9 0)

·         (rplaca x y) – funkcja ta, podobnie jak funkcja replacd, może być użyta do modyfikacji istniejących struktur listowych. Funkcja ta wymienia w istniejącej liście głowę listy na swój drugi argument.

(setq x ‘(a b c))     x -> (A B C)

(rplaca x 12)         x -> (12 B C)

·         (rpalcd x y) – funkcja pozwalająca na wymianę ogona podanej listy na wartość podaną jako drugi argument.

(rplacd x ‘V)         x -> (12 V)

Operacje matematyczne

·         (floor num) (ceiling num) (truncate num) (round num) – funkcje konwertujące liczby do liczb całkowitych zwracające odpowiednio: największą liczbę całkowitą, nie większą nie niż podana; najmniejszą nie mniejszą, liczbę po obcięciu części ułamkowej oraz zaokrągloną do najbliższej liczby całkowitej.

num

Floor

ceiling

truncate

round

2.6

2

3

2

3

2.5

2

3

2

2

2.4

2

3

2

2

0.7

0

1

0

1

0.3

0

1

0

0

-0.3

-1

0

0

0

-0.7

-1

0

0

-1

-2.4

-3

-2

-2

-2

-2.5

-3

-2

-2

-2

-2.6

-3

-2

-2

-3

·         (abs x) – wartość bezwzględna liczby. Działa także dla argumentów zespolonych.

·         (phase z) – faza liczby zespolonej. Dla liczb rzeczywistych - 0

·         (signum x) – znak liczby. Ma sens tylko dla liczb rzeczywistych.

·         (sin phi) – sinus kąta

·         (cos phi) – kosinus kąta

·         (tan phi) – tangens kąta

·         (cis phi) – cosinus i sinus tego samego kąta zapisany jako liczba zespolona której część rzeczywista ma wartość kosinusa, a urojona - sinusa

·         (asin x) – arkus sinus – wartość kąta którego sinus wynosi x. Funkcja odwrotna do funkcji sinus.

·         (acos x) – arkus kosinus – funkcja odwrotna do funkcji sinus.

·         (atan y &optional x) – arkus tangens. Funkcja odwrotna do tangensa. Jeśli podano jeden argument – to wynik jest wartością funkcji arkus tangens tej wartości. Jeśli podano dwa – to ich ilorazu.

·         (sinh n) (cosh n) (tanh n) – sinus, kosinus i tangens hiperboliczny

·         (asinh x) (acosh x) (atanh x) – funkcje odwrotne do funkcji hiperbolicznych

·         (exp x) – funkcja ekspotencjalna ex.

·         (expt x y) – funkcja ekspotencjalna xy.

·         (log num &optional podstawa) – logarytm o zadanej podstawie. Jeśli nie określono podstawy – logarytm jest logarytmem naturalnym.

·         (sqrt x) – pierwiastek kwadratowy z zadanej liczby. Wynik może być zespolony o ile to konieczne.

·         (isqrt x) – całkowity pierwiastek z zadanej liczby. Można oczywiście policzyć (floor (sqr x)), ale isqr jest znacznie szybsze.

Inne operacje na listach

·         (subst wstaw znajdz lista &key test test-not) – funkcja zamieniająca wszystkie wystąpienia wskazanego elementu znajdz na element wstaw w zadanej liście. Lista jest przeszukiwana jak drzewo – jeśli zawiera podlisty – to są one również przeszukiwane. Dodatkowe parametry kluczowe test oraz test-not pozwalają na zadanie funkcji użytej do porównywania.

(subst 1 A ‘(A B (1 2 A C) A)) -> (1 B (1 2 1 C) 1)

·         (adjoin element lista &key test test-not) – funkcja dodająca element do listy pod warunkiem że element nie występuje na liście. Parametry kluczowe pozwalają na określenie funkcji służącej do porównywania.

(adjoin 1 ‘(1 2 3)) -> (1 2 3)

(adjoin 1 ‘(5 6 7)) -> (5 6 7 1)

·         (member element lista &key test test-not) – funkcja sprawdzająca czy element występuje na podanej liście

(member 1 ‘(1 2 3)) -> t

(member 1 ‘(5 6 7)) -> nil

·         (ldif lista podlista) – funkcja zwracająca różnicę list, jednak podlista musi być rzeczywistą podlistą a nie jedynie wyrażeniem z nią identycznym – podlista musi być którymś z cdr-ów listy z której będziemy ją odcinać.

g := (cdddr f)

h := (4 5 6 7 8 9 0) ; identyczna wartość jak g

(ldif f g) -> (1 2 3)

(ldif f h) -> (12 3 4 5 6 7 8 9 0)

·         (union lista1 lista2) – funkcja zwracająca wszystkie elementy znajdujące się na liście1 i liście2. Elementy powtarzające się występują na liście wynikowej tylko raz. Funkcja ta zachowuje się jak wielokrotne wywołanie funkcji adjoin. Również i tu można określić parametry kluczowe test i test-not.

(union ‘(1 2 3 4) ‘(3 6 7 2)) -> (1 2 3 4 6 7)

·         (intersection lista1 lista2) – funkcja zwracająca elementy występujące na obu listach podanych jako argumenty:

(intersection f ‘(4 6 8 12 443 2)) -> (2 4 6 8)

·         (fill lista wartosc &key start end) – funkcja pozwalająca na wypełnienie listy lub jej części zadaną wartością. Jeśli nie podano wartości start i end wypełniana jest cała lista Jeśli określono początek i koniec – wypełniane są tylko elementy o indeksach większych lub równych wartości początku i mniejszych od wartości końcowej. Funkcja ta zmienia listę przekazaną jej jako parametr. Elementy są numerowane od zera. Funkcja może działać na listach i tablicach.

(fill f ‘x)

x -> (X X X X X X X X X X)

(fill f ‘a :start 2 : end 3)

x -> (X X A X X X X X X X)

·         (replace zmienna wyrazenie &key start1 end1 start2 end2) – funkcja modyfikująca zmienną poprzez wstawienie w nią elementów podanego wyrażenia. Jeśli nie określono wartości początkowych i końcowych – to działa podobnie jak setq – podstawiając do zmiennej podane wyrażenie. Jeśli określimy w jakie miejsce należy kopiować – to wymieniony zostanie podany ciąg elementów. Jeśli podano jaki fragment wyrażenia należy przepisać – funkcja pozwoli na podstawienia pod wycinek listy – wycinka innej listy. Podobnie jak w funkcji fill – wartości początku i końca określają element początkowy oraz element za końcowym. Elementy listy numerowane są od zera.

(replace f ‘(A B C D))

f -> (A B C D)

(replace f ‘(1 2 3) :start1 0 :end1 2)

f -> (1 2 3 C D)

·         (remove element lista &key from-end, test test-not start end count) – funkcja pozwalająca na usuwanie elementów z listy. Przy wywołaniu funkcji możemy określić elementy jakiej wartości będą usuwane z listy. Poza określeniem wartości elementu o listy z której będzie wycinany, możemy określić dodatkowe opcje pozwalające na budowanie naprawdę złożonych poleceń.

·         count – pozwala na określenie ile elementów może zostać usuniętych.

·         from-end – działa wyłącznie z count pozwalając na wycięcie określonej liczby wystąpień elementu – ale poszukiwanie rozpoczyna się od końca listy, jeśli wartość tego parametru jest różna od nil.

·         test oraz test-not – pozwalają na zadanie warunku jaki mają spełniać elementy do usunięcia. Jeśli podamy przy wywołaniu funkcji remove wartość :test #’> - wszystkie elementy większe od zadanego – zostaną usunięte. Oczywiście z uwzględnieniem innych parametrów kluczowych. W przypadku test-not – elementy nie spełniające warunku będą usuwane. Jako warunek można podać nazwę dowolnej funkcji, ważne jest by przyjmowała dwa argumenty.

·         start, end – pozwalają na określenie w jakiej części listy elementy będą usuwane.

(remove 2 f) -> (1 3 4 5 6 7 8 9 0)

(remove 3 f :test #’<) -> (3 4 5 6 7 8 9 0)

Inne funkcje

·         (equal a b) – funkcja sprawdzająca czy podane parametry są równe. W odróżnieniu od funkcji eq oraz = powala ona na sprawdzanie dowolnie rozbudowanych struktur danych.

(equal e (cons 30  ‘(1 . 1) )) -> t

·         (find element lista &key from-end test test-not start end) – Funkcja znajdująca element na podanej liście i zwracająca go jako wartość którą możemy modyfikować. Zwracane jest pierwsze wystąpienie (lub ostatnie jeśli from-end na wartość różną od nil) elementu na liście. Parametry kluczowe mają takie same znaczenie jak w funkcji remove. Jeśli nie znaleziono elementu – zwracana jest wartość nil.

(find 3 f) -> 3

·         (mapcar funkcja lista &rest listy) – funkcja pozwalająca na obliczenie podanej funkcji dla listy argumentów. Wartością funkcji jest lista wartości funkcji. Jako parametry podajemy funkcję której wartości mają być liczone oraz tyle list, ile funkcja przyjmuje parametrów. Argumenty funkcji brane są jako kolejne elementy list:

(mapcar #’+ ‘(1 2 3 4 5) (3 3 2 1 6)) -> (4 5 5 5 11)

·         (apply funkcja &rest argumenty) – funkcja która liczy wartość funkcji której nazwa jest podana jako pierwszy parametr funkcji apply, na argumentach podanych jako reszta argumentów. Działa podobnie jak funkcja eval, jednak eval nie wartościuje nazwy funkcji. W funkcji apply nazwa funkcji może być zapisana w zmiennej.

x := ‘>=

(apply x 90 10 12) -> nil

·         (sort lista funkcja &key key) – funkcja sortująca listę. Ponieważ lista może mieć dowolną strukturę i funkcje porównujące dla różnych list mogą różnie wyglądać – jako drugi parametr podano funkcję porównującą elementy, która powinna zwracać wartość nil jeśli dwa elementy, przekazywane jej jako parametry nie są ułożone w dobrej kolejności. Ostatni parametr określa nazwę funkcji która pozwala na wyciągnięcie kluczy do porównywania z elementów listy. Jeśli nie jest ona podana – to jako elementy listy traktowane są jak klucze.

(sort ‘(4 5 6 2 9) #’<) -> (2 4 5 6 9)

·         (string<= a b) (string= a b) (string< a b) (string/= a b) (string>= a b) (string> a b) – operacje porównywania tekstów. Działają podobnie jak relacje <, <=, =, /=, >=. >, ale pozwalają na porównywanie napisów. Przyjmują jednak tylko dwa argumenty.

(string/= ”asd” ”xx”) -> t

(string< ”asd” ”xx”) -> t

(string> ”asd” ”xx”) -> nil

Inne typy danych implementacji Lisp

W czystym Lispie mamy do dyspozycji jedynie dane atomowe oraz pary. W nowoczesnych implementacjach Lispa – dodatkowe typy danych pozwalają na optymalizację obliczeń a nawet na włączenia typizacji do tego języka. Dowolną zmienną możemy zadeklarować zastępując ją listą złożoną z nazwy typu oraz nazwy zmiennej.

Poza typami podstawowymi możemy korzystać z

·         Liczby – Lisp oferuje cztery różne typy liczbowe:

·         Liczby całkowite – zapisane jako ciąg cyfr rozpoczynającymi się ewentualnie znakiem plus lub minus

·         Ułamki – dwie liczby całkowite rozdzielone znakiem łamania. Druga z nich powinna być bez znaku. Lisp potrafi traktować takie liczby jak dokładne wartości.

·         Wartości zmiennopozycyjne – zapisane z kropką i ewentualnym wykładnikiem po literze e.

·         Liczby zespolone – zapisane jako #C(r,i), gdzie r, i są liczbami zmiennopozycyjnymi

·         Tablice wartości. Zapisywane są podobnie jak listy – ale ich użycie jest znacznie bardziej efektywne jeśli chodzi o dostęp swobodny. Aby określić daną jako tablicę – należy nawiasy poprzedzić znakiem #: #(1 2 3)

·         Napisy – zachowują się podobnie jak dane atomowe, ale trudno z napisu zrobić nazwę zmiennej. Napisem jest dowolny ciąg znaków ujęty w cudzysłowy. Np. ”To jest napis”.

·         Tablice bitowe. Jeśli poprzedzimy ciąg zer i jedynej znakami #* - to mamy wektor bitów.

·         Tablice mieszające – pozwalają na budowę szybkich i efektywnych tablic symboli.

·         Struktury

Struktury są budowane przez odpowiednie makra które tworzą funkcje dostępu do poszczególnych elementów oraz cos w rodzaju konstruktora. Ale w głębi kodu – nadal jest to lista...

Ewaluator – czyli Lisp w Lispie

Jako jedno z ćwiczeń proponowałbym napisanie interpretera języka Lisp w Lispie. Może sprawiać to wrażenie masła maślanego, ale czym innym jest wykonywanie prostych operacji na listach, a czym innym wartościowanie form zawierających zmienne oraz obliczanie funkcji zdefiniowanych przez użytkownika, z przekazywaniem parametrów, parametrami lokalnymi itp.

Funkcja wartościująca musi działać w pewnym środowisku, w którym zdefiniowano wartości zmiennych. Wartością zmiennej może być także funkcja. Tu założymy, że pierwszy element listy będącej poleceniem jest funkcją. A jeśli nie jest funkcją wbudowaną – to jest funkcją zdefiniowaną przez użytkownika, a więc jej definicja znajduje się na liście asocjacji.

Na początek jednak – powinniśmy rozróżnić wartościowanie zmiennej od obliczania wyrażenia. Wyrażenie jest listą, zmienna – atomem. Napiszmy więc funkcję wartościującą, która wywoła  wartościowanie zmiennej lub wyrażenia. Zauważmy również, że atomy t i nil są swoją własną wartością:

 

; --------------------------------------------

; funkcja wartościująca podane wyrażenie

; w.g. wartości zapisanych w słoniku

; --------------------------------------------

(defun rozwiaz (forma slownik)

  (if (atom forma)

    (cond ((eq forma 't) t)

          ((eq forma 'nil) nil)

          ( t (zmienna forma slownik) ))

    (wyrazenie (car forma) (cdr forma) slownik)

  )

)

 

Funkcja ta dla argumentu będącego atomem – sprawdza czy nie jest to atom t lub nil, jeśli tak – od razu zwraca wartość. Jeśli jest innym atomem – woła funkcję poszukującą wartości zmiennej w słowniku. Jeśli podana forma jest listą – wołamy wartościowanie wyrażenia, ale od razu odcinamy głowę listy – która jest traktowana jako symbol operacji.

Wartościowanie zmiennych jest bardzo proste. Sprawdzamy po prostu czy głowa listy asocjacji (słownika) odpowiada poszukiwanej zmiennej. Jeśli tak – zwracamy jej wartość. Jeśli nie – wołamy funkcję tą samą funkcję dla słownika pozbawionego pierwszego elementu:

 

; --------------------------------------------

; funkcja poszukująca w słowniku

; wartości zadanej zmiennej

; --------------------------------------------

(defun zmienna (nazwa slownik)

  (if (eq nazwa (caar slownik))

    (cadar slownik)

    (zmienna nazwa (cdr slownik))

  )

)

 

Teraz musimy napisać interpretację wyrażeń. Dla prostych funkcji wbudowanych – nie ma nic prostszego – wartościujemy odpowiednie[4] elementy listy argumentów. Problemem są jedynie funkcja cons oraz funkcje definiowane przez użytkownika.

 

; --------------------------------------------

; funkcja wartościująca podane wyrażenie

; wszystkie funkcje wbudowane są tu liczone

; explicite

; --------------------------------------------

(defun wyrazenie (operacja argumenty slownik)

  (cond

    ( (eq operacja 'quote)

      (car argumenty) )

    ( (eq operacja 'car)

      (car (rozwiaz (car argumenty) slownik) ) )

    ( (eq operacja 'cdr)

      (cdr (rozwiaz (car argumenty) slownik) ) )

    ( (eq operacja 'atom)

      (atom (rozwiaz (car argumenty) slownik) ) )

    ( (eq operacja 'cons)

      (cons (rozwiaz (car argumenty) slownik)

            (rozwiaz (cadr argumenty) slownik) ) )

    ( (eq operacja 'eq)

      (eq (rozwiaz (car argumenty) slownik)

          (rozwiaz (cadr argumenty) slownik) ) )

    ( (eq operacja 'cond)

      (warunkowe argumenty slownik) )

    ( t

      (wolajfunkcje (zmienna operacja slownik)

                    argumenty slownik) )

  )

)

 

Zacznijmy od wartościowania wyrażenia warunkowego. Również tu łatwo poradzimy sobie korzystając z prostej rekurencji. Jeśli pierwszy element głowy listy argumentów ma wartość inna niż nil, zwracamy drugą wartość. Jeśli pierwszy element ma wartość nil – wartościujemy formę dla reszty elementów listy warunkowej:

 

; --------------------------------------------

; pomocnicza funkcja pozwalająca na warunkowe

; wartościowanie wyrażeń

; --------------------------------------------

(defun warunkowe (argumenty slownik)

  (cond

    (rozwiaz (caar argumenty) slownik)

      (rozwiaz (cadar argumenty) slownik)

    ( t

      (warunkowe (cdr argumenty) slownik) )

  )

)

 

Pozostaje najtrudniejsza część: wartościowanie funkcji zdefiniowanych na liście asocjacji. Dla uproszczenia nie będziemy się zajmowali makrodefinicjami, zakładając, że wystarczą nam funkcje. Myślę, że po chwili zastanowienia, uważny czytelnik będzie w stanie przerobić nasze funkcje tak – by działały wywoływania makrodefinicji.

Jeśli funkcję zapiszemy jako listę zawierającą dwa elementy:

1.        Listę nazw argumentów

2.        Formę która policzy wartość funkcji

Wystarczyłoby więc policzyć formę będącą ciałem funkcji, ale przy nieco zmienionej liście asocjacji – takiej do której doklejono asocjacje nazw argumentów i ich wartości przekazane do funkcji. Jeśli argumenty te dodamy na początek listy asocjacji – to przy okazji zaimplementujemy coś takiego jak przykrywanie nazw.

Wystarczy więc policzyć formę funkcji:

 

; --------------------------------------------

; funkcja pomocnicza wartościująca funkcje

; wartościuje ciało funkcji przy użyciu słownika

; rozszerzonego o parametry funkcji

; --------------------------------------------

(defun wolajfunkcje (funkcja argumenty slownik)

  (rozwiaz

    (cadr funkcja)

    (liczargumenty

      (car funkcja)

      argumenty

      slownik

      slownik) )

)

 

Pozostaje nam tylko napisanie, wspomnianej w powyższej funkcji, funkcji liczargumenty która rozbuduje słownik. Funkcję tą bardzo łatwo napisać: wystarczy dodawać do słownika kolejno pary złożone z odcinanych głów list – argumentów i ich wartości. Gdybyśmy jednak operowali na rozbudowywanym słowniku – moglibyśmy przykryć wartości na podstawie których wartości te są liczone. Dlatego będziemy przekazywali słownik rozbudowywany – ten który na końcu zwrócimy, oraz oryginalny, używany do wartościowania argumentów:

 

; --------------------------------------------

; funkcja rozbudowująca słownik o nazwy z listy

; 'argumenty' o wartościach z listy 'wartości'

; --------------------------------------------

(defun liczargumenty (argumenty wartosci

                      slownik orgslownik)

  (if (atom argumenty)

    slownik

    (liczargumenty

      (cdr argumenty)

      (cdr wartosci)

      (dodajwartosc

        (car argumenty)

        (rozwiaz (car wartosci) orgslownik) slownik )

      orgslownik

    )

  )

)

 

Jeszcze tylko malutka funkcja rozszerzająca słownik o podaną wartość i całość powinna działać:

 

; --------------------------------------------

; funkcja rozbudowująca listę asocjacji o

; podaną asocjację nazwy z wartością

; --------------------------------------------

(defun dodajwartosc (nazwa wartosc slownik)

  (cons (cons nazwa (cons wartosc nil) ) slownik)

)

 

Przetestujmy teraz nasze funkcje na prostej liście asocjacji zawierającej tylko dwie wartości oraz jedną funkcję. Jedna z wartości jest wartością prostą, druga – listą. Jako funkcję – pozwoliłem sobie wybrać funkcję if – pozwalającą na wybór wartości w zależności od wartości traktowanej jako warunek.

 

a  := 10

b := (x 12 ((quote a) b c)))

if := ( (a b c) (cond (a b) (t c) ) ) )

 

Na takiej liście asocjacji – policzymy wartości form, otrzymując:

 

(rozwiaz 'b asocjacje) -> (X 12 ((QUOTE A) B C))

(rozwiaz '(quote x) asocjacje) -> X

(rozwiaz '(cdr b) asocjacje) -> (12 ((QUOTE A) B C))

(rozwiaz '(car b) asocjacje) -> X

(rozwiaz '(atom b) asocjacje) -> NIL

(rozwiaz '(atom a) asocjacje) -> T

(rozwiaz '(cons a b) asocjacje) -> (10 X 12 ((QUOTE A) B C))

(rozwiaz '(cons b a) asocjacje) -> ((X 12 ((QUOTE A) B C)) . 10)

(rozwiaz '(eq a (quote 10)) asocjacje) -> T

(rozwiaz '(eq a (quote 11)) asocjacje) -> NIL

(rozwiaz '(cond (nil (quote www))

                (t (quote xyz))

                (t 1123456))

          asocjacje) -> XYZ

(rozwiaz 'if asocjacje) -> ( (a b c) (cond (a b) (t c) ) ) )

(rozwiaz '(if nil (quote a) (quote b)) asocjacje) -> B

(rozwiaz '(if t (quote a) (quote b)) asocjacje) -> A

 

Czyli nasza funkcja dział tak jak powinna.

Przykład programu

Jako przykład proponuję bardzo prosty problem – rozwiązanie równania kwadratowego Ax2+Bx+C=0. Program napiszemy zgodnie z zaleceniami które mogą nas czegoś nauczyć:

1.        Nie piszemy programu jako sekwencji instrukcji – nie będziemy używali formy prog – której należy unikać jak goto w C++.

2.        Nie będziemy używali formy var pozwalającej na tworzenie zmiennych tymczasowych

3.        Nie będziemy tworzyli żadnych zmiennych globalnych.

Czy  daje się w ten sposób programować optymalny kod? Czy w ogóle daje się w ten sposób programować? Jeśli będziemy myśleć w C++ - będzie to trudne, ale jeśli się chwilę zastanowimy – okaże się, ze zamiast sekwencji instrukcji – można to samo zrobić poprzez superpozycję funkcji do których będziemy przekazywali parametry w postaci przetrawionej.

Po pierwsze – musimy sprawdzić czy nasze równanie jest na prawdę równaniem kwadratowym Jeśli nie – to może jest liniowe – może jest tożsamością a może jest sprzeczne... Przydatna okaże się możliwość zwracania przez funkcję różnych typów wartości. Jeśli równanie nie ma rozwiązań – zwracamy pustą listę, jeśli ma jedno rozwiązanie – zwracamy je, jeśli ma dwa rozwiązanie – zwracamy listę rozwiązań, a jeśli jest tożsamością – literę R – jako symbol zbioru liczb rzeczywistych.

W językach z kontrolą typu – nie byłoby to możliwe. Dla przypadku liniowego – rozwiązanie jest proste. Jeśli jednak jest to prawdziwe równanie kwadratowe – to nie jest już tak dobrze. Musimy wliczyć wyróżnik tego równania, i w zależności od jego znaku – policzyć pierwiastek, pierwiastki lub zwrócić pustą listę.

Zauważmy, że w liczeniu pierwiastków – potrzebne są nam nie współczynniki A, B i C – lecz 2A, -B oraz Delta=B2-4AC:

 

(defun trojmian (a b c)

  (if (= a 0)

    (if (= b 0)

      (if (= c 0)

        (quote R)

      nil

      )

      (/ (- c) b)

    )

    (wyniki (* 2 a) (- b) (delta a b c) )

  )

)

 

(defun delta (a b c)

  (- (* b b) (* 4 a c))

)

 

Pozostaje napisać funkcję wyniki która podejmie decyzję co do sposobu rozwiązywania i zwróci wynik. Zauważmy jednak, że albo musimy zapamiętać pierwiastek z wyróżnika równania, albo liczyć go dwukrotnie – co jest niepotrzebnie nieefektywne. Zamiast tego zapiszmy rozwiązanie w dwóch funkcjach – przekazując drugiej – już liczącej dwa pierwiastki – pierwiastek z wyróżnika a nie sam wyróżnik:

 

(defun wyniki (aa mb d)

  (if (< d 0)

    nil

    (if (= d 0)

      (/ mb aa)

      (dwapierwiastki aa mb (sqrt d) )

    )

  )

)

 

(defun dwapierwiastki (aa mb sd)

  (list

    (/ (- mb sd) aa)

    (/ (+ mb sd) aa)

  )

)

 

Proste? Tak też można. Maść na szczury!

Zadania

1.        Proszę napisać funkcję liczącą silnię i przetestować dla jakiej wartości będzie ona działała.

2.        Proszę napisać funkcję która odwróci listę przekazaną jako parametr.

3.        Proszę napisać funkcję zwracającą n-ty wyraz ciągu Fibonacciego. Uwaga – rozwiązanie czysto rekurencyjne jest niemiłosiernie nieefektywne.

4.        Proszę napisać program obliczający wyrażenie które jest pochodną wyrażenia podanego jako parametr. Dla uproszczenia – zakładamy, że wyrażenia są zapisane w takim formacie jak w LISP-ie



[1] W takim przypadku cudzysłów również należy do zapisu atomu.

[2] W początkowych implementacjach była to rzeczywiście lista. W bardziej współczesnych – jest to tablica symboli, zachowująca się w przypadku powtórzeń – jak stos.

[3] Pamiętajmy, że lista jest również parą. Para wartości nie musi koniecznie oznaczać pary atomów.

[4] To znaczy takie których te funkcje się spodziewają. Nie będziemy się tu bawić w kontrolę poprawności danych.