Poczytaj mi Clojure – cz. 1: Lisp

Clojure to funkcyjny język programowania ogólnego przeznaczenia bazujący na modelu Lisp–1. Jego wzorcowa implementacja działa pod kontrolą maszyny wirtualnej Javy, ale istnieją też wydania pracujące w środowisku Uruchomieniowego Języka Wspólnego platformy .NET czy JavaScriptu. Clojure jest Lispem, który powstał z myślą o przetwarzaniu współbieżnym i korzystaniu z ekosystemu Javy.

Język programowania Clojure został stworzony w roku 2007 przez Richa Hickeya, który oparł go na czterech założeniach:

  1. Język funkcyjny (lecz nie tylko), akcentujący niezmienność danych.

  2. Dialekt Lispa.

  3. Przystosowany do wykonywania współbieżnego.

  4. Działający na platformie gospodarza.

Wzorcowa implementacja Clojure działa pod kontrolą maszyny wirtualnej Javy (ang. Java Virtual Machine, skr. JVM) i w tym przypadku jego platformą gospodarza (ang. host platform) jest JVM. Oznacza to, że pisząc mamy dostęp do wszystkich wbudowanych klas i bibliotek Javy, a postać źródłowa programu może być przekształcona do kodu bajtowego.

Clojure jest napisany w Javie, chociaż pewne specyficzne konstrukcje po kompilacji nie dają się bezpośrednio przełożyć na jej kod źródłowy ze względu na optymalizacje. Inne obsługiwane platformy to na przykład .NET (w Środowisku Uruchomieniowym Języka Wspólnego, ang. Common Language Runtime) czy JavaScript.

Zaczniemy od zapoznania się z cechami protoplasty rodziny języków, do której należy Clojure, czyli od Lispa, aby płynnie przejść do opisów specyficznych dla dialektu, któremu poświęcony jest podręcznik.

Lisp

Clojure jest dialektem języka Lisp (kiedyś zapisywanego jako LISP). Nazwa tego ostatniego to akronim od angielskiego wyrażenia List Processor (pol. procesor list), ponieważ w języku tym najczęściej używaną strukturą danych jest lista (ang. list). Stworzony został w roku 1958 przez Johna McCarthiego z pomocą ze strony Steve’a Russella.

Przynależność do rodziny Lisp–1 oznacza, że mamy do czynienia z jednym rodzajem przestrzeni nazw, w której rezydują zarówno odwzorowania nazw funkcji, jak i tak zwane zmienne globalne. Istnieją też dialekty Lispa, w których funkcje i zmienne znajdują się w różnych przestrzeniach (Lisp–2), a nawet takie, gdzie przestrzeni tych jest znacznie więcej (Lisp–3, Lisp–4 itd.). Peter Norvig w książce “Paradigms of Artificial Intelligence Programming” przywołuje aż 7 możliwych rodzin przestrzeni.

Lisp jest jednym z najstarszych języków programowania, które są aktywnie używane po dziś dzień; jest pod tym względem drugi po Fortranie. Powstał, aby wykonywać obliczenia matematyczne, przetwarzać język naturalny i badać zagadnienia związane ze sztuczną inteligencją w tzw. modelu symbolicznym (logika rozmyta, algorytmy genetyczne, wnioskowanie na bazie kolekcji doświadczeń, symulacje konkretnych procesów).

Lisp jest również językiem niezwykle zwięzłym i ekspresywnym, chociaż wymaga dłuższego myślenia nad problemem, zanim przystąpi się do jego sformułowania w postaci kodu. Zwięzłość oznacza, że w porównaniu do innych języków programowania jego konstrukcje składniowe zajmują mniej miejsca, a ekspresywność, że gramatyka pozwala na opisanie problemu w mniejszej ich liczbie.

Cechy

Rachunek lambda bez typów

Lisp bazuje na tzw. rachunku lambda bez typów (ang. untyped lambda calculus) – systemie formalnym stworzonym przez Alonzo Churcha i Stephena Cole’a Kleene’ego. Jest to matematyczna notacja, w której każde wyrażenie jest jednoargumentową funkcją wyższego rzędu, a zarówno wartością zwracaną, jak i przyjmowanym argumentem są też jednoargumentowe funkcje. Bardziej skomplikowane (np. wieloargumentowe) funkcje możliwe są do wyrażenia z użyciem rozwijania (ang. currying). Jeżeli jakiś algorytm da się wyrazić korzystając z rachunku lambda, to z pewnością można stworzyć jego implementację na maszynie Turinga, a więc w postaci programu komputerowego.

Church chciał, aby rachunek lambda stanowił alternatywę dla teorii mnogości, jeśli chodzi o specyfikowanie podstaw matematyki, jednak tak się nie stało. Nieoceniona jest jednak jego przydatność w teorii obliczeń i projektowaniu funkcyjnych języków programowania.

Warto zaznaczyć, że Lisp z założenia nie był i nie jest dokładną komputerową implementacją rachunku lambda, w którym wszystko jest funkcją. W Lispie mamy do czynienia z wyrażeniami, które efektywnie mogą być funkcjami lub wartościami stałymi. Kolejną różnicą jest strategia wartościowania wyrażeń. W rachunku lambda obliczenia są w praktyce realizowane z zachowaniem tzw. porządku normalnego (ang. normal order), w którym najbardziej zewnętrzne, redukowalne wyrażenia są zawsze skracane, a funkcje są stosowane zanim dojdzie do wartościowania ich argumentów. W Lispie z kolei obowiązuje przekazywanie przez wartość (ang. call by value), gdzie najpierw dochodzi do rekursywnego obliczania wartości argumentów i powiązania rezultatów z symbolicznie nazwanymi parametrami, a dopiero one są przekazywane do wywołania.

Można więc powiedzieć, że Lisp to implementacja rachunku lambda bez typów z obsługą wartości stałych i przekazywaniem przez wartość.

Język funkcyjny

Lisp jest przede wszystkim językiem funkcyjnym – podstawowymi elementami służącymi do budowania programów są funkcje lub konstrukcje zachowujące się jak funkcje (podprogramy przyjmujące argumenty i zwracające wyniki), a nacisk kładzie się na obliczanie ich wartości, czyli wartościowanie (ang. evaluation).

Wywołania funkcji są w Lispie często zagnieżdżone lub operują na innych funkcjach, przekazywanych jako argumenty. Programy nie wykonują się więc “od góry do dołu”, jak ma to miejsce w modelu imperatywnym, ale raczej “w głąb”. Znane z innych języków operatory, pętle czy instrukcje warunkowe mają w Lispie funkcyjne odpowiedniki. Pozwala to zachować prostą składnię i ułatwia uczenie przez rozumienie, a nie przez zapamiętywanie.

W Clojure, podobnie jak w językach czysto funkcyjnych, dąży się też do tego, aby umieszczone w pamięci dane były niezmienne, niemutowalne (ang. immutable). Jeśli mamy jakąś strukturę danych czy nawet pojedynczą wartość, to gdy w wyniku jej przetwarzania (obliczeń na niej) powstaje zmiana, rezultat nie zostaje wpisany do obszaru pamięci, w którym źródłowa struktura faktycznie rezyduje, lecz w pamięci powstaje nowy obiekt. Jest on niemodyfikowalną wartością (ang. value), a nie zmienną strukturą przypisaną do jakiegoś stałego miejsca.

Rezultaty wywołań funkcji możemy przechwytywać i nazywać – mamy wtedy do czynienia z tzw. powiązaniami (ang. bindings), a nie ze zmiennymi (ang. variables). Powiązania to w najprostszym wariancie symboliczne nazwy, które identyfikują wartości umieszczone w pamięci.

Są jednak takie przypadki, że potrzeba skorzystać z danych mutowalnych (ang. mutable), czyli takich, których zawartość można i trzeba bezpośrednio zmieniać. Czysto funkcyjny program byłby kalkulatorem, który przyjmuje na początku pracy jakieś dane wejściowe, przekazuje je do głównej funkcji jako argumenty, a ta wywołuje kolejne podprogramy, aż do uzyskania wartości stanowiącej rezultat obliczeń. Problemy przed jakimi stają programiści są nieco bardziej złożone i często pojawia się konieczność reprezentowania w programach zmieniających się stanów (ang. states), które identyfikowane powinny być stałymi nazwami. W tym kontekście stanem nazwiemy wartość bieżącą przypisaną w danym czasie do abstrakcyjnego obiektu reprezentującego pewną tożsamość (ang. identity). Ilość dostępnych środków na rachunku bankowym, pozycja i liczba punktów gracza, reprezentacja aktualnie przetwarzanej ścieżki dźwiękowej – to przykłady stałych tożsamości, które z momentu na moment mogą przyjmować różne stany wyrażane niezmiennymi wartościami.

