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[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ż

Przypisy

Linki zewnętrzne

Media użyte na tej stronie

Corrected S-expression tree 2.svg
(c) Natecull z angielskiej Wikipedii, CC BY-SA 3.0
Drzewo reprezentujące s-wyrażenie w postaci (* 2 (+ 3 4))