Interested Article - S-выражение

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

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

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

Пример: простая грамматика в виде S-выражения :

(((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 года, Рональд Ривест предложил нового RFC . Проект определил синтаксис основанный на S-выражениях Лиспа, но предназначенный для хранения данных общего назначения и обмена ими по аналогии с XML , а не для программирования. Он так и не был утвержден в качестве RFC, но с тех пор цитируется и используется другими документами RFC (например ) и в ряде других изданий. Первоначально он был предназначен для использования в SPKI .

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

Этот формат не был широко принят к использованию за пределами SPKI. Ривест на своей предоставляет исходный код на Си синтаксического анализатора и генератора, которые, теоретически, могут быть использованы в других программах, хотя лицензирование этих программ не ясно. Тем не менее, нет никаких ограничений на независимые реализации работы с этим форматом. Свободную реализацию можно найти по адресам и .