Powyższą potrzebę można zrealizować, wprowadzając zmienne, ale wtedy ryzykujemy, że byłyby one nadużywane i rezygnujemy z założenia, że w domyśle wszystkie wartości są stałe. Taka niekonsekwencja doprowadziłaby do zamieszania jeszcze większego, niż traktowanie wszystkich danych jako potencjalnie podlegających zmianom. Z tego też powodu w Clojure mamy do czynienia z tzw. typami referencyjnymi. Ich instancje same nie przechowują wartości, ale odnoszą się do istniejących. Gdy w wyniku wykonania operacji (np. wywołania funkcji) pojawiają się nowe rezultaty, dochodzi do aktualizacji odniesienia, a nie do nadpisania poprzednich danych. Te ostatnie nadal rezydują w pamięci, chociaż bez wyraźnej tożsamości – obiekt referencyjny wskazuje już na inną wartość. W efekcie elementy programu, które jeszcze operują na poprzedniej wartości, mogą działać w sposób przewidywalny. Oznacza to, że programista nie musi stosować konstrukcji wytwarzających lokalne kopie czy zakładających blokady, jak ma to miejsce na przykład w konwencjonalnym modelu programowania wielowątkowego.

Zauważmy, że większość użytkowanych obecnie języków programowania zakorzenionych jest w paradygmacie imperatywnym, w którym język stanowi zaawansowany etap ewolucji programowania w języku maszynowym, tzn. bazuje na sposobie, w jaki działa sprzęt. W pewnym sensie mamy do czynienia z mniej lub bardziej wyabstrahowanymi interfejsami pamięci operacyjnej i centralnej jednostki obliczeniowej. Dane – którymi mogą być pojedyncze wartości, struktury czy inne obiekty – umieszczane są w komórkach pamięciowych identyfikowanych nazwami zmiennych, a szeregi instrukcji odczytują z tych obszarów wyniki obliczeń i modyfikują je, umieszczając rezultaty nowych. Aplikacja wpływa na to, co znajdzie się określonych, dostępnych jej lokalizacjach RAM-u.

Powyższe nie wydaje się niczym niezwykłym i dla wielu jest oczywistym (jeśli nie jedynym) podejściem do rozwiązywania problemów z użyciem komputera. Skoro wyposażony jest on w pamięć, więc programowanie powinno polegać na dostępie do niej; na wpisywaniu, odczytywaniu i zastępowaniu obecnych tam informacji. Z pewnością będzie to dobra strategia przy projektowaniu systemów operacyjnych, sterowników obsługi urządzeń czy lokalnych baz danych – wszędzie tam, gdzie program musi bezpośrednio operować na pamięciowych strukturach z uwagi na wydajność i oszczędność zasobów. Umieszczony w określonym miejscu obiekt może być wtedy szybko zmodyfikowany lub zastąpiony zupełnie innym. Jednak “z wielką mocą wiąże się wielka odpowiedzialność” – poza opracowywaniem rozwiązania problemu programista musi mieć na uwadze to, że na przykład jednoczesny zapis do tej samej przestrzeni przez więcej niż jeden podprogram może spowodować trudną do wykrycia usterkę w działaniu.

Nie chodzi tu nawet o konieczność ręcznego zarządzanie procesami, którymi powinien zajmować się kompilator czy interpreter języka, ale o niski poziom abstrakcji. Każdy problem modelowany imperatywnie musi zostać dostosowany do rzeczywistości, w której większość obiektów może ulegać zmianom, a gdy już dojdzie do zmian zaplanowanych, poprzednie struktury przypisane do konkretnych miejsc nie są pamiętane, lecz nadpisywane. Wyjątkiem będą sytuacje, gdzie programista obsłuży takie przypadki i zadba np. o tworzenie historii zmian czy kopii niektórych danych.

Niestety świat nie działa dokładnie tak, jak komputer, a większość rozwiązań problemów, do których używamy języków programowania, można wyrazić bez konieczności bezpośredniego operowania na modyfikowalnych obszarach pamięci.

Programowanie mocno zakorzenione w paradygmacie funkcyjnym pozwala nie przejmować się zarządzaniem pamięciowymi zasobami – nie tylko przydzielaniem czy zwalnianiem miejsca (z którym mamy do czynienia np. w językach C czy C++), ale nawet tym, że obiekty zajmują jakiekolwiek, określone miejsce! Uniezależnienie tożsamości informacji od jej umiejscowienia oznacza mniej kłopotów, szczególnie w kontekście przetwarzania współbieżnego.

Inną cechą języków funkcyjnych jest zwłoczność (ang. laziness) obliczania wartości wyrażeń. Cecha ta oznacza, że do wartościowania nie dochodzi natychmiast, ale dopiero wtedy, gdy pojawi się odczyt ostatecznego rezultatu. Dialekty Lispa nie są zwłoczne z natury (mamy do czynienia z przekazywaniem przez wartość), ale Clojure obsługuje tzw. leniwe sekwencje – abstrakcyjne struktury danych, które pozwalają na zwłoczny dostęp do wartości elementów kolekcji lub wartości zwracanych przez rekurencyjnie wywoływane funkcje generujące. Odkładanie pojedynczych obliczeń w czasie możemy też zrealizować z wykorzystaniem funkcji wyższego rzędu lub niektórych typów referencyjnych.

Innowacje

Lisp miał duży wpływ na kształt wielu języków programowania. Mechanizmy, które raptem kilka czy kilkanaście lat temu wprowadzono w wielu nowoczesnych językach jako przełomowe i innowacyjne, zaimplementowano w Lispie już w latach 60–80.

Z Lispa pochodzą m.in. takie technologie jak:

  • odśmiecanie pamięci (ang. garbage collection),
  • konstrukcja eval (ang. eval),
  • rekurencja (ang. recursion),
  • instrukcje warunkowe (ang. conditionals),
  • typ funkcyjny (ang. function type),
  • funkcje pierwszej kategorii (ang. first-class functions),
  • funkcje wyższego rzędu (ang. higher-order functions),
  • domknięcia (ang. closures),
  • symbole (ang. symbols),
  • wiązanie zmiennych (ang. variable binding),
  • wyrażenia (ang. expressions),
  • makra (ang. macros),
  • drzewo składniowe (ang. syntax tree),
  • jednoznaczność (homoikoniczność, ang. homoiconicity),
  • metaprogramowanie (ang. metaprogramming),
  • języki dziedzinowe (ang. domain-specific languages, skr. DSL).

Popularność

Można zapytać czemu język o takiej sile wyrazu i możliwościach nie zdominował rynku i nie stał się najpopularniejszym sposobem rozwiązywania problemów z użyciem komputerów? Powody nie są stricte techniczne.

Po pierwsze Lisp musiał najpierw zmierzyć się z marketingiem Uniksów oraz języka C i walkę tę przegrał. Istniały co prawda komputery specjalizowane w uruchamianiu lispowego kodu, wyposażone w systemy operacyjne stworzone w Lispie, jednak były to ekosystemy mniej otwartemniej przenośne niż Uniksy.

Po drugie, gdy po latach miał szansę “powitać się z gąską”, pojawił się boom na języki obiektowe (C++ i Java), a następnie na technologie webowe i nowoczesne języki wieloparadygmatowe, takie jak Ruby czy Python i ich środowiska Ruby On Rails czy Django. [Osobiście zainteresowałem się Lispami, gdy moje kody w Rubym zaczęły być coraz bardziej funkcyjne i deklaratywne – przyp. aut.]

Lista jako podstawowa struktura danych i działający Garbage Collector, to nie tylko większe zużycie RAM-u, ale też nieco większe obciążenie procesora. Namnażanie struktur pamięciowych (i usuwanie nieużywanych) wymaga przecież pewnej pracy. Programy napisane w Lispie mogą być od 5 do nawet 15 procent powolniejsze, niż ich odpowiedniki stworzone w statycznie typizowanych językach imperatywnych. Kiedyś było to przeszkodą, lecz teraz większość centralnych jednostek obliczeniowych wyposaża się w wiele rdzeni. Dla programów zorientowanych imperatywnie oznacza to konieczność stosowania obejść, aby móc współbieżnie realizować operacje. Wynika to z mnogości stosowanych tam struktur, które ulegają zmianie. W przeciwieństwie do imperatywnego, funkcyjne podejście bardzo dobrze sprawdza się w tej domenie, a obciążenie pojedynczego rdzenia przestaje być już tak istotne; szczególnie, gdy pod uwagę weźmiemy koszt utrzymania i zarządzania zmianami w oprogramowaniu.

