S -výraz - S-expression

Stromová datová struktura představující S-výraz(* 2 (+ 3 4))

V programování počítače , An S-výraz (nebo symbolickým vyjádřením , zkráceně sexpr nebo sexp ) je výraz v podobně pojmenované notací pro vnořené seznamu ( strom -structured) dat. S-výrazy byly vynalezeny a propagovány programovacím jazykem Lisp , který je používá pro zdrojový kód i pro data.

V obvyklé závorkové syntaxi Lisp je výraz S klasicky definován jako

  1. atom, popř
  2. vyjádření formy , kde x a y jsou S-výrazy.(x . y)

Tato definice odráží reprezentaci seznamu LISP jako řady „buněk“, z nichž každá je uspořádaným párem . V jednoduchých seznamech y ukazuje na další buňku (pokud existuje), čímž se vytvoří seznam . Rekurzivní klauzule z definice znamená, že obě tato zobrazení a S-výraz notace představuje libovolný binární strom . Reprezentace však v zásadě umožňuje kruhové odkazy, přičemž v těchto případech struktura není vůbec strom, ale cyklický graf , a nelze ji reprezentovat v zápisu výrazu S, pokud není přidána konvence pro křížový odkaz (analogicky k SQL cizí klíče , XML IDREF atd.).

Definice atomu se liší podle kontextu; v původní definici Johna McCarthyho se předpokládalo, že existuje „nekonečný soubor rozlišitelných atomových symbolů “ reprezentovaných jako „řetězce velkých latinských písmen a číslic s jednoduchými vloženými mezerami“ (podmnožina znakových řetězců a číselných literálů ).

Většina moderních sexpr notací umožňuje obecnější citované řetězce (například včetně interpunkce nebo úplného Unicode ) a pomocí zkrácené notace reprezentuje seznamy s více než 2 členy, takže

(x y z)

znamená

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

NILje speciální objekt na konci seznamu (alternativně napsaný (), což je jediná reprezentace ve schématu ).

V rodině programovacích jazyků Lisp se výrazy S používají k reprezentaci zdrojového kódu i dat. Jiná použití S-výrazy jsou v Lisp odvozených jazyků, jako je DSSSL a jako přirážku v komunikačních protokolů , jako IMAP a John McCarthy je CBCL . Používá se také jako textová reprezentace WebAssembly . Podrobnosti o syntaxi a podporovaných datových typech se v různých jazycích liší, ale nejběžnější funkcí mezi těmito jazyky je použití výrazů S a notace předpon.

Datové typy a syntaxe

Existuje mnoho variant formátu S-expression, podporujících různé syntaxe pro různé datové typy. Nejvíce podporované jsou:

  • Seznamy a páry :(1 () (2 . 3) (4))
  • Symboly :with-hyphen ?@!$ a\ symbol\ with\ spaces
  • Řetězce :"Hello, world!"
  • Celá čísla :-9876543210
  • Čísla s plovoucí desetinnou čárkou :-0.0 6.28318 6.022e23

Znak #je často používán k prefixu rozšíření syntaxe, např. #x10Pro hexadecimální celá čísla nebo #\Cpro znaky.

Použití v Lisp

Při reprezentaci zdrojového kódu v Lispu je prvním prvkem výrazu S obvykle název operátoru nebo funkce a všechny zbývající prvky jsou považovány za argumenty. Toto se nazývá „předponová notace“ nebo „ polská notace “. Jako příklad je booleovský výraz napsaný 4 == (2 + 2)v jazyce C reprezentován jako (= 4 (+ 2 2))v Lispově notaci předpony založené na s-expr.

Jak bylo uvedeno výše, přesná definice „atomu“ se v jazycích podobných LISP liší. Řetězec v uvozovkách může obvykle obsahovat cokoli kromě uvozovky, zatímco atom necitovaného identifikátoru může obvykle obsahovat cokoli kromě uvozovek, prázdných znaků, závorek, závorek, závorek, zpětných lomítek a středníků. V obou případech může být zakázaný znak obvykle zahrnut tak, že mu uniknete s předchozím zpětným lomítkem. Podpora Unicode se liší.

Rekurzivní případ definice s-expr je tradičně implementován pomocí buněk cons .

S-výrazy byly původně určeny pouze pro data, která mají být manipulována M-výrazy , ale první implementace Lispu byla interpretem kódování S-výrazů M-výrazů a programátoři Lispu si brzy zvykli používat S-výrazy pro oba kódy a data. To znamená, že Lisp je homoikonický ; to znamená, že primární reprezentací programů je také datová struktura v primitivním typu samotného jazyka.

Příklady datových S-výrazů

Vnořené seznamy lze zapsat jako S-výrazy: ((milk juice) (honey marmalade))je dvouprvkový S-výraz, jehož prvky jsou také dvouprvkové S-výrazy. Zápis oddělený mezerami používaný v Lispu (a tomto článku) je typický. Konce řádků (znaky nového řádku) se obvykle kvalifikují jako oddělovače.

Toto je jednoduchá bezkontextová gramatika pro malou podmnožinu angličtiny psané jako S-výraz (Gazdar/Melish, Natural Language Processing in Lisp), kde S = věta, NP = podstatné jméno fráze, VP = slovesná fráze, V = sloveso : 

