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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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).