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

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

Zobacz też

[edytuj | edytuj kod]

Przypisy

[edytuj | edytuj kod]
  1. ↑ John McCarthy (1960/2006). Recursive functions of symbolic expressions. Pierwotnie opublikowane w Communications of the ACM.
  2. ↑ Information Technology - Programming Language - Common Lisp (dostęp płatny).
  3. ↑ R5RS. schemers.org.
  4. ↑ The Revised6 Report on the Algorithmic Language Scheme. 6rs.org.
  5. ↑ S-Expressions (draft-rivest-sexp-00.txt).

Linki zewnętrzne

[edytuj | edytuj kod]