S-вираз

S-вираз (sexp для символічного виразу) — спосіб запису напівструктурованих даних в доступній для людського розуміння текстовій формі. Символічні вирази створюються, в основному, із символів і списків. S-вирази найбільш відомі завдяки їх використанню в мовах програмування сімейства Lisp. Також S-вирази застосовують у мовах-спадкоємцях Ліспа, таких як DSSSL, і в розмітці комунікаційних протоколів на кшталт IMAP і CBCL Джона Маккарті.

Деталі синтаксису і підтримуваних типів даних відрізняються в різних мовах, але загальна особливість — використання S-виразів як префіксної нотації з використанням дужок (відомих як кембріджська польська нотація).

S-вирази в Ліспі як для коду, так і для даних (див. Маккарті «Рекурсивні функції символічних виразів»). S-вирази були спочатку призначені тільки для представлення даних, якими повинні були маніпулювати M-вирази, але перша реалізація Ліспа була інтерпретатором S-виразів, в які планувалося перекладати М-вирази, і програмісти Lisp незабаром звикли до використання S-виразів як для даних, так і для коду.

S-вирази можуть бути як окремими об'єктами (атомами), такими як числа, символи, включаючи спеціальні символи nil і t, або точковими парами, у вигляді (x . y). Довші списки, що складаються з вкладених точкових пар, наприклад (1 . (2 . (3 . nil))), можна написати більш звичним способом, як (1 2 3). Вкладені списки також можуть бути записані у вигляді S-виразів: ((молоко, сік) (мед мармелад)). S-вирази не залежать від пропусків та розривів рядків, пропуски використовуються тільки як розмежувачі між атомами.

Приклад: проста граматика у вигляді S-виразу[1]:

(((S) (NP) (VP))
 ((VP) (V))
 ((VP) (V) (NP))
 ((V) died)
 ((V) employed)
 ((NP) nurses)
 ((NP) patients)
 ((NP) Medicenter)
 ((NP) Dr Chan))

Програмний код може бути записаний у вигляді S-виразу (зазвичай із використанням префіксной нотації). Невеликий шматочок синтаксичного цукру для написання програм на Ліспі полягає в тому, що часто використовуваний вираз (quote x) можна замінити скороченням 'x Приклад на Common Lisp:

(defun factorial (x)
   (if (zerop x)
       1
       (* x (factorial (- x 1)))))

Приклад на Scheme:

(define (factorial x)
    (if (zero? x)
        1
        (* x (factorial (- x 1)))))

S-вирази в Ліспі читаються за допомогою функції READ. Ця функція читає текстове представлення S-виразу і повертає Lisp-дані. Функція PRINT може бути використана для виведення S-виразу. Те, що повертає PRINT, можна прочитати за допомогою функції READ за умови, що всі виведені об'єкти даних мають представлення для вводу-виводу. Lisp має таке представлення чисел, рядків, символів, списків і ще багатьох типів даних. Програмний код може бути представлений у вигляді акуратно форматованого (pretty printed) S-виразу за допомогою функції PPRINT.

Lisp програми — це коректні S-вирази, але не всі S-вирази є правильними програмами на Lisp. (1.0 + 3.1) — це коректний S-вираз, але не коректна Lisp-програма, Lisp використовує префіксну нотацію, тому число з рухомою комою (1.0) не може бути розпізнано як операція (перший елемент виразу).