Wyrażenie S - S-expression

Struktura danych drzewa reprezentująca wyrażenie S(* 2 (+ 3 4))

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

  1. atom, lub
  2. 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)))

NILjest 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 #x10przypadku szesnastkowych liczb całkowitych lub #\Cznakó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

Zobacz także: kanoniczne wyrażenia S

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ż

Bibliografia

Zewnętrzne linki