Kolejny powód “hibernacji” Lispów jest taki, że choć składnia i gramatyka są tam prostsze niż w większości innych języków (mniej reguł, mniej gotowych konstrukcji do zapamiętania, mniej operatorów i specjalnych instrukcji o specyficznej syntaktyce, praktycznie brak składni), to odzwierciedlanie problemów może być kłopotliwe dla początkujących. Dzieje się tak, ponieważ w wielu przypadkach należy porzucić sekwencyjne, imperatywne myślenie, w którym wykonujemy instrukcje, a wyniki poprzednich przekazujemy następnym z użyciem zmiennych. Zamiast tego budujemy niewielkie funkcje lub makra, które wizualnie przypominają bardziej korzenie drzewa, niż drabinę. Często zamiast pętli korzystamy z rekurencji, a zamiast przechowywać tymczasowy rezultat wykonania funkcji w zmiennej przekazujemy dalej po prostu tę funkcję!

Dlaczego Lisp, dlaczego Clojure?

Niektórzy uważają, że języki funkcyjne lub wieloparadygmatowe z dobrą obsługą mechanizmów funkcyjnych (jak np. Scala), są przyszłością branży i staną się bardzo popularne. Nie podzielam tego optymizmu, jeśli chodzi o dialekty Lispów. Mimo że korzystanie z nich może dać przewagę konkurencyjną, mogą one okazać się za trudne. Nie chciałbym tu nikogo urazić – nie chodzi o potencjalną zdolność do ich zrozumienia, ale raczej o potrzebną do tego determinację i czas. Nauka języka funkcyjnego dla kogoś, kto większość życia spędził programując imperatywnie może być nieco szokująca i wymagać odpowiednich warunków. Idealnie byłoby, gdyby te warunki panowały również w miejscu pracy.

Aby Clojure stał się popularny, musi być więc użytkowany w biznesie, a tam może okazać się, że taniej będzie zatrudnić dwie czy trzy osoby o niewygórowanych oczekiwaniach oraz umiejętnościach, zamiast jednego programisty, który zrobi to lepiej w Clojure. Problemy, z którymi przychodzi mierzyć się statystycznej większości programistów w dzisiejszych czasach, nie są kwestiami takiego kalibru, aby zespoły IT, które nad nimi pracują, ogłaszały zmianę paradygmatu i użytkowanej technologii. “Działa? Działa! Na co drążyć temat?”.

Warto nauczyć się Clojure (lub innego dialektu języka Lisp) ze względu na jego formalizm i siłę wyrazu. Już na wstępie, pisząc proste, przykładowe programy, wchodzi się w bezpośredni kontakt z mechanizmami, których zrozumienie jest kluczowe dla uzyskiwania pożądanych rezultatów. Te mechanizmy są często wspólne dla wielu języków programowania, po prostu w Lispie ich użytkowanie jest elementem implementacji. Poznanie jak działa i z czego korzysta sam język pozwala unikać niemiłych niespodzianek i pisać programy bardziej skomplikowane niż Hello World.

Zaczynając przygodę z Perlem, PHP, Rubym czy nawet z językiem C, jesteśmy w stanie przez jakiś czas nie przejmować się tym, w jaki sposób interpreter czy kompilator przetwarza kod źródłowy, aby realizować zadania programu. Z czasem możemy zgłębiać wiedzę o tym, jak dokładnie działa wybrany język i stosować bardziej zaawansowane konstrukcje, na przykład wykorzystując obiekty funkcyjne (czy wskaźniki do funkcji w języku C), domknięcia, typy referencyjne czy tworząc podprogramy, które będą realizowane w sposób zwłoczny. Ucząc się coraz więcej, możemy też zechcieć programować bardziej elegancko, z uwzględnieniem sterowania widocznością i zasięgiem identyfikatorów, odpowiednio dobierając typy i struktury danych, a w końcu przystosowując aplikację do użytkowania większej liczby procesorów czy rdzeni. W Lispach sporo z tej wiedzy potrzebujemy już na początku, aby nie programować w ciemno, niczym ktoś, kto pierwszy raz pisząc w C, dostawia i usuwa symbole gwiazdki przy zmiennych wskaźnikowych, żeby program przestał awaryjnie zakańczać pracę z powodu naruszenia ochrony pamięci.

Rzecz nie jest nawet w tym, że Lisp jest wymagający i skłania do zgłębienia szczegółów działania języka. Chodzi raczej o to, co dzieje się z programistą przy okazji. Będąc zmuszanym przez jego charakter do lepszego zrozumienia pewnych mechanizmów, zupełnie inaczej patrzy się na programowanie także w innych językach.

Poza powodami intersubiektywnymi warto używać Lispa z obiektywnych przyczyn technicznych. Poza zaakcentowaną obsługą współbieżności (w przypadku Clojure) Lisp jest językiem, który dzięki rozbudowanemu systemowi makr i cesze zwanej jednoznacznością (homoikonicznością) pozwala tworzyć syntaktyczne warstwy abstrakcji, dopasowane do rozwiązywania konkretnych problemów i przyspieszające prace. Oznacza to, że mamy realny wpływ na to, jak poradzimy sobie z obsługą złożoności, mogąc dodawać do języka konstrukcje, które nie będą tylko procedurami grupującymi wywołania już istniejących, ale elementami zmieniającymi zasady jego działania.

Syntaktyczna elastyczność Lispów sprawia, że korzystając z makrfunkcji wyższego rzędu możemy dodawać zupełnie nowe konstrukcje (pętle, wyrażenia warunkowe, operatory), które w innych językach musiałyby być zaimplementowane przez ich twórców. Wtedy programista, któremu zależałoby na jakimś potrzebnym mechanizmie, mógłby co najwyżej zaproponować zmiany i czekać na wydanie nowej wersji kompilatora lub interpretera.

W Clojure wiele powszechnie używanych formuł specjalnych jest w istocie zaprogramowanych właśnie jako makra, np. when, or czy and.

Podstawowe konstrukcje

Każdy element kodu źródłowego w Lispie jest symbolicznie zapisanym wyrażeniem (ang. expression). Tekstowe reprezentacje wyrażeń po wczytaniu do pamięci umieszczane są w odpowiednich strukturach abstrakcyjnego drzewa składniowego, które w przypadku Lispów są takimi samymi strukturami, z jakich możemy korzystać w programach, a także – co ważne – do których mamy dostęp. Cecha ta (jednoznaczność) otwiera drogę do transformowania wczytanych wyrażeń z użyciem standardowych konstrukcji języka – zależnie od potrzeb kod może być traktowany jak dane, a dane jak kod.

Każde wyrażenie w Lispie powinno reprezentować jakąś formułę (ang. form), czyli poprawną konstrukcję języka. Poprawną w tym sensie, że da się obliczyć jej wartość.

Formuły mogą być stałe (ang. constant forms) i wtedy ich obliczanie polega na zwróceniu ich własnych wartości. Traktowane tak będą na przykład: łańcuchy znakowe, pojedyncze znaki, wartości numeryczne, obiekty funkcyjne czy nawet pewne złożone struktury danych. Pozostałe rodzaje formuł, które zostaną omówione dalej, wymagają rekurencyjnego wartościowania, aż uzyskiwane rezultaty staną się formułami stałymi.

Co ciekawe stałą formułą będzie też tzw. obiekt funkcyjny (ang. function object), który jest wewnętrzną reprezentacją funkcji. W Lispie funkcje są jednostkami pierwszej kategorii (ang. first-class citizens), tzn. wartościami, które mogą być traktowane tak, jak każde inne: przekazywane jako argumenty lub zwracane jako wartości funkcji, a także wskazywane obiektami referencyjnymi oraz identyfikowane symbolicznymi nazwami. Z kolei formuła funkcyjna (ang. function form) jest takim elementem programu, w którym obiekt funkcyjny jest wywoływany – używa się do tego odpowiedniej składni.

Składnia i nawiasy

Lisp z wyglądu przypomina owsiankę
z wmieszanymi obciętymi paznokciami.
 
 
— Larry Wall

To, co pierwsze rzuca się w oczy, gdy czytamy kod źródłowy programów w Lispie, to duża liczba nawiasów. Są one używane do konstruowania tzw. listowych wyrażeń symbolicznych, czyli jednych z podstawowych konstrukcji składniowych. Dzięki nawiasom można jasno i precyzyjnie wyrażać operacje, jakich chcemy dokonywać, bez pamiętania o kolejności operatorów.

Tak wygląda wywołanie funkcji w języku Ruby:

1
suma(a, b)

A tak odpowiednik w Lispie:

1
(suma a b)

