Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Древовидная структура данных, представляющая S-выражение(* 2 (+ 3 4))

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

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

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

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

(x y z)

означает

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

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

В семействе языков программирования 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

Этот символ #часто используется для префикса расширений синтаксиса, например, #x10для шестнадцатеричных целых чисел или #\Cсимволов.

Использование в Лиспе [ править ]

При представлении исходного кода в Лиспе первым элементом 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, обработка естественного языка в Lisp), где S = предложение, NP = словосочетание существительное, VP = фраза глагола, V = глагол :

((( S )  ( NP  VP ))  (( VP )  ( V ))  (( VP )  ( V  NP ))  (( V )  умерли )  (( V )  наняты )  (( NP )  медсестры )  (( NP )  пациенты )  (( НП )  Медикентр )  (( НП )  «Доктор Чан» ))

Пример S-выражений исходного кода [ править ]

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

Пример в Common Lisp :

( defun  factorial  ( x )  ( if  ( zerop  x )  1  ( *  x  ( факториал  ( -  x  1 )))))

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

Программы на Лиспе являются допустимыми S-выражениями, но не все S-выражения являются допустимыми программами на Лиспе. (1.0 + 3.1)является допустимым S-выражением, но не допустимой программой на Лиспе, поскольку Лисп использует префиксную нотацию, а число с плавающей запятой (здесь 1.0) недопустимо как операция (первый элемент выражения).

S-выражение, которому предшествует одинарная кавычка, например , в данном случае 'xявляется синтаксическим сахаром для цитируемого S-выражения(quote x) .

Разбор [ править ]

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

Стандартизация [ править ]

Стандарты для некоторых языков программирования, производных от Lisp, включают спецификацию их синтаксиса S-выражений. К ним относятся Common Lisp (стандартный документ ANSI ANSI INCITS 226-1994 (R2004)), Scheme (R5RS и R6RS [3] ) и ISLISP .

Вариант Ривеста [ править ]

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

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

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

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

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

См. Также [ править ]

  • минусы
  • CAR и CDR
  • Fexpr
  • Лямбда-исчисление
  • М-выражение
  • Канонические S-выражения
  • Сравнение форматов сериализации данных

Ссылки [ править ]

  1. ^ a b Джон Маккарти (1960/2006). Рекурсивные функции символьных выражений. Архивировано 2 февраля 2004 г. в Wayback Machine . Первоначально опубликовано в Сообщениях ACM .
  2. ^ "Пересмотренный отчет ^ 5 по алгоритмической языковой схеме" . schemers.org .
  3. ^ Спербер, Майкл; Дибвиг, Р. Кент; Флэтт, Мэтью; Ван Страатен, Антон; Финдлер, Робби; Мэтьюз, Джейкоб (12 августа 2009 г.). «Пересмотренный6 отчет по алгоритмической языковой схеме». Журнал функционального программирования . 19 (S1): 1–301. CiteSeerX 10.1.1.372.373 . DOI : 10.1017 / S0956796809990074 . 
  4. ^ S-выражения , Network Working Group, Internet Draft, срок действия истекает 4 ноября 1997 г. - Р. Ривест, 4 мая 1997 г. draft-rivest-sexp-00.txt, Рональд Л. Ривест, сайт CSAIL MIT
  5. ^ rivest sexp , Google Scholar (поиск)
  6. ^ "SEXP (S-выражения)" . people.csail.mit.edu .

Внешние ссылки [ править ]

  • sfsexp небольшая, быстрая библиотека S-выражений для C / C ++ на Github
  • minilisp , автор - Леон Ботту.
  • S-выражения в Rosettacode имеют реализации читателей и писателей на многих языках.