thumb|220px|drzewo reprezentujące s-wyrażenie w postaci (* 2 (+ 3 4)) S-wyrażenie (ang. S-expression skrót od symbolic expression) – to notacja, służąca do zapisu struktury list oraz drzew pod postacią tekstu. Wykorzystywana w językach rodziny Lisp oraz do zapisu tekstowego WebAssembly.
Definicja
Oryginalnie S-wyrażenie zostało zdefiniowaneJohn McCarthy (1960/2006). Recursive functions of symbolic expressions. Pierwotnie opublikowane w Communications of the ACM. jako:
atom (w zależności od języka, np. symbol, liczba, lub ciąg znaków) lub para w formie (x . y), gdzie x i y są S-wyrażeniami.
Zgodnie z definicją S-wyrażeniem jest także lista w formie ciągu par (x . (y . (z . NIL))), gdzie atom NIL to specjalny znacznik końca listy (w języku Scheme jest nim pusta lista ()). Taka lista może być zapisana w wygodniejszej notacji jako (x y z). Elementami list mogą być także inne listy.
Dzięki użyciu par można utworzyć dowolne drzewo binarne, którego liśćmi są atomy.
Przykład Przykład S-wyrażenia:
(foo bar (baz "lorem" (quux "ipsum" 10 20) 30))
Przykład kodu języka Common Lisp:
(defun factorial (x) (if (zerop x) 1 (* x (factorial (- x 1)))))
Standaryzacja S-wyrażenia zostały sformalizowane przez standardy języka Common Lisp (standard ANSI, dokument INCITS 226-1994 (R2004)) oraz Scheme (R5RS oraz R6RS). Była także próba (w 1997 r.) standaryzacji poprzez dokumenty RFC standardów internetowych. Dokument opisywał S-wyrażenia jako format wymiany danych (prostsza alternatywa dla XML).
Zobacz też Rachunek lambda
Przypisy
Linki zewnętrzne Parser S-Wyrażeń (języka LISP) w JavaScript S-Expressions na stronie Rosettacode zawiera przykłady implementacji w różnych językach
Kategoria:Języki programowania Kategoria:Lisp