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

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

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

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. Gazdar / MelisH, Natural Language Processing in Lisp
  2. http://theory.lcs.mit.edu/~rivest/sexp.txt
  3. rivest sexp — Google Scholar