S-вираз
S-вираз (sexp для символічного виразу) — спосіб запису напівструктурованих даних в доступній для людського розуміння текстовій формі. Символічні вирази створюються, в основному, із символів і списків. S-вирази найбільш відомі завдяки їх використанню в мовах програмування сімейства Lisp. Також S-вирази застосовують у мовах-спадкоємцях Ліспа, таких як DSSSL, і в розмітці комунікаційних протоколів на кшталт IMAP і CBCL Джона Маккарті.
Деталі синтаксису і підтримуваних типів даних відрізняються в різних мовах, але загальна особливість — використання S-виразів як префіксної нотації з використанням дужок (відомих як кембріджська польська нотація).
S-вирази в Ліспі як для коду, так і для даних (див. Маккарті «Рекурсивні функції символічних виразів»). S-вирази були спочатку призначені тільки для представлення даних, якими повинні були маніпулювати M-вирази, але перша реалізація Ліспа була інтерпретатором S-виразів, в які планувалося перекладати М-вирази, і програмісти Lisp незабаром звикли до використання S-виразів як для даних, так і для коду.
S-вирази можуть бути як окремими об'єктами (атомами), такими як числа, символи[en], включаючи спеціальні символи 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[en])[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-виразів [Архівовано 21 серпня 2008 у Wayback Machine.] надає початковий код на Сі синтаксичного аналізатора та генератора, які, теоретично, можуть бути використані в інших програмах, хоча ліцензування цих програм не ясно. Проте, немає ніяких обмежень на незалежні реалізації роботи з цим форматом. Вільну реалізацію можна знайти за адресами sexpr.sf.net [Архівовано 14 січня 2009 у Wayback Machine.] і leon.bottou.org/projects/minilisp [Архівовано 25 лютого 2012 у Wayback Machine.].
- ↑ Gazdar / MelisH, Natural Language Processing in Lisp
- ↑ Архівована копія. Архів оригіналу за 1 грудня 2008. Процитовано 6 грудня 2016.
{{cite web}}: Обслуговування CS1: Сторінки з текстом «archived copy» як значення параметру title (посилання) - ↑ rivest sexp — Google Scholar. Архів оригіналу за 30 серпня 2013. Процитовано 6 грудня 2016.