S-wyrażenie

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 sexp ) jest wyrażeniem w notacji o podobnej nazwie dla danych zagnieżdżonej listy ( o strukturze drzewa ). S-wyrażenia zostały wymyślone i spopularyzowane przez język programowania Lisp , który wykorzystuje je zarówno do kodu źródłowego , jak i danych.

W zwykłej składni Lispa w nawiasach, wyrażenie S jest klasycznie definiowane jako

  1. atom postaci x , lub
  2. wyrażenie postaci ( x . y ) , gdzie x i y są wyrażeniami S.

Ta definicja odzwierciedla reprezentację LISP-a jako serii "komórek", z których każda stanowi uporządkowaną parę . W zwykłych listach y wskazuje następną komórkę (jeśli istnieje), tworząc w ten sposób listę . Klauzula rekurencyjna definicji oznacza, że ​​zarówno ta reprezentacja, jak i notacja S-wyrażenia mogą reprezentować dowolne drzewo binarne . Jednak reprezentacja może w zasadzie dopuszczać odwołania cykliczne, w których to przypadkach struktura wcale nie jest drzewem, ale wykresem cyklicznym i nie mogą być reprezentowane w klasycznej notacji S-wyrażenia, chyba że zapewniona jest konwencja odsyłaczy (analogicznie do kluczy obcych SQL , SGML / XML IDREF itp.). Nowoczesne dialekty Lispa, takie jak Common Lisp i Scheme , zapewniają taką składnię za pomocą etykiet danych , za pomocą których można oznaczać obiekty, które mogą następnie powtarzać się w innym miejscu, wskazując raczej na wspólną niż powieloną strukturę, umożliwiając czytnikowi lub drukarce wykrywać, a tym samym uruchamiać ocenę lub wyświetlanie cykli bez nieskończonego powtarzania

#n=( xy . #n#)

Definicja atomu różni się w zależności od kontekstu; w pierwotnej definicji Johna McCarthy'ego założono, że istnieje „nieskończony zestaw rozpoznawalnych symboli atomowych ” reprezentowany jako „ciągi wielkich łacińskich liter i cyfr z pojedynczymi osadzonymi spacjami” (podzbiór ciągów znaków i literałów numerycznych ).

Większość nowoczesnych notacji sexpr pozwala na bardziej ogólne ciągi cytowane (na przykład włączając znaki interpunkcyjne lub pełny Unicode ) i używa skróconej notacji do reprezentowania list zawierających więcej niż 2 elementy, dzięki czemu

( x y z )

oznacza

( x . ( y . ( z . NIL)))

NIL jest specjalnym obiektem końca listy (alternatywnie zapisanym () , który jest jedyną reprezentacją w Scheme ).

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ń występują w językach wywodzących się z Lispa, takich jak DSSSL , oraz jako znaczniki w protokołach komunikacyjnych , takich jak IMAP i CBCL Johna McCarthy'ego . 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 najbardziej powszechną cechą tych języków jest stosowanie wyrażeń S i notacji przedrostkowej.

Typy danych i składnia

Istnieje wiele wariantów formatu S-expression, obsługujących wiele różnych składni dla różnych typów danych. Najszerzej obsługiwane są:

  • Listy i pary : (1 () (2 . 3) (4))
  • Symbole : with-hyphen ?@!$ a\ symbol\ with\ spacje
  • Struny : „Witaj, świecie!”
  • Liczby całkowite : -9876543210
  • Liczby zmiennoprzecinkowe : -0,0 6,28318 6,022e23

Znak # jest często używany do poprzedzania rozszerzeń składni, np. #x10 dla liczb całkowitych w systemie szesnastkowym lub #\C dla znaków.

Użyj w Lispie

Podczas reprezentowania kodu źródłowego w Lispie, pierwszym elementem S-wyrażenia jest zwykle nazwa operatora lub funkcji, a pozostałe elementy są traktowane jako argumenty. Nazywa się to „notacją przedrostkową” lub „ notacją polską ”. Na przykład boolowskie zapisane 4 == (2 + 2) w C jest reprezentowane jako (= 4 (+ 2 2)) w Lispie opartej na s-expr notacji przedrostkowej.

Jak wspomniano powyżej, dokładna definicja „atomu” różni się w różnych językach podobnych do LISP-a. Ciąg znaków 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, białych znaków, nawiasów, nawiasów klamrowych, ukośników odwrotnych i średników. W obu przypadkach zabroniony znak można zwykle uwzględnić, poprzedzając go odwrotnym ukośnikiem. Unicode jest różna.

Przypadek rekurencyjny definicji s-wyrażenie jest tradycyjnie implementowany przy użyciu komórek cons .

S-wyrażenia były pierwotnie przeznaczone tylko do danych, które miały być manipulowane przez M-wyrażenia , ale pierwsza implementacja Lispa była interpretatorem kodowania S-wyrażeń M-wyrażeń, a programiści Lispu szybko przyzwyczaili się do używania S-wyrażeń dla obu kodów i dane. Oznacza to, że Lisp jest homoikoniczny ; to znaczy podstawową reprezentacją programów jest również struktura danych w prymitywnym typie samego języka.

Przykłady S-wyrażeń danych

Zagnieżdżone listy można zapisać jako S-wyrażenia: ((sok mleczny) (marmolada miodowa)) to dwuelementowe S-wyrażenie, którego elementy są również dwuelementowymi S-wyrażeniami. Notacja oddzielona spacjami używana w Lispie (i tym artykule) jest typowa. Podziały linii (znaki nowej linii) zwykle kwalifikują się jako separatory.

