(* 2 (+ 3 4))В компьютерном программировании S -выражение (или символическое выражение , сокращенно sexpr или sexp ) представляет собой выражение в одноименной нотации для данных вложенного списка ( с древовидной структурой). S-выражения были изобретены и популяризированы языком программирования Lisp , который использует их как для исходного кода , так и для данных.
В обычном синтаксисе Лиспа в скобках S-выражение классически определяется [1] как
x, или(x . y)Это определение отражает представление списка в LISP как серии «ячеек», каждая из которых представляет собой упорядоченную пару . В простых списках y указывает на следующую ячейку (если она есть), образуя таким образом список . Рекурсивная часть определения означает, что и это представление, и нотация S-выражения могут представлять любое двоичное дерево . Однако представление в принципе может допускать циклические ссылки, и в этом случае структура вообще не является деревом, а циклическим графом , и не может быть представлена в классической нотации S-выражения, если не предусмотрено соглашение о перекрестных ссылках (аналогично Внешние ключи SQL , SGML / XML IDREF и т. д.). Современные диалекты Lisp, такие как Common Lisp [2] и Scheme [3], предоставляют такой синтаксис через метки данных , с помощью которых можно помечать объекты, которые затем могут повторяться где-либо еще, указывая на общую, а не дублированную структуру, позволяя читателю или принтеру обнаруживать и таким образом запускать оценку или отображение циклов без бесконечной рекурсии
#n=(x y . #n#)Определение атома варьируется в зависимости от контекста; в первоначальном определении Джона Маккарти [1] предполагалось, что существует «бесконечное множество различимых атомарных символов », представленных как «строки заглавных латинских букв и цифр с одиночными встроенными пробелами» (подмножество строк символов и числовых литералов) . ).
Большинство современных нотаций sexpr допускают более общие строки в кавычках (например, включая знаки препинания или полный Unicode ) и используют сокращенную нотацию для представления списков, содержащих более двух членов, так что
(x y z)означает
(x . (y . (z . NIL)))NIL— это специальный объект конца списка (также называемый (), который является единственным представлением в Scheme [4] ).
В семействе языков программирования Lisp S-выражения используются для представления как исходного кода, так и данных. S-выражения также используются в языках, производных от Lisp, таких как DSSSL , а также в качестве разметки в протоколах связи , таких как IMAP и CBCL Джона Маккарти . Он также используется в качестве текстового представления WebAssembly . Детали синтаксиса и поддерживаемых типов данных различаются в разных языках, но наиболее общей особенностью этих языков является использование S-выражений и префиксной записи.
Существует множество вариантов формата S-выражений, поддерживающих различные синтаксисы для разных типов данных. Наиболее широко поддерживаются:
(1 () (2 . 3) (4))with-hyphen ?@!$ |a symbol with spaces|"Hello, world!"-9876543210-0.0 6.28318 6.022e23Этот символ #часто используется для префикса расширений синтаксиса, например #x10, для шестнадцатеричных целых чисел или #\Cдля символов.
При представлении исходного кода в Lisp первым элементом S-выражения обычно является имя оператора или функции, а все остальные элементы рассматриваются как аргументы. Это называется «префиксной записью» или « польской записью ». Например, логическое выражение, написанное 4 == (2 + 2)на C , представлено (= 4 (+ 2 2))в префиксной нотации Lisp на основе s-expr.
Как отмечалось выше, точное определение «атома» различается в разных LISP-подобных языках. Строка в кавычках обычно может содержать что угодно, кроме кавычек, тогда как атом идентификатора без кавычек обычно может содержать что угодно, кроме кавычек, пробелов, скобок, скобок, фигурных скобок, обратной косой черты и точки с запятой. В любом случае запрещенный символ обычно можно включить, экранируя его предшествующей обратной косой чертой. Поддержка Unicode варьируется.
Рекурсивный случай определения s-expr традиционно реализуется с использованием ячеек cons .
S-выражения изначально предназначались только для данных, которыми можно было манипулировать с помощью M-выражений , но первая реализация Lisp была интерпретатором S-выражений, кодирующих M-выражения, и программисты Lisp вскоре привыкли использовать S-выражения для обоих кодов. и данные. Это означает, что Лисп гомоиконичен ; то есть первичное представление программ также является структурой данных в примитивном типе самого языка.
Вложенные списки можно записать как S-выражения: ((milk juice) (honey marmalade))— это двухэлементное S-выражение, элементы которого также являются двухэлементными S-выражениями. Обозначение, разделенное пробелами, используемое в Лиспе (и в этой статье), является типичным. Разрывы строк (символы новой строки) обычно считаются разделителями. Это простая контекстно-свободная грамматика для небольшого подмножества английского языка, написанная в виде S-выражения (Газдар/Мелиш, обработка естественного языка в Лиспе), где S=предложение, NP=именная фраза, VP=глагольная фраза, V=глагол. :
((( S ) ( NP VP )) (( VP ) ( V )) (( VP ) ( V NP )) (( V ) умер ) (( V ) трудоустроен ) (( NP ) медсестры ) (( NP ) пациенты ) (( NP ) Медицентр ) (( NP ) "Доктор Чан" )) Программный код может быть записан в S-выражениях, обычно с использованием префиксной записи. Пример в Common Lisp :
( defun факториал ( x ) ( if ( Zerop x ) 1 ( * x ( факториал ( - x 1 ))))) S-выражения можно прочитать в Лиспе с помощью функции READ. READ считывает текстовое представление S-выражения и возвращает данные Lisp. Функция PRINT может использоваться для вывода S-выражения. Затем вывод можно прочитать с помощью функции READ, когда все напечатанные объекты данных имеют читаемое представление. В Lisp есть читаемые представления чисел, строк, символов, списков и многих других типов данных. Программный код можно отформатировать в виде красиво напечатанных S-выражений с помощью функции PPRINT (примечание: с двумя P, сокращением от beautiful -print).
Программы на Лиспе являются допустимыми S-выражениями, но не все S-выражения являются допустимыми программами на Лиспе. (1.0 + 3.1)является допустимым S-выражением, но не допустимой программой на Лиспе, поскольку Лисп использует префиксную запись, а число с плавающей запятой (здесь 1.0) недопустимо в качестве операции (первый элемент выражения).
S-выражение, которому предшествует одинарная кавычка, например , в данном случае 'xявляется синтаксическим сахаром для цитируемого S-выражения(quote x) .
S-выражения часто сравнивают с XML : ключевое отличие состоит в том, что S-выражения имеют только одну форму включения — точечную пару, тогда как теги XML могут содержать простые атрибуты, другие теги или CDATA , каждый из которых использует свой синтаксис. Для простых случаев использования S-выражения проще, чем XML, но для более сложных случаев использования XML имеет язык запросов, так называемый XPath , множество инструментов и сторонних библиотек для упрощения обработки данных XML.
Стандарты некоторых языков программирования, производных от Lisp, включают спецификацию их синтаксиса S-выражений. К ним относятся Common Lisp (стандартный документ ANSI ANSI INCITS 226-1994 (R2004)), Scheme (R5RS и R6RS [5] ) и ISLISP .
В мае 1997 года Рон Ривест представил Интернет-проект [6] для рассмотрения на предмет публикации в качестве RFC . В проекте определен синтаксис, основанный на S-выражениях Lisp, но предназначенный для хранения и обмена данными общего назначения (аналогично XML ), а не специально для программирования. Он никогда не был утвержден в качестве RFC, но с тех пор его цитировали и использовали в других RFC (например, RFC 2693) и ряде других публикаций. [7] Изначально он предназначался для использования в SPKI .
Формат Ривеста определяет S-выражение как строку октетов (серию байтов ) или как конечный список других S-выражений. Он описывает три формата обмена для выражения этой структуры. Одним из них является «расширенный транспорт», который очень гибок с точки зрения форматирования и синтаксически похож на выражения в стиле Лиспа, но они не идентичны. Расширенный транспорт, например, позволяет представлять строки октетов дословно (длина строки следует за двоеточием и всей необработанной строкой), форму в кавычках, допускающую escape-символы, шестнадцатеричные символы , Base64 или помещать непосредственно как «токен», если оно отвечает определенным условиям. (Токены Ривеста отличаются от токенов Лиспа тем, что первые предназначены только для удобства и эстетики и обрабатываются точно так же, как и другие строки, тогда как вторые имеют особое синтаксическое значение.)
Проект Ривеста определяет каноническое представление «для целей цифровой подписи». Он должен быть компактным, простым для анализа и уникальным для любого абстрактного S-выражения. Он допускает только дословные строки и запрещает пробелы при форматировании внешних строк. Наконец, существует «базовое транспортное представление», которое имеет либо каноническую форму, либо закодировано в формате Base64 и заключено в фигурные скобки . Последнее предназначено для безопасной транспортировки канонически закодированного S-выражения в систему, которая может изменить интервал (например, электронное письмо). система, которая имеет строки шириной 80 символов и переносит все, что длиннее этой).
Этот формат не был широко адаптирован для использования за пределами SPKI (некоторые пользователи — GnuPG , libgcrypt, Nettle и GNU lsh). На веб-странице S-выражений Ривеста представлен исходный код C для синтаксического анализатора и генератора (доступен по лицензии MIT ), который можно адаптировать и встроить в другие программы. [8] Кроме того, нет ограничений на самостоятельное внедрение формата.