W obydwu przypadkach najpierw podajemy nazwę funkcji, jednak w Lispie nawiasy nie oddzielają wyłącznie listy przyjmowanych przez nią argumentów, lecz całe wyrażenie. Pierwszym elementem listy umieszczonych między nawiasami wyrażeń jest symbolicznie przedstawiona nazwa funkcji (suma), a pozostałe przekazywanymi jej argumentami. Gdybyśmy podali tylko nazwę, bez otaczających nawiasów, albo nazwa nie byłaby umieszczona na pierwszej pozycji, do czynienia mielibyśmy z obiektem funkcyjnym, a nie wywołaniem funkcji.

Spójrzmy jeszcze na porównanie wywołań zagnieżdżonych. Tak wyglądały będą w Rubym:

1
2
3
suma(a, iloraz(b, c))
(2 + 2) * 3
2 + 2 * 3

A tak w Lispie:

1
2
3
(suma a (iloraz b c))
(* (+ 2 2) 3)
(+ 2 (* 2 3))

Listy

W Lispie często używaną strukturą danych jest lista, która służy zarówno do strukturalizowania kodu, jak i do przechowywania danych.

Przykłady lispowych list zapisanych symbolicznie
1
2
3
4
5
6
7
8
9
10
11
12
13
;; kod jako lista:
(raz dwa trzy)
(1 2 3)
(+ 1 2 3)
(funkcja "argument")
('a zbiór)

;; lista jako kod reprezentujący struktury danych:
'(bułki masło płatki herbata)
'(1 2 3)
(list 'bułki 'masło 'płatki 'herbata)
(list "a" "b" "c")
()

Wszystkie powyższe przykłady to wyrażone w symboliczny sposób listy, będące poprawnym kodem źródłowym.

Warto jednak już na początku wyobrażać sobie listę jako sposób uporządkowania danych, a nie zapis z nawiasami. Kiedy słyszymy, że w Lispie kod jest danymi, a dane są kodem, to nie mamy na myśli tylko symbolicznego zapisu, w którym lista wyrażająca kod przypomina listę wyrażającą strukturę danych, lecz fakt, że wewnętrznie składnia programu odzwierciedlana jest z użyciem listowej struktury danych.

Tak naprawdę lista jest bardziej abstrakcyjna i możemy ją wyrazić na przykład w ten sposób:

1
2
3
4
5
6
7
  [ raz ][ * ]
            \
             \
       [ dwa ][ * ]
                 \
                  \
           [ trzy ][ nil ]

Każdy węzeł, w Lispie nazywany komórką cons (ang. cons cell), ma tu dwa sloty: pierwszy wskazuje na zawartość bieżącego elementu, a drugi na kolejny element listy. Tak naprawdę są to po prostu dwa wskaźniki, które mogą odnosić się do dowolnych wartości, chociaż najczęstszą sytuacją będzie ta, w której jeden z nich (zazwyczaj pierwszy) wskazuje na konkretną, stałą wartość. Stałą to znaczy taką, której próba wartościowania (obliczenia) zwróci dalej tę samą wartość.

Historycznie rzecz biorąc, dostęp do pierwszego slotu każdego z elementów nazywamy car (z ang. Contents of the Address part of Register number), a do drugiego cdr (z ang. Contents of the Decrement part of Register number). Etymologia tych dziwnych nazw pochodzi z czasów, gdy implementowano Lispa na komputerze IBM 704 (lata pięćdziesiąte). Maszyna ta miała specjalną instrukcję, która dzieliła 36-bitowe słowo maszynowe na 4 części – carcdr to skrócone etykiety dwóch pierwszych, a w Lispie znalazły się dlatego, że autor używał ich do dzielenia zawartości wewnętrznej struktury reprezentującej komórkę listy. Żargonowo pierwszy slot komórki cons określa się więc skrótem CAR, a drugi CDR.

Nic nie stoi na przeszkodzie, aby lista zawierała w sobie inną listę:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
      (cons)
   (CAR) (CDR)
     |     |
     v     v

  [ raz ][ * ]
            \
             \
       [ dwa ][ * ]
                 \
                  \
              [ * ][ nil ]
               /
              /
         [ 1 ][ * ]
                 \
                  \
              [ 2 ][ nil ]

W Lispie możemy wyrazić ją jako:

(raz dwa (1 2))

Czyli:

1
2
3
4
5
(raz   ; pierwszy element listy
 dwa   ; drugi element listy
 (     ; trzeci element listy – lista zagnieżdżona
  1    ; pierwszy element zagnieżdżonej listy
  2))  ; drugi element zagnieżdżonej listy

A tak wyglądałby zapis z użyciem tzw. notacji pełnej, która w Clojure nie jest używana. W każdej parze nawiasów znajdziemy dwa sloty oddzielone znakiem kropki:

(raz . (dwa . ( (1 . (2 . nil)) . nil) ))

Kropki oddzielają tu rejestry komórek, a elementy nil oznaczają końce list, tzn. informują, że nie będzie już w nich kolejnych elementów. Jeśli drugi slot ma wskazywać na kolejny element listy, to ten kolejny element jest umieszczany po kropce.

W pierwszych wydaniach języka Lisp listy tworzyło się z użyciem funkcji cons (z ang. construct, pol. konstruować). Na przykład:

1
(cons 'raz (cons 'dwa (cons (cons 1 (cons 2 nil)) nil) ))

Co można przedstawić też jako:

1
2
3
4
5
(cons 'raz
      (cons 'dwa
            (cons (cons 1
                        (cons 2 nil))
                  nil)))

Takie budowanie list może i gimnastykuje analityczny umysł, jednak nie służy produktywnemu pisaniu programów. Obecnie niektóre z dialektów Lispa zrezygnowały z obsługi notacji pełnej, chociaż funkcji cons nadal się używa, ale raczej do przeprowadzania operacji na istniejących listach, niż do ich konstruowania od zera. Poza tym w Clojure mamy do czynienia z dwoma rodzajami list. Funkcja cons tworzy jeden z nich, tzw. listy leniwe, składające się z pojedynczych obiektów typu Cons. Drugi rodzaj list możemy tworzyć, korzystając z funkcji list – są one stałą strukturą danych o określonym rozmiarze.

Nie jest też rzadkością, że kilka różnych kolekcji zespalamy z użyciem komórek cons. Mamy wtedy do czynienia ze strukturą złożoną, którą można wyrazić na przykład tak:

1
2
3
4
(cons (list 1 2 3)
      (cons (list 4 5 6)
            (cons 10
                  ())))

Co z kolei można przedstawić z użyciem symbolicznego zapisu z nawiasami w poniższy sposób:

((1 2 3) (4 5 6) 10)

Dzięki swej charakterystyce lispowe listy mogą mieć nie tylko płaską budowę, ale też – jak możemy zauważyć – zawierać wewnątrz odniesienia do innych list. W ten sposób można wytwarzać zagnieżdżone, drzewiaste struktury, które idealnie nadają się do reprezentowania danych decyzyjnych i obliczeniowych, a więc również kodu programu – w takim przypadku możemy mówić o tzw. drzewach składniowych (ang. syntax trees).

Przykład listy przechowującej dane
1
2
3
'((warzywniak (marchewka pietruszka pomidory) )
  (mięsny     (udka)                          )
  (spożywczy  (bułki mleko ser herbata)       ))

Lista nadaje się nie tylko do przechowywania zestawów danych (np. zakupów, które chcemy zrobić), ale też wyrażeń zrozumiałych przez interpreter lub kompilator języka, czyli kodu źródłowego (ang. source code) programu:

Przykład list zawierających dane i kod
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(def zakupy
  '((warzywniak (marchewka pietruszka))
    (spożywczy  (mleko herbata bułki))))

(defn formatuj-produkty [produkty]
  (str (apply str "  - " (interpose ",\n  - " produkty)) ".\n"))

(defn formatuj-zakup [formator-produktu zakup]
  (str "SKLEP: " (first zakup) "\n"
       (apply str (map formator-produktu (rest zakup)))))

(defn drukuj-kartkę-z-zakupami
  [dane formator-zakupu formator-produktu]
  (print (apply str (map (partial formator-zakupu formator-produktu) dane))))

(drukuj-kartkę-z-zakupami zakupy formatuj-zakup formatuj-produkty)

Nie musimy na razie rozumieć, czemu służą konkretne konstrukcje w powyższym przykładzie. Zauważmy jednak, że nawias otwierający listę w linii nr 2 (reprezentującą dane dotyczące sprawunków) ma dodany apostrof. To nie błąd – w taki sposób zwraca się Lispowi uwagę, że podana lista to wartości stałe (dane), a nie wyrażenia, które trzeba obliczyć, aby je uzyskać.

