S-выражение

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

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

S-выражения могут быть как отдельными объектами (атомами), такими как числа, Символ (Lisp) (англ.), включая специальные символы 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 года, Рональд Ривест предложил Интернет-проект (англ.) ^[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-выражений предоставляет исходный код на Cи синтаксического анализатора и генератора, которые, теоретически, могут быть использованы в других программы, хотя лицензирование этих программ не ясно. Тем не менее, нет никаких ограничений на независимые реализации работы с этим форматом. Свободную реализацию можно найти по адресам sexpr.sf.net и leon.bottou.org/projects/minilisp.

См. также

• M-выражение
• car и cdr (англ.)
• cons (англ.)
• Канонические S-выражения (англ.)
• Сравнение форматов сериализации данных (англ.)

Примечания

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