Jest to prosta gramatyka bezkontekstowa dla niewielkiego podzbioru języka angielskiego zapisanego jako wyrażenie S (Gazdar/Melish, Natural Language Processing in Lisp), gdzie S=zdanie, NP=wyrażenie rzeczownikowe, VP=wyrażenie czasownikowe, V=czasownik : 

  
  
   
  
  
  
  
  
  (((  S  )  (  NP  VP  ))  ((  VP  )  (  V  ))  ((  VP  )  (  V  NP  ))  ((  V  )  zmarł  )  ((  V  )  zatrudniony  )  ( (  NP  )  pielęgniarki  )  ( (  NP  )  pacjenci  )  ((  NP  )  Medicenter  )  ((  NP  )   "Dr Chan"  ))

Przykład S-wyrażeń kodu źródłowego

Kod programu można zapisać w S-wyrażeniach, zwykle przy użyciu notacji przedrostkowej.

Przykład we Common LISP : 

  
     
       
             (  defun  silnia  (  x  )  (  if  (  zero  x  )  1  (  *  x  (  silnia  (  -  x  1  )))))

S-wyrażenia można odczytać w Lispie za pomocą funkcji READ. READ odczytuje tekstową reprezentację S-wyrażenia i zwraca dane Lispa. Funkcji PRINT można użyć do wyprowadzenia S-wyrażenia. Wyjście można następnie odczytać za pomocą funkcji READ, gdy wszystkie drukowane obiekty danych mają czytelną reprezentację. Lisp ma czytelne reprezentacje liczb, ciągów znaków, symboli, list i wielu innych typów danych. Kod programu można sformatować jako ładnie wydrukowane S-wyrażenia za pomocą funkcji PPRINT (uwaga: z dwoma 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 prawidłowym wyrażeniem S, ale nie jest prawidłowym programem Lisp, ponieważ Lisp używa notacji przedrostkowej, a liczba zmiennoprzecinkowa (tutaj 1.0) nie jest prawidłową operacją (pierwszy element wyrażenia).

S-wyrażenie poprzedzone pojedynczym cudzysłowem, jak w 'x , jest cukrem składniowym dla cytowanego S-wyrażenia , w tym przypadku (cytat x) .

Rozbiór gramatyczny zdania

S-wyrażenia są często porównywane do XML : kluczowa różnica polega na tym, że S-wyrażenia mają tylko jedną formę zawierania, parę kropkowaną, podczas gdy znaczniki XML mogą zawierać proste atrybuty, inne znaczniki lub CDATA , z których każdy używa innej składni. W prostych przypadkach użycia wyrażenia S są prostsze niż XML, ale w bardziej zaawansowanych przypadkach XML ma język zapytań, zwany 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 Lispa obejmują specyfikację ich składni S-wyrażeń. Należą do nich Common Lisp (standardowy dokument ANSI ANSI INCITS 226-1994 (R2004)), Scheme (R5RS i R6RS ) oraz ISLISP .

Wariant Rivesta

Zobacz też: Kanoniczne S-wyrażenia

W maju 1997 r. Ron Rivest przesłał projekt internetowy do rozważenia do publikacji jako dokument RFC . W szkicu zdefiniowano składnię opartą na wyrażeniach Lisp S, ale przeznaczoną raczej do przechowywania i wymiany danych ogólnego przeznaczenia (podobnie jak XML ), a nie specjalnie do programowania. Nigdy nie został zatwierdzony jako dokument RFC, ale od tego czasu był cytowany i używany w innych dokumentach RFC (np. RFC 2693) i kilku innych publikacjach. Pierwotnie był przeznaczony do użytku w SPKI .

Format Rivesta definiuje S-wyrażenie jako ciąg oktetów (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 jest składniowo podobny do wyrażeń w stylu Lispa, ale nie są one identyczne. Na przykład zaawansowany transport umożliwia reprezentację ciągów oktetów dosłownie (długość ciągu, po którym następuje dwukropek i cały nieprzetworzony ciąg), forma cytowana umożliwiająca znaki ucieczki, szesnastkowy , Base64 lub umieszczony bezpośrednio jako „token”, jeśli spełnia określone warunki. (Tokeny Rivesta różnią się od tokenów Lispa tym, że te pierwsze służą tylko wygodzie i estetyce oraz są traktowane dokładnie tak, jak inne łańcuchy, podczas gdy te drugie mają określone znaczenie składniowe).

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 spacji jako formatowania poza ciągami. Wreszcie istnieje „podstawowa reprezentacja transportu”, która jest albo formą kanoniczną, albo taką samą zakodowaną jak Base64 i otoczoną nawiasami klamrowymi , ten ostatni miał na celu bezpieczny transport kanonicznie zakodowanego wyrażenia S w systemie, który może zmieniać odstępy (np. system poczty elektronicznej, który ma linie o szerokości 80 znaków i zawija wszystko dłuższe).

Ten format nie został szeroko dostosowany do użytku poza SPKI (niektórzy użytkownicy to GnuPG , libgcrypt , Nettle i GNU lsh ). Strona internetowa S-expressions firmy Rivest zawiera C dla parsera i generatora (dostępny na licencji MIT ), który można dostosować i osadzić w innych programach. Ponadto nie ma ograniczeń dotyczących samodzielnego wdrażania formatu.

Zobacz też

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=S-expression&oldid=1141601896 ”