Odbieranie specjalnego znaczenia pewnym wyrażeniom nazywamy cytowaniem (ang. quoting). Sprawia ono, że są one wewnętrznie traktowane jak tzw. formuły stałe, czyli wartości same w sobie, które nie podlegają dalszemu przeliczaniu.

Każde wyrażenie umieszczone w kodzie źródłowym jest bowiem rekurencyjnie wartościowane, aż do uzyskania jakiejś stałej wartości (formuły stałej). Cytowanie sprawia, że następuje powstrzymanie tego procesu dla wybranych wyrażeń i są one wtedy traktowane jako struktury danych, a nie jako kod źródłowy. Oczywiście jeśli zacytowana zostanie wartość stała, to nadal będzie ona tą samą wartością.

Jeżeli cytowanie jest zastosowane względem wyrażenia złożonego, którego elementy są rekurencyjnie wartościowane (np. listy), w pamięci powstanie formuła stała jego struktury, a każdy z jej elementów również będzie rekursywnie zacytowany i potraktowany jak formuła stała. Weźmy za przykład poniższy zapis:

1
'(warzywniak (marchewka pietruszka pomidory))

Mamy w nim dwie symbolicznie zapisane listy (druga jest zagnieżdżona jako drugi element pierwszej) reprezentujące poprawny kod źródłowy, który z kolei wyraża struktury danych również będące listami.

Umieszczone wewnątrz napisy to tak zwane symbole. W Lispach używane są one do nazywania obiektów pamięciowych (podobnie jak zmienne w językach zakorzenionych imperatywnie), ale jeżeli wyrazimy je w formie zacytowanej, to mogą być również samodzielnymi wartościami. W tym przykładzie zastosowane zostały właśnie w taki sposób – używamy ich zamiast łańcuchów znakowych, żeby nie musieć wpisywać cudzysłowów.

Po wczytaniu umieszczonego wyżej fragmentu programu w pamięci powstanie lista zawierająca dwa elementy, która będzie potraktowana jako struktura przechowująca dane (tzw. formuła stała listy). Jej pierwszym elementem będzie symbol warzywniak (traktowany jako tzw. formuła stała symbolu z powodu zacytowania), a drugim lista, w stosunku do której też zadziała cytowanie. Ta ostatnia będzie zawierała symbole: marchewka, pietruszkapomidory (oczywiście w formułach stałych).

Widzimy, że ta sama struktura (lista) może być używana zarówno do wyrażania źródła programu, jak i do organizowania danych, z których ten program korzysta (np. zbioru sklepowych zakupów). Jednak wymienność danych i kodu w Lispie działa też w drugą stronę: dane zorganizowane w formie list mogą stawać się kodem. Dzięki temu w Lispie jesteśmy w stanie tworzyć i stosować potężne makra. Przypominają one funkcje, ale różnią od nich się tym, że przyjmują wyrażenia podane jako argumenty bez ich natychmiastowego, zachłannego wartościowania.

Podążając dalej za podanym wcześniej przykładem, możemy zaobserwować, że każda niezacytowana lista jest wyrażeniem, którego pierwszy element jest symboliczną nazwą jakiegoś podprogramu, który należy wywołać (uruchomić).

Na przykład lista pierwsza (linia nr 1) zaraz po otwierającym nawiasie zawiera napis def. Ten konkretny symbol odnosi się do podprogramu z użyciem którego można tworzyć tzw. zmienne globalne. Mamy tam również argument zakupy, który będzie przekazany podprogramowi. W efekcie uruchomienia powstanie zmienna globalna zakupy, a jej wartością początkową będzie kolejny argument – zacytowana lista rzeczy do nabycia w różnych sklepach.

Działanie defn jest bardzo podobne – również tworzy zmienną globalną, ale powiązaną nie z dowolnymi danymi, lecz z obiektem tworzonej przez nas funkcji.

Spójrzmy na inny przykład definiowania funkcji:

Definiowanie funkcji łączącej wartości argumentów w łańcuch znakowy
1
2
(defn funk [a b c]  ; nazwa: funk, parametry: a, b, c
  (str a b c))      ; ciało funkcji - wywołanie funkcji str

W języku PHP zapisalibyśmy go tak:

Łączenie argumentów w PHP
1
2
3
4
function funk($a, $b, $c)
{
  return join([$a, $b, $c]);
}

A w Rubym tak:

Łączenie argumentów w Rubym
1
2
3
def funk(a, b, c)
  [a, b, c].join
end

Stworzoną własnoręcznie funkcję można wywołać, podając symbol wyrażający jej nazwę jako pierwszy element listy reprezentującej kod programu. Możemy zaobserwować to w ostatniej linii przykładu:

1
(drukuj-kartkę-z-zakupami zakupy formatuj-zakup formatuj-produkty)

Pozostałe elementy są wartościami argumentów przekazywanymi do wywołania funkcji o nazwie drukuj-kartkę-z-zakupami. Pierwszy (symbol zakupy) będzie przed wywołaniem funkcji zmieniony w obiekt listy z zakupami, drugi i trzeci (symbole formatuj-zakupformatuj-produkty) będą zmienione w obiekty zdefiniowanych wcześniej funkcji (tak, przekazujemy tu do funkcji inne funkcje, ale nie wartości ich wywołań).

Dla zastanawiających się nad efektem pracy wcześniej podanego przykładu:

SKLEP: warzywniak
  - marchewka,
  - pietruszka.
SKLEP: spożywczy
  - mleko,
  - herbata,
  - bułki.

Atomy

Istotnym składnikiem Lispa jest atom (ang. atom). Definiujemy go jako taki element, który nie jest listą. Wyjątek to lista pusta, która jest zarówno listą, jak i atomem.

Atomy to wartości podstawowych typów danych, które ciężko lub mało efektywnie byłoby wyrażać w inny sposób. Przypominają one znane z innych języków tzw. typy podstawowe (ang. primitive types).

W przypadku Clojure atom będzie elementem, który jednocześnie:

  • nie jest listą (za wyjątkiem listy pustej),
  • nie jest wektorem (za wyjątkiem wektora pustego),
  • nie jest mapą (za wyjątkiem pustej mapy),
  • nie jest zbiorem (za wyjątkiem zbioru pustego).

Atomem nazwiemy więc dowolny obiekt spełniający powyższe kryteria, czyli między innymi:

We wcześniejszych przykładach łatwo zauważyć, że niektóre elementy listy to właśnie atomy, np. pojawiające się tam liczby czy symbole.

Atomy, podobnie jak listy, są wewnętrznymi strukturami danych, a nie symboliczną, literalną notacją, chociaż żargonowo i skrótowo widząc zapis 1234, możemy nazwać tak zaprezentowaną liczbę atomem.

To wszystko! Znamy całą podstawową składnię języka! Porozmawiajmy o szczegółach…

Symbole

Na szczególną uwagę zasługują symbole. Pozwalają one nazywać wskazania obiektów w pamięci, aby potem się do nich odwoływać. Poza zastosowaniem symboli do identyfikacji innych struktur programista może też korzystać z nich do własnych celów.

Każdy symbol ma nazwę stanowiącą jednocześnie jego identyfikator. W Clojure jest ona łańcuchem tekstowym rozpoczynającym się znakiem niebędącym cyfrą i mogącym zawierać znaki alfanumeryczne oraz: *, +, !, -, _?.

W wielu Lispach symbol jest typem referencyjnym, to znaczy, że sam nie przechowuje wartości wskazywanego obiektu, lecz pozwala się do niego odwołać. W przypadku Clojure jest inaczej – symbol nie zawiera żadnego odwołania do innego obiektu, a to, że używając symboli, można wywoływać funkcje czy odnosić się do stałych wartości, zawdzięczamy odpowiedniemu traktowaniu przez interpreter i kompilator języka w pewnych kontekstach.

Przykłady użycia symboli
1
2
3
4
(funk 1 2 3)     ; funk jest domniemanym symbolem (umiejscowienie)
(symbol "funk")  ; ta funkcja zwróci symbol o podanej nazwie
'funk            ; funk jest symbolem wyrażonym wprost (cytowanie)
(fn [x y] x)     ; x oraz y są parametrami funkcji

W pierwszej linii powyższego przykładu mamy listę, której wiodący element to wyrażona symbolem funk nazwa. Kiedy interpreter języka widzi taki zapis, zmienia umieszczony napis w symbol (tworzy obiekt symbolu o podanej nazwie), a następnie szuka podprogramu, który jest tak nazwanym symbolem identyfikowany, aby go wywołać. Identyfikacja polega na pobraniu skojarzonego z symbolem obiektu, a skojarzenie to przechowywane jest w specjalnej mapie (strukturze asocjacyjnej) zwanej przestrzenią nazw.

