(* 2 (+ 3 4)) В программировании S-выражение ( или символическое выражение , сокращенно sexpr или sexp ) — это выражение в одноименной нотации для вложенных списков ( структурированных по дереву ) данных. S-выражения были изобретены и популяризированы языком программирования Lisp , который использует их как для исходного кода , так и для данных.
В обычном синтаксисе 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 ) и используют сокращенную запись для представления списков, содержащих более 2 членов, так что
(x y z)означает
(x . (y . (z . NIL)))NIL— это специальный объект конца списка (альтернативно записываемый как (), что является единственным представлением в Схеме [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-выражения как для кода, так и для данных. Это означает, что Lisp является гомоиконичным ; то есть, первичное представление программ также является структурой данных в примитивном типе самого языка.
Вложенные списки могут быть записаны как S-выражения: ((milk juice) (honey marmalade))— это двухэлементное S-выражение, элементы которого также являются двухэлементными S-выражениями. Разделенная пробелами нотация, используемая в Lisp (и в этой статье), является типичной. Разрывы строк (символы новой строки) обычно считаются разделителями. Это простая контекстно-свободная грамматика для небольшого подмножества английского языка, записанная как S-выражение (Gazdar/Melish, Natural Language Processing in Lisp), где S=предложение, NP=именная группа, VP=глагольная группа, V=глагол:
((( S ) ( NP VP )) (( VP ) ( V )) (( VP ) ( V NP )) (( V ) умер ) (( V ) работал ) (( NP ) медсестры ) (( NP ) пациенты ) (( NP ) Medicenter ) (( NP ) "Доктор Чан" )) Программный код может быть записан в S-выражениях, обычно с использованием префиксной нотации. Пример на Common Lisp :
( defun factorial ( x ) ( if ( zerop x ) 1 ( * x ( factorial ( - x 1 ))))) S-выражения можно читать в Lisp с помощью функции READ. READ считывает текстовое представление S-выражения и возвращает данные Lisp. Функция PRINT может использоваться для вывода S-выражения. Затем вывод можно читать с помощью функции READ, когда все объекты печатаемых данных имеют читаемое представление. Lisp имеет читаемые представления для чисел, строк, символов, списков и многих других типов данных. Программный код можно форматировать как красиво напечатанные S-выражения с помощью функции PPRINT (примечание: с двумя P, сокращение от pretty -print).
Программы на Lisp являются допустимыми S-выражениями, но не все S-выражения являются допустимыми программами на Lisp. (1.0 + 3.1)является допустимым S-выражением, но не допустимой программой на Lisp, поскольку Lisp использует префиксную нотацию, а число с плавающей точкой (в данном случае 1.0) недопустимо в качестве операции (первого элемента выражения).
S-выражение, которому предшествует одинарная кавычка, как в 'x, является синтаксическим сахаром для заключенного в кавычки S-выражения , в данном случае (quote x).
S-выражения часто сравнивают с XML : одно из ключевых отличий заключается в том, что S-выражения имеют только одну форму включения, точечную пару, в то время как теги XML могут содержать простые атрибуты, другие теги или CDATA , каждый из которых использует свой синтаксис. Другое отличие заключается в том, что S-выражения не определяют механизм ссылок, где XML предоставляет понятие уникальных идентификаторов и ссылок на них. Для простых вариантов использования S-выражения проще, чем XML, но для более сложных вариантов использования XML имеет язык запросов, называемый XPath , множество инструментов и сторонних библиотек для упрощения обработки XML-данных.
Стандарты для некоторых языков программирования, производных от Lisp, включают спецификацию для их синтаксиса S-выражений. К ним относятся Common Lisp (стандартный документ ANSI ANSI INCITS 226-1994 (R2004)), Scheme (R5RS и R6RS [5] ) и ISLISP .
В мае 1997 года Рон Ривест представил Internet Draft [6] для рассмотрения на предмет публикации в качестве RFC . В проекте был определен синтаксис, основанный на Lisp S-выражениях, но предназначенный для хранения и обмена данными общего назначения (аналогично XML ), а не специально для программирования. Он никогда не был одобрен как RFC, но с тех пор цитировался и использовался другими RFC (например, RFC 2693) и несколькими другими публикациями. [7] Первоначально он предназначался для использования в SPKI .
Формат Ривеста определяет S-выражение как строку октетов (последовательность байтов ) или конечный список других S-выражений. Он описывает три формата обмена для выражения этой структуры. Один из них — «расширенный транспорт», который очень гибок с точки зрения форматирования и синтаксически похож на выражения в стиле Lisp, но они не идентичны. Расширенный транспорт, например, позволяет представлять строки октетов дословно (длина строки, за которой следует двоеточие и вся необработанная строка), в форме кавычек, допускающей экранированные символы, шестнадцатеричном формате , Base64 или размещать непосредственно как «токен», если он соответствует определенным условиям. (Токены Ривеста отличаются от токенов Lisp тем, что первые предназначены только для удобства и эстетики и обрабатываются точно так же, как и другие строки, в то время как последние имеют определенное синтаксическое значение.)
В черновике Ривеста определяется каноническое представление «для целей цифровой подписи». Оно должно быть компактным, простым для анализа и уникальным для любого абстрактного S-выражения. Оно допускает только дословные строки и запрещает пробелы в качестве форматирования за пределами строк. Наконец, есть «базовое транспортное представление», которое является либо канонической формой, либо той же закодированной как Base64 и окруженной фигурными скобками , последнее предназначено для безопасной передачи канонически закодированного S-выражения в системе, которая может изменять интервалы (например, система электронной почты, которая имеет строки шириной 80 символов и переносит все, что длиннее).
Этот формат не был широко адаптирован для использования за пределами SPKI (некоторые из пользователей — GnuPG , libgcrypt, Nettle и GNU lsh). Веб-страница S-expressions Ривеста предоставляет исходный код C для парсера и генератора (доступный по лицензии MIT ), который может быть адаптирован и встроен в другие программы. [8] Кроме того, нет никаких ограничений на независимую реализацию формата.