S выражения в lisp

Обновлено: 21.11.2024

В компьютерном программировании , S-выражение (или символическое выражение , сокращенно sexpr или Sexp ) является выражением в одноименных обозначении вложенного списка ( дерева -structured) данных. S-выражения были изобретены и популяризированы языком программирования Lisp , который использует их как для исходного кода, так и для данных.

В обычном синтаксисе Lisp в скобках S-выражение классически определяется как

  1. атом, или
  2. выражение вида , где х и у являются S-выражениями. (x . y)

Это определение отражает представление списка LISP в виде серии «ячеек», каждая из которых представляет собой упорядоченную пару . В простых списках y указывает на следующую ячейку (если есть), таким образом формируя список . Рекурсивный раздел средств определения , что и это представление , и S-выражение обозначение могут представлять любое бинарное дерево . Однако представление может в принципе допускать циклические ссылки, и в этих случаях структура является вовсе не деревом, а циклическим графом и не может быть представлена ​​в нотации S-выражения, если не добавлено соглашение о перекрестных ссылках (аналогично SQL внешние ключи , XML IDREF и т. д.).

Определение атома варьируется в зависимости от контекста; в первоначальном определении Джона Маккарти предполагалось, что существует «бесконечный набор различимых атомарных символов », представленных как «строки заглавных латинских букв и цифр с одиночными вставленными пробелами» (подмножество символьной строки и числовых литералов ).

Большинство современных нотаций sexpr допускают более общие строки в кавычках (например, включая знаки препинания или полный Unicode ) и используют сокращенную нотацию для представления списков с более чем 2 членами, так что

(x y z)

(x . (y . (z . NIL)))

NIL - это специальный объект конца списка (альтернативный вариант написания () , который является единственным представлением в схеме ).

В семействе языков программирования Lisp S-выражения используются для представления как исходного кода, так и данных. Другие виды использования S-выражения в Lisp-производных языках , такие как DSSSL , а также наценка в коммуникационных протоколах , таких как IMAP и Джон Маккарти «s CBCL . Он также используется как текстовое представление WebAssembly . Детали синтаксиса и поддерживаемых типов данных различаются для разных языков, но наиболее распространенной особенностью этих языков является использование S-выражений и префиксной нотации.

СОДЕРЖАНИЕ

Типы данных и синтаксис

Существует множество вариантов формата S-выражения, поддерживающих множество различных синтаксисов для разных типов данных. Наиболее широко поддерживаются:

  • Списки и пары : (1 () (2 . 3) (4))
  • Символы : with-hyphen ?@!$ a\ symbol\ with\ spaces
  • Струны : "Hello, world!"
  • Целые числа : -9876543210
  • Числа с плавающей запятой : -0.0 6.28318 6.022e23

Использование в Лиспе

При представлении исходного кода на Лиспе первым элементом S-выражения обычно является имя оператора или функции, а любые оставшиеся элементы рассматриваются как аргументы. Это называется «префиксная нотация» или « польская нотация ». Например, логическое выражение, написанное 4 == (2 + 2) на C , представлено (= 4 (+ 2 2)) в префиксной нотации Lisp на основе s-expr.

Как отмечалось выше, точное определение «атома» зависит от LISP-подобных языков. Строка в кавычках обычно может содержать что угодно, кроме кавычек, в то время как атом идентификатора без кавычек обычно может содержать что угодно, кроме кавычек, пробелов, круглых скобок, скобок, фигурных скобок, обратной косой черты и точки с запятой. В любом случае запрещенный символ обычно можно включить, экранировав его предыдущей обратной косой чертой. Поддержка Unicode различается.

Рекурсивный случай определения s-expr традиционно реализуется с использованием cons-ячеек .

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

Примеры S-выражений данных

Вложенные списки могут быть записаны как S-выражения: ((milk juice) (honey marmalade)) это двухэлементное S-выражение, элементы которого также являются двухэлементными S-выражениями. Нотация, разделенная пробелами, используемая в Лиспе (и в этой статье), является типичной. Разрывы строк (символы новой строки) обычно квалифицируются как разделители.

Это простая контекстно-свободная грамматика для крошечного подмножества английского языка, записанная как S-выражение (Gazdar / Melish, обработка естественного языка в Лиспе), где S = предложение, NP = словосочетание существительное, VP = фраза глагола, V = глагол :

Пример S-выражений исходного кода

Программный код может быть записан в S-выражениях, обычно с использованием префиксной нотации.

S-выражения можно читать в Лиспе с помощью функции READ. READ читает текстовое представление S-выражения и возвращает данные Lisp. Функцию PRINT можно использовать для вывода S-выражения. Затем вывод может быть прочитан с помощью функции READ, когда все напечатанные объекты данных имеют читаемое представление. Lisp имеет удобочитаемые представления для чисел, строк, символов, списков и многих других типов данных. Программный код можно отформатировать как красиво напечатанные S-выражения с помощью функции PPRINT (примечание: с двумя буквами P, сокращенно от pretty -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 ) и ISLISP .

Вариант Ривеста

Смотрите также: Канонические S-выражения

В мае 1997 года Рон Ривест представил Интернет-черновик для рассмотрения для публикации в качестве RFC . В проекте определен синтаксис, основанный на S-выражениях Лиспа, но предназначенный для хранения и обмена данными общего назначения (аналогично XML ), а не специально для программирования. Он никогда не был утвержден как RFC, но с тех пор он цитировался и использовался другими RFC (например, RFC 2693) и несколькими другими публикациями. Изначально он был предназначен для использования в СПКИ .

Формат Ривеста определяет S-выражение как строку октетов (последовательность байтов ) или конечный список других S-выражений. Он описывает три формата обмена для выражения этой структуры. Одним из них является «расширенный транспорт», который очень гибок с точки зрения форматирования и синтаксически похож на выражения в стиле Лиспа, но они не идентичны. Расширенный транспорт, например, позволяет дословно представлять строки октетов (длина строки, за которой следует двоеточие и вся необработанная строка), форма в кавычках позволяет использовать escape-символы, шестнадцатеричные числа , Base64 или размещать непосредственно как «токен», если он соответствует определенным условиям. (Токены Ривеста отличаются от токенов Lisp тем, что первые предназначены только для удобства и эстетики и обрабатываются точно так же, как и другие строки, в то время как последние имеют определенное синтаксическое значение.)

Проект Ривеста определяет каноническое представление «для целей цифровой подписи». Он должен быть компактным, более простым для анализа и уникальным для любого абстрактного S-выражения. Он разрешает только дословные строки и запрещает форматирование пробелов вне строк. Наконец, есть «базовое транспортное представление», которое представляет собой каноническую форму или ту же кодировку, что и Base64, и окружено фигурными скобками , последнее предназначено для безопасной транспортировки канонически закодированного S-выражения в системе, которая может изменять интервал (например, электронное письмо система, которая имеет строки шириной 80 символов и переносит все, что длиннее).

Этот формат не получил широкого распространения для использования за пределами SPKI (некоторые из пользователей - GnuPG , libgcrypt, Nettle и GNU lsh). Веб-страница S-выражений Rivest предоставляет исходный код C для синтаксического анализатора и генератора (доступен по лицензии MIT ), который может быть адаптирован и встроен в другие программы. Кроме того, нет ограничений на самостоятельную реализацию формата.

Читайте также: