Kanoniczne S-wyrażenia

Kanoniczne wyrażenie S (lub csexp ) to forma kodowania binarnego podzbioru ogólnego wyrażenia S (lub sexp). Został zaprojektowany do użytku w SPKI , aby zachować moc S-wyrażeń i zapewnić kanoniczną formę dla aplikacji, takich jak podpisy cyfrowe , jednocześnie osiągając zwartość formy binarnej i maksymalizując szybkość analizowania.

Konkretny podzbiór ogólnych wyrażeń S mających zastosowanie tutaj składa się z atomów , które są ciągami bajtów i nawiasów używanych do rozdzielania list lub list podrzędnych. Te S-wyrażenia są w pełni rekurencyjne.

Podczas gdy wyrażenia S są zwykle kodowane jako tekst, ze spacjami oddzielającymi atomy i znakami cudzysłowu używanymi do otaczania atomów zawierających spacje, podczas korzystania z kodowania kanonicznego każdy atom jest kodowany jako ciąg bajtów z prefiksem długości. Żadne spacje oddzielające sąsiednie elementy na liście są niedozwolone. Długość atomu jest wyrażona jako liczba dziesiętna ASCII, po której następuje znak „:”.

Przykład

Seksp

(to „kanoniczne wyrażenie S” ma 5 atomów)

staje się csexp

(4:this22:Canonical S-expression3:has1:55:atomy)

Żadne cudzysłowy nie są wymagane do zmiany znaku spacji wewnątrz atomu „Kanoniczne wyrażenie S”, ponieważ przedrostek długości wyraźnie wskazuje na koniec atomu. Nie ma białych znaków oddzielających atom od następnego elementu na liście.

Nieruchomości

Wyjątkowość kodowania kanonicznego : zakaz spacji między elementami listy i zapewnienie tylko jednego sposobu kodowania atomów zapewnia, że każde S-wyrażenie ma dokładnie jedną zakodowaną formę. W ten sposób możemy zdecydować, czy dwa wyrażenia S są równoważne, porównując ich kodowanie.
Obsługa danych binarnych : Atomy mogą być dowolnym ciągiem binarnym. Tak więc kryptograficzna wartość skrótu lub moduł klucza publicznego, który w przeciwnym razie musiałby być zakodowany w base64 lub innym kodowaniu nadającym się do drukowania, można wyrazić w csexp jako bajty binarne.
Obsługa zakodowanych informacji z tagowaniem typu : csexp zawiera konstrukcję inną niż S-wyrażenie do wskazywania kodowania ciągu znaków, gdy to kodowanie nie jest oczywiste. Każdy atom w csexp może być poprzedzony pojedynczym atomem w nawiasach kwadratowych – na przykład „[4:JPEG]” lub „[24:text/plain;charset=utf-8]”.

Interpretacja i ograniczenia

Podczas gdy csexp generalnie zezwala na puste listy, puste atomy itd., niektóre zastosowania csexp nakładają dodatkowe ograniczenia. Na przykład csexps używane w SPKI mają jedno ograniczenie w porównaniu z csexps ogólnie: każda lista musi zaczynać się od atomu, dlatego nie może być pustych list.

Zazwyczaj pierwszy atom listy jest traktowany tak, jak traktuje się nazwę elementu w XML .

Porównania z innymi kodowaniami

W powszechnym użyciu są inne kodowania:

XML
ASN.1
JSON (i YAML , który zawiera „JSON jako oficjalny podzbiór”, z nadzbiorem, który ma być bardziej czytelny dla człowieka ).

Ogólnie rzecz biorąc, csexp ma parser o jeden lub dwa rzędy dziesiętne mniejszy niż XML lub ASN.1. ^{[ potrzebne źródło ]} Ten mały rozmiar i odpowiadająca mu szybkość ^{[ potrzebne źródło ]} dają csexp jego główną zaletę. Oprócz zalet analizowania istnieją inne różnice.

csexp kontra XML

csexp i XML różnią się tym, że csexp jest formatem reprezentacji danych, podczas gdy XML zawiera format reprezentacji danych, a także mechanizm schematu. W ten sposób XML można „skonfigurować” dla określonych rodzajów danych, które są zgodne z pewną gramatyką (powiedzmy HTML , ATOM , SVG , MathML lub nowe w razie potrzeby). Posiada języki do definiowania gramatyki dokumentu: DTD jest zdefiniowany przez sam standard XML, podczas gdy XSD , RelaxNG i Schematron są powszechnie używane z XML w celu uzyskania dodatkowych funkcji, a XML może również działać bez schematu. Dane csexp mogą oczywiście być obsługiwane przez schematy zaimplementowane na wyższym poziomie, ale same w sobie nie zapewniają takiego mechanizmu.

Jeśli chodzi o znaki i bajty, „łańcuch” csexp może mieć dowolną sekwencję bajtów (ze względu na przedrostek długości każdego atomu), podczas gdy XML (podobnie jak zwykłe wyrażenia S schematu, JSON i literały w językach programowania) wymaga alternatywnych reprezentacje kilku znaków (takich jak „<” i większość znaków sterujących). Nie ma to jednak wpływu na zakres struktur i semantyki, które można przedstawić. XML zapewnia również mechanizmy określające, w jaki sposób dana sekwencja bajtów ma być interpretowana: Powiedzmy, jako Unicode UTF-8 , plik JPEG lub liczbę całkowitą; csexp pozostawia takie rozróżnienia mechanizmom zewnętrznym.

