S-wyrażenie

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 zdefiniowane^[1] 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)^[2]) oraz Scheme (R5RS^[3] oraz R6RS^[4]). Była także próba (w 1997 r.) standaryzacji poprzez dokumenty RFC standardów internetowych.^[5] Dokument opisywał S-wyrażenia jako format wymiany danych (prostsza alternatywa dla XML).

Zobacz też

Rachunek lambda

Przypisy

↑ John McCarthy (1960/2006). Recursive functions of symbolic expressions. Pierwotnie opublikowane w Communications of the ACM.
↑ Information Technology - Programming Language - Common Lisp (dostęp płatny).
↑ R5RS. schemers.org.
↑ The Revised⁶ Report on the Algorithmic Language Scheme. 6rs.org.
↑ S-Expressions (draft-rivest-sexp-00.txt).