(((S) (NP VP))
 ((VP) (V))
 ((VP) (V NP))
 ((V) died)
 ((V) employed)
 ((NP) nurses)
 ((NP) patients)
 ((NP) Medicenter)
 ((NP) "Dr Chan"))

Příklad S-výrazů zdrojového kódu

Programový kód lze zapsat do výrazů S, obvykle pomocí předponové notace.

Příklad v Common Lisp : 

(defun factorial (x)
   (if (zerop x)
       1
       (* x (factorial (- x 1)))))

S-výrazy lze číst v Lispu pomocí funkce READ. READ přečte textovou reprezentaci výrazu S a vrátí data Lisp. K výstupu S-výrazu lze použít funkci PRINT. Výstup pak lze přečíst pomocí funkce READ, když všechny vytištěné datové objekty mají čitelnou reprezentaci. Lisp má čitelné reprezentace čísel, řetězců, symbolů, seznamů a mnoha dalších datových typů. Programový kód lze formátovat jako pěkně vytištěné S -výrazy pomocí funkce PPRINT (poznámka: se dvěma Ps, zkratka pretty -print).

Programy Lisp jsou platné výrazy S, ale ne všechny výrazy S jsou platné programy Lisp. (1.0 + 3.1)je platný S-výraz, ale není platným programem Lisp, protože Lisp používá notaci prefixu a číslo s plovoucí desetinnou čárkou (zde 1,0) není platné jako operace (první prvek výrazu).

S-výraz, kterému předchází jedna uvozovka, jako v 'x, je v tomto případě syntaktický cukr pro citovaný S-výraz(quote x) .

Analýza

S-výrazy jsou často srovnávány s XML : klíčový rozdíl je v tom, že S-výrazy mají pouze jednu formu omezení, tečkovaný pár, zatímco XML tagy mohou obsahovat jednoduché atributy, jiné tagy nebo CDATA , každý s jinou syntaxí. Pro jednoduché případy použití jsou výrazy S jednodušší než XML, ale pro pokročilejší případy použití má XML dotazovací jazyk, tzv. XPath, mnoho nástrojů a knihovny třetích stran, které zjednodušují manipulaci s daty XML.

Standardizace

Standardy pro některé programovací jazyky odvozené od Lisp zahrnují specifikaci pro jejich syntaxi S-výrazu. Patří sem Common Lisp (standardní dokument ANSI ANSI INCITS 226-1994 (R2004)), schéma (R5RS a R6RS ) a ISLISP .

Rivestova varianta

Viz také: Kanonické S-výrazy

V květnu 1997 předložil Ron Rivest internetový koncept, který měl být považován za zveřejněný jako RFC . Návrh definoval syntaxi založenou na výrazech Lisp S, ale určenou spíše pro ukládání a výměnu dat pro všeobecné účely (podobně jako XML ), než konkrétně pro programování. Nikdy nebyl schválen jako RFC, ale od té doby byl citován a používán jinými RFC (např. RFC 2693) a několika dalšími publikacemi. Původně byl určen pro použití v SPKI .

Rivestův formát definuje S-výraz buď jako oktetový řetězec (řada bajtů ), nebo jako konečný seznam dalších S-výrazů. Popisuje tři výměnné formáty pro vyjádření této struktury. Jedním z nich je „pokročilý přenos“, který je z hlediska formátování velmi flexibilní a je syntakticky podobný výrazům ve stylu Lisp, ale nejsou totožné. Pokročilý transport například umožňuje doslovné znázornění řetězců oktetů (délka řetězce následovaná dvojtečkou a celým nezpracovaným řetězcem), citovaná forma umožňující únikové znaky, hexadecimální , Base64 nebo umístěná přímo jako „token“, pokud splňuje určité podmínky. (Tokeny Rivest se liší od tokenů Lisp v tom, že ty první jsou jen pro pohodlí a estetiku a jsou zpracovány přesně jako ostatní řetězce, zatímco ty druhé mají specifický syntaktický význam.)

Rivestův návrh definuje kanonickou reprezentaci „pro účely digitálního podpisu“. Má být kompaktní, snáze analyzovatelný a jedinečný pro jakýkoli abstraktní S-výraz. Umožňuje pouze doslovné řetězce a zakazuje mezery jako formátování mimo řetězce. Nakonec je zde „základní transportní reprezentace“, která je buď kanonickou formou, nebo je kódována jako Base64 a je obklopena složenými závorkami , přičemž druhá z nich je určena k bezpečnému přenosu kanonicky kódovaného výrazu S v systému, který může měnit mezery (např. E-mail systém, který má 80 znaků široké řádky a obaluje cokoli delšího než to).

Tento formát nebyl široce upraven pro použití mimo SPKI (někteří uživatelé jsou GnuPG , libgcrypt, Nettle a GNU lsh). Webová stránka Rivest S-expressions poskytuje zdrojový kód C pro analyzátor a generátor (k dispozici pod licencí MIT ), který lze přizpůsobit a integrovat do jiných programů. Kromě toho neexistují žádná omezení při nezávislé implementaci formátu.

Viz také

Reference

externí odkazy