W drugiej linii mamy symbol funk stworzony przez programistę z użyciem funkcji, która przyjmuje łańcuch znakowy i zwraca obiekt symbolu o podanej nazwie. Taki symbol jest formułą stałą, czyli reprezentuje wartość własną.

W linii trzeciej również mamy symbol w formie stałej, lecz wygenerowany z użyciem mechanizmu cytowania.

W ostatniej linii używamy symbolicznych nazw do identyfikowania argumentów nienazwanej funkcji w jej ciele. Zapis [x y] to tzw. wektor parametryczny funkcji, a x oraz y są symbolami wyrażającymi tzw. formułę powiązaniową. Nazywa się ona w ten sposób, ponieważ w leksykalnym zasięgu ciała funkcji dochodzi do powiązania symboli z wartościami przekazanymi jako argumenty. Dzięki temu można potem korzystać z nich do odczytywania tych wartości.

Zobacz także:

Przestrzenie nazw

W Clojure funkcjonuje pojęcie przestrzeni nazw (ang. namespaces). Są to asocjacyjne struktury pamięciowe przechowujące odwzorowania typu klucz–wartość. Dzięki nim można lepiej organizować poszczególne elementy programów i separować pakiety z oprogramowaniem. Jeśli dwie biblioteki mają funkcje o takich samych nazwach wyrażonych odwołującymi się do nich symbolami, można uniknąć konfliktu, gdy odwołania te będą zapisane w różnych przestrzeniach nazw. Wtedy wywoływanie funkcji lub ich importowanie będzie wymagało podania przestrzeni, w jakiej się znajdują.

Przestrzenie nazw to w istocie mapy (jeden z typów złożonych w Clojure), czyli słowniki zawierające odwzorowania symboli na zmienne globalne lub klasy Javy.

Obiektom symboli opcjonalnie możemy przypisać nazwę przestrzeni nazw. W zapisie literalnym podajemy ją przed nazwą symbolu i oddzielamy od niej ukośnikiem. Informacja o przestrzeni nie sprawia, że dany symbol zostaje w niej umieszczony, ale zostanie spożytkowana, kiedy będzie on użyty do zidentyfikowania zmiennej globalnej. Odpowiednie odwzorowanie nie będzie wtedy poszukiwane w bieżącej, lecz w określonej przestrzeni.

