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) не може бути розпізнано як операція (перший елемент виразу).

Стандартизація

В травні 1997 року, Рональд Рівест запропонував Інтернет-проект (Internet Draft)[2] нового RFC. Проект визначив синтаксис заснований на S-виразах Ліспа, але призначений для зберігання даних загального призначення та обміну ними за аналогією з XML, а не для програмування. Він так і не був затверджений як RFC, але з тих пір цитується і використовується іншими документами RFC (наприклад RFC 2693) і в ряді інших видань.[3] Спочатку він був призначений для використання в SPKI.

Формат Рівеста визначає S-вираз як якийсь октет-рядок (серію байт) або кінцевий список інших S-виразів. Він описує три формата обміну для виразів з цією структурою. Один з них, «advanced transport» (розширене транспортне подання), дуже гнучкий в плані форматування, і синтаксично схожий на вирази Lisp-стилю, але не є ідентичним. Розширене транспортне представлення, наприклад, дозволяє октет-рядками бути представленими дослівно (довжина рядка, потім двокрапка і весь рядок «як є»), що дозволяє уникнути символів шістнадцяткового або base64 представлення, октет-рядок може бути розміщений безпосередньо як «лексема», якщо він відповідає певним умовам. Лексеми Рівеста відрізняються від лексем в Lisp тим, що існують лише для зручності та естетики, і трактуються так само, як і інші рядки, а не мають конкретного синтаксичного сенсу. Інший формат обміну даними, призначений бути більш компактним, і простіше аналізованим, а також унікальний для будь-якого абстрактного S-виразу — це «канонічне представлення», яке допускає тільки дослівні рядки і забороняє використання пробілів як елементів форматування поза рядками. Нарешті, є ще «базове транспортне представлення» (basic transport representation), яке є канонічною формою, або ті ж елементи в кодуванні Base64, оточені дужками, причому останній слугує безпечним транспортом для канонічно-закодованих S-виразів в системі, яка дозволяє змінювати пробільні проміжки (наприклад, поштова система, яка має рядки 80-рядкової ширини, що накладаються на щось більш довге).

Цей формат не був широко прийнятий до використання за межами SPKI. Рівест на своїй веб-сторінці S-виразів надає початковий код на Сі синтаксичного аналізатора та генератора, які, теоретично, можуть бути використані в інших програмах, хоча ліцензування цих програм не ясно. Проте, немає ніяких обмежень на незалежні реалізації роботи з цим форматом. Вільну реалізацію можна знайти за адресами sexpr.sf.net і leon.bottou.org/projects/minilisp.

Див. також

  • M-вираз
  • car та cdr
  • cons
  • Канонічні S-вирази
  • Порівняння форматів серіалізації даних

Примітки

  1. Gazdar / MelisH, Natural Language Processing in Lisp
  2. Архівована копія. Архів оригіналу за 1 грудня 2008. Процитовано 6 грудня 2016.
  3. rivest sexp — Google Scholar
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.