S-wyrażenie

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 zdefiniowane 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

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