Wyrażenie S - S-expression
W programowaniu komputerowym , S-wyrażenie (lub wyrażenie symboliczne , w skrócie sexpr lub s-wyrażenie ) jest wyrazem w podobnie nazwie notacji dla zagnieżdżonej listy ( drzewo -structured) danych. Wyrażenia S zostały wynalezione i spopularyzowane przez język programowania Lisp , który wykorzystuje je zarówno w kodzie źródłowym, jak i danych.
W zwykłej nawiasowej składni Lisp wyrażenie S jest klasycznie definiowane jako
- atom, lub
- ekspresja formy , gdzie x i y są S-wyrażenia.
(x . y)
Ta definicja odzwierciedla reprezentację LISP-a listy jako serii "komórek", z których każda stanowi uporządkowaną parę . W zwykłych listach y wskazuje na następną komórkę (jeśli istnieje), tworząc w ten sposób listę . Rekurencyjne punkt środków rozdzielczości, który to reprezentacja i oznaczenie S wyrażenie może reprezentować dowolny drzewo binarne . Jednak reprezentacja może w zasadzie dopuszczać odwołania cykliczne, w których to przypadkach struktura nie jest wcale drzewem, ale grafem cyklicznym i nie może być reprezentowana w notacji S-wyrażenia, chyba że zostanie dodana konwencja odsyłacza (analogicznie do SQL klucze obce , identyfikatory IDREF XML itp.).
Definicja atomu różni się w zależności od kontekstu; w oryginalnej definicji Johna McCarthy'ego zakładano, że istnieje „nieskończony zbiór rozróżnialnych symboli atomowych ” reprezentowanych jako „ciągi wielkich liter łacińskich i cyfr z pojedynczymi osadzonymi spacjami” (podzbiór ciągu znaków i literałów numerycznych ).
Większość nowoczesnych notacji sexpr dopuszcza bardziej ogólne łańcuchy w cudzysłowie (na przykład zawierające interpunkcję lub pełny Unicode ) i używa notacji skróconej do reprezentowania list zawierających więcej niż 2 elementy, dzięki czemu
(x y z)
oznacza
(x . (y . (z . NIL)))
NIL
jest specjalne końcówki liście obiekt (alternatywnie napisano ()
, które to jedyny w schemacie ).
W rodzinie języków programowania Lisp wyrażenia S są używane do reprezentowania zarówno kodu źródłowego, jak i danych. Inne zastosowania S-wyrażeń są w językach Lisp-pochodnych, takich jak DSSSL i jak Mark-up w protokołach komunikacyjnych , takich jak IMAP i John McCarthy „s CBCL . Jest również używany jako tekstowa reprezentacja WebAssembly . Szczegóły składni i obsługiwanych typów danych różnią się w różnych językach, ale najczęstszą cechą tych języków jest użycie wyrażeń S i notacji przedrostkowej.
Typy danych i składnia
Istnieje wiele wariantów formatu S-expression obsługujących różne składnie dla różnych typów danych. Najczęściej wspierane są:
-
Listy i pary :
(1 () (2 . 3) (4))
-
Symbole :
with-hyphen
?@!$
a\ symbol\ with\ spaces
-
Ciągi :
"Hello, world!"
-
Liczby całkowite :
-9876543210
-
Liczby zmiennoprzecinkowe :
-0.0
6.28318
6.022e23
Znak #
jest często używany jako przedrostek w rozszerzeniu składni, np. w #x10
przypadku szesnastkowych liczb całkowitych lub #\C
znaków.
Użyj w Lisp
Podczas reprezentowania kodu źródłowego w Lisp, pierwszy element wyrażenia S jest zwykle operatorem lub nazwą funkcji, a wszelkie pozostałe elementy są traktowane jako argumenty. Nazywa się to „notacją przedrostkową” lub „ notacją polską ”. Jako przykład, wyrażenie Boolean napisane 4 == (2 + 2)
w C jest reprezentowane tak, jak (= 4 (+ 2 2))
w notacji prefiksu Lisp opartej na s-expr.
Jak wspomniano powyżej, dokładna definicja "atomu" różni się w językach podobnych do LISP-a. Ciąg w cudzysłowie może zazwyczaj zawierać wszystko oprócz cudzysłowu, podczas gdy niecytowany atom identyfikatora może zazwyczaj zawierać wszystko oprócz cudzysłowów, znaków odstępu, nawiasów, nawiasów klamrowych, ukośników odwrotnych i średników. W obu przypadkach zabroniony znak można zwykle dołączyć, unikając go z poprzedzającym ukośnikiem odwrotnym. Obsługa Unicode jest różna.
Rekurencyjny przypadek definicji s-expr jest tradycyjnie implementowany przy użyciu komórek cons .
Wyrażenia S były pierwotnie przeznaczone tylko do manipulowania danymi przez wyrażenia M , ale pierwsza implementacja Lisp była interpreterem kodowania wyrażeń S dla wyrażeń M, a programiści Lisp wkrótce przyzwyczaili się do używania wyrażeń S dla obu kodów i dane. Oznacza to, że Lisp jest homoikoniczny ; to znaczy, że podstawowa reprezentacja programów jest również strukturą danych w prymitywnym typie samego języka.
Przykłady danych wyrażeń S
Listy zagnieżdżone można zapisać jako wyrażenia S: ((milk juice) (honey marmalade))
jest to dwuelementowe wyrażenie S, którego elementy są również dwuelementowymi wyrażeniami S. Notacja oddzielona białymi znakami używana w Lisp (i tym artykule) jest typowa. Podziały wiersza (znaki nowego wiersza) zwykle kwalifikują się jako separatory.
Jest to prosta gramatyka bezkontekstowa dla małego podzbioru angielskiego zapisanego jako wyrażenie S (Gazdar/Melish, przetwarzanie języka naturalnego w Lisp), gdzie S=zdanie, NP=fraza rzeczownikowa, VP=fraza czasownikowa, V=czasownik :
(((S) (NP VP))
((VP) (V))
((VP) (V NP))
((V) died)
((V) employed)
((NP) nurses)
((NP) patients)
((NP) Medicenter)
((NP) "Dr Chan"))
Przykład kodu źródłowego S-expressions
Kod programu można napisać w wyrażeniach S, zwykle przy użyciu notacji przedrostkowej.
Przykład w Common Lisp :
(defun factorial (x)
(if (zerop x)
1
(* x (factorial (- x 1)))))
Wyrażenia S można odczytać w Lisp za pomocą funkcji CZYTAJ. READ odczytuje tekstową reprezentację wyrażenia S i zwraca dane Lisp. Funkcja PRINT może być użyta do wyprowadzenia S-wyrażenia. Wynik może być wtedy odczytany za pomocą funkcji CZYTAJ, gdy wszystkie drukowane obiekty danych mają czytelną reprezentację. Lisp ma czytelne reprezentacje liczb, łańcuchów, symboli, list i wielu innych typów danych. Kod programu może być sformatowany jako ładnie drukowane wyrażenia S za pomocą funkcji PPRINT (uwaga: z dwoma literami Ps, skrót od pretty -print).
Programy Lisp są prawidłowymi wyrażeniami S, ale nie wszystkie wyrażenia S są prawidłowymi programami Lisp. (1.0 + 3.1)
jest poprawnym wyrażeniem S, ale nie jest poprawnym programem Lisp, ponieważ Lisp używa notacji przedrostkowej, a liczba zmiennoprzecinkowa (tutaj 1.0) nie jest poprawna jako operacja (pierwszy element wyrażenia).
Wyrażenie S poprzedzone pojedynczym cudzysłowem, tak jak w 'x
, jest cukrem składniowym dla cytowanego wyrażenia S , w tym przypadku (quote x)
.
Rozbiór gramatyczny zdania
Wyrażenia S są często porównywane do XML : kluczowa różnica polega na tym, że wyrażenia S mają tylko jedną formę zawierania, parę kropkowaną, podczas gdy tagi XML mogą zawierać proste atrybuty, inne tagi lub CDATA , każdy z inną składnią. Dla prostych przypadków użycia wyrażenia S są prostsze niż XML, ale dla bardziej zaawansowanych przypadków użycia XML ma język zapytań o nazwie XPath, wiele narzędzi i bibliotek innych firm, aby uprościć obsługę danych XML.
Normalizacja
Standardy dla niektórych języków programowania wywodzących się z Lisp zawierają specyfikację ich składni S-expression. Należą Common Lisp (ANSI standardowy dokument ANSI INCITS 226-1994 (R2004)), Scheme (R5RS i R6RS ) i ISLISP .
Wariant Rivesta
W maju 1997 r. Ron Rivest przesłał projekt internetowy do rozpatrzenia do publikacji jako RFC . Projekt zdefiniował składnię opartą na wyrażeniach Lisp S, ale przeznaczoną do ogólnego przechowywania i wymiany danych (podobnie jak w XML ), a nie specjalnie do programowania. Nigdy nie został zatwierdzony jako RFC, ale od tego czasu był cytowany i używany przez inne RFC (np. RFC 2693) oraz kilka innych publikacji. Pierwotnie był przeznaczony do użytku w SPKI .
Format Rivesta definiuje S-wyrażenie jako ciąg oktetu (seria bajtów ) lub skończoną listę innych S-wyrażeń. Opisuje trzy formaty wymiany do wyrażania tej struktury. Jednym z nich jest "transport zaawansowany", który jest bardzo elastyczny pod względem formatowania i składniowo podobny do wyrażeń w stylu Lisp, ale nie są one identyczne. Zaawansowany transport, na przykład, umożliwia dosłowną reprezentację ciągów oktetowych (długość ciągu, po której następuje dwukropek i cały ciąg surowy), postać cytowana umożliwiająca znaki ucieczki, szesnastkowe , Base64 lub umieszczane bezpośrednio jako „token”, jeśli spełnia określone warunki. (Tokeny Rivesta różnią się od tokenów Lisp tym, że te pierwsze służą wyłącznie wygodzie i estetyce i są traktowane dokładnie tak, jak inne ciągi znaków, podczas gdy te drugie mają określone znaczenie syntaktyczne.)
Projekt Rivesta definiuje reprezentację kanoniczną „do celów podpisu cyfrowego”. Ma być zwarty, łatwiejszy do przeanalizowania i unikalny dla każdego abstrakcyjnego wyrażenia S. Pozwala tylko na dosłowne ciągi i zabrania białych znaków jako formatowania zewnętrznych ciągów. Wreszcie istnieje "podstawowa reprezentacja transportu", która jest albo formą kanoniczną, albo taką samą zakodowaną jak Base64 i otoczoną nawiasami klamrowymi , ta ostatnia ma na celu bezpieczne transportowanie kanonicznie zakodowanego wyrażenia S w systemie, który może zmienićodstępy (np. e-mail system, który ma 80-znakowe linie i owija wszystko, co jest dłuższe).
Ten format nie został powszechnie zaadaptowany do użytku poza SPKI (niektórzy użytkownicy to GnuPG , libgcrypt, Nettle i GNU lsh). Strona internetowa S-expressions firmy Rivest zawiera kod źródłowy C dla parsera i generatora (dostępny na licencji MIT ), który można zaadaptować i osadzić w innych programach. Ponadto nie ma ograniczeń dotyczących samodzielnego wdrażania formatu.
Zobacz też
- Cons
- SAMOCHÓD i CDR
- Fexpr
- Rachunek lambda
- Wyrażenie M
- Kanoniczne wyrażenia S
- Porównanie formatów serializacji danych
Bibliografia
Zewnętrzne linki
- sfsexp mała, szybka biblioteka wyrażeń S dla C/C++ na GitHub
- minilisp , autorstwa Léona Bottou.
- Wyrażenia S w Rosettacode mają implementacje czytników i pisarzy w wielu językach.