Przykład wywołania funkcji identyfikowanej symbolem z dookreśloną przestrzenią nazw
1
(clojure.set/select odd? #{1 2 3 4})

Symbol w powyższym przykładzie ma nazwę select i przestrzeń nazw określoną łańcuchem znakowym clojure.set. Ponieważ jest on niezacytowany i znajduje się na pierwszej pozycji listy, będzie potraktowany jak identyfikator funkcji, którą trzeba wywołać. Aby odnaleźć funkcyjny obiekt, przeszukana zostanie przestrzeń nazw clojure.set, a w niej odnaleziony zostanie symbol o takiej samej nazwie (select) i przypisana do niego zmienna globalna. Ta ostatnia powinna zawierać odniesienie do podprogramu funkcji, który zostanie wywołany z argumentami podanymi jako kolejne elementy listy (odd? oraz #{1 2 3 4}). Oczywiście mamy do czynienia z przekazywaniem przez wartość, więc argumenty zostaną wcześniej przeliczone: symbol odd? zmieni się w funkcyjny obiekt a wyrażenie #{1 2 3 4}zbiór zawierający podane liczby całkowite.

Zobacz także:

Zmienne globalne i powiązania

Opowiadając o Clojure, podkreśla się, że nie ma tam zmiennych. Dlaczego więc już kilka razy pojawiło się określenie “zmienne globalne”? Zmienne globalne (ang. global variables) to jeden z najczęściej wykorzystywanych typów danych w tym dialekcie Lispa. Jako jeden z kilku tzw. typów referencyjnych (ang. reference types) służy do tworzenia odwołań do obiektów pamięciowych, czyli tzw. powiązań, a dokładniej powiązań zmiennych globalnych.

Spójrzmy na symboliczne nazwanie zmiennej globalnej i powiązanie jej z wartością z użyciem def.

Przykład powiązania zmiennej globalnej (identyfikowanej symbolem) z wartością
1
(def x 8)

W powyższym wyrażeniu symbol x zostanie w przestrzeni nazw przypisany do stworzonej zmiennej globalnej, której początkową wartością jest 8. Zmienna globalna nie przechowuje tej wartości, ale odwołuje się do niej.

Dokładniejsze opisy powiązań pojawią się w kolejnych odcinkach, teraz wystarczy wiedzieć, że terminem tym możemy określać:

  • sposób kojarzenia symbolicznych identyfikatorów z obiektami w pamięci;
  • sposób kojarzenia typów referencyjnych z obiektami, do których się odwołują.

Zmienność polega na tym, że odwołania do wartości mogą być aktualizowane. Zmiany dokonywane w zmiennej globalnej stają się widoczne we wszystkich wątkach programu, chyba że programista wybierze inaczej.

Z jednej strony zmiennym globalnym mogą być nadawane nazwy (przez skojarzenie z nimi symboli w przestrzeni nazw), a z drugiej mogą one zawierać odwołania do innych obiektów. Łatwo więc dojść do wniosku, że jest to w Clojure sposób na nadawanie nazw wszystkim dostępnym globalnie wartościom w programach. Wyjątkiem są obiekty Javy, do których odwołania umieszczone mogą być bezpośrednio w przestrzeni nazw.

Poza zmiennymi globalnymi w Clojure korzysta się też często z niezmiennych powiązań leksykalnych, które polegają na nadawaniu symbolicznych nazw stałym wartościom umieszczonym w pamięci (np. rezultatom obliczeń czy argumentom przekazywanym do funkcji). Miejscem ich przechowywania jest stos.

Zobacz także:

S-wyrażenia

Lista to struktura danych, którą można wyrazić na różne sposoby: rysując diagram na kartce, tworząc – jak w naszych przykładach – reprezentację graficzną złożoną ze znaków ASCII, czy w końcu, używając pełnej lub uproszczonej symbolicznej notacji z nawiasami, np.:

(raz 2 3)

W ten sposób wyrażona lista to fundamentalny element składniowy programu w języku Lisp – tak zwane wyrażenie symboliczne (ang. symbolic expression), w skrócie S-wyrażenie (ang. S-expression).

(Zauważmy, że słowo “symboliczne” nie ma tu ścisłego związku z symbolami rozumianymi jako pewien typ danych i oznacza po prostu zapis oparty o ustaloną konwencję).

Jednak S-wyrażenie może być nie tylko listą, ale również pojedynczym atomem. Dokładniej rzecz ujmując, S-wyrażeniem nazwiemy:

  • symbolicznie wyrażony atom lub
  • listę złożoną z S-wyrażeń, zapisaną w postaci (a … x) lub (a . b).

Możemy więc wyróżnić atomowe S-wyrażenialistowe S-wyrażenia. Te ostatnie poznamy po tym, że na ich początkach i na końcach znajdują się nawiasy, natomiast pierwsze po tym, że nie są poprzednimi.

  • Jaka jest różnica między S-wyrażeniem a listą?

    S-wyrażenie to podstawowy element składniowy (sposób zapisu zarówno danych, jak i kodu), a lista to struktura danych, która jest używana do organizowania informacji. W przypadku listowych S-wyrażeń ich reprezentacją w pamięci będą listy. Listy powstałe z S-wyrażeń będą stanowiły część drzewa składniowego – wewnętrznej, abstrakcyjnej reprezentacji kodu źródłowego.

  • Jaka jest różnica między S-wyrażeniem a atomem?

    Atom to np. komórka pamięci zajmowana przez liczbę, która wcześniej mogła być symbolicznie wyrażona w postaci tzw. atomowego S-wyrażenia. S-wyrażeniem nazwiemy więc również umieszczony w kodzie źródłowym literał liczbowy czy łańcuch znakowy. Takie S-wyrażenia są postacią zapisywania atomów.

  • Jaka jest różnica między S-wyrażeniem a wyrażeniem?

    S-wyrażenie (zapisane symbolicznie wyrażenie) znajdziemy w kodzie źródłowym programu, a wyrażenie w strukturze danych (np. liście) umieszczonej w pamięci i stanowiącej element drzewa składniowego. Wyrażenia można wartościować, czyli obliczać ich wartości, pod warunkiem, że są formułami.

  • Jaka jest różnica między wyrażeniem a formułą?

    Formułą nazwiemy takie wyrażenie (efekt wczytania do pamięci S-wyrażenia), które jest poprawną reprezentacją programu, czyli da się je wartościować bez wystąpienia błędu.

W Clojure nie tworzy się listowych S-wyrażeń z użyciem notacji pełnej, a poza mamy do czynienia z dodatkowymi rodzajami symbolicznych wyrażeń, które mają znaczenie składniowe:

  • mapami wyrażanymi postacią {k v … x y),
  • zbiorami wyrażanymi postacią #{a … x},
  • wektorami wyrażanymi postacią [a … x].
Przykłady nielistowych S-wyrażeń w Clojure
1
2
3
4
[1 2 3 4]          ; wektor
[1 2 3 (+ 2 2)]    ; wektor
{:a 1 :b (inc 1)}  ; mapa
#{1 2 3}           ; zbiór

Możemy więc mówić dodatkowo o wektorowym S-wyrażeniu (ang. vector S-expression), zbiorowym S-wyrażeniu (ang. set S-expression) i mapowym S-wyrażeniu (ang. map S-expression). W praktyce rzadko kiedy zajdzie potrzeba posługiwania się tak precyzyjnymi określeniami – korzysta się raczej z określeń potocznych: wektor, zbiór i mapa.

Mając zaktualizowaną wiedzę, zdefiniujmy raz jeszcze S-wyrażenie. Będzie nim jedna z następujących konstrukcji składniowych:

  • symbolicznie wyrażony atom (wartość niezłożona);
  • lista S-wyrażeń zapisana w postaci (a … x);
  • wektor S-wyrażeń zapisany w postaci [a … x];
  • mapa S-wyrażeń zapisana w postaci {k v … x y};
  • zbiór S-wyrażeń zapisany w postaci #{a … x}.

(Opcjonalnie można między kolejnymi podawanymi elementami poza spacjami umieszczać przecinki i/lub znaki nowej linii).

Analogicznie jak w przypadku list: zbiór, mapa czy wektor to struktury w pamięci, natomiast odpowiadające im S-wyrażenia są sposobami ich zapisywania. W przeciwieństwie do list: pierwszy element umieszczony w zbiorowych, mapowych czy wektorowych S-wyrażeniach nie będzie traktowany jak podprogram do wykonania (formuła funkcyjna, makrowa lub specjalna), lecz po prostu jako pierwszy element struktury danych.

W drugiej i trzeciej linii ostatnio podanego przykładu mogliśmy zaobserwować, że ostatnimi elementami wektora i mapy były listy reprezentujące kod źródłowy (wywołania funkcji + oraz inc). Podczas przetwarzania takich wyrażeń zostaną one obliczone, zanim w pamięci powstaną ich reprezentacje, ponieważ mamy do czynienia z przekazywaniem przez wartość (argumenty i elementy złożonych S-wyrażeń są rekurencyjnie przeliczane, aż do uzyskania formuł stałych). Wartościowanie będzie polegało na wywołaniu funkcji i przekazaniu im argumentów podanych jako kolejne elementy list. W efekcie te dwie struktury będą zawierały następujące elementy:

  • wektor: [1 2 3 4],
  • mapa: :a 1 :b 2.

Zobacz także:

Zacytowane S-wyrażenia

Ciekawym przykładem wyrażeń symbolicznych są zacytowane S-wyrażenia (ang. quoted S-expressions). Wyrażają one konstrukcje językowe, które nie powinny być wartościowane, tzn. nie powinny być dla nich (lub ich elementów) wyliczane wartości, nawet jeśli ich umiejscowienie w kodzie programu sprawia, że taka operacja byłaby przeprowadzona.

Przykłady cytowania składniowego
1
2
3
4
5
6
7
'(raz 2 3)
'(raz dwa trzy)
'raz
'(+ 2 (* 2 3))
'[1 2 3]
'{:a 1 :b 2}
'#{a b c}

Powyższe można zapisać także bez posługiwania się lukrem składniowym:

Przykłady użycia konstrukcji quote
1
2
3
4
5
6
7
(quote (raz 2 3))
(quote (raz dwa trzy))
(quote raz)
(quote (+ 2 (* 2 3)))
(quote [1 2 3])
(quote {:a 1 :b 2})
(quote #{a b c})

Łatwo zapamiętać cytowanie, ponieważ przypomina ono podobny mechanizm występujący w języku naturalnym. Jeśli mówimy do kogoś, że ma przyjść w gości, to wyrażenie takie będzie miało znaczenie, a może i nawet zostanie wykonane i odwiedzi nas znajomy. Jeżeli jednak wyślemy komuś e-maila, w którym napiszemy, że powiedzieliśmy komuś “masz przyjść w gości”, to odbiorca nie będzie interpretował tego cytatu jako czynności do zrealizowania, ale jako relację wypowiedzianych słów, która jest informacją, lecz nie instrukcją działania.

W praktyce cytowanie to takie oznaczanie fragmentów abstrakcyjnego drzewa składniowego, że są one w specjalny sposób traktowane w fazie obliczania wartości wyrażeń, tzn. zamiast przeprowadzać na nich obliczenia, po prostu zwraca się rezydujące w drzewie obiekty, np. listy (zamiast wywołań funkcji czy makr) czy symbole (zamiast identyfikowanych nimi wartości).

Form(uł)y

Pozostaje jeszcze jedno ważne określenie, które warto poznać (i które zostało już kilkukrotnie użyte): forma (ang. form), nazywana też konstrukcją bądź formułą.

Lispowa formuła to symbolicznie wyrażone dane, które reprezentują poprawny kod źródłowy programu. Innymi słowy formułą nazwiemy takie S-wyrażenie, na którym da się przeprowadzić wartościowanie i uzyskać wynik.

Nie każde S-wyrażenie będzie formułą, chociaż każdą konstrukcję da się (a nawet trzeba) przedstawić w postaci wyrażenia symbolicznego. Formuły są składnikami programu, a S-wyrażenia sposobem ich zapisywania.

Weźmy za przykład zapis:

(raz 2 3)

Jest to listowe S-wyrażenie, które reprezentuje listę składającą się z trzech elementów: raz, 23. Wewnętrznie stanie się ono wyrażeniem, a jego strukturą danych będzie lista. Nie wiemy jednak, czy wyraża ono poprawny kod, a więc czy jest formułą. Jakie warunki muszą być spełnione, aby tak było? Wyrażenie musi być obliczalne, tzn. powinno dać się je przetworzyć, aby otrzymać rezultat (nawet jeśli jest to wartość stała – wtedy rezultatem będzie własna wartość). Czy tak jest w tym przypadku?

Interpreter oczekuje, że pierwszy element listowego wyrażenia symbolicznego emanującego formułę będzie symbolem skojarzonym z podprogramem funkcji, podprogramem makra albo podprogramem formuły specjalnej (o tych dwóch ostatnich później). Oczekuje tego, aby uruchomić odpowiedni kod, a w miejsce formuły wstawić zwróconą wartość w celu dalszych obliczeń.

Aby nasze S-wyrażenie miało szansę stać się formułą języka Clojure:

  1. Jego pierwszy element (napis raz) musi dać się przekształcić do symbolu.

    Tekst będzie przekształcony do symbolu, a więc musi on spełniać wspomniane wcześniej warunki dotyczące poprawności nazwy.

  2. Powinna istnieć zmienna globalna, która w bieżącej przestrzeni nazw została nazwana symbolem (tzn. dany symbol został jej przypisany).

    W tym celu będzie dokonane przeszukanie przestrzeni nazw, pod kątem tego, czy zawiera parę, której kluczem jest symbol, a wartością odwołanie do zmiennej globalnej.

  3. Zmienna globalna powinna zawierać odwołanie do podprogramu (np. obiektu funkcji).

Jeśli te warunki zostaną spełnione, to funkcja jest wartościowana (pobierana jest wartość zwracana w efekcie uruchomienia jej podprogramu).

Przed wywołaniem odnalezionej funkcji każdy z przekazywanych jej argumentów będzie również obliczony, a więc oczekuje się, że one również będą formułami.

Warto przy okazji nadmienić, że niektóre atomy są wartościami samymi w sobie (np. liczby czy słowa kluczowe) i w kontekście realizowania programu nazywamy je tzw. formułami stałymi (ang. constant forms). Tak jest w naszym przykładzie: liczby 2 i 3 to formuły, które same są własnymi wartościami i obliczanie nie zmienia reprezentowanej przez nie wartości.

Spójrzmy na formułę stałą, która jest zapisana z użyciem atomowego S-wyrażenia.

Atomowe S-wyrażenie formy stałej liczby całkowitej
1
12345

Przyjrzyjmy się tez przykładom S-wyrażeń, które formułami nie są.

Przykłady niepoprawnych formuł
1
2
3
4
5
(coś 2 3)  ; symbol "coś" na nic nie wskazuje
coś        ; tu również
(1 2 3)    ; cyfra 1 nie jest makrem, funkcją czy formułą specjalną,
           ; a umiejscowienie na początku listy wskazuje, że ma być
           ; potraktowana jak podprogram

Rodzaje formuł

Możemy mówić o następujących rodzajach formuł (nie trzeba ich pamiętać, ale warto wiedzieć, że możliwy jest taki podział):

  • formuły złożone (ang. compound forms):
    • formuły funkcji anonimowych (ang. lambda forms) – listy, których pierwsze elementy to formuły specjalne lambd (np. fn);
    • formuły ciał funkcji (ang. function body forms) – listy, których elementy to wyrażenia do przeliczenia, gdy funkcje będą wywołane;
    • formuły funkcyjne (ang. function forms) – listy, których pierwsze elementy to symbole wskazujące funkcję;
    • formuły makrowe (ang. macro forms) – listy, których pierwsze elementy to symbole wskazujące makro;
    • formuły kolekcyjne (ang. collection forms) – kolekcje:
      • formuły wektorowe (ang. vector forms) – wektory,
      • formuły mapowe (ang. map forms) – mapy,
      • formuły zbiorowe (ang. set forms) – zbiory,
    • formuły powiązaniowe (ang. binding forms) – powiązania wartości z symbolami:
      • wektorowe formuły powiązaniowe (ang. vector binding forms) – powiązania wartości z symbolami z użyciem wektorowego S-wyrażenia,
      • mapowe formuły powiązaniowe (ang. map binding forms) – powiązania wartości z symbolami, gdzie zarówno wartość, jak i symbol są wyrażone jako asocjacja w mapowym S-wyrażeniu z opcjonalną wartością domyślną;
      • formuły dekompozycyjne (ang. destructuring forms) – powiązania symboli z wybranymi elementami struktur asocjacyjnych lub sekwencyjnych na podstawie abstrakcyjnych powiązań strukturalnych;
  • formuły stałe (ang. constant forms) – wyrażenia będące własnymi wartościami;
  • formuły symbolowe (ang. symbol forms) – atomy symboli, które są obliczalne (wskazują na argumenty funkcji, zmienne globalne, powiązania leksykalne, nazwy obiektów Javy).

Niektóre wyrażenia, m.in. te przedstawiające symbole czy listy, są przez język traktowane w specjalny sposób. Symbole domyślnie są traktowane jak formuły symbolowe (powiązane leksykalnie lub z użyciem zmiennych globalnych z jakimiś wartościami stałymi lub podprogramami), a listy jak formuły funkcyjne (służące do wywoływania podprogramów). W przypadku tego typu S-wyrażeń można skorzystać z cytowania, sprawiając, że powstaną formuły stałe symboli czy formuły stałe list, które nie będą poddawane rekurencyjnemu wartościowaniu, ale traktowane jak struktury służące do przechowywania danych.

Przykłady cytowania listy, wektorów i symbolu
1
2
3
4
'(1 2 3)           ; zacytowana lista pozostaje formułą stałą listy
(quote (raz 2 3))  ; zacytowana lista pozostaje formułą stałą listy
(quote [raz 2 3])  ; zacytowany wektor pozostaje formułą stałą wektora
'abc               ; zacytowany symbol pozostaje formułą stałą symbolu

Formuły specjalne

Formuły specjalne (ang. special forms), zwane też konstrukcjami specjalnymi, są – jak sama nazwa mówi – formułami, które cechuje specjalna składnia i/lub specjalne zasady wartościowania. Niektóre z nich mogą sterować procesem wykonywania się programu i/lub bezpośrednio wpływać na wartości obiektów umieszczonych w pamięci.

W istocie formuła specjalna to rodzaj wbudowanej w język funkcji, której – podobnie jak w przypadku makr – nie wszystkie argumenty od razu są przeliczane. Każda formuła specjalna może mieć odmienny od innych sposób wartościowania wybranych argumentów. Dzięki temu można na przykład tworzyć instrukcje warunkowe.

Zazwyczaj formuły specjalne służą do tworzenia powiązań symboli z obiektami pamięciowymi i umożliwiają budowanie struktur kontrolujących wykonywanie się programu (warunki, iteracje, itp.) – są to operacje, które trudno byłoby w sposób czytelny wyrazić jako zwykłe funkcje.

Operatory

Tworząc anonimową funkcję we wcześniejszym przykładzie, mogliśmy zobaczyć, że jej ciało również wyraża listę.

Przykład tworzenia funkcji anonimowej z użyciem fn
1
2
(fn [a b]
  (+ a b))

W linii drugiej po otwierającym nawiasie pojawia się symbol +, a po nim dwa inne symbole (ab). Interpreter spodziewa się, że pierwszym symbolem jest identyfikator zmiennej globalnej (bo nie ma w nim kropki, jest pierwszym elementem listy, nie jest argumentem konstrukcji let ani argumentem definiowanej funkcji). W mapie przestrzeni nazw znajdzie więc symbol + i odpowiadającą mu referencję do odpowiedniego Vara. Ten ostatni zawierał będzie powiązanie z funkcją sumującą, która zostanie wywołana.

Wywołując kod funkcji, interpreter przekaże dwa kolejne elementy listowego S-wyrażenia, ale najpierw je obliczy. Dla każdego sprawdzi co reprezentuje dany symbol i wykryje, że jego odwzorowanie znajdzie we właśnie definiowanej funkcji, a dokładnie w jej parametrze. W miejsce symboli ab podstawione więc zostaną przyjęte przez anonimową funkcję argumenty identyfikowane symbolami o takich samych nazwach.

Mamy więc do czynienia z poprawną lispową formułą, a efektem jej wyliczenia będzie obiekt funkcji, który sumuje przekazywane argumenty. Możemy nawet jednorazowo użyć tak stworzonej funkcji, korzystając z listowego S-wyrażenia, w którym będzie ona na pierwszym miejscu.

Przykład wywołania funkcji anonimowej w listowym S-wyrażeniu
1
2
( (fn [a b] (+ a b)) 2 2 )
; => 4

W żargonie funkcyjnym funkcję wywoływaną z użyciem listowego S-wyrażenia nazywa się czasem operatorem, a przekazywane argumenty operandami. Z racji składni, w której należy formalnie odróżnić operatory od operandów i zrobić to we właściwej kolejności, nie występuje konieczność wprowadzania tzw. priorytetów operatorów (ang. operator precedence), zwanego też pierwszeństwem operatorów.

Sposób zapisu, w którym najpierw podajemy operację, a potem dane, na których będziemy ją przeprowadzali, jest dobrze znany matematykom i nazywa się notacją polską (ang. polish notation), polską notacją przedrostkową lub po prostu notacją przedrostkową. Dzięki niej można zapisywać długie wzory, które w notacji wrostkowej byłyby mniej czytelne. Jak widać nie tylko dla człowieka, ale również dla interpretera języka Lisp.

Praktyczne definicje

Zanim przejdziemy dalej, spróbujmy podsumować istotne terminy związane z językiem Lisp:

  1. Lista to taka struktura danych, której każdy element poza wartością zawiera też informację o tym, gdzie występuje kolejny element. Można używać jej do przechowywania danych, ale i kodu źródłowego programu (listowych wyrażeń będących efektem wczytania listowych S-wyrażeń).

  2. Atom to taka struktura danych, która nie jest listą, zbiorem, wektorem ani mapą (za wyjątkiem tych struktur pustych), ale może się w nich znaleźć. Cechuje ją niezłożoność.

  3. S-wyrażenie to symboliczny zapis (postać, notacja) wyrażenia.

  4. Wyrażenie to umieszczona w pamięci wewnętrzna reprezentacja fragmentu kodu źródłowego (np. lista, obiekt symbolu, łańcuch znakowy czy liczba).

  5. Formuła to wyrażenie, którego wartość da się obliczyć.

  6. Obliczanie wartości (wartościowanie) wyrażenia polega na rozpoznaniu reprezentowanej nim formuły i wywołaniu odpowiedniego podprogramu lub na zwróceniu wartości stałej (jeżeli wyrażana jest formuła stała).

  7. Struktury danych używane do przechowywania złożonych wyrażeń w drzewie składniowym to listy, wektory, mapyzbiory. Wszystkie ich elementy będą wartościowane, aż do uzyskania formuł stałych, chyba że użyto cytowania. W przypadku list przeprowadzone będzie dodatkowe wartościowanie, polegające na rozpoznaniu operacji wskazywanych ich pierwszymi elementami.

  8. Typy danych używane do przechowywania atomowych wyrażeń zależą od konkretnych obiektów: mogą to być np. łańcuchy znakowe, symbole czy liczby.

Ten materiał jest częścią większej całości, którą można zobaczyć odwiedzając poniższy odnośnik:

Komentarze