Na najbardziej podstawowym poziomie zarówno csexp, jak i XML reprezentują drzewa (podobnie jak większość innych zewnętrznych reprezentacji). Nie jest to zaskakujące, ponieważ XML można opisać jako inaczej interpunkowaną formę wyrażeń S podobnych do LISP-a lub odwrotnie.

Jednak XML zawiera dodatkową semantykę, która jest zwykle osiągana w csexp za pomocą różnych konwencji, a nie jako część języka. Po pierwsze, każdy element XML ma nazwę (aplikacje csexp zwykle używają do tego pierwszego elementu potomnego każdego wyrażenia). Po drugie, XML zapewnia typowanie danych, po pierwsze za pomocą gramatyki schematu. Schemat może jednak również rozróżniać liczby całkowite, łańcuchy znaków, obiekty danych z typami (np. JPEG) oraz (zwłaszcza z XSD ) innymi typami).

Element XML może również mieć atrybuty , konstrukcję, której csexp nie udostępnia. Aby reprezentować dane XML w csexp, należy wybrać reprezentację takich atrybutów; oczywistym jest zarezerwowanie drugiego elementu w każdym S-wyrażeniu dla listy par (nazwa-wartość), analogicznie do listy skojarzeń LISP-a . Atrybuty XML ID i IDREF nie mają odpowiedników w csexp, ale mogą być łatwo zaimplementowane przez aplikację csexp.

Wreszcie element XML może zawierać komentarze i/lub instrukcje przetwarzania. csexp nie ma konkretnych odpowiedników, ale ich przedstawienie jest trywialne, wystarczy zarezerwować nazwę dla każdego z nich. Na przykład nazwanie ich „*COM” i „*PI” (znak „*” zapobiega kolizjom z nazwami typów elementów XML):

(4:*COM15:Tekst komentarza) (3:*PI6:target11:font="helv")

Zarówno csexp, jak i XML są w pełni rekurencyjne.

Pierwszy atom na liście csexp, zgodnie z konwencją, z grubsza odpowiada nazwie typu elementu XML w identyfikowaniu „typu” listy. Jednak w csexp może to być dowolny atom w dowolnym kodowaniu (np. JPEG, ciąg Unicode, plik WAV , …), podczas gdy nazwy elementów XML są identyfikatorami ograniczonymi do określonych znaków, jak identyfikatory języka programowania. metoda csexp jest oczywiście bardziej ogólna; z drugiej strony określenie, w jakim kodowaniu znajduje się taki element, a tym samym sposób jego interpretacji, zależy tylko od konwencji konkretnego użytkownika, co oznacza, że aplikacja csexp musi zbudować takie konwencje dla siebie, w kodzie, dokumentacji itd. .

Podobnie atomy csexp są binarne (składają się z prefiksu długości, po którym następują całkowicie dowolne bajty ), podczas gdy XML jest zaprojektowany tak, aby był czytelny dla człowieka (choć prawdopodobnie mniej niż JSON lub YAML ) – więc dowolne bajty w XML muszą być jakoś zakodowane (na przykład na przykład obraz bitmapowy można dołączyć przy użyciu base64 ). Oznacza to, że przechowywanie dużych ilości nieczytelnych informacji w nieskompresowanym formacie XML zajmuje więcej miejsca; z drugiej strony przetrwa translację między alternatywnymi zestawami znaków (w tym transmisję przez hosty sieciowe, które mogą stosować różne zestawy znaków, konwencje końca linii itp.).

Sugerowano, że XML „scala” sekwencję łańcuchów w jednym elemencie w jeden ciąg, podczas gdy csexp pozwala na sekwencję atomów na liście, a atomy te pozostają oddzielone od siebie; ale to jest niepoprawne. Podobnie jak S-expressions i csexp, XML ma pojęcie „sekwencji łańcuchów” tylko wtedy, gdy „ciągi” są w jakiś sposób rozdzielone:

 <s>Ciąg A</s><s>Ciąg B</s> kontra <s>Ciąg ACiąg B</s>

 ("Ciąg A" "Ciąg B") a ("Ciąg ACiąg B")

 (8: Ciąg A8: Ciąg B) kontra (16: Ciąg A Ciąg B)

csexp vs. ASN.1

ASN.1 to popularna forma kodowania binarnego. Jednak wyraża tylko składnię (typy danych), a nie semantykę. Dwie różne struktury – każda SEKWENCJA dwóch LICZB CAŁKOWITYCH – mają identyczne reprezentacje na przewodzie (poza specjalnymi znacznikami do ich rozróżnienia). Aby przeanalizować strukturę ASN.1, należy powiedzieć parserowi, jakiego zestawu struktur się oczekuje, a parser musi dopasować typ analizowanych danych do opcji struktury. Zwiększa to złożoność parsera ASN.1.

Struktura csexp zawiera pewne wskazówki dotyczące własnej semantyki (zakodowanej w nazwach elementów), a parser struktury csexp nie dba o to, jaka struktura jest analizowana. Po przeanalizowaniu wyrażenia w formacie drutu do postaci wewnętrznego drzewa (podobnego do DOM XML), konsument tej struktury może sprawdzić, czy jest zgodne z oczekiwaniami. Dokument XML bez schematu działa pod tym względem podobnie jak csexp, podczas gdy dokument XML z nimi może działać bardziej jak ASN.1.

Linki zewnętrzne

Uwagi i odniesienia